On the Asymptotic Learning Curves of Kernel Ridge Regression under Power-law Decay
Authors: Yicheng Li
Haobo Zhang
Qian Lin
Venue: NeurIPS 2023 poster (2023)
Keywords: generalization
reproducing kernel Hilbert space
bias-variance trade-off

Abstract: The widely observed 'benign overfitting phenomenon' in the neural network literature raises the challenge to the `bias-variance trade-off' doctrine in the statistical learning theory.
Since the generalization ability of the 'lazy trained' over-parametrized neural network can be well approximated by that of the neural tangent kernel regression,
the curve of the excess risk (namely, the learning curve) of kernel ridge regression attracts increasing attention recently.
However, most recent arguments on the learning curve are heuristic and are based on the 'Gaussian design' assumption.
In this paper, under mild and more realistic assumptions, we rigorously provide a full characterization of the learning curve in the asymptotic sense
under a power-law decay condition of the eigenvalues of the kernel and also the target function.
The learning curve elaborates the effect and the interplay of the choice of the regularization parameter, the source condition and the noise.
In particular, our results suggest that the 'benign overfitting phenomenon' exists in over-parametrized neural networks only when the noise level is small.

On the Asymptotic Learning Curves of Kernel Ridge Regression under Power-law Decay
Yicheng Li, Haobo Zhang
Center for Statistical Science, Department of Industrial Engineering Tsinghua University, Beijing, China fliyc22, zhang- hb21 J@mai ls. tsinghua.edu.co cn
Qian Lin
Center for Statistical Science, Department of Industrial Engineering Tsinghua University, Beijing, China qianlin@ts inghua. edu.h.aaedddccc.. edu.cn
Abstract
The widely observed 'benign overfitting phenomenon' in the neural network lit- erature raises the challenge to the biissvvriance trade-off' doctrine in the statis- tical learning theory. Since the generalization ability of the 'lazy trained' over- parametrized neural network can be well approximated by that of the neural tangent kernel regression, the curve of the excess risk (namely, the learning curve) of ker- nel ridge regression attracts increasing attention recently. However, most recent arguments on the learning curve are heuristic and are based on the 'Gaussian realistic assumptions, we
design' assumption. In this paper, under mild and rigorously provide a full characterization of the learning curve the asymptotic sense under power-law decay condition of the eigenvalues of the kernel and also the target function. The learning curve elaborates the effect and the interplay of the choice of the regularization parameter, the source condition and the noise. In particular, our results suggest that the 'benign overfitting phenomenon' exists in over-parametrized neural networks only when the noise level is small.
Introduction
Kernel methods, particular kernel ridge regression (KRR), have been one of the most popular algorithms in machine learning. Its optimality under various settings has been an active topic since Caponnetto and De Vito [2007). Andreas Christmann [2008]. The renaissance of kernel methods arising from the neural tangent kernel (NTK) theory [Jacot al. 2018). which shows that over-parametrized neural networks can be well approximated by certain kernel regression with the corresponding NTK. has posed further challenges about the interplay generalization, regularization and noise level. For example, it has been observed empirically that werr-paaametrized neural networks can fit any data perfectly but also generalize well [Zhang al.) 2017), which contradicts to our traditional belief of bias-variance trade-off [aannik] 1999].
The aforementioned 'benign overfitting phenomenon' that overfitted neural networks generalize well attracts lots of attention recently. Researchers provide various explanations to reconcile the contradiction between it and the bias-variance trade-off principle. For example, [Belkin et al.) [2019] proposed the 'double descent theory' to explain why large model can generalize well; some other works (e.g.. Liang and Rakhlin 2020)) argued that kernel interpolating estimators can generalize
"Qian Lin also affiliates with Beijing Academy of Artificial Intelligence, Beijing, China
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

well in high dimensional settings. In contrast to the "benign overfitting phenomenon' several other works (e.g., Rakhlin and Zhai 2018 Li al. 2023a] recently showed that keree interpolation can not generalize in traditional fixed dimension setting. In order to understand the 'benign overfitting phenomenon', it would be of great interest to characterize the learning curve: the curve of the exact order of the generalization error of certain algorithm (e.g., KRR) varying with respect to different
choices of regularization parameters.
Recently several works (e.g., Bordelon et al. 2020 Cui et al. (021]] depicted the learning curve
of KRR under the Gaussian design assumption that the eigenfunctions (see (5)) are i.idd. Gaussian random functions. Though it is easy to figure out that the Gaussian design assumption can not be
true in most scenarios, with some heuristic arguments. Cui et al. [2021] provide description of the learning curves of KRR with respect to the regularization, source condition and noise levels. These works offered us some insights on the learning curve of KRR which strongly suggests that the learning curve should be U-shaped if the observations are noisy or monotone decreasing if the observations are noiseless.
In this paper, we consider the learning curves of KRR under the usual settings (without the Gaussian design assumption). Under mild assumptions, we rigorously prove the asymptotic rates of the excess risk, including both upper and lower bounds. These rates show the interplay of the eigenvalue decay of the kernel, the relative smoothness of the regression function, the noise and the choice of the regularization parameter. As result, we obtain the traditional U-shaped learning curve for the noisy observation case and a monotone decreasing learning curve for the noiseless case, providing full picture of the generalization of KRR in the asymptotic sense. Combined with the NTK theory, our results may also suggest that 'the benign overfitting phenomenon' may not exist one trains a very wide neural network.
1.1 Our contributions
The main contribution of this paper is that we remove the unrealistic Gaussian design assumption in previous non-rigorous works [Bordelon et al. 2020 Cui et al.) 2021] and provide mathematically solid proof of the exact asymptotic rates of KRR with matching upper and lower bounds.
To be precise, let us introduce the quantities X, the regularization parameter in ( 3, the eigenvalue decay rate in (6). which characterizes the span of the underlying reproducing kernel Hilbert space (RKHS); and s, the smoothness index in [12). describes the relative smoothness of the regression function with respect to the RKHS. Here note that larger 3 implies better regularity the RKHS and also larger s also implies better relative smoothness. Then, the asymptotic rates of the generalization error (excess risk) R((A) in the noisy case is roughly
[0()min(s2)) + +02x-1/8/m)
if A Q( if A= On +);
R(A)
(9))2)
where n is the number of the samples and の² the noise level. This result justifies the traditional U-shaped learning curve (see also Figure I on pagelo) with respect to the regularization parameter. For the technical part, both terms. Since the variance term was already considered in Li et al. [2023a], the main focus of this work is the bias term. Our technical contributions include:
the
decomposition and determine the exact rates of the
When the regularization parameter À is not so small, that is, À = 22n -9), we provide sharp estimates of the asymptotic orders (Lemma 4b of the bias term with both upper and lower bounds. Our result holds for both the well-specified case (s 2 1) and the mis-specified case
(s (0, 1)), which improves the upper bounds given in Zhhan et al. 2023a].
We further show an upper bound (Lemma A.12) of the bias term in the nearly interpolating case, i.e., x~ O(n -9). The upper bound is tight and matches the coormation-theorede lower bound provided in Proposition 4.4
Combining these results, we provide learning curves of KRR for both the noisy case (Theorem (.2) and the noiseless case (Theorem 3.4. The results justify our traditional belief of the bias-variance trade-off principle.
Our new techniques can also be generalized to other settings and might be of independent interest.

---

1.2
Related works
The optimality of kernel ridge regression has been studied extensively Caponnetto and De Vito 2007 Steinwart al. 2009, Fischer and Steinwart 2020 Zhang et al. 2023a]. Caponnetto and De Vito [2007] provided the classical optimality result of KRR in the well-specified case and the subsequent works further considered the mis-specified case. However, these works only provided an upper bound and the worst-case (minimax) lower bound, which are not sufficient for determining the precise learning curve. In order to answer the "benign overfitting" phenomenon [Bartlett et al., 20200 Liang and Rakhlin 2020 , several works [Rakhlin and Zhai 2018 [Bcchhllz] [202 Beaglehole et al., 2022] tried to provide a lower bound for the kernel interpolation, which is limiting case of KRR, but these works only focused on particular kernels and their techniques can hardly be generalized to provide a lower bound for KRR.
Another line of recent works considered the generalization performance of KRR under the Gaussian design assumption of the cigenfunctions [Bordelon et al. 2020 Jacot et al. 2020 Cui et al. 2021 Mallinar et al., 2022] In particular, the learning curves of KRR was described in Bordelon et al. 2020], Cui et al. 202T]. but heuristic arguments are also made in addition to the unrealistic Gaussian design assumption. Though the heuristic arguments are inspirational, rigorous proof is indispensable one plans to perform further investigations. this work, we provide the first rigorous proof for most scenarios of the smoothness s, eigenvalue decay rate 3, noise level o² and the regularization parameter À based on the most common/realistic assumptions.
Recently, in order to show the so-called "saturation effect" in KRR. Li et al. [023b) proved the exact asymptotic order of both the bias and the variance term when the regression function very smooth and the regularization parameter À is relatively large. Inspired by their analysis, [i et al.) [2023a] showed the exact orders of the variance term. Our work further determines the orders of the bias term, completing the full learning curve KRR.
KRR is also connected with Gaussian process regression (Kanagawa et al. 2018 Jin et al. [202]] claimed to establish the learning curves for Gaussian process regression and thus for KRR. However, as pointed out in Zhang al.] [2023b]. there is gap in their argument. Moreover, their results are also more restrictive than ours, see Section 3.3 for comparison.
Notations We write IP(X' du) for the Lebesgue space and sometimes abbreviate it as LP. We use asymptotic notations O(-), o(.), 22-)) and 0(-). and use Ô(-) to suppress logarithm terms. We also write On x bn for an (bb)). We will also use the probability versions of the asymptotic notations such as Or(-). Moreover, present the results more clearly, we denote a, Opoly (b,,) an Onnbb,) for any p > an Qooly (bw) if an (2(n~bb)) for any p > a, Opoly (b.) a, Opoly (bn), and a,, = Qpoly (b,.); and add subscript p for their probability versions.
2 Preliminaries
Let X Rd be compact and p be probability measure on X I, whose marginal distribution on X' is denoted by Suppose that we are given n i.i.d. samples (I1, 91),,.,................... .................. (In, yn) from p. Let k be a continuous positive definite kernel k over X' and H be the separable reproducing kernel Hilbert space (RKHS) associated with k. Then, kernel ridge regression (KRR) obtains the regressor fx via the following convex optimization problem
1
n M (14
fx arg min fEH
f(x:))
AII
(1)
where À >>00 is the regularization parameter. Let us denote X = ...,..... un) and y (y)..... ....... Un) ). closed form of (T) can provided by the representer theorem Andreas Christmann 2008
fx(=) K(x, X) (XX, nd)
(2)
where K) (K(I, k(I, and K(X, X)) 25)
3

---

In terms of the generalization performance of fx. we consider the excess risk with respect to the squared loss
Ezzp f())) - TAA-Fallaaa Falxaxa
where (x) = Byly æ] is the conditional expectation and is also referred to as the regression function. We aim to provide asymptotic orders of with respect to
2.1 The integral operator
We will introduce the integral operator, which is crucial for the analysis, as the previous works [Capon netto and De Vito. 2007 Lin et al. 2018). Denote by the marginal probability measure of on X. Since continuous and X compact, let us assume supzex k(z,z) S x²² Then, it is known [Andreas Christmann 2008 Steinwart and Scovel [2022] that we have the natural embedding Sp + T.2, which a fillber-SShhidtt operator with Hilbert-Schmin norm |Sp ll S k. Let
S I > H the adjoint operator of S,, and T S L L Then, it easy to show that T' is an integral operator given by
(T)))== - M(,, (Z,
and it is self self-adjoint. positive and clacscllas (thus compact) with trace norm [|]| S n² [Caponnetto and De Vitol [007]] (Steiwwart and Scovel [0012]. Moreover, the spectral theorem of compact self- adjoint operators and Mercer's s theorem [Steinwart and Scovel, 2012] yield the decompositions
T
Σ Na (x KEN
k(x,y) = Σ (sex(z)es()),
IEN
where N C N is index set, {No is the set of positive eigenvalues of T' in descending order, and is the corresponding eigenfunction. Furthermore, {eiheN forms orthonormal basis of Ran S C 2 and {>!²
ei)
forms orthonormal basis of Ran Sp C H.
iEN
The eigenvalues A; actually characterize the span of the RKHS and the interplay between 7. and μ.. Since we are interested in the dimnnie-dimesiionll case, we will assume following polynomial eigenvalue decay in the literature [Caponnetto and De Vitol 2007 Fischer and Steinwart 2020 Li al. 2023b), which also referred as the capacity condition or effective dimension condition. Larger 3 implies better regularity of the functions in the RKHS.
and assume the
Assumption (Figenvalue decay). There some
B > 1 and constants Cg2 Cp > such that
cai < x S Cgi (i = 1.2......
(6)
where A₃ is the cigenvalue of T defined in 5
Such polynomial decay is satisfied for the well-known Sobolev kernel Fischer and Steinwart 2020), Laplace kernel and, of most interest, neural tangent kernels for fully-connected multilayer neural networks [Bietti and Mairal 2019 Bietti and Bach 2020 Lai et al. 2023
2.2 The embedding index of an RKHS
We will consider the embedding index of an RKHS to sharpen our analysis. Let us first define the fractional power T 1,2 + 1,2 for 8 2 0 by
(f)
Σ X (f.e)
Then, the interpolation space (Steinwart and Scovel 2012, 2023b] [H] is define by
Fischer and Steinwart 2020 Li al.
a;20/2 e; Σ af < 00 ) C
| = Ran /
Σ VEN
)
(8)
iEN

---

with the norm EiEN and?
[2)- (EiEN a?) d?) 1/2 One may easily verify that [H]] is also
separable Hilbert space with orthonormal basis (x/22c;
e: JEE Moreover, it is clear that [7]]
Ran S C LL and [H]' Ran S C H. It can also be shown that if $1 > 2 0, the inclusions
[+] + [Ad]*2 are compact (Steinwart and Scovel 2012].
Now, say H. has an embedding property of order (0, 1] [H] can be continuously embedded into - (x,, du), that is, the operator norm
|| Lx, Ma < co.
Moreover, Fischer and Steinwart 2020 Theorem 9] shows that
|| + I _ (X, 11]
|
ess sup Σ (2))(1)) ZER, EEN
(10)
Therefore, since s k(x, x) S K² we know that 99) always holds for a 1. By the inclusion relation of interpolation spaces, it clear that if H has the embedding property of order a, then has the embedding properties of order a' for any a' 2 Consequently, we may introduce the following definition (Zhang et al. 2023b]:
Definition 2.1. The embedding index ag of an RKHS is defined by
ag inf {a [[ + L Td (X, p)ll
Ma 00}.
(11)
It is shown in Fischer and Steinwart 2020 Lemma 10] that cr B and assume the equality holds as the following assumption.
Assumption 2 (Embedding index). The embedding index ag = 1/3, where 3 is the eigenvalue decay in (6)
Lots of the usual RKHSs satisfy this embedding index condition. It is shown in Steinwart et al. (2009 that Assumption 2 holds if the eigenfunctions are uniformly bounded, namely suptew ||e: 1 oo.
Moreover, Assumption 2 also holds for the Sobolev RKHSs, RKHSs associated with periodic translation invariant kernels and RKHSs associated with dot-product kernels spheres, see /Zhang
ct al. 2203aa Section 4].
3 Main Results
Before presenting our main results, we have to introduce a source condition on the regression function. Since we will establish both precise learning rates, have characterize the exact smoothness order of f rather than merely assume fø belongs to some interpolation space [H]].
Assumption 3 (Source condition). There some 0 and sequence (a:)121 such that
Σ 2,2 1/2
(12)
and < <c |a,1 S for some constants c, C.
Remark 3.1. Assumption 3 is also considered in Cui al. 2021 Eq. (8)] and slightly weaker
version of it is given in Jn et al. [202 Assumption 5]. We only consider this simple form since there no essential difference in the proof to consider the weaker version. From the definition (8) we can
see that Assumption implies fo [H]] for any < s but fü & [H]
3.1
Noisy case
Let us first consider the noisy case with the following assumption: Assumption (Noise). We assume
E(e,y) -v- (x)))
x] x
o² > w.e.IEER
(13)
5

---

Gld')
erron rate
Bias
Noiseless case
Effectively noisy
Effectively
Interpolating, Q(1)
Interpolating, Q(1)
O(n
6Gp - B
Overfitting e W9))
Overfitting @(n -0 )
Optimal
Underfitting B(n Bin-
(t+11P 6up 3Fr
Underfitting @(n-*)
6.p
16+
Underfitting Ø(n #*)
Saturation 22)
Optimo
toomatani nobb))
Figure 1: An illustration of the learning curves when choosing À n First row: The birs-variance
plot and the error curves for the noisy and noiseless cases. Second row: Tow phase diagrams of the asymptotic rates of the excess risk with respect to parameter pairs (0, s) and (0, r). where we min(s, 2). In the "underfitting" ("overfitting) region, bias (variance) is
set o² n and dominating. The "interpolating" region refers to the extreme cases of overfitting that the excess risk lower bounded by a constant. For the first diagram we consider the case of constant noise. For second diagram, the red vertical line shows the crossover of the noisy regime the noiseless regime and an upper bound for the blank area on the upper-right corner is unknown yet.
For technical reason, we have further assume the kernel to be Hölder-comtinuous. which is first in introduced in Li et al. [2023b). This assumption is satisfied for the Laplace kernel, Sobolev kernels and neural tangent kernels.
Assumption 5. The kernel l is Hölder-continuous, that is, there exists some E (0, 1] and I, > 0 such that
1k(21, x2) k(y1 v221 < L|[(21, 222) (y1, 92) 1 Ve,, 22, V1. 32 X.
(14)
Theorem 3.2. Under Assumptions
suppose X = n for 0 > 0. Then,
E A 1/
x
(Ôr(n min(s.2) + + -1--011-)131) spooly (a²),
if < B
(15)
if 2 B,
where Ög can be replaced with for the first case if + 2.
Remark 3.3. The two terms in the first case in Theorem 3.2 actually correspond to bias and the variance term respectively. Balancing the two terms, we find the optimal regularization is 8 0op プØ4 and the optimal rate is ø341 where ğ min(s, 2), which recovers the classical optimal rate results [Caponnetto and De Vito 2007). Moreover, while we treat o as fixed for simplicity, we
ag
can also allow o² to vary with Then, we recover the results in Cui et al. 2021

---

3.2 Noiseless case
Theorem 3.4. Under Assumptions
assume further that the noise is zero, ie., y = (x). Then,
have:
Suppose Ax Axn-t for 0 E (0, we have
| fp
E
X
(16)
where Op can be replaced with Dp if * 2.
Suppose X A= x=n for 0 2 B and assume further that > Then,
E -| rol x -p
Opoly (n
min(
(17)
Moreover, we have the information- theoretical lower rate:
sup po
E
[|
f
X (0(n=
(18)
SR
where R > is a fixed constant.
Remark 3.5. Theorem 3.4 shows that the generalization error of KRR in the noiseless case is monotone decreasing when increases and reaches the optimal rate - when 3 if S 2. Since the case + do corresponds kernel interpolation, optimal when there no noise. In contrast, as shown in Theorem 3.2 (or Li et al. (2023a) )) kernel interpolation can not generalize in the noisy case. For the saturation and the resulting convergence rate limited to n -2 while the possible lower rate is n s/
result implies that kernel interpolation is
2, the KRR method suffers from
3.3 Discussion
Our results provide full picture of the generalization of KRR, which is in accordance with traditional belief of the bias-variance trade-off principle: the generalization error a U-shaped curve with respect to the regularization parameter À in the noisy case and is monotone decreasing in the noiseless case. See Figure on page for an illustration.
Our rates coincide with the upper rates in the traditional KRR literature CCaponnetto and De Vito 2007 Fischer and Steinwart) 2020). Moreover, our results also recover learning curves Cui al.
2021], but do not need the strong assumption of Gaussian design cigenfunctions in Cui ct al. 2021 which may not be true in most cases. Our assumptions are mild and hold for a large class of kernels including the Sobolev kernels and the neural tangent kernels (NTK) spheres.
Our results are based on the bias- variance decomposition and determining the rates for each term respectively. In the proof oi et al. 2023b), they determined the rates of the variance term under the condition that f < 2 and that of the bias term when 2 2 and f < The subsequent work Li et al. 2023a proved the rates of the variance term when 0 < 3 and provided near constant lower bound for 0 2 B. Considering the counterpart, our works further prove the rates of the bias term, which finally enables to determine the complete learning curve of KRR.
The connection between KRR and Gaussian process regression also results in the connection between their learning curves. Jin et al. [2021] claimed to show learning curves for Gaussian process regression. However, regardless the gap their proof as pointed out in Zhang al. [023b). their results are more restrictive than ours. Considering a boundedness assumption of the eigenfunctions that ||e:ll < Ct for some 2 O. they could only cover the regime of B1 + 2T). Moreover, to approach the = 3 regime for the Q(1) bound in the noisy case or the optimal rate in noiseless case, they have to require T 0, that is, the eigenfunctions are uniformly bounded, but it is not true for some kernels such as dot-product kernels on spheres (and thus for NTK) since in general spherical harmonics are not uniformly bounded. In contrast, our embedding index assumption still holds in this

---

Proof sketch
We first introduce the following sample versions of the auxiliary integral operators. which commonly used in the related literature [Caponnetto and De Vito 2007 Fischer and Steinwarl, (2020]
et al. 2023b]. We define the sampling operator Kr R - H by KzY yk(a, -), whose adjoint
K 7 + IR is given by K2 = fz)). The sample covariance operator Tx H - 7 is defined by
Tx
Kr K
(19)
n1
and the sample basis function is 92 == 2007], the operator form of KRR writes
1 Σ Kw:li E H. As shown in Caponnetto and De Vito
n2
fx = (Tx + gz.
(20)
Let us further define
Íz == (gz
K f (x,)) EH,
(21)
and
A = E (fxx) = (Tx + A) - Íz E H.
(22)
Then, the traditional bias-variance decomposition Li et al. 2023b Zhang et al.
2023a yields
E (I
X
Bias (A) Var(A),
(23)
12
where
Bias² (A) = || ---llaa
sall?
a²
m (Tx + x)
Var(A)
(24)
n
4.1 The noisy case
To prove the desired result, we have establish the asymptotic orders of both Bias? and Var(A). We first prove the asymptotic order of Bias? as one of our technical contributions. As far know, we are the first to provide such a lower bound in (25).
Lemma 4.1. Under Assumptions
12
suppose x n for E 3). Then,
Bias² (A) 6r min().2)8)
(25)
where Öo can be replaced with Op ifs $ 2.
Denote min(s, 2). We first introduce the regularized regression function fx = T(T + fp and triangle inequality implies
Proof sketch of Lemma
Bias(A) = || -1 > | 5 - S
There is no randomness in the first term and we can use the expansion 12 and 5 to show that ||/a - foll = é (n= Then, we have to prove the error term i
ʃA to infinitesimal L2
with respect the main term, which is the main difficulty since requires refined analysis. Previous work only consider the case 0 8
(corresponding to the optimal regularization) and show an On bound rather than the o(n 50 bound that we require. For the proof, we (1) apply the concentration techniques in Fischer and Steinwart [000]]: (2) consider the L.H-embedding property in Zhang et al. [2023a] for the mis-specified case when is small; (3) sharpen the estimation by exploiting the embedding property dg = 1/3 and 0 < B. For the detail, see Section 2.2 in the supplementary material.
D

---

The variance term has been analyzed in Li et al. [023a]. We present the following proposition as combination of Proposition 5.3 and Theorem 5. in Li et al. 2023a Proposition 4.2. Under Assumptions
5 suppose that x n Then, @poly (0==-(1-0/3)))
if 0 3 if
Var(A)
(26)
Spoly (o²),
8 2 3.
4.2 The noiseless case
For the noiseless case, the variance term vanishes in 23 and thus we only need to consider the bias term. Since we have already established the estimation for large À in Lemma 4.1 we focus on the case of small À.
Lemma 4.3. Under Assumptions
assume further s > 1. Suppose À x n for 0 2 B. Then, Bias² (A) Op (n minn(,2))))
3
(27)
Proof sketch of Lemma A.12 Intuitively, we hope bound Bias (A) with Bias for X >>> such that concentration still works. However, we can not directly derive no monotone property of Bias (A). Nevertheless, since fp H when 1, the bias term can be written
Bias (A) ||xTxx + 1) ما = T + AJ
'501ixx -
S T + +1)
((H)) 1 11
Then, by operator calculus we can show that
- [A(Tx + "1 $ | [xTXX + + (8(H)
((10)
reducing to Å. Now, we can replace Tx with T using concentration results and derive the desired upper bound.
The following proposition shows that the upper bound in Lemma A.12 12 matches the information- theoretical lower bound. The proof follows idea of the minimax principle [Micchlli and Wahba 1979] and is deferred to the supplementary material.
Proposition 4.4. Suppose Assumption holds and 2 1. For any X = In), we have
sup
Bias (A)
(28)
||
( ER
where we note that here (ias(A) is viewed as function depending also on fü and X.
Experiments
Lots of numerical experiments both synthetic data and real data are done to study to learning curves of KRR (Li et al.] 20236 Cui et al. [202I]. In this section, we consider numerical experiments on toy model to verify theory.
Let us consider the kernel k(x,y) v) min(a,y) y) and x U(00 1]. Then, the corresponding RKHS is Wainwright 2019]
H f [0 +R R f is absolutely continuous, f()) - 0, (' ((()) < <o0
and the eigenvalue decay rate B = 2. Moreover, the eigensystem of k is known to be X; = (2 πT) and ex(x) sin 2i-1 which allows functions. For some fr, generate data from the model y f*(x) + where No 0.05) and perform KRR with À cn for different 0's with some fixed constant c. Then, we numerically compute the variance, bias and excess risk by Simpson's 's formula with N >> n nodes. Repeating the experiment for ranged in 1000 to 5000, we can estimate the convergence rate by logarithmic least-squares log err = r log n + b on the values (variance, bias and excess risk). The results are collected in T on page 10 It can be seen that the resulting values basically match the theoretical values and we conclude that our theory is supported by the experiments. For more experiments and more details, we refer to the supplementary material.
directly compute the smoothness of certain

---

[()
cos 2
sin 2Tx
1.5)
sin 2 oc)
0
Variance
Bias
Risk
Bias
Risk
Bias
Risk
0.2
0.90 (0.90)
0.13 (0.10)
0.13 (0.10)
0.34 (0.30)
0.34 (0.30)
0.40 (0.40)
0.42 (0.40)
0.4
0.80 (0.80)
0.22 (0.20)
0.22 (0.20)
0.68 (0.60)
0.69 (0.60)
0.82 (0.80)
0.81 (0.80)
0.5
0.75 (0.75)
0.26 (0.25)
0.26 (0.25)
0.84 (0.75)
0.79 (0.75)
1.04 (1.00)
0.77 (0.75)
1.0
0.49 (0.50)
0.54 (0.50)
0.52 (0.50)
1.69 (1,50)
0.49 (0.50)
2.21 (2.00)
0.49 (0.50)
2.0
0.00 (0.00)
1.05 (1.00) 0.09 (0.00)
3.26 (3.00)
0.00 (0.00) 3.99 (4.00)
0.00 (0.00)
3.0
0.00 (0.00)
1.05 (1.00) 0.09 (0.00) 3.26 (3.00)
0.00 (0.00) 3.98 (4.00) 0.00 (0.00)
Table 1: Asymptotic rates of bias, variance and excess risk under three regressions and different
choices 0. The numbers in parenthess are the theoretical values. The bolded cells correspond to
the best rate over the choices of ('s.
6 Conclusion
In this paper, we prove rigorously the learning curves of KRR, showing the interplay of the eigenvalue decay of the kernel, the relative smoothness of the regression function, the noise and the choice of the regularization parameter. The results justify our traditional bias-variance trade-off principle and provide a full picture of the generalization performance of KRR. These results will help us better understand the generalization mystery of neural networks.
As for future works, we notice that for the nearly interpolating regime when 0 2 3, there are still some missing parts due technical limitations. We expect that further analysis will prove the exact orders of the variance term like that given in Mallinar et al. [2022] under the Gaussian design assumption. We also hypothesize that Lemma A.12 still holds in the mis-specified case < 1).
Acknowledgments and Disclosure of Funding
This work is supported in part by the Beijing Natural Science Foundation (Grant Z190001) and National Natural Science Foundation of China (Grant 11971257).
References
Ingo Steinwart (auth.) Andreas Christmann. Support Vector Machines. Information Science and Statistics. Springer- New York, New York, NY, 1 edition, 2008. ISBN 0-387-77242-1 0-387-77241-3 978-0-387-77241-77
978-0-387-77242-4, doi: 10.1007/978.003387-7744----4
Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117448)33003333077 December 2020. ISSN 0027-8424, 1091-6490. doi: 10.1073/pnas. waappnass...9..... 1907378117.
Daniel Beaglehole, Mikhail Belkin, and Parthe Pandit. Kernel ridgeless regression is inconsistent in low dimensions. (arXiv:2205..1 (.XXV:22005115255 June 2022. doi: 10.448550/axXx.22055.333
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical vari-nee trade-off. Proceedings of the National Academy of Sciences, 118632):15849-1585 2019.
Alberto Bietti and Francis Bach. Deep equals shallow for ReLU networks in kernel regimes. arXiv preprint htt::2009.143997 2020.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. In Advances in Neural Information Processing Systems, volume 32, 2019.
Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In Proceedings of the 37th International Conference Machine Learning, pages 1034. PMLR, November 2020.
10

---

Simon Buchholz. Kernel interpolation in Sobolev spaces is not consistent in low dimensions. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 3410-3440. PMIR, July 2022.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares al- gorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007. doi: 10.1007/ (10208-00601990
Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization entor rates in kernel regression: The crossover from the noiseless to noisy regime. Advances in Neural Information Processing Systems, 34:10111-10143 2021.
Simon-Raphaee Fischer and Ingo Steinwart. Sobolev norm learning rates regularized least-squares algorithms. Journal Machine Learning Research, 21:205:1-205:38. 2020.
Junichi Fujii, Masatoshi Fujii, Takayuki Furuta, and Ritsuo Nakamoto. Norm inequalities equivalent to Heinz inequality. Proceedings of the American Mathematical Society, 118(3):827-883) 1993.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Arthur Jacot, Berfin Şimşek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Kernel alignment risk estimator: Risk prediction from training data. June 2020. doi: 10.48550/arXiv.22006 09796.
Hui Jin, Pradeep Kr Banerjee, and Guido Montúfar. Learning curves for Gaussian process regression with power-law priors and targets. 10.Xi:22100122331 November 2021.
Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath K. Sriperumbudur. Gaus- sian processes and kernel methods: A review on connections and equivalences. arXiv preprint arXiv.1807.02582. 2018
Jianfa Lai, Manyun Xu, Rui Chen, and Qian Lin. Generalization ability of wide neural networks on R. (arXiv:2302.05933) February 2023. doi: 10.485500a2xxv.2200.5533
Yicheng Li, Haobo Zhang, and Qian Lin. Kernel interpolation generalizes poorly. (arXiv:200.115809)
March 2023a. doi: 20.48550/axxx..233315588
Yicheng Li, Haobo Zhang, and Qian Lin. On the saturation effect of kernel ridge regression. In International Conference on Learning Representations, February 2023b.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. The Annals of Statistics, 48(3), June 2020. ISSN 0090-5364. doi: 10.
Junhong Lin, Alessandro Rudi, L. Rosasco, and V. Cevher. Optimal rates for spectral algorithms with least-squares regression over Hilbert spaces. Applied and Computational Harmonic Analysis, 48: 868- 890, 2018. doi: 10. 10.1006/j.acha.200 2018.09.009
Shao-Bo Lin, Xiangyu Chang. and Xingping Sun. Kernel interpolation high dimensional scattered data. (arXiv:2009.0155 514514), September 2021.
Neil Mallinar, James B. Simon, Amirhesam Abedsoltan, Parthe Pandit, Mikhail Belkin, and Preetum Nakkiran. Benign, tempered, or catastrophic: A taxonomy of overfitting, (arXiv:2207.06566) July 2022. doi: 010555500a2ii.220000555555
Charles A. Micchelli and Grace Wahba. Design problems for optimal surface interpolation. Technical report, Wisconsin Univ-Madison Dept of Statistics, 1979.
Alexander Rakhlin and Xiyu Zhai. Consistency of interpolation with Laplace kernels a high- dimensional phenomenon. (11) December 2018.

---

Barry Simon. Operator Theory. American Mathematical Society, Providence, Rhode Island, November 2015. ISBN 778-1-4704-1103-9 978-1-479--2222220 1-4704-2766-4,
doi: 10.1090/simon/004.
Ingo Steinwart and C. Scovel. Mercer's theorem on general domains: On the interaction between measures, kernels, and RKHSs. Constructive Approximation, 35(3):363-417, 2012. doi: 10.1007/ 001365-012-913--2
Ingo Steinwart, D. Hush, and C. Scovel. Optimal rates for regularized least squares regression. In COLT, pages 79-93, 2009.
Vladimir Vapnik. The Nature of Statistical Learning Theory. Springer science & business media, 1999.
Martin J. Wainwright. High- High-Dimensional Statistics: A Asm-ssymii Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi:
10.1017/9781 108627771.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. (utXiv:611.003300, February 2017.
Haobo Zhang, Yicheng Li, and Qian Lin. On the optimality of misspecified spectral algorithms. (arXiv:2303. 14942), March 2023a. doi: 2
Haobo Zhang, Yicheng Li, Weihao Lu, and Qian Lin. On the optimality of misspecitied kernel ridge regression. In International Conference on Machine Learning, 2023b.
12

---

A Detailed proofs
The first step of the proof is the traditional birs-variance decomposition. Let us further define
-z: = (gzl
Ka,f((z)) E EH,
(29)
2=1
and
A = E (faxx) (Ix +) gz H.
(30)
Recalling 20
have
A (Tx + A) Σ
Kz,Wii Di = - (Tx + A)
Ks. (f((a)) +
1m
1 11
(Tx 2) 9z +
Σ
(Tx + 1) Kx
n
so that
f (fx f2)
(Tx + - Ka, Es.
n
Taking expectation over the noise e conditioned on since g|x are independent noise with mean and variance o², we have
E (1L.
2 f/
x
Bias (A) + Var(A),
(31)
L2
where
Bias² (A) = [ 1 ralle
Var(A) =
0² 1
n Σ (Tx + A) [k(a;; 11E
(32)
A.1
The variance term
Theorem A.1. Under Assumptions
!
suppose that X x n Then,
poly (o2n (222-(1-018)),
if 0 < 8;
Var(A)
(33)
poly (o2).
0 2 B.
The computation in Li et al. 2023b shows that
o²
/ K(x, X)(K + ----))--( 2K(X x)d(()).
Var(A)
n²
Then, Theorem A.I directly follows from Proposition 5.3 and Theorem 5.10 in Li al. [023a
A.2
The bias term
Theorem A.2. Under Assumptions 12 suppose À x n- for 0 E (0, B). Then,
Bias (A) = @p (n mmn((s2)0))
(34)
where Ö₂ can be replaced with Op if + 2.
Let us define the regularized version of the regression function
A = (T'+))
(35)
13

---

Then, the triangle inequality implies that
Bias A) = [ 5اl1,2
2 1fx fálا
- J - fx
(36)
Then, the proof of Theorem A.2 is the combination of the following Lemma A.3 (with 7 = 0) and Lemma A.4, showing that the main term
||/2 fاll Or (n min(s ,,0 and the error term
[
l 12
op (u-minns.2))/73
Lemma A.3. Under Assumptions 7 and 3
for any 0 S 7
< we have
X²7 X2 In
8- 7 2; 8- 7 = 2;
1IAx - 1allpan
(37)
- > 2.
Proof. From the definition of interpolating norms, letting p = (s - 72/ we have
X
X
2
|/ 1p [R] Σ
12
(38)
(4:
A
+
i=1
Then result then follows by applying Proposition
B.2 for the last series.
The following lemma shows the error term in 36 is infinitesimal, whose proof relies on fine-grained concentration results established in Section A.3
Lemma A.4. Under Assumptions
7
Suppose
X x n with 0 E (0, B). then
f 1 12 OF mmn((..)0/22))
(39)
Proof. We begin with
A f2
= | T (fx - -f1))
$ | $
|
|T (ăz Txafa)
(40)
71
From operator calculus we know |
< 1. Moreover, since 0 < B and the embedding index
ag 1/3. by Lemma B.5 we get
T x
< 3 with high probability as long is sufficiently
large. For the last term in (40), we have
T (āz - Txxa) = -T [īz - (Tx + (T)
= =T (0z TxJA) - -)++ fa + TM
T 1(ăz TxfN) -
Therefore, Lemma A.5 and Lemma A.10 show that
| (ăz - Txxfa) |1 H
T [(āz Txfx) - (g - (o-TTi)) (1 (n (n-min(6.200/2)
for both > 0gg and s S og cases.
A.3 Approximation results
Let us further denote
E(x) = T (Kzf(x)) - TafA).
(41)
Then, is easy to check that
T 1 (āāz Txfa) - (g T'Aa
7 Σ E(x;) Exn
The following lemma deals with the easy case when > Okp-
14

---

Lemma A.5. Suppose Assumptions hold and s Let X x n- with & E (0, 5) and
8 E (0, 1). Then,for > ag 3 being sufficennlly close. it holds with probability least 1 that
läz Tx -g ( C''n 2 T
MM2 + Ma
x In n
X8/2
(42)
8.
where 3 = min(s, 2). Consequently,
rx
[@2 - Txfx) - (g- Tfw) or (1 = or (80/2))
(43)
Before proving Lemma A.5 we have to introduce the following proposition bounding the RKHS
norm of the regularized basis function, which is part of et al. 2023a Corollary 5.6]. Proposition A.6.
Suppose H. has embedding index cgg. Then for any a > ao.
T 1/2 k(x, >> S MaA-a//2 pla.e. x E.
(44)
Proof of Lemma A.5 E(x):
To Bernstein inequality in Lemma B.4 let us bound the m-th moment of
E []
12 T K2 (z) (x(x))
H (((
m k( :)
x)]
(45)
#
The first term in (45) is bounded through 44). embedding condition and Lemma A.3 we have
For the second term, since 8 op, using the
fA fill S Ma fA
füll follpa I C'M.A 1min s CM,A
where we notice that min(s a, 2) = min(s, 2 + a) a 2 3- for the last inequality. Moreover, Lemma A.3 also implies
- f))))
[|{(2)) - (x) cCA x s CC CXLInn.
Inn.
Plugging in these estimations in (45) we get
45
S (M,X-a/2) /m)mm 11ʃ2 - 1/ 10 [1) (
S (M.X -2/mm (CMa (CX$1mm)
m-2
5 (CM2)==*In))
(46)
The proof is then complete by Lemma
B.4
The case of og is more difficult. We will use the truncation technique introduced in Zhang et al. [203a]] The following lemma can be proven similarly to Lemma A.3 Lemma A.7. Under Assumptions
7 and 3
for any 0 S y + we have
s< %
[
|
x
In X
8 7
(47)
1,
> 7.
Proof. Simply notice that
X
Il.f 1(pp]
(3
(>1
+
i=1
where p (s 2 7)/2. Then apply Proposition B.2
15

---

Then, we are able to show the following concentration result about the truncated & Es, whose proof resembles that of LemmalA.S
Lemma A.8. Suppose Assumptions hold and 0o. Let X n with 0 E (0, and 5 E (0, 1). For any > O, denote 2 {ar E X [f) S and E(x) [(x) (mERL)) Then, for du 3- being sufficiently close, holds with probability least 6 that
((xz)) EE(x)
C'nn
2
Ma
(Mad
+ + ++x=
Ma
A a Inn
X (48)
n
n
Consequently, ift n¹' with 1 < 1 -
at 0. we have
1 T
E(<;) - 13((T)
(p(22/2).
(49)
Proof. We follow the same routine the proof of Lemma A.5 and obtain 445 with replaced with E. The only difference is that we have to control
|| e 2/ - 1
< Il + | E falfpl
I Ma MMlllfallpp +t
(CM,A(s-a)) (5 +
where we apply Lemma A.7 at the second inequality. Then, (6 changes to
1 m! (CM3x==<nn)) (CM3X- a+3/2 -0+3/2 Mad (lad)a/2)) mn
and the rest follows.
To bound the extra error terms caused by truncation, we have to use the following proposition about the L embedding of the RKHS [Zhang et al. 2023a Theorem 5].
Proposition A.9. Under Assumption
2 for any S Org and a > ap. we have embedding
2a
[H]] + L (X,
9. a
(50)
Lemma A.10. Suppose Assumptions 5 E (0, 1). Then
7 hold and
with 0 (0, 3) and on. Let Xx 8
T
(īz Tx - (g- TSJ) (g-T5>) (A*/22) op(n -0/22).
(51)
Proof. We will choose / - nt' for some that will be determined later and choose some a > 0o being sufficiently close. Using the same notations in (49). we decompose
E(x:) - (x)
((x.) Bε(x)
E(x, (
(52)
(
The first term in (49 is already bounded by 49 i < we notice that
2ot2 0. To bound the second term in
52
I S4 Vi 1,
implies
{ (1:es))) 0.
71
Since Markov's inequality yields
Panp fa $
24 S $
(53)
16

---

where 2a we get
P (2t Ωe Wi (Paw (ir (2,))* (1 Parn for $ (la))* -1-1-% "1..)) So the second term vanishes with high probability as long as 1/9.
For the third term in (52). using (44). we get
H - (())
E (mgnn)) (f) - (
[11
- Mad T [1 (ego,) (f7 Axx1)]
MaX Mad-a/2 (zff(z) fa(z)) [P $ 22)
MaX -M
Consequently, if then
[ o(\
Finally, the three requirements / are
a a+00
1> Oa
1 <<
0
1> q
and
2
where q=
2a a-s Since 0 < 3 = 0r -1
we can choose a sufficiently close to og such that Oa < 1.
Then,
a + 8
1
a a 8
(1
8)
(1-0a)
> 0,
2
9
2a
and thus
8a
a a
<
<
0
9
showing that we can choose some satisfying all the requirements and the proof is finish.
L
A.4 The noiseless case
The case when À n- for 0 < already covered in Theorem A.2 For the case 0 2 3, the approximation Lemma B.5 no longer holds, and we must reduce it to the former case. However, there have the following monotone relation
direct monotone property of Bias(A) (A). Nevertheless, about the operator norms, whose proof utilizes the idea in Lin et al. [202]] Proposition 6. with modification.
Proposition A.11. Let a = A(Tx + A)-1 E (H)) Suppose A1 S A2, then for any s,P 2 0,
|
((H) = || T (7{) - 1 Il Il = | T
(54)
200
Proof. Let us denote by the partial order induced by positive operators. Since the function A_ is monotone decreasing with X, obtain J = 2. which further implies X 2+X
TO = 2
Then, since ||A|]2 ||AA|| 11. we have
| 2 (H)) = |
2p 3
< 1 1 2
= | 11 ((())))))))))))())))
A1
(9)
(9(())
and the equality in (54) is proven by ||||| Lemma A.12. Under Assumption
||A-||-
assume further s 1. Suppose X = n n- for B. Then, Bias² 2 (A) Opaly (n min(,,2)3)
(55)
17

---

Proof. Since fo is given in 122 and > 1, we have f3 E [7]]" for 1 S < s. In particular, fz E H. so the bias term can also be written as
Bias(A) ||2(Tx + 1)=
(56)
Moreover, from the construction 8 of [H]", we may assume fp = T g for some E I,² with ||a||y= S C, and restrict further that & < 2. Let À x - forl (), Then, using the same notation in Proposition A. we have
(A) = | 62 |
// N 1/ 0
T S/ 1 11/2
||
| 9
$ 0 r /2 // /2
1
1
- 0
T 1/2
N 1
<c r ///
N/ (2-21)/2 1)/2
| ワ
7ー
CX
| 1/2
|| Xi
< cxx2 / 1/2 1/21"
where we use Lemma B.6 for the last inequality. Finally, since Ā x n- for 8, Lemma B.5 implies that with high probability we have
|
x
T
+
-
|
+ xi
51 $1. v3 V3.
Therefore, we obtain
Bias (A) = O3( On(n -1/2))
Since & < minn(s, 2) and 1 < B can arbitrarily close, we conclude 555
Proof of Proposition Let us denote FF = =(f ||5 [z]]-
S R for convenience. Since fz E H.
the bias term can be given by
Bias (A) 1155 (Tx A) ->>1,ر11 [|[[-[x)]]
Lx Ixx5f1l2
for a linear operator Lx = Tx (Tx + +A)=1 1 on H. Then,
sup Bias(A) sup GEFF
||[I [x 15 |
(a)
sup
Tb( Ix 9
GJEF
(T's - -X 0g
sup Issl n sn
T - T (B(H)
(6)
2 x = (n 1) = 9
where in (a) we use the relation between the interpolation spaces and in (b) we use the fact that
and ||A - B| 2 An+1(A) (A) for any operator B with rank at most n (see, for example, Simon (2015
Section 3.5]).
B Auxiliary results
Proposition B.1. Let
f(z) =
+ X
Then,
18

---

(1) If a = 0, then f(2) is monotone decreasing.
(2) If a E (0, then f(z) is monotone increasing in [0, p-.., and decreasing in - to0).
Consequently, f(z) S X
(3) a 2 1, then f()) monotone increasing on [0, +00).
Proof. We simply notice that
2011
f'(2) (++ f)2 (ad - a))=)
Proposition B.2. Suppose cgi S di S Ogi and p > then À -
have
22
1;
i
In 1
p 1;
(57)
p 1.
Proof. We first consider the case when p < 1. Since Cgi letting q
< x < Cgi- from Proposition B.1
-Sp have
Cgr-Pa
if Cgi S qd:
Cai-R+X:
A +
XP/a S Cgi
Cgi- > q²:
Therefore,
2-2p3
SC Σ
2 +C
Σ
d A
(Csi- X)2
i:Cai PygA
MC PSqA
S1 + S2.
For S1, noticing Cgi 8= > qu implies < (gA/Ca) 1/3 we have
((>//c))11/
S C
Σ
8 2(1-11 S ((-11-
For S2, using Proposition
B.l
again we have
f
x --8 2p8
S2 C
-dd dr
(1N/CC)-118_11 (Car 8 + ))2
y-g
2
(Cal9) (Cay- 1)2 y 'y (x= = x-10g
I -
where we note that the last integral is bounded above by a constant. Therefore, we conclude that
fA fo sollpay
I 2 For the lower bound, if Cgi < qd, we have
P
P8
+
A
Cgi 8 +X
and hence
X d + X
I (g>/Ca) 1/9 (CAx A)2"
2p8 -2p8
1 C
dx
y 2p/
C
(Css/)Mo (Coy 3 + 1)2 y dy
2 -
19

---

where we note that the last integral is independent of A.
For the case p= 1, by Proposition B.1 we have
2 --506
20
i-8
Σ
1-1
d + 1
CBt
+
[2X-1/9]
i-9
2
i-8
2
C
Σ
+-+
Σ
i-1
Cgi
C3i +
1/2
[2X [2x-1/0]
2
0
Σ
x
x
dx
22 22-1/08
1=1
10
y 8
2
S SCIn
dy
Cny--+11
2
1
<'nn
For the lower bound, we have
[A-1
Xi
i-
i-
i-1
A + A
CBt 3 A
i=1
[A 1/2
8- cln 1
20
Σ
X
For the case p > 1, by Proposition B.1 we have
2 Σ
x
2
i 1-2
'cc 20
S C,
(Cgi + +
since the last series is summable. The lower bound is derived by
P
2
Proposition B.3. Under Assumption ! for any p 2 we have
N₂(A) = tr (TT
8
A A+ )²
d
x1-1/3
(58)
Proof. Since c 0 < A4 S 3,
we have
= N₂(())
di +
A
P
<
Ci- -x
)
Ci
Σ
C+ Xi
C P
i=l
i=1
C
dx
- -
2/3 2/8
C
P
dy 5 Čx-1118
yo
+C)
for some constant C. The lower bound is similar.
The following inequality about vector-valued random variables is well-known in the literature Caaon-- netto and De Vito 2007
20

---

Lemma B.4. Let H. be real separable Hilbert space. Let E, .i................. En be i.i.d random variables taking values H. Assume that
Eiie - BEll
I =m
Lm
Vm = 2,3,.....
(59)
2
Then for fixed 8 (0, 1), one has
P
Σ & ES
2
+
ln 8
2 - 8.
(60)
vnl
Particularly, a sufficient condition for 559 is
L
||
a.s., and El|s|| S o².
2
The following concentration result has been shown in Fischer and Steinwart (2020), Zhang al.
2023a
We use the form in Li et al. 2023a Proposition 5.8] for convenience, see also Zhang et al.
2023a
Lemma 12].
Lemma B.5. Suppose H has embedding index oo and Assumption I Tholds. Let X = X(n) - 0 satisfy
Q (111/oot)) for some > and fix arbitrary a (as; Og + p)) Then, for all E (0, 1), when is sufficiently large, with probability at least 8.
1/2
11 SC
lun
(61)
n2
where C' > 0 is a constant no depending on 8, n,a, a, and we also have
T2/2T~1/12
T
1/2
T
1/2
I V3.
(62)
XX
(H))
The following operator inequality Fujii et al.
1993 will be used our proofs.
Lemma B.6 (Cordes' Inequality). Let A, B be two positive semi-definite bounded linear operators on separable Hilbert space H. Then
|| 1 2(H) S ||All 2(1)'
Vs E [0, 1].
(63)
The following lemma is a consequence of the fact that x" is operator monotone when E (0, 1] and Lipschitz when 1, see Zhang et al. [2023a] Lemma 35] Lin et al. (2018) Lemma 5.8]. Lemma B.7. Suppose that A and B are two positive self-adjoint operators on some Hilbert space, then
for E (0, 1], we have
||' - BBII S I|A Bl for r 2 1, denote c max max(11 (|| BB).). we have
||AT B" rc 1 Bl|-
C Experiments
C.1 Details of experiments in the main text
Recall that in the experiments section of the main text, we considered the kernel k( y) = min( y)
and [0 1]. We know the eigensystem of k that A; (اi- and e, /2 [ ( n. For the three target functions used in the experiments, simple calculation shows that the relative smoothness (source condition) of (in22)) sin πτ) are 0.5, 1.5, oo respectively.
For some f*, generate data from the model y (z) + where (O, 0.05) and perform KRR with À = en for different 0's with some fixed constant c. Then, we numerically compute the variance, bias and excess risk by Simpson's 's formula with N > n nodes. Repeating the experiment for n ranged in 1000 to 5000 with an increment of 100, we can estimate the convergence rate by a logarithmic least-squares log err = r log n + on the resulting values (variance, bias and excess risk). Figure 2 on page 22 shows the corresponding curves of the results in Table 1 in the main text. Note that for each setting, we tried different e's in the regularization parameter -9 and show the curves under the best choice of (c 0.005).
21

---

Blas; fecos2pix
0.2.2 m=0000
6m02. 0.333
-10
8-24 t- 0.80
5-2.5 mm4.75
-20
2-34 1.22
mm...
-2.
1ug vorlunce
-..
-30
-35
-5.0
-40
-45
1000
2x10
10'
4x10'
5000
2x10
30
4x 5000
Blas: Fpsin
Bias: fmeigen1
8-0.2 tw
2-0.2
0.40
2-2.4 mm-000
0-2-4. mm4.82
2-0.5
awb.5
-6-
6=2.0.
6-3.0.
mm3326
1ug 002
5-1.0.
m=3.9
-8-
-12
2x100
3 10?
X10
5000
2X100
4x 19
Excess risk; fwcos2 pix
Excess risk; f=sin2pix
0-0.2 mm333
0-3-2 m-4.M
6-34,
2-1.4
-2.0
ex0020 maX
9m2.0
3325
9-2.0.
3-3.0. no 0.05
3.50
0.3.0. 0=0.00
224
-4.00
-1.0
-4.25
2x10'
1x10
2xx10
3
4x10"
Excess risk: [meigen1
1-02..m00.5
3.0
0-1.0
-3.5
2-2.0. 1-0.0
Su3.0. 020.00
4.6
-45
20P
Figure 2: Decay curves of the variance: the bias and excess risk of three target functions. Both axes are logarithmic. The curves show the average bias over 100 trials; and the regions within one standard deviation are shown in the corresponding colors.
22

---

C.2 Learning curves with different noises
Cui al. 2021] discussed the "crossover from the noiseless to noisy regime" and shown the interaction between the magnitude of noise and the sample size. As discussed in Remark 3.2 in the main text, our theory can also reflect this interaction. In Figure on page 23 we exhibit the learning curves with different magnitudes of noises and visualize this interaction. Note that in the following the sample size is chosen 10, 20, ... 100, 120, ... 1000, 1100, ... 5000. and we use the same kernel and data generation process before. We repeat the experiments for 100 times for each sample size and present the average excess risk.
Excess 0=1.0; fmcos2pix
Excess risk: 0=2 [=cos2pix
-2.
-2.0
-25
-25
10g
2.0.0
-3.0
2-0.0
0.15
-35
0.15
0-0.30
e.2.0
0.0.0
-40
10
5000
10
5000
fwsin2pix
Excess f=sin2pix
-1.-
-2.0
log ex00s risk
-25
-2.
335
-30
log
-005
0005
-45
2-0.00
0.10
-35
2+0.88
0.30
0.15
-1.
0.15
0.20
10
500D
10
500D
risk; 0m1.0; [meigen1
fmeigen1
115
-2.0
-20
-2.5
0-0.1
-300
log
-4.0
2-0.5
20002
log
2.0.2
2+0.55
-45
0.00
0.68
0.00
0.00
0.15
4.0
0.05
10
5000
5000
Figure 3: Learning curves of three target functions with different noises when choosing À = en
0 1.0, 2.0. Both axes are logarithmic. The black dashed lines represent the theoretical slopes under each choice of 0.
In the above settings, the bias decays faster than variance. Figure 3 on page 23 shows that the excess risk decays fast when n is relatively small and coincides the theoretical asymptotic rate in Theorem 3.2 when is large. The crossover happens for smaller n when the magnitude of noise is larger. Similar phenomenon has also been reported by Cui al. 202T FIG.2, FIG.3). In addition, comparing the sample size when crossover happens for three target functions, our results show that the crossover happens for smaller a when the function smoother, which also consistent with
Thcorem 3.2
23

---

Theorem shows that when 8 2 B. the excess risk is constant asymptotically. Figure on page 24 shows the curves of kernel interpolation 0). It can be seen that they are similar the curves in the second column of Figure 3 on page 23 where we choose 0 = 3 = 2.
D00 bod Euca2pa
RacosLiiA beb: Iungeet
2.2
0.55
0.25
Figure 4: Learning curves of three target functions with different noises when choosing = 0. Both axes are logarithmic. The black dashed lines represent the theoretical slopes.
24


Reviews:
[{"review_id": "blzAHx7IiC", "reviewer": "Reviewer_MHmF", "summary": "This paper studies the generalization error/excess risk of the kernel ridge regression (KRR). Using the classical bias-variance decomposition, the authors gives bounds on the bias term, which is claimed to be tighter than previous literatures. Together with the variance term results from another paper  \"Yicheng Li, Haobo Zhang, and Qian Lin. Kernel interpolation generalizes poorly, March 2023a.\", the authors conclude the bounds on the excess risk asymptotic in the sample size, where the effect of the decay of the ridge is stated explicitly.", "questions": "Could you explain more on the novelty of the paper?", "limitations": "This is a theoretical paper, where the assumptions 1-5 are stated clearly. The authors has remarked that these assumptions hold in general settings. ", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper gives a comprehensive reviews on the excess risk of KRR. There are experiments in both main text and appendix supporting the claimed result.", "weaknesses": "My biggest concern would be that this paper is merely an incremental paper from \"Yicheng Li, Haobo Zhang, and Qian Lin. Kernel interpolation generalizes poorly, March 2023a.\" \n\nAccording to the remarks 3.3 and 3.5, the main theorems 3.2 and 3.4 basically recover the results from previous works: \"Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331–368, 2007. doi: 10.1007/ s10208-006-0196-8.\", \"Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization error rates in kernel regression: The crossover from the noiseless to noisy regime. Advances in Neural Information Processing Systems, 34:10131–10143, 2021.\" and \"Yicheng Li, Haobo Zhang, and Qian Lin. Kernel interpolation generalizes poorly, March 2023a.\"  Other than tightening the bounds, I hardly see more novelty or improvement from the main result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> My biggest concern would be that this paper is merely an incremental paper from \"Yicheng Li, Haobo Zhang, and Qian Lin. Kernel interpolation generalizes poorly, March 2023a.\"\n>\n> According to the remarks 3.3 and 3.5, the main theorems 3.2 and 3.4 basically recover the results from previous works: \n> \"Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331–368, 2007. doi: 10.1007/ s10208-006-0196-8.\", \"Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization error rates in kernel regression: The crossover from the noiseless to noisy regime. Advances in Neural Information Processing Systems, 34:10131–10143, 2021.\" and \"Yicheng Li, Haobo Zhang, and Qian Lin. Kernel interpolation generalizes poorly, March 2023a.\" Other than tightening the bounds, I hardly see more novelty or improvement from the main result.\n\n---\n\n\n\nThe learning curves of KRR, depicting the interaction between the source condition ($s$) of the regression function, the capacity ($\\beta$) of the underlying RKHS, the choice of the regularization parameter ($\\lambda$), and the noise level ($\\sigma^{2}$), might be one of the most important questions in the recent renaissance of the study of kernel methods.  It requires us to obtain the matching upper and lower bounds of the bias term, the variance term and thus the excess risk of KRR estimator for specific regression function $f^*$ with respect to the regularization parameter $\\lambda$.   \n\nWe have to first emphasized that the learning curves is quite different than the traditional minimax theory: \n\n1. the minimax theory only provide the worst-case lower bound for a class of regression functions, while the learning curves can show the exact rate for any specific regression function;\n2. the minimax theory only considers the optimal choice of $\\lambda$ and the optimal rate, while the learning curves determine the exact asymptotic rate ( both upper bound and lower bound) for any choice of $\\lambda$ ( $\\propto n^{?}$).\n\nWe then list the differences in several related works (some of them already mentioned by you): \n\n1. The work \"Andrea Caponnetto and Ernesto De Vito. 2007\" considered only the minimax framework. Since it explicitly assumed that $f\\in [\\mathcal H]^{s}$ for $1\\leq s\\leq 2$, it can not be applied to the more general situation where $f\\in [\\mathcal H]^{s}, s\\in (0,2]$. Moreover, it did not provide the lower bounds for both the bias term and variance term, so it can not provide the learning curves.\n2. The paper \"Yicheng Li et al. 2023\" focused on the variance term of the kernel interpolation, so it also can not answer the question of the learning curve.\n3. \"Hugo Cui et al. 2021\"  firstly described the learning curve based on an heuristic argument and the Gaussian design assumption.  However, the Gaussian design assumption is unrealistic: it requires the eigenfunctions (see Eq. (5)) to be distributed independently, which can not be the case even for a simplest 1-d toy model (see the model in the Experiment section).\n4. Random matrix arguments were used by [Jin et al](arxiv.org/abs/2110.12231), but some gaps existed in their argument (as discussed in [Zhang et al. 2023](https://openreview.net/forum?id=Kg2al3GXBR)).\n\nTo sum up, several groups of researchers recently tried to solve the learning curve problem from various aspects. The novelty/contribution is that we provide the **first** mathematically solid solution of determining the exact asymptotic rates of learning curve in KRR under more realistic/general assumptions. \n\nWe believe that our paper is more like a landmark paper in the theory of KRR rather than an incremental paper and hope that we can convince you of its importance to the community of kernel regression. Moreover, the learning curve of the KRR with data of fixed dimension would also be served as a prototype study of the investigation of the generalization ability of KRR with data of large dimension where $d$ may diverge. \n\nLastly, to conclude this part, we want to talk a little bit more about the importance of determining the learning curve of KRR. Since Jacot et al. 2018 observed that the training process of the wide neural network trained by gradient descent can be well approximated by that of kernel regression with respect to NTK trained by gradient descent, studying the kernel regression with respect to the NTK becomes a common strategy to grasp the basic asymptotic properties of training a neural network.\n\nIn addition, kernel gradient descent with stopping time $t$ roughly corresponds to KRR with regularization $\\lambda = t^{-1}$ despite some subtle differences. Since it is of interest to understand how the condition of the regression function, the noise level and the choice of stopping time affect the generalization of neural networks, we want to investigate effect of these parameters on KRR, which is answered by the so-called learning curves. \n\nWe hope that our explanation would address your concern and convince you that our contribution is enough.\n"}, {"review_id": "TKrG1wqWw9", "reviewer": "Reviewer_oJ4i", "summary": "The paper studies the asymptotics of kernel ridge regression learning curves when the kernel eigenvalues and the ridge parameter both obey a power law.", "questions": "1. In line 56, $s$ is not defined. Also, it does not match the main result (i.e. it should be $s \\geq 2$  rather than $s \\geq 1$).\n\n2. In random matrix theory, precise asymptotics can be obtained by relying on Gaussian equivalence principles and provide almost perfect learning curves for kernel regression (see Cui et.al. 2021). What insights the theory developed here brings in addition to the previous results and why do you think Gaussian assumption works so well?", "limitations": "The limitations section is missing.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "1. The paper is readable and well written. \n\n2. It derives asymptotic results for KRR for a specific choice of kernel eigenvalues and regularization. \n\n3. The introduction of technical definitions is clear, and sufficient background for previous results is provided.", "weaknesses": "1. The claims of the paper are confusing to me. The double-descent phenomena (in this case sample-wise in the noisy case) implies that there is a second descent after the U-shaped curve, while the authors did not seem to reproduce that result.\n\n2. The learning curves plotted in Figure 1. are with respect to the ridge parameter, while learning curves often refer to the generalization error as a function of training set size.\n\n3. Experiments are not sufficient to demonstrate the tightness of the theoretical results. \n\n4. The references (Bordelon et al. [2020], Cui et al. [2021]) cited in the paper demonstrate near perfect agreement with experimental learning curves despite the Gaussian assumption, but a discussion relating those results to the theory here is missing.\n\n5. The claim regarding wide neural networks and benign overfitting stated in line 47 is neither explained nor demonstrated by experiments.\n\n6. In general, a clear comparison to previous literature is missing, and it is hard to understand the novelty brought by this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your carefully review. \n\nThe KRR learning curve, recently proposed in Bordelon et al. [2020], Cui et al. [2021], aims to   depict the interaction between the source condition ($s$), capacity ($\\beta$), the choice of the regularization parameter ($\\lambda$), and the noise level ($\\sigma^{2}$).The main novelty/contribution is that we provided the first mathematically solid solution under more realistic/general assumptions. \n### Weakness:\n*\"1. The claims of the paper are confusing...\"*\n\n There are several works used the terminology \"double descent\":\n\n1.   [Nakkiran, 2019a](https://openreview.net/forum?id=B1g5sA4twr) used it to desribe the double descent behaviour as the number of parameters increases.\n2.  ([Nakkiran, 2019b](http://arxiv.org/abs/1912.07242), [Hastie, 2020](http://arxiv.org/abs/1903.08560)) and related simple models used it to descirbe double descent behaviour as $\\rho=\\lim\\frac{p}{n}$ increases.\n3.  [Yilmaz, 2022](http://arxiv.org/abs/2206.01378) used it to describe that a second valley may occur after the U-shaped curve with respect to the regularization parameter in some certain settings.\n\nSince  the data of dimension is fixed in the current paper, the most relevant scenarios to us should be the 1st and the 3rd cases.\n\nIf you are referring to the 1st scenario,  the double descent curve should be a curve describe the generalization performance of neural network along with the width $m$ goes to infinite. Our work only discuss the scenario $m=\\infty$. We do not need to be consistent with the double descent phenomenon.\n\nIf you are referring to the 3rd scenario, our results prove that the learning curve of KRR is exactly U-shaped in our setting, so the regularization-wise double-descent phenomenon does not exist in KRR. \n\n*\"2.The learning curves plotted in Figure 1...\"*\n\nIn this paper, we adopt the terminology \"learning curve\" appeared in Bordelon et al. [2020], Cui et al. [2021] which refers to the generalization error curve with respect to the model complexity (corresponding to the ridge parameter $\\lambda$ here). The learning curve is upper bounded traditionally by a U-shaped curve.\n\n*\"3.Experiments are not sufficient to...\"*\n\nThe experiment is for illustrative purpose in a theoretical paper.  In Table 1, the experimental results of both variance and bias term match the theoretical values. Could you please provide more comments so that we could improve the experiments? \n*\"5.The claim regarding wide neural networks and...\"*\n\nThanks for your suggestion. We are sorry that we did not make it clear enough in this version and will make more explanation in the new revision.  \n\n1. It is showed that  the generalization error of wide neural networks can be well approximated by that of kernel regression with NTK (see [Jacot et al. 2018](https://proceedings.neurips.cc/paper/2018/file/5a4be1fa34e62bb8a6ec6b91d2462f5a-Paper.pdf) and follow-up works).\n2. Our results imply that in the noisy case KRR with NTK does not perform well if $\\lambda$ is relatively too small, which is the case when overfitting happens. \n3. Consequently, we can expect that overfitting in neural networks also impairs generalization. \n\n*\"4.The references (Bordelon et al. [2020], Cui et al. [2021]) cited...\"* \n\n*\"6.In general, a clear comparison...\"*\n\nWe will make it is more clear in the revision. For example, we will add the following paragraph:\n\n\"The learning curve of KRR was recently described by in  Bordelon et al. [2020], Cui et al. [2021]. However, these works are all based on the unrealistic Gaussian design assumption and some heuristic argument. Though the heuristic arguments are inspirational, a rigorous proof is indispensable if one plans to perform further investigations. In this work, we provide the first rigorous proof for most scenarios of the smoothness $s$, eigenvalue decary rate $\\beta$, noise level $\\sigma^{2}$ and the regularization parameter $\\lambda$ based on the most common/realistic assumptions.\"\n\nWe hope this will make the contribution and significance of our work more clear.\n### Questions:\n\n*\"1.In line 56, $s$ is not defined...\"*\n\nWe will add the explanation of the quantity $s$ before its appearance in the new revision: $s$ refers to the smoothness of the regression function (Eq. (12)). When $s \\geq 1$, $f^* \\in \\mathcal{H}$ so this case is often called the well-specified case, and when $s \\in (0,1)$, $f^* \\notin \\mathcal{H}$ so it is called the mis-specified case, so the statement in Line 56 is correct. Moreover, since our main results (Eq. (15) in Thm 3.1 and Eq. (16) in Thm 3.4) cover both the cases, we do not distinguish them in the statement. \n\nWe guess the statement in Eq. (17) might be the reason for your confusion. In fact, Eq. (17) deals with the case $s > 1$ and the separation of $s \\in (1,2]$ and $s > 2$ is due to technical difficulties. We hope these explanation will clarify the issue.\n\n*\"2.In random matrix theory, precise asymptotics can be obtained...\"*\n\nThanks for your great question. It is actually a very delicate problem. Though solve it certainly beyond the scope of the current paper, we would like to discuss a little bit on it and will try to solve it in a future work.\n\n- (A) The Gaussian design assumption is an unrealistic assumption (i.e., one can not hope it hold for general kernel), however, with this assumption and some heuristic argument, Cui et al, 2021 can describe the learning curve in all scenarios.\n\n- (B) On the other hand, we provide a rigorous mathematical proof in almost all the scenarios via a completely different approach using the concentration inequality of integral operators.\n\nThe interesting thing is that these two results actually suggests there might be a strong universality hidden here. This hypothetic universality might be the reason why Gaussian design assumption works so well. Furthermore, we think this universality (if we can make it rigorously) might help us extend our results from almost all the scenarios (A) to all the scenarios (B)."}, {"review_id": "yhhyfGhYxw", "reviewer": "Reviewer_j73d", "summary": "The authors focus on the learning curve of kernel ridge regression, an important topic in theoretical machine learning, which is also used to approximate the generalization ability of 'lazy trained/NKT regime' neural networks. \n\nThe authors provide a nearly full characterization of the learning curve in the setting of Source/Capacity conditions, considering the effects and interplay of the regularization parameter, the source condition, and the noise, rigorously closing many gaps in the literature, and in particular the picture arising from recent works in Neurips.\n\nThe paper's contributions include: \n* Providing sharp estimates of the asymptotic orders of the bias term when the regularization parameter is not too small. This result holds for both well-specified and misspecified cases, improving the upper bounds given in previous research.\n* Showing an upper bound of the bias term in the nearly interpolating case. This upper bound is tight and matches the information-theoretic lower bound.\n* Providing learning curves of KRR for both noisy and noiseless cases, and the interplay between the two. \n\n", "questions": "* I would be interested to know more about the limitation of the predictions. Removing the Gaussian assumption is quite a feat, but are they any restrictions on the data structure except the power law distribution/embedding dimension? Indeed, it seems there are only Eigenvalue decay assumptions in the paper! Do this means that any distribution of data in the RKHS is OK and that only the Covariance matrix matters? It would help me immensely to be explicit and to give counter examples.\n\n* With respect to Cui et al, it seems to me that the authors prove their entire phase diagram (Theorem 1 and 2), except for the left region of the blue region in Fig. 1 of Cui et al. I believe. The regime where θ ≥ β, is also very interesting, and I would be interested in understanding the reason why it is harder to control. Is it a possibility that in this region the data structure becomes relevant so that the Gaussian assumption is needed or do the authors believe it is only a technical problem? I remember a similar problem arises in Jacot et al.", "limitations": "From a theoretical point of view, the paper is certainly addressing its limitation and has no ethical issue that I can foresee. It would still be interesting to be given the code to reproduce the figure in the supplementary material.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I believe this is a strong paper. \n\nMost recent arguments on the learning curve of kernel methods were not entirely rigorous, and are based on the ‘Gaussian design’ assumption, which is certainly very restrictive. Even within the realm of Gaussians, Bordelon et al used a non-rigorous the replica method, while Cui et al used results from CGMT, but extrapolated their domain of validity. Random matrix arguments were also used by Jin et al, but some gap existed in the argument. \n\nThis paper bridges the mathematical gap and manages to prove rigorously a nearly complete picture, removing the Gaussian assumptions. It closes a clear gap in the mathematics of Kernel ridge regression.\n\n\n\n\n", "weaknesses": "I do not believe the paper has any particular weaknesses.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive feedback on our work.\n\nQuestions:\n\n> *1.\"I would be interested to know more about the limitation of the predictions. Removing the Gaussian assumption is quite a feat, but are they any restrictions on the data structure except the power law distribution/embedding dimension? Indeed, it seems there are only Eigenvalue decay assumptions in the paper! Do this means that any distribution of data in the RKHS is OK and that only the Covariance matrix matters? It would help me immensely to be explicit and to give counter examples.\"*\n\n**Our response:**  \n\nThe current work relies on two essential assumptions: 1.  the power law eigenvalue decay; and 2. the embedding index assumption.  These two assumptions implicitly depend on the data marginal distribution $\\mu$ on $\\mathcal{X}$, which serves as the underlying measure defining the eigenvalue (Eq. (4) and (5)). \n\nSince we have illustrted that the assumption 2 holds for many RKHSes, we would like to speculate that the embedding index assumption holds for all RKHS defined on $\\mathcal X$ when $\\dim \\mathcal X$ is fixed. We are not sure if we can  construct a concrete example. \n\n\n\n> 2.*\"With respect to Cui et al, it seems to me that the authors prove their entire phase diagram (Theorem 1 and 2), except for the left region of the blue region in Fig. 1 of Cui et al. I believe. The regime where θ ≥ β, is also very interesting, and I would be interested in understanding the reason why it is harder to control. Is it a possibility that in this region the data structure becomes relevant so that the Gaussian assumption is needed or do the authors believe it is only a technical problem? I remember a similar problem arises in Jacot et al.\"*\n\n**Our response:** We believe that the regime where $\\theta \\geq \\beta$ is very tricky. In this regime, althought we can provide matching upper and lower bounds for the bias term, only the lower bound for the variance term is obtained so far. \n\nThe main difficulty we are facing is that we can no longer use the concentration approach when $\\theta \\geq \\beta$. The basic idea of concentration approach is that we want to show $(T_X+\\lambda)^{-1}$ (for $T_X$, see Eq. 18) can approximate $(T+\\lambda)^{-1}$ well. Since the eigenvalues of $T$ (and $T_X$ of course) tends to zero, $(T+\\lambda)^{-1}$ diverges as $\\lambda \\to 0$ so we can not expect the concentration can still hold when $\\lambda = n^{-\\theta}$ is small, which turns out to fall into the regime $\\theta \\geq \\beta$. \n\nThough our current technical tools fail in this regime, we expect that it is still be possible to rigorously prove the learning curve predicted by Bordelon et al. [2020], Cui et al. [2021] in this regime. We guess there might be some universality hidden in the learning curve problem of KRR. More precisely, if we take the learning curve as an output of the jont distribution of $\\{\\phi_{j}(x_{\\mu})\\}$, the results based on Gaussian design assumption (which assumes that the joint distribution is indpedeng Gaussian variables) and our results actually suggest that this output(the learning curve of KRR) does not depend on the distribution. "}, {"review_id": "STR2pZ4Aox", "reviewer": "Reviewer_xyck", "summary": "This paper analyzed generalization error rates for the Kernel Ridge Regression (KRR) problem. The authors make use of several generic assumptions, including (i) eigenvalue decay, (ii) Embedding index, (iii) source condition, and (iv) Holder continuity of the kernel. It is worth noting that assumptions (i), (ii), and (iv) are generally applicable to popular kernels. The findings of this study align with previous knowledge: in the absence of noise, interpolation achieves optimality, while in the presence of noise, a well-known Bias-Variance tradeoff emerges.", "questions": "In addition to Weaknesses section I have Following questions,\n\nI understand assumption 2 and 3 are common for these kind of analysis. But would you please elaborate,\n\n1. What is the significance of the \"embedding index\"? What are the implications if α << 1/β or α >> 1/β?\n\n2. What are the limitations of assumption 3? From my understanding, as \"s\" increases, the function f* becomes smoother since it belongs to H^s. Could you please clarify when this assumption holds or fails?\n\n\nI am willing to increase my score if the authors address these questions in Weaknesses/Questions sections.", "limitations": "See weaknesses and questions.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper is well-written, exhibiting a high level of clarity and coherence in its structure and language.\n2. The main result presented in the paper is not only insightful but also highly intriguing, contributing valuable insights to the research area.\n3. The authors have demonstrated diligent referencing and citation of relevant prior work, showcasing a thorough understanding of the existing literature in the field.", "weaknesses": "While I believe the paper is well-written, I feel that there are some areas where the authors assume background knowledge from the reader or make claims without providing adequate supporting discussions. I have identified a few specific points that I believe could benefit from clarification or additional explanation:\n\n1. The contribution section appears to be highly technical. It would be helpful to provide a high-level, less technical overview of the contributions before diving into the specifics. For example, it would be beneficial to provide a brief explanation of the significance of variables such as β and s, as these variables are not defined prior to that section. \n\n2. In line 47, it is mentioned that \"our results...MAY suggest the benign...\". The term \"may\" introduces uncertainty, but it is unclear how this conclusion was reached or what factors contribute to this interpretation/uncertainty. It seems that the authors may have intended to convey that since wide neural networks are essentially kernels, and the rates clearly demonstrate that noise impairs generalization, it is unlikely for the noise to have a benign effect. If this is indeed the case, it would be helpful to present this point in a clearer and less convoluted manner.\n\n3. The second row of Figure 1 mentions \"overfitting\" and \"underfitting,\" but there is no prior discussion or explanation of these terms in the paper. It would be beneficial to define these terms and provide some context.This would enhance the understanding of the results presented in the figure. Overall the second row figures were unclear to me.\n\n4. In line 290, the statement mentions that \"These results will help us better understand the generalization mistery of neural networks.\" \nIt is unclear how this conclusion was reached or what specific discussions led to it. It would be valuable to elaborate on the implications of the results and provide a more thorough explanation of how they contribute to a better understanding of the generalization of neural networks.(by the way \"mistery\" is a typo!)\n\nOverall, by addressing these points, the paper can become more accessible to a broader range of readers and ensure a clearer understanding of the key concepts and conclusions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive feedback on our work.\n\n### Weaknesses:\n\n> *\"1. The contribution section appears to be highly  ...\"*\n\n**Our response:** \n\nWe agree that our contribution is indeed relatively technical and thanks for your helpful suggestions. \n\nFollowing your advice, in the new revision we will add a high-level, less technical overview of our contributions and the explanation of the quantity $s$ and $\\beta$ prior to that section as well. We plan to add several paragraphs discussing the significance of the parameters \"$\\beta$, $s$\".  For example, we plan to include something like following into the revision:\n\n“The parameter $\\beta$, describing the eigenvalue decay rate ($\\lambda_i \\asymp i^{-\\beta}$, see Eq. (6)) of a certain operator, characterizes the span of the RKHS and the interplay between the RKHS and the marginal distribution of $\\mu$, which is also referred to as the capacity condition or effective dimension condition (Caponnetto & De Vito, 2007; Steinwart et al., 2009). Moreover, larger $\\beta$ implies better regularity of the functions in the RKHS. \n\nAnother parameter $s$ (see Eq. (12)) further describes the relative smoothness of the regression function $f^*$ with respect to the RKHS. For example, $s=1$ implies that the regression function has no more smoothness rather than just belonging to the RKHS. Similarly, larger $s$ implies better relative smoothness of $f^*$. ”\n\n> *2. \"In line 47, it is mentioned that \"our results...MAY suggest the..\". ...\"*\n>\n> *4. \"In line 290, the statement ...\"*\n\n**Our response:** We are sorry that we did not make it clear enough and your explanation is indeed the case. \n\nThe theory of neural tangent kernel (NTK) shows that wide neural networks trained by gradient descent can be well approximated by certain kernel regression called kernel gradient descent with the corresponding NTK (Jacot et al. 2018). In addition, kernel gradient descent with stopping time $t$ corresponds to KRR with regularization $\\lambda = t^{-1}$ despite some subtle difference. \n\nOn the other hand, our assumptions hold for NTK associated with ReLU neural networks as discussed in the paper, so our results imply that in the noisy case KRR with NTK does not perform well if $\\lambda$ is not chosen properly. \n\nConsequently, we can expect that if the stopping time in training the neural network is not chosen properly, the neural network can not generalize well. In particular, too late stopping time, namely overfitting, will impair the generalization. This is the theoretical insight that we provide for understanding the generalization of neural networks.\n\nHowever, we note that there is a subtle difference between KRR and the kernel gradient descent regression which approximates wide neural networks, so our results could not directly apply to neural networks and we have to use the term \"may\" here. We are looking forward to dealing with this subtle difference rigorously in our future work.\n\n> *3. \"The second row of Figure 1 mentions \"overfitting\" and \"underfitting,\" ...\"*\n\n**Our response:** We use the terms \"overfitting\" and \"underfitting\" in basically the traditional sense: if the variance dominates the bias, then overfitting happens, and if bias dominates the variance, underfitting happens. We will add more explanation on these terms in the new revision. The second row figures demonstrate convergence rates obtained by different magnitude of regularization ($\\lambda = n^{-\\theta}$). From the bias-variance tradeoff, we can expect that a relatively smaller $\\lambda$ (i.e., larger $\\theta$) results in overfitting that the variance dominates the bias, and a larger $\\lambda$ leads to underfitting. Therefore, we can divide the domain of $\\theta$  into regions of underfitting and overfitting (interpolating as an extreme case of overfitting). Moreover, since these regions are also related to the parameters $s$ and $\\sigma^2$, we can make a phase diagram showing how these regions are affected by these parameters. The two plots show the impact of $s$ and $\\sigma^2$ respectively. We hope this will clarify the plots. \n\n## Questions:\n\n> *1. \"What is the significance of the \"embedding index\"? ...\"*\n\n**Our response:** \n\nIf we did not mis-understand your question, the \"$\\alpha$\" in your question should be $\\alpha_{0}$, the embedding index.\n\nIn our analysis, the embedding index serves as a critical tool to sharpen the concentration inequalities (e.g., Lemma 3.5 in the supplementary material).  Smaller $\\alpha_{0}$ enables us to derive better (tighter) concentration inequalities. \n\nFrom the theory of RKHS, it can be shown that the embedding index $\\alpha_0$ always satisfies $1/\\beta \\leq \\alpha_0 \\leq 1$. As we have listed in the paper, $\\alpha_{0}=1/\\beta$ holds for lots of RKHSs. Since we did not find any example with $\\alpha_{0}>1/\\beta$, we would like to further speculate that $\\alpha_{0}=1/\\beta$. To prove this conjecture would require more involved mathematical argument, so we  leave it to the future study.\n\nIn case that $\\alpha_{0}>1/\\beta$ happens, we can only obtain the exact asymptotics for a restrictive range of $\\lambda$ and the full learning curve can not be provided.  \n\n> *2. \"What are the limitations of assumption 3? ...\"*\n\n**Our response:** \nYou are right. The larger the $s$, the smoother the functions in $[\\mathcal H]^{s}$. \n\nAssumption 3 assumes an expansion of the regression function under the eigen-basis such that the coefficients satisfy a polynomial decay. Since $\\{e_i\\}$ forms a orthonormal basis for $L^2$, any $L^2$ function admits an expansion over the basis with some square-summable coefficients. Then, the rate at which the coefficients tend to zero determines the smoothness index $s$, so this assumption is rather general. In fact, this assumption can also be weaken to other forms such as a polynomial decay of the tail sums of the coefficients, but we adopt this form of simplicity. Thus, we think this assumption is general enough to cover most the cases of interest."}, {"review_id": "33DHgAUacG", "reviewer": "Reviewer_3aFw", "summary": "This paper provides a rigorous analysis of the asymptotic rates of kernel ridge regression. Building on works which analyzed the Gaussian design case, this work recovers the same rates using less severe restrictions on the distribution of features. The novel contribution here beyond similar works of Li et al 2023 (a,b) is to characterize the rate of the bias term. The authors derive a complete phase diagram of the possible behaviors and provide the optimal scaling of the ridge parameter $\\lambda \\sim n^{-\\theta}$.  They provide experiments on simple sinusoidal regression problems where eigenvalues and eigenfunctions are exactly known and show that the theoretical rates match the experimental rates. ", "questions": "1. Can similar analysis techniques be applied to other decay rates? Suppose the eigenvalues fell not as a power law but instead exponentially fast $\\lambda_i = e^{- i \\beta}$. Could the same techniques be used to prove rates in this case ? Another setting of interest are polynomial regression problems in high dimension such as those studied by [Canatar et al 2021](https://www.nature.com/articles/s41467-021-23103-1). Is a rigorous proof of these curves possible as well in the high dimensional limit?\n\n2. The authors claim that \"that the benign overfitting phenomenon may not exist if one trains a very wide neural network.\"  Which of the results in the paper do the authors thinks support this claim?\n\nTypos\n1. line 6 \"attentions\" should be \"attention\"\n2. line 17 \"arisen\" -> \"arising\"\n3. line 32  \"attentions\" -> \"attention\"\n4. line 86 \"orders\" -> \"order\"\n5. line 291 \"mistery\" -> \"mystery\"\n", "limitations": "The authors address the technical limitation of their current approach in the $\\theta \\geq \\beta$ regime and leave the solution open as a future problem. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper gives a rigorous analysis of kernel regression rates when eigenvalues fall in a power law $\\lambda_i \\sim i^{-\\beta}$. The specifically novel contribution in this work is obtaining the rate of decay of the bias term and giving an exact set of assumptions that give these rates (embedding index, source condition, Holder condition on kernel, etc). \n\nThe analysis recovers known (correct) results, which have been proven in the worst case, and calculated exactly under Gaussian design assumptions. The authors also provide empirical evidence to support their claimed rates on a toy data distribution, which is good for a theory paper. ", "weaknesses": "**Obtained learning curves pre-exist in the literature**\n\nThe rates obtained match prior non-rigorous analyses and so do not exhibit *new* behaviors over what has been studied in the prior works. That said, the rigorous proof under relaxed set of conditions is still useful.\n\n**Title seems too broad**\n\nThe title seems to cover too much territory. I would recommend a more descriptive title like \"Rigorous analysis of bias and variance rates for KRR\" \n\n**Relevant works**\n\nWhile the paper does mostly a good job of citing relevant prior works, it misses a few relevant works on this area\n\n1. [Spigler et al 2019](https://arxiv.org/abs/1905.10843) which obtains rates in the noiseless regime using statistical physics techniques. \n2. [Canatar et al 2021](https://www.nature.com/articles/s41467-021-23103-1), which also gives the bias and variance terms for noisy kernel ridge regression under the Gaussian design with the replica method.  \n3. [Simon et al 2023](https://openreview.net/forum?id=FDbQGCAViI), which uses a different heuristic to derive the average case KRR learning curve and introduces the idea of 'learnabilities' as a way of reasoning about the KRR predictor. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive feedback on our work.\n\n### Weaknesses:\n\n> **Obtained learning curves pre-exist in the literature**\n>\n> The rates obtained match prior non-rigorous analyses and so do not exhibit *new* behaviors over what has been studied in the prior works. That said, the rigorous proof under relaxed set of conditions is still useful.\n\n**Our response:** Thanks for recognizing our contribution in providing a rigorous proof of prior works. To be honest, we owe much to the pioneer works by Bordelon et al. [2020] and Cui et al. [2021] who proposed the description of the exact order of the learning curve. It is our honor to have the chance to provide a rigorous proof of their inspirational statements.\n\n> **Title seems too broad**\n>\n> The title seems to cover too much territory. I would recommend a more descriptive title like \"Rigorous analysis of bias and variance rates for KRR\"\n\n**Our response:** The terminology \"learning curve\" was used in Bordelon et al. [2020] and Cui et al. [2021]. We think this title clearly indicates that our work is a follow-up work of their inspirational arguments/statements and we owe much credits to their works.  Thanks to your concern, we realized that we only solve the problem in the asymptotic sense under the power law decay, so how about we change the title to \"On the asymptotic learning curve of KRR under power law decay\"?\n\n\n\n> **Relevant works**\n>\n> While the paper does mostly a good job of citing relevant prior works, it misses a few relevant works on this area\n\n**Our response:** Thank you for referring these relevant works on this area. We will add them in the revision of the paper.\n\n### Questions\n\n>  Can similar analysis techniques be applied to other decay rates? Suppose the eigenvalues fell not as a power law but instead exponentially fast-$\\lambda_i=e^{-i\\beta}$. Could the same techniques be used to prove rates in this case? Another setting of interest are polynomial regression problems in high dimension such as those studied by [Canatar et al 2021](https://www.nature.com/articles/s41467-021-23103-1). Is a rigorous proof of these curves possible as well in the high dimensional limit?\n\n**Our response:** We believe that our analysis techniques can be applied to other decay rates, including the exponential rate, but the analysis will be more sophisticated.\n\nThanks for your nice reference. It greatly enlarges our understandings of kernel regression in high dimensions. We are also very interesting in determining the learning curve of KRR with high dimensional data. When the dimension $d$ is large, the eigenvalues may depend on $d$.  This makes the learning curve problem much more difficult.   Our current results can not be applied to the high dimensional data. We will try to extend our results to the high dimensional setting in future work.\n\n\n\n> The authors claim that \"that the benign overfitting phenomenon may not exist if one trains a very wide neural network.\" Which of the results in the paper do the authors thinks support this claim?\n\n**Our response:** The theory of neural tangent kernel (NTK) shows that wide neural networks can be well approximated by certain kernel regression with the corresponding NTK (Jacot et al. 2018). On the other hand, our assumptions hold for NTK associated with ReLU neural networks as discussed in the paper, so our results imply that in the noisy case KRR with NTK does not perform well if $\\lambda$ is relatively too small, which is the case when overfitting happens. Consequently, we can expect that overfitting in neural networks also impairs generalization. \n\nHowever, we note that there is a subtle difference between KRR and the kernel gradient descent regression which approximates wide neural networks, so our results could not directly apply to neural networks and we have to use the term \"may\" here. Nevertheless, we think that our theoretic results strongly suggest that the benign overfitting phenomenon for wide neural networks does not hold in our fix dimension setting."}]

Author rebuttal:

Meta-review: The paper studies the generalization error/excess risk of the kernel ridge regression through a bias/variance decomposition. There is a vast literature on this topic in the past few years, and the paper does make a few novel contributions, mostly deriving a matching upper and lower bound (lower bounds are somewhat rare in the literature to the best of my knowledge) without the typical Gaussian assumption.

Overall, the reviewers are positive about the paper. Some concerns raised by the reviewers have been successfully answered by the authors during the discussion period. There are some concerns that the authors promised to address in the revised version. This includes better explanations regarding the novel aspects of the proof as well as changing the title (as raised by one reviewer, the current title is simple too general and does not clearly highlight the contribution of the paper). I think it would also be beneficial to make the abstract and introduction more precise regarding the setting of the paper (e.g. over-parametrized regime, polynomial decay for the eigenvalues of the kernel, etc). I trust the authors will address this point as promised in the rebuttal. I personally think this will significantly increase the impact of the paper as it otherwize might simply be overlooked due to the large literature in this field.

In conclusion, I recommend acceptance, and I expect the camera-ready version to address the remaining concerns.
Decision: Accept (poster)