Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime
Authors: Hugo Cui
Bruno Loureiro
Florent Krzakala
Lenka Zdeborova
Venue: NeurIPS 2021 Poster (2021)
Keywords: Statistical Physics
Kernel ridge regression
Teacher-Student
Replica method
High-dimensional statistics
Gaussian Design

Abstract: In this manuscript we consider Kernel Ridge Regression (KRR) under the Gaussian design. Exponents for the decay of the excess generalization error of KRR have been reported in various works under the assumption of power-law decay of eigenvalues of the features co-variance. These decays were, however, provided for sizeably different setups, namely in the noiseless case with constant regularization and in the noisy optimally regularized case. Intermediary settings have been left substantially uncharted. In this work, we unify and extend this line of work, providing characterization of all regimes and excess error decay rates that can be observed in terms of the interplay of noise and regularization. In particular, we show the existence of a transition in the noisy setting between the noiseless exponents to its noisy values as the sample complexity is increased. Finally, we illustrate how this crossover can also be observed on real data sets.

Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime
Hugo Cui SPOC, EPFL, Lausanne bugo.cui@epfl...
Bruno Loureiro IdePHICS, EPFL, Lausanne
Florent Krzakala IdePHICS, EPFL, Lausanne
Lenka Zdeborová SPOC, EPFL, Lausanne
Abstract
In this manuscript we consider Kernel Ridge Regression (KRR) under the Gaussian design. Exponents for the decay of the excess generalization error of KRR have been reported in various works under the assumption power-law decay eigenvalues of the features variance. These decays were, however, provided for sizeably different setups, namely in the noiseless case with constant regularization and in the noisy optimally regularized case. Intermediary settings have been left substantially uncharted. In this work, we unify and extend this line of work, providing characterization of all regimes and excess error decay rates that can be observed in terms of the interplay of noise and regularization. In particular, we show the existence of a transition in the noisy setting between the noiseless exponents to its noisy values as the sample complexity is increased. Finally, we illustrate how this crossover can also be observed on real data sets.
Introduction
Kernel methods among the most popular models in machine learning. Despite their relative simplicity, they define powerful framework in which non-linear features can be exploited without leaving the realm of convex optimisation. Kernel methods in machine learning have long and rich literature dating back to the 60s II 2], but have recently made it back to the spotlight as a proxy for studying neural networks in different regimes, e.g. the infinite width limit [3+6] and the lazy regime of training (7). Despite being defined in terms of a non- caraaaamettri optimisation problem, kernel methods can be mathematically understood as standard parametric linear problem (possibly infinite) Hilbert space spanned by the kernel eigenvectors
features). This dual picture fully characterizes the asymptotic performance of kernels in terms of trade-off between two key quantities: the relative decay of the eigenvalues of the kernel (a.k.a. its capacity) and the coefficients of the target function when expressed feature space (a.k.a. the source). Indeed, a sizeable body of work has been devoted to understanding the decay rates of the excess error as a function of these two relative decays, and investigated whether these rates are attained by algorithms such as stochastic gradient descent g 19.
Rigorous optimal rates for the excess generalization error in kernel ridge regression and are well- known since the seminal works of [10 [1]. However, recent interesting works [12 [3] surprisingly reported very different and actually better rates supported by numerical evidences. These papers appeared to either not comment on this discrepancy [13,, or to attribute this apparent contradiction difference between typical and worse-case analysis [1]. As we shall see, the key difference between these works stems instead from the fact that most of classical works considered noisy data and fine-tuned regularization, while 22 focused on noiseless data sets. This observation raises number of questions: is there connection between both sets of exponents? Are Gaussian design
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

exponents actually different from worst-case ones? What about intermediary setups (for instance noisy labels with generic regularization, noiseless labels with varying regularization) and regimes (intermediary sample complexitiss)? How does infinitesimal noise differ from no noise at all?
Main contributions - In this manuscript, we answer all the above questions, and redeem the apparent contradiction by reconsidering the Gaussian design analysis. We provide unifying picture of the decay rates for the excess generalization error, along more exhaustive characterization of the regimes in which each is observed, evidencing the interplay of the role of regularization, noise and sample complexity. We show in particular that typical-case analysis with Gaussian design is actually in perfect agreement with the statistical learning worst-case data-agnostic approach. We also show how the optimal excess error decay can transition from the recently reported noiseless value to its well known noisy value as the number of samples is increased. We illustrate this crossover from the noiseless regime the noisy regime also in variety of KRR experiments on real data.
Related work The analysis of decay rates for kernel methods and ridge regression a classical topic in statistical learning theory [10 optimally regularized noisy linear regression on features with power-law co-variance spectrum have been provided. Interestingly, it has been shown that such optimal rates can be obtained in practice by stochastic gradient descent, without explicit regularization, with single-pass [7 or multi-pass [8] algorithms, as well as by randomized algorithms [18]. Closed-fort bounds for the prediction error have been provided in a number of worst-case analyses 19). We show how the decay rates given in the present paper can also be alternatively deduced therefrom in Appendix B
13 In this classical setting, decay exponents for
The recent line of work on the noiseless setting includes contributions from statistical learning theory 19, 18] and statistical physics [12 This much more recent second line of work proved decay rates for a given, constant regularization. An example of noise-induced crossover furthermore mentioned in 19] The interplay between noisy and noiseless regimes has also been investigated in the related Gaussian Process literature (20).
The study of ridge regression with Gaussian design is also a classical topic. Ref. 21 considered model in which the covariates are isotropic Gaussian in RP, and computed the exact asymptotic generalization error in the high- nigh-dimensional asymptotic regime p. n + oo with dimension to-sample- arbitrary co-variances [22] 23 using
complexity ratio p/n fixed. This result was generalised fundamental results from random matrix theory [24]. Non-asymptotic rates of convergence for related problems were given in (25]. Previous results also existed in the statistical physics literature, e.g. 29). Gaussian models for regression have seen surge of popularity recently, and have been used in particular study verrparamettiizatoon and the double-descent phenomenon, e.g. in [30
2 Setting
Consider a data set D {a"', "y".."") )/=1 with independent samples from a probability measure P on X' x Y, where X' C RRd the input and y C IR the response space. Let K be a kernel and H denote its associated reproducing kernel Hilbert space (RKHS). Kernel ridge regression (KRR) corresponds to the following non non-parametric minimisation problem:
min FEH VL
E(s(tt) - )1)) + 111/112
where I|x is the norm associated with the scalar product in H. and À 2 is the regularisation. The convenience of KRR is that it admits dual representation in terms of standard parametric problem. of T.2()))
Indeed, the kernel K can be diagonalized in an orthonormal basis
J Pa (dx' (dd') (1, (x')) " (x)
where {n are the corresponding negatiegative) kernel eigenvalues and ps is the marginal distribution over X. It is convenient to define the re-scaled basis of kernel features (h((x) = (n)ok(()) (z) and to work in matrix notation in feature space: define Φ(x) = {o)(x)) (with p possibly infinite)
(x) = 1d
Exre, [+())(()
1p, Exiop, ((<x2'))(=')1 = EΦ(x), (3)
2

---

where Σ = Exsp, [ - diag(m .2...., 7p) is the features co- co-variance (a diagonal
operator in feature space). With this notation, we can rewrite eq. (4) in feature space as a standard parametric problem for the following empirical risk:
Ru(w)) =
Σ 1=1
(b(")) - y²r) + AwTwr w.
(4)
Our main results concern the typical averaged performance of the KRR estimator, measured by the typical prediction (out-of-sample) error
'g ED (x.))))))) -y)²,
where the first average is over the data = { 3/²) and the second over a fresh sample (x, y) ~ p. In what follows we assume the labels y E y' were generated. up to an independent additive Gaussian noise with variance o², by a target function f* (not necessarily belonging H)):
yd d (* + (0,
and we denote by 0* the coefficients of the target function in the features basis f*(x) = ( we will characterize below, whether the target function f belongs or not to H. depends on the relative decay coefficients 0* with respect to the cigenvalues of the kernel. We often refer to 0* as the teacher. While the present results and discussion are provided for additive gaussian noise for simplicity, our method are not restricted to this particular form of noise, and more complete extension of the results for other noise settings is left for future work. We are then interested in the evolution of the excess error Eg - o² as the number of samples n is increased.
T As
Capacity and source coefficients - Motivated by the discussion above, we focus on ridge
regression in an infinite dimensional (p + 30) space H. with Gaussian design ul def (xx")) d (( Σ) with (without loss of generality) diagonal co-variance Σ = diag(1) (7.......... We expect however the results of this manuscript be universal for a large class of distributions beyond the Gaussian one. In particular, we anticipate that the gaussianity assumption should be amenable to being relaxed to sabbsiasssanss
44 or even any concentrated distribution
45 46
Following the statistical learning terminology. we introduce two parameters a > 1, 2 0, herefrom referred to as the capacity and source conditions (14), to parametrize the difficulty of the target function and the learning capacity of the kernel
+ oC,
|| 1| <0.
As in 9 12 components t have exactly power-law form satisfying some source/capacity conditions:
we consider the particular case where both the spectrum Σ and the teacher
1+((2-1)
M
While this follows the standard naming convention, it is useful translate these notations to the ones used in others works, and we give a dictionary in Appendix B Table For instance, a is b and r is (a 1)/2b in [13], while the change of variable a as//d and r (aT/as, d)/2 allows to recover the notation from 12).. The power law ansatz (8) is empirically observed to be a rather good approximation for some real simple datasets and kernels, see Fig- Appendix C The parameters o, introduced in ( control the complexity of the data and of the teacher respectively. A large a can be seen as characterizing an effectively low dimensional (and therefore easy fit) data distribution. By the same token, a large signals good alignment of the teacher with the important directions of the data co-variance, and therefore an priori simple learning task. The regularization À is allowed to vary with n according to power-law X = n- This very general form allows us to encompass both the zero regularization case (corresponding
= oo) and the case where À X optimized, with some optimal decay rate f* Note also that this power law form implies that À is assumed positive. While this is indeed the assumption of [10 14 with which we intend to make contact, [37 have shown that the optimal À may in some settings may be negative. Some numerical experiments suggest that removing the positivity constraint on À while optimizing does not affect the results presented in this manuscript. A more detailed investigation is left to future work.
3

---

Zaminir. 1)
2/minír,
d"w
Figure 1: Different decays for the excess generalization error 'g - x² for different values of n and different decays of the regularization crossover line, separating the effectively noiseless regime (green and
n n- at given noise variance o. The red solid line
represents the blue) on its left from effectively noisy regime (red and orange) on its right. Any KRR experiment at fixed regularization decay & (corresponding to drawing horizontal line at ordinate é) crosses the crossover line if f a/(1 + 2amin((; 1)). The corresponding learning curve will accordingly exhibit crossover from fast decay (noiseless regime) to slow decay (noisy regime).
3 Main results
Depending on the regularization decay strength É, capacity a, source and noise variance o², four regimes can be observed. The derivation of these decays from the asymptotic solution of the Gaussian design problem is sketched in Section and detailed in Appendix A and here we concentrate on the key results. The different observable decays for the excess error 6g a² are summarized in Fig. and are given by:
l 2 a (weak regularization X = n n
Omax - 0² === = 0 maxx (a² n 2comin(r:)))
The excess error transitions from fast decay 2amin((, 1) (green region in Fig. and green dashed line Fig. 2 to plateau (red region Fig. [ and red dashed line in Fig. 2 with no decay as
increases. This corresponds to crossover from the green region to the red region in the phase
diagram Fig. [
If f < (strong regularization x= = n
cg 02 0max
maxx (02, (n2 1221minn(r)11)-- t-o
(10)
The excess error transitions from a fast decay 26min(r, 1) (blue region in Fig. to a slower decay is increased and the effect of the additive noise kicks in, Fig. 3 The crossover disappears for too slow decays & a/(1 /1 + 2omin 1)), as the regularization
(a f)/a (orange region in Fig. [
A is ways sufficiently large completely mitigate the effect of the noise. This corresponds the max in (IO) being realized by its second argument for all n.
Given these four different regimes as depicted in Fig. D one may wonder about the optimal learning solution when the regularization is fine tuned to its best value. To answer this question, we further define the asymptotically optimal regularization decay l as the value leading fastest decay of the typical excess eπror Eg a. We find that two different optimal rates exist, depending on the quantity of data available.
If n ni amintr.)) any 8t (a, 00) yields excess error decay
9 ~ 20min((,1)
(11)
n2 max (2, amiin
. nf
Eg 0² 2amint)))))
X 142mmin(
(12)

---

r=
10-1
10a
10-4
10:2
10'4
2=0.0
g=0.0
10-4
0.032
0= 0.01
10
10-4 30 20'
10 10
Figure 2: Kernel ridge regression on synthetic data sets with capacity a and source coefficient r, with no regularization À 0. Solid lines correspond the theoretical prediction of eq. (14) using the GCM package associated with (25 Points are simulations conducted using the python scikit- Kernel Ri Rigg package 477. where the feature space dimension has been cut off p 10 for the simulations, and to 10 for the theoretical curves. Dashed lines represent the slopes predicted by eq. (9). with the color (red and green) in correspondence the regime from Fig. [ The code used to generate this figure is available at wttts//gghhooocmm////Piiiccccene
The optimal decay for the excess error cg - thus transitions from fast decay 2omin(r, 1) when < ni corresponding to, effectively, the optimal rates expected in "noiseless" situation to slower decay 2amin((, (1 + 2amin(r; 1)) when n > nz corresponding to the classical "noisy" optimal rate, depicted with the purple point in Fig. This illustrated in Fig. where the two rates are observed in succession for the same data as the number of points is increased.
We can now finally clarify the apparent discrepancy in the recent literature discussed in the introduc- tion. The exponent recently reported in [3] actually corresponds to the "noiseless" regime. In contrast, the rate described in (12) is the classical result (10) for the non-saturated case < 1 for generic data. We see here that the same rate is also achieved with Gaussian design, and that there differences between fixed and Gaussian design long the capacity and source condition are matching. We unveiled, however, the existence two possible sets of optimal rate exponents depending the number of data samples.
setups (effectively non-regularized KRR 9 effectively regularized KRR 10 or optimally regularized KRR I1I. 12 can therefore exhibit crossover from an effectively noiseless regime (green or blue Fig. to an effectively noisy regime (red, orange in Fig. depending on the quantity of data available. We stress that while the noise is indeed present the green and blue "noiseless" regimes, its presence is effectively not felt, and noiseless rates are observed. In fact, the noise is small, one will not observed the classical noisy rates unless astronomical amount of data available. This can be intuitively understood as follows: for small sample size n, low-variance dimensions used overfit the noise, while the spiked subspace of large-variance variance dimensions well fitted. noiseless regions, the excess eтror is thus characterized by a fast decay. This phenomenon, where the noise variance is diluted over the dimensions of lesser importance, is connected to the benign overfitting discussed by (38] and [44]. Benign overfitting is possible due the decaying structure of the co-variance spectrum
As samples accessed, further decrease of the excess error requires good generalization also over the low-variance subspace, and the overfitting of the noise results slower decay.
While our analysis is for the optimal full-batch learning, we note that a similar crossover in the case of SGD in the effectively negulagulr case (from green to red) has been discussed in 9 48
Note that the rates derived in these two works for SGD are slower than the green decay rate (9) for full-batch learning. It would be interesting to further explore how SGD can behave in the different regimes discussed here.
When À = -f for prefactor Å that is allowed to be very small, regalarization-immuuee crossover, similar to the one reported in [13), can also be observed on top of the noise-induced crossover which is the focus of the present work. This setting is detailed in Appendix.
5

---

a=3,0, D.1667
a=
10A
10:4
10
10
10
6.0.8
10
0-
10
0-0000
0.01
10
10-11
Figure 3: Kernel ridge regression on synthetic data sets with capacity a and source coefficient r, with regularization À n n- Solid lines correspond the theoretical prediction of eq. (14) using the GCM package associated with [25] Points are simulations conducted using the python scikit- Kernel Ride package [47] where the feature space dimension has been cut off p 10* for the simulations, and to 10S for the theoretical curves. Dashed lines represent the slopes predicted by eq. (TO), with the color (blue and orange) in correspondence the regime from Fig. [1 The code used to generate this figure is available at http://gihiii.oomm////iiii//llet
Sketch of the derivation
We provide this section the main ideas underlying the derivation of the main results exposed in section 3 and summarized in Fig. 1 A more detailed discussion is presented in Appendix A
Closed-fore formm solution for Gaussian design The starting point to consider the closed-form, rigorous solution of the risk of ridge regression with Gaussian data of arbitrary co-variance in the high-dimensional asymptotic regime [23] 39). We shall use here the equivalent notations of (25), who have the advantage of having rigorous asymptotic rates guarantees. Within this framework. we shall sketch how the crossover phenomena (9) (I) and (12), which are the main contribution of this paper, can be derived. With high probability when n. are large the excess prediction error is expressed as
Cg
2² p 2m* 9":
(13)
with 8+1 E8" and (m"
9²") (m=,9"
are the unique fixed- fixed-points the following self-consistedd equations:
Gn n?m
q = Σ pV
V
[nd+pVna)
V
(14)
pto 2m-o²
o
nA pVVp
P (1+V)²
ndtpVm
We recall the reader that À > is the regularisation strength and (л 12 are the kernel eigenvalues. The next step is thus to insert the power-law decay (8) for the eigenvalues into (14). and to take the limit n. P co. We note, however, that this last step is completely justified rigorously. Indeed, (23) assumes p/n O(1) as n. + oo while here we first send oo and then take the large limit, thus working effectively with p/n + O. While the non-asymptotic rates guarantees of (25] are reassuring in this respect, finer control of the limit would be needed for a fully rigorous justification; perhaps using the tights non-asymptotic bounds from 44] Nevertheless, we observed in our experiments that the agreement between theory and numerical simulations for the the excess prediction error (5) perfect (see Figs. 2 and In the large limit, one can finally close the equation for the excess prediction error into
1 1ro
k- 20
(1na k-a
[1 [ 1
Eg
(15)
k-
1
k-
[+nz kk-a2
with being a solution of
(2) (2) 1-1
00
dr 11) 1 z
2 ~ n2 +
(16)
n

---

d 1.5, 1=1,0 2
8 2.5, r- 0.6, F"
10a
10"
10
10
10
10"
10
10
10-3
10-41
o=0.0 0.0
10-11
0=0.0
10:14
0-
10:11
om 1.0
1.0
10
10
10-2
10
10:3
10
10-1
10a 102
10
10a 10a 10a
Figure 4: Kernel ridge regression on synthetic data sets with capacity a and source coefficient r. The regularization À is chosen the one minimizing the theoretical prediction for the excess generalization error, deduced from eq. [14) using the GCM package associated with [25]. Solid lines correspond the theoretical prediction of eq. (14) Points simulations conducted with the python scikit-leari KernelRidge package [47] where the feature space dimension has been cut off to p 10 for the simulations, and 10S for the theoretical curves. In simulations, the best X was determined using python scikit-lears Gri GridSecccCCV cross validation package [47]. Note that because cross validation is not adapted small training sets, few discrepancies smaller n. Dashed lines represent the slopes predicted by theory, with the colors in correspondence the regimes in Fig. [ purple for the purple point in Fig. [ Top: excess error. Bottom: optimal
observed for
X Note the noiseless case has X O. The code used to generate this figure is available at Saapshubb.comm/ePPPiS//eeeeee
The detailed derivation is provided in Appendix A, We note that this equation was observed with heuristic arguments from statistical physics (using the non-rigorous cavity method) 44
The different regimes of excess generalization error rates discussed Section 3 are derived from this seff-consistent equation. Note that the excess error (15) decomposes respectively accounting for the sample variance and the noise-induced variance. In contrast to typical bias-variance decomposition, the effect of the bias introduced in the task for non-vanishing is subsumed in both terms.
sum of two contributions,
Derivation of the four regimes- - If the second term in (66) dominates, then 2 ~ n 1- which is self consistent if é 2 a. This the effectively von-regularized regime, where the regularization is not sensed, and corresponds to the green and red regimes in the phase diagram in Fig. [ This scaling of can then be used estimate the asymptotic behaviour of the sample and noise induced variance in the decomposition on the excess eтror
15) yielding
( 2cmiin6:1)) +
(17)
which can be rewritten more compactly as 9 Therefore, for small sample sizes the sample variance drives the decay the excess prediction error, while for larger samples sizes the noise variance dominates and causes the error to plateau. The crossover happens when both variance terms in [1 are balanced, around
(18)
which corresponds to the vertical part of the crossover line in Fig.
7

---

MNIST. XXX x) 1001000000 P.
Fashion MNISS, K0s,
109
0.0
10-1_
10
d- 0.5
ora 1.0
107 10a 10a 10* 10
10a
10
Figure 5: Excess error for MNIST odd versus even (above) and Fashion MNIST t-shirt versus coat (below) with labels corrupted by noise of variance o². The kernel used indicated in the title. Solid lines with points come from numerical experiments with zero regularization. Dashed lines are the slopes -ar (as r < 1) or O, predicted by the theory from the empirical values a, r measured from the Gram matrix spectrum and the teacher for each data set, see Table [ Colors of the dashed lines (green & red) indicate the regimes Fig. T The code used to generate this figure is available at hatp////boooommeeeee/ccceceeeeie
If the first term n. dominates in (16), then ~ nd, which is consistent provided that / < a. This the effectively regularized regime (blue, orange regions in Fig. T. The two variances in (15) are found to asymptotically behave like
Eg = (((nnnnnn(r)))) + O (n"===))
(19)
which can be rewritten more compactly as (1O). If the decay of the noise variance term (a- 1oe-8p f)/a a is faster than the 26min(r; 1) decay of the sample variance term, then the latter always dominates and no crossover is observed. This is the case for & < a/(1 + 22mmin(r, 1)). J on the contrary the decay
of the noise variance term is the slowest, then this term dominates larger n, with a crossover when both terms in 19) are balanced, around
(1 2mmia((r.1)
(20)
Eqs. (17 and 19 respectively equivalent ()) and (TO), and completely define the four regimes
observable in Fig. Equations (20) and (18) give the expression for the crossover line in Fig.
Asymptotically optimal regularization
Determining the asymptotically optimal t' is matter of finding the l leading to fastest excess error decay. We focus on the far left part and the far right part of the phase diagram Fig. [
In the n > nš maxx(2 (mmnnr limit where the crossover line confounds itself with its E = a/(1 + 2omin(r, 1)) asymptot, this is tantamount to solving the maximization problem
E- = argmax
2fmin(r, 1)Aocee, 2amin
(mmmmi)))) <t<a + 0 last)
(21)
a
which admits as solution 12). In the n < nj 2 amintr..1 range, the maximization of the excess error decay reads
argmax (26min(r, 1)losesaa + 2amin(r; 1)llace)
(22)
and admits as solution
5 Illustration on simple real data sets
In this section we show that the derived decay rates can indeed be observed in real data sets with labels artificially corrupted by additive Gaussian noise. For real data, the decay model in eq. (8) is idealized, and in practice there is firm reason expect power-law decay. However, we do find

---

MNIST. Rtx. x') (1+ X....
MNIST, xix,x-= TP-TE
0=1.0
1.0
3.0
30*
3.00
2x-0-1
10-1
10a
10a
100
Fashion MNIST, ROX, x')
10 (xx,x))
Superconductivity, Kix, = 44
am 0.0
om 0.0
0.5
109
0.5
50-10-2
10-1
4x10--
3x11-1
16A
10
10a
10
18P
10
Figure 6: Excess error for MNIST odd versus even, and Fashion MNIST t-shirt versus coat, and the critical temperature regression. The kernel used is indicated in the title. Solid lines with dots come from numerical experiments with the regularization optimized using the python scikit t- t-learn GridSear chCV package [47). Dashed lines are the slopes predicted by the theory, from the empirical values of r measured from the Gram matrix spectrum and the teacher for each data set, see Table I Colors of the dashed lines indicate the regime Fig. [T. The code used to generate this figure is available at
that for some of the data sets and kernels we investigated, the power law fit is reasonable and can be used to estimate the exponents a and r, see Appendix for details. For those cases, we compare the theoretically predicted exponents, eqs. (9) (TO). (II and (12) with the empirically measured learning curve, and obtain a very good agreement. We stress that the decay rates are not obtained by fitting the learning curves, but rather by fitting the exponents and from the data. We also observe the crossover from the noiseless (blue, green in Fig. (1) to the noisy (orange, red in Fig. [ regime given by the theory. Here we illustrate this with the learning curves for the following three data sets:
MNIST even versus odd, a data set of 7 x 10t 28 x 28 images of handwritten digits. Even (odd) digits were assigned label y 1+ + oN 1) (y- = -11 + aN (0. 1)).
Fashion MNIST t-shirts versus coats, a data set of 14702 28 x 28 images of clothes from an online shopping platform [00]. T-shirts (coats) were assigned label y = 1+ aN (0, 1) (y = -11 aN((,, 1)). Superconductivity [51]+ a data set of 81 attributes of 21263 superconducting materials. The target y corresponds to the critical temperature of the material, corrupted by additive Gaussian noise.
Learning curves are illustrated for a radial basis function (RBF) kernel K ((x,x') = -- 211e-=='11 with
parameter 7 10- and degree 5 polynomial kernel K(x, x²) (1+ 7'x, with parameter
10-3 3 In Fig. 5 the regularization À was set to 0, while in Fig. 6 A was optimized for each sample size n using the python scikit-lean Gr GridSearchCV package 47). KRR was carried out using the scikit-learr KernelRidgs package [7). The values of a, r were independently measured (see Appendix () for each data set, and the estimated values summarized
Table From these values the theoretical decays (9. (I] and (12) were computed, and compared with the simulations with very good agreement. Since for real data the power-law form (8) does not exactly hold (see Fig. in the appendix), the estimates for r slightly vary depending on how the plwer-law is fitted. The precise procedure employed described in Appendix [ Overall this variability does not hurt the good agreement with the simulated learning curves in Fig. Jand 6

---

Dataset
Kernel
Fashion MNIST
K(x, (1 (,, ((x,x') (1+10- (x,)'))
1.3
0.13
MNIST
1.2
0.15
MNIST
(xr,r') -exp= (:tp==")=x(p1001101
1 12)2)
1.65
0.097
Superconductivity
K(x,x') 1xp x 112))
2.7
0.046
Table I:
Values of the source and capacity coefficients 7 as estimated from the data sets. The details on the estimation procedure can be found in Appendix
When À 0 (Fig. 5) the characteristic plateau for large label noises is observed for both MNIST' & Fashion MNIST. For polynomial kernel regression on Fashion MNIST (Fig-5) right), the crossover between noiseless (slope 20r
1) and noisy (slope 0) regimes is apparent on the same learning curve at noise levels a = 0.5, 1. For MNIST, the a = 0 (a = 1) curve is in the noiseless (noisy) regime for larger n, while at intermediary noise a 0.5, and small for 1, the curve is in the crossover regime between noiseless and noisy, consequently displaying in-between decay. Our results for the decays for 0 agree with simulations for RBF regression MNIST provided in [[2]
For optimal regularization À X (Fig. 6 as the measured r < 1 we have exponents -2ra for the noiseless regime and -2ra/ 2ra) for noisy. Since the measured value of 2ra is rather small the difference between the two rates is less prominent. Nevertheless, seems that in our experiments the noisy regime observed for polynomial and RBF kernels MNIST and 0.5, 1. For Superconductivity. the green and purple decay have close values and difficult to clearly identify the regime. For Fashion MNIST only the noiseless rate is observable in the considered noise range and sample range.
Conclusion To conclude, we unify hitherto disparate lines of work, and give comprehensive study of observable regimes, along the associated decay rates for the excess error, for kernel ridge regression with features having power-law co-variance spectrum. We show that the effect of the noise only kicks in at larger sample complexity, meaning, in particular, that the KRR transitions from noiseless regime with fast error decay to a noisy regime with slower decay. This crossover is shown to happen for zero, decaying and optimized regularization, and is observed variety of real data sets corrupted with label noise.
Due to the theoretical nature of this paper, no negative societal impact of this work is anticipated.
Acknowledgments- - warmly thank Loucas Pillaud- Vivien for his insights, and for his help in navigating the literature kernel ridge regression. We also thank Volkan Cevher, Cedric Gerbelot and Matthieu Wyart for useful discussions. We acknowledge funding from the ERC under the European Union's 's Horizon 2020 Research and Innovation Programme Grant Agreement 14600-SMMLL,, and from the French National Research Agency grants ANR-17-CE23-0023-0 PAIL.
References
[1] È. A. Nadaraja. On a regression estimate. Teor. Verojatnost. i Primenen. 9:157-159, 1964.
[2] Geoffrey S. Watson. Smooth regression analysis. Sankhyā: The Indian Journal of Statistics, Series A (1961-2002), 26(4):359-37) 372, 1964.
[3] Radford M. Neal. Priors for Infinite Networks, pages 29-53. Springer New York, New York,
NY, 1996.
[4] Christopher K. I. Williams. Computing with infinite networks. In Proceedings of the 9th International Conference on Neural Information Processing Systems, NIPS*96, page 295-301. Cambridge, MA, USA, 1996. MIT Press.
[5] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 8571-8580, 2018
[6] Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S. Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as Gaussian processes, 2018. ICLR 2018, arXiv:1711.00165
10

---

[7] Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable program- ming. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buse Buc. E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[8] Loucas Pillaud-Vivien, Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes. In Advances in Neural Information Processing Systems, volume 31. pages 8114-8124, 2018.
[9] Raphael Berthier, F. Bach, and P. Gaillard. Tight nonparametric convergence rates for stochastic gradient descent under the noiseless linear model. ArXiv, abs/2006.08812, 2020.
[10] A. Caponnetto and E. D. Vito. Fast rates for regularized least-squares algorithm. In 2005.
[11] Ingo Steinwart, Don R Hush, Clint Scovel, et al. Optimal rates for regularized least squares regression. In COLT, pages 79-93, 2009.
[12] Stefano Spigler, Mario Geiger, and Matthieu Wyart. Asymptotic learning curves of kernel methods: empirical data versus teacher-student paradigm. Journal of Statistical Mechanics: Theory and Experiment, (020((2):1 12000,, 2020.
[13] Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning, pages 1024-1034. PMLR, 2020.
[14] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-36$ 2007.
[15] Simon Fischer and Ingo Steinwart. Sobolev norm learning rates for regularized least-squares algorithms. Journal of Machine Learning Research, 21 (205):11338 2020.
[16] Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging.
SIAM journal on control and optimization, 30(4):838-88) 1992.
[17] Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. Iiley-Interscience, 1983.
[18] Kwang-Sung Jun, Ashok Cutkosky, and Francesco Orabona. Kernel truncated randomized ridge regression: Optimal rates and low noise acceleration. In NeurlPS, 2019.
[19] Junhong Lin, Alessandro Rudi, L. Rosasco, and Cevher. Optimal rates for spectral algorithms with least-squares regression over hilbert spaces. Applied and Computational Harmonic Analysis, 48:868-88888 888886888000.8 2018.
[20] M. Kanagawa, Hennig, D. Sejdinovic, and B. K. Sriperumbudur. Gaussian processes and kernel methods: A review on connections and equivalences. Arxiv e-prints, N.Xiv:1805.0884555
[sL, 2018.
[21] Lee H Dicker et al. Ridge regression and asymptotic minimax estimation over spheres of growing dimension. Bernoulli, 22(1): 2016.
[22] Daniel Hsu, Sham M. Kakade, and Tong Zhang, Random design analysis of ridge regression. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, Proceedings of the 25th Anmual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pages 9.1-9.24, Edinburgh, Scotland, 25-27 Jun 2012. JMLR Workshop and Conference Proceedings.
[23] Edgar Dobriban and Stefan Wager. High-dimensionall asymptotics of prediction: Ridge regres- sion and classification. The Annals of Statistics, 46(1):247-279 2018.
[24] Olivier Ledoit and Sandrine Péché. Eigenvectors of some large sample covariance matrix ensembles. Probability Theory and Related Fields, 151(1):233-264, 2011.
[25] Bruno Loureiro, Cédric Gerbelot, Hugo Cui, Sebastian Goldt, F. Krzakala, M. Mézard, and Lenka Zdeborová. Capturing the learning curves of generic features maps for realistic data sets with teacher-student model. ArXiv, abs/2102.08127, 2021.
[26] Rainer Dietrich, Manfred Opper, and Haim Sompolinsky. Statistical mechanics of support vector networks. Physical review letters, 82(14):2975, 1999.
[27] Manfred Opper and Wolfgang Kinzel. Statistical mechanics of generalization. In Models of neural networks III, pages 151-209 Springer, 1996.
11

---

[28] M. Opper and R. Urbanczik. Universal learning curves of support vector machines. Phys. Rev. Lett., 86:4410-4413, May 2001.
[29] Yoshiyuki Kabashima. Inference from correlated patterns: a unified theory for perceptron learning and linear vector channels. In Journal of Physics: Conference Series, volume 95, page 012001. IOP Publishing, 2008.
[30] Madhu Advani, Andrew M Saxe, and Haim Sompolinsky. High-dimensional dynamics of generalization error in neural networks. Neural Networks, 132:428-444 2020.
[31] Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4):1 2020.
[32] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint arXiv:1903.08855 2019.
[33] Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv preprint 108555590, 2019.
[34] F. Gerace, B. Loureiro, F. Krzakala, M. Mézard, and L. Zdeborová. Generalisation error in learning with random features and the hidden manifold model. In 37th International Conference on Machine Learning, 2020.
[35] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Limitations of lazy training of two-layers neural network. In H. Wallach, H. Larochelle, A. Beygelzimer, d'lché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32, pages 9111-9121, 2019.
[36] Dmitry Kobak, Jonathan Lomond, and Benoit Sanchez. The optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization, Journal of Machine Learning Research, 21(169):1-16, 2020.
[37] Denny Wu and Ji Xu. On the optimal weighted &2 regularization in overparameterized linear regression. In Advances in Neural Information Processing Systems, volume 33, 2020.
[38] P. Bartlett, Philip M. Long, G. Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117:30063 30070, 2020.
[39] Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco. Asymptotics of ridge (less) regression under general source condition. In International Conference on Artificial Intelligence and Statistics, pages 3889-3897. PMLR, 2021.
[40] Zhenyu Liao, Romain Couillet, and Michael W Mahoney. A random matrix analysis of random fourier features: beyond the gaussian kernel, precise phase transition, and the corresponding double descent. In Advances Neural Information Processing Systems, volume 33, 2020.
[41] Arthur Jacot, Berfin Şimşek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Kernel alignment risk estimator: Risk prediction from training data. arXiv preprint arXiv:2006.09799 2020.
[42] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods? In Advances in Neural Information Processing Systems, volume 33, 2020.
[43] Fanghui Liu, Zhenyu Liao, and Johan AK Suykens. Kernel regression in high dimension: Refined analysis beyond double descent. arXiv preprint arXiv:2010.02681, 2020.
[44] Alexander Tsigler and P. Bartlett. Benign overfitting in ridge regression. arXiv preprint 1rXiv:2009.14286 2020.
[45] Michel Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de l'Institut des Hautes Études Scientifiques, 81:73-205, 1994.
[46] Cosme Louart, Zhenyu Liao, and Romain Couillet. A random matrix approach to neural networks. ArXiv, abs/ 702.04992.. 2017.
[47] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Duchesnay. Seikit-learn: Machine learning Python, Journal of Machine Learning Research, 12:2825-2834 201
12

---

[48] Aditya Varre, Loucas Pillaud- -iivien, and Nicolas Flammarion. Last iterate convergence of sgd for least-squares in the interpolation regime. ArXiv, abs/2102.03183, 2021.
[49] Abdulkadir Canatar, B. Bordelon, and C. Pehlevan. Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks. Nature Commu- nications, 12: 12:1-12, 2021.
[50] H. Xiao, K. Rasul, and Roland Vollgraf. Fashion- novel image dataset for benchmarking machine learning algorithms. ArXiv, abs/ 00w000770077777 2017.
[51] Kam Hamidieh. data-driven statistical model for predicting the critical temperature of superconductor. Computational Materials Science, 154:346-354, 2018.
[52] Noureddine El Karoui. Asymptotic behavior of unregularized and ridge-regularized high- dimensional robust regression estimators rigorous results, 2013.
[53] Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise enror analysis of regularized m-estimators in high dimensions. IEEE Transactions on Information Theory, 64(8):5592-566
2018.
13


Reviews:
[{"review_id": "lyiqj1-3WzU", "reviewer": "Reviewer_Z2bD", "summary": "The paper proposes an asymptotic analysis of the excess generalization error of kernel ridge regression under a gaussian design. In summary, the authors identify four regimes of functioning of kernel ridge regression as a function of the number of samples and the regularization parameter. These regimes allow unifying the theory of kernel ridge regression which had been performed previously in extreme cases (without noise, with noise but optimal regularization parameter).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "** Overall review **\n\n1-Strong Points: The insights drawn are quite interesting, seem quite valid empirically on synthetic data, and allows for unifying the kernel ridge regression methods. The article is well written\n\n2-Weak Points: The experiments in real data are not so convincing. It consists of self-added noise on the existing dataset (MNIST) which is far to be realistic. The question is how the theory can actually help to understand the excess generalization error of kernel ridge regression applied on existing datasets (which are already noisy by being collected manually, by humans, ...). Adding Gaussian noise is the same as creating synthetic data. The authors should also detail/motivate more the power-law decay assumption (should it model realistic features extracted from real dataset? Some real-world examples (figures of eigenvalues of the features co-variance) where this happens would also be interesting.)\n\n** Detailed review **\n\n1-Line 28: ... regression and are --> ... regression are\n\n2-Line 59: a reference is missing\n\n3-Line 96/97 Why is it important to assume this power-law decay (theoretical traceability, insights from experiments?). It should be good to precise.\n\n4-In the paragraph Capacity and source coefficients, the authors should try to give a better interpretation, i.e., what does equation (7) mean in plain English?\n\n5- The authors should try to make as possible their figure reproducible. For example, in Figure 3, it is impossible for a practitioner to obtain the figure (which kernel has been used for example, ...)\n\n6-Line 177: for the the ---> for the\n\n7-In figure 5, there is a reference for figures above and below.\n\n8-The real data experiments on MNIST and Fashion MNIST are quite toyed examples and not really real data experiments. What is the motivation to add noise to the labels?\n\n9- It would be better to make some connection between these predictions and the theoretical and exact large dimensional analysis of kernel ridge regression from Random Matrix Theory (RMT)? (How do they differ? Is the prediction of RMT be recovered?). There is a discussion in the last paragraph of 'Related work' but never discussed afterward in the main results.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations of the works are put in the work. For suggestions, the authors should consider trying to do some real-world experiments that are not played, clarify more specifically the link with exact (and not the order of magnitude as a function of sample size) asymptotic performed in RMT or at least what is the further insights with respect to reference [21] for example.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hr"}, "extra_text": {}}, {"review_id": "gr7T7YB5_eP", "reviewer": "Reviewer_Jd5V", "summary": "This submission studies the asymptotic generalization error of kernel ridge regression (KRR) under Gaussian design with specific eigen-decay conditions. Major contributions include (i) specifying the decay rate of the generalization error based on the noise level and source / capacity conditions of the kernel / target function, (ii) identifying different regimes of learning, and (iii) deciding the optimal ridge regularization. Theoretical results are verified in various experiments.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strength\n\nThe excess risk of kernel regression has been extensively studied in the nonparametric regression literature. This paper provides a somewhat unifying perspective, which takes into account the noise level, different eigen-decay conditions and regularization strength.   \nThe analysis builds upon recently derived precise asymptotics for ridge regression under general feature covariance and target function, and it is nice to see that these elusive asymptotic formulas can be used to provide quantitative understanding of classical machine learning models (instead of only generating good-looking double descent figures). To my knowledge, the different regimes of learning is an interesting contribution, and the matching empirical results on realistic datasets demonstrate the practical relevance of the theory. \n\n## Weakness\n\n1. The considered model is a bit idealized. I initially thought that the Gaussian design refers to the input features (as in [41] in the reference list), but instead it is directly assumed that the kernel features are Gaussian. It might be a good idea to comment on this gap, and whether the findings can be translated to the other setting via Taylor expansion on the kernel matrix. \n\n2. Related to the previous point, due to the assumed Gaussian features, it seems that the generalization error of the studied estimator in the proportional limit has already been derived in prior works (e.g., [35][37]). The authors should comment on whether this is the case and the improvement over previous results. \nFor example, prior works in the proportional scaling usually assumed the population eigenvalues to be bounded away from 0, which cannot capture the power law decay. Would this be an advantage of the new analysis?\n\n3. As the authors noted, the derivation of the excess risk rate is not completely rigorous due to the order of limits taken. While the empirical results are reassuring, would it be possible for certain terms that vanish in the proportional limit (and thus omitted in the asymptotic formulas) to reappear and dominate the rate when $p/n\\to 0$?\n\n**Additional Comments and Questions**\n\n1. In the proportional limit, [35] showed that the optimal ridge regularization can be negative in the noiseless case under specific source conditions. Is it possible to observe similar phenomenon under the power-law eigen-decay setting? If not, what might be the reason for this difference?\n\n2. Is there an intuition of why the power-law decay is a good fit for MNIST? The decaying eigenvalues for the capacity condition seems reasonable, but I don't really know why the source condition also follows a similar decay. \n\n3. (minor) The reference [21] in Section 4 cannot handle the varying source condition due to the isotropic prior on the true coefficients. A more appropriate reference would be the general result of [35][37].  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2-3 hours. "}, "extra_text": {}}, {"review_id": "Qa83xkzh98a", "reviewer": "Reviewer_5R13", "summary": "The paper considers kernel ridge regression under the Gaussian design and derives decay rates of the excess generalization error under capacity and source conditions. The analysis reveals interesting phase transition phenomena in the noiseless and noisy regimes.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The presented decays rates of the excess generalization error of kernel ridge regression (KRR) under Gaussian design and the observed phase transition phenomena are of interest. The first result in (9) is the excess error of effectively non-regularized KRR, which transitions from a fast decay to a plateau with no decay as the sample size $n$ increases. The second result in (10) is the excess error of effectively regularized KRR, which transitions from a fast decay to a slower decay as $n$ increases. The results in (11) and (12) are the excess error of optimally regularized KRR, which transitions from a fast decay (optimal rate in noiseless regime) to a slower decay (optimal rate in noisy regime) as $n$ increases. The numerical experiments also verify their theoretical claims about the crossover from the noiseless to noisy regime. Overall, the paper is well written and the results are theoretically sound. It sheds light on how the decay rates of the excess error of KRR depend on the regularization decay strength, capacity, source, and noise variance. The Gaussian design is a rather strong condition for KRR, is it possible to remove this assumption in the future study?\n\nAfter Rebuttal\n\nI thank the authors for addressing my concerns.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "9hGewXSaGx5", "reviewer": "Reviewer_rxhv", "summary": "In this paper, the authors evaluate the excess error of Kernel Ridge Regression, in a unified manner by considering general settings for regularization and noise levels, as well as a power-law decay for the eigenvalues of feature covariance. The main results can be summarized in Figure 1, where one particularly observes the transitions between different regimes. Numerical results on real-world datasets such as MNIST, Fashion MNIST, and Superconductivity are also reported.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is in general well written and easy to follow, the transition from the noiseless to noisy values reported here is, to the best of my knowledge, characterized for the first time in the general setting. I believe this work is of general interest to the NeurIPS community.\n\nDetailed comments:\n* Page 2, \"Related work\" section: the reference is missing for \"the related Gaussian Process literature\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the possible limitations of their approach. This work is mainly theoretical and algorithmic and I do not see any possible negative societal impact.\n", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies asymptotic analysis of the excess generalization error of kernel ridge regression under a gaussian design. The authors identify four regimes of functioning of KRR as a function of the number of samples and the regularization parameter. These regimes allow unifying the theory of kernel ridge regression which had been performed previously in extreme cases. Numerical results on real-world datasets are also reported.

All the reviewers agree that the paper is well written, easy to follow and brings interesting theoretical insights. It’s pointed out that the paper provides `a missing point of view of asymptotic analysis of ridge regression of general interest to the ML` (reviewer `Z2bD`), `transition from the noiseless to noisy values reported here is, to the best of my knowledge, characterized for the first time in the general setting` (reviewer `rxhv`), `sheds light on how the decay rates of the excess error of KRR depend on the regularization decay strength, capacity, source, and noise variance` (reviewer `5R13`) and `different regimes of learning is an interesting contribution, and the matching empirical results on realistic datasets demonstrate the practical relevance of the theory` (reviewer `Jd5V`). Some of the limitations and concerns raised are addressed during the discussion period (authors promised to clarify limitations regarding the noise assumption and their potential robustness in the revision). In the end, all reviewers recommended for acceptance  (3 accepts, 1 weak accept). The AC believes this is a solid work that would be of interest to the broad NeurIPS audience. 

Decision: Accept (Poster)