A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression
Authors: Tin Sum Cheng
Aurelien Lucchi
Anastasis Kratsios
David Belius
Venue: NeurIPS 2024 poster (2024)
Keywords: kernel ridge regression
generalization
Primary area: learning_theory
TL;DR: We validate the Gaussian Equivalent Property rigorously, and provide novel bounds for kernel ridge regression.

Abstract: This paper conducts a comprehensive study of the learning curves of kernel ridge regression (KRR) under minimal assumptions.
Our contributions are three-fold: 1) we analyze the role of key properties of the kernel, such as its spectral eigen-decay, the characteristics of the eigenfunctions, and the smoothness of the kernel; 2) we demonstrate the validity of the Gaussian Equivalent Property (GEP), which states that the generalization performance of KRR remains the same when the whitened features are replaced by standard Gaussian vectors, thereby shedding light on the success of previous analyzes under the Gaussian Design Assumption; 3) we derive novel bounds that improve over existing bounds across a broad range of setting such as (in)dependent feature vectors and various combinations of eigen-decay rates in the over/underparameterized regimes.

A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression
Tin Sum Cheng, Aurelien Lucchi
Department of Mathematics and Computer Science University of Basel, Switzerland
tinsum. tinsum.cheng@nee www.:mmmnnnnnnnaa.....m ch, aurelien. lucchi@uniber ch
Anastasis Kratsios
David Belius
Department of Mathematics
Faculty of Mathematics and Computer Science UniDistance Suisse Switzerland david. belius@cantab. ch
McMaster University and The Vector Institute Ontario, Canada
kraatsio@@mcmaster..cm
Abstract
This paper conducts comprehensive study the learning curves of kernel ridge regression (KRR) under minimal assumptions. Our contributions are three-fold: 1) we analyze the role of key properties of the kernel, such its spectral eigen-decay, the characteristics of the eigenfunctions, and the smoothness of the kernel; 2) we demonstrate the validity of the Gaussian Equivalent Property (GEP), which states that the generalization performance of KRR remains the same when the whitened features are replaced by standard Gaussian vectors, thereby shedding light on the success of previous analyzes under the Gaussian Design Assumption; 3) we derive novel bounds that improve over existing bounds across a broad range of setting such as (in)dependent feature vectors and various combinations of eigen-decay rates in the over/unddrparammttriiee regimes.
Introduction
Kernel ridge regression (KRR) central tool in machine learning due to its ability to provide flexible and efficient framework for capturing intricate patterns within data. Additionally, it stands as one the earliest endeavors statistical machine learning, with ongoing research into its generalization properties [12, 45). Over the past few years, kernels have experienced a resurgence in importance in the field of deep learning theory [49, 8, 6]. partly because many deep neural networks (DNNs) can be interpreted approaching specific kernel limits they converge [25, 9].
One central topic in machine learning theory is the learning curve of the regressor in the fixed input dimensional setting as the sample size grows to infinity. Formally: let n be the sample size, X(n) be the ridge regularization parameter depending on n and R,, be the test error/excess risk of the ridge regression. For large n. the test error R,, should decay with n as R, = O, (9(n)) for
some function g IR + such that g(n) upper bound on the learning curve of the ridge regressor and will be the main focus of this paper. To conduct our analysis, we concentrate several crucial properties of the kernel, including its spectral cigen-decay and the characteristics of the eigenfunctions, which we will elaborate on next.
2
2-000
The decay of g with respect to n provides an
Properties of the eigenfunctions series of studies [10, 16, 34], the feature vectors are sub- stituted by random Gaussian vectors following the Gaussian Design (GD) Assumption, and the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

learning curve is derived using the Replica method. In a separate body of research [29, 30, 31], it is demonstrated that similar learning curves occur for Hölder continuous kernels under an assumption called the Embedding Condition (EC) (see Section A for more details). Consequently, there is fundamental mismatch between the distribution of the feature vector and the Gaussian random vectors used in [10, 16, 34]: in the former case, each coordinate is highly dependent on the others, whereas in the Gaussian Design case, each coordinate operates independently from the others. Astonish- ingly, however, both settings share similar learning curves. This phenomenon, initially identified by [21, 3, 42, 20], is termed the Gaussian Equivalence Property. This prompts the question:
Q1: When and why does the Gaussian Equivalence Property exist?
Spectral eigen-decay Many recent papers [10, 35, 44, 36] have attempted to characterize the test error solely by the (kemel) eigenspectrum decay. is for instance common to differentiate between different eigenspectrum decays: [29, 30, 31] assumes the embedding condition (EC) and Hölder continuity to kernel with polynomial eigen-decay; [33] assumes either polynomial or exponential eigen-decay (with noiseless labels) under the Maximum Degree-of-Freedon (MaxDof) Assumption; [36] assumes some concentration and the so-called hypercontractivity on eigenfunctions.
However, [14] pointed out that the characterization of generalization performance solely by the spectral eigen-decay might oversimplify the generalization performance of ridge regression. In relation to the second question, we further ask:
Q2: Under what conditions is the generalization error fully determined by the eigen-decay?
Additional assumptions and settings In addition to the two properties above, other hyperparam- eters or settings, including capacity of the kernels/feature vectors, the ridge regularization decay, the source condition of the target function, the noise level in the output label, and the amount of over over-paramen preeparamettrizaiion, play an important role in the analysis of the learning curve of ridge regression. Within the present body of research, various papers establish bounds the test error of KRR across diverse assumptions and settings (we refer the reader to Section A for further elaboration). It is therefore of significant interest to ask:
Q3: Is there a unifying theory explaining the generalization under minimal assumptions?
Contributions We address questions Q1-3 through the following contributions:
(i) Unified theory:
We provide unifying theory of the test error of KRR across wide variety of settings (see Subsection 2.2 and Table in Section 3).
(ii) Validation and GEP: We show that the generalization performance with independent (Gaussian) features and dependent (kernel) features coincides asymptotically and it solely depends on the eigen-decas under strong ridge regularization, hence validating the Gaussian Equivalent Property (GEP) (see Subsection 3.2).
(iii) New and sharpened bounds: We provide novel bounds of the KRR test error that improve over prior work across various settings (see Subsections 3.2).
(iv) Smoothness and generalization: We relate the spectral eigen-decay to kernel smoothness (see Appendix B.2) and hence to the kernel's generalization performance.
2 Setting
In this section, we introduce the basic notation for ridge regression, which includes high-dimensional linear regression and kernel ridge regression special cases.
2.1 Notations
Suppose p E N U (oo). Let = (xx) E R be random (feature) vector sampled from some distribution j on R". Let n E N be an integer and denote by Xi...., X,, n i.i.d. draw of x. Denote the input matrix X R"xp to be matrix with rows x,_ By fixing orthonormal basis, we assume that the covariance matrix is diagonal:
Σ E, [xx]] diag(An de. .......)))) Ap) E R2x,,

---

where the eigenvalues 2 Ao 2 2 Ap > 0 is decreasing sequence of positive numbers.
We also assume that y E R is output vector such that
X0 E
where 0* E IRP is a deterministic vector, 6 E R is random vector whose entries are i.i.d. drawn from a centered random variable e with variance = = oo and independent to X. Then the linear regressor
((y)
(XX + nAI,,
the minimizer of the empirical mean square loss (MSE) problem:
min ARR 72
X6
y112 2/10112.
where À 2 O is the ridge?. This paper focuses bounding the test error, with which analyse the learning curve of the regressor. To do so, we use the following well-known bias-variance decomposition.
Definition 2.1 (Bias-variance decomposition). Consider input-output pairs y) of sample size n and ridge À 2 0. Define the test error R be the population mean squared error between the regressor and the true label averaged over noise.
R del Ex,e
(x xxTo))xx (xx
Note that R random variable depending on the samples (X, y) and the ridge À 0. Hence, we can also view R R., as a random variable indexed in n, where the samples (X,y) are n i.i.d. drawn oututt pairs and is chosen to depend on n.
We decompose the test error into bias B and variance V, which is typical for most KRR literature [32, 23, 6, 46, 29, 30, 31, 13, 14]:
R= BB+ +
(5)
where B def Ex (x (xT 21
-x
drt Ex,c (xT6(c))
Remark 2.2 (Noiseless labels). If there is no noise in the label, that is, 0, the test error R is simply the bias Hence, the analysis of the bias term B in this paper is directly applicable the noiseless labels setting.
We now summarize the combinations of assumptions and settings made in this paper.
2.2 Assumptions and Settings
Polynonialeexponentaal eigen-decay We consider two types of spectral decay rates, namely, polynomial and exponential decay rates, because: 1) polynomial eigen-decay is, roughly speaking equivalent to the case where the RKHS is comprised at most finitely many continuous derivatives; 2) the exponential eigen-decay is. possibly up to canonical change in the relevant function space, equivalent to the case where the RKHS consists smooth (infinitely differentiable) functions. For the formal definition of the eigen-decay, see Assumptions (PE) and (EE). For further details and explanation on the relationship between eigen-decay and smoothness, we refer the reader to Section B.
Source condition Many previous works [6, 16, 7, 30] include the so-called source condition as assumptions on the target. If the task is proper, that is, 0* E H = H. we have 2 1. More generally, larger source coefficient& implies smoother target 0 in the RKHS H.
For p = co, we regard x as a vector of an infinite dimensional Hilbert space and Σ as a Hilbert Schmidt operator, meaning Tr [ < co. With abuse of notation. we write as vector and Σ as matrix throughout the paper. In some proofs, would apply with p = oc, replace those results with their Hilbert space counterparts.
linear algebraic results some p matrices. When dealing
FFor À without subscript, we mean the ridge regularization coefficient; for A with subscript k we mean the eigenvalues of the covariance E xx "
3

---

Definition 2.3 (Interpolation space). Let 2 be real number. Define the interpolation space
H c { R²: | -!- < <o0}.
Assumption (SC) (Source Condition). The source coefficient of target coefficient 0 is defined as
== inf (t > 0: 0* E H
See Subsection A.5 for more elaborations for the source coefficient s in polynomial or in exponential decay.
Strong/weak ridge We set the ridge À X(n) 2 0 to depend on the sample size The ridge is
considered strong (relative the eigen-decay) if x Amiu(n.p)+ that is, if A/ Aminff.pp) n0-00 0; otherwise, it is considered weak. Intuitively, the ridge is weak when it is negligible compared to the entries in the kernel matrix, effectively making ridgeless.
To summarize the assumptions discussed previously, let (Ae)k=1 be the eigenvalues of the kernel K, and l def. (0t) the coefficients of the target function being learned in the eigen-bace basis defined by K. Then assume either of the following assumptions:
Assumption (PE) (Polynomial Higen-decay). Assume that A = Ox (k-1-19,, 10%1 = O₂ (k-"), nn (n b) for some constants a, b, O, where + 2 2 & 2r unless specified. 3 Hence, if Assumption (SC) holds, the source coefficient is 20+0 We call the ridge À strong if (0, + a). Ita
and weak if b (1 + a, ool, under the convention that b == oc implies == 0.
Assumption (EE) (Exponential Figen-decay). Assume that A = O (e-ak), 0% = O2 (e-nk) = On (e b-bn) for some constants b,r r > O, where + 2r unless specified. 4 Hence, if Assumption (SC) holds, the source coefficient is 2r+e + L. We call the ridge X strong if b E (0, a). and weak if E (a, oo). under the convention that oo implies X = 0.
Generic/indeenndent features Our analysis centers on the assumptions regarding feature vectors, with focus on the dependencies between coordinates, particularly exploring two cases:
1. Generic features (GF): include the cases where the feature vectors are dependent on each other, for example, the feature vectors from the following kernels:
dot-product kemnels hyperspheres;
kernels with bounded eigenfunctions;
radial base function (RBF) and shift-invariant kernels;
kernels hypercubes.
satisfy Assumption (GF). Most previous literature [30, 33, 36, 19] have assumptions that only a proper subset of the above kemels satisfies. Therefore, we believe that we are operating under the minimal assumptions that exist in the field.
2. Independent features (IF): replace the feature vector with sub- Gab-Gaussinn random vector with independent coordinates. A special case is the Gaussian Design assumption (GD) used in literature [44, 35, 16].
For further explanations regarding the assumptions, refer the reader to Section A.
3
Main result
We first present an overview of the test error bounds across various properties, assumptions, and regimes. Our main results, summarized in Table 1, describe the learning curve in the over- parameterized regime, in terms of the bias B and variance decomposition (see Equation (5)). Then, we will discuss the implications of our results in depth.
'The condition a + a is purely technical and aims to simplify the results.
Similar as above.

---

3.1 Overview
Table summarizes many of our results in the over- perr-aaaeterizedd regime under various combinations of the assumptions described in subsection 2.2. The bounds are expressed in terms of the sample size On (-) or On (-) (ignoring logarithmic terms). Whenever we can also prove matching lower bound, we replace On (.) with On (-). We write (++
def. max ().
Ridge
strong
weak
Feature
(IF)
(GF)
(IF)
(GF)
O (n be)
(n (oo)))
O nn (144))
>>
Poly (PE)
O (min (min(2(r 02)
y
02n-1+ata
0 8An onn-
(a2)
Ô (aAn2
B
8
(e=beu)
(en)
(erain)
(c-aan)
Exp (EE)
V
o (
catastrophic overfitting
Table 1: Learning curve in the reee-parrmeterizedd regime (p n.:: n is the sample size, a,
define the eigen-decay rates of the kernel and target function, > controls the decay rate of the
ridge regularization parameter (Assumptions (PE) and (EE)), o² def. E [e]] is the noise level, and 8 O a technical parameter often determined by a and r (e.g. under Assumption (SC)). Here def min 2).
Results in blue indicate either previously unstudied regimes or improvements in available rates in a studied regime. See Table 6 for comparisons and Subsection 2.2 for details various settings.
Before delving into the detailed discussion of our comprehensive results in Subsection 3.2, let us highlight some important observations from Table 1.
Asymptotic bounds The upper bound illustrates the asymptotic relationship between the test error and sample size n as well as the following constants: a related to the eigen-decay, related to the ridge, related to the target function and o² related to the label noise.
Independent feature (IF) versus generic features (GF) The bounds in both cases coincide under strong ridge (see the left columns of Table 1); meanwhile, under weak ridge (see the right columns of Table 1), the bounds with generic features are looser than those with independent features. In Subsection 3.2, we will explain the necessity of this difference and hence showcase the previous limitations in the literature, which has widely adopted the Gaussian Design Assumption (GD) under the weak ridge/interpolation regime.
Novel bound of bias under weak ridge A notably sophisticated bound (on the upper right corner of Table I)
1 (n (1+o)5)
(n-(t)))))
5 >> 1
(6)
8 <
is novel to the best of our knowledge. Our improvement compared to previous literature [7] under various eigen-decay (in terms of a) and target coefficients' decay (in terms of r) is shown in Figure 1. By comparison, can see that the decay of our novel bound in Equation 6 is faster than previous results. Also, we prove that the upper bound the middle green region, ,hhrre & E (1, 2), is sharp.
Experimental validations of the results in Table 1 are given in Section 6.
In the under-parametterize regime, the bias B and variance V terms can be bounded similarly in over-parameterized regime. We postpone the details of these results to Section F.
3.2 Detailed discussion
In this subsection, elaborate more on the details of our results shown in Table
Independent and generic features Table 1 indicates that the test error exhibits the same up- per bound with either independent or generic features under strong ridge conditions in the over- parameterized regime. This similarity arises from the bounds in both cases being derived from the
5

---

Our result on B
Previous result on B
O(n 2(1 +a))
O(n 12 8))
19
(n al)
O(n On--ir-)
O1n 1/- 21)
r=a
341
341
((1)
((1)
21 2
Figure Phase diagram of the bound (Equation( 6)) of the bias term B under weak ridge and polynomial eigen-decay. AØ O (k-1-9), 0 θ (k-"), for some r >> 0. Our result (Propositions D.5+D.6+E. is on the left, which improves over previous result from [7] (Proposition D.6) on the right. On the left plot, the range of the source coefficient 2r+a in Assumption (SC)
is shown in gray font in each colored region.
same Master inequalities that will introduce later (see Section 4). However, under weak ridge conditions, the empirical kernel spectrum displays qualitative differences, as reported in [7, 14]. From Figure 2, we that V O (1) with Laplacian kernel in the left plot and V diverges with the neural tangent kernel (with hidden layer) the right plot. Hence under weak ridge and polynomial eigen-decay, the case distinction of the bound
== (o²) (o Assumption (GF) holds
Assumption (IF) holds,
Table necessary, as Assumption (GF) includes the cases of Gaussian Design (GD) (or more generally independent features (IF)) and Laplacian kernel which yields V = θ (1), the so-called tempered overfitting from [35]; as well as the case of neural tangent kernel (NTK) which yields
V 10-200 oc, the so-called catastrophic overfitting. In particular, our proof shows that the Gaussian Equivalent Property (GEP) does not hold under weak ridge.
Overfitting Laplacian komel
Overfitting with
Variance
1000
500
0.40
0
1030
Figure 2: Variance V against sample size n for the Laplacian kernel (left) and the neural tangent
kernel with hidden-layer (right) defined on the unit 2-disk, validating Equation (7) where the variance with generic features (GF) can be as good as with independent features (IF) (V O, (1))
qualitatively different (V n=000 oo). See Section 6 for more details.
We are now prepared address the first question posed in Section 1:
Q1: When and why does the Gaussian Equivalence Property (GEP) exist?

---

The Master inequalities provide the same non-asymptotic bounds for both cases under a strong ridge. However, GEP does not hold under weak ridge!
In particular, our work implies that previous works [10. 16, 34, 44, 35] under the Gaussian Design assumption (GD) can be applied only when the ridge is strong.
Upon finalizing the preparation for this paper, we became aware of concurrent research conducted by [19], which also concerns the Gaussian Equivalence Property (GEP) in the non-asymptotic setting. For more comparison between their assumptions and ours, refer the reader to Section A.
Importance of ridge To address the second question posed in Section 1, is evident that in either the under-paree paleetrpraettri setting with any ridge (see Section F) the over- werr-prametteizee regime with a strong ridge (see Table 1), the bounds for both and V remain the same, irrespective of the features:
Q2: Under what conditions is the generalization error fully determined by the eigen-decay? Either (i) in the under-parameterized setting; or (ii) with strong ridge in the over-parameterized regime.
Several results [39, 33, 36] have suggested that the test error bound can be characterized by the covariance spectrum Σ, but they implicitly require the ridge À >> O to be larger than some threshold. This paper clearly demonstrates the necessity of the presence of a strong ridge in such analyses.
From Table 1, we can see that the eigen-decay also affects the test error qualitatively. As mentioned in [33], the bias term B decays polynomially (or, respectively, exponentially) when the eigen-decay is polynomial (or, respectively, exponential). However, we prove that V decays only polynomially rate at most O (H), regardless of the eigen-decay. Hence, in noisy setting with polynomial
eigen-decay, one can find an optimal ridge x O, [1=n)=+T to balance both terms and V as in [16, 31]. In contrast, in noisy settings with exponential eigen-decay, V dominates the test error.
The bound of the variance term V with exponential eigen-decay under weak ridge is omitted in Table I due to the so-called catastrophic overfitting phenomenon observed in [35, 14].
Improved upper bound During our research, discovered that we can improve the upper bound of B (Equation 6) in the over-parameterized regime with polynomial decay, weak ridge, and Assumption (GF) by adapting the result from [31] and integrating with the insights from [7] (see the upper right corner in Table or 6, and Figure 1 for visualization).
Theorem 3.1 (Improved upper bound). Suppose Assumption (GF) holds. Assume the eigen-spectrum and the target coefficient both have polynomial decay, that is, 0E O2 (k- and 0%)
O& T) Let s 2r be the source coefficient defined in Definition (SC). Then the kernel ridgeless 1+a
regression has the following learning rate for the bias term B:
On (n (n-(r=a)+)
for s < 1; for 1 < s S 2; for s > 2.
B
On (n -2(2rta))
On (n (2-+a)))
where n is the sample size and (+)+ max(:,0).
For detailed explanation of our improvements, refer to our novel Proposition D.5 and the known Proposition D.6 from [7] in Section D.
Lower bound of test error It is of theoretical interest to provide lower bounds as well. For indepen- dent features, can prove that the upper bound is tight using the result from [46], generalizing the result from [16], which only showed upper bounds Gaussian Design Assumption (GD). However, for generic features, we can only provide lower bounds in some but not all settings, using the result from [31]. We summarize our results in Table 2.
Herr we only concern the upper bound of the asymptotic learning rate for GEP. As far as we know, there no other literature also concerning the lower bound. For readers interested in whether a matching lower bound for GEP exists, please refer to the paragraph Lower bound of the test error" and Table 2 below.
7

---

Ridge
strong
weak
Feature
(IF)
(GF)
(IF)
(GF)
B
(when 1 2)
Poly (PE) or Exp (EE)
because of Figure 2 Table 2: The table shows whether the lower bound is matching the upper bound deduced in this paper.
V
unknown
X
See Section E for details on our proof of matching lower bounds. We note that there is some KRR literature, such as [31, 36, 191, that discusses matching upper and lower bounds of test error under more assumptions, which is beyond the scope of this paper. For comparison of assumptions in different papers, see Section A.
Finally, we summarize the above discussion by answering the third question we raised in Section 1:
Q3: Is there a unifying theory on the generalization performance under minimal assumptions? Yes, this paper considers assumptions (IF) and (GF) which cover wide range of kernel settings under any regularization and source conditions.
4 Proof sketch
All the above results in Table can be derived using the following proof strategy:
1. We prove concentration result the whitened features z under Assumptions (GF) (IF) (see Section G).
2. Using the above result, we bound the condition number of the (truncated) kernel matrix (see Section G) as in [7, 14), which will be used to bound the test error in the next step.
3. Combining the bound of the condition number with the result from [6, 46], which call the Master inequalities (see the paragraph below for details), we can compute the non-asymptotic test error bound for various settings (see Section D).
4. In the over-parameteriize regime, we derive the asymptotic behavior of the learning curves by plugging in the eigen-decay and the choice the target function and ridge in the above non-asymptotic bound (see Section D).
5. Using the results from [46], we are able to show that the asymptotic upper bound for independent features (IF) tight (see section E).
6. For generic features (GF), we only provide tight bound results in limited settings (see section
E). As shown in Figure 2 in Section 3, the generic feature Assumption (GF) includes broad variety of features where universal matching lower bound does not exist.
7. In the padee-pprameterizeed regime, the Master inequalities also give upper bounds for B and V. which might not be tight if the ridge À is strong. However, we present another way to obtain tight bounds without the Master inequalities (see Section F for more details).
We summarize the proof techniques with flowchart in Figure 4.
Master Inequalities We will now briefly introduce the key inequality used our analysis (further details can be found in the Appendix). We will use the subscript > 1 or S & to refer to the submatrix of a matrix consisting of columns with index > & or < k (see definition C.3), The analysis relies on two crucial matrices: A X>*X + nAI, E nxx defined for any k E N, which is employed
to partition the spectrum, and whitened input matrix Z X 1/2 Raxp, Additionally, require the following definitions.
Definition 4.1 (Concentration coefficients [7]). Define the quantities:
def. n2 EE > + s1
del. 81 1 Zek)
E def. 81 (Z Zck)
8n (A+)
5k (Z Z<c)
where sx(-) denotes the i-th largest singular value of the matrix.
8

---

Definition 4.2 (Effective ranks [6]). Let & E N. Define two quantities:
Tr Σ
Ei=k+1
T
E A1) Σ Ei Af
def.
RR
del.
>>klogp
Ak+1
TR
The Master inequalities provide upper bounds on the bias and the (scaled) variance term of the test error in the following form:
1 1 2-2 +p
+ (525 + 2 -5 (AA))
B -
110 110
1 Sh Eg
8
n²
V/02 sp² (
Tr
rk 22
71 a T
n n (E)
The term appearing in the above bound can be categorized into two distinct components: the "probably constant" part (highlighted in blue) and the "decay" part (highlighted in gray). The "probably constant" part consists of terms that, with high probability, are bounded both below and above by positive constants these bounds represent primary contribution of this paper. On the other hand, the "decay" part can be approximated using basic calculus, once specific constant & E N, smaller than the sample size n, selected. Together, these two parts allow to derive the KRR learning rate for all combinations of eigen-spectra, features, and ridge parameters discussed in the preceding sections. Furthermore, [46] provides a corresponding lower bound under certain assumptions, demonstrating that the decay of the upper bound matches that of the lower bound. Establishing that Assumption (IF) satisfies these assumptions another key contribution of this work. For the formal definitions of the terms in the above inequalities, we refer the reader to Propositions C.6 and C.7 in the appendix.
5 Related work
We briefly discuss related previous works and compare them with our results in the over wer-parameterized regime: (see Table 6 for more visual illustration)
1. [16] considered the upper bound of B and V polynomial eigen-decay under any ridge and under the Gaussian Design Assumption. Our result proves both the matching upper and lower bound with the same decay rate under a weaker assumption (IF). This implies that we validate the Gaussian Equivalence Property for Sub-Gaussian Design.
2. [30, 31] proved tight upper bounds of B3 and V for Hölder continuous kernels under polynomial eigen-decay, strong ridge and the so-called Embedding condition (EC). [7] recovered the upper bounds under Assumption (GF).
3. For polynomial decay under weak ridge, [31] provided tight upper bound of B when the source condition > 1: while [7] provided a loose bound regardless of s. Hence we modify the proof in [31] under Assumption (GF) instead and combine it with [7] to obtain novel upper bound the bias.
4. [7] also provided an upper bound of under polynomial decay, weak ridge and Assumption (GF).
5. [14] showed that V bounded above and below by positive constants under polynomial eigen- decay, weak ridge and Assumption (IF), and it exhibits the so-called tempered overfitting from [35].
6. [33] provided tight upper bounds of B for both polynomial and exponential eigen-decay for kernels under the so-called Maximal
(MaxDoF) Assumption. We recover their result under Assumption (GF) instead of Assumption (MaxDoF).
7. We apply the result from [46] and [31] obtain matching lower bound in settings and strengthen our result from O, (-) to O, (.).
Experiments
Due to page constraints, this section focuses solely on experiments validating the Gaussian Equivalent Property (GEP). For detailed experiments other contributions, refer to Section I.

---

We consider simple example: let A = ( (26-1 T) and wh(()) = sin x such that 11vellzz 1 for μ unif 1]; let 0%
-)) For p and
the regression
coincides with kernel ridge regression with kernel k(z,z") min x'} defined on the interval [0, 1] [48]. Similar experiments have been conducted on this kernel k by [30, 33]. However, to simulate regression for independent features (IF), the feature rank must be finite. In the following experiment, we choose p, 2000, and the sample size n ranges from 100 1000, with ridge parameter À = =(2t (2m-- x) where b E [0, 1 + a).
In Figure 3, our experiment demonstrates the GEP, as the learning curves with kernel features (Sine features) and independent features (Gaussian features 2 ~ (N,, Ip) or Rademacher features (=1)))++)))) coincide and match the theoretical decay.
Blas, a=1, 2= 1=1
Bias, a=0.5, b=1.5, 115.
Sine feature
10
Sine feature
Test Error (log scale)
10
Rad emacher feature
Test (lng scale)
Rademacher feature
Gaussian feature
10
Gaussian feature Slope 3.22
10
Slope= 3.11
10
10"
10 -1
10
10
2x10' 1010''x10" 6x10'
10
10'
2x10"
3 10140xx00" (log scale)
60
10*
(log scale)
10" -3
Variance, 3=1, b
Variance, a=1, b-1
Sine feature
Sine feature
Enrer (log scalle
Rademacher feature
Test Error (log scale)
4x10
Rademacher feature
Geussian feature
Gauesian festure Slopen-0.51
Stope- 1.00
3x10"
2x10 -2
10
10²
2x100
3x10"4x100 (log scale)
6x10"
10"
10'
2x10" 3x 3x10'xx10" 6x (log scale)
10"
Figure 3: Decay of the bias term B and the variance lerm V under disferent ridge decays and target coefficient decays. All features demonstrate the same theoretical decay, validating the GEP for independent features.
7 Conclusion
In this paper, we present unifying theory and comprehensive analysis of the learning curve of kernel ridge regression under various settings. We elucidate the coincidence of learning curves between the Gaussian Design (GD) setting (or more generally, independent features (IF)) and the kernel setting (or more generally, generic features (GF)), and validate the Gaussian Equivalence Property under strong ridge. In addition to recovering previous results, we also improve test error bounds under specific circumstances, thus filling gap in the existing literature.
Future potential work Our results also raise several theoretical questions. For instance: i) The upper bound in several regions of the phase diagram in Figure is not known to be sharp. would be of interest to either improve it or find matching lower bounds in those regions; ii) Why is there qualitative difference in overfitting with the Laplacian kernel and the neural tangent kernel, as shown in Figure 2? Can one further distinguish different cases in the generic feature Assumption (GF) to explain such differences? Additionally, how tight would the bound V/ = O (o²n²") in Eq. (7) be?
Addressing these questions could provide deeper insights into the behavior of kernel ridge regression under various conditions and contribute to further advancing our understanding in machine learning.
10

---

Acknowledgments
A. Kratsios acknowledges financial support from an NSERC Discovery Grant No. RGPIN-2023- 04482 and No. (GEECR-2023-00300. A. Kratsios also acknowledges that resources used in preparing this research were provided, part, by the Province Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute
References
[1] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang- Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. International Conference Machine Learning, pages 322-332. PMLR, 2019.
[2] Kendall Atkinson Weimin Han. Spherical harmonics and approximations on the unit sphere: an introduction, volume 2044 of Lecture Notes in Mathematics. Springer, Heidelberg. 2012.
[3] Benjamin Aubin, Florent Krzakala, Yue Lu, and Lenka Zdeborová. Generalization error in high-dimensional perceptrons: Approaching bayes error with convex optimization. Advances in Neural Information Prucessing Systems, 33:12199-12211 2020.
[4] Francis Bach. Breaking the curse of dimensionality with convex neural networks, 2016.
[5] Francis Bach. High-dimensional analysis of double descent for linear regression with random projections. arXiv preprint arXiv:2303.01372. 2023.
[6] Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(45):30063-30077) 2020.
[7] Daniel Barzilai and Ohad Shamir. Generalization in kernel regression under realistic assump- tions, 2023,
[8] Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 541-549. PMLR, 10-15 Jul 2018.
[9] Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels, Advances in Neural Information Processing Systems, 32, 2019.
[10] Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves kernel regression and wide neural networks. In International Conference on Machine Learning, pages 1024 1034. PMLR, 2020.
[11] David Borthwick. Spectral theory-basee concepts and applications, volume 284 of Graduate Texts in Mathematics. Springer, Cham, [2020] @2020.
[12] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7:331-368, 2007.
[13] Tin Sum Cheng, Aurelien Lucchi, Ivan Dokmanić, Anastasis Kratsios. and David Belius. theoretical analysis of the test error of finite-rank kernel ridge regression. Annual Conference on Neural Information Processing Systems, 2023.
[14] Tin Sum Cheng, Aurelien Lucchi, Anastasis Kratsios, and David Belius. Characterizing overfit- ting kernel ridgeless regression through the eigenspectrum. In The Eleventh International Conference on Learning Representations, 2024.
[15] Samuel N Cohen, Deqing Jiang, and Justin Sirignano. Neural q-learning for solving pdes. Journal of Machine Learning Research, 24(236), 2023.

---

[16] 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:11111-10113,, 2021.
[17] Harold Donnelly. Bounds for eigenfunctions of the Laplacian on compact Riemannian manifolds.
J. Funci. Anal., (87(1):247-26)) 2001.
[18] Junichi Fujii, Masatoshi Fujii, Takayuki Furuta, and Ritsuo Nakamoto. Norm inequalities equivalent heinz inequality. Proceedings of the American Mathematical Society, 118(3):227- 830, 1993.
[19] Georgios Gavrilopoulos, Guillaume Lecué, and Zong Shang. A geometrical analysis of kernel ridge regression and its applications, 2024.
[20] Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. The gaussian equivalence of generative models for learning with shallow neural networks. In Mathematical and Scientific Machine Learning, pages 426-471, PMLR, 2022.
[21] Sebastian Goldt, Marc Mézard, Florent Krzakala, and Lenka Zdeborová. Modeling the influence of data structure learning in neural networks: The hidden manifold model. Phys. Rev. X. 10:041044, Dec 2020.
[22] Moritz Haas, David Holzmüller, Ulrike Luxburg, and Ingo Steinwart. Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension. Advances in Neural Information Processing Systems, 36, 2024.
[23] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. Annals of statistics, 50(2):949, 2022.
[24] Simon Hubbert, Emilio Porcu, Chris J. Oates, and Mark Girolami. Sobolev spaces, kernels and discrepancies over hyperspheres. Transactions on Machine Learning Research, 2023.
[25] 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
[26] Deqing Jiang, Justin Sirignano, and Samuel N Cohen. Global convergence of deep galerkin and pinns methods for solving partial differential equations. arXiv preprint arXiv:2305.0600 060000 2023.
[27] Vladimir Koltchinskii and Karim Lounici. Concentration inequalities and moment bounds for sample covariance operators. Bernoulli, 23(1):1 10-133, 2017.
[28) Lars Larsson-Cohn. [P-norms of Hermite polynomials and an extremal problem on Wiener chaos. Ark. Mat., 40(1):133-144, 2002.
[29] Yicheng Li, Haobo Zhang, and Qian Lin. On the saturation effect of kernel ridge regression. In The Eleventh International Conference on Learning Representations, 2022.
[30] Yicheng Li, Haobo Zhang, and Qian Lin. Kernel interpolation generalizes poorly. Biometrika, 2023.
[31] Yicheng Li, Haobo Zhang, and Qian Lin. On the asymptotic learning curves of kernel ridge regression under power-law decay. In Thirty-seventh Conference on Neural Information Pro- cessing Systems, 2023.
[32] Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. The Annals of Statistics, 48(3), Jun 2020.
[33] Jihao Long, Xiaojun Peng, and Lei Wu. duality analysis of kernel ridge regression in the noiseless regime, 2024.
12

---

[34] Bruno Loureiro, Cedric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Mare Mezard, and Lenka Zdeborová. Learning curves of generic features maps for realistic datasets with teacher-student model. Advances in Neural Information Processing Systems, 34:18137-18151, 2021.
[35] Neil Mallinar, James B. Simon, Amirhesam Abedsoltan, Parthe Pandit, Mikhail Belkin, and Preetum Nakkiran. Benign, tempered, or catastrophic: A taxonomy of overfitting, 2022.
[36] Theodor Misiakiewicz and Basil Saeed. A non-asymptotic theory of kernel ridge regression: deterministic equivalents, test errr, and gcv estimator, 2024.
[37] Étienne Pardoux. Backward stochastic differential equations and viscosity solutions of systems of semilinear parabolic and elliptic PDEs of second order. In Stochastic analysis and related topics, VI (Geilo, 1996), volume 42 of Progr. Probab., pages 79-127. Birkhäuser Boston, Boston, MA, 1998.
[38] Etienne Pardoux and Shige Peng. Backward stochastic differential equations and quasilinear parabolic partial differential equations. In Stochastic Partial Differential Equations and Their Applications:
Proceedings of IFIP WG 7/1 International Conference University of North Carolina at Charloute, NC June 6-8, 1991, pages 200-217. Springer, 2005.
[39] Lorenzo Rosasco, Mikhail Belkin, and Ernesto De Vito. On learning with integral operators. Journal of Machine Learning Research, 11(2), 2010.
[40] Saburou Saitoh and Yoshihiro Sawano. Theory of reproducing kernels and applications, volume 44 of Developments Mathematics. Springer, Singapore, 2016.
[41] Isaac J Schoenberg. Positive definite functions spheres. Duke Mathematical Journal, 91): 108, 1942.
[42] Mohamed EI Amine Seddik, Cosme Louart, Mohamed Tamaazousti, and Romain Couillet. Random matrix theory proves that deep learning representations of gan-data behave as gaussian mixtures. In International Conference on Machine Learning, pages 8573-8582. PMLR, 2020.
[43] Barry Simon. Operator theory, volume 4. American Mathematical Soc., 2015.
[44] James B Simon, Madeline Dickens, Dhruva Karkada, and Michael Deweese. The eigenlearning framework: A conservation law perspective kernel ridge regression and wide neural networks. Transactions on Machine Learning Research, 2023.
[45] Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science & Business Media, 2008.
[46] Alexander Tsigler and Peter Bartlett, Benign overfitting in ridge regression. Mach. Learn. Res., 24:123-1, 2023.
[47] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices, page 210-268. Cambridge University Press, 2012.
[48] Martin J. Wainwright. High-DDiensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
[49] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization, 2017.
[50] Haobo Zhang, Yicheng Li, and Qian Lin. On the optimality of misspecified spectral algorithms, 2023.
[51] Nikita Zhivotovskiy. Dimension-free bounds for sums independent matrices and simple tensors via the variational principle. Electronic Journal of Probability, 29:1-28, 2024.
13

---

Appendix
The appendix will be organized in the following way:
The detailed discussion of the assumptions used in this paper and the comparison to previous
literature presented in Section A;
extended discussion of the eigen-decay assumptions is presented in Section B; the main tool of this paper, the Master inequalities, is presented in Section C;
the details of the proof on the asymptotic over-parameterizze regime in Table presented in Section D;
the proof for matching lower bound is presented in Section E;
the details of the proof on the non-asymptotic bound in under-parameterizer regime is presented in Section F;
the concentration result the whitened feature and the conditioning of the kernel matrix are presented in Section G;
related technical results from previous literature are collected in Section H;
experimental results are shown in Section
extra tables of summary can be found in Section J.
The summary of our proof can be found in the flowchart in Figure 4.
Concentration (Section
Master inequalities (Section C)
under-param. (Section E)
Conditioning (Section Gi)
Test error upper bound (Section D)
matching lower bound (Section E)
unknown
e, (+) bound
O₂ (-) bound
Figure 4:
flowchart about the proof techniques this paper
Big-O Notation We use the standard Big-O notations O (+), o. (.). (+), O. (-) to represents the asymptotic behaviours the bounds in this paper, where the subscript indicates that the constant in the bound is independent to the variables in the subscript. We use to suppress logarithmic terms. With abuse of notation, we use the same notations for their probability versions, when the context clear.
14

---

A Assumptions in details
The primary assumptions made in this paper concern the whitened feature vectors E RR: Assumption (GF) (Generic features (7]). Let N {oo). Assume the isotropic feature vector z def Σ x-1/2x I2P and the covariance matrix Σ RPXP are such that:"
| Ese = =xx (1),
O css inf 2
def
Tr|
| 11
||
|| 1
3x der
ess sup max
Tr
Esk
Tr S
O, (1),
Remark A.1 (l==00 -). For k = 0, we take the convention that Bo def css sup, max
x TE
| 12:0
TrE
Remark A.2 (Intuition). The intuition is that the three fractions above have expected values of 1:
|| TTE
22 12
Ex
Ex
Ex
1. Hence, Assumption (GF) imposes strong
Tt T=
concentration each truncation point le E N.
Remark A.3 (Weaken Assumption (GF)). One can further replace the essential supremum and infinum by a high probability guarantee. The argument on the test error bounds would follow analogously with weaker probability. For simplicity reasons, only consider the assumption in the above formulation.
Assumption (GF) encompasses both cases of dependent and independent features 2g. which can have qualitatively different effects on the test error.
To compare the realistic kernel setting with the Gaussian Design setting (GD) used in previous literature [10, 34, 16, 44, 35], which replaces the feature vectors with Gaussian random vectors (with independent entries), we consider a weaker version of the Gaussian Design assumption commonly required in KRR literature [6. 13, 5, 36, 19]:
Assumption (IF) (Independent sub-Gaus Gaussian features). Suppose E N. Assume that the features 2g 's in the isotropic feature vector are independent each other and there exists constant G 0 such that the Sab-Gaussian norm || l,22 of any feature 2ą is bounded by G. In over pee-pearaeterizee regime, we also assume that there exists some constant > independent to n such that p > 1pn
Remark A.4 (Infinite rank). With Assumption (GF), the feature dimension p can be taken as oc; with Assumption (IF), however, if no further boundedness assumption is imposed, the norm xx|22
VEE= A can be undefined if p CO. However, if the sub- Gaussian variables 24 's are all bounded in the sense of Assumption (GF), then p can be chosen to be infinity as well.
Remark A.5 (Special case). If the features 24 are additionally bounded, then Assumption (IF) becomes special case of Assumption (GF). The former assumes independence of the features, while the latter does not.
Both assumptions (GF) and (IF) are much weaker than those in most KRR literature in the sense that: i) there is no explicit assumption the input space X: ii) the distribution of the feature vector need not even be continuous! It is surprising that even with such minimal assumptions, one can derive tight bounds on the test error.
For more detailed comparison between the assumptions in this paper and those in previous literature, see Section A.
We next compare the assumptions (IF), (GF) with the assumptions in previous literature.
A.1 Among assumptions with independent features
The Gaussian Design Assumption, often employed in various literature such as [10, 16, 34, 20, 35, 44], can be considered a special case of Assumption (IF):
We write l|vl details.
Vv Mv for PDS matrix M and any vector v. See Definition C.I Section C for more
15

---

Assumption (GD) (Gaussian Design). The feature vector z ~ (O, Ip) is distributed as isotropic Gaussian.
Note that Assumption (IF) is much weaker than Assumption (GD) in the sense that: the distribution of the feature vector z is no longer rotational invariant or enjoys anti-concentration property; ii) the distribution of each feature 2g needs not be continuous; iii) the features 2y. needs not be identical.
Meanwhile, Assumption (IF) appear commonly in KRR literature, for example [6, 46, 23, 5, 13, 14].
A.2 Among assumptions with dependent features
Examples that satisfy Assumption (GF), which is first introduced by [7], includes:
1. dot-product kemels on hyperspheres;
2. kernels with bounded eigenfunctions;
3. radial base function (RBF) and shift-invariant kernels;
4. kernels on hypercubes.
In particular, the features from Assumption (IF) also satisfies the weakened version of Assumption (GF). See Remark A.3 for details.
Before comparing assumptions with previous literature, first define the oc-norm in the ridge regression setting analog to its kernel counterpart:
Definition A.6 (oo-norm). Fix a distribution μ on I2 and let v E Define
|/
llo def.
ess sup x T v| = sap e l|aa I x a.s. for x ~ p}
zmpp
Remark A.7. Note that ||- is indeed semi-norm and for all v E RP, we have
|ivll S ||
Choose k: = and Assumption (GF) and Remark A.1 imply:
1z| Tr
|z|
|x| 2 ess sup ||I|| ess sup / S Bo def.
ess sup max
00;
Tr
as we assume that Tr < OC.
Embedding condition [29, 50, 30, 31] used the Embedding Condition to show tight bounds of learning curve with polynomial eigen-decay:
Assumption (EC) (Embedding Condition). Given random vector x E EP with covariance Σ E[xx] let z = 1 be the isotropic random vector. Define the embedding coefficient:
i/u inf (css sup ||x 13-12--- < 20) inn fessssssup | < <00].
71
Suppose the eigen-decay is polynomial: A = O₂ (k-1-a) for some a > O. Assume the embedding coefficient To I+a
Remark A.8 (General range of rjo). Rewrite the expression:
x
OF
k n (1+))))
where we write x = ( E IR and z = (2x) E RP. In the kernel case, it is obvious that No 1: for all inputs E X' with embedding k(x,)) .) in the feature space H. sup,, k(x,
'Rotational invariant, and respectively onticconcentration property. are crucial in some literature using Gaussian Design Assumption, for example [44], and respectively [14].
16

---

|x < co. Since the cigenvalues have polynomial decay, we have no 2
Ita or otherwise there
1
were some 1y (no: T such that:
2k 1) 52
Ex [ Ω
E
Σ k
Σ Ex-n(tte) 00,
contradicting Assumption (EC). Thus one have yo E [Tta 1] in general.
Hence Assumption (GF) is much weaker assumption than Assumption (EC) in the sense that the former one only requires 7o S 1, which holds in general: while the latter one requires no I+a' which the smallest possible size of 7/o Hence, many examples mentioned [50], that satisfy Assumption (EC) also satisfy Assumption (GF). For instance, the examples include:
__
1. dot-product kermels on hyperspheres;
2. kernels with bounded eigenfunctions;
3. shift-invariant periodic kernels.
Nevertheless, [29, 50, 30, 31] also require Hölder continuity of the kernel K while Assumption (GF) requires no continuity assumption.
Maximal degree of freedom We rewrite and simplify the assumption used [33] with our notation:
Assumption (MaxDoF) (Maximal ofgree--o-FFreddmm) For any À > 0 and s 2 1, define:
der (*(A)
esssup
(E + ^I,) -//3)
Assume: there exists N such that
5F (X.) max (og
for some constant 8 (0, 1).
Usually, the constant s is chosen as the source coefficient in Assumption (SC), Again, Assumption (MaxDoF) requires some extra boundedness condition on the norm of Examples that satisfy Assumption (MaxDoF) include:
dot-product kernels on hyperspheres;
2. kernels with bounded eigenfunctions;
3. periodic kernels on hypercubes,
which also satify Assumption (GF).
Low/High-degree feature concentration [36] proved the convergence of the test error to its "de- terministic equivalent" using list of assumptions for each fixed sample size n. To avoid introducing extra notations, we list their assumption here in semi-rigorous way:
Assumption (LH) LLowHiggh-egree feature concentration). Fix n E N and À 2 0. Suppose there exists an integer ls I p such that:
1. A+TrE>a] 2 2n; Au+1
2. the low-degree feature vector X E R2 is highly concentrated:
3. with high probability, the high-degree feature vector X> E IBP-k satisfies:
X Tr C J
(A + T+
where C > 1 is constant depending K.
17

---

Point 3 in Assumption (LH) is closely related to Assumption (GF) since:
Tr|E>A]
TrXX
Tr|E In] & > x S
Tr/E
[I op
| Tr|Es1]
ess esssupx
O& (1), then 1 n Ex=1 1>> TrE 22 (1).
According to [36], examples that satisfy Assumption (LH) include:
1. kernel satisfying Assumption (IF);
2. dot-product kemnel on hyperspheres.
Moment-equivalent assumption [19] use a geometric argument with Dvoretzky-Milman Theorem to bound the test error from above under the assumptions:
Assumption (ME) (L2++-L* Moment-Equivales Assumption). Fix a sample (x.) Suppose there exists some e,
such that:
1. for any k E N and any function f E Hys in the high-degree feature space, we have I S [I]
(a) ife 2, then no extra assumption is required;
2-c
V Tr(33,]
(b) if (0, then kn 2012 log
is small.
Tr|Es
[[())>*ll T+|x>+]
2. with high probability, max;=1....
||(=:)> 1133
3. with high probability, max;=1,...
Rs 1;
Trp
[2,) 1 Ox (1).
4. with high probability, maxi=1,....
While points 2-4 are implied by the weakened version of Assumption (GF), point a strong geometric assumption the RKHS H. According to [19], the addition of point I can drop the logarithmic terms in the upper bound test eиrоr under weak ridge, and thus strengthening some results in Table from (+) to (.). Examples satisfying Assumption (ME) includes:
1. rotational invariant kernel.
A.3 Between independent and dependent features: random features
A random feature setting be considered midpoint between independent and dependent features: Let W E be a random matrix, typically with i.id. random entries, and z Rd be the input vector, usually comprising independent entries. We define the random feature x E RP
one-hiddennlayer neural network: x (WW,), where IR -> IR represents an activation function acting entry-wise Wz. Thus, the coordinates of the pre-activation independent, while those of the post-activation are not.
However, it is worth noting the Gaussian Equivalent Property highlighted in [20], which asserts that in wide neural networks, the distribution of the feature vector x is approximately Gaussian. Consequently, it reduces to the case of independent features previously discussed.
A.4 Interpolation space
Many KRR literature [29, 30, 31, 33] introduced the notation of interpolation space and the source condition on the L inttergaeee target function f*. This can be easily translated to the notion of generalized vector norm.
Definition A.9 (Interpolation space).
Let 2 0 be real number. Define the interpolation space
Hs {0 RP |0 x
oo).
18

---

Evidently, s1 I $2, then | g I |اا| and hence Hes 5 Maz The intuition is that, in the KRR setting, the space H. interpolates between the -spcce L (2) 5 H. and the RKHS H. = H."
A.5
Source condition
Given the asymptotic of the eigen-decay As and the target coefficient 0", find the largest possible source coefficient s. For instance, if A O2 (k-1- for some a >> 0 and [0 = O2 (k""),
then we can choose 8 to be 2r+a.
0 E 71 + 10 | < 00
10 1- <00
k=1
hi -2 (2r ((11-)(-1-0) < <00
1=1
h: 1---atttto-22 <00
8
4=1
-1 - 1-aat= ta 2r < <1
+
1+
Suppose Au = Ox (e-ak), 10 = O₂ (e-rk) for a, > 0. Then we can choose 8 to be 2r
+ 1:
0" E H. + |00 |اك ب <0
(8") 2 x/- <
p
2 -ak)1= 1-t 00
-(2r+o-aa <
k=1
3 2r at 0
2r
+ #t < + 1.
A.6 Kernel ridge regression
KRR can be regarded as ridge regression on the feature space, where the positive definite symmetric (PDS) kernel K sends each input æ E X' to a vector/function K(x,) -) in the corresponding reproducing kemel Hilbert space (RKHS) H. and the kernel regressor simply linear regressor in the RKHS H. Here we briefly explain how to translate the notations above in the kernel ridge regression (KRR) setting.
With abuse of notation, let be (data-generating) distribution on an input space X. Let K X' x X + R be positive definite symmetric kernel with corresponding reproducing kernel Hilbert space (RKHS) H. By Mercer decomposition, we have for all x, x' E supp(u) C C.:
K K(x, x') = E (edn(
where d are the eigenvalues of K indexed in decreasing order and v'a X - RR's are eigenfunctions of K forming an orthonormal basis on L (X)): Eew [+x()) dy for all k, N. Hence for
19

---

each 2 E supp(u) C. (x, is feature vector in the RKHS H. which has an orthonormal basis
( Vhe 1k
y= + e be the labels where f (X') and é a centered random variable with finite variance independent to æ. Let (Ii, 1) be a set of ii.d. drawn input-ouiput pairs. The kernel ridge regression in the form:
min ((f(z)) -1)² +11l JEH 1=1
which minimum admits the form:
f(x) K (K + nd1,) ly, Yx R.
where K₂ (K(z, E R", K [K Fz )R E Rnx* and y (y:)i=1- Note that if we write 1.. = (x)) R., v [1;(x;)]ı Rux and A = diag(Au]i E IRXP,, by Mercer decomposition, we have Kg MA = AAY We are ready to translate our linear ridge regression to the KRR setting. See Table 5 for details.
20

---

B Smoothness and spectral decay rate
In this section, will explain the reason assume the eigen-decay to be either polynomial or exponential the paper.
Concretely, the "polynomial decay regime" arises as the Neural Tangent Kernel (NTK) limit of Multi- Layer Perceptrons (MIPss with an activation function of the form (t det max 0, 1", where 2 1, as studied in [4]. In cases where is an integer, d, represents the (s 1)tth iterated anti-derivative of the ReLU function, making exactly s times weakly differentiable.
Suppose X' the d-dimensional sphere Sd {u E Rd |u| = }} (with its usual Riemannian metric). In this scenario, every neural network function f : + belongs to the Sobolev space H' (S*) (see Proposition B.7 in Appendix B.2), characterized by having s continuous and integrable (weak) partial derivatives on gd Additionally, the NTK limit manifests as a "radially symmetric kernel", specifically of the form (zz, y) k(x' y) for some suitable function K [-1, R.
is worth noting that the choice of the smoothness level, and hence the decay rate, naturally emerges when approximately solving Partial Differential Equations (PDEs), as demonstrated in works such as [26. 15]. In these scenarios, it is desired that the kerrel regressor exhibits the correct level of smoothness matching that of the theoretical solution to the PDE, with its higher-order derivatives also converging. is emphasized that the solution to several PDEs only possesses finitely many derivatives, as seen in (viscosity) solutions to PDEs arising in stochastic control [37, 38].
In the remainder of this section, we justify the use of Assumptions (PE) and (EE) by establishing connection between the spectral eigen-decay and the smoothness of the Reproducing Kernel Hilbert Space (RKHS), which is independent of the rest the paper. Readers primarily interested in proof' presented in Table may opt skip this section and proceed to Section C during their initial reading.
B.1 Notations
Fix a positive integer E N and let X' be non-empty subset Rd We equip X' with a regular Borel probability measure Jr, which we specify shortly. We denote the space of (equivalence classes of) u-square-integrable on Rd by L (Rd), equipped with its usual L norm || 1|12-
Consider a kernel K X' X X + R with its associated to the RKHS (H, (x-))) (abbreviated by H). We denote the induced norm H by || Ilx- By the Mercer decomposition theorem, see [40, Theorem 2.30], there is some M E N U {oo} such that we may write
<(x, w)
(8)
1=
where ( are normalized eigenfunctions of the linear operator (z) Jeex k(x, (u) du on (2) and each eigenvalue (A:) is non-negative; which, form an orthonormal basis of H.
We motivate our analysis, by the following connection between the spectral decay of dot-product kernels on spheres and the smoothness of functions in their RKHS.
Example B.1 (Radial Kernels and Sobolev Spaces on Spheres). In the setting of Examples B.3 and (B.5), suppose that there is function k [-1, 1] R such that
*(x,00 v) del.
k((x,v))
for each N. E Sd. As shown in [41], is kernel if and only if there is a summable sequence of non-negative real numbers (a satisfying k(t) = -in ag tt for each E [-1,1]. Kernels of the form (9) are called radial. The RKHS H associated to k consists of all functions f Sd + R with
O.ja V3.
(10)
j=0
for square-summable real sequence (ag,) depends only on the radial function k, and thus only the radial kernel K; and (3),)) the
(aga) voc.d. i.e. Eie E/ 0z, < 00 (where (as.)) yo.J,
po.
21

---

spherical harmonics described in Example B.3. As discussed in [24, Chapter 4], for any k > 0 H. belongs to the Sobolev space H ( if and only if: for each H. the coefficients {=;))==
in the representation (10) satisfy
Pj E O(U + 21)
As discussed in [22, Lemma B.1] in this case the norms of H. and on (**( are equivalent.
B.2 Preliminaries: regular domains and Sobolev spaces
We consider the case where X' is sufficiently regular open subset of the d-dimensional Euclidean space so that we may comfortably describe the smoothness of functions on X using classical notions of tools. We therefore assume the following.
Assumption (DR) (Domain Regularity). Either one of the following holds:
(i) Compact manifold: (X.9) g) is d-dimensional compact Riemannian manifold, with 2 and = Vx( Vg is the uniform law on (X. 9) and Vg is its volume measure.
(ii) Bounded Euclidean domain: X is a non-empty bounded open domain in R with Lipschitz boundary and p is the normalized Lebesgue measure.
In cases (i)-ii), X can be viewed as Riemannian manifold (possibly with boundary).
In what follows, let A denote either of the following Laplacian, depending on which of assump- tion (DR) we have assumed. If (i) or (ii) holds then A will denote the usual Laplacian-Belle Beltrami operator X. note that when (iii) holds then A d 3a
We denote the eigenfunctions of A
d.?"
by (Di) whose respective eigenvalues A1 A2 ... arranged in non-decreasing order. If (iii) holds, then A will denote the Dirichlet Laplacian (see [11, Section 6. 1.2) on X (with its usual Euclidean Riemannian metric) which acts the spaces of functions vanishing the boundary Ox of X: namely on the homogeneous Sobolev space Hi (X)).
Example B.2. Under assumption (i), the eigenfunctions of A are the Hermite polynomials on (R*)
0¹
5x(x)) = (-1)² ex
for each E N4-
Ox
For concreteness, the size, in ..g-norm, of the Hermite polynomials is computed in [28, Theorem 2.
where it shown that [WPella, S 272 01+0(1)))
(a1)a/2
Example B.3. Suppose that X is the d-dimensional sphere Sd def. {I RR+11 ||=|22 1} equipped with the (usual) Riemannian metric induced by inclusion into the + 1-dimensional Euclidean space Rd++1 Let μ be the normalized (uniform) Riemannian (volume) measure Tr.. Then, (x)) are an orthogonrmal basis of L consisting of spherical Harmonics (counting multiplicittie Jj E N4 for each eigenvalue E N+); that is the restriction of homogeneous polynomial f gd+1 + IR satisfying Aj = 0 to there sphere Sd. Spherical harmonics are not very large (in uniform norm) [17, Theorem 1.6] and one can show that || 11 S X (d-1)/4 i N4. See (2, Chapter 2] for further details on spherical harmonics.
.frr each
B.2.1 Sobolev spaces on Riemannian manifolds
Let (X, g) be a compact (smooth) Riemannian manifold, possibly with boundary 0x. For any E N., we define C2(M be the set of smooth functions f on X' satisfying
V du
and
f(x) = 0 (Vx E 8x)
(11)
Homoggeeeus Boundary Conditions
Square Integr-ll Derivatives
where μ is the Riemannian volume measure on (X, is the covariant derivative thereon. Then, the Sobolev space H3 (X, g) is the Hilbert space obtained as the completion of CT(( with respect
"Meniing that, there exist constants 0 < < C' such that: for each E H (Sd) we have c||u||ı S (()))))) S C|| 1|
22

---

to the norm
11 (x) def
fllez
Remark B.4 (The Sobolev Spaces H (X and (x' Observe that when X' is compact Riemannian manifold without boundary, i.e. when ax 0; then the condition f(x) = 0 for all in the boundary set 0.'' holds vacuously. In this case, this condition can be ignored, and the spaces ( 9) coincide with the usual Sobolev spaces H (X. g) for Riemannian manifolds without boundary; where H g)) defined much the same way Hy (X, K))) but without requiring the homogeneous boundary condition in (11).
A more convenient expression for the norm of Sobolev spaces on spheres can be arrived at by manipulating the definition of the Laplacian. We summarize this norm in the next example.
Example B.5 (Sobolev spaces spheres). Fix k N+. Following the discussion [2, page 120-121), the f E H (S g) if and only if the following norm
00
J:
2
def.
Ca) spectral decory
(12)
j=0
projection onto 8)th spherical harmonic
finite; where ca def. (d (d-2)/2. That is, the norms
|| l|x and (x)) [
are equivalent.
The key takeaway of Example B.5, is that the smoothmess of function on there sphere (8*, g). i.c. the largest for which f H (Sd g), can be expressed terms of the decay rate of its projection onto the basis of spherical harmonics. Indeed, this expression (12) implies that f H (S", g) only
if SSea f(r) p(dr) O(i + ca) -2 for all S > 0.
This observation smoothness of functions the RKHS associated to certain radial kernels, e.g. certain NTK limits. We generalize this argument, and use it to relate the spectral decay rate of kernel to the smoothnes/regullrity of the functions in its associated RKHS.
used in [24, Chapter 4] and circa [22, Lemma B.1] characterize the
B.3 Standardization operator
We require that the (X)) norm of the eigenfunctions are non-vanishing and non-exploding. Assumption (ND) (Non-degenerate L²-Norm).
Suppose that:
(i) Non-vanishing: 0 < infie[M] I|
(ii) Non-exploding: supse[M] (1gll < cc.
Again, if ( is orthonormal then (i) and (ii) necessarily hold and this is non-assumption. To generalize the discussion in Example B.1, we first define the linear standardization operator
: H + (2)
M (.. Σ (. We)a lbblll J. T=
(13)
1 (12
Example B.6 (Standardization Is Inclusion for Radial Kernels Spheres). In the setting of Exam- ple B.I, we have that (up to reordering) Vi.j = Vi.- Since, in that case, for k large enough on has H = H g) then A is simply the inclusion operator of H (gd .g) into 124).
In what follows, when assume Assumption (DR) (iii), will use (2) to denote the set of smooth functions the closure X of X' in the norm topology Ed Under Assumption (DR) (i)-(ii), use C (X) denote 8 (xt); that is, the set of smooth functions on the smooth manifold X.
23

---

Proposition B.7 (Identification: Spectral Decay and Standardized Regularity), Suppose that Assump- tion (DR) holds and that (2b)) are orthonormal in H.
Then, the linear operator A, defined in (13), is an isometric embedding when M & oo (resp. isomttric isomorphism when M = oc). Moreover, it characterizes the "regularity" of finctions in H via:
1. Sub-Expe Sub-Exponential Decay: If k. has infinite-rane Sefinite-rank (M = oo) and there exists an r > such that Kff, (1) S i- and inf lim ())
-+E ite
then
8-700
A(f) E Ho (2)
Ho
+ (x)
and A(F) E N (*)).
620
vd/2>k
Soboley Space Charucterization
C Spoce Description
2. Exponential Decay: If K has infinite-rank (M = o0) and there exists some T > 0 such that (J, (2) e then
A(f) E C (
3. Finite-Rank:
(i) If d'Assumption (DR) (ii) holds then: k. has finite rank (M < o0) then A(f) is smooth. (iit) If Asssupptinn (DR) (iit) holds then: has finite rank (M oc) then A(f) is real- analytic.
direct corollary of the first statement in Proposition B.7 guarantees that A preserves convergence. Consequentially, any finite-rank truncation or any sequence of learners converging to limiting function in the RKHS do so if and only if their standardized versions do; moreover, both sequences converge at the same speed due to A being an isometric embedding.
Corollary B.8 (Preservation Convergence Rates). (fx)) NEN is sequence in converging to some f E H then: for each N E N on has [N fl1x = A(SN) A(f)l123(R.)
We now are now prepared to prove Proposition B.7.
Proof of Proposition B.7. We first show that A linear isometric embedding (resp. linear iso- morphism). This allows us to relay the spectral decay rate of any function in 7 to that of its "standardization" A(f) in L2 (X). We then use this identification, together with results from spectral theory (see [1 [] for references) obtain our conclusion.
Step A is Linear Isometric Embedding (Resp. Linear Isomorphism):
Observe that A admits a linear left-inverse given by
B (x)
M
f= f= (f. 2 (f,.)))1())) d. +
Σ (f. ())) I1 1/. 2=0
1=0
In partieular, A is linear isomorphism if and only if M oe; since otherwise B is not two-sided (linear) inverse. Furthermore, is an isometric embedding (resp. isometric isomorphism when M = oo) since due the following. For each H we have that
M
Kif. (b) 11 (
|A(f)) ((())
(14)
1 Pigea2)
KF
(15)
|| 11721122000
M
Iif. vhr)ml?
1 |
M
ICS, (1)
24

---

M
(16)
==
= =II
(17)
where (14) and (16) held by virtue of (vb:) being an orthonormal basis of H. From (14)- (17) we conclude that for each f E H we have | |A(H)l)3(()) || Thus, an isometric embedding.
Finite Rank Kernel:
Suppose that M < 30. We consider two cases in Assumption (DR) separately.
Under Assumption (DR) (ii), [11, Corollary 9.28] guarantees that each to...... Dy is smooth. Since any finite sum of real analytic functions is again smooth then, in this case, A(f) is smooth.
Under Assumption (DR) (iii), [11, Theorem 6.8] each th....., .MM is real-analytic. Since any finite sum of real analytic functions again real-analytic then A(f) is real-analytic.
Infinite- Finite Rank Kernel:
Suppose that M 3o and fix > By definition of (v4) and of the Sobolev space (*))
have that: for each f E L (2)
[1 =
KS, vi) 1ye (n1 A) 10
(18)
Σ KI. 23 -7)"
Since f E (X)) if and only if (l is well-defined and finite. Consequentially. the elements of the Sobolev space (x) are characterized by the summability of the right-hand side (18). That is, for each f E (2)) one has
f Hx) + Σ 10, (1' <0.
(19)
By Assumption (ND), both 0 < C det inf (20ll1z(2)) and C def sulselmi ( < oo are well-defined, non-negative real numbers. Therefore, for every E N
0 < KS, wi)dd
< [(, vi)m <
(20)
C
C
From (20) we deduce that: for each f E (2) and every s s> 0
00
KL Xr <
(1- 10--x0 Axe² <
Kf (1-A)))
(elle3(20)
0 10
1=0
Consequentially, (18) implies that
A() ( + Σ 10.0) { <0.
(21)
Step Asymptotics Laplacian Eigenspectrum Under Assumption (DR) (ii), Weyl's law for compact Riemannian manifolds (see e.g. [11, Corollary 9.35I) implies that there are dimensional < oo such that: for each e N
(depending on d, X, and on g) constants 0 < C S C
2/d
2/d
Cwa
Da Vo(ot)
C Cw2
Va Vg(X))
00,
(22)
where Ug def. V((x E IRd ||0|| I 13) measure 1
4/2
and where V is the d-dimensional Lebesgue
I(1+4/2]
25

---

Under Assumption (DR) (iii,, Weyl's law (see e.g. [11, Theorem 6.27l) implies that: there are dimensional (depending on d and on X)) constants 0 < Owa1 S Cw:2 < oc such that: for each i E N
2/d
2/d
0 < Owal Pa V(()
S S Cw:2
00.0
(23)
Ca V(())
With some abuse of notation, for 1, 2. we write Cw for Cw. Cw. depending which of Assumptions (DR) (ii) or (iii) are being used. therefore, wild mild abuse of notation, we collect (22) and (23) into the following single expression:
< Cw:1 (ei va vxx)
2/d
S S Cw:2 (e))
2/d
< <0,
(24)
where the constant c > O is defined by
4//2 r(I r(1+d/2)
if Assumptions (DR) (ii) holds
7 4/22
if Assumptions (DR) (iii) holds
+(1+/22)
Combining (21) with (24), we find that
A(F) E H*(X) + Σ (f <0.
(25)
Pulling out the common 22// factor in all summands on the right-hand side of (25) we find that: for any any e (X') belongs (xX) if and only if
A() E HXX)
+
Kf 2, 20/d 00.
(26)
1=0
Sub-Exponential Decay: Suppose that there exists an > such that Kf,, vs)aa X i-" and Kf, vx)) i-+t = oo then (26) implies that
for every E > 0 we have lim
(1ord
(2) Ho (+r3 + (xx).
A()) Ho
<>0
If Assumption (DR) (ii) (iii) holds the Sobolev embedding theorem for Riemannian manifolds with boundary, as formulated [11, Theorem 9.26], implies that H (X) S
(²²(()) where S, d/2 > ky for some k, 2 be determined shortly; where for us (1 r)d/2. Therefore, dr/2 > kr. Consequentially, for each f H we have that
A() E N C* (X*).
rd/2>>k
2. Exponential Decay: Suppose that there exists some r > 0 such that kf,, v))x S e-ri. Then, then (26) implies that A(f) E N,so (x)).. By the Sobolev Embedding Theorem, in the bounded case ([11, Theorem 9.2.6))
A(f) E C (X).
26

---

C Master inequalities
In this section, we will present and proof the Master inequalities, which is crucial in argument.
Our approach bounds each term the bias-variance decomposition in line (5):
E. |0( + 0- 3 =B+V
under minimal assumptions.
C.1 More notations
We first introduce some more notations. We define the empirical covariance matrix:
Σ
-
X
x,X, E RPXP,
and denote by
del Σ 1/2 x R
the whitened/isotropic feature vector where F jzz Ip RRxx, Denote the whitened input
matrix by Z del. XI- Rnxp, then the of Z are isotropic centered i.i.d. random vectors. We introduce the notation of generalized vector norm, which will be frequently used in this paper:
Definition C.1 (Generalized vector norm). We denote ||v||M def. Vv matrix M and vector
Mv for any positive definite
Remark C.2 (Examples). Let v E TR and we have li v I, matrix. Another example is that the euclidean norm of equals to the Eorom of its whitened counterpart z:
| where Ip is the identity
|xx12 = TT 2 Σz = |
Furthermore, if M1 & M2, we have | I || In particular, since E < Ap we have
|i S A2 |v]|2-
Lastly, it convenient to write the expected values in a generalized vector norm: fix a distribution μ. an input block X E Raxp, where its rows are drawn i.dd. by μ. and denote by f = Em 8x. the empirical distribution of jr, then for any E TR", we have
Exzμ [(x] ) = |
Expp [(x T v) = 1|vl
Definition C.3 (Truncated Terms). For any vector R.M, write Vsa + VSA E R o
M- For any square matrix M E RMM write M = M
M with McA E TR
and My E ((MM-R)((M-A) Analogously, for any non-square matrix M RNX write M Mg: + M E Nxk @ Nx(M-N) Also write M. del
M + Ms E Nx(M-1)
and M.j MM,a) E NxU-0.
Denote A del. XXT + nnI, E Raxx For any N, denote
A = = + nAI, E 8
The symmetric matrix Aş plays an important role the analysis. Intuitively, when ie is chosen appropriately, A is approximately equal to scaled identity, with spectrum bounded by some constants from below and from above.
We introduce a few more definitions that have been used in the previous literature. Definition C.4 (Effective ranks [6]). Let & E N. Define two quantities:
del. Tr Tr( Ei d
R def. Tr
(Ei Σ X7
E>>klop
d4t1
T
Note that we have r3 < R₂ < 1 10
"eeee [6] for details.
27

---

Definition C.5 (Concentration coefficients [7]). Define the quantities: 11 |>> laap + 81 (An)
def. $1 2 Zck)
der. $1(22x Zgh)
Po.k
def.
sn (Ax)
S
8: (2 Zga)
En.
n
where s;(-) denotes the i-th largest singular value of the matrix.
To enhance readability, we will omit the subscript "n,& when the context is clear. The intuition of the concentration coefficients is that for fixed k E N and n large enough, Ç and concentrate around some constants; when k is smaller but scales with n, P converges to a constant, as it essentially represents the condition number of Ag- As mentioned earlier, the spectrum of A& is bounded. Therefore, selecting an appropriate k ensures that all three concentration coefficients converge to certain constants.
C.2 Statements and proofs
Now we are ready to present the Master inequalities, which are proved in [46, 7]:
Proposition C.6 (Master inequality for B, [46, 7)). Let ls E N be an integer. For any d E (0, 1), with probability least 8.
B < 1 + 55 +
100 B.
(525-2 + 2( 81
(As)) n²
_0 x
8
Proof.
We begin by bounding the terms that appear in Lemma H.8: plug in Definition C.5 Cf S.E.
since
$1 (AA
k
1
$1 (Z <k Esk
81 (Ax) 2 $1 (Z Z2x)2
n2
1
S
2pp55-1 1
8, (A 1/2 8k (Z ggx)²
s, (Ax)) )2 8k (Z 21
3g (g
81 (Z
2k 2sk)
1
81 (An)²
81 (Ac) 81 (1 756)
11²
(Ac)) n²
525-2
8n (A, k 1) [L Zz
Sh
Sk (Z
SR Zz2)²²
n²
sz UgA)
51
(Z
2zz)²
|2nx|lop
>>>llop 1
1
|| | llop 81 (A²1))
p
$n Sn(AA)
Sn (n(As)
71
n
Σ E llop
$1
81 (1 Igk)
$1 (Ax)² -|
n
81 (Z Zga)
n
$ 2
$1(
sn (A k
1/2 8/ L Zgz))
sn (Ak)
n²
8k [Z] 2 Zgx)) 2 81 s1 Zgk)
n²
we have
|| 0 S 2
B < 100
n
+ 52 22-22 (Ax))
||0%x|
2
n²
(27)
+ 0
+ P525 1 11 (Ax)
|10
| 2
n²
We regroup the terms into:
+ s1(n))
B < 10 E.. + (02535-1 + pp)
(28)
n²
By Lemma G.6, we can further simplify the expression into high probability bound: for any 5 E (0, with a probability at least 1 - 5, it holds that
B < 1 2 110 E + 2 (Ac))
1
(29)
5
n2
x
Note that 1/8 > 1 and we obtain the result.
Altermatively, define smaller A def. max(m] 23>ll (nAx) = e(n) | >Dsxllog)). the two definitions differs only by constant.
11 - 1 (2)(A
If s(s))
(A,)
sn (An)
28

---

Proposition C.7 (Master inequality for V. [46, 7J). Let ls E N be an integer. Then the variance is bounded by:
v/02 S x² ( Tr E
PR 2
Tr S
n nRe 2
where x² del E [e2)
is the noise level.
Proof. We start from Lemma H.9:
81 (A )
V/o²
5k
+ "T
sn ( S 5k X 5/
1/2
8ı (Ax) 2 Tt ZrZ
2
| 12
Tr D
2, (Ax)² 5K Z ZEn)²
8n (Aa)
n² b>> lrpp
Tr(ZgK 2Jd
Tr|x, E>AX
8x SA ZgN)²
n E> 18p
han (2
Tr x
Tr Th 12 Tr
Sz SA ZZe)2
n Tr
Σ I Tr[E>
k
Tr/X E x
TA [E)
sp²
25 (5--1
Tr (
nR (E)
k
Tr 33 Z [
rx {x)
p²
(5
+
n
n Tr E
nR E
(ZZ,, Zen)
del (Z Zek)
del a E (As)
Tr Rr Es 1lop
where En,
Sn,K
22 Zgn)
Pa.k
(At)
Th
Tr]
TH
C.3
Sanity check
Recall that B det ||@(x0)) 0-13. Let le E N be integer. For any 5 (0, 1), with probability least 1 - 6, we have
x)2
target's tail
26 1+ 2
(A ) (525 +
B <
100
E2 +
0 <A
(30)
8
n²
constant
constant
target's head
We that:
1. the regressor barely learns the tail the target (the eigenfunctions with small eigenvalues), thus the first term [ I in the upper bound is just multiple of the E-norm square (or
12 -norm square in KRR setting) of the target's tail;
2. the second term indicates that the regressor leamns well if the ridge À is small, showing the trad-off between (noiseless) interpolation and regularization;
3. the term ||0 ||0|+| zgi
corresponds to norm square of the target's head in the interpolation
space H². This term will explain the so-called saturation effect reported in [29] where the bias ceases to improve once the source coefficient in Assumption (SC) surpasses Consequently, the bias term B bound in Table is closely related to the constant min s, 2.
29

---

[46, 7] also derived non-asymptotic bound of V. Recall that V del E. [10(e)]13]
Let &
be an
integer. Then
Tr Zr
D k.
Th (2)²
VS
2
(31)
TR
Tr
n nR (
noise level
=0(
We see that:
1. the upper bound is proportional noise level o² E 2 0:
2. we will show later that for n large enough, the second term is approximately & hence the decay rate of V is at most On, (n-
The derivation of Eq (30) and (31), which we refer to as the Master inequalities in this paper, is purely algebraic, and the statement holds regardless of the assumptions the eigen-decay and the features. One can optimally choose the integer E N to achieve a tight upper bound, as we will demonstrate later in this paper. Surprisingly, the Master inequalities alone sufficient to establish tight bounds for most cases under various settings.
30

---

D Over-parameterized regime
In this section, provide the proof for the upper bounds presented in Table 1. For all the statements in this section, the big O notation Ô (-) can be replaced by O (-) if * 2r.
brief summary of the propositions can be found in Table 3.
Ridge
strong
weak
Feature
(F))
(GF)
(IF)
(GF)
B
Proposition D.2
Proposition D.6 Proposition D.5+D.6
Poly (PE)
V
Proposition D.7
Proposition D.8
B
Proposition D.3
Proposition D.5
Exp (EE)
V
Proposition D.9
Table Brief summary propositions derived in Section D used for proving the upper bounds on
Table 1.
D.1 Bias under strong ridge
Proposition D.1 (Asymptotic upper bound of the bias term with polynomial decay). Suppose: A = 4 (k-1-2), |0%] = O² (k-") and X = O (k=²) for some b, > O. Furthermore, suppose Assumption (GF) (or resp. (IF)) holds, and 8, E, < = On, (1) with probability at least 1 - yp Then, & (or resp. ô --
for any t (0, 1], with probability least by:
- e),, the bias is bounded
B = Ön (p2n
for some constant
del min + u), min + Ia] 1(2 + 2r)+3 >
(32)
with with following lower bound:
[2r + a) 2(1a -1 2(0 1+ b < la;
C2
(33)
(t2 + a), 26(1 + a)}
bb 1 + ta.
Proof. For simplicity, we only prove the statement for all a, except when a 2 2r. In such case, the argument follows similarly with O (+) replaced by Ô (-)-
For any k E N. pick k @n., (n") for some t E (0, 1]. Suppose the event 6, 5. On, n (1) happens, then:
B
On,
[ 1- (1 +D)
16 +
+ nb C2 Tr
2
|10 11
5
(34)
k (2r+a) + n k ) 2 0²
(12ta-213t) 27)+ )
On.
(35)
On,
0²
n (2r+t) + n + n (]tae)) m n((2ta-2r))
(36)
On,
(2r
2 (b. 122 (2tt-22))
On..k n.
(pa
(2r+a) 2 mmin
On.
min min (00__-+aa)))mmm0_00aa]--))a0
where apply Proposition C.6, Lemma G.8 in line (34); apply Lemma H.10: ||0r
O (k((+a-2r))+ where x, = maxf2, 0}, as well as plug in Tr(E>a] = O (k-a) in line (35); we plug in & θn, (n') for some E (0, 1] in line (36).
31

---

Hence the bias B has a decay in form of On (p"n 0) where
( + a), min (, ta} t(2 a
is constant defined in nested minima and maxima. To bound C' from below, we make two case distinctions: b ta 2 1
For < 1 + la, we have
C = ( + a), 26 t(2 -
o)) 1 a 2r)}
2 1--22 2r
m))
2 + a < 2r
20
d)) aa) 2 ())
2(ta + b]}
.2+ a 2r
+ + < 2r
20
d() +a) 2 + 1 b]} min(t(2+a+o)) 26}
2 a+a23 2r
22 2r
a(2r+a) + 2
(2min(ta+ b.
2
(((2r+a) 2(ta + b)
2
2 (2min(b- (2min(b1144,
2
[t(2r + 2(ta +
2
2(b 1+b)
<2
2 min(t(22 + a) - 2(ta -
b), 1
For b 2 1 + to, have
C = m (0)00-++))))1-----((2---------0-
+2+a- tt) - 2r)}
.2 a 2 2r
mmin(((r+ac)]]+tta))
2 a < 2r
((1n( + - t)}
2 12220 2r
())
2
2 a 2 2r
minn(2(t + ta), ta))
2 2r
((2r+ a 22 2r
2( ta) 22 a < 2r
2 min/f(2r + a), 2f(1 + a)}.
Replacing C' by its lower bound, we obtain the claimed decay.
Proposition D.2 (Asymptotic upper bound of bias under strong ridge and polynomial eigen-decay). Suppose: A = O (k 1k---), 10%
On (k-r) and x O (k (k-)) for some a,r >> and b e (0. 1 + a). Fix constant 5 E (0, 1). If. additionally, Assumption (GF) (or resp. (IF)) holds, then, with probability at least 1 5 - o on (or resp. 1 - - 3e -in),, the bias is bounded by:
O (n" min(sb,26)
with del.
14a
Proof. Use Proposition D.I as the backbone, and use Propositions G.1 and G.2 obtain the high probability guarantee for E.5 On,k k (I). Then for different value of b, we plug different values
32

---

of E (0, 1] and set & = n, (n'), such that p = Pro,k = Ön (1) by Proposition G.3, in order to obtain different decay rates of bias.
Assume b E [0, a 1). Pick k kk,n (n') with t Tea" As above, it holds that p A, (1) with
b_ high probability. This time, we plug in I. == I4a in the definition of C. By the choice of b, we have
b < 1 + ta and hence
C def min a), -00
2r)+}
min
2r)+)
2)) 2r))
2 a 2 2r
[min(((2++a))2)))
2 < 2r
20
((2 + t(1 + +a))
2 a 2 2r
min 26]
2 2r
mminft(2r + a), ((2r + a)}
22+
min(t(2r (0 a),
2 a < 2r
+ a)
Finally, assume = a - 1. Pick k = Ok.n (n²) with t = Ita
b = 1. But this time, since b 2 + ta,
b we plug in t 1ta into the second lower bound of C line (33):
C 2 min a), 21(1 a)) min ((2r + a) 2b(1 + a) 1 1+a
minfsb, 26}.
(37)
L
The argument for exponential decay follows analogously as above. Recall Assumption (EE): A
O& (e aak) for some O. Suppose 18% O₂ (e (k) and À = O, e bn) for some b, >> 0. Then the asymptotic bounds follows similarly to the polynomial case. For sake of completeness, in this section, list out some propositions for illustration.
Proposition D.3 (Asymptotic upper bound of bias under strong ridge and exponential eigen-decay). 04 = O2 (e-rk) and X O, (e (c-mn) for some a, r > 0 and E (0, a).
Suppose d = O (e (e-ak))
If Assumption (GF) (or resp. (IF)) holds, then with probability at least 1 - on (t) (or resp. 1 - 3e 3e ), the bias is bounded by:
[Onk (e min(,,2)6n
+ 2r
B
(38)
On,, (e-sbn ne 22m)
2r.
for some constants > 0, where s
2r +1> 0 is the source coefficient.
Remark D.4. Note that the factor n in the case of a = 2r does not play a big role asymptoticalll: by taking a slightly smaller i < b, the decay is exponential in bn.
Proof. By Proposition C.6, with probability at least (or resp. 1 1- e)), the bias is bounded by:
1 + 25 + B <
((((A)) n2
|10 1 =c( 2
|
(39)
5
By Proposition G.I and G.2, there exists some c >> such that, if c&akk log S n (or resp. k/c S n), then with probability least 1 exp
(- 8 (or resp. 1 2 exp (-cin)), holds that
fn
2i Gk S C2.
The extra factor serves only for simplification purpose and has effect the choice of b.
33

---

Fix ò (0, 1). With probability least 1 8- exp (-hxe) cen (or resp. 1- -
-- -2 -1)))
it holds that:
81 (A(s))
B = On.
P
110 1105xlBEs0
10
n
O n
(p
k (2rta)
+n + (c (e- $105211
where the last inequality comes from Proposition G.4. For b set def & < 1.By Proposition G.4 again, we have م O (1) with probability at least - On (+) (or resp. e²)) Set del 2r be the source coefficient and we write:
B On,
e
(er+oo) (e (e-bn)² cla-2r))
1=1
On.
abn
+ E 2bn
laa-2r)1
1=1
On,k sbn
26m
2la-2r)
On,k E obb
+ E 2bm
a 2r
On,k (e-obn
+ e 22n
0 < 27
On, (e-abn
+ - sbn)
0 > 2r
On,k (e obn
+ ne - 26m)
a 2r
On,k (c-shn + c 2mmb
a < 2r
On,k k (e- mii((.22)b)
a + 2r
On,k (e-sbm ne ne-=bn) 2bn)
a 2r.
D.2 Bias under weak ridge
Proposition D.5 (Asymptotic upper bound of bias under weakleffectively no ridge for 8 > 1). Suppose Assumption (GF) (or resp. (IF)) holds, and the source coefficient 1. Then with high probability, the bias has decay:
B = Ön (A (xmin(a.1). for = Sn (An)
Proof. By definition, rewrite the bias into:
B- 0 0(x0))
100 X [XX
+ - 'xx0"))x)) 2
| - (XX + nAI,) -
0"
(40)
P
Denote PA def. X T (XX ndI, ) -1x E RRXP, By NMerman-Morrison-oodddee formula,
xxTxx -1 = (NL, =>(M +2)
I1 (I, (nd) - x AIp + n
a positive definite matrix such that the matrix I PA is monotonic increasing in that is:
0 * I - PA I P I..
(41)
34

---

for all Ā 2 X > 0, since the map A H A+
A_
is monotone. Hence, for t E mi, {)) 13
B |1Tp - -Px)0'
(42)
(1, PA)O
-- (11-1)/2001 1/
Σ (I, - PA)E (1-1//2
<
op
(1, 1/2
P PA) (2- (I,,
||0-||=-- x
Σ 21, P2)
[12 - P2) 12-02//2
11/2 5
(1/22
-10011 |1
op
<
Σ 1/2 (I, 1/2
12- 1/2
|| PA (t)((11))) (1-1)/ D 11/22
110 1
(43)
<
E 12 14 PA) 1/2
[1 11/2 (Ip - -Px) (t- 1)/2
110 ||
(44)
op
<
3 E II, PA)
|X// (Tp Px)
1(1-1)
2
(45)
up
up
21
M [1, - PA) 1/2
110 10-1 E
Σ (1, - PA) E 1/2
(46)
op
Σ (I, P Σ <
|00
(47)
where rewrite line (40) in line (42); apply the monotonicity from line (41) in line (43); the fact that ||,, = |M2M] up for symmetric matrices M,, M2 in line (44); we use Lemma H.17 to pull out the power (t 2 1) from the matrix to its operator norm in line (45); we use the fact that
M M. /2
M M// /2 (M] /2 MM/ /
MM/MM, /2|
for any positive definite lop
symmetric matrices 14 M1, M2 in line (46); by the monotonicity from line (41) again and the fact that / is positive definite, choose Ā 2 À > dn to be strong in the sense of polynomial/exponettall cigen-decay in line (47): À x= On (n-1 for polynomial case and Ā = O,, (e)) for exponential case.
Let E SP-1
RP be unit vector such that | PX)
| -0--P. PX)EI/2/|1
[| By definition, we have
12/2/ 2
Σ Σ-1 = =1iv122 = < <o,
hence the vector 11/2 lies on the interpolation space H Note that the expression
-2)) 1 - op
| - -, 2y 11 = (I, - Pz) (2))(2("/2)) (Σ>K2v)
is just the bias term of another task 1/2 with source coefficient 2 and ridge Ā == Qn (An) on the same dataset X. Apply Proposition D.2 with polynomial decay and Proposition D.3 with exponential decay that new task with strong ridge S, with high probability, the above term has a decay rate:
(I,
P3 op = I|a, P3) 1
(x>)22)
Ö, (X2)
(48)
2rta 2r
Assumption (PE) holds
Recall that
is the source coefficient.
+ 1
Assumption (EE) holds
14 "Same as above.
35

---

Plug in line (48) into line (47) to obtain the decay rate of the original bias: with high probability:
B On (( [ PXI
1/2
On (112) O, (A%)
op
This holds for any E min,,ns, 2)), hence conclude that
B Ön (A
For polynomial eigen-decay, we can still apply the Master inequality for B obtain another upper bound:
Proposition D.6 (Asymptotic upper bound of bias under weak/no ridge for any > 0)- Suppose:
A O₁ (k-1-a), 10g1 Ox (k") and X O& (k- for some a, b, > O. Fix a constant
5 E (0, If. additionally, Assumption (GF) (or resp. (IF)) holds, then, with probability at least
1 - On logn
(or resp. 1 5 - 31 the bias is bounded by:
B = On (n
where
C (min - a), 2- a}) bE [1 + a, oo]
(49)
(or resp.
min + a a)}; b E [1 a, oo).)
(50)
(or resp. = n/cc for some constant 1) and control E, by Propositions G.1 and G.2. Now, by Proposition G.3, with probability at least 1 log since 2 + a,
Proof. The proof similar to Proposition D.2. Take Ok.n log
p == Ön, (n").
(or resp. On, (1).) Now by Proposition D.1, since E [1 + a, oo) and we choose = 1, with high probability,
Ōn, (p'n-min min((((2+t0)2((400)))
(51)
Plug in p Ön, (na) and = 1 to obtain:
= Ön,k (n- min
(52)
The index in the above bound can be negative, causing the upper bound vacuous. By line (41), since
= [I[I, - -P I || there a trivial bound that B O, (1). Combining both results, have
B Ön,k nn (2-(min(2(r-a)222 (000rrrr),2aa111.
(53)
D.3 Variance with polynomial eigen-decay
Proposition D.7 (Asymptotic upper bound of the variance term with strong ridge). Suppose
A O₂ (k-1-a), 00 O₂ (k-"), and X = Or (n-*) for some a,r > 0 and E (0, + 1). Furthermore, suppose Assumption (GF) (or resp. (IF)) holds. With probability at least on (2) (or resp. 1 - 3e 30-m1)) 91)), the variance term is bounded:
V On (N
for E N large enough.
36

---

Proof. We divide the case where Assumption (GF) or (IF) holds.
Suppose Assumption (GF) holds. By Proposition G.2, there exists constants 1, e1 >> 0 such that, for k < elogn
with probability at least - Se - c/n/k holds that
kn,ki Sn,k On, (1).
Also, by definition, it always holds that
T 1 E
E Σ1
11
Σ 2
S sup
Ba -n,t (1) Tr Tr
TT
Tr Tr
By Proposition C.7,
02 (1x
Tk (2)2
V/0² = On, =Onk
nRx )))
Let c >> 1 be the constant in Proposition G.3. Choose k = Ita n S <clog
for E N large enough.
By Proposition G.3, with probability least 1 On (7); + (Ak) On,k Σ > op (As)
nd + +nd nd nd
def.
On,k (1)
by the choice of (0, 1 + a). Combine the result with Lemma H.12, with probability at least 1 On ( have
k
22 On,
1++
On, (ntia-1)
V On,k
kn
71
conclude the claim.
Suppose Assumption (IF) holds. The argument follows analogously. As in Proposition G.2, choose
k b < n/c for n E large enough. With probability at least 2e- we have
En,ki Sn. On, (1).
By Proposition G.3, with probability at least -
p p= 2n (1)
by the choice of b a 1). By possibly choosing 1 3e - we have E, S.P bounded. The rest of the argument follows similarly.
constant 0. with probability at least
Proposition D.8 (Asymptotic upper bound of variance term with weak/no ridge). Suppose A O (k- (.) 10%1 = O& (k-"), and X = O, (n (n=)) for some a, > 0 and E a + 1, co). Further- more, suppose Assumption (GF) (or resp. (IF)) holds. With probability at least 1 on log (or resp. 1 - 3e c),), the variance term is bounded:
V= O, (n²a). (or resp. V (1).)
Proof. We divide the case where Assumption (GF) or (IF) holds.
Suppose Assumption (GF) holds. By Proposition G.2, there exists constants 1, c > 0 such that, for k < elogn with probability at least Se -enc/n it holds that
En,k, Sn.k On. (1).
Choose = n lelog
Then by Proposition G.3, with probability at least On logg holds that
Ön.k n= + n + n 6+1
Ön. (n*)
n + n
by the choice of b. Moreover, since clogm Proposition C.7, have
) 2 On. (p² ( rx(E) n
On. ( (,20 k -
= -n. 2n
n2
37

---

Suppose Assumption (IF) holds, choose k = |n/c] for some constant c > 1 as in Propositions G.3. with probability at least 3e-es cin it holds that
p nn (1).
Then by Proposition C.7, we have
(0² h: rx(22)2
))
k n
= On,
- nRx (Σ)
Ün, (1).
D.4 Variance with exponential decay
Proposition D.9 (Asymptotic upper bound of the variance term with strong ridge). Suppose Av= O (e-ak), 10% = O (e-rk), and X = =6,, (=e-bm) sorsome some a, >> 0 and E (0, a). Furthermore, suppose Assumption (GF) (or resp. (IF)) holds. With probability at least 1 - (2) (or resp. 1 3e "1 J, the variance term is bounded:
V On n2 (n=-1)
for n E M large enough.
Proof. The argument is similar to Proposition D.7. The difference is the bound of and the second term in Proposition C.7: if g, = On,k (1), by Lemma H.12,
k
Tr E
Th E)
V/0² 6² 555--
71
ES
RR
0²
On
+
n
= On,
p
Choose 1: == 1 1. Combine Proposition G.4 and the above inequality to obtain the result.
38

---

E
Matching lower bound
In this section, we provide the proof for the matching lower bounds presented on Table 1, A quick summary of propositions can be found in Table 4.
Ridge
strong
wcak
Feature
(IF)
(GF)
(IF) Proposition E.3
(GF)
B
Proposition E.3
Proposition E.1 for 8 E [1,2]
Poly (PE)
V
Proposition E.5
Proposition E.5
B
Proposition E,4
Proposition E.1 for E [1,
Exp (EE)
V Proposition E.6
Table 4: Quick summary of propositions used for proving the matching lower bounds on Table I.
E.1
Bias under weak ridge and source coefficient between 1 and
Proposition E.1 (Asymptotic lower bound of bias, Proposition 4.4 in [31], Theorem 3.4 [33]).
Suppose Assumption (PE)(EE) holds. Then
sup
B 2n (AH))
1 $1
where s is the source coefficient.
Remark E.2. Note that for both polynomial (with 2r + 2 a) and exponential decays (with * a),
by Proposition D.5, have B O (X the upper and lower bound matches.
max Aax(x)2)) for source coefficient 1. Hence when [1,2].
Proof. Recall the expression of the bias in line (40):
0 - 0. (1Ip PX)00
where def. (XXT
ndIp) -XX. Recall the source coefficient s satisfies: ||0 ||
co. By
definition of operator norm, we have:
sup
B =
sup
I[(p P2)0
0 1
<1
51
1///2 (I,
sup
10 10-1-
2
/ - -P) (1-1))11)))) 1)/2
/ 1/22 E
1)/2
By [43], [M] - M2llop op 2 s.+1 (M,) for any operator M, with rank at most n. Note that Px E
RPxp is of rank n, hence
E0/2 2 ( (-- 1)/2 2
(>x12)) S2 (Aa))
sup 1g
B
op
E.2 Independent features and prior signs
Instead of bounding the bias from below in the worst case scenario, we can also bound it in average sense. this case, we need to pose an assumption on the target coefficient 0-.
Assumption (PS) (Prior Signs). Assume target coefficient O" E TRP is drawn from a distribution i where entries 0% 's are drawn independently of each other and have the same distributions as the random variables 0% s.
39

---

Proposition E.3 (Asymptotic lower bound of bias with polynomial decay and independent fea-
tures). Suppose Assumption (PS) holds and ) Or. (k (k=1-- (6-1-)), Eg. [(e]] Oz (k=21 and
= n (n ") for some a, b,r > O. Fix a constant ó E (0, 1). If. additionally, Assumption (IF)
holds, then, with probability at least ő 11e 11e
11 the bias is bounded by:
Eg. [ = On (n (n-bmin())))
for def 2r+ta Ita
Proof. By Lemma H.14, it holds that:
Ag [B)))]
Eg- [8] 2
Ais A 1)-1 1|20012)
Hence, we want to bound the term 8n sn (A-1) and || from above.
If Assumption (IF) holds, then apply Lemma G.7 A- instead of A, I I,... p. with probability at least 1 - 2e"
(A [In (ndn); On (ndn+1);
ifl > Ωn (add) = Ur (Tr(E>n))
if S
By Lemma H.7, with probability at least 1 2e "e we have,
| 2 S e17, VI = I...,,.
Plug in the above two inequalities, by union bound, with probability at least 4e
AxE [(0)]]]
AxEE' [(0))
On
(1 + Ays, A ()- | 12
(
ndy Antian
Tr 2+ for any k. If we choose & n/c for some constant such that A y lly On (ndn), then Tr Tr] On (Tr(Exn]). Hence
where тк
A [077)
AelE [00))]]
Sn
(1 + Aus (A A (A- 12/112)
1
ndy Netira
By Lemma H.15, with probability least n
XE [00))
Eg [ Pn
+
ndi AEt1tk
where B is defined as in Theorem H.16. since ты fraction F' +.., (1) and Fx satisfies the condition of Theorem H.16. By Theorem H. 16, we have upper bound B matching the lower bound B:
Th Tr
kA Ax
O (k)), hence the
nd Tr
2
B = On
100 +
0
Ez
n
40

---

By Propositions C.6, D.2 and D.6, we have, with probability at least 8 - 3,
B = On 13) = On (n bmin(s,2)
All together, with probability at least
8 3e -0n n n..
Eg. [3]
S2n ( S2 n bmbim(2)))
Proposition E.4 (Asymptotic lower bound of bias with exponential decay and independent features un- der strong ridge), Suppose Assumplion (PS) holds and A O₂ (e-ak), ) Eg. [[0g) O2 (e-2rk) and À On (e-bu) for some a. 0 and b E (0,a). Fix constant 8 E (0. If. additionally, Assumption (IF) holds, then, with probability least 1 8 Te the bias is bounded by:
Eg- [3] 22n (e (e-hamin(s.3) min(s.2)
for det.
Proof. The proof similar Proposition E.3. By Lemma H.14, holds that:
P
A [(0))
Eg-
B
+ Ais (A 1) - 2'
By Lemma H.7, with probability least 1 - -n, we have,
||z:| 2 S cin, Vl = 1, 1,..,,.
By the choice of b E (0,
sn (A-1) = Qn (ni) Snn (ne -bn) Sn (ndn+1).
Plug the above two inequalities, with probability at least 22
AE [()))²]
A,E [(0)
AEE [(0))2]
S2p
22
(1 A15 A -1 |2:12)2
(1
2
1 An-iPn
Xn+i
where 7%
Tr E>
Ox (1). By Lemma H.15, with probability at least
-n
XE [()))2]
Eg- [B] = Ωn
+
mdi Au AE
B
where B is defined as in Theorem H.16. since
O& (1), pick such that rk > 1. This satisfies the condition of Theorem H.16. By Theorem H.16, have upper bound B matching the lower bound B:
Tr Ex [S
100 + nd (nd+Tr
Tr/Ess]
2 0
1 x
B On
n1
41

---

By Propositions C.6, and D.3, we have, with probability at least 1 - 8 3
B = On B = On (e bn min(s.2))
All together, with probability at least - 8 - -3e -1 4e
Un ( (e-bn
Eg
[
B
Lemma E.5 (Asymptotic lower bound of variance with polynomial eigen-decay and independent features). Suppose A = O₂ (A=1-9)), x= (n="). Additionally, suppose Assumption (IF) holds.
Then with probability at least ce -n/c, it holds that
V Ωn n1- 14a
strong
Qn (1)
weak
Proof.
This is consequence of Propositions C.7, D.7 Lemma H.13 and Theorem H.16: with
[n [n
X strong we have
probability at least 1 - - by choosing k
n/cc
À weak
On n1 On (1)
1+ rea
À strong
V
O, (V),
À weak
Tr 2
where V
defined as in Theorem H.16. Since the polynomial eigen-decay X satisfies the condition in Theorem H.16, we have
m+ E
V On,k (V).
S2 I+ rea
À strong
By Lemma H.13, V
By taking larger constant 0, the above
[2, (1)
À weak
events hold with probability least 1 - ce n/c.
Lemma E.6 (Asymptotic lower bound of variance with exponential eigen-decay and independent features), Suppose Å = O (e -a),,,, X x= Or (e e-"n). Additionally, suppose Assumption (IF) holds. Then with probability at least 1 ce -n/o, it holds that
V On n -1 riu
strong
O, (1)
weak
Proof. The proof follows similar pattern to that of Proposition E.5. Ensure that the exponential eigen-decay also meets the condition outlined in Theorem H.16. Consequently, V. O,,k (V), and the remaining argument proceeds accordingly.
42

---

F Under-parameterized regime
For the under- under-paramettn parameterized regime, one can clearly use the Master inequalities in Section C to bound the test error from above by setting k p n. However, one prove asymptotic convergence in the following way.
we first prove the convergence of the empirical covariance matrix.
Lemma F.1 (Convergence Σ). Suppose Assumption (GF) (or resp. (IF)) holds. Fix an e E (0, 1). Then there exists constant e such that, for p < n²- least On (n="), holds that
elogn (or resp. nnttt/// with probubility
I
1 Z
Z
=
Σ
Σ
Onp
n (n=
up
op
where E del E Xx
E Rexp and
Σ
del
Ei=
X Rpxp.
Proof. We argue similarly as in Proposition G.2. Fix an E (0,
Suppose Assumption (GF) holds. We have | S 3pp by definition of Bg. Apply Theorem H.3 on
the whitened input block Z E En x there exists some constant > 0 such that, with probability at least 1 - 2pe-pee eft² we have:
S VT -ύ- - 1- S sy(2) S (
By setting / = log n and the choice of p <
n'-c clogn
with probability at least 1
on log n. we have
vnl
Bp n=
5p (Z) S (1 S Vn 1 V
Bp 201
n
201
Hence, for large enough, with probability least 1
cn log it holds that:
2
1
23p
On (12
I
Z
Z
71
201
op
and hence:
Σ
<
Σ//2
I
1 Z Z
Σ
1/2
op
op
12
Up
op
29p
1/2
1/2
201
313p n
On (n/2
Suppose Assumption (GF) holds. By Lemma H.7 and union bound, we have ||z.1/2 < 2p for all = 1,..,, with probability 2ne-ou -inn When this event happens, apply Theorem H.3 on the whitened input block Z E RRxp, the rest of the argument follows similarly.
L
Proposition F22 (Convergence of the bias and variance terms). Suppose Assumption (GF) (or resp.
(IF)) holds. Then there exists an e E (0, 1) and a constant such that, for p < clogn (or resp. P < ni-- (ol-t/c) /c), with probability at least 1 On (n="), it holds that
1-
P
X (A + X)2
B On.p
1
On,p
(A + 2)2
7
43

---

Proof. We begin with B. By line (40) and the formula Mi¹ -22' = -M (M - 22)M2
rewrite the bias term B as:
B = 1TT - 11)0115
A(AI, + ----0-1 |
= - + Σ)-
(AI, ()
- + +E) +-)- 0- 0=1
Denote
A = (É - {AI, + -ン
Note that
A
11/2
-z 1,
1//2 1/2 + +Ip) - 1/2 -1g1/22
up
72
1
Z
Z
I
||(EE=++ + 11)
/ 1/2 Σ 1/2
n1
up
op
n 13)
On
We apply the matrix difference formula iteratively:
E +
Σ}(E + (I))
= -
= =E+ -1 - 1A) A
= AI -1 A
t=0
we write:
B = A + (I xI,)) M
|> ((AI + Σ)- + -AII + -
(AI, + Σ)
0.
A(AI + -00 + +X(
+ AI,)
-1 A
2
A(AI + E)
Σ A'
0-
1==
Σ
OnP (IA(AI, + -)-
Σ
Finally, write
P
du (0))
|AAII + +D)
X2
1=1 (At + 2)2
44

---

Now we argue similarly for V. By Lemma H.19:
V
Ex xx
| + AIp)
x
$
2
Excuut
E + AIp)
-1
Σ
A x
1=
T
20
Ex
X
(I)
(E+
-1 Σ
A'x
1=0
1=0
T
8
8
Ex
x
Σ
(A + X1)+
Σ
A'x
11
0² ++
[ + On (14ll
We argue similarly as in Proposition F22: with probability at least 1 - O, (n-), we have
0
V = On
(A
h=
Plugging in the values of n, p.p and other metrics a, r in Proposition F.2, we can obtain the
45

---

G Concentration of features
In the following, we shall give sufficient conditions to control the concentration coefficients Ço,ks Sn. and Pn.k- Note that Pr,k, and Én, depends on the whitened/isotropic features but not the spectrum Σ. We start from the easiest to the most difficult.
Proposition G.1 (Control on En,.). Let & E be an integer. Recall that En, det 21(Z2, If
Assumption (GF) (or resp. (IF)) holds, then with probability at least - 2 exp (- (020 (or resp.
1 2 2exp kn))), holds that
En,k 2 2
Proof. Since the largest singular value is larger than the average of the singular values,
Sn def. 81 (Z
Zen)
Tr Tr
Zgal
Tr TriZ Zenl
71
n
kn
By Lemma G.5, with respective probability,
1 Sn,k 2
2
Proposition G.2 (Control on Sn,k), Let k S be an integer. Recall that Ca,k 5. 75sk)
If
co Zzn)'
Assumption (GF) (or resp. (IF)) holds, then there exists some
>> such that, if cf log S (or
resp. k/c S n), then with probability at least 2 exp holds that
- (or resp. 2 2xxp (-c1n)),
m
Dx
Sn.k S C2.
Proof. For the case where Assumption (GF) holds, see Lemma in [7]. Suppose Assumption (IF) holds, then by Theorem H.2, there exists constants Ci, C2 O, such that, with probability least
1 - 2exp (2)) the spectrum of random matrix Zgg B is bounded:
Vn C2k - S sx (z S $ (Zek) S Vn C2k +t.
Set v and
- that if k.cc S n, the bound becomes: 16c5
3 V sx (Z<x) < s1 VVn.
and hence Gn. < (Zv with probability least 2 2exp -.. Set and C2 = 6 to conclude the statement.
Proposition G.3 (Control on Pr,k)) Let le S n be an integer. Recall that Pa.k del n 11, +8, (Av)
8n, $m1[AN] (Aa)
If Assumption (PE) holds and Assumption (GF) (or resp. (IF)) holds, then there exists some C > such that, if clogn (or resp. k nf/c), then with probability least O, logn
(or resp.
1 3e ")), holds that
Pn,k Ön (n (or resp. Pn,k = On (1).)
If X On (n (n-b) with b E (0, 1 a) and Assumption (GF) holds. If [ni with probability
least 1 O, (1) it holds that
Po,k O, (1).
46

---

Proof. The statement where Assumption (GF) holds is proved in Theorems 4 and in [7]. The statement where Assumption (IF) holds can be proved proved via Lemma G.7: since:
E>pllop (Ax)
Sn (Ax))
ndA + nd
OKn
ndn+ + nd
ndd
Okn
ndn+k
k k-1-a
OKn
(n+
Ok, (11+ (1+n/k)(
Ok, ((1 + c) (ta)
OK (1).
with probability at least 1 3e
Proposition G.4 (Control on Pn.k under exponential eigen-decay). Let S n be an integen. If AE= O₂ (e-ak), = On (e-bn) for some a > O and b E (0, a), and Assumption (GF) (or resp. (IF)) holds, choose k = n then with probability at least 1 - (#) (or resp. 1 exp (-n)), it holds that
$1 (Aa) On (ne-bm), Purk O, (1).
Proof. For the case where Assumption (GF) holds, by Corollary in [7]. with probability at least On (2), holds that
log k Tr[E>a] + )
(Ax) = On, AA+I+
On,k (n (e-ak + E bm))
On,k k (n ( aa- + e-bn)
= On (ne-b
For the case where Assumption (IF) holds, the upper bound of $1 (A+) is proven in Lemma G.7. In both cases, the derivation of bounding p is the same:
> loop + (Ax)
Σ
>> op
81 (AE).
ne /ne-bn
p
Sn (A))
nd
Onn.
nbn
On.k (1).
Lemma G.S (Lemma 1 in [7]). Let l be an integer. Suppose Assumption (GF) (or resp. (IF)) holds.
Then with probability at least 2exp
(- 28, n2 (or. resp. 2 2exp (-cikn)), it holds that
kn S Tr Ze - 2 kn.
Proof. If Assumption (GF) holds, then
n
Tr Tr Zcrl Tr Σ ((zz)) s Bykn.
Set M 3gk and by Hoeffding's inequality, the above trace concentrates:
2+2
P P([TiZZzAZNl - kn 1t} < 2 exp
nM2
47

---

Set t = nk/2 to conclude the statement.
Analogously, if Assumption (IF) holds, for 1...,, n and l,... k. (z 1 is centered
sub-exponential variable with sub-exponential norm (x! -1 1/1
G² By Lemma H.7, with
probability at least 1 - 2exp kn),
Tr Tr 2ea knl
kn
- kn.
2
1m1
Lemma G.6 (Lemma in [7]) For any S and E (0, 1), with probability at least - 6, it holds that
| 0 - 10 10>
Proof. Since E
X O [] 100 Ezx² use Markov's is inequality to obtain the result.
Lemma G.7. Suppose Assumption (IF) hold. Then for any integer k S n1,
1. If Assumption (PE)(EE) holds, then with probability at least 1 - - it holds that 81 (1(A)) = On, (nAx + +A).
2. If Assumption (PE) holds, then with probability at least 2e " it holds that
8n (n(A)) S2n (ndn+* nd),
for large enough.
Proof. First we prove statement 1. For any N,
Ei-in 1 (k-1)
rkk def
Er|E
1
I-a
O k-a
OO (k) O (1)
Assumption (PE) holds
Σ E>kllop
1k
2i aal
O
Assumption (EE) holds
Hence, set t = n in Theorem H.5, with probability least 1 n holds that
- Σ>
On,
|>>iklop
max
Tk
Tk
On, (Au)
op
n
n
By triangle inequality, Hence, with the same probability.
| 11 I n
X
Σ>< lop
+ n
> = On,k (ndx).
(A+) $s (X nAI,) (X X x)) + nd On. (ndx + nd).
Now we prove statement Note that the smallest singular value of a matrix does not increase after discarding column: for some constant 7) > 1 to be determined, it holds that
Sn (X (X
kk) s, Z E 1/2 2 sn (Zeznn
Σ 1/2 ) 2 Apn &n (Zeanm) ) kuma
By Assumption (IF), the columns of Zk:pp independent to each other. By Theorem H.2, with probability least 1 2e -crt² it holds that
Smin (Zk.p) (minn(..nn-A) (Zerm) / mm -on--t t
Choose Vn/c1 and 17 (2+ + + +02) (given that p > r large enough), then with probability least 1 2e it holds that
Sn (Zzzm) Smin (Zkspp) Vn. Hence with the same probability, by Assumption (PE), 8 (Ax)
sn, (X nAI,) 2 nd + nd Pmn.e (nd, nd).
48

---

Lemma G.8 (Theorem 2 in [7]). Suppose Assumption (GF) resp. (IF)) holds, then with probability
least (or resp. 1 2pe "2"), it holds that
81 (Ax)
Tr[E>a] A C2
S
2 Pn,k
n2
n
Suppose Assumptions (IF) holds. Furthermore, if Assumptions (PE) or (EE) holds, then one obtains a probability bound which allows arbitrary large P. with probability least e", ", it holds that
$1 (Ax) n²
c1 (A+
Tr|Esk]
Proof. Since the trace of a matrix is the sum of eigenvalues, we obtain:
$1
(Aa)²
81 (Ax))
sn (Aa)²
n2
8n
Ax )2
n²
2
Pn.k
2
Tr
Ak
n
xx > (xi) x 1)
1
1 Σ
S Pi,
Tr [MIn)) + TT
[(nx+
2
S
Pn,k
nd
+
((x))><11
n
n
By Assumption (GF), since ess supx
||* Ti|E
< BB, we have
$1 (Ax)² S PiLk ( (m>+supp sup |x> )
3x Tr|E>>] 2 S Pin {
n²2
n
If Assumption (IF) holds, then for each I > k, the random variable (2(0)²2 1 is centered sub- exponential, hence with probability at least 2 exp (-cin), it holds that
Σ
(()))2 n S n.
(54)
By union bound, with probability at least - 2(p - k:) cxp ( ( cin), it holds that
Σ 1(x))+++1
Σ 22 12
3 3
(55)
If Assumptions (IF) and (PE)((E) hold, then by Lemma G.7: with probability at least 1 - holds that
$1 (Ax) = On. (ndn, + nA)
for any lo E N. Hence with the same probability,
$1 (A+)
[nd (("A+ ndn 2) )) = On ((+ Tr Eg]
2
O.
n²
49

---

H
Technical lemmata
Theorem H.1 (Theorem and Example [51]). Assume that M1. M2, ... Mn are independent
copies of a d x d positive semi-definite symmetric random matrix M with I [ E, which satisfies:
VIv M'Mvlly I Mv
Mv
(56)
for some constant K 2 1 and for any R2. Then, for any > with probability at least e the inequality holds:
1
+t
M. E
S 20 Σ
n
whenever 2 4r + I, and r is the effective rank.
Theorem H.2 (Theorem 5.39 and Remark 5.40 in [47]). Let A be an N x n matrix with independent
rows A, of aub-Gaussian random vector with covariance Σ del A
E ERax Then there
exists constants Cs, Cs > O 15 (depending only on the nub-Gaussian norm of entries of A), such that for any I. Z O, with probability at least - -ct we have
A
E
max (6, 02) 11 I
N
op
where 5 = Cov
NV + $. In particular, if E I,p. we have
VN- VCn tt Smin (A) Smax (A) S VNN VCnn+ +t.
Theorem H.3 (Theorem 5.41 in [47]). Let A be an x n matrix whose rows A, are independent
isotropic random vectors in R Let > 0 be number such that ||iil2 mm a.s. for all i. Then for every 2 0, it holds that:
VN- tym S Smin (A) S (A) S VNN + t/m.
Theorem H.4 (Theorem 5.58 in [47]). Let A be an N x matrix (N 2 n) with independent columns A; E IRN of sub-Gaussian isotropic random vector with with || = vN almost surely. Then there exists constants Cs, Cg (depending only on the sub- Gaussian norm of entries of A), such that for any t O, with probability least -Cat
CCt? we have
- CyVn
Smin (A) S Smax(() VN Covn+t.
Theorem H.5 (Theorem 9 in [27]). Let A be an N x n matrix with i.i.d. columns C₁ E R of sub-Gaussian random vector with covariance E " [ E RNN, Then there exists constant > 0, such that for any 2 O. with probability at least 1 e we have
1 AAT n
Σ S 1El max
op
n
T where r [.
is the effective rank of the covariance Σ.
Remark H.6. Theorem H.5 is different from Theorem H.2 a few ways: first, the upper bound in the former one contains the term N which requires < N in order to obtain good concentration. while that in the latter one contains the term E Σm Ext. which can still be bounded if N > and the decay of Σ& is fast enough; second, former one requires i.i.d columns while the latter one requires only independent rows.
"
Lemma H.7 (Sub-Expon Sub--Expnnental Deviation, see Corollary 5.17 in [47]). Let N E N. Let XI,..., XN be independent centered random variables with sub-exponential norms bounded by B. Then for any 8 > 0,
N
8N < 2cxp (-C, min B B N))
82
1o be precise, set Css 18 6 and Co 2e 2ev2log9, 6
50

---

where CT > O is an absolute constant.
In particular, if X ~ x(N) is the Chi-square distribution, then P {1x - 1| > o S 2e -N-N Vt E (0,1), 1).
Lemma H.8 (Lemma 28 in [46]; Lemma 14 in [7]. Suppose that for some k < N, the matrix A positive definite, then the following inequality holds:
(A )22 81 Zgk
B 1
|x
Sn (A
)
Sx z5x
1 11
8n (A ) (Z Zg
(57)
+ Σ E ol $1(A ||
+ E (1 1 81 5z [skk)
|| 0 Ez
sn (A 112 8k (Z Zggk)
Lemma H.9 (Lemma 27 [46]: Lemma 13 [7]). For any N, we have
$1 (A T Tr
1/o²
+ (1 Tx
28 D x sk
xxx 13
where 2² def.
2
Lemma H.10 (Lemma 18 in [7]). Assume X2= = -x (k-1-a) and 10%1 = Ox (k- for some a, 0.
Then the square norms |0 E..
2 and 1 xzi
have bounds:
O (k2-2rta),
2r < 222
110% = Oz (k (k-2r
| <0
2
O₂ (logk)
2r = 2 Ô₂ (k(2ta-2r)))
xzl
O₂ (1),
2r 2
where (x)+ del. max(x; xx 03.
Lemma H.11. Assume À = Ox (e-ak) and 10%] = On (e-rk) for some a, > O. Then the square
norms |0:el and 110 11=11=1 have bounds:
4 (k(a-2r)),
2r < a
100 100 Ox (k-2)
0
2
<
O (k),
2r = (,((a))))++
1 (1),
2r
Lemma H.12. Recall that
Tk det. Tr Σ k
Rs def. Tr(E ]2
Σ |Σ> Mlop
Tr|E3
If Ax = 0s (k-1-a) for some a > 0, then
Ts = On (k),
R₁ = Ox (k).
If >x = 02 (E) for some a 0, then
rk = 0x (1),
R₁ = O2 (1).
Proof. By simple calculus,
DP Ei=t1 1 -11- = O₁ (J -1-adt) = O₂ (t-9), similarly.
Ei k- 2- 2a O₂ (Jor t-2 2-2-2a dt)
= 0₁ 11)) If \ 02 (k-1-a) for some a > 0.
then
2
Th = Ok
02 (k),
Ry = 0, k-1-20
= =0p (k).
|x+1
51

---

If A₂ = 0x (e
then 21=k+1 A = 0₁ (Jxx e-afdt) = x (e-ak). Hence,
e ak
2ah
rk Ub
(--((+TT) - Op (1), Rx = On
Ox (1)
Lemma H.13 (Lemma [46]). Suppose Assumption (IF) holds. Then there exists some constant
> 0 such that, for any & < n//c, with probability at least 1 - ce -//c, its holds that
V
1
Σ min
(1,
1,
X7
en
X2
(1 Tk/n)2
Lemma H.14 (Lemma 8 in [46]). Suppose Assumption (PS) holds. Furthermore, if Assumption (GF) (or resp. (IF)) holds, then with probability 1 1, the following inequality holds:
Ae [(0g)
E d B
(58)
( [20013)
2
where the expectation is taken as described in Assumption (PS), and A det
Ev (z()))
nAI, Ruxa where (1)) IK" denotes the 1-th column of the whitened feature block Z del XE 1/2
Proof. By Assumption (PS), the expected value over on the bias admits the following expression as in line (40);
Eg. [8] = Eg.
|I(I, PAOO [ = Eiu, - PAEEL,, - Px)lu Eg. [(0T)]]
1=1
where Px def. X [XX + nAI,))
X. Denote (() R" be the 1-th column of the whitened feature
block Z del =
X - 1/2 E R=x,,
Then the 1-th diagonal element of the matrix (Ip - PI)E(IIp Px)
can be written as
P.
[1, - PI) - PAJLU Σ 2 [1- (A +
A --=2))
Σ dn (G09)TA~\211) Ri
1==
where A def XX
+ nnIp. we write A-1 del A (z))) by therman-Morrison www-iooo---oooouurryy Woodbury
formula, we have
1 () -12
1+ 1+1(1Z()) (
and hence the averaged bias is bounded by:
Ag [0)))]
Eg
B
(z)) T TA 7Z
Ae [(8))2]
A A [ ||2(0
XrEa [(0))2]
1 + Ais (A 1)- ()) (| 2'
Lemma H.15 (Lemma 9 in [6]). Suppose that {Xx)P is sequence of non-negative random variables, and that {1x)2 is sequence of non-negative real numbers (with at least one of which strictly positive), such that for some 8 E (0, 1). with probability at least 1 - 8, nk >> tç for all
1,.... P. Theb with probability at least 25,
p
1
p
Σ
tg-
2
k=1
52

---

Lemma H.16 (Theorem 10 in [46]). Let l E N be an integer. Denote
11
B def
+
nd )2
1=1
A4-17e
nd + Tr
B
Σy +
1 Ezl
n
X2
V
min
1,
Nx+1
rk/n)2
1ml
V
del
k
Tr D
(nd + Tx(2
n
Fix constants 0, > 0 and b 1. There exists constant that only depends a, such that: if
either E b) or = min(x Tx > bn}. then
<B/B < 1,
<V/V S1. 1
Lemma H.17 (Corde's inequality, [18)). For any positive definite symmetric matrices 16 M2,M2 and positive number m E [0, 1]. it holds that IM'M llop S ||
Proposition H.18. Let X > 0. The bias term B Ex (x [(x00)))) - x =T²) 2]
has the following
expression:
B X2 1²I + Σ) E -000
x
where D del X
Proof. By definition, rewrite the bias into:
B 0- ((X0)) |
E
0" x TXXT nAI,) - '(00))
2
Σ
Ip - (XX + nAI,) -Ix
0*
(59)
Σ
Denote Px Jef. X
XX
nAI,)) - 'x E RpxP, By Ineemmnn-Morrisee Woodbury formula,
I, P = (nd))) T (I, + (nd) -XX x xxxx=xx0 ->(M²² 1xxx) =x (AI + Σ
Hence = - E) 10
(x) has the
Proposition H.19 (Variance expression). The variance term v del Exc
following expression:
== 0² Tr " MI, -s
|| S x1,)
12
Exeoy
xIp)
16 Or equivalently positive definite self-adjoint operator in Hilbert space.
53

---

Proof. By definition,
V Ee ((E)
Ee (c (XX + + XEX (XX + + -
Ee [Tx[(XX + + XXX (Xx ndI,)) EeE []
-T((XX + (XX* + +ndI,) 'Ee [Ec]
TF +ndln) ( XEX (xx" + =nd1)) 1
Tx X xd1p)) E(X xx X -
0²
-1 x + AI,)
-1 x x + sT,)
Th
E
x X
n
n
n
a²
T
-1 ( ( (1p1))
Ex [X 7
-1 Σ ( AIp) (1
11
o²
Exar
Tr ( 21,) -1 xx
xxT($ + lII)
-1 $
n
Exara
x ( \I,)
(
-1 Σ (
+ Alp)
x
n
0²
2
Ex Exar
x
11
S
54

---

I Experiments in details
Some of the results in Table have already been validated by experiments in previous literature. Hence, this section will focus on the novel result of this paper:
1. Same decay rate for independent (IF)/genrric (GF) features under strong ridge;
2. Decay of B for s < under weak ridge;
3. Decay of V under weak ridge (tempered vs catastrophic overfitting).
All experiments were conducted on a computer with a 2.3 GHz Quad-Cor Core Intel Core i7 processor. The code for the experiments is available in the supplementary materials.
L1 Bias under strong ridge
we first consider a simple example: let A = ( (2k-1 11) 11)-110, v/((-) = V2sin (2x-1 such that I|velllz = 1 for μ unif (0, 1]; let 0% = ( m) For = Do and a = 1, the regression coincides with the kernel ridge regression with kernel k(z, x²) = min(x, x') defined on the interval [0, 1] by [48]. [30, 33] have conducted similar experiments on this kernel k. However, to simulate the regression for independent features (IF), the feature rank p has be finite. In the following experiment, we choose 2000, the sample size n ranges from 100 to 1000, ridge À An (2m (a-m)--1-
--
The first thing to check is whether both independent features ((IF) and generic features ((GF) satisfy
B = O bn-b
under strong ridge, where def. min 8, 2 and 8 compute the exact formula:
20+r Ita"
To accurately obtain the bias term B, we
B B= == x2 ( + Σ) 0
x
as shown in Proposition H.18, rather than computing the squared difference (f()) by evaluating on test points as done in [31], or by using an integral function as in [33]. To demonstrate the Gaussian Equivalent Property (GEP), we also compute B after replacing the Sine feature vector
zb 2/y (z) R_ with random Gaussian vector z (O, 1) random Rademacher vector z ~ [= It worth noting that the random Rademacher vector z ~ (unif =1]}) satisfies Assumption (IF), This shows that our statement holds more generally than under the Gaussian Design Assumption (GDD). From Figure 5, we observe that for different choices of a and r (and hence s), the bias decays at its theoretical rate for all three different features.
Bias, a=1, b=2, 1=1
Bias, a=0.5, b=1.5, 1=5
Sine feature
10
Sine feature Rademscher feature
Test Error (log scale)
Rad Rademacher feature
Emar (log scale)
Gaussian feature
10"
saisn feature Slope=.3.22 3.22
10"
Sl0pe=
10
10"
10
-0
10
2x 3x10'4x10"
6x10'
10'
2x10' 3* 3x10'4x10" 6x10²
10
scale)
(log scale)
Figure 5: Decay of the bias term B under strong ridge x Xn θ (n-119). d = ((2-1) (2 π
0% = (2k-1 (2)=117)* -) Theoretical decay B O (n (I+a)) O (n- (1+a)a) where min s 2}.
2atr (Left): s = 1.5 and B = 0 (n (1- (n-(111) min mi.1m))) = O (n-3): (right):
source coefficient s = 1+a
O (n- showing the saturation effect mentioned in [29]. All features demonstrate the same theoretical decay, validating the GFP.
2.33 2 and B O (1+000)) min
55

---

1.2 Bias under weak ridge
For weak ridge, we find that the decay rate is better than this theoretical rate (see Figure 6). One explanation for this is the estimation error of replacing the kernel K (x,,²') = min (ar, x' } by its finite rank approximation; another reason is that the decay flattens for large sample sizes n > 1000. However, the learning curve of independent features (Gaussian or Rademacher) behaves similarly to the dependent one (Sine). The left plot in Figure fits our theoretical result, as s 1, while the right plot shows that our theoretical bound is too pessimistic. However, suspect this is due to the fact that the eigenfunctions on the me-dimensional input space are simply sines, which are uniformly bounded.
Bias, a=1, b=4, F=1
Bias, a=0.25, 25, b=2.5 5, r=0.5
10
Test Entor (log scale)
10"7 10
Rademacher feature
Sine feature
Test Test Error (log scale)
10"
Rademacher feature
feature
Gaussian feature
Gaussian feature Slopen-1.55
Slopem-3.25
10
10
10
10
2x10' (log scale)
3x10''x10"
6x10'
10"
10
2x10' 3x10'4x10"
6x10"
10
(log scale)
Figure Decay of the bias term B under weak ridge. A θ (n d 22 ②T)
-)-1) lla
0% = x)- Theoretical decay B O (n- (n-(1+)))) = O (n=()))))) where min 2}, source coefficient
2a+r. (Left): s = 1.5 > 1 with theoretical bound B Ita
0.8 < 1 with theoretical bound B = O (n (n-(1+t) (1+0.25) (0..). ) = (n-1) for Gaussian and Rademacher (independent) features, the
O (n (1+00.5)) min (2.33.3))) O (n=3) for all features; (right):
empirical result for Sine features is better than its theoretical bound B = O (n (a-(-aa) O (n -.225.
I.3 Variance under strong ridge
Analogous to B, we want to check whether both independent features ((IF) and generic features ((GF)) satisfy
== o 00 --2n--+15 -111)
under strong ridge, where の² E [e2] is the noise level. To ease the computation, instead of computing the expression of V directly from Proposition 1.19:
== Tr
(S (1
-
n
a²
Tr
Σ + XI,) -E + AI,)
n
q² Tr +
where Σ T is the singular value decomposition of Σ. Figure 7 confirms the Gaussian Equivalent Property (GEP) under strong ridge.
All dotted lines in Figures 5, 6 and 7 are regression of the learning curve with Gaussian features.
1.4 Variance under weak ridge
As reported in [7, 14], by setting À 0, is indeed the norm minimum interpolant, which may demonstrates tempered or catastrophic overfitting as - oc. For this example, we focus another setting where we take samples uniformly from unit 2-disk and approximate V by evaluating the regressor of the zero function the test point. We set À 0 and compute the kernel ridgeless
56

---

Variance, a=1, b=0
Variance, aF1,
Sine fedture
Sine feature
Rademacher feature
Test Emor (log scale
4 4x10"
Rademacher feature
Gaussian feature
Gaussian feature
3 x ?
(log
Slope=-1.00
Slope=-0.51
xx10
10*
2x10" 10=4 n (log scale)
6x 10
10 10"
2x10 3x 10
6x 10
10.
(log scale)
Figure 7: Decay of the variance term V under strong ridge. A = A (n- d (2
Theoretical decay V O -+=)+ (Left): Theoretical decay (right): Theoretical decay O (n 1/2) for all features.
O (n-1) for all features;
Overfitting of Laplacian kemel
Overfitting of NTK with L=1
0.45
2000
0.44
1500
Vañarce
0.43
Veriance
0.42
0.41
0.40
200
600
800
1000
600
1000
Figure 8: The variance against the sample size n under no ridge. (Left): Tempered overfitting with Laplacian kernel. (Right): Catastrophic overfitting with NTK.
regression with the Laplacian kernel K(x, 2) = -- and the neural tangent kernel K K(x, 2)
2n0 (x x1 2) where Ko (t) def 1-1 arccos(t), (t) 1 (f( arccos(t)) + v1 2).
In Figure we can see that although having polynomial eigen-decay, the Laplacian kernel exhibits tempered overfitting, as termed by [35], while the NTK catastrophic overfitting.
57

---

J
Tables
Linear
Kernel
X
K( )
z
Σ
A
Z
y
XX
K 11-11
||-
11-11x,
|| I--1aze || 13))
|1-1
Σ
|1-11
I1-11,o on supp(p)
0+
f
Table 5: The translation of ridge regression setting in KRR setting (see Subsection A.6 for the elaboration.)
Ridge
strong
weak
Feature
(IF)
(GF)
(IF)
(GF)
[16]
[31. 7]
[16]
[31. 7]
Poly (PE)
[16]
[30, 7]
[16, 14]
[7]
Exp (EE)
this paper
[33]
this paper
[33]
this paper
this paper
Ridge
strong
weak
Fcature
(IF)
(GF)
(IF)
(GF)
B
O (n-
O (nt [min [minn/2fr-)))2-03)
Poly (PE)
V
o 547
+ (a²)
(a2n22)
Exp (EE)
catastrophic overfitting
Ridge
strong
weak
Feature
(IF)
(GF)
(IF) (n (2+0)))
(GF) (n (1=0)8)
Poly (PE)
B
(n d2)
,
y
n 14
8
O (e-ain)
s>1
Exp (EE)
catastrophic overfitting
Ridge
strong
weak
Feature
(IF)
(GF)
(IF)
(GF)
(n--ba)
(n--ba)
(n (L+0))
O (n (1+01)
8>> 1
Poly (PE)
1
(min (min
$
y
(02)
Ô (02
B
(e-hia) 9
o
(e-hin)
(e-nin)
(e-nin) s>11
Exp (EE)
V
(1
O
(1
catustrophic overfitting
Table 6: Various filters for Table 1. (top): Recovered (in black), improved (in blue) and novel (denoted
by "this paper") results over previous literature. (top 2): Recovered results under same assumptions. (top 3): Recovered results under weaker assumptions. (bottom): State-of-ther -fttte---ttttttt (SOTA) result. Black indicates results recovered results under our assumptions, blue indicates improved results over previous literature, orange indicates SOTA results from [31] under extra assumptions.
58

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims asserted in Abstract and the questions raised in the introduction section I are directly addressed in the main section of our paper; namely in section 3 and the additional material in the appendix section.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: This is theoretical paper where assumptions are clearly stated. We admit that verifying the conditions of the assumptions (e.g., eigen-decay rate or rigen-functions of kernels in realistic datasets) can be challenging, and we limit our experiments to relatively simple examples. Further investigation into the generalization performance of kernel ridge regression realistic datasets is left for future work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specificattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
59

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:
[Yes]
Justification: All mathematical objects are clearly stated, and further explain, in section $2.2.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proof' can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented
by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The experiment is done some synthetic settings, which details are clearly stated in I.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
60

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code for the experiments is uploaded as supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips..
wwwssssinoooilillo for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. htc//ublicggguiiii /tcegguuudds/ooeuuubiiiii SondeeuubisssioPoooe
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Error bars are displayed in the figures in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
See Section I.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
61

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification; All experiments were conducted on computer with 2.3 GHz Quad-Core Intel Core i7 processor.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httppp///eerrrp...cppbiibicceeet httpppulll/tiicaaiiieieeeoooeeee
Answer: [Yes]
Justification: Since our paper is purely theoretical, it does not involve human subjects or participants, data-related concerns, nor are there any negative societal implications. Rather, by elucidating the theoretical foundations of some kernel ridge regression models, we help verify the reliability of commonly used machine learning models.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper focuses on enhancing the theoretical underpinnings of machine learning. leading to predominantly positive societal impacts. By emphasizing the importance principled machine learning and furthering our understanding of Al capabílities, contributes the advancement of technology constructive manner.
Guidelines:
62

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: As our contributions are theoretical justifications of commonly used Al models, this does not apply here.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
63

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com comddataees has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not use new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
64

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
65


Reviews:
[{"review_id": "JrAYGfRohD", "reviewer": "Reviewer_8wF6", "summary": "This paper studies the learning curve of kernel ridge regression under both eigendecay assumption and the source condition assumption. Assuming the fixed input dimension setting, this paper derives the finite sample bound for the bias and variance where features can either be generic or independent. Depending on the assumptions used, matching lower bound are also provided. After this, the authors provide a unifying theory of the KRR test error and demonstrates the settings where Gaussian equivalence property holds. They also provide an answer for when the test error is fully determinded by the eigen-decay of the kernel. Finally, they provide simulation experiments to validate the bound on the test error.", "questions": "See weakness", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "By providing the matching upper and lower bounds for the test error under IF and GF where strong ridge is used, the paper shows that the Gaussian equivalence property only holds when strong ridge is used. In dosing so, the paper also provides a novel master inequality for both bias and variance.\n\nIn many cases, for example the expoenential eigendecay under strong ridge, the paper provides the sharpest learning rates so far.\n\nThe paper aslo addresses the question of when the learning rate of KRR is fully determined by the kernel eigenspectrum.", "weaknesses": "In demosntrating the GEP, the paper seems only provide the upper bound for bias and variance under generic features while a matching lower bound is missing. Given this, it is not completely convincing that the GEP holds although the author did show that the upper bound under GF matches with IF. So I was wondering if the author could explain this a bit or can detail the challenges in obtaining the lower bound.\n\nRecently, there is a growing interest in studying the KRR when the output is infinite-dimensional, see e.g. \n\"Towards Optimal Sobolev Norm Rates for the Vector-Valued Regularized Least-Squares Algorithm.\" (2024)\n&\"Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms.\" (2024)\n\nI am curious whether the results hold in the setting where the output is infinite dimensional. Maybe the author could draw some link between their results and this setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort reviewing our paper. Regarding your questions,\n\n> In demosnstrating the GEP, the paper seems to only provide the upper bound for bias and variance under generic features while a matching lower bound is missing... I was wondering if the author could explain this a bit or can detail the challenges in obtaining the lower bound.\n\nThis is indeed a good question to ask for the lower bound in the (GF) case, which we did not have space to discuss in the main text. We refer to the **Author's Rebuttal** for a detailed answer.\n\nPrevious works that mention GEP typically focus on the upper bound; hence, our paper also demonstrates GEP on the upper bound. However, the lower bound is complex, our paper is a first step understanding it better, and we will explore it further in a future work dedicated to these questions.\n\nWe will update the paper to provide a detailed discussion of the aspects discussed in this answer as well as clarify the GEP claim, thank you for your comment.\n\n> Recently, there is a growing interest in studying the KRR when the output is infinite-dimensional...\nI am curious whether the results hold in the setting where the output is infinite-dimensional. Maybe the author could draw some link between their results and this setting.\n\nThank you for pointing out this interesting setting. We were not aware of it. We looked at the proof technique and it seems it relies on an assumption similar to the embedding condition and relies on similar proof techniques (spectral calculus and concentration inequalities). A direct comparison seems difficult, as we for instance do not see a way to establish a comparison between different eigendecay and regularization regimes.\n\nThat said, we do expect that many of these results could be extended to the infinite-dimensional setting, for instance, by projecting the target function to finite dimensions (via a Schauder basis truncation) then applying our results, and then (isometrically) embedding the learned (finite-rank) up be encoding it as weights to the chosen given Schauder basis.  In effect, one can view the current results as doing precisely this using the standard orthonormal basis of Euclidean space $\\mathbb{R}^D$ as the Schauder basis and “truncating” at the full-dimension $D$ (in which case the truncation reduces precisely to the identity map, and the embedding is also the identity map).  This type of argument has successfully been used in the approximation-theory literature; see e.g. [1] for the Hilbert case (where the Schauder basis can be taken to be orthonormal) or [2] (in the Banach or even Fréchet case) where the basis is a genuine Schauder basis (eg a Wavelet basis when the target space is a Besov space over any E-thick domain with Lipschitz boundary (see Theorem Theorem 3.13 in [3] such as the Euclidean unit Euclidean ball).\n\n[1] Lanthaler, Samuel. \"Operator learning with PCA-Net: upper and lower complexity bounds.\" Journal of Machine Learning Research 24.318 (2023): 1-67.\n\n[2] Galimberti, Luca, Anastasis Kratsios, and Giulia Livieri. \"Designing universal causal deep learning models: The case of infinite-dimensional dynamical systems from the stochastic analysis.\" arXiv preprint arXiv:2210.13300 (2022).\n\n[3] Triebel, Hans. Function spaces and wavelets on domains. No. 7. European Mathematical Society, 2008.", "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": "", "extra_scores": {}}, {"review_id": "OFofnXtnQ8", "reviewer": "Reviewer_x66w", "summary": "This paper studies learning curves of kernel ridge regression (KRR) under minimal assumptions. The authors analyze the role of key properties of the kernel, such as its spectral eigen-decay, the characteristics of the eigenfunctions, and smoothness of the kernel. They also demonstrate the validity of the Gaussian Equivalent Property (GEP), which states that the generalization performance of KRR remains the same when the whitened features are replaced by standard Gaussian vectors. Additionally, they derive new improved bounds across several settings.", "questions": "Does the result hold under the assumptions used in the related work, e.g., Embedding Condition?", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The authors study the learning curves for various settings, including weak ridge vs strong ridge, independent features vs generic features, and polynomial vs exponential kernel eigenvalue decay. This comprehensive study provides a deeper understanding of the behavior of KRR in different scenarios.\n- An improved bound is presented for the bias under the weak ridge assumption. In particular, the authors show that the generalization performance with independent (Gaussian) features and dependent (kernel) features coincides asymptotically and it solely depends on the eigen-decay under strong ridge regularization, hence validating the Gaussian Equivalent Property (GEP).\n- The paper provides an answer to the key question \"Under what condition the generalization error fully determined by the eigen-decay?\"--- 1) in under-parameterized setting; or 2) with strong ridge in over-parameterized regime.", "weaknesses": "- The presented results seem to be based on a set of different assumptions while comparing with the current bounds. However, it is unclear how the discrepancy in the assumptions impacts the bounds. For example, the paper compares the presented bounds with related work using Hölder continuous kernels or the Embedding Condition, but it is not clear how the differences in assumptions affect the comparison.\n- The numerical studies demonstrate the validity of the bounds for a couple of constructed kernels. However, it would be beneficial to consider more general/practical kernels to assess the practical impact of this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort reviewing our paper. Regarding your questions,\n\n> The presented results seem to be based on a set of different assumptions while comparing with the current bounds... it is not clear how the differences in assumptions affect the comparison.\n\nSection A.2 is dedicated to explaining and discussing the comparison between different assumptions from various papers. We kindly refer the reviewer to Section A.2 for more detailed information. We also refer to the **Author's Rebuttal** for a detailed answer.\n\n> The numerical studies demonstrate the validity of the bounds for a couple of constructed kernels. However, it would be beneficial to consider more general/practical kernels to assess the practical impact of this work.\n\nAn important contribution of this paper is to provide a unifying theory connecting all scattered results from previous literature. We have derived the same optimal upper bound with a more general assumption.  Demonstrations on practical kernels can be seen in various previous literatures, including [12, 16, 31]. We will make this clear in the revision of the manuscript.\n\n>Does the result hold under the assumptions used in the related work, e.g., Embedding Condition?\n\nYes. There is a detailed discussion in Section A.2 page 15 - 16.", "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": "", "extra_scores": {}}, {"review_id": "TAqBPABVtG", "reviewer": "Reviewer_v1Hz", "summary": "A recent line of work has derived excess error rates for kernel ridge regression in a source and capacity setting under the assumption of Gaussian universality of the kernel features. This work investigates the validity of this assumption in this context.\n\nThe main result is that while the rates derived under Gaussian design are correct in the strong regularization regime, the excess error rate can be faster in the weak regularization regime.", "questions": "- In the introduction, the authors say their work addresses three questions. While Q1 and Q2 are precisely addressed by the results, I find that the answer to Q3 falls short. First, the assumption (GF) is surely weaker, but it is still constraining. Second, some of the results in Table 1 are only upper bounds. I understand that most of the excess rate results in the classical kernel literature are also upper bounds, and the authors explicitly discuss that under (GF) it is not possible to derive a matching lower bound, but there is nothing telling us that the picture is not richer in these regimes. Perhaps my problem is with the phrasing of Q3, which differently from Q1 and Q2 is vague.\n\n- I miss a discussion on the intuition behind the (GF) assumption. For instance, in the Gaussian design approximation, one possible intuition is the identification of \"orthogonality\" (of the features) with \"independence\". Do you have an intuitive understanding of the two conditions in L440? Why does strong regularization justifies independence?\n\n- Related to the question above, how (GF) differs from the concentration assumption in previous work, e.g. (a1, a2, b1) in [36]. Note that the formulas derived under similar concentration conditions from [36] allow to recover exactly the Gaussian design rates from [16], see the contemporary recent work [DLM]. This suggests (GF) is strictly weaker?\n\n- Since the main result in this work dialogues with previous literature, I suggest commenting and comparing the important notation (source, capacity, regularization decay, etc) in this work with the ones employed in the relevant Gaussian design literature, e.g. [10, 16, 35, 44]. For example, a table like Table 1 in [44] or Table 2 in [16].\n\n- Can you please elaborate on Remark A.5?\n\n[DLM] https://arxiv.org/abs/2405.15699\n\n**Minor points**:\n\n- The authors discuss the \"over-parametrized\" and \"under-parametrized\" regime in the text, but never define what they mean. While this can be inferred from the text, it would be good to precisely define it, since this terminology is used in different ways in the ML theory literature.\n\n- For the sake of completeness, it would be better to add the definition of the source in (L106-L108) to the main text in a final version.\n\n- Unpublished pre-prints in the bibliography are missing the arXiv identifiers.\n\n- L110, define $\\succeq$ in the notation section.\n\n- L597, maybe $\\psi_{k}$ and $\\phi_{k}$ are switched?\n\n- L634, \"*Consider a kernel $\\kappa:\\mathcal{X}\\times\\mathcal{X}\\to\\mathbb{R}$ be a kernel with [...]*\"\n\n- Eq. below L651, missing right bracket.\n\n- Assumption \"Domain Regularity (DR)\" in Appendix B.2 there are two items (i), (ii) but (iii) is mentioned in the paragraph below (L662-L669) twice.\n\n- L679, precise what \"$\\lambda$\" in $||\\bar{\\psi}_{i,j}||\\lesssim \\lambda^{(d-1)/4}$ is.", "limitations": "Limitations are discussed in the \"Future potential work\" section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a solid work. The manuscript is clearly written: the context is well explained and the reading is smooth. The results fit in an established literature studying excess error rates for kernel ridge, which recently has seen a revival of interest in the context of deep learning (NTK) and neural scaling laws. Therefore, I believe it is of significant interest to the theoretical community in NeurIPS.", "weaknesses": "A minor weakness of this work is that it mostly combines existing technical results. But I think this is minor since in the end the conclusions are novel and interesting", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> In the introduction, the authors say their work addresses three questions. While Q1 and Q2 are precisely addressed by the results, I find that the answer to Q3 falls short. First, the assumption (GF) is surely weaker, but it is still constraining. \n\nWe refer to the **Author's Rebuttal** for a detailed answer.\n\n> ...some of the results in Table 1 are only upper bounds. I understand that most of the excess rate results in the classical kernel literature are also upper bounds, and the authors explicitly discuss that under (GF) it is not possible to derive a matching lower bound, but there is nothing telling us that the picture is not richer in these regimes...\n\nThank you for raising this important question on a matching bound, which we did not have space to discuss in the main text.\nPrevious literature which mentions GEP usually only focuses on the upper bound, however, we will put more discussion on the lower bound in a future edition.\nWe refer to the **Author's Rebuttal** for a detailed answer.\n\n> I miss a discussion on the intuition behind the (GF) assumption... Do you have an intuitive understanding of the two conditions in L440? \n\nAgain thank you for your question. The intuition behind (GF) is that the random distribution of the feature $\\mathbf{z}$ is concentrated. By a Bernstein-type concentration inequality, one can show that independent features enjoy some concentration properties. See remark A.2 for more details.\n\n> Why does strong regularization justify independence?\n\nTo be precise, strong regularization does not justify independence. Instead, we proved that the learning rates for the (GF) and (IF) cases are asymptotically identical under strong ridge, demonstrating a necessary condition for GEP.\n\n> ... how (GF) differs from the concentration assumption in previous work, e.g. (a1, a2, b1) in [36]... This suggests (GF) is strictly weaker?\n\nFirst, Assumption 1 in [36] requires the regularized tail rank to be bounded from below, in this paper’s notation, it is $\\frac{\\sum\\_{l>k}\\lambda\\_l +\\lambda}{\\lambda\\_{k+1}} \\geq 2n$. Note that this cannot hold for exponential decay as LHS is bounded but not RHS. On the other hand, assumption (GF) does not have similar restrictions. \n\nNow we try to show how assumptions in [36] “imply” (GF).  As mentioned in Remark A.2 and A.3, the intuition of (GF) is the concentration of the truncated features at their expected value. \nNow suppose Assumption a2 in [36] holds, for any $\\mathbf{x}\\_{\\leq k}=\\Sigma\\_{\\leq k}^{1/2}\\mathbf{z}\\_{\\leq k}$,  pick $\\mathbf{A}=\\Sigma\\_{\\leq k}^{-1}$ and we have w.h.p. \n$$ | \\mathbf{x}\\_{\\leq k}^\\top\\Sigma\\_{\\leq k}\\\\mathbf{x}\\_{\\leq k} - tr[\\Sigma\\_{\\leq k}\\mathbf{A}] | \\leq t \\phi\\_1(k) \\\\|\\Sigma_{\\leq k}^{1/2}\\mathbf{A}\\Sigma\\_{\\leq k}^{1/2}\\\\|\\_{F} $$\nAnd hence, w.h.p.:\n$$| \\\\| \\mathbf{x}\\_{\\leq k}\\\\|^2/k - 1 | \\leq t \\phi\\_1(k), $$\nwhich implies the concentration of the first term in (GF).\n\nSimilarly, Assumption 2 in [36] implies the concentration of the second term in (GF). At the moment, we do not know if the concentration of the third term in (GF) can be derived from any assumptions in [36], but as mentioned in Section A.2, the kernels satisfying the assumptions made in [36] form a proper subset of those which satisfies (GF).\n\nHence, we believe our paper gives a more general result. If the reviewer could find any kernels which satisfies assumptions [36] but not (GF), please let us know as it would be of significant interest.\n\n> Since the main result in this work dialogues with previous literature, I suggest commenting and comparing the important notation (source, capacity, regularization decay, etc) in this work with the ones employed in the relevant Gaussian design literature...\n\nThank you for your suggestion. We will put this into our consideration in our future edition to enhance readability and comparison with previous literature.\n\n\n> Can you please elaborate on Remark A.5?\n\nSuppose (IF) holds and each coordinate $z_l$ of the isotropic feature vector $\\mathbf{z}$ is drawn i.i.d. from a random distribution with bounded support, hence there exists constants $a,b$ such that $z_l^2$ is a.s. In the interval $[a,b]$. By Hoeffding’s inequality, for any $t>0$,\n$$ \\mathbb{P} \\\\{  | \\\\|\\mathbf{z}\\_{\\leq k}\\\\|^2 - k   | > t  \\\\} \\leq 2\\exp(-2t^2/k(b-a))   $$\nLet  $t=\\frac{k}{2}$, we have\n$$ \\mathbb{P} \\\\{ \\frac{3}{2} > \\\\|\\mathbf{z}\\_{\\leq k}\\\\|^2/ k  > \\frac{1}{2}  \\\\} \\geq 1-  2\\exp(-k/2(b-a))   $$\nThen w.h.p., the fraction $ \\\\|\\mathbf{z}\\_{\\leq k}\\\\|^2/ k$ is concentrated at its expected value 1, similar argument holds for the other two fractions  $ \\\\| \\mathbf{z}\\_{> k}\\\\|\\_{\\Sigma\\_{>k}}^2 / tr[\\Sigma\\_{>k}]$ and  $ \\\\| \\mathbf{z}\\_{> k}\\\\|\\_{\\Sigma\\_{>k}^2}^2 / tr[\\Sigma\\_{>k}^2]$. By remark A.3, it suffices to show a weaker version of (GF). For technical simplicity, we require ess sup and ess inf in (GF) instead of a high probability bound.\n\n> **minor points: ...**\n\nThank you very much for your effort improving our manuscript. We will adjust the points mentioned accordingly in our revised version.", "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": "", "extra_scores": {}}, {"review_id": "orFq2DJfIq", "reviewer": "Reviewer_xgGe", "summary": "This paper conducts a comprehensive study of the learning curves of kernel ridge regression (KRR) under minimal assumptions", "questions": "The writing style of this paper is quite challenging for me to engage with. I find the presentation could be improved in terms of clarity and readability. \n\nFor instance, could the author make their own results and assumptions in a more clear way? There is not even a single explicit theorem  provided for me to verify. It is quite unusual for a theoretical paper to be presented in this manner. I am uncertain if this document has been generated by an artificial intelligence.", "limitations": "NONE", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The authors claimed that they provide a comprehensive analysis on the learning curves in kernel ridge regression.", "weaknesses": "The learning curves of kernel ridge regression have been extensively studied in recent literature. e.g.,  \n1. \"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.\", \n2. \"Yicheng Li, Haobo Zhang, and Qian Lin. On the asymptotic learning curves of kernel ridge  regression under power-law decay.\", and \n3.  \"Bruno Loureiro, Cedric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc Mezard,  and Lenka Zdeborová. Learning curves of generic features maps for realistic datasets with a  teacher-student model. Advances in Neural Information Processing Systems, 34:18137–18151,382 2021.\"\n\nIt is really hard for me to understand the difference between the current paper with the above papers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The learning curves of kernel ridge regression have been extensively studied in recent literature...\nIt is really hard for me to understand the difference between the current paper with the above papers.\n\nThank you for your feedback. The three papers you mentioned are cited in the paper as references [16, 31, 34]. As explained in the paper, references [16, 34] assume the feature vectors are distributed according to Gaussian random vectors. This is what we call the IF case in our paper. These papers do not discuss the general feature case (GF). They also do not differentiate between exponential and polynomial decays and do not discuss differences between weak and strong regularization. Reference [31] employs a different assumption on the features, we have summarized the difference between their results and ours in Table 1 in the paper’s main body and in Table 5 in the appendix. For instance, Table 1 shows that our bounds are tighter than the results of [31].\n\nSince this is the only weakness noted by the reviewer, we would like to request further details on the reasoning behind the score of 3. Does our response above address your concerns? Are there any other questions or doubts we can address?\n\n\n> The writing style of this paper is quite challenging for me to engage with. I find the presentation could be improved in terms of clarity and readability.\nFor instance, could the author make their own results and assumptions in a more clear way? There is not even a single explicit theorem provided for me to verify. It is quite unusual for a theoretical paper to be presented in this manner. I am uncertain if this document has been generated by an artificial intelligence.\n\n\nWe would like to clarify that this paper was not written using ChatGPT or any other language model. We would appreciate it if the reviewer could specify which aspects of the presentation need to be improved.\n\nWhile we agree that some results are technical, we have tried to present them in the most reader-friendly way through Table 1 and Figure 1. For instance, Table 1 outlines the bounds we derived for three different scenarios: \n1) polynomial vs. exponential eigendecay,\n 2) strong vs. weak regularization, and \n3) independent vs. dependent features. \n\nAll formal theorems are provided in the appendix, with Table 1 summarizing the key results, which we believe is a clearer way than listing each theorem individually. Additionally, Figure 1 illustrates the improvements achieved by these bounds in a diagram.\n\nCould the reviewer specify what aspects of the table and figure are unclear?\n\nRegarding the assumptions, we have a dedicated section (Section 2.2: Assumptions and Settings, line 96) that thoroughly covers them. Could you please further clarify your concerns? We are eager to improve the paper’s accessibility.", "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": "", "extra_scores": {}}]

Author rebuttal:
Thank you for your time and effort on reviewing our paper. Since some of you asked for the same or similar questions concerning important points in our paper, we will refer the reviewers to here from their individual rebuttal sections.

---

## A matching lower bound for (GF)

we can summarize the existence of a matching lower bound in the cases considered in the paper with the following table:

| Ridge    | Strong                | Weak                    |
|----------|-----------------------|-------------------------|
| Feature  | (GF)                  | (GF)                    |
| Bias     | Yes, with modification in Prop. E.3 | Yes, if $1 \leq s \leq 2$ |
| Variance | Unknown               | No, because of Fig. 2   |

We discuss the results one by one:

- Under the strong ridge and (GF) assumptions, we could modify Prop. E.3 to obtain a matching lower bound for the bias. In more detail, in the second equation in the proof, we have $s_n(\mathbf{A}_{-l}) \geq n \lambda = \Omega(n \lambda_n)$ by the strong ridge assumption. The remainder of the proof follows similarly. We will include this modification in the revised version of the paper.

- Under the strong ridge and (GF) assumptions, we were not able to derive any matching lower bound, since the independent feature assumption (IF) seems necessary in the proof. However, based on results from the previous literature and under stronger assumptions, one could prove that the upper bound has a matching lower bound. See the orange-coloured result in Table 5.

- Under weak ridge and (GF) assumptions, we did prove a matching lower bound for the bias term with source coefficient $s \in [1,2]$. See Lemma E.1. For $s$ not in $[1,2]$, as far as we know, there is no matching lower bound result in the kernel setting. We would be happy if you could point out any results that we have overlooked.

- Under the weak ridge and (GF) assumptions, we demonstrated there is no matching lower bound for the variance term by Fig. 2, since there can be different overfitting phenomena for different kernels.

To address the comment from the reviewer, we will refine the statements made in the paper about GEP in the next revision, according to the above explanations.

Please see Section E for more details on the lower bounds.

---

## How general is the (GF) assumption?

Kernels satisfying (GF) includes:
- dot-product kernels on hyperspheres
- kernels with bounded eigenfunctions 
- radial base function (RBF)
- shift-invariant kernels
- kernels on hypercubes.

As far as we know, the kernels satisfying the assumptions made in any existing theoretical papers on KRR learning rate (for instance [19,23,29-31,33,36]) form a proper subset of the above list. Although (GF) is constraining, it is clearly the most “general” in this sense. For more discussion, please see Section A.2.

---

Thank you again for reading our response. We are looking forward to hearing your feedback, and if possible, we kindly ask you for raising your score and confidence after you have considered our rebuttals.

Meta-review: This paper proposes a unifying analysis on the learning rates of kernel ridge regression that connects existing results in the literature and offers several improvements. The reviewers unanimously recognized it as a valuable contribution after the rebuttal. 

Several important suggestions were made by the reviewers to present this analysis in a more formal and complete manner, including a formal statement of the derived learning rates in the main text, a more precise reformulation of Q3 and a more explicit discussion on matching lower bounds. Please take into account of these points (some of which were addressed by the authors during the rebuttal) in the preparation of the final version.
Decision: Accept (poster)