Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime
Year: 2021

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.

heading: 1 Introduction
text: Kernel methods are among the most popular models in machine learning. Despite their relative simplicity, they define a powerful framework in which non-linear features can be exploited without leaving the realm of convex optimisation. Kernel methods in machine learning have a long and rich literature dating back to the 60s [1, 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-parametric optimisation problem, kernel methods can be mathematically understood as a standard parametric linear problem in a (possibly infinite) Hilbert space spanned by the kernel eigenvectors (a.k.a features). This dual picture fully characterizes the asymptotic performance of kernels in terms of a 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 in 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 [8, 9].
Rigorous optimal rates for the excess generalization error in kernel ridge regression and are wellknown since the seminal works of [10, 11]. However, recent interesting works [12, 13] 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 to a difference between typical and worse-case analysis [12]. 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 [12, 13] focused on noiseless data sets. This observation raises a number of questions: is there a connection between both sets of exponents? Are Gaussian design
35th Conference on Neural Information Processing Systems (NeurIPS 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 complexities)? 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 a unifying picture of the decay rates for the excess generalization error, along a 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 a 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 to the noisy regime also in a variety of KRR experiments on real data.
Related work — The analysis of decay rates for kernel methods and ridge regression is a classical topic in statistical learning theory [10, 11, 14, 15]. In this classical setting, decay exponents for 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 [16, 17] or multi-pass [8] algorithms, as well as by randomized algorithms [18]. Closed-form bounds for the prediction error have been provided in a number of worst-case analyses [18, 19]. We show how the decay rates given in the present paper can also be alternatively deduced therefrom in Appendix E.
The recent line of work on the noiseless setting includes contributions from statistical learning theory [9, 18] and statistical physics [12, 13]. This much more recent second line of work proved decay rates for a given, constant regularization. An example of noise-induced crossover is furthermore mentioned in [9]. 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 a model in which the covariates are isotropic Gaussian in Rp, and computed the exact asymptotic generalization error in the high-dimensional asymptotic regime p, n→∞ with dimension-to-samplecomplexity ratio p/n fixed. This result was generalised to arbitrary co-variances [22, 23] using fundamental results from random matrix theory [24]. Non-asymptotic rates of convergence for a related problems were given in [25]. Previous results also existed in the statistical physics literature, e.g. [26–29]. Gaussian models for regression have seen a surge of popularity recently, and have been used in particular to study over-parametrization and the double-descent phenomenon, e.g. in [30–43].

heading: 2 Setting
text: Consider a data set D = {xµ, yµ}nµ=1 with n independent samples from a probability measure ρ on X × Y , where X ⊂ Rd is the input and Y ⊂ R the response space. Let K be a kernel andH denote its associated reproducing kernel Hilbert space (RKHS). Kernel ridge regression (KRR) corresponds to the following non-parametric minimisation problem:
min f∈H
1
n n∑ µ=1 (f(xµ)− yµ)2 + λ||f ||2H. (1)
where || · ||H is the norm associated with the scalar product inH, and λ ≥ 0 is the regularisation. The convenience of KRR is that it admits a dual representation in terms of a standard parametric problem. Indeed, the kernel K can be diagonalized in an orthonormal basis {φk}∞k=1 of L2(X ):∫
X ρx(dx
′)K(x, x′)φk(x ′) = ηkφk(x) (2)
where {ηk}∞k=1 are the corresponding (non-negative) kernel eigenvalues and ρx is the marginal distribution over X . It is convenient to define the re-scaled basis of kernel features ψk(x) =√ ηkφk(x) and to work in matrix notation in feature space: define φ(x) ≡ {φk(x)}pk=1 (with p possibly infinite)
ψ(x) = Σ 1 2φ(x) Ex∼ρx
[ φ(x)φ(x)> ] = 1p , Ex′∼ρx [K(x, x′)φ(x′)] = Σφ(x) , (3)
where Σ ≡ Ex∼ρx [ ψ(x)ψ(x)> ] = diag(η1, η2, ..., ηp) is the features 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:
R̂n(w) = 1
n n∑ µ=1 ( w>ψ(xµ)− yµ )2 + λ w>w. (4)
Our main results concern the typical averaged performance of the KRR estimator, as measured by the typical prediction (out-of-sample) error
g = EDE(x,y)∼ρ(f̂(x)− y)2 , (5)
where the first average is over the data D = {xµ, yµ} and the second over a fresh sample (x, y) ∼ ρ. In what follows we assume the labels yµ ∈ Y were generated, up to an independent additive Gaussian noise with variance σ2, by a target function f? (not necessarily belonging toH):
yµ d = f?(xµ) + σN (0, 1), (6)
and we denote by θ? the coefficients of the target function in the features basis f?(x) = ψ(x)>θ?. As we will characterize below, whether the target function f? belongs or not toH depends on the relative decay coefficients θ? with respect to the eigenvalues of the kernel. We often refer to θ? 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 a 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 g − σ2 as the number of samples n is increased.
Capacity and source coefficients — Motivated by the discussion above, we focus on ridge regression in an infinite dimensional (p → ∞) space H with Gaussian design uµ def= ψ(xµ) d= N (0,Σ) with (without loss of generality) diagonal co-variance Σ = diag(η1, η2, ...). We expect however the results of this manuscript to 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 sub-gaussians [44] or even any concentrated distribution [45, 46].
Following the statistical learning terminology, we introduce two parameters α > 1, r ≥ 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
tr Σ 1 α <∞, ||Σ 12−rθ?||H <∞. (7)
As in [9, 12, 13, 23], we consider the particular case where both the spectrum of Σ and the teacher components θ?k have exactly a power-law form satisfying some source/capacity conditions :
ηk = k −α , θ?k = k − 1+α(2r−1)2 . (8)
While this follows the standard naming convention, it is useful to translate these notations to the ones used in others works, and we give a dictionary in Appendix B, Table 2. For instance, α is b and r is (a − 1)/2b in [13], while the change of variable α = αS/d and r = (αT /αS − 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. 7 in Appendix C. The parameters α, r introduced in (8) control the complexity of the data and of the teacher respectively. A large α can be seen as characterizing an effectively low dimensional (and therefore easy to fit) data distribution. By the same token, a large r signals a good alignment of the teacher with the important directions of the data co-variance, and therefore an a priori simple learning task. The regularization λ is allowed to vary with n according to a power-law λ = n−`. This very general form allows us to encompass both the zero regularization case (corresponding to ` =∞) and the case where λ = λ? is optimized, with some optimal decay rate `?. 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.

heading: 3 Main results
text: Depending on the regularization decay strength `, capacity α, source r and noise variance σ2, four regimes can be observed. The derivation of these decays from the asymptotic solution of the Gaussian design problem is sketched in Section 4 and detailed in Appendix A, and here we concentrate on the key results. The different observable decays for the excess error g − σ2 are summarized in Fig. 1, and are given by: • If ` ≥ α (weak regularization λ = n−`),
g − σ2 = O ( max ( σ2, n−2αmin(r,1) )) . (9)
The excess error transitions from a fast decay 2αmin(r, 1) (green region in Fig. 1 and green dashed line in Fig. 2) to a plateau (red region in Fig. 1 and red dashed line in Fig. 2) with no decay as n increases. This corresponds to a crossover from the green region to the red region in the phase diagram Fig. 1. • If ` ≤ α (strong regularization λ = n−`) ,
g − σ2 = O ( max ( σ2, n1−2`min(r,1)− ` α ) n `−α α ) . (10)
The excess error transitions from a fast decay 2`min(r, 1) (blue region in Fig. 1) to a slower decay (α− `)/α (orange region in Fig. 1) as n is increased and the effect of the additive noise kicks in, see Fig. 3. The crossover disappears for too slow decays l ≤ α/(1 + 2αmin(r, 1)), as the regularization λ is always sufficiently large to completely mitigate the effect of the noise. This corresponds to the max in (10) being realized by its second argument for all n.
Given these four different regimes as depicted in Fig. 1, 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 `? as the value leading to fastest decay of the typical excess error g − σ2. We find that two different optimal rates exist, depending on the quantity of data available. • If n n∗1 ≈ σ − 1 αmin(r,1) , any `? ∈ (α,∞) yields excess error decay
?g − σ2 ∼ n−2αmin(r,1) . (11)
• If n n∗2 ≈ σ −max(2, 1αmin(r,1) ),
?g − σ2 ∼ n 1 1+2αmin(r,1) −1 , λ? ∼ n− α 1+2αmin(r,1) . (12)
The optimal decay for the excess error ?g − σ2 thus transitions from a fast decay 2αmin(r, 1) when n n∗1 – corresponding to, effectively, the optimal rates expected in a "noiseless" situation – to a slower decay 2αmin(r, 1)/(1 + 2αmin(r, 1)) when n n∗2 corresponding to the classical "noisy" optimal rate, depicted with the purple point in Fig. 1. This is illustrated in Fig. 4 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 introduction. The exponent recently reported in [12, 13] actually corresponds to the "noiseless" regime. In contrast, the rate described in (12) is the classical result [10] for the non-saturated case r < 1 for generic data. We see here that the same rate is also achieved with Gaussian design, and that there are no differences between fixed and Gaussian design as long as the capacity and source condition are matching. We unveiled, however, the existence of two possible sets of optimal rate exponents depending on the number of data samples.
All setups (effectively non-regularized KRR (9), effectively regularized KRR (10) or optimally regularized KRR (11), (12)) can therefore exhibit a crossover from an effectively noiseless regime (green or blue in Fig. 1), to an effectively noisy regime (red, orange in Fig. 1) depending on the quantity of data available. We stress that while the noise is indeed present in the green and blue "noiseless" regimes, its presence is effectively not felt, and noiseless rates are observed. In fact, if the noise is small, one will not observed the classical noisy rates unless an astronomical amount of data is available. This can be intuitively understood as follows: for small sample size n, low-variance dimensions are used to overfit the noise, while the spiked subspace of large-variance dimensions is well fitted. In noiseless regions, the excess error 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 to the decaying structure of the co-variance spectrum (8). As more samples are accessed, further decrease of the excess error requires good generalization also over the low-variance subspace, and the overfitting of the noise results in a 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 non-regularized 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 λ = λ0n−` for a prefactor λ0 that is allowed to be very small, a regularization-induced 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. D.

heading: 4 Sketch of the derivation
text: We provide in 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-form solution for Gaussian design — The starting point is 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, 37, 39]. We shall use here the equivalent notations of [25], who have the advantage of having rigorous non-asymptotic rates guarantees. Within this framework, we shall sketch how the crossover phenomena (9) (10)(11) and (12), which are the main contribution of this paper, can be derived. With high-probability when n, p are large the excess prediction error is expressed as g − σ2 = ρ− 2m? + q?, (13) with ρ = θ?>Σθ?, and (m?, q?) are the unique fixed-points of the following self-consistent equations:
{ V̂ = n p
1+V
q̂ = np ρ+q−2m+σ2 (1+V )2
,  q = p p∑ k=1 q̂η2k+θ ?2 k η 2 km̂ 2 (nλ+pV̂ ηk)2
m = pV̂ p∑ k=1 θ?2k η 2 k nλ+pV̂ ηk
, { V = 1p p∑ k=1 pηk nλ+pV̂ ηk . (14)
We recall the reader that λ > 0 is the regularisation strength and {ηk}pk=1 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 → ∞. We note, however, that this last step is not completely justified rigorously. Indeed, [23] assumes p/n = O(1) as n, p→∞ while here we first send p→∞ and then take the large n limit, thus working effectively with p/n→ 0. While the non-asymptotic rates guarantees of [25] are reassuring in this respect, a 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) is perfect (see Figs. 2, 3 and 4). In the large n limit, one can finally close the equation for the excess prediction error into
g − σ2 =
∞∑ k=1 k−1−2rα (1+nz−1k−α)2
1− nz2 ∞∑ k=1
k−2α
(1+nz−1k−α)2
+ σ2
n z2 ∞∑ k=1
k−2α
(1+nz−1k−α)2
1− nz2 ∞∑ k=1
k−2α
(1+nz−1k−α)2
. (15)
with z being a solution of
z ≈ nλ+ ( z n )1− 1α ∫ ∞ ( zn ) 1/α dx 1 + xα . (16)
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) in [49].
The different regimes of excess generalization error rates discussed in Section 3 are derived from this self-consistent equation. Note that the excess error (15) decomposes over a sum of two contributions, respectively accounting for the sample variance and the noise-induced variance. In contrast to a typical bias-variance decomposition, the effect of the bias introduced in the task for non-vanishing λ is subsumed in both terms.
Derivation of the four regimes — If the second term in (16) dominates, then z ∼ n1−α, which is self consistent if ` ≥ α. This is the effectively non-regularized regime, where the regularization λ is not sensed, and corresponds to the green and red regimes in the phase diagram in Fig. 1. This scaling of z can then be used to estimate the asymptotic behaviour of the sample and noise induced variance in the decomposition on the excess error (15), yielding
g − σ2 = O(n−2αmin(r,1)) + σ2O(1), (17)
which can be rewritten more compactly as (9). Therefore, for small sample sizes the sample variance drives the decay of 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 (17) are balanced, around
n ∼ σ− 1 αmin(r,1) , (18)
which corresponds to the vertical part of the crossover line in Fig. 1.
If the first term nλ dominates in (16), then z ∼ nλ, which is consistent provided that ` < α. This is the effectively regularized regime (blue, orange regions in Fig. 1). The two variances in (15) are found to asymptotically behave like
g − σ2 = O(n−2`min(r,1)) + σ2O(n `−α α ), (19)
which can be rewritten more compactly as (10). If the decay of the noise variance term (α− `)/α is faster than the 2`min(r, 1) decay of the sample variance term, then the latter always dominates and no crossover is observed. This is the case for ` < α/(1 + 2αmin(r, 1)). If on the contrary the decay of the noise variance term is the slowest, then this term dominates at larger n, with a crossover when both terms in (19) are balanced, around
n ∼ σ 2 1− ` α (1+2αmin(r,1)) (20)
Eqs. (17) and (19) are respectively equivalent to (9) and (10), and completely define the four regimes observable in Fig. 1. Equations (20) and (18) give the expression for the crossover line in Fig. 1.
Asymptotically optimal regularization — Determining the asymptotically optimal `? is a matter of finding the ` leading to fastest excess error decay. We focus on the far left part and the far right part of the phase diagram Fig. 1.
In the n n?2 ≈ σ −max(2, 1αmin(r,1) ) limit where the crossover line confounds itself with its ` = α/(1 + 2αmin(r, 1)) asymptot, this is tantamount to solving the maximization problem
`? = argmax `
( 2`min(r, 1)10<`< α
(1+2αmin(r,1)) + α− ` α 1 α (1+2αmin(r,1))
<`<α + 0× 1α<` ) (21)
which admits as solution (12). In the n n?1 ≈ σ − 1 αmin(r,1) range, the maximization of the excess error decay reads
`? = argmax ` (2`min(r, 1)10<`<α + 2αmin(r, 1)1α<`) , (22)
and admits as solution (11).

heading: 5 Illustration on simple real data sets
text: 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 no firm reason to expect a power-law decay. However, we do find
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 α and r, see Appendix C for details. For those cases, we compare the theoretically predicted exponents, eqs. (9), (10), (11) 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 r from the data. We also observe the crossover from the noiseless (blue, green in Fig. 1) to the noisy (orange, red in Fig. 1) 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× 104 28× 28 images of handwritten digits. Even (odd) digits were assigned label y = 1 + σN (0, 1) (y = −1 + σN (0, 1)). • Fashion MNIST t-shirts versus coats, a data set of 14702 28× 28 images of clothes from an online shopping platform [50]. T-shirts (coats) were assigned label y = 1 +σN (0, 1) (y = −1 +σN (0, 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′) = e− γ 2 ||x−x ′||2 with parameter γ = 10−4 and a degree 5 polynomial kernel K(x, x′) = (1 + γ〈x, x′〉)5 with parameter γ = 10−3. In Fig. 5 the regularization λ was set to 0, while in Fig. 6 λ was optimized for each sample size n using the python scikit-learn GridSearchCV package [47]. KRR was carried out using the scikit-learn KernelRidge package [47]. The values of α, r were independently measured (see Appendix C) for each data set, and the estimated values summarized in Table 1. From these values the theoretical decays (9), (11) 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. 7 in the appendix), the estimates for α, r slightly vary depending on how the power-law is fitted. The precise procedure employed is described in Appendix C. Overall this variability does not hurt the good agreement with the simulated learning curves in Fig. 5 and 6.
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−2αr as r < 1) and noisy (slope 0) regimes is apparent on the same learning curve at noise levels σ = 0.5, 1. For MNIST, the σ = 0 (σ = 1) curve is in the noiseless (noisy) regime for larger n, while at intermediary noise σ = 0.5, and small n 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 on MNIST provided in [12].
For optimal regularization λ = λ? (Fig. 6), as the measured r < 1 we have exponents −2rα for the noiseless regime and −2rα/(1 + 2rα) for noisy. Since the measured value of 2rα is rather small the difference between the two rates is less prominent. Nevertheless, it seems that in our experiments the noisy regime is observed for polynomial and RBF kernels on MNIST and σ = 0.5, 1. For Superconductivity, the green and purple decay have close values and it is 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 a 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 a 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 on a 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 — We warmly thank Loucas Pillaud-Vivien for his insights, and for his help in navigating the literature on 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 Horizon 2020 Research and Innovation Programme Grant Agreement 714608-SMiLe, and from the French National Research Agency grants ANR-17-CE23-0023-01 PAIL.

Review summaries:
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).

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.

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.