Learning Curves for Gaussian Process Regression with Power-Law Priors and Targets
Authors: Hui Jin
Pradeep Kr. Banerjee
Guido Montufar
Venue: ICLR 2022 Poster (2022)
Keywords: Gaussian process regression
kernel ridge regression
generalization error
power law
neural tangent kernel

Abstract: We characterize the power-law asymptotics of learning curves for Gaussian process regression (GPR) under the assumption that the eigenspectrum of the prior and the eigenexpansion coefficients of the target function follow a power law. Under similar assumptions, we leverage the equivalence between GPR and kernel ridge regression (KRR) to show the generalization error of KRR. Infinitely wide neural networks can be related to GPR with respect to the neural network GP kernel and the neural tangent kernel, which in several cases is known to have a power-law spectrum. Hence our methods can be applied to study the generalization error of infinitely wide neural networks. We present toy experiments demonstrating the theory.

Published as a conference paper at ICLR 2022
LEARNING CURVES FOR GAUSSIAN PROCESS REGRESSION WITH POWER-LAW PRIORS AND TARGETS
Hui Jin UCLA
Pradeep Kr. Banerjee MPI MiS
Guido Montúfar UCLA & MPS
huijingucl edu
pradeepêmis s www..pp....... de
montufa r@math. uel edu
ABSTRACT
We characterize the power-law asymptotics of learning curves for Gaussian process regression (GPR) under the assumption that the eigenspectrum of the prior and the eigenexpansion coefficients of the target function follow a power law. Under similar assumptions, we leverage the equivalence between GPR and kernel ridge regression (KRR) to show the generalization error of KRR. Infinitely wide neural networks can be related to GPR with respect to the neural network GP kernel and the neural tangent kernel, which in several cases is known to have a power-law spectrum. Hence our methods can be applied to study the generalization error of infinitely wide neural networks. We present toy experiments demonstrating the theory.
INTRODUCTION
Gaussian processes (GPs) provide flexible and interpretable framework for learning and adaptive inference, and are widely used for constructing prior distributions in non- con-parametric Bayesian learning. From application perspective, one crucial question is how fast do GPs learn, i.e., how much training data needed to achieve a certain level of generalization performance. Theoretically, this is addressed by analyzing so-called "learning curves". which describe the generalization error function of the training set size n. The rate at which the curve approaches zero determines the difficulty of learning tasks and conveys important information about the asymptotic performance of GP learning algorithms. In this paper, we study the learning curves for Gaussian process regression. Our main result characterizes the asymptotics of the generalization error in cases where the eigenvalues of the GP kernel and the coefficients of the eigenexpansion of the target function have power-law decay. In the remainder of this introductory section, we review related work and outline our main contributions.
Gaussian processes A GP model is a probabilistic model on an diinitt-dimensionall parameter space (Williams and Rasmussen, 2006; Orbanz and Teh, 2010). In GP regression (GPR), for example, this space can be the set of all continuous functions. Assumptions about the learning problem are encoded by way a prior distribution over functions, which gets transformed into a posterior distribution given some observed data. The mean of the posterior is then used for prediction. The model uses only finite subset of the available parameters to explain the data and this subset can grow arbitrarily large as more data are observed. In this sense, GPs are mnon-parametric" and contrast with parametric models, where there is a fixed number of parameters. For regression with Gaussian noise, a major appeal of the GP formalism is that the posterior analytically tractable. GPs are also one important part in learning with kernel machines (Kanagawa et al., 201 8) and modeling using GPs has recently gained considerable traction in the neural network community.
Neural networks and kernel learning From a GP viewpoint, there exists a well known correspon- dence between kernel methods and infinite neural networks (NNs) first studied by Neal (1996). Neal showed that the outputs of randomly initialized one-hidden layer neural network (with appropriate scaling of the variance of the initialization distribution) converges to a GP over functions in the limit of an infinite number of hidden units. Follow-up work extended this correspondence with analytical expressions for the kernel covariance for shallow NNs by Williams (1997), and more recently for deep celly-coneected NNs (Lee al., 2018; de G. Matthews et al., 2018), convolutional NNs with many channels (Novak et al., 2019; Garriga- Alonso et al., 2019), and more general architectures (Yang, 2019). The correspondence enables exact Bayesian inference in the associated GP model for

---

Published as a conference paper at ICLR 2022
infinite-wiie width NNs regression tasks and has led to some recent breakthroughs in understanding of overparameterized NNs (Jacot et al., 2018; Lee et al., 2019; Arora et al., 2019; Belkin et al., 2018; 88; Daniely et al., 2016; Yang and Salman, 2019; Bietti and Mairal, 2019). The most prominent kernels associated with inftnite-width NNs are the Neural Network Gaussian Process (NNGP) kernel (Lee al., 2018; de G. Matthews et al., 2018), and the Neural Tangent Kernel (NTK) (Jacot et al., 2018) Empirical studies have shown that inference with such infinite network kernels is competitive with standard gradient descent-basee optimization for funnecco architectures (Lee et al., 2020).
Learning curves large-scale empirical characterization of the generalization performance of state-of-the-art deep NNs showed that the associated learning curves often follow power law of the form with the exponent 3 ranging between 0.07 and 0.35 depending on the data and the algorithm (Hestnss et al., 2017; Spigler et al., 2020). Power-law asymptoties of learning curves have been theoretically studied in early works for the Gibbs learning algorithm (Amari et al., 1992; Amari and Murata, 1993; Haussler et al., 1996) that showed generalization error scaling with exponent 3 = 0.5, 1 or 2 under certain assumptions. More recent results from statistical learning theory characterize the shape of learning curves depending on the properties of the hypothesis class (Bousquet et al., 2021). In the context of GPs, approximations and bounds on learning curves have been investigated in several works (Sollich, 1999; Sollich and Halees, 2002: Sollich, 2001: Opper and Vivarelli, 1999; Opper and Malzahn, 2002; Williams and Vivarelli, 2000; Malzahn and Opper, 2001;;b; Seeger et al., 2008; Van Der Vaart and Van Zanten, 2011; Le Gratiet and Garnier, 2015), with recent extensions to kernel regression from spectral bias perspective (Bordelon et al., 2020; Canatar et al., 2021). For review on learning curves in relation to its shape and monotonicity, see Loog et al. (2019); Viering et al. (2019); Viering and Loog (2021). A related but complementary line of work studies the convergence rates and posterior consistency properties of Bayesian non- non-parametric models (Barron, 1998; Sceger et al., 2008; Van Der Vaart and Van Zanten, 2011).
Power-law decay of the GP kernel eigenspectrum The rate of decay of the eigenvalues of the GP kernel conveys important information about its smoothness. Intuitively, if a process is "rough" with more power at high frequencies, then the eigenspectrum decays more slowly. On the other hand, kernels that define smooth processes have a fast-decaying eigenspectrum (Stein, 2012; Williams and Rasmussen, 2006). The precise eigenvalues (Ap) of the operators associated to many kernels and input distributions are not known explicitly, except for a few special cases (Williams and Rasmussen, 2006). Often, however, the asymptotic properties are known. The asymptotic rate of decay of the eigenvalues of stationary kernels for input distributions with bounded support is well understood (Widom, 1963; Ritter et al., 1995). Ronen et al. (2019) showed that for inputs distributed uniformly on hypersphere, the eigenfunctions of the arc-cosine kernel are spherical harmonics and the eigenvalues follow a power-law decay. The spectral properties of the NTK are integral to the analysis of training convergence and generalization of NNs, and several recent works empirically justify and rely power law assumption for the NTK spectrum (Bahri et al., 2021; Canatar et al., 2021; Lee et al., 2020; Nitanda and Suzuki, 2021). Velikanov and Yarotsky (2021) showed that the asymptotics of the NTK of infinitely wide shallow ReLU networks follows power-law that is determined primarily by the singularities of the kernel and has the form Ao xp" with a 1+ 1 where d is the input dimension.
d.
Asymptotics the generalization error of kernel ridge regression (KRR) There is a well known equivalence between GPR and KRR with the additive noise in GPR playing the role of regularization in KRR (Kanagawa et al., 2018). Analysis of the decay rates of the excess generalization error of KRR has appeared in several works, e.g, in the noiseless case with constant regularization (Bordelon et al., 2020; Spigler et al., 2020; Jun et al., 2019), and the noisy optimally regularized case (Caponnetto and De Vito, 2007: Steinwart et al., 2009; Fischer and Steinwart, 2020) under the assumption that the kernel eigenspectrum, and the eigenexpansion coefficients of the target function follow a power law. These assumptions, which are often called resp. the capacity and source conditions are related to the effective dimension of the problem and the difficulty of learning the target function (Caponnetto and De Vito, 2007; Blanchard and Mücke, 2018). Cui et al. (2021) present a unifying picture of the excess error decay rates under the capacity and source conditions in terms of the interplay between noise and regularization illustrating their results with real datasets.
Contributions In this work, we characterize the asymptotics of the generalization error of GPR and KRR under the capacity and source conditions. Our main contributions follows:
2

---

Published as a conference paper at ICLR 2022
When the eigenspectrum of the prior decays with rate a and the eigenexpansion coefficients of the target function decay with rate B, we show that with high probability over the draw of n input samples, the negative ong-aaginal likelihood behaves as O( 1-28 +1)) (Theorem 7) and the generalization error behaves as (n. 2 - (Theorem 9). In the special case that the model is correctly specified, i.e., the GP prior is the true one from which the target functions are actually generated, our result implies that the generalization error behaves as O( recovering as a special case a result due to Sollich and Halees (2002) (vide Remark 10).
Under similar assumptions as in the previous item, we leverage the equivalence between GPR and KRR to show that the excess generalization error of KRR behaves as max result implies that the
(Theorem 12). In the noiseless case with constant regularization, recovering as a special case a result due to Bordelon et al.
generalization error behaves as (n 1-28 (2020). Specializing to the case of KRR with Gaussian design, we recover a special case result due to Cui et al. (2021) (vide Remark 14).
For the unrealizable case, i.e., when the target function is outside the span of the eigenfunctions with positive eigenvalues, we show that the generalization error converges to constant.
We present few toy experiments demonstrating the theory for GPR with arc-cosine kernel without bi- ases (resp. with biases) which is the conjugate kernel of an infinitely wide shallow network with two in- puts and one hidden layer without biases (resp. with biases) (Cho and Saul, 2009; Ronen al., 2019).
2 BAYESIAN LEARNING AND GENERALIZATION ERROR FOR GPs
In GP regression, our goal is to learn a target function : S + R between an input x E Q and output y IR based on training samples D {(r,, ))) We consider an additive noise model 3/1 fzz + C₁ where E; iid. o( If p denotes the marginal density of the inputs Iy then the pairs (xz, 3r) are generated according to the density q(x, y) = p(z ((z)q()( where ((gl)))=(((l(())))ce We assume that there a prior distribution H. on f which defined as a zero-mean GP with continuous and bounded covariance function k2 x2 + IR, i.e., f ~ (0.k). This means that for any finite set x (ZI,.....i )²= the random vector f(x) = f the multivariate normal distribution N K) with covariance matrix K,, = (k(z,, (), ER By Bayes' rule, the posterior distribution over ff given the training data is given by
follows
(II,) z(D,)
I ( (dod))))) 1=1
where II is the prior distribution, Z(D,) / likelihood model evidence and model the sample variance used in GPR. In practice, we do not know the exact value of Otree and so our choice of mmndel can be different from True- The GP prior and the Gaussian noise assumption allows for exact Bayesian inference and the posterior distribution over functions is again GP with mean and covariance function given by
model (ff is the marginal
m(x) = KT (K, + moddel -n) y'
b(c,a")=((t;,) KT, (Kn +o o model In) K Maaa,, EΩ,
(2)
where Kxr (K(2,,.),....(((,,...)) 2.23-24).
T and y (y1,...,,)) ER" (Williams and Rasmussen, 2006, Eqs.
The performance of GPR depends how well the posterior approximates f as the number of training samples n tends to infinity. The distance of the posterior to the ground truth can be measured in various ways. We consider two such measures, namely the Bayesian generalization error (Seeger et al., 2008; Haussler and Opper, 1997; Opper and Vivarelli, 1999) and the excess mean squared error (Sollich and Halees, 2002: Le Gratiet and Garnier, 2015; Bordelon et al., 2020; Cui et al., 2021).
Definition 1 (Bayesian generalization error). The Bayesian generalization error is defined as the Kullback-Leibler divergence between the true density q(y|z) and the Bayesian predictive density Pn ( ( Dn)
G(D,)= ((x.)))oo g(v1x) dxdy.
(3)
(n)
3

---

Published as a conference paper at ICLR 2022
A related quantity of interest is the stochastic complexity (SC), also known as the free energy, which is just the negative log marginal likelihood. We shall primarily be concerned with a normalized version of the stochastic complexity which is defined follows:
z(D))
-log Ny (Z)) (dllo(f)
Fd (D,))) -lo -o0 1I:-1900 mi)
(4)
II= 10 (2))
The generalization error (3) can be expressed in terms of the normalized SC as follows (Watanabe, 2009, Theorem 1.2):
G(D,) = (e.. (D
(5)
where 1 (
is obtained by augmenting D,, with a test point (In+1-0n+1).
If we only wish measure the performance of the mean of the Bayesian posterior, then we can use the excess mean squared error:
Definition (Excess mean squared error). The excess mean squared error is defined as
M (D.) = (e.,..1.0 ()((+++))) 1e 1--++++1** -o - EErat (m( [1n+1))² (6)
Proposition 3 (Normalized stochastic complexity for GPR). Assume that o = = The
=0².
normalized SC Ft (D,, for GPR with prior (0,k)) is given as
FO = (In =2)++ y (In 51 )
y 2n f (xx(x))),
(7)
where 6= 6= (e1,,...,, The expectation of the normalized SC w.r.l. the noise e. given as
E, F (Dx) logdee (In (T - (In -I (x
f(x) (In )x) f(x).
(8)
This is basic result and has applications in relation to model selection in GPR (Williams and Rasmussen, 2006). For completeness, we give a proof of Proposition 3 in Appendix B. Seeger et al. (2008, Theorem 1) gave upper bound on the normalized stochastic complexity for the case when lies in the reproducing kernel Hilbert space (RKHS) of the GP prior. It well known, however, that sample paths of GP almost surely fall outside the corresponding RKHS (Van Der Vaart and Van Zanten, 2011) limiting the applicability of the result.
We next derive the asymptotics of (D,), the expected generalization error GDD,) = E. Mo-1) 1o -1, and the excess mean squared error EE M (D.).
ASYMPTOTIC ANALYSIS OF GP REGRESSION WITH POWER-LAW PRIORS
We begin by introducing some notations and assumptions. We assume that f (2,,p). By the generalization of Mercer's 's theorem (Steinwart and Scovel, 2012, Corollary 3.2), the covariance
function of the GP prior can be decomposed as k( x2) Ep= 2 (2) 0 (x2) p-almost surely, where (x)( p>1 are the eigenfunctions of the operator L2 (2, p) + I22 p): (t (s)d((s) and (Ap)r21 are the corresponding positive eigenvalues. We index the sequence of cigenvalues in decreasing order, that is a 2 A 2 > O. The target function f(x) is decomposed into the orthonormal set (p)()))))) and its orthogonal complement (dp(x):p21) as
f(x) Eupon +ood (oooh))) E p=l
(9)
where μ= (Ho. (p.... )rr are the coefficients of the decomposition, and (o( satisfies |/ (t)]12
I and dz(x)= E (1)( 2 13- For given sample inputs x, let (x) = (dp(21), )..., Sp (p(()))) )²² + (0u(x),01 (x).... &p (x).... and A= di............ppp....... Then the covariance matrix K₂ can
be written K, $T and the function values the sample inputs can be written as f(x)= -p.
We shall make the following assumptions in order to derive the power-law asymptotics of the normalized stochastic complexity and the generalization error of GPR:
Assumption 4 (Power law decay of eigenvalues). The eigenvalues (Ap)221 follow the power law
Cxp <A a Ypp1
(10)
where Cx. Cx and are three positive constants which satisfy 0< Cx SC and
4

---

Published as a conference paper at ICLR 2022
As mentioned in the introduction, this assumption, called the capacity condition, is fairly standard in kernel learning and is adopted in many recent works (Bordelon et al., 2020; Canatar et al., 2021; Jun et al., 2019; Bietti et al., 2021; Cui et al., 2021). Velikanov and Yarotsky (2021) derived the exact value of the exponent a when the kernel function has a homogeneous singularity on its diagonal, which is the case for instance for the arc-cosine kernel.
Assumption 5 (Power law decay of coefficients of decomposition). Let Cn > and 8 >>11/ 1/2 be positive constants and let (p: 1:21 be an increasing integer sequence such that sup;2 i (Pi+1- -P:) < co. The coefficients (pp)p21 of the decomposition (9) of the target function follow the power law
1upl S Cup Vp21 and
[pp, 1 CuPi -8 vi21.
(11)
Since f E (St,p) we have Ep=a U < 30. The condition 3 > 1/2 in Assumption 5 ensures that the sum Ep does not diverge. When the orthonormal basis (d)():)) is the Fourier basis the spherical harmonics basis, the coefficients (μp)p decay at least as fast as a power law so long as the target function f(x) satisfies certain smoothness conditions (Bietti and Mairal, 2019). Velikanov and Yarotsky (2021) gave examples of some natural classes of functions for which Assumption is satisfied, such as functions that have bounded support with smooth boundary and are smooth on the interior of this support, and derived the corresponding exponents B.
Assumption 6 (Boundedness of eigenfunctions). The eigenfunctions (ép(z))p20 satisfy
| xc CC and | S Cop",p21,
(12)
where Cs and T are two positive constants which satisfy T - 2
The second condition in (12) appears, for example, in Valdivia (2018, Hypothesis H₂) and is less restrictive than the assumption of uniformly bounded eigenfunctions that has appeared several other works in the GP literature, see, e.g., Braun (2006); Chatterji et al. (2019); Vakili et al. (2021).
Define
(I++ 016"" )
(D,,,) = 2 logdet [I, -A4²)
DA4"
1 I, (h--(xx
(13)
-1 T2(D,)) = 2// f(x)² (I+
$2g
f(x),
(14)
o²
(D = (en 1.
(D -D,)),
(15)
G2(D,) = (en (Tz(D (D.)))
(16)
and andE.C(D.)=G(DD))GGGG itively, Gi corresponds to the effect of the noise on the generalization error irrespective of the target func- tion f. whereas G2 corresponds to the ability of the model to fit the target function. As we will see next in Theorems 9 and 11. if a large, then the error associated with the noise smaller. When f contained in the span of the cigenfunctions (Øp p21, G2 decreases with increasing n. but if ff contains an orthogo- nal component, then the error remains constant and GP regression not able to learn the target function.
Using (8) and (5), we have E. (..
Intu-
3.1 ASYMPTOTICS OF THE NORMALIZED STOCHASTIC COMPLEXITY
We derive the asymptotics of the normalized SC (8) for the following two cases: μo = 0 and μu >> 0. When (4g 0, the target function f (x) lies in the span of all eigenfunctions with positive eigenvalues. Theorem 7 (Asymptotics of the normalized SC, μo 0). Assume that μt = 0 and and 6, with probability of least true o2 (11). Under Assumptions (28-11(---21) a-1-2r the expected 4n2 2a
model
1 1- n over sample inputs (z:)i where 0 S minf
normalized SC (8) has the asymptotic behavior:
F.Fo(D. (D,.) logdet (I+ A) 1 (I [ (I+ (T-(I+ - 20 T (I+ ( 11 (1+o(1))
1-28
( max
(17)
The complete proof of Theorem 7 is given in Appendix D.I. We give a sketch of the proof below. In the sequel, we use the notations O and θ to denote the standard mathematical orders and the notation Ô to suppress logarithmic factors.
5

---

Published as a conference paper at ICLR 2022
+T In Proof sketch of Theorem 7. By (8), (13) and (14) we have (D,) = (D,),, order to analyze the terms (D,) and Tz(D,), we will consider truncated versions of these quantities and bound the corresponding residual emror. Given truncation parameter R E N, let E TR be the truncated matrix of eigenfunctions evaluated at the R--1,
n = (do (x)),,(xx).....400
data points, An = (0.iag(,
E (R(++))((R+)) and pa (Ho./H1.....In)) ER
We define
the truncated version of 7 (Dn) as follows:
ar Tr,n(D,))= = logdot In *xARDR) 1Tr In-
(In @RARTR) )
(18)
Similarly, define PyR (0R+1(x), ( 0 ..),, ASR diag(AR RR-1 ... Apr ..... [n(()) = Σø (1)) fn(x) = (Jn(si), ..... [R(En)) [x((1) ʃ(x) [n(x), and f>a(x)= ((>_((r))....>>llll
The truncated version of T2(x)) is then defined as (i((x)(((n)) (In @
T2, (2,) 2े. fR(x)"
fR(x)².
(19)
The proof consists of three steps:
Approximation step: In this step, we show that the asymptotics of T I. resp. T2,R dominates that of the residuals, [ī, (D.)) Ti (D,) resp. (D,) (D.)) (see Lemma 32). This builds upon
TT
first showing that | mA> Rl2 - (max . 3 .R' R)) (see Lemma 25) and then
choosing n= +* where << 2=1-2r when have RA>>R>>R0 2 o Intuitively, the choice the truncation parameter is governed by the fact that X = O -)= =)== - ++
=onn" 1).
Decomposition step: In this step, we decompose Tn.n into a term independent of t and series forT2.r T2,R (see Lemma 34). This builds upon first showing using the Woodbury matrix identity (Williams and Rasmussen, 2006, $A.3) that
involving 8 R - nIRR and likewise for
(D,) (oogdet(IR- A T ( -AR
(20)
T2,n(Dn) (D,))= = In
p.n.
(21)
and then Taylor expanding the matrix inverse (O²IR + 2 in (20) and (21) to show that the & ieginndeendeent terms in the decomposition of Tı, and T2 are, respectively, +l An) Ir (In Ax))))) and 2 / ( 2/ AR)
un.
. Concentration step: Finally, we use concentration inequalities to show that these p independent terms dominate the series involving $ t -oa--1l. nz (see Lemma 35) when we have
Tr, (5logdet AR) Tr (I(RR-(IR++ = ())
O (n max - +1)),
2 -1, a a= -1.
n AR) P (1+0(1))) =
(logn),
The key idea is to consider the matrix A (I+ (I+ 1/2 / AR) 1/2 R and show that it concentrates around nA ) (see Corollary 22). Note that an ordinary application of the matrix Bernstein inequality to $ n yields 0 - O(R/T), which is not sufficient for our purposes, since this would give ((R/n)=ol =(n) only when a >>2. 2. In contrast, our results are valid for a>> and cover cases of practical interest, c.g., the NTK of infinitely wide shallow ReLU network (Velikanov and Yarotsky, 2021) and the arc-cosine kernels over high-dimensional hyperspheres (Ronen et al., 2019) that have 1 +O)), where is the input dimension.
Li
For Ho > 0, we note the following result:
Theorem 8 (Asymptotics of the normalized SC, Hu > 0). Assume Hi Loodel = - - = 0² = (1). Under Assumptions 4, 5 and 6, with probability of at least 1 1-n 9 over sample imputs (x.) where 0S < min 28-1
and
2 ,a) min a-1-21 28 }. the expected ---
normalized SC (8) has the asymplotic behavior:
(D,) 2 #g)+)(n))
The proof of Theorem 8 is given in Appendix D.I and follows from showing that when 1i0 > 0, To T2,R( (.,)) (2 (I 2 AR) "PR) (1 + o(1)) = 1 nnnn + o(n) (see Lemma 38), which dominates T, (Dx) and the residual (T2,n(D,)) (D.))T((D.)))

---

Published as a conference paper at ICLR 2022
3.2 ASYMPTOTICS OF THE BAYESIAN GENERALIZATION ERROR
In this section, we derive the asymptotics of the expected generalization error E,G (D..) by analyzing the asymptotics of the components GI (D,)) and G2 in resp. (15) and (16) for the following two cases: Mo = 0 and P4o > 0. First, we consider the case /o =
Theorem 9 (Asymptoties of the Bayesian generalization error, 140 - 0). Let Assumptions 4, 5, and 6 hold. Assume that μuu = 0 and model = -irue = x² (n²)) where 1 - 1427 <t< Then with
probability of at least 1 - 4I over sample inputs (xi) where 0 S <-< (0-11-2ri11+)(288)) the expectation of the Bayesian generalization error (3) W.E.. the noise e has the asymptotic behavior:
4n
GeG,),,)= (+) 20
TT(I+ n -A // (T+ -1
AA
On
(n max1
wid 2010
(22)
The proof of Theorem is given Appendix D.2. Intuitively, for a given t, the exponent (1=a)(1-t) in (22) captures the rate which the model suppresses the noise, while the exponent (1-28)(1-t) captures the rate at which the model learns the target function. A larger implies that the exponent (1-29)(1-t)
a
a
is smaller and is easier to learn the target. A larger a implies that the exponent (I=a)[-t) is smaller and the error associated with the noise is smaller well. A larger a, however, also implies that the exponent (1 (1-23)(1-t) is larger (recall that a 1 and B >> 1/2 by Assumptions and resp.), which means that it is harder to learn the target.
GP(O, k)), then using the Karhunen-Loöve expansion we have f(z) Ep= V Appupóp(z) where (up) are i.i.d. standard Gaussian variables. We can bound wp almost surely as |upl S Clogg, where C = supp21 logp is a finite constant. Comparing with the expansion of (x) in (9), we find that Hy = Xpuu = a0pp= -0pp-a/2+e) where e E> O is arbitrarily small. Choosing 3= ar/2-- e in (22), we have E. (DD,) =D. -1 matches that of earlier result due to Sollich and Halees (2002), where it shown that the asymptotic learning curve (as measured by the expectation of the excess mean squared error, E M (D,)) scales as n when the model is correctly specified, i.e., f is sample from the same Gaussian process (',(,,)) and the eigenvalues decay as power law for large i, Xa Ai-i
Remark 10. If f
This rate
For μl -0, we note the following result:
Theorem 11 (Asymptotics of the Bayesian generalization error, 14 > 0). Let Assumptions 4, 5, and 6 hold. Assume that yu > 0 and model = oirue 0² O(n') where 1 1+27 < <t<l 1. Then with
probability of at least 1 - 4 over sample inputs (x:))=n where S (o=(+))((1=)((23 4n
the expectation of the Bayesian generalization error (3) w.r.t. the noise E has the asymptotic behavior: E,G(D,)) 2 +o (1).
In general, if μoo > 0, then the generalization error remains constant when n + dc. This means that if the target function contains component in the kernel of the operator Lx, then GP regression is not able to learn the target function. The proof of Theorem is given in Appendix D.2.
3.3 ASYMPTOTICS OF THE EXCESS MEAN SQUARED ERROR
In this section we derive the asymptotics of the excess mean squared error in Definition
Theorem 12 (Asymptotics of excess mean squared error). Let Assumptions 4, 5, and 6 hold. Assume
maddl = O(n') where 1- a <1 1. Then with probability of least 1-n - over sample inputs
(x.) where 0 ja- (1+27) (1)3811)311) the excess mean squared error (6) has the asymptotic:
la
(.M(())=((+(f)
Lu mondal
(T((T+
-)- 11
2 A) __> 1
moddll
modal
1-a-t (1 (1-28)
+1[ +
n
A)
1ul =
max ftrue
model
when po= 0. and F. M (D.)= +o(1) (1), when pr > 0.
7

---

Published as a conference paper at ICLR 2022
The proof of Theorem 12 uses similar techniques Theorem and is given in Appendix D.3.
Remark 13 (Conrespondence with kernel ridge regression). The kernel ridge regression (KRR)
estimator arises as a solution to the optimization problem
i -aargmn 1 ((s(n)) + JEHL
(23)
where the hypothesis space Hy is chosen to be an RKHS, and X 0 is a regularization parameter. The solution to (23) is unique as a function, and is given by f(z) = KT (Kn + +dI which coincides with the posterior mean function m((x) of the GPR (1) if of = nn (Kanagawa et al., 2018, Proposition 3.6). Thus, the additive Gaussian noise GPR plays the role of regularization in KRR. Leveraging this well known equivalence between GPR and KRR we observe that Theorem 12 also describes the generalization error of KRR as measured by the excess mean squared error.
Remark 14. Cui al. (2021) derived the asymptotics of the expected excess mean- rrean-squard error for different regularization strengths and different scales of noise. In particular, for KRR with Gaussian 1/2
design where A R ( ........ (z) is assumed to follow Gaussian distribution N (O,AR)) and regularization x= =n where - 0 St Cui et al. (2021, Eq. 10) showed that
B (D,) = (max true
(24)
Let 8= n where 0 S la- (0-(4+2)11-)1200 4na
By Markov's inequality, this implies
that with probability of least 8, (e, O max -at 0-2010-9)
Tb
})
(1-281111) }). Theorem 12 improves upon this by showing that with prob- On''max 1 .2
ability of at least 1- we have an optimal bound E. M (Dn)= (
1-a-t (-2011-9) }).
Furthermore, contrast to the approach by Cui et al. (2021). we have no requirement on the distribution of (x)x. and hence our result is more generally applicable. For example, Theorem 12 can be applied to KRR with the are-cosine kernel when the Gaussian design assumption is not valid. In the noiseless setting (Otrue = 0) with constant regularization (t (1, Theorem 12 implies that the mean squared error behaves as O(n 1-28
This recovers a result in Bordelon et al. (2020, $2.2).
Our upper bound in Theorem 12 matches with the ones derived in (Steinwart et al., 2009; Fischer and Steinwart, 2020). Steinwart al. (2009) and Fischer and Steinwart (2020) also derived algorithm independent minmax lower bounds. In contrast to their results, our Theorem 12 gives lower bounds for different regularization strengths X.
4 EXPERIMENTS
We illustrate our theory on a few toy experiments. We let the input x be uniformly distributed on a unit circle, i.e., S= and (s The points on 5t1 can be represented by x= (cos@,sinn)) where (-(-)).) We use the order arc-cosine kernel function without bias, // bias (=1,)2)= (sing) (I- costp) where e = (x)) is the angle between 21 and Z2. Hence Assumption 4 is satisfied with a= 4. We consider the target functions in Table 1, which satisfy Assumption 5 with the indicated 8. and μ4 indicates whether the function lies in the span of eigenfunctions of the kernel. For each target we conduct GPR 20 times and report the mean and standard deviation of the normalized SC and the Bayesian generalization error in Figure 1, which agree with the asymptotics predicted in Theorems 7 and 9. The details of the experiments appear in Appendix A, where we also show more experiments confirming our theory for zero- and second- order arc-cosine kernels, with and without biases.
CONCLUSION
We described the learning curves for GPR for the case that the kernel and target function follow a power law. This setting is frequently encountered in kernel learning and relates to recent advances on neural networks. Our approach is based on a tight analysis of the concentration of the inner product of empirical eigenfunctions TT around n/. This allowed us to obtain more general results with more
8

---

Published as a conference paper at ICLR 2022
function value
B.G(D.)
f1
cos
+.00
0
(mn//4)
Onn 4/4)
/2
0
2
>0
(n)
((1)
f3
(10) 7 7/2)²
2
0
O 7+)
O(n 5/4)
T/2-6,
0 [0
f4
0
((n4/4)
O(n ((n
-2/2-0, 0,
Table I: Target functions used in the experiments for the first order arc-cosine kernel without bias k01)
"w/o bias? their values of 3 and μo. and theoretical rates for the normalized SC and the Bayesian generalization error from our theorems.
Nomalized SC
1:00
R198
Normaltzdd SC.
8.17 6,1735,44
Normaltred SC
16 8976
Normaltrad SC
10
2::0
Psperiment values
20
Experiment values
Experiment values
1.0
10
10
Experment values
10 Number of Samples
16 Number of Samples
Number of Samples
Number of Samples
10
Si 46454n-- Experiment
13.6961n-9.1118
Experiment valuen
10
Experiment values
20
6. 1.3946r--00
Experiment values
10
10
10
10a
10"
10 Samples
Number of
Number Samples
Number Semples
Figure 1: Normalized SC (top) and Bayesian generalization error (bottom) for GPR with the kernel x())
ww blas and the target functions in Table 1. The orange curves show the linear regression fit for the experimental values (in blue) the log Bayesian generalization error as a function of log n.
realistic assumptions than previous works. In particular, recovered some results on learning curves for GPR and KRR previously obtained under more restricted settings (vide Remarks 10 and 14).
We showed that when 2 a/2. meaning that the target function has compact representation in terms of the eigenfunctions of the kernel, the learning rate as good as in the correctly specified case. In interpret (3 from spectral bias perspective. When 1 < 7. the
addition, our result allows larger the value of B3, the faster the decay of the generalization error. This implies that low-frequency functions are learned faster in terms of the number of training data points.
By leveraging the equivalence between GPR and KRR, we obtained a result on the generalization error of KRR. In the infinite-width limit, training fully-connected deep NNs with gradient descent and infinitesimally small learning rate under least-squared loss is equivalent to solving KRR with respect to the NTK (Jacot al., 2018: Lee al., 2019; Domingos, 2020), which several cases is known to have a power-law spectrum (Velikanov and Yarotsky, 2021). Hence our methods can be applied to study the generalization error of infinitely wide neural networks. In future work, would be interesting to estimate the values of a and / for the NTK and the NNGP kernel of deep fully-connected or convolutional NNs and real data distributions and test our theory in these cases. Similarly, it would be interesting to consider extensions finite width kernels.
ACKNOWLEDGMENT
This project has received funding from the European Research Council (ERC) under the EU's Horizon 2020 research and innovation programme (grant agreement n" 757983).

---

Published as a conference paper at ICLR 2022
REFERENCES
S. Amari and N. Murata. Statistical theory of learning curves under entropic loss criterion. Neural Computaation ((1 400):140-553, 1993.
S. Amari, N. Fujita, and S. Shinomoto. Four types of learning curves. Neural Computation, 4(4): 605-618, 1992.
S. Arora, S. S. Du, W. Hu, Z. Li, R. R. Salakhutdinov, and R. Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems, volume 32, pages 8139-8148, 2019.
Y. Bahri, E. Dyer, J. Kaplan, J. Lee, and U. Sharma. Explaining neural scaling laws. arXiv preprint arXiv:2102.06701, 2021.
A. R. Barron. Information-tiee theorrttc characterization of Bayes performance and the choice of priors in parametric and nonparametric problems. In D. A. Bernardo J., Berger J. and S. A., editors, Bayesian statistics, volume 6, pages 27-52. Oxford University Press, 1998.
M. Belkin, S. Ma, and S. Mandal. To understand deep learning we need to understand kernel learning. In Proceedings of the 35th International Conference Machine Learning (ICML), pages 541-549, 2018.
A. Bietti and J. Mairal. On the inductive bias of neural tangent kernels. In Advances in Neural Information Processing Systems, volume 32, pages 22873122844 2019.
A. Bietti, L. Venturi, and J. Bruna. On the sample complexity of learning with geometric stability. arXiv preprint 2 1010060019958 2021.
G. Blanchard and N. Mücke. Optimal rates for regularization of statistical inverse learning problems. Foundations of Computational Mathematics, 18(4):971-1013, 2018.
B. Bordelon, A. Canatar, and C. Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In Proceedings of the 37th International Conference Machine Learning (ICML), pages 1024-1034, 2020.
O. Bousquet, S. Hanneke, S. Moran, R. van Handel, and A. Yehudayoff. A theory of universal learning. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 532-541, 2021.
M. L. Braun. Accurate error bounds for the eigenvalues of the kernel matrix. The Journal of Machine Learning Research, 1:2303-2328, 2006.
A. Canatar, B. Bordelon, and C. Pehlevan. Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks. Nature communications, 12(1):1-12,2021
A. Caponnetto and E. De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):311336, 2007.
N. Chatterji, A. Pacchiano, and P. Bartlett. Online learning with kernel losses. In Proceedings of the
36th International Conference on Machine Learning (ICML), pages 971-980, 2019.
Y. Cho and L. K. Saul. Kernel methods for deep learning. In Advances in Neural Information Processing Systems, volume 22, pages 342-350, 2009.
H. Cui, B. Loureiro, F. Krzakala, and L. Zdeborová. Generalization enror rates in kernel regression: The crossover from the noiseless to noisy regime. arXiv preprint 2rXiv:2105.1500. 2021.
A. Daniely, R. Frostig, and Y. Singer. Toward deeper understanding of neural networks: The power of initialization and a dual view on expressivity. In Advances Neural Information Processing Systems, volume 29, pages 2253-2261. 2016.
10

---

Published as a conference paper at ICLR 2022
A. G. de G. Matthews, J. Hron, M. Rowland, R. E. Turner, and Z. Ghahramani. Gaussian process behaviour in wide deep neural networks. In International Conference on Learning Representations, 2018.
P. Domingos. Every model learned by gradient descent is approximately a kernel machine. arXiv preprint arXiv:2012.001555 2020.
S. Fischer and I. Steinwart. Sobolev norm learning rates for regularized least-squares algorithms. Journal of Machine Learning Research, 21:1-38, 2020.
A. Murria--Aonsee C. E. Rasmussen, and L. Aitchison. Deep convolutional networks as shallow gaussian processes. In International Conference on Learning Representations. 2019.
D. Haussler and M. Opper. Mutual information, metric entropy and cumulative relative entropy risk. The Annals of Statistics, 25(6):2451-2492 1997.
D. Haussler, M. Kearns, H. S. Seung, and N. Tishby. Rigorous learning curve bounds from statistical mechanics. Machine Learning, 25(2-3):195-2233 1996.
J. Hestness, S. Narang, N. Ardalani, G. Diamos, H. Jun, H. Kianinejad, M. Patwary. M. Ali, Y. Yang. and Y. Zhou. Deep learning scaling is predictable, empirically. arXiv preprint arXiv: 171.:0011 2017.
A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kemel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems, volume 31, pages 8571-8580, 2018.
K.-S. Jun, A. Cutkosky, and F. Orabona. Kernel truncated randomized ridge regression: Optimal rates and low noise acceleration. Advances in Neural Information Processing Systems, 32: 12:15588-15367, 2019.
M. Kanagawa, Hennig, D. Sejdinovic, and B. K. Sriperumbudur, Gaussian processes and kernel methods: A review on connections and equivalences. arXiv preprint arXiv:/807.02558, 2018.
Gratiet and Garnier. Asymptotic analysis of the learning curve for Gaussian process regression. Machine Learning, 98(3):407-433, 2015.
J. Lee, J. Sohl-Dickstein, J. Pennington, R. Novak, S. Schoenholz, and Y. Bahri. Deep neural networks as gaussian processes. In International Conference Learning Representations, 2018.
Lee, L. Xiao, Schoenholz, Y. Bahri, R. Novak, J. Sohl-Dickstein, and J. Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in Neural Information Processing Systems, volume 32, pages 0572-8583, 2019.
J. Lee, S. Schoenholz, J. Pennington, B. Adlam, L. Xiao, R. Novak, and J. Sohl-Dickstein. Finite versus infinite neural networks: an empirical study. In Advances in Neural Information Processing Systems, volume 33, pages 15156-15172, 2020.
M. Loog, T. Viering, and A. Mey. Minimizers of the empirical risk and risk monotonicity. In Advances in Neural Information Processing Systems, volume 32, pages 7478-77777 7478-7487, 2019.
D. Malzahn and M. Opper. Learning curves for Gaussian processes regression: A framework for good approximations. Advances in Neural Information Processing Systems, volume 13, pages 273-279, 2001a.
D. Malzahn and M. Opper. Learning curves for Gaussian processes models: Fluctuations and universality. In International Conference Artificial Neural Networks, pages 27 271-276, 2001b.
R. M. Neal. Bayesian Learning for Neural Networks. Springer- Verlag, Berlin, Heidelberg, 1996. ISBN 0387947248.
A. Nitanda and T. Suzuki. Optimal rates for averaged stochastic gradient descent under neural tangent kernel regime. In International Conference on Learning Representations, 2021.
11

---

Published as a conference paper at ICLR 2022
R. Novak, L. Xiao, Y. Bahri, J. Lee, G. Yang, D. A. Abolafia, J. Pennington, and J. Sohl-Dicksteii Bayesian deep convolutional networks with many channels are gaussian processes. In International Conference Learning Representations, 2019.
M. Opper and D. Malzahn. variational approach to learning curves. Advances in Neural Information Processing Systems, volume 14, pages 463 (63--69,440 2002.
M. Opper and Vivarelli. General bounds on Bayes errors for regression with Gaussian processes. In Advances in Neural Information Processing Systems, volume 11, pages 302-308, 1999.
Orbanz and Y. W. Teh. Bayesian nonparametric models. In Encyclopedia of Machine Learning. pages 81 199 Springer, 2010.
K. Ritter, G. W. Wasilkowski, and H. Wožniakowski. Multivariate integration and approximation for random fields satisfying Sacks Ylvisaker conditions. The Annals of Applied Probability, pages 1995.
B. Ronen, D. Jacobs, Y. Kasten, and S. Kritchman. The convergence rate of neural networks for learned functions of different frequencies. Advances in Neural Information Processing Systems, 32:4761-4771,2015 2019.
M. W. Seeger, S. M. Kakade, and D. P. Foster. Information consistency of nonparametric Gaussian process methods. IEEE Transactions on Information Theory, 5445):337-2282,, 2008
P. Sollich. Learning curves for Gaussian processes. Advances in Neural Information Processing Systems, volume 11, pages 344-350, 1999.
P. Sollich. Gaussian process regression with mismatched models. In Advances in Neural Information Processing Systems, volume 13, pages 519-526, 2001.
P. Sollich and A. Halees. Learning curves for Gaussian process regression: Approximations and bounds. Neural Computation, 1466):13331148, 2002.
S. Spigler, M. Geiger, and M. Wyart. Asymptotic learning curves of kernel methods: empirical data versus saacher-studend paradigm. Journal of Statistical Mechanics: Theory and Experiment, 2020 (12):124001, 2020.
M. L. Stein. Interpolation of spatial data: Some theory for kriging. Springer Science Business Media, 2012.
I. Steinwart and C. Scovel. Mercer's theorem on general domains: On the interaction between measures, kernels, and rkhss. Constructive Approximation, 35:363-417, 2012.
I. Steinwart, D. R. Hush, C. Scovel, al. Optimal rates for regularized least squares regression. In Conference on Learning Theory, pages 79-93, 2009.
J. A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389 434, 434,201,22111 2012.
S. Vakili, K. Khezeli, and V. Picheny. On information gain and regret bounds in Gaussian process bandits. In International Conference on Artificial Intelligence and Statistics, pages 82-90, 2021.
E. A. Valdivia. Relative concentration bounds for the spectrum of kernel matrices. arXiv preprint arXiv: 1082 2018
A. Van Der Vaart and H. Van Zanten. Information rates of nonparametric Gaussian process methods. Journal of Machine Learning Research, 12(6). 2011.
M. Velikanov and D. Yarotsky. Universal scaling laws in the gradient descent training of neural networks. arXiv preprint arXiv:2105.00507, 2021.
Viering and M. Loog. The shape of learning curves: review. arXiv preprint arXiv:2103.10944 2021.
12

---

Published as a conference paper at ICLR 2022
T. Viering, A. Mey, and M. Loog. Open problem: Monotonicity of learning. In Conference Learning Theory, pages 3198-3201
Watanabe. Algebraic Geometry and Statistical Learning Theory. Cambridge University Press, 2009.
H. Widom. Asymptotic behavior of the eigenvalues of certain integral equations. Transactions of the American Mathematical Society, 109(():278-)) 277-29,, 1963.
C. K. Williams. Computing with infinite networks. In Advances in Neural Information Processing Systems, volume pages 295-301, 1997.
C. K. Williams and C. E. Rasmussen. Gaussian processes for machine learning. MIT press, 2006.
C. Williams and F. Vivarelli. Upper and lower bounds on the learning curve for Gaussian processes. Machine Learning. (atp:inn.00(0)7771-11 40(11:77-112, 2000.
G. Yang. Wide feedforward or recurrent neural networks of any architecture are gaussian processes. In Advances in Neural Information Processing Systems, volume 32, pages 9951 9951-9960, 2019.
G. Yang and H. Salman. A fine-grained spectral perspective on neural networks. arXiv preprint arXiv: 1907, 10599, 2019.
APPENDIX
A EXPERIMENTS FOR ARC-COSINE KERNELS OF DIFFERENT ORDERS
In our experiment, the input space and input distribution are Q= St and U(S"), and we use the first order are-cosine kernel function. (Cho and Saul, 2009) showed that this kernel is the conjugate kernel of an infinitely wide shallow ReLU network with two inputs and no biases in the hidden layer. GP regression with prior GP(O, k) corresponds to Bayesian training of this network (Lee al., 2018). Under this setting, the eigenvalues and eigenfunctions
\ x2. 2 and &1 (0) =1, (2 = L cosO, es v2 sind, 22 (0) = vا cos(22 2p 2)0. (0) L sin (2p (2pp2)0--00.) p> 2. Hence Assumption is satisfied with 4, and the second part of Assumption 6 is satisfied with || < L .211.
22 A3= 4- A2p = A2p+1 ((p
The training and test data are generated as follows: We independently sample training inputs II.....Tx and test imput In+11 from U(())) and training outputs ys, i 1,...,n from (f(x))), where we choose o = 0.1. The Bayesian predictive density conditioned on the test point In+1 (m((n+11) (( the Bayesian generalization error by the Kullback-Leebbe divergence between, N (f (f((+++1) ( o) and A (m (Zn+1) 1) (*+1))
is obtained by (1) and (2). We compute the normalized SC by (7) and
Next we present experiment results for arc-cosine kernels of different orders and arc-cosine kernels with biases. Consider the first order arc-cosine kernel function with biases,
kw/ bius (21 = _ (simm (ι --)oo)))) where 전 = arccos ((21,22) +1)).
(25)
Ronen et al. (2019) showed that this kernel is the conjugate kernel of an infinitely wide shallow ReLU network with two inputs and one hidden layer with biases, whose eigenvalues satisfy Assumption with = 4. The eigenfunctions of this kernel are the same as that of the first-order arc-cosine kernel without biases, (1)) bias in Section 4. We consider the target functions in Table 3, which satisfy Assumption with the indicated 8, and po indicates whether the function lies in the span of cigenfunctions of the kernel. For each target conduct GPR 20 times and report the mean and standard deviation of the normalized SC and the Bayesian generalization error in Figure 3, which agree with the asymptotics predicted in Theorems 7 and 9.
Table 2 summarizes all the different kernel functions that we consider in our experiments with pointers to the corresponding tables and figures.
Summarizing the observations from these experiments, we see that the smoothness of the activation function (which is controlled by the order of the arc-cosine kernel) influences the decay rate of the
13

---

Published as a conference paper at ICLR 2022
kernel function
activation function
bias
pointer
(sinc) + (I v² co08e)))
max (0,zz
Table 1/Figure
A (1t)
w/ bias
(sind + (πr - co08+)
max max(0,x)
yes
Table 3/Figure
A bias
(3sim/cossp + (-T 11) 2cos=
(max (maxx(0,x))*
Table 4/Figure
A / bias
(2)
(3sing/cosp (iT (1 200s= w))
(max 00
yes
Table 5/Figure
(sind (0---)00000)
(1++iggn(2))
Table 6/Figure
(0)
w/ bias
(sini) (IT - )o081))
(1+sigg((z))
yes
Table 7/Figure
Table 2: The different kernel functions used in our experiments, their values of a, the corresponding neural network activation function along with pointer the tables showing the target functions used for the kernels and the corresponding figures.
eigenvalues. In general, when the activation function is smoother, the decay rate is larger. Theorem then implies that smooth activation functions are more capable in suppressing noise but slower in learning the target. We also observe that networks with biases are more capable at learning functions compared to networks without bias. For example, the function cos (20) cannot be learned by the zero order arc-cosine kernel without biases (see Table 6 and Figure 6), but be learned by the zero order arc-cosine kernel with biases (see Table 7 and Figure 7).
function value
Po
E, F (n.)
G,G(D,)
f1
cos20
+
0
((n2/1)
(n
f2
0
2
0
(/4
(nn3/44 3/4)
fs
(00)
T/2]²
2
0
O(n!/4)
O ((n-3/4) 3/4)
2/2
0,
0 [0,T)
fa
@(23/4)
On
122 22
0
Table 3: Target functions used the experiments for the first order arc-cosine kernel with bias, (0)) their values of / and μo, and theoretical rates for the normalized SC and the Bayesian generalization error from theorems.
bias"
Normalized SC
12 2304
Sileettee SC
Narman Dommallee SC
15 6332 values
Cormalzze SE
Experiment values
Normalzzess
10"
2200 2000
10a
7.8299pA711
Experiment valuee
Exporiment values
Number of Samples
Number of Samples
Number of Samples
Number of Samples
10a
17 17-9911n 1440 Experiment values
0.7374p 0.737 0.990
10-1
10
3.3806 $.73.
10
3.0622 6.300
10-3
Experment values
Experment values
10
10
10a
10a
10?
103
107
10'
Number Somples
Number Samples
Number Samples
Number Samples
Figure 3: Normalized SC (top) and Bayesian generalization error (bottom) for GPR with kernel (()) biss and the target functions in Table The orange curves show the linear regression fit for the experimental values (in blue) of the log Bayesian generalization error a function of log
14

---

Published as a conference paper at ICLR 2022
function value
Pg
Eg (D
(D
cos20
+00
((n2/6)
O(n
f2
sign (0)
((n)/o)
O(n 176)
f3
T/2- [
2
(n2
O(n 1/2)
4/2-0 0,
0 (0,T))
f4
1
>0
(n)
(
1-
0E(-n,0)
Table 4: Target functions used in the experiments for the second order arc-cosine kernel without
(22)
bias, ww/ bias their values of? 3 and Pu. and theoretical rates for the normalized SC and the Bayesian generalization error from our theorems.
Normalized Sc
15 2503
1eteaaaaa SC 000100
20
Mormainned SC
6 elm
Sormazza SC
20
14.2478p a1
Experiment values
Expertment valuee
Experiment values
Experiment volues
10
10
202
10
10 Number Samples
10
10
10a
16 Number of samples
10
10 Number of Samples
Number of Samples
Min
2.9335n 1.040
1.711 6788
Experiment values
Experiment values
Expertment values
10-2
10
10a
17.6592r
Expenment
107
10
10a
10a
107
10
16'
10
Number of Somples
Number of Semples
Number of Samples
Number of Samples
Figure 4: Normalized SC (top) and Bayesian generalization error (bottom) for GPR with kernel (2)
wwo blas and the target functions in 4.
function value
Pg
E. (D.)
E,G(D,)
f1
cos20 6²
+00
0
(n
(n (/b)
f2
2
0
(n2
On (n
f3
(10)
T/2)²
2
0
O(n 1/2)
On 1/2)
T/2
0,
0E (0,
fa
1
0
((15/8)
O(n 1/6)
1-x/2-
Table 5: Target functions used in the experiments for the second order arc-cosine kernel with bias, (2(2)
w/ biss? their values of 3 and μo, and theoretical rates for the normalized SC and the Bayesian generalization error from our theorems.
Norma ized Sc
No Normaltzed SC
Non Aormallted SC
10a
10 10.53186110 DI
Mermaltzed SC
Experiment values
10a
Experiment values
10
Experiment values
10
Experiment values
10
10'
107
10
10
10' Number of Samples
10
10'
Samples
Number Samples
Number Samples
2.5265n 1950 Experiment values
9.14
20
8.0765n 3340 Experiment
10a Sempo mud Lancaaaa
10a
10a
Experiment values
10
10-1
922AL
Experiment values
10a
19 Number of Samples
10"
Number of Somales
Number of Samples
Number of Samples
Figure 5: Normalized SC (top) and Bayesian generalization error (bottom) for GPR with kernel (2)
w biss and the target functions in Table 5.
15

---

Published as a conference paper at ICLR 2022
function value
P4
E. (D,,
f1
cos28
+00
>0
(n))
((1)
/2
sign(0)
1
0
((n
((n-1/2)
fa
/ [0]
2
0
(nn!
O(n 1/2-1/2)
17/2
8
0 (0.T)
f4
>0
(n)
((1)
n 7/2-0. 8
Table 6: Target functions used in the experiments for the zero order arc-cosine kernel without bias, (0) bias" their values of 3 and μo. and theoretical rates for the normalized SC and the Bayesian generalization error from our theorems.
Normllzed SC
10
Normllzzdd SC
Normaltzdd SC
6.2139,44128
Normaltzed SC
12:10814--11
20"
Experiment values
Experiment values
Experiment values
Experiment values
-0%
10a
20²
10
10
107
10
10
10 Number of Samples
10
10' Number of Samples
10
10' Number Samples
Number samples
-8329n-- 469
3.83600-- 490
Experiment values
Experiment va Lan
15. 72957
21.0097A
Expariment valuee
Experiment values
10
10-1
10-1 10
10
10
10
10
10
10a
10a
Number of Samples
Number Semples
Number Samples
Number of Samples
Figure 6: Normalized SC (top) and Bayesian generalization error (bottom) for GPR with kernel (0)
w/ bins and the target functions in Table 6.
function value
Hg
E. (D.)
G,G(D,)
f1
cos20 6²
+oc
0
(22
On 172)
f2
2
0
(n2
On
f3
(10)
T/2)²
2
0
O(n'/2
On (n-112)
12/2-0 0,
0E (0,
fa
1 0
((n!/2)
O(n 1/2)
1-x/2-4 A 0,)
Table 7: Target functions used in the experiments for the zero order arc-cosine kernel with bias, 1.(0)
w/ biss? their values of 3 and μo, and theoretical rates for the normalized SC and the Bayesian generalization error from our theorems.
Nermalized SC
Norma Ized SC
2335 1405
Nermaltzed SC
Exter
2.506332 49G4
Normalteed SC
Experiment vsles
Experiment valuee
Experiment values
10
10a
10
Experiment values
10
16
10'
10
16' Number of Samples
10
10' Number of samples
Numb of Samples
Samples
5,7555n 144%
5,9260n 8 44413
41177
5.8773n a 400 Experiment values
60. 60.7124n 0.324
Experiment values
Experiment values
Experieent values
10a
10-1
10 10a
30-1
10a
19a
"19 Number of Samples
Number of Samales
Number of Samples
Number of Samples
Figure 7: Normalized SC (top) and Bayesian generalization error (bottom) for GPR with kernel (0)
/ biss and the target functions in Table 7.
16

---

Published as a conference paper at ICLR 2022
B PROOFS RELATED TO THE MARGINAL LIKELIHOOD
Proof of Proposition 3. Let y = (JI.....On)
-T.) be the outputs of the GP regression model on training inputs Under the GP prior, the prior distribution of y is (O,...... Then the evidence of the model is given as follows:
(9: 181
Zn
20
12TT
(2x) Kn
22/2
(26)
1
2K, 119 - 20 dy.
(2 (2T))o"'el( (K,)
12
Letting K₂ -= Kn 1 + 0² Iand μ= o² Kny, we have
e --1 ( y Re M
2n = (2m)" (,, 1/2
8"
(2 ( (kt,)) dot(Knn) 1/2
(In) kk) /1/2 y Ri
(27)
e 202y
=22n" y+ "
(2n)m/20deet K 11/2
The normalized evidence is
Zn
(2T)- nn200 ne 20z
(28)
det Net(K,,)1/
202 2 1 k ah (a-(y-()))))))))) f(x))) (y- 1(x))
det (,,) 1/2
So normalized stochastic complexity
F F (D.,) logg
I
2 logdet Kn 1/2 logdet (Kn) 202 y 5Mt R- p- 20 (x))) (y-[(()
2
1)+ (Kg) 2020"y y 20s a (Kal+ 1
logdot (K= 1) -
g² 02 -ly
2
20 (y ((x)) (y-((xx))
Kn
- (I+ K - y- (y
1
logdet(I+
f(x)).
g² 20
g²
202
2 (ogdet(I+_0
1
(2)+
Kn
+
202 f(x) (I+
Kn ( 1
(I+ K Kn Kny-le c- e'c
1
0²
0² 202
0²
202
Kn
T
(1t
) f(x)
20
(29)
After taking the expectation over noises we get
E.F = logdet(I+ σ² k2t)+
1
202 f(x)
Kn / -(x()) Tr([ - (I+
Kn
1
Kn )
K
(30)
σ2
2
σ2
This concludes the proof.
C HELPER LEMMAS
Lemma 15. Assume that m OC as n - 00. Given constants a,, 01,52,81,82 >0, 0, if and
8283 > 81 1, we have that
Σ
a1i
#3 =0mm 1-
(31)
(1+aym
17

---

Published as a conference paper at ICLR 2022
s1 > and 828, -1, we have that
R
ai
(1+azmi = (m mm0mmmmmmommm logm).
(32)
1f'1 > and 8283 <81 1, we have that
R
a1 51
(1 + a2 (m))
(33)
Overall, if >> 1 and m + 00,
R
O(mmax (-00 1-2 1)
011 81
$283 81 1,
(34)
(1 + a2mi 82)
Omm "2 logm),
$1 -1
Proof of Lemma 15, First, when 81 > I and 8283 > 51 100--,,- 1, we have that
R
012-81
01 dx
+
(1+a2m))s
[1,+000|
(1+0mm 528
Q1
1-21
my 1/ -81 a1
+
(1+agm)** 8g
[1,t,0] (1+ m=//// )
-2 22
m 1/ 82
+m 1-
a 01 11/mb//2,4o0 (1+ 8338
dz
(1+agm)*) "9
11 = (m "2
On the other hand, we have
a1
01 81
118+1]] (1 (1+ 0:22==000 820 dx
(1 + a2mi
22
1-21
a1 m/
81
22
[1,+1]] (1+ m 82 )a3 d
1/22
a1 81
m
(1 (1+0gr dx
(m 1-=1
"2
Second, when 81 1 and 6283=88 1, we have that
R
i1i-
a1
1-81 +m +2
a1 11/m too) (1+agz s2)0s dx
<
(1+ (1+agmi-sa))
(1+a2m)* 50
+ 1
(logm((1/z))
(1+ 1+ammm)
(m logn).
On the other hand, we have
R
01 dr (1+ a222 42
+gamm
22)
118+1]
1-61
m/
m
[1,+1]] (1+02( mn//a
83 m /
1-s1
a1æ 81
og
(R+ (1 (1+ 323 dx
9mm " logn).
18

---

Published as a conference paper at ICLR 2022
Third, when 81 > and $283 < S1 1, we have that
m 1-
01
(1+a22 -0))0 dx
+ +aamii
(1 + agm) )8
11/m//r,,t0
a1
Omm (100/
+m
(1 12m))
(m )
On the other hand, we have
R
01t P S
d1
+ 1-41
01 12/m 102) (1 a2x )
dx
+ a2mm -
(1+ (1+a2m)*
a1
"2 0(m(-1/6))(-atttee)
< (1+agm)))
+
(m *))
Overall, 81 >
R
01 01
maxt (-0 max( - }), (m m
8283 1,
(35)
(1aammi )x))
(mm= logn),
8283 81 1.
Lemma 16. Assume that R=m * for k 0. Given constants 01 01,02, 00, if 1, we have
that
R
a1 91
+ +taammia =2)33 = =maxx(m " "a,R" ",,,""__ {).
(36)
Proof of Lemma 16. First, when $1 S 1 and 8283 > 81 1, we have that
R
ait api=
I al +
a 81
[1,R] (1 a1ya 52 ooy dx
(1+a2m)*s + 1-aammi-aaa )2)03
+ 1--1
a1 m 17m2
)08 d m 1/
(1+agm))s
[1,8] (1+ m //1//
a1
+m 1-41
a1 dx
(1+a2m))s
12/m///22 R2//// (1 22 )o
01
1-91 +0(m ) )1-31)
(1+a2m)ss 533
= (maxx m
Second, when 81 S 1 and $283 s - 1, we have that
R
aji S (1+a2m)ss (1 (1+aymi
a1
1 +m
010 dr /1/mb/ra Rt/m///a,/////// R/m///2] (1+ )83
22
=2.00 +2)a
d1
+ 1-1 22 (mm( (11/22)(1 + mm 11
<
(1+agm)ss
= =maxx 83 -)
Overall, if 11
R
aj 51
= Ōmmax - 83 (R--s:)) }).
(37)
(1 [1+ 11aammi-0 1aamii=+)+ +2)=0
19

---

Published as a conference paper at ICLR 2022
Lemma 17. Assume that f E (9.,)) Consider the random vector f(x) (f()))..... where Bn are drawn i.idd from p. Then with probability of at least 1 1- we have
l - (
where |1 (ee
Proof of Lemma 17. Given a positive number C2 applying Markov's 's inequality we have
p(f(())>() 1
Let A be the event that for all inputs (1))) Then
11,11
(38)
Define P(x) m C). Then (x) - Ex)() IIfI So 11((
max (,1 = C' Since 0 - (z) SC, we have
B (E
(39)
So we have
(40)
Applying Bernstein's inequality, we have
P
((x))(4nBP(()) Sexp
- $
<exp
/(nC1|/[12+ Ct
8 4max
Sexp
[nC f cr
Hence, with probability of at least 1 1-6, /2/22 we have
2
40
2
Σ P Smax
AClog n
n
log
+nEff((X)
6
3
81
(41)
40
<max
AClog 8
log
+n
3
When event A happens, (xx (xx)) for all sample inputs. probability at least 1 n111f112 82, we have
According to (38) and (41), with
[ (a.)) max
{V |Clog n|| f12,
4C log
2 1
81
Choosing C= 2 fl2. with probability of at least 1 1- 51 we have
Σ
(()) Σ ((x)) S max
Smax
V
5,
8 n
log log-
b
2
1
35,
n
w fl
113log
5,
+n
1=1
1=1
Lemma 18. Assume that f E (9,,p.. Consider the random vector f(x) (f(z)),... )Ix,))
where It In are drawn i.i.d from p. Assume that || = =uup f (x) < C. With probability of at least 1 -- we have
1 (VCnll +n|l
where || f
20

---

Published as a conference paper at ICLR 2022
Proof of Lemma 18, We have m Since 0 0 (z) C, have
(42)
So we have
(43)
Applying Bernstein's inequality, we have
P
(r.))(+nE/f Sexp
((nE]f((X) E -X 2
t²
<exp
2(nC² If Cat)
<cxp
4max 4max(nC2||
[nC21 c
Hence, with probability of at least 1 1- we have
Σ 2x Smax]
(
1 10 81
nIlfl log
402
1 +nBBf
81
<ō max
/Cnnl111BBB +nl1f11ß
(44)
sō Cxnl|/1BB+
f12l15112.
For the proofs in the reminder of this section, the definitions of the relevant quantities are given in Section 3.
Corollary With probability of at least 1-8,, we have
[ (1
Proof of Corollary 19. The L2 norm of f>R(2) is given by ||f> - Applying Lemma 17 we get the result.
R² 23 23-1
Corollary 20, For any v RR, with probability at least 1 1- 81 we have
Proof of Corollary 20. Let g()) E (p) 1o0 Then & ØRV= = gxx). The L2 norm of g(x) is given
by ||g| ンØー = Applying Lemma we get the result.
Next we consider the quantity, T R-II. The key tool that we use is the matrix Bernstein inequality that describes the upper tail of sum of independent zero-mean random matrices.
Lemma 21. Let D diag(d,, ... dR}, di.... dR and dmax max(d1, dR). Let
M max (Σ = 01 Lmaxc }. Then with probability of at least 1-8, we have
|D - - nl) S max v ynd Mlgg A.log.Moo .Mgg
(45)
21

---

Published as a conference paper at ICLR 2022
Proof Lemmna 21. Let Y, (01(z)).... on(x,)) and Z; DY,. It is easy to verify that
) = D2 Then the left hand side of (45) Σド= [Z, 2 -E(Z,Zf)) We note that
||zzz E(2,22) max 2, (2, max mmax)
For 12yll we have
R Σ
R - Σ
12,11
d (z
(46)
p=0
==U
we have
2l 2p Pmax }.
On the other hand,
Since
R 211,,182,,311 x
El
1 23 (b6)
p=0
Σ 111,,11111,221111
have
[[[ 1B(2 5 max > p= 00 11: [E|Z 21 11,.
< max
0
d2
dmax
x= p
max
d2 max max Σ
11 110 dmaac
p=
Using the matrix Bernstein inequality (Tropp, 2012, Theorem 6.1), we have
P( 12,z ((2223)1122+
j=1
-22
Rexp
-111
fmax, 12, -B(2,)))
<Rexp
2(nd max Σ R d2 Punax
mmax D Baas
12
=Rexp
(max (ndP max max 1
2 1 Praxx Amax EE 221l ((nax)))
Then with probability of at least 1 6, we have
1z B(ZzZ,))) )112
{ V ndda max max
< <max
R Ei o dbllppl 1 Hog
12 & max (Epr oz 1 I1'c
Le log B
Corollary 22. Suppose that the eigenvalues (Ap)p21 satisfy Assumption 4, and the eigenfinctions satisfy Assumption 6. Assume o² = (nn') where 1 a
1+27 < < Let r be a positive number such
that 140427- (1427+2011
<g 11
1. Then with probability at least 1 - we have
2a
(I+
3 AR) x22 12
RI)A (I+ An) 7/2 1/1 (
-/2
27 (1+27 21+2r+ +2x)
(47)
<0
11
2a
7(1-0 (1-)) -)) log R
22

---

Published as a conference paper at ICLR 2022
Proof of Corollary 22. Use the same notation in Lemma 21. Let D (I+ + AR) 7//2 A X5Par
Then l 1 e²t and Σn dlll 8pll S Σx= C (I++ Ap)) nt
-(())²) --a)), ) where the
first inequality follows from Assumptions 4 and 6 and the last equality from Lemma 15. Then
M max === (Ep= 8 0 Ilo.. &max ((,0,, 1-10+2r
Applying Lemma 21, we have
1/2 ( nl II+ AR) A/
A (I4 2 AR) 7/2
$ o2 max V
( 1onet
log 0
R ((2))
1-3a+2:
ylg
177
(48)
=0 1 (1)
122
n²)= in n²) = =0( log
(1 (1-210+2-(
+ -
=0 (V logg nn
1lu12. (1+24+20)
7(1-1)
Corollary 23. Suppose that the eigenvalues (Apl221 satisfy Assumption 4, and the eigenfinntions
satisfy Assumption 6. Let Å1 = (1, Assume o² = ((n²) where I << 1 Let y be
positive number such that 1+2r <TS1. Then with probability af least 1 - 5, we have
II(T+ (AR)
1/2 1/
1.
AR) -
n nT)
2/2
11 50
V logBniz
(49)
Proof of Corollary 23. Use the same notation as in Lemma 21, Let D= AR)
//2
Then 1
AEp2 dh L S 1 and o 1 + C (I+ ンッ C% +0 (- 0(1] where
the first inequality follows from Assumptions 4 and 6 and the second equality from Lemma 15. Then M max ( 01 11 dmax = 011). Applying Lemma 21, we have
I1[++ n An) 1/2
A7
n nI)
2/2 (T+ An)
I max
V
(n0 (og 8011)
(50)
= =o 1og
Corollary 24. Suppose that the eigenvalues (Xp)p21 satisfy Assumption 4, and the eigenfinctions satisfy Assumption 6. Let & R- probability of at least 1- we have
and AR+1:S (XR+1......s) Then with
|A R ( T
1/2 mtsssl
S-R max 2222t22 R R1-a+223). (51)
Proof of Corollary 24. Use the same notation as in Lemma 21. Let D A 1
ARt.s. Then
d == and C > CARRICCCCA C2 =0(== -o+2r) where
the first inequality follows from Assumptions 4 and 6. Then M = =mxx p= R+ C &zdpp" d
8
O(Rl-a+2r), Applying Lemma 21, have
II(T 1
1/ 1/ ( (T+ g² Ag) 7/21/2
S <max
llo R ( (
(52)
= 0 S
1212r R Rl-a+2r))
23

---

Published as a conference paper at ICLR 2022
Lemma 25. Under the assumptions of Corollary 24, with probabilliyy of at least 1 1-6, we have
1 SR lll (maxx(RR n _22R 1-20+2r
n Rl }).
Proof of Lemma 25, For S E,,, we have
00 s s9l12 S
(xxx)xx
p=
Σ
(x)
p=S+1
ApnC2p
p=S-1
=0(nS1-at22)
Let S= Then we get $2 ").
Let (e
We then have
R 50(n R+1 R
1/2
1/2
R+1islle
50(nR~ |
/
T
i 2
- 1/2
R+ 1:9
50(nR +0
R - R
maxtn' R 1-2g+22 R (l-)))2))
-0(max(nRt' n R 1220 R nl-at2r)),
where in the fourth inequality Corollary 24.
Corollary 26. Assume that o² = (1). IfR to where 0 < < of at least 1 - 8, we have
a-1-22 then with probability
a(122r)
II(T+ PRAgwR )-1 n
Aandsn (nn-)())=0(1)
Proof of Corollary 26. By Lemma 25 and the assumption R R=n++r +h we have
I1(++ + nn n
S n
< <maxx(nntt
R. (l-aat2r) 1 1-20+2r
n R
(ka)aa))
Lemma 27. Assume that
11+ a AR) -1/217 (" (1+ AA) 7/2 1 where
142r
<1 1. We then have
(I+ d2 A
=(I+
Proof of Lemma 27. First note that
1 (I+
AAR) 1/2
",,
(1 (1+ <
24

---

Published as a conference paper at ICLR 2022
we have that when is sufficiently Let (I+ + o² - nI) e (I+ Ae,)) 1/212 < 1. Since all diagonal small, |1 [
Since Ag =
1/2
entries of Â. are positive, we have
(I+ k
= A R+ $ -1|) (
= = شx R)
1+ 1 (T+ 0
(,, -1
(1 (1 (c, 1/2 1 11/
=1+ 7 Ac,
-1/2 (I+ - (.
1=
(I 2 A R) 1
Ae
= (I+ 34 A4, 11
(-1> (T+ (7+ " -
(I+
1=1
Letting c +00, we get
(1+ AR 2 R
AR)
Σ (-1))
L (
(-=
This concludes the proof.
Lemma 28. (I+ bnAnd
112 1, then we have
(I+ AAΦT 1-1 -1 (I+ An
11 (1+ 2ndg02) -1 & PaRAAR a S2 )) (I )ndgo
j=1
(53)
In particular, assume that 0² - O(1). Let R=n to where 0< 0-1-27
Then with probability of
a(l+2r) at least 1 1 for sufficiently large n, we have |[ @ndnoh -1 0
12 < 1 and (53) holds.
o²
Proof of Lemma 28. Define 2> = (x) ),p (ig Then have
(1 4A4T 1-1 - (I+ 02AyOR )
=(1+ AnAn + PoRlZRO
(I+ 2
oe
- (T+(((++ RRAROT ( ts An
2RARO ( 02
I (I+
By Corollary 26, for sufficiently large n, |1(T+ Andn 4 R at least ò. Hence
SR
l|2 < with probability of
1 2AΦ 1 (It o
1 [+ (T+ Andndh 2 aondan
2R
-1 -1) (T
2nAn -1
1)) (1+ 22 2 PoRdg (I+
of
o2
1=1
25

---

Published as a conference paper at ICLR 2022
Lemma 29. Assume that Poo p==0 o2 where 1- 1427 <t< Let R=n +x)((1-)))) where
0 O<<< 2-1-2r+(1+22)), Then when n is sufficiently large, with probabilliyy of least 1 28 we have
(1(11)
I1(I+ 3. #RAAATH) = (2)+))nn (1 maxt 100xxx/-111111 (1-(),
(54)
Proof Lemma 29, Let AI.R diag(A1. ARt. P1:R (x), (1 dn(x))
and P1-R = (M1, ... PR). Since No = O, we have (I + 2 ( fa(x)
(1+ 1. - Using the Woodbury matrix identity, we have that
(I+ 1 PIRRMRR -- 1innn (R))) An. " PIRMEER
=PLRMIR 1I:R(0 I1
I. AA R
PIRRMIR
1 A1 1: (:R) P1.RR
TT
(55)
Let A (I+ A1 1:R
47 1: 1I)A A
BByyy Corollary 22, with
probability of at least 1-8, we have | 2 V log f/
1-a42r 20
(1+23)
2a
When is sufficiently large,
== is less than 1 because (I 2/2 A1 1 (1:R)
1+27 <t 1. By Lemma 27, we have
-11+AA1R) - Σ
==1
then have
II[+ 02 A T. "
(I+ A1:)) +
1- (2 (I+ - A (I+ ~t A1:a) p1:
j=1
< [I(++ A M1.2l2+
( - ( a 3
(56)
By Lemma 15 and Assumption 5, assuming that sup1>1 Pi = hi, we have
CRp 23
[[I+ (A+R) -MA
man ((1 (-22)) llog n22
L+pCsp a 0/22/2
#
CRi-28
(11+ AARR) "M1_))))
11121122
(1+ H (h(i)-aap O max ((1x)(((1))))))))))) (1-28)(1_))
00
2, 1, 11
where k =
2a 20=23-1 1. Overall we have
||[+ (1++2AAR:)) -1 m1.R|22 0(1 (l)max))) 2x
1.229
1-29
1og//2 k/2
log
(57)
Using the fact that
A1 | / log fn 1aat2 (1-2724
and
|| 2 A1.n) A1n
we have
μ | A A (I (1+ 11:8
AY (I+ A 1 1 1.
11+ - A (
(58)
~0(n 1/4 || A| 3 A 2
26

---

Published as a conference paper at ICLR 2022
By Lemma 16 and the assumption R= +x)((11)-)))
[[[ A1:)) #A (1+nC2p a 0/22)1
(59)
=0 (n-
(1-1)/2 /R R112--8ta/2)
=n (1 , - +x1122-340/2)11000
We then have
( (1+ (I+ (111+1110 A1.R) ( - nl)) (I+ (1:A1))-aaaa
(60)
=|I (max -2 +e(1/2 - (aalii/-tta22)(-- 1+20/2)(1100
By (56), and (60), we have
|I(++ I A 11 11.1122
(1-n)__)a 11, 222 log" k12
*/2 222n) Σl
A Al320maxxf (1-1) (1-0) (1- - +x(000(/22-040//11
j=1
-O (1-tmx))) 22 log k/2 n)) O(
1-
2+2-2 2a
(mmax (1-1) 1-20 +x(1 1 (x(000(/2--53///))
20
(61)
By ussumption K
--1-27+(1+2r) we have that a=(1-1)
x(1-t))12-3+ta2)) 1 1-a+27
(1+2T)t
1 1-a+27 (1+2T)t
<xa(l-t)/2+
<0.
20
20
20
2a
Using (61), then get
II(1+ 1 A TR (I.)
"m.nll2=(n1 (1)xx(( 1-1, 1og
1/2
1+)
(62)
(1 T A1:R) -
By Corollary 20, with probability of at least 1-6, 5, we have
| (I+ Ar. T. PIR) - (1) +1]n]][(++ 2/2 -M1
(1:al22)
(63)
=Ō(/ (1-
From (55), get |I(7 J I
1- - - 1.RMRR = =O(V(5 +1-1)nn n (1-1)max 1-20 )).
1:R)
This concludes the proof.
Lemma 30. Assume that pa and a² = O(n') where 1 1- 1 <1< Let R +x where O<K< a-1-2r+ Then when is sufficiently large, with probability of at least 1 1 28, we have
[I ((+ f
(64)
Proof of Lemma 30. Using the Woodbury matrix identity, we have that
(1 11 AR Ø
(65)
- MR.
Let (R,1 ( and #R.2 (0 Then PR= M.2. Then we have
| || A
A TT
(66)
27

---

Published as a conference paper at ICLR 2022
According to (62) in the proof of Lemma 29, have 11 + 22 A
*R,2ll2
O(n )-)))-))))) )).
Next we estimate [I - A RR) -1 ARR,
Let
n A- (1 2 AI.R)
1/ A2/2 1. I. 1. R -/))
n AI.R) A1R2)
02
where - 2 ( <9 1. Since 1 1+27 <|<,, - t (1+27+20)(
2a so the range for y is well-defined.Bt By Corollary 22, with probability of at least
2a
2a
2a ō, have
A log In 1ig (1+24+20) -1-111==0ff0)) When is sufficiently large, 11 All2 is
less than because a 1+27
<1< By Lemma 27, we have
(1+ AR
= Σ
(0004+44)=~AA((((/// (1+ AA)
We then have
I1++ # 1R11122
(1 + Σ
(1+ #(H) (4
(A (1+ (1) peR.1
j=1
||| AR) MR 1 Σ
(+ (4 nl)) (I)) (1+
MRR 112
(67)
By Lemma 15,
R
C2p-28 28
II( g2 AR) 1RI112s,
P +
1In0xp-a/000 0(1). =
(68)
p=1
Let Â1 = diag (1. An) and To 10, 1). Then Ar = AI, Let B = (I
= RR)
A) According to Corollary 23, we have || BB||2 =
0 1og (V1oggBnt) Bnt) Using the fact that All2 - Ö( v log Bn 12: (142742015
-2(1-)) we have
(I+ (22
nl)) (I+ nh AR) -
[I+ An) 1+ AR 1- 3 (A(I+ AR) 1+7 1
B(I+ AR) -1+ p.R.1
σ2j
< 0² (n (-1 1+ 1-1++++1+0+0------ 1010
0
log fn 11-101 12 11427420
7(1 (11-01))
log R 5
nz PRIM
5n (-(1)+))1-
1n 1-ot2r- (1420)111)))))
/log
R
||R
=Ō(n -1 ++3 +)+ (1--110-11
(69)
Since I- ( ( (1+27+20)t
2a
<
< and
2
1
1-7
2a
(1+27+20]t
2a
2 <0, we can let
7 be a little bit larger than (68). (69), we have
(1+27
+2a)
and make + -1) < holds. By (67),
[-1
20
2a
A
12
50(1)+
Σ
Ō(n - ( --
(70)
j=1
=0(1)+o())=0())
28

---

Published as a conference paper at ICLR 2022
According to (66), we have I|(I+ A (11). By Corollary 20, with probability of at least 1-ô, we have
"uRll2 = mmn (2-00 10-00-200 201
0n
+
h [T An u
+ 1 (3+1)ml((+
=0 V (1+1)n)
From (65), we get + #RAR (Rxx))22 (v(+t)))))
This concludes the proof.
Lemma 31. Assume that o² - @11). Let Rt = n +x where 0 < < 2_ Assume that pio 0.
Then when r. sufficiently large, with probability of at least 36 we have
II(I+ a² fu(x)]]
(1mm)mmnn" max -,
(71)
Assume that P4o > O. Then when is sufficiently large, with probability of at least - 36 we have
II 2A4 )- -=====(())))==00
(72)
Proof of Lemma 31. We have
2A# fn(x) (I+
a²
(73)
=(1 + PnAn * a
[R(x)+ (1+ --1 -(1- ) (
[R(X).
When (4 by Lemma 29, with probability of at least 1 1-26, we have
[[ 1 DRAR f (1+1)n-n max
1-28
200
Since 0-1-22 2=1-21, apply Lemma 28 and Corollary 26 and get that with probability of at a(142r)
least 5, the second term in the right hand side of (73) is estimated as follows:
(T+
014 02
) (T+
o² $RAR00 )-1 [x(x]]
1y (1+ -1 (1+ T fx(2))12
1=1
[T+
$ndgol)- -1barsaans
BaRASAt |/ [[[++ #ndn42) )
o²
1-28
max (n - jua Õ6 + +1)nnn max Zo
j=1
1-29
=o(v (1 + +1+=) max-
20x
Overall, from (73), we have that with probability 1-36,
1-28 1 mux/-11
||(/ AA4T
fn(x)]l2=
2a 1).
When 140 > O, using the same approach and Lemma 30, we can prove that ||(/ "gg² - [x())]
Ō / (1
+1)n.. This concludes the proof.
D PROOF OF THE MAIN RESULTS
D. PROOFS RELATED TO THE ASYMPTOTICS OF THE NORMALIZED STOCHASTIC COMPLEXITY
Lemma 32. Under Assumptions 4, 5 and 6, with probability of at least 1 - 25 we have, we have
(T,n(D,) -T..))) = (0 (nR' 1/2 2--447 R Rl=)+22)
=ō
(74)
29

---

Published as a conference paper at ICLR 2022
If we further assume that 0 O<K< CCK<2-1-2 a² 110 =0==00mm and x² = then for sufficiently large n with probability of at least 46
= na where K >> O, we have
we have
(Bs((D))TT(DDa)-F (1+ ( (12 tx:) 1-2 1-20 (1-2000
-1-xa,144 1-.1122-2 1-22 -xa)) (75)
Proof of Lemma 32. Define P> (Bag(AR+11 ARt1.....pp..... We then have
(0x+1(x), 0R+2(X), 0x(x), n.), and ArR
1 (D,))) logdet (lt
1 RRAR
loggdet(1+ (+ σ
of 2
(76)
1 Tr(I+
$AΦT
AnAn
) -T([+
2
o²
As for the first term in the right hand side of (76), we have
2 logdet(1+ (I+ (AT") logdet(I+
#nA
σ²
2
σ²
logdet
(I+ (1+ 2
R (I+ 2 Rn
2
nA
2
(77)
logdet
I+ (I+
$
AnA
- (2)
RA R
2
σ²
Trlog
I+ (1+
(I+ 0²
2
1 RA
n >R
Given a concave function h and a matrix B E nx whose eigenvalls S1, are all positive, we have that
(78)
where we used Jensen's inequality. Using h (())= log +2x in (78), with probability 8-8, we have
+ 2240") -
M. +1 (I+ $2 1
k #logg1+ n (1 ARARO
11 RA
RA>
< 2 (1 na2 Ep=R+1 O x 1 - 2
Σ R+1 2 (111)11111100x
(79)
2 Ep=R+1 C20
p pp 12 + 27
+ 11110p11
p== M+1 App + n 1/2 " p= 1++ App + 2p= R++
>pp2T) 2
(nn = ( +n 1/2 n2= - + R² -at2r =0 t
where in the second inequality we use the fact that Tr AB < || 2 positive definite matrices, and the last inequality we use Lemma 18.
TrB when A and B are symmetric
As for the second term in the right hand side of (76), let A= (I+ 2 4RAR 1/2 Then we have
Tr(I+
#AΦ" 72 - T
42An )
y-1
2
A>
= TrA - (I+A(
)A) A
o2
</ / (1+ 0 JA)
< <g (1 41A 4 B ) AA) (1- " (
(1 (1+ no Σp- 11 (x) [12)) - 1 -x
Ep= xxl (x)
20
= = (nR' a +m 12 12 atr
Rd ( = (
30

---

Published as a conference paper at ICLR 2022
where in the first inequality
the fact that ||||| and T+ABA | when A and B are symmetric positive definite matrices, in the second inequality we use and in the last equality use the last few steps of (79). This concludes the proof of the first statement.
in (78)
As for (D,) - (2 we have
-2, f(x))
DA0" o² -1 FR(x)
DA4" -
(80)
+ fn(()* (1+ DAΦ" )
2
For the first term on the right-hand side of (80), we have
f(x) (1+ BAg" (x)) (1+ DAT"
[x(x)
o²
<2 (>)(x))(11)) (1+ SA0"
x² ) (x(x)(((()))))))))) + (x) (1+ $A87 )-1 f xx(
(1+
<2]1/>((x]]l2]((
a²
PA4" <2]]
[x(x) 2 +x)
o²
Applying Corollary 19 and Lemma 31, with probability of at least 45, we have
DA4" [(x)*(( (1+
-1 f(x) [R(x)" (1 "ΛΦ" fR(x))
0²
0(1 (1)nn) max 1-28
$20
( 23
1)+ 1+0((3 +0((+1))m+ -28)
-2
(++1)) ++( -x) 1-20
2 +max/ -1,
1-28
+0( +2)(((12)
=2
(#+1)) - -x) 1-28
2
+max( -1,
20
1-28
where the last equality holds because 2 +k) 1-28
1-28
when K 0.
2a
As for the second term on the right-hand side of (80), according Lemma 28, Corollary 26 and Lemma 29, we have
fR(x) (1+
(14
DART > fx(x)-fR(xx) o²
OndnoR fR(x))
-10 (I+ Endn02 SR(x)
$ P>
(1+ 4RAa07 0²
-
111 0RAR07 -1 fR(x)
(81)
o²
1=1
Ō( jkc jÓl() +1) + 1-29
= =O(( + 1)m +mmxx(-2 2 )-xa).
1-28
By (80), we have
(T.(D))-TaR(D))==0
( (1+1)m 1 +x) 1-23
m1 2a
1-29
+0
(f+1)n 1+max( 1-28
=Ō ( +1+111 max + 222
1-28
2-))
1-28
na}
This concludes the proof of the second statement.
In Lemma 32, we gave a bound for (D,) TD().)) when no <R<n" <n note the following lemma:
1 1-0-1-2 For n.
31

---

Published as a conference paper at ICLR 2022
Lemma 33. Let R = n and o² n'. Assume that C 2 1 and C(1 - + 2 -t 0. Under Assumptions 4, 5 and for sufficiently large n and with probability of at least 1 1-36 we have
(82)
Proof of Lemma 33. Define 2>R (ØR+1(x), 0R+2(x), " pp(x), ..), and ASR
diag(ARR. (....)p...))) Then we have
f(x) (1+ PAΦ"
DAΦ"
(T,( (T2,))
[(x)
r² In(x))
(83)
DA4T
Sx() (I+ DRAR Sn(X)
+ [n(())((++ (I+ a2
For the first term on the right-hand side of (83), with probability 1 - 38 we have
[(+) $
$ΛΦT
) (((x))]n(x))
σ² )-1 '[m(x)
r²
PA
DA4
22
[3((x) (14
) [R(X)
{x (1+
- ss [x((
$ΛΦ-
)
#11215>x(x)))
σ²
o²
2 =l/3
220 (
ogv
-ō (1)R
where we used Corollary 19 and Lemma 17 for the last inequality.
The assumption C(1
2T) < O means that R1-wa R1-ut2 right-hand side of (83), by Lemmas 28 and 25, we have
o(1). For the second term on the
o²
2
DRARDT [x(xx)
[R(x)* r (1+
(1+ [R(x)
o²
r²
1) (
-- 1 - (I+ RRAN0
(I+
1)-
T²
o²
PRAR 11
R R
-1lst .1|
1 [
(84)
/=1
(
Ri
101 10(
j=1
1
=ō((
5
+
Using (83), have
(T(D.))-an(D.))=o))
(1))))))) +ōll 5 +1m 02
R2-at2r)
=0
1
1 1 pmaxt p
1)n σ2
Next we consider the asympototics of T1, Ti (D.) and T2 Dz)
32

---

Published as a conference paper at ICLR 2022
Lemma 34. Lel A (I+ + A/ - 3AR)~=Pe
Assume that
||A||2 <1 where 1+2r <7 1. Then have
(2.n(Dn) 2ラ MR [+
(R) uR (
2
where
E - -R [0 - (T+ 2 An) pRn-
Proof of Lemma 34. Let A, <, AR) Since An = diag )R), we have that when e is sufficiently small, || (I+
(I+ - n1
Ae,)) 1/2 1|2 < 1.
Since all diagonal entries of Â., are positive, we have R
T
R DRUR
20
20
R
R
R
02
1
2
1- R (
1 R 2R) 'A, 24 DRRR
20
1
202
RPR
20 "
A xR) R
(85)
T
2
PR
T
R
2
MR
1 A R T RR)
c,
R
| 92
R
pR.
Using Lemma 27, we have
1
1
RR
11 R
A x
|n pn
2
0²
un 3 /
[I+
N Ar Un
02
11)5t1
11
AR E.
(1+ 2/ S R) ( "(+= uR
n2
==1
n
I
(I+
π1
A, -1 FR
20
0²
Am) nl) - + 00 5-1
-1)0t
PR g2
T
(1+ -
2
n À R) - P Pn (I
(86)
Letting c --+ 0, we get
1
T2, - 20 11 R R
(1 DRARD - RUR
0²
20 u (
(I+
ARR PR
0²
8-1
(-1) +1
l x²
(I+ -2 An)
^n) - 0 nT) (- n
0² An)
A An
An
n -nn)
12 (I+
R 1 uR
This concludes the proof.
1 tx where 0 1-1-22 Under Assumptions
Lemma 35. Assume that x² = (1)) Let R R= =-
5 and 6, with probability at least 1 -8, we have
(D.) (blogdet(T++ ( (T(-----------)))((((())))------
(87)
33

---

Published as a conference paper at ICLR 2022
Furthermore, we assume Niu =0, we have
= 0 max( 1-29 1-2011
1-221 )
2 AR) (2
a 1,
(88)
(logn))
2-23-1
Proof of Lemma 35. Let
A= (1+ (R) Ag ( - (1+ n
-z AR)
(89)
where 1+a+2r 2n
<9 By Corollary 22, with probability of least we have
|||| Ō( 1-2v
(90)
When n is sufficiently large, ||-||22 is less than 1. Let B= (R)
AR) 11/2 Then [BI|2 -20 All2 Ö(n 2.122 ). Using the Woodbury matrix identity, we
compute (D,) as follows:
TD, = +4 1/2 1/2 ( (1+ -AR)
AR
(A) -123
blogdet AR)+ +
f ()
j=l
Tr
1-11
Σ
(-1)/ (1+ An
A (1+ (R)
1=1
= ( -=)
+
BY
j=1
Tr
(11 2 (T+ ~ 1/2 Bd (T 1/2
1/2
(91)
where in the last equality apply Lemma 27.
Let (xx) -1)
easy to verify that h((x) is increasing on (0,+-0)). As for the first term on the right hand side of (91), we have
logdet (+ AA (T
log(1+ App)
I+ -
R
Cxp a)
<P
h(
[1,19
= _
C5) 2/22 1/0
h 1 -d)
11/nt/a
34

---

Published as a conference paper at ICLR 2022
where in the last equality use the fact that 200 h(2 "x <o. On the other hand, we have
logdet
h
Σ h CHP
p=1
22
h Th Cx
[1,R+1|
=n n/
Cxx
=a(n
Overall, we have 3
- =
TT
As for the second term the right hand side of (91), have
Tr
(-11
B)
S
BI
25 R
Ō(n
(1-))
2u
==1
j=1
==1
=RÖ(n
1-a-2r
2a
)= Ō
-
+xa
20
As for the third term on the right hand side of (91), we have
Tt
(T+ (22
TH
Σ
(1+ 2 AR) -12 1/+
< _
(I+ 3 AR) 1/2 a AR)
021
1=1
B³ Ō ta+ 1-
<R
2n
74)
j=1
Then the asymptotics of TT (D.) given by
tot 1-at27
1 tx+ 1-a+27
=D, loogdet([+++ N Ar) [ (I+ -
2a
)+Ō(na 2a
=0(n )0( +N+ 2a
1-o+2r
=0(n=),
where in the last inequality use the assumption that K a-1-2r Since ( +xx 222t order term compared to (n=)), we further have
is lower
Ti. = (1 logdet(I+ 2 AR) [T (I+ AR) ())=)))((++(1)))
This concludes the proof of the first statement.
Let AI.R = diag {A.....An 1b 1 ( (x), (x)...))) and pi.= (AI.....RR.. Since A4 = 0.
we have (2,) = 2 M4 i fn (T+ 2 0 - 1.: According to Lemma 34,
35

---

Published as a conference paper at ICLR 2022
have
T2, = (I
n
T
?
A1:R) 11:8 #1:8
202
0²
(-1
1
n
AIR) (0 I.R 1-R-
(1+
1
n o An A 5-1
MLR 0z
/=1
2 M
(I+ A1.R) M1.8
0²
(-1)-t1
1
A Minn( (1 n A ATT
1-/12/ A ((10:(((TT)) (1+) 1117 1 A) ))²
5-1
(2)
(T+ 11
A1:n 1+//2 / A.1 PI.
(92)
where in the second to last equality we used the definition of (89). As for the first term on the right hand side of (92), by Lemma 15, Assumption 4 and Assumption 5, we have
2 MÍ. [++ n 0²
T
Mn:n A
12
Cpp-21
+ (1
0=23-1 1, a 28 1.
20
Cxp
(logn))
On the other hand, by Assumption 5, assuming that sup;2 P1+1 P:= we have
CRP."
22
2g 1: (1+ jz A
n MI. " 2
20
CXP,
C2i228 28
20 2
Ch(hi)-a
1-:0 1),
a 1,
O(logn).
a= 1.
Overall, we have
n (I AIR)
p1:== - max uax llog
20
n))
where k=
00 a723 1, 1,
20 02
a= 1.
By Lemma 16, we have
n CRp
22 (Cxpp
|[[ σ AI.)
-1
-1/ 1nn
1 Cxp-arp--
(93)
=maxx(n 2t RR RRl (2128t077)
=Ō(n -2+% 1-28 + +
Using (90), the second term on the right hand side of (92) is computed as follows:
7/2 A (1.) - j-1
T M
127/2 -
A A
22j
g2
(I+
n2
1 7/2 7/2
1:12 MIR
20
||
11 (-1+7) 1) (2)
n (1I+
-1:R)-147/22
-147/2 1 AT. p1
2j
0²
(94)
1=1
1
Ö(n
111 (1-22atat22)
(-1+>)6-1)
Ö max 2+ tota (20+0)))))))
1=1
= =0 maxt -2
2na 1
1-
+y+
+xx
(1-28+)7))
20
20
-2+ 1-042r
1-28 1
+x(1-
-28+ar)))
36

---

Published as a conference paper at ICLR 2022
Since 1+a+2r
14a+2r = 1, we have -24 1+a42r < 0.Also we have a+142
1 1-23
1+a+2r
+x(1-23+ar
20
1 1-2
1-a+27
+1+
+x(1 -x(11-3++nn)
20
(95)
1 1-28
1-
1
+1+
2a
1 2,3
+1,
where the last inequality holds because <
a-1-21 2r and y S 1. Hence we have 2a
T2 nD,) = 20 M
n I+
o² Ann)
Pi Ön max{ - 22 1:u 1-20 1 +x(1 (1112))))))
-O(n m 0.14 1-
log " n) Ö( maxt ( -24 1t 1-28, 1-nt2r +x(1-28+07)))
(n max 1 log"") n).
00 2 1,
Since Ö max (-24 11 2x
28
11
12: +x(1 +x(1-28+a7))) is lower order
where k
22
22
1, a=28 1."
term compared to mn (0.1+ 1-288 llgg n). we further have
Te,R(Dn)
n 20 2i. a² AI.) mm (1+o(1))
n1
This concludes the proof of the second statement.
Lemma 36. Under Assumptions 4, 5 and 6, with probability of at least 1-56, we have
Ti(D,) = 2
logdet(( (I+ -
-) Tr
(1+(1-(1+--)) (1+)(1)==((n))
n
(96)
Furthermore, let ô 8= 4 where 0 oiq<min!
(28 (28- ()6a-11--127)
we assume 140 = 0, we have
1a
20
Te(D,)=
(200 n 20 n (I+
02 +1)))=))1++((1) (1+)(1))
(n الا 1),
2,
(97)
O(logn),
a a 1.
Proof of Lemma 36. Let R=n te where 05K< 2-1-27 By Lemmas 32 and 35, with probability of at least 1 1-55 56 we have
+m(1-o)),
(98)
and
max +N) +N) - (
(T.n(D.)
29 28)
1-80- -- 1-20
(99)
as well as
Tı,n(D,)= logdot(T+ n
n Ar) 1 (Tr(I-(I+ o² And An) (1+o(1))=((n)) (100)
and
0(nmax(01+==2))
T2,n(Dn)= 202 20 T
gz 1 (1+o0())))
a
(101)
O(logn),
a=23-1
then have
Since Ön _ +x(1-a)) is lower order term compared to O = ), further have
n 1 (T+ - AR) -a) (1
(D.,,) = logdet(T -
AR)
(1+((1))=
2
37

---

Published as a conference paper at ICLR 2022
Besides, we have
logdet(I+ (1+ A) -lggdeet(
n
Ar)
00
log(1+
Ap) Σ
Xp S
Σ
Cxp ==
O
σ²
0²
R+1
D=R+1
p=R+1
"
02
=o(nt).
Then we have log det(I + AR) log det(I + A) + o()). Similarly we can prove
(T(--(1-AA)-) = Tr(I-(I+ ARR) - + o()). This concludes the proof the first statement.
As for T2(D,., we have
D,) (T -1)--
=n max max (0,1 1=28
log n) +0
( max 11.1-11 1-28 (1-28) -I-,0,,1 1-28 xxa)
= (n max
log nn) + 0 + +N) 11 222 (1-28)6 -1-k0, 1 ko))
0, a+23-1,
where use 8 8=n ",
1, a= -1
Since 0<<<<= and 0sgg<inn (28 (1
a-1-20
}. we can choose K << a-1-2r and
2a
da
20
2a
arbitrarily close to a-1-2r 2r such that 0 <
(28 (28-1)x 1)x
ko.). Then we have (1 +*) + O
1-xa+ (1-28)s 2x
+ and -xa -a++<+++0.. So we have
2
(axx log n).
Since (( +x)
1+ 1 -1
-1-ma,1 1-29 -ca) is lower order term
compared to (n max 10,1 22 log * n), we further have
o (1
20 M Te
(I+ n
AR) - (1+01)))
Furthermore, we have
[1+
n 72
[1+
AR PR
1 < 0² R=
Σ
-0
(1+ 22
R=
R= R+1
O(n (1-2)) +*))
=0( 1-28
Then have u TI+ 2 1= (I+ An) second statement.
pn(1 (
This concludes the proof of the
Proof of Theorem
Using Lemma 36 and noting that 1 > 0, with probability of at least 1-55, we have
E,, F = (D).)))))))
loggeet(
-T Tr - (I+ 1-+ n
AR)
2
2
n
T
n
AR) -1
us (1+o(1))
20
R
(n max +, 1-28
+1)
Letting 8=50, get the result.
38

---

Published as a conference paper at ICLR 2022
In the case of po> > O, we have the following lemma:
n +x where 0 < << a² Assume that po > 0. Lemma 37. Assume that o² = (11), Let R no
Under Assumptions 4, 5 and for sufficiently large n with probability of at least 1-46 we have
(1+(2 11 = 1-ka] )
(T.R(D.)-TT(D.))1--
(102)
of Lemma 37. As for
(Dn)), we have
(T.( [(+) DΛΦ -xx(())
PAΦT fx(())
o²
AA -x(x))
IRARDR y [((())
+ [n(x)" (1+
a²
o²
(103)
For the first term on the right-hand side of (103), we have
PA
2AT"
f(+
-(((())
fn((xx
x²
o²
TAΦT
) [n(x) + 1x((x)
DAΦ
x2
(2x(x) (T+
)
0²
σ²
TAΦT
TΛΦT
<2]]s=((x]lall(+++
fa(x))l++
(x)))
σ²
52]]
>
a²
Applying Corollary 19 and Lemma 31, with probability of at least 1-46, have
TAΦT o²
TΛΦT
[I+
fxx) (I+ o2 ) fn(x)
<20
1 1
(1)R))R1 29
Ō(V ( +11m)++ + 1)mR1-200
-2
+1m +2d 1-28
+ +oll + +1) (w)(11-23))
8
20
+ 1)m
1)
(22
As for the second term on the right-hand side of (80), according to Lemma 28, Corollary 26 and Lemma 30, have
TA fR(x) (1+
02 fxxx
(1+
R [((())
02
- BRRASRD
Σ
{n(x))
(1+
(I+
fn(x)
0²
0²
0 0²
--
R 1
1/ |[[
1
PRANDT
1R(x)11
(104)
σ²
Σ
Ō - iNa j0(( +(((++1mm)
1=1
- 1
+1)m
39

---

Published as a conference paper at ICLR 2022
By (80), have
T2(D,) (T.D,))TTn(D.))11-- (
+0l( 1 +1)mmt
=6 { +1 1) max +N) +N) 1-ka]
Lemma 38. Assume that o² (1)). Let R R= R= where 0 < K < min aa-faaa1110 a-1-2r 20-1
}.
Assume
2n o²
that Po > 0. Under Assumptions 4, and 6, with probability of least 1- 6, we have
T2,n(Da)=
20 Mb +0(n
1ife 2z 14 22 1).
(105)
Proof of Lemma 38. Let
n A= (I+
AR) 1/2
n (T+
+2 AR) 7/2 ?
(106)
where
1+a+27 20
<9 < 1. By Corollary 22, with probability of at least - 6, we have
|||||2 1112=0(m
1-2
2a
(107)
When n sufficiently large, ||A||2 is less than 1. Let MR,1 (Ho, and MR, = (O.
Then μæ = 1R, R.2- Let R = (.A and lo, = (0,1.....I). Then Ar = AI R.
Let B (T 2 An) 1/2 7 1/2 o Tn nT) + Ann) -1/2 By Corollary 23, we have
I.
[B]] = =0 /log 5 n² By Lemma 34, we have
(D,)(Dn))
2n 4 R +
AR) PR
x
3-1 f न. (I AR) - -nI] ( (I+ T - AR)) -nnnnnn(fff n
(11++
T
n (I+
An) un σ²
(108)
As for the first term on the right hand side of (108), by Lemma 15, we have
Chp-28 28
202 1 T' (1+ 1 2s
2
2 - max 221). 1).
202
Cxp-a
define Q1.j, Q2,j and Q3.j by
1 (I- (I+ (1- - An 5-1
2
[I G²
An)
-
nl)
n (I+ Ag) PR.1
Φz [1= (I+ ( - 8-1
Q2 = F
1
(T+ a
An)
( n1)
1
(109)
n
(I+
AR) PR.
Q3 = 1
1
IT+ n
Ar)
-1
1 t nl)
( (1= AR)
n
-1 A
f-1
R.2
n (I+
Ag) UR2
40

---

Published as a conference paper at ICLR 2022
The quantity Qs.5 actually shows up in the case of po = 0 in the proof of Lemma 35. By (92), (94) and (95), we have that
(-- 10-1 1--1it--+- a+22)) (-1)++1((1
)o(n max ) = o(n =(x= - )
2a
1=1
(110)
For Q1, we have
Q
1
MR,1 (1+ n1
B( A
11
-e AR)
AR) 1+ PRR.
σ25
1
|RR
Ag)
11 1
σ25
0²
R
=0(
log
log
nt))
8
where in the last equality we use
1B|12 1 0( / log _/- nz)
For j22, we have
Qi,
σ2j HR,1
1 T
(I+ Ar)
1 B (I+ 02
Ar) A 24)²
3-2
(I+ n
0²
02
B(+ o² An)
1+3 11,1
1
|RR
(1+ n
Ar)
1 1 A1 I1( 2 AR)- 1 11 11
22
=
O(og 8 n-
R
(1-2) 22
22 (1--)))-11)
R
0 0-210-ot21)
=000g 8
n
n
Then have
11 log f n2))
R
0
Olog
R
-n
5
210 a 12-)
)
0(log no)
R
(III)
j=2
For Q2,j we have
Q2
T
(I
AR)
1 B
(1+
n
-
5-1
(1+ n
A) 1+ 3/2 A A.R. R
22
R11
g2
||
|A
||
n
Ar)
147
A/4 1
|| |11
n
A)
1+ A 222222
σ2
0²
0²
=0ly
log
R
n nn
(-1
I[[[
n
A)
A)
11
22.2122
5
02
Since II(1+ A)
1+ 3 A
1 2222ll is actually the case of μO 0, we can use (93) in the proof of
Lemma 35 and get
[|(I+ A) - A 2 g2
AI.R)
-1+7/2
A 1/2
1.8
11
=a(n -2+7,
1-20 +y=x 1-2 11-xx1112aa0r 23
(112)
-2 122 +x=x(1123tar))
=o(n?),
where in the last equality we use x
28-1 a²
Then we have
Σ (-1)5+1Q2.0
Q2 2 Σ ol
xc
log
R
147 (-120-042))
-n
)= )=ol(
R log - b
(113)
41

---

Published as a conference paper at ICLR 2022
Choosing 7= 21+ 1+a++2r)
143a +2
1, we have
4a
T2, T2,n(Dn)=
20² M
T
AR) PR
mn 1-22 1
R n²) + + log 0
R #2
20 16
11
max max 1
20²
n +0(n
max 217 1 -
20
20
Proof of Theorem Let R = th where 0 < x < min 20-122-111
28
Since
2a
at
0 S q < min 23-1
2 .a) min a-1-2r _ J. we can choose < min n- 1-1122
2a
2a
a
and
-a-i 28-1) such that 0 g < min (1 ( 1-28 + and xx 0. As for (D,), we have
arbitrarily close to x << min
aa-1-2
(29- 11s
,Ra). Then we have
2a²
a²
T2 =2 (D.)
Dn T2 (Dn)
2x 1 + 0 max +770+2r 1-28 + (f+1))nmxx1+( 1-28 _1-xa)
20 1 + 0 max m 117042r 1 12 1)+ + 0 ( +,
20 16 +o())
By Lemma 36, we have Ti (Dx) = Ont)). Hence E, (DF) = Ti(D.) + T2(D,) 26 15+ +o(n).
D.2 PROOFS RELATED THE ASYMPTOTICS OF THE GENERALIZATION ERROR
Lemma 39. Assume a² (n')) where 1
1+2- < 1 < Let R naaaa-i +1)(1-)) Under
Assumptions 4, 5 and 6, with probability at least 1 5 over sample inputs (z;) we have
(1-a)
G.(D,)= 1+0(1) 2n
(Tr(I+ AAR) AR- An
112)) -Ad = 2/2 9
AR)
a
(114)
Proof Lemma 39. Let (D,)(Dn)) E 08.4 ( - Ti,x(( (n))), where R = n for some constant C. By Lemma 32, we have that
=
= [B (( 00
(115)
=0( =
Define n2= = 21 (Xn+ 1)... ( and x (0 As for GI, we have
G1, E (zn+ (z)+1 (D - (D))(Dn))
ARA
1
T k
E (an 1:80a 11)
logdet(I+
Rt
)
Tr(I- - (I+
2
(llodde((++
TRA
1 Tr([I (I+ 2
BRAn y-1)
2
(116)
1
TRANTR
$ DRANDT
E logdet
logdet(I+ +
2
o²
0²
A T Tr Tr(1-(1- (1+
RnAn T
B(za-1 Tr(l-(I+
)
)-1
2
o2
42

---

Published as a conference paper at ICLR 2022
As for the first term in the right hand side (116), we have
4
DRARTH
PRAR
E i logdet(T+
logdet(T+ 0²
2
σ²
A A 1
logdel(I+ + ARDRIR
1 logdel (logee
2
1
1 R AR
ARDHOR
11 logdet(I+
-logdeet
2
0²
1
AnDROR (I+
An
A
[( logdet
(I+
2
x²
σ²
0²
An
Annanl
11 logdet
I+(I+
R
2
σ²
1
1
An
E (0 log
1+
y-
A
ARRR
2
g²
Let
n Ar) - 1122
1/2 ( (1+ n AR) σ²
A= (1+
(117)
According
Corollary 22. with probability of at least 1 6, we have ll A
O(y log 1- (1+2rit
= o(1). When n is sufficiently large, Al12 less than 1. By
Lemma 27, we have
AR
"ARTR
0²
An) -1 An ( on (nnnn))))))))))))) ) (T+ g² An) An)- AAnn
T =
AR)
Annnn
1-1 T
(I+ σ²
(T+
02 o2
AR) ARRRR+
+
8
111
1
1n
T
[1+
AR)
R
A (I+ 02 AR) A 1/2
j=1
[I+ 0
AR) -1
ARRRR
+
1
(1+
n
AR)
1/2 1/2
A
7 2
g²
j=1
Oxp
Uxp a 1+nOxp-0102
pp (n++1) 1+n0 //2
Oxp 22T
1+nCap 0/022
1+nCxp -a/0 0/02
(1
All 1( (10+27)(1-))
<0(n
-
(1-++2((1-1)
=0(n
=o(1),
(118)
43

---

Published as a conference paper at ICLR 2022
where use Lemma 15 in the last inequality. Next have
DRAR
DRANDR
(ogdett
logdet(I+
x²
0²
F(ontti log
1 1R(
(14
ARTRER 1
0²
0²
ARDRIR ARRRIR (1+0(1))
2
(T((T+
An
A
R An
(1+0(1)).
2x²
0²
where in the last equality we use the fact that E ((
1 I. By Lemma 27, we have
Tr(I+ An
AR
02
0
=Tr(I+ AR)-
1-1)'T
(1+ 1 AR) (1+ AR) -AA
j=1
=Tr(I+ AR)
AR+
(-1)Tr
(1+ n
AR)
1/2 1/2 1/2
A' n
72 AR) 11/ A/
2]
==1
By Lemma 15, we have
n Tr(1 -AARRRAA
AARS
R
Cxp a
=0(1
(-=)(-=0)
0²
++CCap 1022
p=1
Cxp
(1-a)1-0)
Tr( マー Ar)
AR
=0(1
+
1/2
Overall,
Tr(I+ 2z AR)
- 0 a1
(119)
Since Al =((), we have that the absolute values of diagonal entries of yby A are at most o(1).
Let (Ar) p.p denote the (p.p)-th entry of the matrix A1, Then we have
Tr 2
n (I+
AR)
1/2
A (I+
1/2 1/2 0²
AR)
A
02
R
R
Pozs
(A))
P.P
Xpll
2i
AlE
On
(1--x1-1)
jō(n
(11-0+2r-(142m)
(logR)//2),
(120)
l+ndp/o"
1+n
p=1
1=1
where in the last step we used (119). According (119) and (120), we have
RRAR#
logdet(I+ (1+ 1 R
E (1 logdet(1+
o²
o²
AR Tr(I -
R
AR
(1+o(1))
20
8
(121)
+ O(n (1-w)(1-1
(1-01119)
)0(n -1 -0 (1+20))
(log 1/22)
O(n (1-))1-1)
) 0 (--)(1-1)
[0(1)= = (1-))(-1)
/o
(Tr[I+ n
Ar) -1 AR (1+o(1)).
20
o²
44

---

Published as a conference paper at ICLR 2022
Using the Woodbury matrix identity, the second term in the right hand side (116) is given by
$RAR
DRARDH
Bi 1:26. 11) Tr(I (141-(14
(1+
T
2
o²
o²
1
B 11)
1
In(I+
-
RR(I+
A
-1
-A
2
σ²
o²
σ²
((
(I+
Ap
An
27 n) An
2
0
=
B( Tr[I+
Tr[+
An
Tx
2
σ²
σ²
B( Tr(I+
An
T
2 R + -² Annnn) Tr(1 + - An An
2
(T+ A R
n A
T (1+ g² An A fn)
E [[aa41:
Tr
2r2
1+ [+ J= A n -IAni
where the last equality uses the ( Ax
formula. According to (118), we get
E (( Tt (I+ An R An
02
20
M/
p - ARTR (1 1
0²
B(zn 19th 11)
Tr([+ + An - AI 0² A
202
1+0(1)
1 Tr(I+ 02
1
AR
A
AR
202
1+0(1)
1/2 (T+
1 1/2
//2
A
20²
1+0(1)
1
An
1/2
11/22
202
gz
= 1+0(1)
Tr(I+
AR
1/2
A
(++
1
1/2
0 13
202
0²
0²
1+0(11
20²
||
1/2
(I+
0²
A
R
1/2
1+0(11
||
2 R
(1+ (1+
- AR) 1/2
(1
-
1
A)
n (1+
- 0
AR)
1/
20
0
where in the penultimate equality we use Tr Tr(BB")=
F. | e is the Frobenius norm of A, and
the last equality we use the definition of A (117). Then we have
1+)(1)
11
1/2
(T+
n AR)
1/2
1 0²
A)
(T+
n2 0²
An)
1/2
20
02
1+o(1)
||A
1/2
(1+
n2 AR) 1/2
(1
A 41)(1=
+ -
n
112-1/2122
202
0²
j=1
1+0(1)
||
1/2
n (T+
An)
(-13
1/2 (T
2
-12
n
1/21/2
20
0²
2
0²
/=1
(122)
By Lemma 15, we have
Cxp (1-)(1-0)
1/ (T+ 02 An)n)~11ex>
(1+nCxp (I
Cxp
1/ (T+ Φ2
An) 1|
(1+nCxp o//20)p0 (n
(-=
45

---

Published as a conference paper at ICLR 2022
Overall, we have
| (14 n2 (
||== On
(-a)(n_
20
(123)
Since A11
log f1 n
20
(1-272 2a
=o(]), we have
マ2 A
1/2
(1+
-1/2 11/2A((1+ (1+ n AR) 1//2// AR)
0²
0²
1/2
(T+
02 AR) 11/1 |||| Al (T 02 A/2-1/2112
(124)
(n (--)(1-0 )((n
-1-
(ogR))/2)
where in the first inequality we use the fact that Lemma 15, we have
|AB|I S ||A||=|BBl2 when B is symmetric. By
TrA R
1/2
n2 (1+
AR)
1/2 R
n (1+
(1+
AR)-1/2A
A//2
1/2
2/ AR) AR) 1/2
2
02
02
ft Ap ( PPP
n
Al
On
(-ا)حاo1 )((n 11--0+2--
(logR)//2).
(I+nAp/02) p=1
(1+2dp 02ح3
(125)
According to (123), (124) and (125), we have
$ R
R
- (T+ $ @xdROR)11 11
Tr(T- (T+
Tr(T
2
0²
o²
1+0(1))
1
Tr(I+ + 0²
ARD
-1 AR(
+
ART D2)
20²
0²
1+0(1)
|A (I+
1
n
An)
-1 Σ
1-13
AR
1/2
(I+
AR)
1/2 11+ An)
1
20²
0²
22
σ²
σ²
j=1
1+0(1)
||
1/2 [I+
n
Ar)
11
8 Σ
n
AR)
1/2
1//2 (1+
AR)
-1/2
20
0²
22
0²
0²
)=1
F
+2TrA
1/2 R
(1+
n
AR)
A
n (1+
AR)
-
1/2 A (1+ n AR) 1/2
22
/=
1+0(1)
O(n
(1-01-11)
O
(1-) a
1
1 11-022-
2a
(log Ry (logR) 1/2
20²
2
1=1
+2
x
1
(n
(-a)(iit)
)0(n
2u
(logR)0/2)
22
j=1
O(n 0-m1011)
1+0(1)
A (1+ oz AR) 112.
20
(126)
Combining (121) and (126) we get that (r,)(Dn)))) [+o(1) (Tr(I AAR)-'ARR 2 AAR) = 0 (1
20
From (115) we have that (D,) S
(D,)(Dm) + (G, (D,)( 0 (--21-0 an
Choosing
R=n R=n(aa (I +1)(11)) we conclude the proof.
Lemma 40. Assume o² = Onn') where - 1+27 <t< Lers D. Assume that 11112=11. 1. When n is sufficiently large, with probability of at least 1 1- 28 we have
- (1-()).
(127)
46

---

Published as a conference paper at ICLR 2022
Proof of Lemma 40. Using the Woodbury matrix identity, we have that
((T+
σ² - - Ag $
=0 = A
(128)
(1 AsE.
Let (I+ ( n 170
As) 2/2 where y > 2a(1-1)
By Corollary 22, with probability of at least 1 8- we have A = =(n 1+0+2-- - (1-)).
When is sufficiently large, 1/2 All2 is less than 1. By Lemma 27, we have
(I+ oe As4505
=(I+ ( As)
11
1 (I+ n 02
A As(0g0s-n1)) (I+ n As)
0² As)
0²
Then have
+ 3 As
T -
AsEl12
) (I+ 0² As)= Ase
[I+
As) - Σ
1)
(I+ n
02
02 0²
j=1
[[[+ 02
AA
Σ
(1
(T+ n Ass mn) (I+
- Ase
02
j=l
(129)
For the first term in the right hand side of the last equation, we have
o² -= 0(n ((n-1))))
[I 02 As) AsEl12 || -
(130)
n
Using the fact that || All2 = Ö(n 1 +uttar((42rtau)) - and ||(T As) ( S 5n- we have
As)
(1+ n (s) Ase
1
(1+ -
As)
1+3 1--
A((1 22
As)
1 1 1/-
A(I
As) -1 A 7
Ase
-2
2
5n (1-11 1)(
1+ (-1+))0-1)) 1(
10 (112 -jy(1
2a
Ag) 0²
11 A33 $ E|122
=ō(n (1-
2a
I[
1- As) - 02
112111112
=ō(n -11-1)) 11ام 11320 2m
)0(n( (1+71111))))1
=Ō(n (1-+)+ (1-1)) -1=tt2-11+2:10
(131)
Using (129), (130) and (131), have
[|(1+ 4A4 -AsEll2
Ö(n (1-t)) ))
Σ O( (1-422
2
1=1
(132)
((n=(1-1))+0
14 (112r)
-((n-(1-1)
47

---

Published as a conference paper at ICLR 2022
By Corollary 20, with probability of at least 1 1-6, 8, we have
|0 - A
+1)mll(T+ -AsE(| *AsEl12)
=ō(V ( +1)n.n
From (128) we get |l + proof.
Õlv (1 +1)n.n (1-)). This concludes the
Lemma 41. Assume o² (nn') where 1 1+2 <t< Let ó n where S q
1--1++2(11-0122--1 Under Assumptions 4, 5 and 6, assume that μi = O. Let R nl (x)(1-t) 2-1-22+(14222 Then with probability of at least 1 - 65 over sample inputs (2+))==
where 0 <<<<< a-1 2a (1-(1-
we have G2(D,)) (I+((1)
II[+ AR) "2Rl2= (n (0mxx(22(111) 22(111111) 0-2000-0) log 1/3 n). where
20
0,
2 -1,
k
1,
=0 1.
Proof of Lemma 41. Let S = nD Let (2,s(D,)) Ei 1. u (T2,5(Dn+1) ( By
(2,s(D,))
Lemma 33, when S max(1, (--i- with probability of least 1 30 we have that
(G2(D 22 (D,)l || = |B wn+1) (P T2,5 (Dn+))D (7 [
= Ber 0 (1 +1+1 1) (n+ 1) ( - /
=Ō (1) +1) f
Smaa 112 1/2 1
(133)
(134)
Let irS diag ( 11.5 (x) Φ2 (x), os())) and p4s (11,..,s)))) Since
No = O. we have Te.s(D,, = x " + oz I.sA " 1-P1.sH.. Define mh.s =
(o( 1)a and 11.s (... )T In the proof of Lemma 34, we showed that 1
1
T2,s(Dn) 20 M
x"
[1+
11.AA1
(.s)
1 #1.S41:
r²
1
1
1
1:5
11:8
Ans
M1ss u
σ²
We have
G2,s(Dn) E (s., Me (22, - T2,)(Dn)))
1 T
(++ 1
=I =B(pn4s
11 \ 1:s Mss
-
A
1:
0²
A1s A1sT55s) -1 mn:s
-
1
A
11 (miss)
-
2
11
g²
1
-B
5
1:5
(1
A
M U A (I+
( Ans
14188
1
(1+ H 4 A
(4 ( P1.)
=E -E(entidhes)
202
1:8
1 1+ - 21.5) - A1.57:s
m1.))
1
T PT.
oZ
A D1.)) M1s)
= -B(rati
20"
1t 4 J A $ 21.8)
A1:s7::
1+0(1)
1 02 VT. (1s)n:s) I (T+ Φ AnsTTs p1:5
11 IT
202
1+0(1) T
1
P (I+ 1 0² TTs -1:s
M.s((I
p1s8
20
g²
1+o(1)
||(T
A
T p1.l1.
20
(135)
48

---

Published as a conference paper at ICLR 2022
where in the fourth to last equality used the Sherman Morrison formula, in the third inequality we used (118), and in the last equality we used the fact that E(z, 1.261 11) =I.
Ahermann-Morrion
Let R (R.......... R
Then we have
1 I[[+
1
1
Aus
(:s)
11s - (1+
A A.s 11s)) ( (1.
σ²
IKT+ 0²
A1ss
P1s)
pass (T+ o²
A1s
1.S)
i 1 ||[+
A1s
1.5 (M:))--)
1:5
(136)
Let R = (l (1) where 0 < < a-1-2r+(142r)
Lemma 29, (62), we showed that with
(0-(1-t)
probability of at least 1-
(I(T 3 An fR.))
p1.ll22 0 0-n 12 hog*/2n)
2/2
(137)
= =[1+o())]|(+++
A1.)) - M1:R12
where ho [0, 2xx 2,3-1111
11 20==23-1 The same proof holds we replace 11:8 with L1.s. AIR with A1ss
and p1. with f1:R. We have
[[I A1 ff
mn:nll2 = (n (1)x(-1)m 1-20
20 1og
1/2 1l0gh/22)
(138)
n = =(1+o(1))l(T+
02 A1:)) 11:R122.
Next we bound [I + 32 A1. i:s (
pl)e)lle. By Assumption 5, we have that ||Mi:s P1.ull2 = O(R - ). For any & ERR and || 1, using the Woodbury matrix identity, with
probability of least 1-26 26 have
1 (1+ A
=15"
1-
A1s (ss
(1+
UISAASHTs -21s (HIss- (1:))
= (5T(Mss--A (1:
S A
1
D - 1 - pI.n)
o²
1
1
<1 -
15
A
(1+ $
D1sA (M1: - p1.R)
1
5O(R
(1(
P1sAA1
-
P1.s -
o²
=O(R
00
[ (
(1)n)n
(
1
=0((=+1)R==
where in the second last step we used Corollary 20 to show [[ () Olv / (2++m)mR= 1-32 with probability of at least 1 8, and Lemma 40 to show that
II(I + 1 2 2 (T.)) - P.sAnse12 = ol 0((()+1)n nー with probability of at least
1-5. Since R R= -nn (2 (1)--1),, we have
[T -1++=Anss (1.)) 1 ( -1::) = +1)n (12810--) (1-20)(i-t) 2a
Since is arbitrary, we have [I( + 1 A.s D1s)) - pn:R)l2 = O(
201a 20111 Un) Since 0 5 q < [==[+2)[[-]](23--) and 0 < k < 2-1-2+
1)n
20
(1-01
choose a-1-22 (1+2-11 and is arbitrarily close to e-1-2r+(1-27) such that (a²(1-1)
2a-(1-1)
49

---

Published as a conference paper at ICLR 2022
039 (28-1)
Then we have (1-28)(1-()) +q 0. From (136) and (138), we have
1 I|[+ a²
A1 1:9 11:))
M1 0 max max
(2-2--1)) llog (2) +0()
+1)n (1
(1-2011-1))
2n
2011L
=0(mmax(-(111))
2a
log k/2 +0
2200
2a
2011
2
= -n (-221)1-1) log 2/2
=(1+o(1))I(++ A1:s) fu1:1112
=(1+o(1))I(T++ (1)) An) 7Mel22
(139)
Hence (2,) 1 |[[ 2 A1. TT Then by (133), we have
1:9 11:s) P1:s11 | O( 0( 2-222 log 22)
G2(Dn)= mux 2(1-t), (لاار1
llg h/2n) +0
( +11
n σ²
Smaxx (umx(112-811--22)
Ltg+ 2دقة (1-1)
max 1,pa-
Choosing =
we get the result.
Proof of Theorem From Lemmas 39 and 41 and 1 a 1-1> 2, we have that with probability of
least 76,
B,G(DD)= 1+0(1) (Tr(I+ And - A 1 (I+ (I AR) 11 1[I+ AAAn-'nnl
202
0²
= 0 a1 aa)li 6 )+ max( a 2010 ) log 1og 222
0n max (i-a)(--)) (1 )
(140)
10, #3 1
where k: =
2a=2: 23-1 and R=n(++))0-0) k>0
1,
Furthermore, we have
Tr(I (M(+==A) n 0²
-T
n
AR) -1 AR
0²
CAp a 1 n Cap
"xp-== n σ²
0(RRR
R=
p=R+1
p=R+1
(1a(10) +k))
=o(n (-mi(1-1)
Then we have
Tr(I+ 2
An == AR)-IAR TT=+=
)2 -) -1A11A1000000 A(1+0(1))
(141)
Similarly we can prove
|| 1/2 (I+ デ AR) || ~) 1 (1+0(1)
(142)
n
[I(++ AR) 1 [[|
π A) -1 (1(+0((1)
(143)
72
Letting 8 8- 77, the is complete.
In the case of po
have the following lemma:
Lemma 42. Let 0 = n where 0 S < [o-( Under Assumptions 4, 5 and 6.
4nd
assume that Mu > Then with probability of at least 68 over sample inputs (I:)7= we have Gz(Dn)= 2 10 o o(1)
50

---

Published as a conference paper at ICLR 2022
Proof of Lemmaa 42. Let S = n?. Let (2,)(D,)) 1 (T (T,,(DD)). (.. By
Lemma 33, when S> n1 max(1, (-- with probability of at least 30 have that
Ma+ (1000
= ((
0 + +1) (n+ 1) S -
= Ö ((: (1)+1) +1) 2 n (10aaxx1122111111 (,122,
ox(x)) (x).,,())... Let As = (iag()),.... )sh. Vs = (01 (x), @1 (x).
and μs = (fI...., Us)) Define and @s = ns)) )" By the same technique as in the let - and show the counterpart
7s = (zu (In+1 1.++1))11 (#n+1),... (xn+:))..,0((xx++1
proof of Lemma 34, we replace AR by A. of the result (135) in the proof Lemma 41:
G2.s (D,)(Dn) =B (an+ Ma+1)
(T2,s (Du41) T2.5
11 (I 72 T33 t $ 1 As us
=
-Bepnt
20
1+ 1
[I
Ag AsTs
(+0(1)
(I
D5
$5A
15 T [++
(T+
As
As 4s)
us
20
0²
1+0(1)
1
D
s ) (I+
05 ps
202
0²
0²
1+o(1)
1
I1(+
Ag 0²
Usl12
202
(144)
where in the fourth last equality used the we used (118), and in the last equality we used the fact that E(z, 1.2441) 1.
formula, in the third inequality
Let n (Ho Pn. ===
= R Then we have
A 14s [1(T
A5 inll2 + || A5 (ns jn)) 2|
[[ 02 As ' [I
A
iull2 - | As (Ms - ( 43)
σ²
(145)
Choose R (1-(1 where 0 <<<<<>
0- 2- In Lemma 29, (62), we showed that with (1(-+)
probability of at least 1-
[I(T + 3 A 2 ian 1I.)
11:1112=11 p (1-))ax 1,122 1lg k/2 2/2
(146)
=(1+o(1))l((T+
nh o2 A1R) 11.2l12
S0, 2,3
where k
The same proof holds if we replace P1.8 with D1.s. ArR with A
11 2a -."
and f1:t with fi.n. We have
[(T A1.
D1s) ( (m (1 -t)max( (1, 1118 log
(147)
=(1+o(1))](T++ o2 A1:)) f21:1112.
So we have
[11+ (14451905055
"oo O (1-txaxx(- log k/2
(148)
+01).
Next we bound
[I(T + 1 A5 (us pn)ll2. By Assumption 5, we have that
||s falll2
O
1-20 2
For any & R and ||E|| 1, using the Woodbury matrix
51

---

Published as a conference paper at ICLR 2022
identity, with probability of at least 1-22 26 we have
(1+ 1 ( (
As430s)
02
=|6² T- As 1 D5. (Hs- pn)
= (ws
1
1 25
- -s(ss
< Kélaalus 4 -
As
25A5 (s(us-
1
SO )
(1+
$
=O 12
0(1
1
=1 1 11)
=0((++1)R**
12
where in the second to last step we used Corollary to show |[ p | = (
with probability of at least 1 8, and Lemma 40 to show that II(T + 1 5 s (2--)) 11=+--n--a-0)
O + +)m-n
with probability of at least 1 1- Since R R= +x](1-() we have
(e As03 11 (1:0)ss)"((ee (mus ju))== - +1m 20
a1 a-2010-0 (1 a1-200-0n
Since & is arbitrary, we have |I(7 + $5 1)n (--011=t), ( Since 0 $ q <
jR)ll O
(0-(++r)[--(](38-11 and 0 < K < 2-1-2++(1+2-2) (1-(1-0)
1a
2 and is arbitrarily close --1-2r+(1-27) such that choose a-1-27 21-(1-1)
20-(1-1)
059< (28- (18-1)(111)) Then we have (1-29)(1-)) +9<0. From (145) and (148), we have
2
I|(++ 4444A4$5555
-))axx (-x (1-0)
1, 1-28
log 1/2 +0([+
(1228(1-0) (1-2811-0k Ol 20
= (1 (1-)maa 1-20
log k/2
=o()
(149) Then by (144),
Hence (D,)(Dn) = (+o(1)
|1(1 + As usl
2 + o(1).
G2(D,)= 2 11 (()))))
1/2- 1/2-8.1-a)]
max 1
Livi 28-1
[1-)]
Choosing S=n
mm
we get the result.
Proof of 11. According to Lemma 42, (2(),)= - +o(1. By Lemma 39, have Gi (D,)) =(( (1-a)(-t) Then B.G(D.)==G(DD))+GG to().
52

---

Published as a conference paper at ICLR 2022
D.3 PROOFS RELATED THE EXCESS MEAN SQUARED GENERALIZATION ERROR
Proof of Theorem 12. For p4 = 0, we can show that
( B.r, ( []]+1]]
= -EE,
to model-nn y [x
-E In
to model (n) 1 ( (Du++)) (o-+te))p -17" 1s?
-EE 11 In" AΦT (DAΦ ( to - model (n)
-Exati [n] (AT* to model [n)
1 ) T)
=dre TrA1 TrAT" (FAT" to !n)
T+
T+
A T
modal
Tr(I+
A
A-Tr((+
A# T o model
1 A+
(1+ (++==-10')) Φ) 1111
moodel
moddel
ioddel
According to (139) from the proof of Lemma 41, the truncation procedure (133) and (143), with probability at least 1 we have
10=0)=1- -1-11 0( max( max(-2(1-1)) (1-20)(1()
II(++
log = =
"model
model
0,
2x
where k
1,
20 =3
1.
According to (121) and (126) from the proof of Lemma 39, the truncation procedure (115), (141) and (142), with probability of at least we have
Tr(I+ Ar -A -ii-Tr((--
A0 ) -2A
Tr
A) A) -
(1-a)
= =O(n
Combining the above two equations we get
(D,
Trun (T([+
(I+
AA) +
+|[[I n
A) -
model
modell
model
model
Line (n
(1-a)(1-t
0 max (21-() (1-28)(1-)) 1ogg//22)
1-a-t
) +(( maxl (1-23)1-1)
1og x22
1-
(1-20)(1-t)
max
When > 0. according to (149) in the proof of Lemma 42 and the truncation procedure (133), with probability of least 5 we have
(D,)
(-
) +
=14 +o().
53


Reviews:
[{"review_id": "wpZ0vBhC5GS", "reviewer": "Reviewer_nLLV", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths\n- The early sections of the paper are clear and motivate the paper well.\n- The results appear to be interesting, the problem of characterizing learning curves for Gaussian processes under mis-specification is important.\n\n## Weaknesses\n- Parts of the main results feel like a bit of list of results. I think the exposition in these sections could be improved by providing more context for each result as well as how the results differ. I would like to see more examples of how they apply to concrete examples.\n- It isn't entirely clear to me how to interpret the results. In particular, the rate of decay depends on the smoothness of the kernel (unsurprising), but also on how quickly the coefficients of the observed function decay with a decomposition with respect to the Mercer basis of the kernel. I suspect that they can only decay quickly if the function is smooth, but the converse is not at all clear to me. I realize you cite other papers for this result, but for the purposes of being self-contained.\n- The connection to neural networks is interesting, but the result is really a result on Gaussian processes. The connection to neural nets seems a bit orthogonal to the results in the paper, and I am not convinced it should be emphasized so heavily.\n \n## Questions/comments\n- Make explicit if $f$ is assumed to be in $L^2(\\Omega,\\rho)$ (I assume this is needed for the decomposition in eqn 9).\n- Does $\\phi_0$ in general depend on $f$? If so, perhaps consider noting this for clarity. (My understanding is that it is the projection of $f$ onto the orthogonal complement of the $\\phi_p$).\n- The assumption that eigenfunctions are uniformly bounded seems quite restrictive. I realize it is present in at least several other works in the GP literature (e.g. Braun, 2006, Vakili et al 2020). However, I it seems somewhat restrictive (for example for a squared exponential kernel and Gaussian inputs, this condition doesn't hold, Zhu et al 1997 eqn 44, of course this also doesn't have polynomial decay, just an example where the bounded eigenfunction condition doesn't hold). The authors provide an example on the sphere where this condition holds. Are there examples on compact subsets of $\\mathbb{R}^d$ where this condition holds? Alternatively, can the results be generalized to relax this condition? \n- If I understand correctly, Theorem 8 in some sense corresponds to the \"unrealizable\" setting, in which the target function is outside the span of the features. In this case, should the question be about how accurately the posterior approximate $f$, or how accurately the posterior approximates the projection of $f$ onto the span of the features? (Essentially, I am wondering if this result is in some sense vaccuous in a not terribly interesting way). Any insight the authors can provide would be helpful.\n- I am concerned remark 10 is incorrect/misleading and I would appreciate clarification. If I understand correctly, the suggested conclusion is that a sample from the GP prior (almost surely?) satisfies the decay conditon with $\\beta=\\alpha/2$. I don't see why this would be the case. In particular, for this to be true, it seems we would need there to exist a constant $C$ such that $\\sup_{p} \\omega_p \\leq C$ which is almost surely not the case. Perhaps this only contributes some log factors (see Boucheron et al, 2012, Section 2.5), which will end up hidden in the $\\tilde{O}$ notation anyway, but I think some subtlety may have been lost here. If not, I would appreciate clarification.\n- Can lower bounds on any of your results be established? I realize this may be beyond the scope of this paper, but it would be interesting to know if the upper bounds presented are optimal.\n\n## Minor comments and questions:\n- \"For inputs distributed uniformly on the unit interval, Ritter et al. (1995) showed that $r$-times mean square differentiable processes feature an asymptotic power-law decay of the form $λ_p∝p^{−(2r+2)}$\" --Does this not follow from the earlier work due to Widom? Is the difference that Ritter doesn't need to assume stationarity?\n- Distributions and densities seem to be conflated slightly in the problem setup. In particular, at times $\\mathcal{N}$ is used to refer to a distribution while at other times it is the density of the distribution.\n- When citing a textbook, please provide a section or page number. \n- For Mercer's theorem to apply you need some assumptions on the kernel/input distribution. A relatively standard set of assumptions is compact support for the input distribution and a continuous kernel, though I believe there are more general formulations. \n\n### References for review\n- Bucheron, Lugogsi, Massart. Concentration inequalities. 2012.\n- Braun, 2006. Accurate Error Bounds for the Eigenvalues of the Kernel Matrix. https://jmlr.org/papers/volume7/braun06a/braun06a.pdf\n- Vakili, Khezeli, Picheny. 2020. On Information Gain and Regret Bounds in Gaussian Process Bandits. \n-  Zhu,  Williams, Rohwer, Morciniec. 1997. Gaussian regression  and optimal finite  dimensional  linear  models.", "summary_of_the_paper": "The paper consider asymptotic properties of Gaussian process models where the eigenvalues from Mercer's theorem exhibit polynomial decay. Unlike the earlier analysis of Sollich, the authors do not assume that the model is correctly specified. The authors provide a short experiment to illustrate the theory.", "summary_of_the_review": "Overall, the result seems interesting. I have only minor concerns about the correctness, but I think these can be resolved (or it is possible I have misunderstood). I think the exposition could be improved to provide better context for the results, and tie them more concretely to real problems. Overall, I think the paper is above the threshold for acceptance. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "OXEFM9ifQsy", "reviewer": "Reviewer_N1ou", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper uses the negative log marginal likelihood and its relationships to Bayesian generalization error to give interesting generalization bounds. The paper largely cites previous theorems for most of its theoretical distributions and under power decay assumption, they use the log likelihood formula to derive bounds. However, it is unclear how novel the contributions are, other than plugging the power decay assumption into the previously derived formula. Furthermore, the relationship to NTK is only briefly touched upon. \n\nGiven that the paper is largely theoretical, I believe there should be more emphasis on the technical novelty and the difficulty of extracting an asymptotic expression for the loglikelihood formula given the strong assumptions made on the kernel spectrum. For example, what is the novel theoretical contribution for showing that \n? Doesn't it follow from a matrix concentration inequality? If it's an nontrivial application of matrix concentration, can you point out how it is nontrivial. I also saw that you applied a spectral truncation argument. Is this argument necessary and/or novel? Perhaps emphasizing such points in the main sections of the paper would significantly strengthen the paper since it seems like the reader would need to infer the non-triviality from the appendix.\n\n**Update: The authors have significantly strengthened the theoretical understanding of the problem and the intuition/novelty of their techniques.", "summary_of_the_paper": "The paper summarizes the generalization error of kernel ridge regression and Gaussian processes under a spectral decay assumption.", "summary_of_the_review": "Since this is largely a theoretical paper, it is unclear if these results are novel since it seems like just plugging the power decay assumption into the log likelihood formula.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "J4coNc_3EUc", "reviewer": "Reviewer_e3WT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Studying the asymptotic decay of the generalisation error for power-law spectrum and target function decay is a classic subject in the Kernel ridge regression (KRR) literature, where these are known as capacity and source conditions. Indeed, the rate $n^{\\max\\left(\\frac{1}{\\alpha}-1, \\frac{1-2\\beta}{\\alpha}\\right)}$ reported in this work for the decay of the generalisation MSE is known in the KRR literature. The exponent $n^{\\frac{1}{\\alpha}-1}$ appears in Caponnetto and De Vito in 2007 [1] for optimally regularised KRR and a particular choice of target decay (eq. 19 of [1]), while the branch $n^{\\frac{1-2\\beta}{\\alpha}}$ was reported more recently in [2,3]. The existence of a region with exponent $n^{\\frac{1}{\\alpha}-1}$ for other choices of regularisation and the cross-over between these two regimes is a particular case of the discussion in [4] (cross-over between blue and orange regions in Fig. 1, with purple point corresponding to [1]).\n\nIn my opinion the biggest contribution in this work is to put on rigorous footing some of the results appearing in [3,4] which were derived using semi-heuristic methods, and to extend them beyond the Gaussian design setting (note that [4] provides numerical evidence suggesting this decay holds more broadly) within the GP framework. \n\nI do believe this is a valuable contribution, but the way the authors present it with respect to previous literature - specially in the abstract and introduction - is misleading. For instance, the abstract suggests the rates and cross-over reported for the MSE are new, and fail to cite [2-4]. The introduction only superficially makes contact with what is known from the KRR literature, and would benefit from a discussion like the one sketched above. \n\nSpecific comments / questions / suggestions:\n\n1.  Top of page 5: *As mentioned in the introduction, this assumption is adopted in many recent works (Bahri et al., 2021;\nCanatar et al., 2021; Nitanda and Suzuki, 2021). Velikanov and Yarotsky (2021)*. \nThis is a classic assumption on the KRR literature, and to my knowledge were introduced by Caponnetto and De Vito in the mid 2000s, see [1]. They are commonly known in this context as source and capacity conditions.\n2.  Proof sketch, top of page 6: is there any intuition behind the choice of truncation $R=n^{\\frac{2}{1+\\alpha}-\\kappa}$? Can this be related to hypercontractivity property in the concentration results from [5]?\n3. The notation for functions, vector and matrices is confusing. Explicitly writing the conventions used, or writing more often the dimensions of vectors and matrices could help clarify this. For example, $\\Phi_{R}\\in\\mathbb{R}^{n\\times R}$, $K_{n}\\in\\mathbb{R}^{n\\times n}$, etc.  \n4. Figure 1 is very hard to read, as one needs to zoom +300% to read the axis and caption. The matching of the power-laws would be easier to visualise in a log-log plot in terms of the slopes.   \n5. Remark 14: As mentioned before, even though [4] derives the rates for Gaussian designs, they provide numerical evidence that this result works more broadly.\n6. Is it possible to recover the other rates from [4] from the GP framework?\n\n[1] Caponnetto, A., De Vito, E., *Optimal Rates for the Regularized Least-Squares Algorithm*. Found Comput Math 7, 331-368 (2007). https://doi.org/10.1007/s10208-006-0196-8\n\n[2] Stefano Spigler, Mario Geiger, and Matthieu Wyart. *Asymptotic learning curves of kernel methods: empirical data versus teacher-student paradigm*. Journal of Statistical Mechanics: Theory and Experiment, 2020(12):124001, 2020.\n\n[3] Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. *Spectrum dependent learning curves in kernel regression and wide neural networks*. In International Conference on Machine Learning, pages 1024-1034. PMLR, 2020\n\n[4] Hugo Cui, Bruno Loureiro, Florent Krzakala, Lenka Zdeborová, *Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime*, arXiv: 2105.15004 [stat.ML]\n\n[5] Song Mei, Theodor Misiakiewicz, Andrea Montanari, *Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration*, arXiv:2101.10588 [stat.ML]", "summary_of_the_paper": "This paper considers the problem of fitting a target function corrupted by additive iid Gaussian noise using with a zero mean Gaussian Process (GP).\n\n It provides an asymptotic characterisation of the typical Bayesian and mean-squared generalisation errors under the assumption of power-law decay of the covariance eigenvalues and the target function coefficients when expressed in the covariance eigenbasis.\n \n The main result is to derive the exponents characterising the rate of decay of the aforementioned errors with the number of samples $n$, as a function of the spectrum and target function decays. The key technical step is to prove the concentration of $\\Phi_{R}^{\\top}\\Phi_{R}\\in\\mathbb{R}^{R\\times R}$ around $n I$ where $\\Phi_{R}\\in\\mathbb{R}^{n\\times R}$ the truncated matrix of eigenvectors evaluated at the data points, and $R=n^{\\frac{2}{1+\\alpha}-\\kappa}$ with $0\\leq \\kappa < \\frac{\\alpha-1}{\\alpha(\\alpha+1)}$.\n\nFinally, the authors provide one numerical experiment with the arc-cosine kernel and data uniformly distributed in the unit circle.", "summary_of_the_review": "The results in this work are interesting, but in my opinion the discussion is largely misplaced with respect to existing literature. In particular the abstract and introduction. I am willing to raise my score in case the authors address these issues in a revision. \n\n------------------------------------------------------------------------\n**Update after the discussion period**\n\nDuring the discussion period the authors have addressed all my questions and have welcomed my suggestions. In particular, they have extended their GP treatment to include the \"strongly regularised\" regime, finding results which are consistent with the literature. Although the rates derived in this work are known, this work derives them under a different framework, and broadens the scope under which they can be rigorously established.\n\nFor these reasons, I am updating my score towards an accept.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IyWgKZaM_Hk", "reviewer": "Reviewer_LR4t", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall the writing is clear. I found it helpful that the authors gave proof sketches and summary of the main steps detailed in the rather long appendix. The results improved upon those in the literature by being more widely applicable and with less stringent assumptions. Moreover, several rates derived by past authors are special cases of the general rates derived in this paper.\n\nHere are some questions /comments:\n1. The error variance $\\sigma^2$ is assumed to be known which is rarely the case in practice. Also, the ReLU network mentioned in the paper is noiseless, i.e., there is no $\\epsilon_i$. So how do the results presented in this paper reconcile with real-world practice?\n\n2. Are the rates the best possible under power-law decay of the target and prior kernel? Is it possible to get better rates by using different kernel functions or eigenfunctions?\n\n3. It can be seen that $\\alpha$ encodes the prior smoothness, and it is related to the order of the kernel family used. In the experiments, the authors used the first-order arc-cosine kernel to yield $\\alpha=4$. What is the rationale of choosing first-order and not higher orders? \n\n4. The interplay between $\\beta$ and $\\alpha$ is summarized in the second paragraph of the conclusion. However, how do we apply this conclusion in practice since we often do not know $\\beta$? \n\n5. How did you compute the blue lines in Figure 1? In particular, where did $2.0795$ and $0.7875$ come from in $2.0795n^{-0.7875}$ for the excess mean square error of $f_1$?\n\n############################################################################################################\n\nTYPOS:\n1. The line after (2), $K_{x\\mathbf{X}}$ should be $(k(x,x_1),\\dotsc,k(x,x_n))$ a row vector. Also to be clear, you need to assume that the kernel is symmetric in order for $K_{x\\mathbf{X}}=K_{\\mathbf{X}x}^T$ to be true.\n2. In (3), I think $q(x,y)$ should be $q(y|x)$\n3. The display after (17),  $\\|(\\mathbf{I}+\\mathbf{\\Phi\\Lambda\\Phi}^T/\\sigma^2)^{-1}\\|_2$\n4. In (20), $F_0(D_n)$ should be $F^0(D_n)=T_1(D_n)+T_2(D_n)$ and not $\\mathbb{E}_{\\mathbf{\\epsilon}}F^0(D_n)=T_1(D_n)+T_2(D_n)$ as defined in the line after (13).\n5. In the Proof sketch of Theorem 9 the first step, I think you need to take expectations with respect to the errors in $G_{1,R}(D_n)$ and $G_{2,R}(D_n)$. See also the proofs.\n6. In the Proof sketch of Theorem 9 the second step, what is $\\delta$?", "summary_of_the_paper": "Working under the nonparametric regression model, the authors established asymptotic rates for the Bayesian generalization error, normalized stochastic complexity and excess mean square error. The authors adopted the Bayesian approach by endowing the unknown regression function with a Gaussian process prior, and the covariance function is parameterized by a kernel function. By diagonalizing this kernel, the authors used the resulting eigenfunctions to represent the target function. They assumed that the kernel eigenvalues and the target basis coefficients decay according to the power-law, i.e., polynomial decay. Lastly, a simulation experiment was performed to verify the claims.", "summary_of_the_review": "I feel that some parts of the paper need more explanation and exposition. For example, discussion about the rates' optimality and modeling choices such as knowing $\\sigma$ would significantly improve this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The title of the paper nicely summarizes the main goal of the paper and the abstract does the same for the achieved results. For this reason I abstain from providing another summary. 

The initial reviews were somewhat mixed but during the discussion phase, a lot of questions have been resolved so that actually three reviewers updated (upgraded) their score. Remark 14 certainly needs to be updated according to the discussion in the final few days of the rebuttal phase. In addition, one reviewer pointed to a naive application of Mercer's theorem. This should be addressed as well, either by restricting to compact domains and continuous kernels as suggested by the reviewer, or by considering generalizations as done by e.g. the cited Fischer and Steinwart. Finally, the cited survey by Kanagawa et al also contains some information on learning curves and thus it should be cited more prominently, e.g. around Remark 14.

In any case, this paper is above the acceptance threshold.
Decision: Accept (Poster)