A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression

Authors: sum  cheng
aurelien  lucchi
anastasis  kratsios
david  belius
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 15:38:15

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.

Main paper: 
 introduction: 
 Kernel ridge regression (KRR) is a central tool in machine learning due to its ability to provide a flexible and efficient framework for capturing intricate patterns within data. Additionally, it stands as one of the earliest endeavors in 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 as approaching specific kernel limits as they converge [25, 1, 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, λ = λ(n) be the ridge regularization parameter depending on n and R n be the test error/excess risk of the ridge regression. For large n, the test error R n should decay with n as R n = O n,P (g(n)) for some function g : R → R such that g(n) n→∞ ----→ 0. The decay of g with respect to n provides an 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 on several crucial properties of the kernel, including its spectral eigen-decay and the characteristics of the eigenfunctions, which we will elaborate on next.Properties of the eigenfunctions In a series of studies [10, 16, 34] , the feature vectors are substituted by random Gaussian vectors following the Gaussian Design (GD) Assumption, and the 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 a 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. Astonishingly, 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 (kernel) eigenspectrum decay. It 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-Freedom (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 hyperparameters 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-parameterization, play an important role in the analysis of the learning curve of ridge regression. Within the present body of research, various papers establish bounds on 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 a unifying theory of the test error of KRR across a wide variety of settings (see Subsection 2.2 and Table 1 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-decay 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. 
setting: 
 In this section, we introduce the basic notation for ridge regression, which includes high-dimensional linear regression and kernel ridge regression as special cases.Suppose p ∈ N ∪ {∞}. Let x = (x k ) p k=1 ∈ R p be a random (feature) vector sampled from some distribution µ on R p . Let n ∈ N be an integer and denote by x 1 , ..., x n n i.i.d. draw of x. Denote the input matrix X ∈ R n×p to be a matrix with rows x ⊤ i . By fixing an orthonormal basis, we assume that the covariance matrix is diagonal:Σ def. = E µ xx ⊤ = diag(λ 1 , λ 2 , ..., λ p ) ∈ R p×p ,where the eigenvalues λ 1 ≥ λ 2 ≥ ... ≥ λ p > 0 is a decreasing sequence of positive numbers. 1We also assume that y ∈ R n is an output vector such thatEQUATIONwhere θ * ∈ R p is a deterministic vector, ϵ ∈ R n is a random vector whose entries are i.i.d. drawn from a centered random variable ϵ with variance E ϵ2 = σ 2 < ∞ and independent to X.Then the linear regressor θ(y)def. = X ⊤ (XX ⊤ + nλI n ) -1 y (2)is the minimizer of the empirical mean square loss (MSE) problem:EQUATIONwhere λ ≥ 0 is the ridge 2 . This paper focuses on bounding the test error, with which we can 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 (X, y) of sample size n and a ridge λ ≥ 0. Define the test error R to be the population mean squared error between the regressor and the true label averaged over noise.EQUATIONNote that R is a random variable depending on the samples (X, y) and the ridge λ ≥ 0. Hence, we can also view R = R n as a random variable indexed in n, where the samples (X, y) are n i.i.d. drawn input-output pairs and λ is chosen to depend on n.We decompose the test error into a bias B and variance V, which is typical for most KRR literature [32, 23, 6, 46, 29, 30, 31, 13, 14] :EQUATIONwhere B def.= E x x ⊤ θ(Xθ * ) -x ⊤ θ * 2 , V def. = E x,ϵ x ⊤ θ(ϵ) 2 .Remark 2.2 (Noiseless labels). If there is no noise in the label, that is, ϵ = 0, the test error R is simply the bias B. Hence, the analysis of the bias term B in this paper is directly applicable to the noiseless labels setting.We now summarize the combinations of assumptions and settings made in this paper.Polynomial/exponential 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 of at most finitely many continuous derivatives;2) the exponential eigen-decay is, possibly up to a canonical change in the relevant function space, equivalent to the case where the RKHS consists of 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, θ * ∈ H = H 1 , we have s ≥ 1. More generally, a larger source coefficient s implies a smoother target θ * in the RKHS H.Definition 2.3 (Interpolation space). Let s ≥ 0 be a real number. Define the interpolation spaceH s def. = {θ ∈ R p : ∥θ∥ Σ 1-s < ∞}.Assumption (SC) (Source Condition). The source coefficient of a target coefficient θ * is defined ass = inf{t > 0 : θ * ∈ H t }.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 λ = λ(n) ≥ 0 to depend on the sample size n. The ridge is considered strong (relative to the eigen-decay) if λ ≽ λ min{n,p} , that is, if λ/λ min{n,p} n→∞ ----→ 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 it ridgeless.To summarize the assumptions discussed previously, let (λ k ) p k=1 be the eigenvalues of the kernel K, and θ * def.= (θ * k ) p k=1 the coefficients of the target function being learned in the eigen-basis defined by K. Then we assume either of the following assumptions:Assumption (PE) (Polynomial Eigen-decay). Assume that λ k = Θ k k -1-a , |θ * k | = Θ k (k -r ), λ = Θ n n -bfor some constants a, b, r > 0, where a + 2 ̸ = 2r unless specified. 3 Hence, if Assumption (SC) holds, the source coefficient is s = 2r+a 1+a . We call the ridge λ strong if b ∈ (0, 1 + a], and weak if b ∈ (1 + a, ∞], under the convention that b = ∞ implies λ = 0.Assumption (EE) (Exponential Eigen-decay). Assume that λ k = Θ k e -ak , θ * k = Θ k e -rk , λ = Θ n e -bnfor some constants a, b, r > 0, where a ̸ = 2r unless specified. 4 Hence, if Assumption (SC) holds, the source coefficient is s = 2r+a a = 2r a + 1. We call the ridge λ strong if b ∈ (0, a], and weak if b ∈ (a, ∞], under the convention that b = ∞ implies λ = 0. Generic/independent features Our analysis centers on the assumptions regarding feature vectors, with a 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 kernels on hyperspheres;• kernels with bounded eigenfunctions;• radial base function (RBF) and shift-invariant kernels;• kernels on hypercubes, satisfy Assumption (GF). Most previous literature [30, 33, 36, 19] have assumptions that only a proper subset of the above kernels 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-Gaussian 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, we refer the reader to Section A. 
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 overparameterized regime, in terms of the bias B and variance V decomposition (see Equation ( 5)). Then, we will discuss the implications of our results in depth. = max{•, 0}. Before delving into the detailed discussion of our comprehensive results in Subsection 3.2, let us highlight some important observations from Table 1 .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, b related to the ridge, r related to the target function and σ 2 related to the label noise.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 1 )EQUATIONis 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, we can see that the decay of our novel bound in Equation 6 is faster than previous results. Also, we prove that the upper bound in the middle green region ,where s ∈ (1, 2), is sharp.Experimental validations of the results in Table 1 are given in Section 6.In the under-parameterized regime, the bias B and variance V terms can be bounded similarly as in over-parameterized regime. We postpone the details of these results to Section F.In this subsection, we elaborate more on the details of our results shown in Table 1 . EQUATION(n (r a) )(n 2(1 + a) ) s<1 s<1 1<s<2 s>2Our result onEQUATION(n (r a) )(n (2 a) ) 6)) of the bias term B under weak ridge and polynomial eigen-decay.Previous result on r = a 2r = 2 + aλ k = Θ k k -1-a , |θ * k | = Θ k (k -r), for some a, r > 0. Our result (Propositions D.5+D.6+E.1) 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 s = 2r+a 1+a in Assumption (SC) is shown in gray font in each colored region.same Master inequalities that we 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 can see that V = O (1) with Laplacian kernel in the left plot and V diverges with the neural tangent kernel (with 1 hidden layer) in the right plot. Hence under weak ridge and polynomial eigen-decay, the case distinction of the boundV = Θ σ 2 , Assumption (IF) holds, O σ 2 n 2a , Assumption (GF) holds (7)in Table 1 is 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 n→∞ ----→ ∞, the so-called catastrophic overfitting. In particular, our proof shows that the Gaussian Equivalent Property (GEP) does not hold under weak ridge. We are now prepared to 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!5 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, we refer the reader to Section A.Importance of ridge To address the second question posed in Section 1, it is evident that in either the under-parameterized setting with any ridge (see Section F) or the over-parameterized regime with a strong ridge (see Table 1 ), the bounds for both B 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 a 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 λ > 0 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 at a rate at most O 1 n , regardless of the eigen-decay. Hence, in a noisy setting with polynomial eigen-decay, one can find an optimal ridge λ = Θ n n -1+a (1+a)s+1 to balance both terms B 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 1 due to the so-called catastrophic overfitting phenomenon observed in [35, 14] .Improved upper bound During our research, we 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 it with the insights from [7] (see the upper right corner in Table 1 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,λ k = Θ k k -1-a and |θ * k | = Θ k (k -r ). Let s = 2r+a1+a be the source coefficient defined in Definition (SC). Then the kernel ridgeless regression has the following learning rate for the bias term B:B =    O n n -(r-a)+ for s < 1; Θ n n -(2r+a) for 1 ≤ s ≤ 2; O n n -2(1+a)for s > 2.where n is the sample size and (•)+ def.= max(•, 0).For a 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 independent features, we can prove that the upper bound is tight using the result from [46] , generalizing the result from [16] , which only showed upper bounds in 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 See Section E for details on our proof of matching lower bounds. We note that there is some KRR literature, such as [31, 36, 19] , that discusses matching upper and lower bounds of test error under more assumptions, which is beyond the scope of this paper. For a 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 a wide range of kernel settings under any regularization and source conditions. 
proof sketch: 
 All the above results in Table 1 can be derived using the following proof strategy:1. We prove a concentration result on the whitened features z under Assumptions (GF) or (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 we 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-parameterized regime, we derive the asymptotic behavior of the learning curves by plugging in the eigen-decay and the choice of 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) is 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 a broad variety of features where a universal matching lower bound does not exist.7. In the under-parameterized 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 a flowchart in Figure 4 .Master Inequalities We will now briefly introduce the key inequality used in our analysis (further details can be found in the Appendix). We will use the subscript > k or ≤ k to refer to the submatrix of a matrix consisting of columns with index > k or ≤ k (see definition C.3). The analysis relies on two crucial matrices: A k = X >k X ⊤ >k + nλI n ∈ R n×n , defined for any k ∈ N, which is employed to partition the spectrum, and a whitened input matrix Z def.= XΣ -1/2 ∈ R n×p . Additionally, we require the following definitions. Definition 4.1 (Concentration coefficients [7] ). Define the quantities:ρ def. = n ∥Σ >k ∥ op + s 1 (A k ) s n (A k ) ; ζ def. = s 1 (Z ⊤ ≤k Z ≤k ) s k (Z ⊤ ≤k Z ≤k ) ; ξ def. = s 1 (Z ⊤ ≤k Z ≤k ) n ,where s i (•) denotes the i-th largest singular value of the matrix.Definition 4.2 (Effective ranks [6] ). Let k ∈ N. Define two quantities:r k def. = Tr[Σ >k ] ∥Σ >k ∥ op = p l=k+1 λ l λ k+1 , R k def. = Tr[Σ >k ] 2 Tr[Σ 2 >k ] = p l=k+1 λ l 2 p l=k+1 λ 2 l .The Master inequalities provide upper bounds on the bias and the (scaled) variance term of the test error in the following form:B ≤ 1 + ρ 2 ζ 2 ξ -1 + ρ δ ∥θ * >k ∥ 2 Σ >k + (ζ 2 ξ -2 + ρζ 2 ξ -1 ) s 1 (A k ) 2 n 2 θ * ≤k 2 Σ -1 ≤k ; V/σ 2 ≤ ρ 2 ζ 2 ξ -1 k n + Tr[Z >k Σ 2 >k Z ⊤ >k ] n Tr[Σ 2 >k ] r k (Σ) 2 nR k (Σ) .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 a primary contribution of this paper. On the other hand, the "decay" part can be approximated using basic calculus, once a specific constant k ∈ N, smaller than the sample size n, is selected. Together, these two parts allow us 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 is 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. 
related work: 
 We briefly discuss related previous works and compare them with our results in the over-parameterized regime: (see Table 6 for more visual illustration)1. [16] considered the upper bound of B and V in 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 B 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 a tight upper bound of B when the source condition s > 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 a novel upper bound on the bias.4. [7] also provided an upper bound of V under polynomial decay, weak ridge and Assumption (GF).5. [14] showed that V is bounded above and below by positive constants under polynomial eigendecay, 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 Degree-of-Freedom (MaxDoF) Assumption. We recover their result under Assumption (GF) instead of Assumption (MaxDoF).7. We apply the result from [46] and [31] to obtain a matching lower bound in some settings and strengthen our result from O n (•) to Θ n (•). 
experiments: 
 Due to page constraints, this section focuses solely on experiments validating the Gaussian Equivalent Property (GEP). For detailed experiments on other contributions, refer to Section I. We consider a simple example: letλ k = ( 2k-1 2 π) -1-a and ψ k (•) = √ 2 sin 2k-1 2 π• such that ∥ψ k ∥ L 2 µ = 1 for µ = unif[0, 1]; let θ * k = ( 2k-1 2 π) -r .For p = ∞ and a = 1, the regression coincides with kernel ridge regression with kernel k(x, x ′ ) = min{x, 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 p must be finite. In the following experiment, we choose p = 2000, and the sample size n ranges from 100 to 1000, with ridge parameter λ = ( 2n-1 2 π) -b where b ∈ [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 z ∼ N (0, I p ) or Rademacher features z ∼ (unif{±1}) p ) coincide and match the theoretical decay.  
conclusion: 
 In this paper, we present a unifying theory and a 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 a 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 1 is not known to be sharp. It would be of interest to either improve it or find matching lower bounds in those regions; ii) Why is there a 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 σ 2 n 2a 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. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: As our contributions are theoretical justifications of commonly used AI 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: 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?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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset. 
 
 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 is presented in Section A; • an 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 in over-parameterized regime in Table 1 is presented in Section D; • the proof for a matching lower bound is presented in Section E; • the details of the proof on the non-asymptotic bound in under-parameterized regime is presented in Section F; • the concentration result on the whitened feature z 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 I;• extra tables of summary can be found in Section J.The summary of our proof can be found in the flowchart in Figure 4 .Master inequalities (Section C)Test error upper bound (Section D) Θ n (•) bound O n (•) bound matching lower bound (Section E) unknown under-param. (Section E)-O notations O • (•) , o • (•) , Ω • (•) , Θ • (•)to represents the asymptotic behaviours of 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 is clear.The primary assumptions made in this paper concern the whitened feature vectors z ∈ R p : Assumption (GF) (Generic features [7] ). Let p ∈ N ∪ {∞}. Assume the isotropic feature vector z def.= Σ -1/2 x ∈ R p and the covariance matrix Σ ∈ R p×p are such that: 7α k def. = ess inf z ∥z >k ∥ 2 Σ >k Tr[Σ >k ] = Θ k (1) , β k def. = ess sup z max    ∥z ≤k ∥ 2 2 k , ∥z >k ∥ 2 Σ >k Tr[Σ >k ] , ∥z >k ∥ 2 Σ 2 >k Tr[Σ 2 >k ]    = Θ k (1) , Remark A.1 (k = 0).For k = 0, we take the convention that β 0 def.= ess sup z max∥z∥ 2 Σ Tr[Σ] , ∥z∥ 2 Σ 2 Tr[Σ 2 ] . Remark A.2 (Intuition).The intuition is that the three fractions above have expected values of 1:E z ∥z≤k∥ 2 2 k = E z ∥z >k ∥ 2 Σ >k Tr[Σ >k ] = E z ∥z >k ∥ 2 Σ 2 >k Tr[Σ 2 >k ]= 1. Hence, Assumption (GF) imposes strong concentration on z at each truncation point k ∈ 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 a weaker probability. For simplicity reasons, we only consider the assumption in the above formulation.Assumption (GF) encompasses both cases of dependent and independent features z k , 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-Gaussian features). Suppose p ∈ N. Assume that the features z k 's in the isotropic feature vector z are independent to each other and there exists a constant G > 0 such that the sub-Gaussian norm ∥z k ∥ ψ2 of any feature z k is bounded by G. In over-parameterized regime, we also assume that there exists some constant η > 1 independent to n such that p > ηn.Remark A.4 (Infinite rank). With Assumption (GF), the feature dimension p can be taken as ∞; with Assumption (IF), however, if no further boundedness assumption is imposed, the norm ∥x∥ 2 = p k=1 λ k z 2 k can be undefined if p = ∞. However, if the sub-Gaussian variables z k '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 z k are additionally bounded, then Assumption (IF) becomes a 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 on 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 a 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.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): 7 We write ∥v∥ M def.v ⊤ Mv for PDS matrix M and any vector v. See Definition C.1 Section C for more details.Assumption (GD) (Gaussian Design). The feature vector z ∼ N (0, I p ) is distributed as isotropic Gaussian.Note that Assumption (IF) is much weaker than Assumption (GD) in the sense that: i) the distribution of the feature vector z is no longer rotational invariant or enjoys anti-concentration property;8 ii) the distribution of each feature z k needs not be continuous; iii) the features z k 's needs not be identical.Meanwhile, Assumption (IF) appear commonly in KRR literature, for example [6, 46, 23, 5, 13, 14] .Examples that satisfy Assumption (GF), which is first introduced by [7] , includes:1. dot-product kernels 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 our assumptions with previous literature, we first define the ∞-norm in the ridge regression setting analog to its kernel counterpart:Definition A.6 (∞-norm). Fix a distribution µ on R p and let v ∈ R p . Define ∥v∥ ∞ def. = ess sup x∼µ |x ⊤ v| = sup{a ∈ R|a ≤ |x ⊤ v| a.s. for all x ∼ µ} Remark A.7. Note that ∥•∥ ∞ is indeed a semi-norm and for all v ∈ R p , we have ∥v∥ Σ ≤ ∥v∥ ∞ .Choose k = 0 and Assumption (GF) and Remark A.1 imply:∥x∥ 2 ∞ = ess sup x ∥x∥ 2 2 = ess sup z ∥z∥ 2 Σ ≤ β 0 def. = ess sup z max ∥z∥ 2 Σ Tr[Σ] , ∥z∥ 2 Σ 2 Tr[Σ 2 ] < ∞,as we assume that Tr[Σ] < ∞.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 a random vector x ∈ R p with covariance Σ = E[xx ⊤ ], let z = Σ -1/2x be the isotropic random vector. Define the embedding coefficient:η 0 = inf η {ess sup x ∥x∥ 2 Σ η-1 < ∞} = inf η {ess sup z ∥z∥ 2 Σ η < ∞}.Suppose the eigen-decay is polynomial:λ k = Θ k k -1-afor some a > 0. Assume the embedding coefficient η 0 = 1 1+a . Remark A.8 (General range of η 0 ). Rewrite the expression:∥x∥ 2 Σ η-1 = x ⊤ Σ η-1 x = p k=1 λ η-1 k x 2 k = p k=1 λ η k z 2 k = Θ k p k=1 k -η(1+a) z 2 kwhere we write x = (x k ) p k=1 ∈ R p and z = (z k ) p k=1 ∈ R p . In the kernel case, it is obvious that η 0 ≤ 1: for all inputs x ∈ X with embedding x = K(x, •) in the feature space H, sup x k(x, x) = ∥x∥ 2 2 < ∞. Since the eigenvalues have polynomial decay, we have η 0 ≥ 1 1+a , or otherwise there were some η ∈ (η 0 , 1 1+a ) such that:E x ∥x∥ 2 Σ η-1 = Ω E z p k=1 k -η(1+a) z 2 k = Ω p k=1 k -η(1+a) = ∞,contradicting Assumption (EC). Thus one have η 0 ∈ [ 1 1+a , 1] in general. Hence Assumption (GF) is a much weaker assumption than Assumption (EC) in the sense that the former one only requires η 0 ≤ 1, which holds in general; while the latter one requires η 0 = 1 1+a , which is the smallest possible size of η 0 . Hence, many examples mentioned in [50] , that satisfy Assumption (EC) also satisfy Assumption (GF). For instance, the examples include:1. dot-product kernels 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 in [33] with our notation: Assumption (MaxDoF) (Maximal Degree-of-Freedom). For any λ > 0 and s ≥ 1, define:F s (λ) def. = ess sup x (Σ + λI p ) -s/2 x 2 Σ s-1 . Assume: there exists n ∈ N such that n ≥ 5F s (λ n ) max{1, log(14F s (λ n ))/δ}for some constant δ ∈ (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 x. Examples that satisfy Assumption (MaxDoF) include:1. 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 "deterministic equivalent" using a list of assumptions for each fixed sample size n. To avoid introducing extra notations, we list their assumption here in a semi-rigorous way: Assumption (LH) (Low/High-degree feature concentration). Fix n ∈ N and λ ≥ 0. Suppose there exists an integer k ≤ p such that:1. r λ k def. = λ+Tr[Σ >k ] λ k+1 ≥ 2n;2. the low-degree feature vector x ≤k ∈ R k is highly concentrated; 3. with high probability, the high-degree feature vector x >k ∈ R p-k satisfies:X >k X ⊤ >k -Tr[Σ >k ]I n op ≤ C n r λ k • (λ + Tr[Σ >k ])where C > 1 is a constant depending on n, k.Point 3 in Assumption (LH) is closely related to Assumption (GF) since:1 n n i=1 ∥z >k ∥ 2 Σ >k -Tr[Σ >k ] = 1 n Tr[X >k X ⊤ >k -Tr[Σ >k ]I n ] ≤ Tr[X >k X ⊤ >k -Tr[Σ >k ]I n ] op , if ess sup x ∥z >k ∥ 2 Σ >k Tr[Σ >k ] = Θ k (1), then 1 n n i=1 ∥z >k ∥ 2 Σ >k -Tr[Σ >k ] = Ω k (1). According to [36] , examples that satisfy Assumption (LH) include:1. kernel satisfying Assumption (IF); 2. dot-product kernel 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) (L 2+ϵ -L 2 Moment-Equivalent Assumption). Fix a sample (x i ) n i=1. Suppose there exists some ϵ, κ > 0 such that:1. for any k ∈ N and any function f ∈ H >k in the high-degree feature space, we have∥f ∥ L 2+ϵ ≤ κ ∥f ∥ L 2 . (a) if ϵ > 2, then no extra assumption is required; (b) if ϵ ∈ (0, 2], then κn 2-ϵ 2ϵ+ϵ 2 log n √ n Tr[Σ 2 >k ] Tr[Σ >k ] is small. 2. with high probability, max i=1,...,n ∥(zi) >k ∥ 2 Σ >k Tr[Σ >k ] ≈ 1;3. with high probability, max i=1,...,n∥(zi) >k ∥ 2 Σ 2 >k Tr[Σ 2 >k ]≈ 1;4. with high probability, max i=1,...,n ∥(zi)≤k∥2 2 k = O k (1).While points 2-4 are implied by the weakened version of Assumption (GF), point 1 is a strong geometric assumption on the RKHS H. According to [19] , the addition of point 1 can drop the logarithmic terms in the upper bound of test error under weak ridge, and thus strengthening some results in Table 1 from Θ (•) to Θ (•). Examples satisfying Assumption (ME) includes:1. rotational invariant kernel.A random feature setting can be considered as a midpoint between independent and dependent features: Let W ∈ R p×d be a random matrix, typically with i.i.d. random entries, and z ∈ R d be the input vector, usually comprising independent entries. We define the random feature x ∈ R p as a one-hidden-layer neural network:x def.= φ(Wz), where φ : R → R represents an activation function acting entry-wise on Wz. Thus, the coordinates of the pre-activation are 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.Many KRR literature [29, 30, 31, 33] introduced the notation of interpolation space and the source condition on the L 2 -integrable target function f * . This can be easily translated to the notion of generalized vector norm. Definition A.9 (Interpolation space). Let s ≥ 0 be a real number. Define the interpolation spaceH s def. = {θ ∈ R p : ∥θ∥ Σ 1-s < ∞}. Evidently, if s 1 ≤ s 2 , then ∥θ∥ Σ 1-s 2 ≤ ∥θ∥ Σ 1-s 1 and hence H s1 ⊃ H s2 .The intuition is that, in the KRR setting, the space H s interpolates between the L 2 -space L 2 µ (X ) ⊃ H 0 and the RKHS H = H 1 .Given the asymptotic of the eigen-decay λ k and the target coefficient θ * , we can find the largest possible source coefficient s. For instance, ifλ k = Θ k k -1-a for some a > 0 and |θ * k | = Θ k (k -r), then we can choose s to be 2r+a 1+a :θ * ∈ H t ⇔ ∥θ * ∥ 2 Σ 1-t < ∞ ⇔ p k=1 (θ * ) 2 λ 1-t k < ∞ ⇔ p k=1 k -2r k (1-t)(-1-a) < ∞ ⇔ p k=1 k -1-a+t+ta-2r < ∞ ⇔ -1 -a + t + ta -2r < -1 ⇔ t < 2r + a 1 + a . Suppose λ k = Θ k e -ak , |θ * k | = Θ k e -rk for a, r > 0.Then we can choose s to be 2r a + 1:θ * ∈ H t ⇔ ∥θ * ∥ 2 Σ 1-t < ∞ ⇔ p k=1 (θ * ) 2 λ 1-t k < ∞ ⇔ p k=1 e -2rk (e -ak ) 1-t < ∞ ⇔ p k=1 e -k(2r+a-at) < ∞ ⇔ 2r + a -at > 0 ⇔ t < 2r a + 1.KRR can be regarded as ridge regression on the feature space, where the positive definite symmetric (PDS) kernel K sends each input x ∈ X to a vector/function K(x, •) in the corresponding reproducing kernel Hilbert space (RKHS) H, and the kernel regressor is simply a 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 a (data-generating) distribution on an input space X . Let K : X × X → R be a positive definite symmetric kernel with corresponding reproducing kernel Hilbert space (RKHS) H. By Mercer decomposition, we have for all x, x ′ ∈ supp(µ) ⊂ X :K(x, x ′ ) = p k=1 λ k ψ k (x)ψ k (x ′ ),where λ k 's are the eigenvalues of K indexed in decreasing order and ψ k : X → R's are eigenfunctions of K forming an orthonormal basis on L 2 µ (X ):E x∼µ [ψ k (x)ψ l (x)] = δ kl for all k, l ∈ N. Hence for each x ∈ supp(µ) ⊂ X , K(x,•) is a feature vector in the RKHS H, which has an orthonormal basisϕ k = 1 √ λ k ψ k p k=1.Let y = f * (x) + ϵ be the labels where f * ∈ L2 µ (X ) and ϵ is a centered random variable with finite variance independent to x. Let (x i , y i ) n i=1 be a set of i.i.d. drawn input-output pairs. The kernel ridge regression is in the form:f def. = min f ∈H 1 n n i=1 (f (x i ) -y i ) 2 + λ ∥f ∥In this section, we will explain the reason to assume the eigen-decay to be either polynomial or exponential in the paper.Concretely, the "polynomial decay regime" arises as the Neural Tangent Kernel (NTK) limit of Multi-Layer Perceptrons (MLPs) with an activation function of the form σ s (t) def.= max 0, t s , where s ≥ 1, as studied in [4] . In cases where s is an integer, σ s represents the (s -1)-th iterated anti-derivative of the ReLU function, making it exactly s times weakly differentiable. Suppose X is the d-dimensional sphere S d def.= {u ∈ R d : |u| = 1} (with its usual Riemannian metric). In this scenario, every neural network function f : S d → R belongs to the Sobolev space H s (S d ) (see Proposition B.7 in Appendix B.2), characterized by having s continuous and integrable (weak) partial derivatives on S d . Additionally, the NTK limit manifests as a "radially symmetric kernel", specifically of the form k(x, y) = κ(x ⊤ y) for some suitable function κ :[-1, 1] → R.It 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 kernel regressor exhibits the correct level of smoothness matching that of the theoretical solution to the PDE, with its higher-order derivatives also converging. It 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 a connection between the spectral eigen-decay and the smoothness of the Reproducing Kernel Hilbert Space (RKHS), which is independent of the rest of the paper. Readers primarily interested in the proofs presented in Table 1 may opt to skip this section and proceed to Section C during their initial reading.Fix a positive integer d ∈ N and let X be a non-empty subset of R d . We equip X with a regular Borel probability measure µ, which we specify shortly. We denote the space of (equivalence classes of) µ-square-integrable on R d by L 2 µ (R d ), equipped with its usual L 2 µ -norm ∥ • ∥ L 2 µ . Consider a kernel κ : X × X → R with its associated to the RKHS (H, ⟨•, •⟩ κ ) (abbreviated by H). We denote the induced norm on H by ∥ • ∥ κ . By the Mercer decomposition theorem, see [40, Theorem 2.30] , there is some M ∈ N ∪ {∞} such that we may writeEQUATIONwhere (ψ i ) M i=0 are normalized eigenfunctions of the linear operator T κ (f )(x) =x∈X κ(x, u)f (u) du on L 2 µ (X ) and each eigenvalue (λ i ) ∞ i=0 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. = k(⟨x, y⟩)for each x, y ∈ S d . As shown in [41] , κ is a kernel if and only if there is a summable sequence of non-negative real numbers(α i ) ∞ i=0 satisfying k(t) = ∞ i=0 α i t i for each t ∈ [-1, 1]. Kernels of the form (9) are called radial. The RKHS H associated to κ consists of all functions f :EQUATIONfor a square-summable real sequence (α j,i ) ∞,Ji j,i=1 ; i.e.Ji j=1 α 2 j,i < ∞ (where(α i,j ) ∞,Ji i,j=1depends only on the radial function k, and thus only on the radial kernel κ; and ( ψj,i ) in the representation (10) satisfy µ j ∈ Θ((j + 1) -2s ).As discussed in [22, Lemma B.1] in this case the norms of H and on H s (S d ) are equivalent9 .We consider the case where X is a 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 , g) is a d-dimensional compact Riemannian manifold, with d ≥ 2, and µ = V g (X ) -1 V g is the uniform law on (X , g) and V g is its volume measure, (ii) Bounded Euclidean domain: X is a non-empty bounded open domain in R d with Lipschitz boundary and µ is the normalized Lebesgue measure.In cases (i)-(ii), X can be viewed as a Riemannian manifold (possibly with boundary).In what follows, we let ∆ denote either of the following Laplacian, depending on which of assumption (DR) we have assumed. If (i) or (ii) holds then ∆ will denote the usual Laplacian-Beltrami operator on X , note that when (iii) holds then ∆ =d i=1 ∂ 2 ∂x 2 i. We denote the eigenfunctions of ∆ by ( ψi ) i∈N whose respective eigenvalues λ 1 ≤ λ 2 ≤ . . . are arranged in a non-decreasing order. If (iii) holds, then ∆ will denote the Dirichlet Laplacian (see [11, Section 6.1.2]) on X (with its usual Euclidean Riemannian metric) which acts on the spaces of functions vanishing on the boundary ∂X of X ; namely on the homogeneous Sobolev space H 1 0 (X ). Example B.2. Under assumption (i), the eigenfunctions of ∆ are the Hermite polynomials onL 2 µ (R d ) ψi (x) = (-1) i e x 2 /2 ∂ i ∂x i (e -x 2 /2 ) for each i ∈ N + .For concreteness, the size, in L 1 µ -norm, of the Hermite polynomials is computed in [28, Theorem 2.1] where it it shown that∥ ψi ∥ L 1 µ ≲ (i!) 1/2 i 1 /2 (1 + O(1/i)).Example B.3. Suppose that X is the d-dimensional sphere S d def.= {x ∈ R d+1 : ∥x∥ 2 = 1} equipped with the (usual) Riemannian metric induced by inclusion into the d + 1-dimensional Euclidean space R d+1 . Let µ be the normalized (uniform) Riemannian (volume) measure on R d . Then, ( ψi,j (x)) ∞,Ji i=1,j=1 are an orthogonrmal basis of L 2 µ consisting of spherical Harmonics (counting multiplicities J i ∈ N + for each eigenvalue i ∈ N + ); that is the restriction of a homogeneous polynomial f : R d+1 → R satisfying ∆f = 0 to there sphere S d . Spherical harmonics are not very large (in uniform norm) [17, Theorem 1.6 ] and one can show that ∥ ψi,j ∥ ≲ λ Chapter 2] for further details on spherical harmonics.(d-1)/4 i , for each i ∈ N + . See [2,Let (X , g) be a compact (smooth) Riemannian manifold, possibly with a boundary ∂X . For any k ∈ N + , we define C 2 k (M ) be the set of smooth functions f on X satisfyingM |∇ i f | 2 g dµ < ∞Square-Integrable Partial Derivatives and f (x) = 0 (∀x ∈ ∂X )Homogeneous Boundary Conditions (11) where µ is the Riemannian volume measure on (X , g), ∇ is the covariant derivative thereon. Then, the Sobolev space H k 0 (X , g) is the Hilbert space obtained as the completion of C p k (X ) with respectto the norm ∥f ∥ H k (X ) def. = k i=1 ∥∇ i f ∥ L 2 µ .Remark B.4 (The Sobolev Spaces H k 0 (X , g) and H k (X , g)). Observe that when X is a compact Riemannian manifold without boundary, i.e. when ∂X = ∅; then the condition f (x) = 0 for all x in the boundary set ∂X holds vacuously. In this case, this condition can be ignored, and the spaces H k 0 (X , g) coincide with the usual Sobolev spaces H k (X , g) for Riemannian manifolds without boundary; where H k (X , g) is defined much the same way as H k 0 (X , g) 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. spectral decayEQUATIONis finite; wherec d def. = (d -2)/2. That is, the norms ∥ • ∥ k and ∥ • ∥ H k (X ) are equivalent.The key takeaway of Example B.5, is that the smoothness of a function on there sphere (S d , g), i.e. the largest k for which f ∈ H k 0 (S d , g), can be expressed in terms of the decay rate of its projection onto the basis of spherical harmonics. Indeed, this expression (12) implies that f ∈ H k 0 (S d , g) only if x∈S d f (x) ψi,j (x) µ(dx) 2 ∈ O (j + c d ) -2k-ϵ for all ε > 0.This observation was used in [24, Chapter 4] and circa [22, Lemma B.1] to characterize the smoothness of functions in the RKHS associated to certain radial kernels, e.g. certain NTK limits. We now generalize this argument, and use it to relate the spectral decay rate of a kernel to the smoothnes/regularity of the functions in its associated RKHS.We require that the L 2 µ (X ) norm of the eigenfunctions are non-vanishing and non-exploding. Assumption (ND) (Non-degenerate L 2 -Norm). Suppose that:(i) Non-vanishing: 0 < inf i∈[M ] ∥ ψi ∥ L 2 µ (X ) , (ii) Non-exploding: sup i∈[M ] ∥ ψi ∥ L 2 µ (X ) < ∞.Again, if ( ψi ) ∞ i=0 is orthonormal then (i) and (ii) necessarily hold and this is a non-assumption.To generalize the discussion in Example B.1, we first define the linear standardization operatorEQUATION)Example B.6 (Standardization Is Inclusion for Radial Kernels on Spheres). In the setting of Example B.1, we have that (up to reordering) ψ i,j = ψi,j . Since, in that case, for k large enough on hasH = H k 0 (S d , g) then A is simply the inclusion operator of H k 0 (S d , g) into L 2 µ (S d ).In what follows, when we assume Assumption (DR) (iii), we will use C ∞ (X ) to denote the set of smooth functions on the closure X of X in the norm topology on R d . Under Assumption (DR) (i)-(ii), we use C ∞ (X ) to denote C ∞ (X ); that is, the set of smooth functions on the smooth manifold X .Proposition B.7 (Identification: Spectral Decay and Standardized Regularity). Suppose that Assumption (DR) holds and that (ψ i ) M i=0 are orthonormal in H. Then, the linear operator A, defined in (13) , is an isometric embedding when M ≤ ∞ (resp. isometric isomorphism when M = ∞). Moreover, it characterizes the "regularity" of functions in H via:1. Sub-Exponential Decay: If κ has infinite-rank (M = ∞) and there exists an r > 0 such that |⟨f,ψ i ⟩ κ | ≲ i -r and inf ε>0 lim i→∞ |⟨f, ψ i ⟩ κ | i -r+ε = ∞ then A(f ) ∈ H (1+r)d 2 0 (X ) \ ε>0 H (1+r)d 2 +ε 0 (X ) Sobolev Space Characterization and A(f ) ∈ rd/2>k C k (X ) C k -Space Description .2. Exponential Decay: If κ has infinite-rank (M = ∞) and there exists some r > 0 such that |⟨f,ψ i ⟩ κ | ≲ e -r i , then A(f ) ∈ C ∞ (X ).3. Finite-Rank:(ii) If Assumption (DR) (ii) holds then: κ has finite rank (M < ∞) then A(f ) is smooth. (iii) If Assumption (DR) (iii) holds then: κ has finite rank (M < ∞) then A(f ) is real- analytic.A 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 a 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 of Convergence Rates). If (f N ) N ∈N is a sequence in H converging to some f ∈ H then: for each N ∈ N on has ∥f N -f ∥ κ = ∥A(f N ) -A(f )∥ L 2 µ (R d ). We now are now prepared to prove Proposition B.7.Proof of Proposition B.7. We first show that A is a linear isometric embedding (resp. linear isomorphism). This allows us to relay the spectral decay rate of any function f in H to that of its "standardization" A(f ) in L 2 µ (X ). We then use this identification, together with results from spectral theory (see [11] for references) to obtain our conclusion.Step 1 -A is a Linear Isometric Embedding (Resp. Linear Isomorphism): Observe that A admits a linear left-inverse given byB : L 2 µ (X ) → H f = ∞ i=0 ⟨f, ψi ⟩ L 2 µ (X ) ψi → M i=0 ⟨f, ψ i ⟩ L 2 µ (X ) ∥ ψi ∥ L 2 µ (X ) ψ i .In particular, A is a linear isomorphism if and only if M = ∞; since otherwise B is not a two-sided (linear) inverse. Furthermore, A is an isometric embedding (resp. isometric isomorphism when M = ∞) since due to the following. For each f ∈ H we have thatEQUATIONEQUATIONEQUATIONwhere ( 14) and ( 16) held by virtue of (ψ i ) M i=0 being an orthonormal basis of H. From ( 14)-( 17) we conclude that for each f ∈ H we have ∥A(f )∥ L 2 µ (X ) = ∥f ∥ κ . Thus, A is an isometric embedding. Finite Rank Kernel: Suppose that M < ∞. We consider two cases in Assumption (DR) separately.Under Assumption (DR) (ii), [11, Corollary 9.28] guarantees that each ψ0 , . . . , ψM 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 ψ0 , . . . , ψM is real-analytic. Since any finite sum of real analytic functions is again real-analytic then A(f ) is real-analytic.Suppose that M = ∞ and fix s > 0. By definition of (ψ i ) ∞ i=0 and of the Sobolev space H s (X ) we have that:EQUATIONSince f ∈ L 2 µ (X ) if and only if ∥f ∥ H s (X ) is well-defined and finite. Consequentially, the elements of the Sobolev space H s (X ) are characterized by the summability of the right-hand side of (18) . That is, for eachEQUATIONBy Assumption (ND), both 0 < C def.∥ ψi ∥ L 2 µ (X ) andC def. = sup i∈[M ] ∥ ψi ∥ L 2 µ (X )< ∞ are well-defined, non-negative real numbers. Therefore, for every i ∈ NEQUATIONFrom (20) we deduce that: for each f ∈ L 2 µ (X ) and every s > 01 C ∞ i=0 |⟨f, ψ i ⟩ κ | 2 (1 -λi ) s ≤ ∞ i=0 |⟨f, ψ i ⟩ κ | 2 ∥ ψi ∥ L 2 µ (X ) (1 -λi ) s ≤ 1 C ∞ i=0 |⟨f, ψ i ⟩ κ | 2 (1 -λi ) s .Consequentially, (18) implies thatEQUATION)Step 2 -Asymptotics of Laplacian Eigenspectrum Under Assumption (DR) (ii), Weyl's law for compact Riemannian manifolds (see e.g. [11, Corollary 9.35] ) implies that there are dimensional (depending on d, X , and on g)EQUATIONwherev d def. = V ({x ∈ R d : ∥x∥ 2 ≤ 1}) = π d/2Γ(1+d/2) and where V is the d-dimensional Lebesgue measure on R d . Under Assumption (DR) (iii), Weyl's law (see e.g. [11, Theorem 6.27] ) implies that: there are dimensional (depending on d and on X ) constants 0 < CW :1 ≤ CW :2 < ∞ such that: for each i ∈ NEQUATIONWith some abuse of notation, for i = 1, 2, we write C W :i for C g W :i or CW :i depending on which of Assumptions (DR) (ii) or (iii) are being used. We therefore, wild a mild abuse of notation, we collect ( 22) and ( 23) into the following single expression:EQUATIONwhere the constant c > 0 is defined byc def. = π d/2 Γ(1+d/2) Vg(X ) : if Assumptions (DR) (ii) holds π d/2 Γ(1+d/2) V (X ): if Assumptions (DR) (iii) holds .Combining ( 21) with ( 24), we find thatEQUATIONPulling out the common c 2s/d factor in all summands on the right-hand side of ( 25) we find that: for any s > 0 any f ∈ L 2 µ (X ) belongs to H s (X ) if and only ifEQUATION1. Sub-Exponential Decay: Suppose that there exists an r > 0 such that |⟨f, ψ i ⟩ κ | ≲ i -r and for every ε > 0 we have limi→∞ |⟨f, ψ i ⟩ κ | i -r+ε = ∞ then (26) implies that A(f ) ∈ H (1+r)d 2 0 (X ) \ ε>0 H (1+r)d 2 +ε 0 (X ).If Assumption (DR) (ii) or (iii) holds the Sobolev embedding theorem for Riemannian manifolds with boundary, as formulated in [11, Theorem 9.26] , implies that H sr 0 (X ) ⊆ C kr (X ) where s r -d/2 > k r for some k r ≥ 0 to be determined shortly; where for us s r def.= (1 + r)d/2. Therefore, dr/2 > k r . Consequentially, for each f ∈ H we have thatA(f ) ∈ rd/2>k C k (X ).2. Exponential Decay: Suppose that there exists some r > 0 such that |⟨f,ψ i ⟩ κ | ≲ e -r i .Then, then (26) implies that A(f ) ∈ ∩ s>0 H s 0 (X ). By the Sobolev Embedding Theorem, in the bounded case ([11, Theorem 9.2.6])A(f ) ∈ C ∞ (X ).In this section, we will present and proof the Master inequalities, which is crucial in our argument.Our approach bounds each term in the bias-variance decomposition in line (5):R = E ϵ ∥ θ(Xθ * + ϵ) -θ * ∥ 2 Σ = B + V, under minimal assumptions.We first introduce some more notations. We define the empirical covariance matrix:Σ def. = 1 n X ⊤ X = 1 n n i=1 x i x ⊤ i ∈ R p×p ,and denote by z def.= Σ -1/2 x ∈ R p the whitened/isotropic feature vector where E µ zz ⊤ = I p ∈ R p×p . Denote the whitened input matrix by Z def.= XΣ -1/2 ∈ R n×p , then the rows of Z are isotropic centered i.i.d. random vectors.We introduce the notation of a generalized vector norm, which will be frequently used in this paper: Definition C.1 (Generalized vector norm). We denote ∥v∥ M def.v ⊤ Mv for any positive definite matrix M and vector v. Remark C.2 (Examples). Let v ∈ R p and we have ∥v∥2 2 = v ⊤ I p v = ∥v∥ 2 Ip, where I p is the identity matrix. Another example is that the euclidean norm of x equals to the Σ-norm of its whitened counterpart z: ∥x∥2 2 = x ⊤ x = z ⊤ Σz = ∥z∥ 2 Σ . Furthermore, if M 1 ≼ M 2 , we have ∥v∥ M1 ≤ ∥v∥ M2 . In particular, since Σ ≼ λ 1 I p , we have ∥v∥ Σ ≤ λ 1 ∥v∥ 2 .Lastly, it is convenient to write the expected values in a generalized vector norm: fix a distribution µ, an input block X ∈ R n×p , where its rows are drawn i.i.d. by µ, and denote by μ = 1 n n i=1 δ xi the empirical distribution of µ, then for any v ∈ R p , we have -k) . Analogously, for any non-square matrix M ∈ R N ×M , we writeE x∼µ (x ⊤ v) 2 = ∥v∥ 2 Σ ; E x∼μ (x ⊤ v) 2 = ∥v∥ 2 Σ . Definition C.3 (Truncated Terms). For any vector v ∈ R M , write v = v ≤k ⊕ v >k ∈ R k ⊕ R M -k . For any square matrix M ∈ R M ×M , write M = M ≤k * * M >k with M ≤k ∈ R k×k and M >k ∈ R (M -k)×(MM = M ≤k ⊕ M >k ∈ R N ×k ⊕ R N ×(M -k) . Also write M -k def. = M ≤k-1 ⊕ M >k ∈ R N ×(M -1) and M l:j = [M i,k ] j k=l+1 ∈ R N ×(j-l) . Denote A def. = XX ⊤ + nλI n ∈ R n×n . For any k ∈ N, denote A k = X >k X ⊤ >k + nλI n ∈ R n×n .The symmetric matrix A k plays an important role in the analysis. Intuitively, when k is chosen appropriately, A k is approximately equal to a 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 k ∈ N. Define two quantities:r k def. = Tr[Σ >k ] ∥Σ >k ∥ op = p l=k+1 λ l λ k+1 , R k def. = Tr[Σ >k ] 2 Tr[Σ 2 >k ] = p l=k+1 λ l 2 p l=k+1 λ 2 l . Note that we have r k ≤ R k ≤ r 2 k . 10Definition C.5 (Concentration coefficients [7] ). Define the quantities: 11ρ n,k def. = n ∥Σ >k ∥ op + s 1 (A k ) s n (A k ) ; ζ n,k def. = s 1 (Z ⊤ ≤k Z ≤k ) s k (Z ⊤ ≤k Z ≤k ) ; ξ n,k def. = s 1 (Z ⊤ ≤k Z ≤k ) n .where s i (•) denotes the i-th largest singular value of the matrix.To enhance readability, we will omit the subscript • n,k when the context is clear. The intuition of the concentration coefficients is that for fixed k ∈ N and n large enough, ζ and ξ concentrate around some constants; when k is smaller but scales with n, ρ converges to a constant, as it essentially represents the condition number of A k . As mentioned earlier, the spectrum of A k is bounded. Therefore, selecting an appropriate k ensures that all three concentration coefficients converge to certain constants.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 k ∈ N be an integer. For any δ ∈ (0, 1), with probability at least 1 -δ,B ≤ 1 + ρ 2 ζ 2 ξ -1 + ρ δ ∥θ * >k ∥ 2 Σ >k + (ζ 2 ξ -2 + ρζ 2 ξ -1 ) s 1 (A k ) 2 n 2 θ * ≤k 2 Σ -1 ≤k .Proof. We begin by bounding the terms that appear in Lemma H.8: plug in Definition C.5 of ρ, ζ, ξ, sinces 1 (A -1 k ) 2 s n (A -1 k ) 2 s 1 (Z ⊤ ≤k Z ≤k ) s k (Z ⊤ ≤k Z ≤k ) 2 = s 1 (A k ) 2 s n (A k ) 2 s 1 (Z ⊤ ≤k Z ≤k ) 2 s k (Z ⊤ ≤k Z ≤k ) 2 n s 1 (Z ⊤ ≤k Z ≤k ) 1 n ≤ ρ 2 ζ 2 ξ -1 • 1 n 1 s n (A -1 k ) 2 s k (Z ⊤ ≤k Z ≤k ) 2 = s 1 (A k ) 2 s k (Z ⊤ ≤k Z ≤k ) 2 = s 1 (A k ) 2 n 2 s 1 (Z ⊤ ≤k Z ≤k ) 2 s k (Z ⊤ ≤k Z ≤k ) 2 n 2 s 1 (Z ⊤ ≤k Z ≤k ) 2 = s 1 (A k ) 2 n 2 • ζ 2 ξ -2 ∥Σ >k ∥ op s 1 (A -1 k ) = ∥Σ >k ∥ op s n (A k ) = n ∥Σ >k ∥ op s n (A k ) 1 n ≤ ρ • 1 n ∥Σ >k ∥ op s 1 (A -1 k ) s n (A -1 k ) 2 s 1 (Z ⊤ ≤k Z ≤k ) s k (Z ⊤ ≤k Z ≤k ) 2 = n ∥Σ >k ∥ op s n (A k ) s 1 (A k ) 2 n 2 s 1 (Z ⊤ ≤k Z ≤k ) 2 s k (Z ⊤ ≤k Z ≤k ) 2 n s 1 (Z ⊤ ≤k Z ≤k ) ≤ ρζ 2 ξ -1 s 1 (A k ) 2 n 2 ,we haveEQUATIONWe regroup the terms into:EQUATIONBy Lemma G.6, we can further simplify the expression into a high probability bound: for any δ ∈ (0, 1), with a probability at least 1 -δ, it holds thatEQUATION)Note that 1/δ > 1 and we obtain the result. 11 Alternatively, one can define a smaller ρ n,k def.= max{n∥Σ >k ∥ op ,s 1 (A k )} sn(A k ) ≤ n∥Σ >k ∥ op +s 1 (A k ) sn(A k ) . If s1(A k ) = Θ(nλ k ) = Θ(n ∥Σ >k ∥ op ), the two definitions differs only by a constant.Proposition C.7 (Master inequality for V, [46, 7] ). Let k ∈ N be an integer. Then the variance is bounded by:V/σ 2 ≤ ρ 2 ζ 2 ξ -1 k n + Tr[Z >k Σ 2 >k Z ⊤ >k ] n Tr[Σ 2 >k ] r k (Σ) 2 nR k (Σ) ,where σ 2 def. = E ϵ 2 ≥ 0 is the noise level.Proof. We start from Lemma H.9:V/σ 2 ≤ s 1 (A -1 k ) 2 Tr[X ≤k Σ -1 ≤k X ⊤ ≤k ] s n (A -1 k ) 2 s k (Σ -1/2 ≤k X ⊤ ≤k X ≤k Σ -1/2 ≤k ) 2 + s 1 (A -1 k ) 2 Tr[X >k Σ >k X ⊤ >k ] = s 1 (A k ) 2 s n (A k ) 2 Tr[Z ≤k Z ⊤ ≤k ] s k (Z ⊤ ≤k Z ≤k ) 2 + n 2 ∥Σ >k ∥ 2 op s n (A k ) 2 Tr[X >k Σ >k X ⊤ >k ] n 2 ∥Σ >k ∥ 2 op ≤ ρ 2 Tr[Z ≤k Z ⊤ ≤k ] s k (Z ⊤ ≤k Z ≤k ) 2 + Tr[X >k Σ >k X ⊤ >k ] n 2 ∥Σ >k ∥ 2 op ≤ ρ 2 ks 1 (Z ⊤ ≤k Z ≤k ) s k (Z ⊤ ≤k Z ≤k ) 2 + Tr[X >k Σ >k X ⊤ >k ] n Tr[Σ 2 >k ] Tr[Σ >k ] 2 n ∥Σ >k ∥ 2 op Tr[Σ 2 >k ] Tr[Σ >k ] 2 ≤ ρ 2 ζ 2 ξ -1 k n + Tr[X >k Σ >k X ⊤ >k ] n Tr[Σ 2 >k ] r k (Σ) 2 nR k (Σ) = ρ 2 ζ 2 ξ -1 k n + Tr[Z >k Σ 2 >k Z ⊤ >k ] n Tr[Σ 2 >k ] r k (Σ) 2 nR k (Σ)where ξ n,kdef. = s1(Z ⊤ ≤k Z ≤k ) n , ζ n,k def. = s1(Z ⊤ ≤k Z ≤k ) s k (Z ⊤ ≤k Z ≤k ) , ρ n,k def. = n∥Σ >k ∥ op +s1(A k ) sn(A k ) , r k def. = Tr[Σ >k ] ∥Σ >k ∥ op , R k def. = Tr[Σ >k ] 2 Tr[Σ 2 >k ] .Recall that B def.= ∥ θ(Xθ * ) -θ * ∥ 2 Σ . Let k ∈ N be an integer. For any δ ∈ (0, 1), with probability at least 1 -δ, we haveEQUATION)We see that:1. the regressor barely learns the tail of the target (the eigenfunctions with small eigenvalues), thus the first term ∥θ * >k ∥ 2 Σ >k in the upper bound is just a multiple of the Σ-norm square (or L 2 µ -norm square in KRR setting) of the target's tail; 2. the second term indicates that the regressor learns well if the ridge λ is small, showing the trad-off between (noiseless) interpolation and regularization;3. the term θ * ≤k 2 Σ -1 ≤k corresponds to norm square of the target's head in the interpolation space H 2 . This term will explain the so-called saturation effect reported in [29] where the bias ceases to improve once the source coefficient s in Assumption (SC) surpasses 2. Consequently, the bias term B bound in Table 1 is closely related to the constant min s, 2.[46, 7] also derived a non-asymptotic bound of V. Recall thatEQUATION)We see that:1. the upper bound is proportional to noise level σ 2 = E ϵ 2 ≥ 0;2. we will show later that for n large enough, the second term is approximately k n , hence the decay rate ofV is at most O n,k n -1 .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 on the eigen-decay and the features. One can optimally choose the integer k ∈ N to achieve a tight upper bound, as we will demonstrate later in this paper. Surprisingly, the Master inequalities alone are sufficient to establish tight bounds for most cases under various settings.In this section, we 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 a + 2 ̸ = 2r.A brief summary of the propositions can be found in Table 3 . 3 : Brief summary of propositions derived in Section D used for proving the upper bounds on Table 1 .Proposition D.1 (Asymptotic upper bound of the bias term with polynomial decay). Suppose:λ k = Θ k k -1-a , |θ * k | = O k (k -r ) and λ = Θ k k -bfor some a, b, r > 0. Furthermore, suppose Assumption (GF) (or resp. (IF)) holds, and δ, ξ, ζ = Θ n,k (1) with probability at least 1 -φ. Then, for any t ∈ (0, 1], with probability at least 1 -δ -φ (or resp. 1 -δ -φ -e -n ), the bias is bounded by: B = Õn ρ 3 n -C for some constantEQUATION) with with following lower bound:EQUATION)Proof. For simplicity, we only prove the statement for all a, r except when a + 2 = 2r. In such case, the argument follows similarly with O (•) replaced by Õ (•).For any k, n ∈ N, pick k = Θn,k (n t ) for some t ∈ (0, 1]. Suppose the event δ, ξ, ζ = Θ n,k (1) happens, then:B = O n,k 1 + ρ 2 ζ 2 ξ -1 + ρ δ ∥θ * >k ∥ 2 Σ >k + (ρ 2 ζ 2 ξ -2 + ρ 3 ζ 2 ξ -1 ) n -b + c 2 Tr[Σ >k ] n 2 θ * ≤k 2 Σ -1 ≤k (34) = O n,k ρ 3 k -(2r+a) + n -b + k -a n 2 k (2+a-2r)+ (35) = O n,k ρ 3 n -t(2r+a) + n -b + n -(1+at) 2 n t(2+a-2r)+ (36) = O n,k ρ 3 n -t(2r+a) + n -2 min{b,1+ta} n t(2+a-2r)+ = O n,k ρ 3 n -t(2r+a) + n -2 min{b,1+ta}+t(2+a-2r)+ = O n,k ρ 3 n -min{t(2r+a),2 min{b,1+ta}-t(2+a-2r)+}where we apply Proposition C.6, Lemma G.8 in line (34) ; we apply Lemma H.10:θ * ≤k 2 Σ -1 ≤k = Θ k k (2+a-2r)+ where x + def.= max{x, 0}, as well as plug in Tr[Σ >k ] = Θ k (k -a ) in line (35) ; we plug in k = Θn,k (n t ) for some t ∈ (0, 1] in line (36) . = min{t(2r + a), 2 min{b, 1 + ta} -t(2 + a -2r) + } ≥ 0 is a constant defined in nested minima and maxima. To bound C from below, we make two case distinctions: b < 1 + ta or b ≥ 1 + ta.For b < 1 + ta, we haveC = min{t(2r + a), 2b -t(2 + a -2r) + } = min{t(2r + a), 2b -t(2 + a -2r)} , 2 + a ≥ 2r min{t(2r + a), 2b} , 2 + a < 2r =    min{t(2r + a), t(2r + a) + 2( ≥0 1 -t) -2(ta + 1 -b)} , 2 + a ≥ 2r min{t(2r + a), 2b} , 2 + a < 2r ≥    min{t(2r + a), t(2r + a) -2( ≥0 ta + 1 -b)} , 2 + a ≥ 2r min{t(2 + a + a), 2b} , 2 + a < 2r = t(2r + a) -2(ta + 1 -b) , 2 + a ≥ 2r 2 min{ta + t, b} , 2 + a < 2r ≥ t(2r + a) -2(ta + 1 -b) , 2 + a ≥ 2r 2 min{b -1 + t, b} , 2 + a < 2r = t(2r + a) -2(ta + 1 -b) , 2 + a ≥ 2r 2(b -1 + t) , 2 + a < 2r ≥ min{t(2r + a) -2(ta + 1 -b), 2(b -1 + t)}.For b ≥ 1 + ta, we haveC = min{t(2r + a), 2(1 + ta) -t(2 + a -2r) + } = min{t(2r + a), 2(1 + ta) -t(2 + a -2r)} , 2 + a ≥ 2r min{t(2r + a), 2(1 + ta)} , 2 + a < 2r ≥ min{t(2r + a), t(2r + a) + 2(1 -t)} , 2 + a ≥ 2r min{t(2 + a + a), 2(1 + ta)} , 2 + a < 2r = t(2r + a) , 2 + a ≥ 2r min{2(t + ta), 2(1 + ta)} , 2 + a < 2r = t(2r + a) , 2 + a ≥ 2r 2(t + ta) , 2 + a < 2r ≥ min{t(2r + a), 2t(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:λ k = Θ k k -1-a , |θ * k | = O k (k -r ) and λ = Θ k k -bfor some a, r > 0 and b ∈ (0, 1 + a]. Fix a constant δ ∈ (0, 1). If, additionally, Assumption (GF) (or resp. (IF)) holds, then, with probability at least 1 -δ -o n -1 (or resp. 1 -δ -3e -c1n ), the bias is bounded by:B = Õn n -min{sb,2b}with s def.1+a .Proof. Use Proposition D.1 as the backbone, and use Propositions G.1 and G.2 to obtain the high probability guarantee for ξ, ζ = Θ n,k (1) . Then for different value of b, we plug different values of t ∈ (0, 1] and set k = Θ n,k (n t ), such that ρ = ρ n,k = Õn,k (1) by Proposition G.3, in order to obtain different decay rates of bias.Assume b ∈ [0, a + 1). Pick k = Θ k,n (n t ) with t = b 1+a . As above, it holds that ρ = Θn,k (1) with high probability. This time, we plug in t = b 1+a in the definition of C. By the choice of b, we have b < 1 + ta and henceC def. = min{t(2r + a), 2 min{b, 1 + ta} -t(2 + a -2r) + } = min {t(2r + a), 2b -t(2 + a -2r) + } = min{t(2r + a), 2b -t(2 + a -2r)} , 2 + a ≥ 2r min{t(2r + a), 2b} , 2 + a < 2r =    min{t(2r + a), t(2r + a) + 2( ≥0 b -t(1 + a))} , 2 + a ≥ 2r min{t(2r + a), 2b} , 2 + a < 2r ≥ min{t(2r + a), t(2r + a)} , 2 + a ≥ 2r min{t(2r + a), 2b} , 2 + a < 2r ≥ min{t(2r + a), 2b}.Finally, assume b = a + 1. Pick k = Θ k,n (n t ) with t = b 1+a = 1. But this time, since b ≥ 1 + ta, we plug in t = b 1+a = 1 into the second lower bound of C in line (33) :EQUATIONThe argument for exponential decay follows analogously as above. Recall Assumption (EE): λ k = Θ k e -ak for some a > 0. Suppose |θ * k | = Θ k e -rk and λ = Θ n 1 n e -bn12 for some b, r > 0. Then the asymptotic bounds follows similarly to the polynomial case. For sake of completeness, in this section, we list out some propositions for illustration. Proposition D.3 (Asymptotic upper bound of bias under strong ridge and exponential eigen-decay). Suppose λ k = Θ k e -ak , |θ * k | = Θ k e -rk and λ = Θ n e -bn for some a, r > 0 and b ∈ (0, a). If Assumption (GF) (or resp. (IF)) holds, then with probability at least 1 -δ -o n 1 n (or resp. 1 -δ -3e -c1n ), the bias is bounded by:EQUATIONfor some constants c 1 > 0, where s = 2r a + 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 asymptotically: by taking a slightly smaller b < b, the decay is exponential in bn.Proof. By Proposition C.6, with probability at least 1 -δ (or resp. 1 -δ -e -n ), the bias is bounded by:EQUATIONBy Proposition G.1 and G.2, there exists some c > 1 such that, ifcβ k k log k ≤ n (or resp. k/c ≤ n),then with probability at least 1 -2 exp -cβ k n k (or resp. 1 -2 exp (-c 1 n)), it holds that ξ k,n ≥ 1 2 ; ζ k,n ≤ c 2 .Fix a δ ∈ (0, 1). With probability at least1 -δ -2 exp -c β k n k (or resp. 1 -δ -e -n -2e -c1n), it holds that:B = O n,k ρ ∥θ * >k ∥ 2 Σ >k + s 1 (A k ) n 2 θ * ≤k 2 Σ -1 ≤k = O n,k ρ k -(2r+a) + n -2 e -bn 2 θ * ≤k 2 Σ -1 ≤k .where the last inequality comes from Proposition G.4. For b < a, set t = 2r+a a be the source coefficient and we write:B = O n,k e -b a (2r+a)n + e -bn 2 k l=1 e (a-2r)l = O n,k   e -sbn + e -2bn b a n l=1 e (a-2r)l   =      O n,k e -sbn + e -2bn • e (a-2r) b a n , a > 2r O n,k e -sbn + e -2bn • b a n , a = 2r O n,k e -sbn + e -2bn , a < 2r =    O n,k e -sbn + e -sbn , a > 2r O n,k e -sbn + ne -2bn , a = 2r O n,k e -sbn + e -2bn , a < 2r = O n,k e -min{s,2}bn , a ̸ = 2r O n,k e -sbn + ne -2bn, a = 2r.Proposition D.5 (Asymptotic upper bound of bias under weak/effectively no ridge for s > 1). Suppose Assumption (GF) (or resp. (IF)) holds, and the source coefficient s > 1. Then with high probability, the bias has decay:B = Õn λ min{s,2} n , for λ = Ω n (λ n ) .Proof. By definition, rewrite the bias into:EQUATION) Denote P λ def. = X ⊤ (XX ⊤ + nλI n ) -1 X ∈ R p×p . By Sherman-Morrison-Woodbury formula, I p -P λ = I p -(nλ) -1 X ⊤ I n + (nλ) -1 XX ⊤ -1 X = λ λI p + 1 n X ⊤ X -1 = λ λI p + Σ -1is a positive definite matrix such that the matrix I p -P λ is monotonic increasing in λ, that is:EQUATIONfor all λ ≥ λ > 0, since the map λ → λ λ+x is monotone. Hence, for t ∈ [1, min{2, s}) 13 ,EQUATIONEQUATIONEQUATIONEQUATIONEQUATIONwhere we rewrite line (40) in line (42) ; we apply the monotonicity from line (41) in line (43) ; we use the fact that (44) ; we use Lemma H.17 to pull out the power (t -1) from the matrix to its operator norm in line (45) ; we use the fact that∥M 1 M 2 ∥ op = ∥M 2 M 1 ∥ op for symmetric matrices M 1 , M 2 in lineM 1/2 1 M 1/2 2 2 op = M 1/2 1 M 1/2 2 (M 1/2 1 M 1/2 2 ) ⊤ op = M 1/2 1 M 2 M 1/2 1 opfor any positive definite symmetric matrices 14 M 1 , M 2 in line (46) ; by the monotonicity from line (41) again and the fact that Σ 1/2 is positive definite, we choose λ ≥ λ ≽ λ n to be strong in the sense of polynomial/exponential eigen-decay in line (47): λ = Θ n n -1-a for polynomial case and λ = Θ n (e -an ) for exponential case.Let v ∈ S p-1 ⊂ R p be a unit vector such thatΣ 1/2 (I p -P λ)Σ 1/2 2 op = Σ 1/2 (I p -P λ)Σ 1/2 v 2 2. By definition, we haveΣ 1/2 v 2 Σ -1 = ∥v∥ 2 2 = 1 < ∞,hence the vector Σ 1/2 v lies on the interpolation space H 2 . Note that the expressionΣ 1/2 (I p -P λ)Σ 1/2 2 op = Σ 1/2 (I p -P λ)Σ 1/2 v 2 2 = (I p -P λ) Σ 1/2 v 2 Σis just the bias term of another task Σ 1/2 v with source coefficient 2 and ridge λ = Ω n (λ n ) on the same dataset X. Apply Proposition D.2 with polynomial decay and Proposition D.3 with exponential decay on that new task with strong ridge λ, with high probability, the above term has a decay rate: 13 Recall that s def.EQUATION), Assumption (PE) holds 2r a + 1 , Assumption (EE) holds is the source coefficient. 14 Same as above.Suppose Assumption (IF) holds, choose k = ⌊n/c⌋ for some constant c > 1 as in Propositions G. 3 . with probability at least 1 -3e -c1n , it holds that ξ, ζ, ρ = Θ n,k (1) .Then by Proposition C.7, we have 1 -3e -c1n ), the variance term is bounded:EQUATIONV = O n n b a -1 for n ∈ N 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 ξ, ζ = Θ n,k (1) , by Lemma H.12,V/σ 2 ≤ ρ 2 ζ 2 ξ -1 k n + Tr[Z >k Σ 2 >k Z ⊤ >k ] n Tr[Σ 2 >k ] r k (Σ) 2 nR k (Σ) = O n,k ρ 2 k n + 1 n 2 = O n,k ρ 2 k n .Choose k = ⌊ b a ⌋ < 1. Combine Proposition G.4 and the above inequality to obtain the result.Proposition E.3 (Asymptotic lower bound of bias with polynomial decay and independent features). Suppose Assumption (PS) holds andλ k = Θ k k -1-a , E θ * (θ * k ) 2 = O k k -2rand λ = Θ n n -b for some a, b, r > 0. Fix a constant δ ∈ (0, 1). If, additionally, Assumption (IF) holds, then, with probability at least 1 -δ -11e -c1n , the bias is bounded by:E θ * [B] = Ωn n -b min{s,2}for s def.1+a .Proof. By Lemma H.14, it holds that:E θ * [B] ≥ p l=1 λ l E θ * (θ * l ) 2 1 + λ l s n (A -l ) -1 z (l) 2 2 2 .Hence, we want to bound the term s n (A -l ) -1 and z (l) 2 2 from above. If Assumption (IF) holds, then apply Lemma G.7 on A -l instead of A, l = 1, ..., p, with probability at least 1 -2e -n ,s n (A -l ) = Ω n (nλ n ) , if l > n Ω n (nλ n+1 ) , if l ≤ n = Ω n (nλ n ) = Ω n (Tr[Σ >n ]) .By Lemma H.7, with probability at least 1 -2e -n , we have,∥z l ∥ 2 2≤ c 1 n, ∀l = 1, ..., p. Plug in the above two inequalities, by union bound, with probability at least 1 -4e -n , λ l E (θ * l ) 2 (1 + λ l s n (A -l ) -1 ∥z l ∥ 2 2 ) 2 = Ω n    λ l E (θ * l ) 2 1 + nλ lλ l E (θ * l ) 2 (1 + λ l s n (A -l ) -1 ∥z l ∥ 2 2 ) 2 = Ω n    λ l E (θ * l ) 2 1 + nλ l λ k+1 r k 2   By Lemma H.15, with probability at least 1 -8e -n ,E θ * [B] = Ω n         p l=1 λ l E (θ * l ) 2 1 + nλ l λ k+1 r k 2 B        , where B is defined as in Theorem H. 16 . sinceEQUATION) and r k satisfies the condition of Theorem H. 16 . By Theorem H.16, we have upper bound B matching the lower bound B:B = Θ n      ∥θ * >k ∥ 2 Σ >k + nλ + Tr[Σ >k ] n 2 θ * ≤k 2 Σ -1 ≤k B     .By Propositions C.6, D.2 and D.6, we have, with probability at least 1 -δ -3e c1n ,B = O n B = O n n -b min{s,2} .All together, with probability at least 1 -δ -3e -c1n -8e -n ,E θ * [B] = Ω n B = Ω n n -b min{s,2} .Proposition E.4 (Asymptotic lower bound of bias with exponential decay and independent features under strong ridge). Suppose Assumption (PS) holds andλ k = Θ k e -ak , E θ * (θ * k ) 2 =O k e -2rk and λ = Θ n e -bn for some a, r > 0 and b ∈ (0, a). Fix a constant δ ∈ (0, 1). If, additionally, Assumption (IF) holds, then, with probability at least 1 -δ -7e -c1n , the bias is bounded by:E θ * [B] = Ωn e -bn min{s,2}for s def.a + 1.Proof. The proof is similar to Proposition E.3. By Lemma H.14, it holds that:E θ * [B] ≥ p l=1 λ l E θ * (θ * l ) 2 1 + λ l s n (A -l ) -1 z (l) 2 2 .By Lemma H.7, with probability at least 1 -2e -n , we have,∥z l ∥ 2 2 ≤ c 1 n, ∀l = 1, ..., p.By the choice of b ∈ (0, a):s n (A -l ) = Ω n (nλ) = Ω n ne -bn = Ω n (nλ n+1 ) .Plug in the above two inequalities, with probability at least 1 -2e -n , (1) . By Lemma H.15, with probability at least 1 -4e -n ,λ l E (θ * l ) 2 (1 + λ l s n (A -l ) -1 ∥z l ∥ 2 2 ) 2 = Ω n    λ l E (θ * l ) 2 1 + λ l λn+1 2    = Ω n    λ l E (θ * l ) 2 1 + nλ l λn+1rn 2    where r k = Tr[Σ >k ] ∥Σ >k ∥ op = Θ kE θ * [B] = Ω n         p l=1 λ l E (θ * l ) 2 1 + nλ l λ k+1 r k 2 B        , where B is defined as in Theorem H. 16 . sincer k = Tr[Σ >k ] ∥Σ >k ∥ op = Θ k (1), pick k such that r k > 1.This satisfies the condition of Theorem H. 16 . By Theorem H.16, we have upper bound B matching the lower bound B:B = Θ n      ∥θ * >k ∥ 2 Σ >k + nλ + Tr[Σ >k ] n 2 θ * ≤k 2 Σ -1 ≤k B     .For the under-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 can even prove an asymptotic convergence in the following way.we first prove the convergence of the empirical covariance matrix.Lemma F.1 (Convergence of Σ). Suppose Assumption (GF) (or resp. (IF)) holds. Fix an ϵ ∈ (0, 1).Then there exists a constant c > 1 such that, for p < n 1-ϵ c log n (or resp. p < n 1-ϵ /c), with probability at least 1 -o n (n -ϵ ), it holds thatI p - 1 n Z ⊤ Z op = Σ -Σ op = o n,p n -ϵ/2 ,whereΣ def. = E xx ⊤ ∈ R p×p and Σ def. = 1 n n i=1 x i x ⊤ i ∈ R p×p .Proof. We argue similarly as in Proposition G.2. Fix an ϵ ∈ (0, 1).Suppose Assumption (GF) holds. We have ∥z∥ 2 2 ≤ β p p by definition of β k . Apply Theorem H.3 on the whitened input block Z ∈ Rn × p: there exists some constant c 1 > 0 such that, with probability at least 1 -2pe -c1t 2 , we have:√ n -t β p p ≤ s p (Z) ≤ s 1 (Z) ≤ √ n + t β p p.By setting t = log n c1 and the choice of p < n 1-ϵ c log n , with probability at least 1 -2 cn ϵ log n , we have √ n 1 - β p 2c 1 n -ϵ ≤ s p (Z) ≤ s 1 (Z) ≤ √ n 1 + β p 2c 1 n -ϵ .Hence, for n large enough, with probability at least 1 -2 cn ϵ log n , it holds that:I p - 1 n Z ⊤ Z op ≤ 2β p 2c 1 n -ϵ = o n n -ϵ/2 .and hence:Σ -Σ op ≤ Σ 1/2 op I p - 1 n Z ⊤ Z op Σ 1/2 op ≤ Σ 1/2 op • 2β p 2c 1 n -ϵ • Σ 1/2 op = λ 1 β p c 1 n -ϵ = o n n -ϵ/2 .Suppose Assumption (GF) holds. By Lemma H.7 and union bound, we have ∥z i ∥ 2 2 ≤ 2p for all i = 1, ..., n with probability 1 -2ne -c1n . When this event happens, apply Theorem H.3 on the whitened input block Z ∈ R n×p , the rest of the argument follows similarly.Proposition F.2 (Convergence of the bias and variance terms). Suppose Assumption (GF) (or resp. (IF)) holds. Then there exists an ϵ ∈ (0, 1) and a constant c > 1 such that, for p < n 1-ϵ c log n (or resp. p < n 1-ϵ /c), with probability at least 1 -o n (n -ϵ ), it holds thatB = Θ n,p λ 2 p k=1 λ k (θ * k ) 2 (λ k + λ) 2 , V = Θ n,p σ 2 n p k=1 λ 2 k (λ k + λ) 2 .Proof. We begin with B. By line (40) and the formulaM -1 1 -M -1 2 = M -1 1 (M 1 -M 2 )M -12 , rewrite the bias term B as:B = ∥(I p -P λ )θ * ∥ 2 Σ = λ(λI p + Σ) -1 θ * 2 Σ = λ (λI p + Σ) -1 + (λI p + Σ) -1 ( Σ -Σ)(λI p + Σ) -1 θ * 2 Σ . Denote ∆ = ( Σ -Σ)(λI p + Σ) -1 . Note that ∥∆∥ op = Σ 1/2 1 n Z ⊤ Z -I p Σ 1/2 Σ -1/2 (λΣ -1 + I p ) -1 Σ -1/2 op ≤ 1 n Z ⊤ Z -I p op • (λΣ -1 + I p ) -1 op • Σ 1/2 Σ 1/2 Σ -1/2 Σ -1/2 op = o n n -ϵ/2 .We apply the matrix difference formula iteratively:( Σ + λI p ) -1 = (Σ + λI p ) -1 + ( Σ + λI p ) -1 ( Σ -Σ)(Σ + λI p ) -1 = (Σ + λI p ) -1 + ( Σ + λI p ) -1 ∆ = (Σ + λI p ) -1 + (Σ + λI p ) -1 + ( Σ + λI p ) -1 ∆ ∆ = ... = (Σ + λI p ) -1 ∞ t=0 ∆ t ,we write:B = λ( Σ + λI p ) -1 θ * 2 Σ = λ (λI p + Σ) -1 + (λI p + Σ) -1 ( Σ -Σ)(λI p + Σ) -1 θ * 2 Σ = λ(λI p + Σ) -1 θ * + λ( Σ + λI p ) -1 ∆θ * 2 Σ = λ(λI p + Σ) -1 ∞ t=0 ∆ t θ * 2 Σ = Θ n,p λ(λI p + Σ) -1 θ * 2 Σ .Finally, writeλ(λI p + Σ) -1 θ * 2 Σ = λ 2 p k=1 λ k (θ * k ) 2 (λ k + λ) 2 .Now we argue similarly for V. By Lemma H.19:V = σ 2 n E x∼µ Σ + λI p -1 x 2 Σ = σ 2 n E x∼µ   (Σ + λI p ) -1 ∞ t=0 ∆ t x 2 Σ  = σ 2 n E x   x ⊤ ∞ t=0 ∆ t ⊤ (Σ + λI p ) -1 Σ(Σ + λI p ) -1 ∞ t=0 ∆ t x   = σ 2 n E x   x ⊤ ∞ t=0 ∆ t ⊤ (Σ + λI p ) -1 ∆ + Σ(Σ + λI p ) -1 ∞ t=0 ∆ t x   = σ 2 n Tr[Σ 2 (Σ + λI p ) -2 ] 1 + O n ∥∆∥ op .We argue similarly as in Proposition F.2: with probability at least 1 -o n (n -ϵ ), we haveV = Θ n,p σ 2 n p k=1 λ 2 k (λ k + λ) 2 .Plugging in the values of n, p and other metrics a, b, r in Proposition F.2, we can obtain theIn the following, we shall give sufficient conditions to control the concentration coefficients ζ n,k , ξ n,k and ρ n,k . Note that ρ n,k , and ξ n,k depends on the whitened/isotropic features z but not on the spectrum Σ. We start from the easiest to the most difficult. 1 -2 exp (-c 1 kn)), it holds thatξ n,k ≥ 1 2 .Proof. Since the largest singular value is larger than the average of the singular values,ξ n,k def. = s 1 (Z ⊤ ≤k Z ≤k ) n ≥ 1 k Tr[Z ⊤ ≤k Z ≤k ] n = Tr[Z ⊤ ≤k Z ≤k ] kn .By Lemma G.5, with respective probability,ξ n,k ≥ 1 2 . Proposition G.2 (Control on ζ n,k ). Let k ≤ n be an integer. Recall that ζ n,k def. = s1(Z ⊤ ≤k Z ≤k ) sn(Z ⊤ ≤k Z ≤k ) . If Assumption (GF) (or resp. (IF)) holds, then there exists some c > 1 such that, if cβ k k log k ≤ n (or resp. k/c ≤ n), then with probability at least 1 -2 exp -c β k n k (or resp. 1 -2 exp (-c 1 n)), it holds that ζ n,k ≤ c 2 .Proof. For the case where Assumption (GF) holds, see Lemma 2 in [7] . Suppose Assumption (IF) holds, then by Theorem H.2, there exists constants C 1 , C 2 > 0, such that, with probability at least 1 -2 exp -C 1 t 2 , the spectrum of random matrix Z ≤k ∈ R n×k is bounded:√ n -C 2 k -t ≤ s k (Z ≤k ) ≤ s 1 (Z ≤k ) ≤ √ n + C 2 k + t.Set t = √ n/4 and c = 1 16C2 so that if k/c ≤ n, the bound becomes: Proof. The statement where Assumption (GF) holds is proved in Theorems 4 and 5 in [7] . The statement where Assumption (IF) holds can be proved proved via Lemma G.7: since: 1 4 √ n ≤ s k (Z ≤k ) ≤ s 1 (Z ≤k ) ≤ 3 2 √ n, and hence ζ n,k ≤ ( 3 2 √ n)/( 1 4 √ n) = 6 with a probability at least 1 -2 exp -C1 16 n . Set c 1 = C1ρ = n ∥Σ >k ∥ op + s 1 (A k ) s n (A k ) = O k,n nλ k + nλ nλ n+k + nλ = O k,n nλ k nλ n+k = O k,n k -1-a (n + k) -1-a = O k,n (1 + n/k) 1+a = O k,n (1 + c) 1+a = O k,n (1) .-exp (-n)), it holds that s 1 (A k ) = O n ne -bn , ρ n,k = O n (1) .Proof. For the case where Assumption (GF) holds, by Corollary 1 in [7] , with probability at least1 -o n 1 n , it holds that s 1 (A k ) = O n,k n λ k+1 + log k Tr[Σ >k ] n + λ = O n,k n e -ak + e -bn = O n,k n e -a• b a n + e -bn = O n ne -bn .For the case where Assumption (IF) holds, the upper bound of s 1 (A k ) is proven in Lemma G.7. In both cases, the derivation of bounding ρ is the same:EQUATION.Lemma G.5 (Lemma 1 in [7] ). Let k be an integer. Suppose Assumption (GF) (or resp. (IF)) holds.Then with probability at least 1 -2 exp -1 2β k n (or. resp. 1 -2 exp (-c 1 kn)), it holds that1 2 kn ≤ Tr[Z ⊤ ≤k Z ≤k ] ≤ 3 2 kn.Proof. If Assumption (GF) holds, thenTr[Z ⊤ ≤k Z ≤k ] = Tr[Z ≤k Z ⊤ ≤k ] = n i=1 ∥(z i ) ≤k ∥ 2 2 ≤ β k kn.Set M = β k k and by Hoeffding's inequality, the above trace concentrates:P Tr[Z ≤k Z ⊤ ≤k ] -kn ≥ t ≤ 2 exp - 2t 2 nM 2Set t = nk/2 to conclude the statement. Analogously, if Assumption (IF) holds, for i = 1, ..., n and l = 1, ..., k, (z(l) i ) 2 -1 is centered sub-exponential variable with sub-exponential norm (z (l) i ) 2 -1 ψ1 ≲ G 2 . By Lemma H.7, with probability at least 1 -2 exp (-c 1 kn), Tr[Z ⊤ ≤k Z ≤k ] -kn = n i=1 k l=1 (z (l) i ) 2 -kn ≤ 1 2 kn.Lemma G.6 (Lemma 3 in [7] ). For any k ≤ n and δ ∈ (0, 1), with probability at least 1 -δ, it holds that1 n ∥X >k θ * >k ∥ 2 2 ≤ 1 δ ∥θ * >k ∥ 2 Σ >k . Proof. Since E 1 n X >k θ * >k 2 2 = θ * >k 2 Σ >k, we use Markov's inequality to obtain the result.Lemma G.7. Suppose Assumption (IF) hold. Then for any integer k ≤ n,1. If Assumption (PE)/(EE) holds, then with probability at least 1 -e -n , it holds that s1 (A k ) = O n,k (nλ k + nλ) .2. If Assumption (PE) holds, then with probability at least 1 -2e -n , it holds thats n (A k ) = Ω n,k (nλ n+k + nλ) ,for p large enough.Proof. First we prove statement 1. For any k ∈ N,r k def. = Tr[Σ >k ] ∥Σ >k ∥ op =        Θ k p l=k+1 l -1-a (k+1) -1-a Θ k p l=k+1 e -al e -ak =    Θ k k -a k -1-a Θ k e -ak e -ak = Θ k (k) Assumption (PE) holds Θ k (1) Assumption (EE) holds .Hence, set t = n in Theorem H.5, with probability at least 1 -e -n , it holds that1 n X ⊤ >k X >k -Σ >k op = O n,k ∥Σ >k ∥ op max r k n , r k n , t n , t n = O n,k (λ k ) By triangle inequality, X ⊤ >k X >k op ≤ n 1 n X ⊤ >k X >k -Σ >k op + n ∥Σ >k ∥ op = O n,k (nλ k ).Hence, with the same probability,s 1 (A k ) = s 1 (X >k X ⊤ >k + nλI n ) = s 1 (X ⊤ >k X >k ) + nλ = O n,k (nλ k + nλ) .Now we prove statement 2. Note that the smallest singular value of a matrix does not increase after discarding a column: for some constant η > 1 to be determined, it holds thats n (X >k X ⊤ >k ) = s n (Z >k Σ 1/2 >k ) 2 ≥ s n (Z k:ηn Σ 1/2 k:ηn ) 2 ≥ λ ηn s n (Z k:ηn ) 2. By Assumption (IF), the columns of Z k:ηn are independent to each other. By Theorem H.2, with probability at least 1 -2e -c1t 2 , it holds that s min (Z k:ηn ) = s min{n,ηn-k} (Zk:ηn ) ≥ √ ηn - √ c 2 n -t. Choose t = n/c 1 and η > 2 + 1 c1 + c 2 2(given that p > ηn large enough), then with probability at least 1 -2e -n , it holds that s n (Z k:ηn ) = s min (Z k:ηn ) ≥ √ n.Hence with the same probability, by Assumption (PE),s n (A k ) = s n (X >k X ⊤ >k + nλI n ) ≥ nλ ηn + nλ = Ω n,k (nλ n + nλ) .Lemma G.8 (Theorem 2 in [7] ). Suppose Assumption (GF) (or resp. (IF)) holds, then with probability at least 1 (or resp. 1 -2pe -c1n ), it holds thats 1 (A k ) 2 n 2 ≤ ρ 2 n,k λ + c 2 Tr[Σ >k ] n 2 .Suppose Assumptions (IF) holds. Furthermore, if Assumptions (PE) or (EE) holds, then one obtains a probability bound which allows arbitrary large p: with probability at least 1 -e -n , it holds thats 1 (A k ) 2 n 2 ≤ c 1 λ + Tr[Σ >k ] n 2 .Proof. Since the trace of a matrix is the sum of its eigenvalues, we obtain:s 1 (A k ) 2 n 2 = s 1 (A k ) 2 s n (A k ) 2 s n (A k ) 2 n 2 ≤ ρ 2 n,k 1 n Tr 1 n A k 2 ≤ ρ 2 n,k 1 n Tr [λI n ] + Tr 1 n n i=1 (x i ) >k (x i ) ⊤ >k 2 ≤ ρ 2 n,k 1 n nλ + 1 n n i=1 ∥(x i ) >k ∥ 2 2 2By Assumption (GF), since ess sup x∥x >k ∥ 2 2 Tr[Σ >k ] ≤ β k , we have s 1 (A k ) 2 n 2 ≤ ρ 2 n,k 1 n nλ + sup x ∥x >k ∥ 2 2 2 ≤ ρ 2 n,k λ + β k Tr[Σ >k ] n 2 .If Assumption (IF) holds, then for each l > k, the random variable (z (l) ) 2 -1 is centered subexponential, hence with probability at least 1 -2 exp (-c 1 n), it holds thatEQUATIONBy union bound, with probability at least 1 -2(p -k) exp (-c 1 n), it holds thatEQUATIONIf Assumptions (IF) and (PE)/(EE) hold, then by Lemma G.7: with probability at least 1 -e -n , it holds thats 1 (A k ) = O n,k (nλ n + nλ)for any k ∈ N. Hence with the same probability,s 1 (A k ) 2 n 2 = O n nλ + nλ n n 2 = O n λ + Tr[Σ k ] n 2 .where C 7 > 0 is an absolute constant.In particular, if X ∼ χ(N ) is the Chi-square distribution, then P | X N -1| > t ≤ 2e -N t 2 /8 , ∀t ∈ (0, 1). Lemma H.8 (Lemma 28 in [46] ; Lemma 14 in [7] ). Suppose that for some k < N , the matrix A k is positive definite, then the following inequality holds:EQUATIONLemma H.9 (Lemma 27 in [46] ; Lemma 13 in [7] ). For any k ∈ N, we haveV/σ 2 ≤ s 1 (A -1 k ) 2 Tr[X ≤k Σ -1 ≤k X ⊤ ≤k ] s n (A -1 k ) 2 s k (Σ -1/2 ≤k X ⊤ ≤k X ≤k Σ -1/2 ≤k ) 2 + s 1 (A -1 k ) 2 Tr[X >k Σ >k X ⊤ >k ], where σ 2 def. = E ϵ 2 ≥ 0.Lemma H.10 (Lemma 18 in [7] ). Assumeλ k = Θ k k -1-a and |θ * k | = O k (k -r) for some a, r > 0. Then the square norms θ * Lemma H.12. Recall thatr k def. = Tr[Σ >k ] ∥Σ >k ∥ op , R k def. = Tr[Σ >k ] 2 Tr[Σ 2 >k ].If λ k = Θ k k -1-a for some a > 0, thenr k = Θ k (k) , R k = Θ k (k) .If λ k = Θ k e -ak for some a > 0, thenr k = Θ k (1) , R k = Θ k (1) .Proof. By simple calculus,p l=k+1 k -1-a = Θ k ∞ k t -1-a dt = Θ k (t -a ), similarly, p l=k+1 k -2-2a = Θ k ∞ k t -2-2a dt = Θ k t -1-2a . If λ k = Θ k k -1-afor some a > 0, then Lemma H.13 (Lemma 7 in [46] ). Suppose Assumption (IF) holds. Then there exists some constant c > 0 such that, for any k < n/c, with probability at least 1 -ce -n/c , its holds that V ≥ 1 cn l=1 min 1, λ 2 l λ 2 k+1 (1 + r k /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:r k = Θ k k -a λ k+1 = Θ k (k) , R k = Θ k k -2a k -1-2a = Θ k (k) .EQUATION)where the expectation is taken as described in Assumption (PS), and A -l def.= l ′ ̸ =l λ l ′ z (l ′ ) (z (l ′ ) ) ⊤ + nλI n ∈ R n×n where z (l) ∈ R n denotes the l-th column of the whitened feature block Z def.= XΣ -1/2 .Proof. By Assumption (PS), the expected value over θ * on the bias admits the following expression as in line ( 40): where P λ def.= X ⊤ (XX ⊤ + nλI p ) -1 X. Denote z (l) ∈ R n be the l-th column of the whitened feature block Z def.= XΣ -1/2 ∈ R n×p . Then the l-th diagonal element of the matrix (I p -P λ )Σ(I p -P λ ) can be written as = A -λ l z (l) (z (l) ) ⊤ , by Sherman-Morrison-Woodbury formula, we have 1 -λ l (z (l) ) ⊤ A -1 z (l) = 1 1 + λ l (z (l) ) ⊤ A -1 -l z (l) , and hence the averaged bias is bounded by:E θ * [B] ≥ p l=1 λ l E θ * (θ * l ) 2 (1 + λ l (z (l) ) ⊤ A -1 -l z (l) ) 2 ≥ p l=1 λ l E θ * (θ * l ) 2 1 + λ l s 1 (A -1 -l ) z (l) 2 2 2 = p l=1 λ l E θ * (θ * l ) 2 1 + λ l s n (A -l ) -1 z (l) 2 2 2 .Lemma H.15 (Lemma 9 in [6] ). Suppose that {X k } p k=1 is a sequence of non-negative random variables, and that {t k } p k=1 is sequence of non-negative real numbers (with at least one of which strictly positive), such that for some δ ∈ (0, 1), with a probability at least 1 -δ, η k > t k for all k = 1, ..., p. Theb with probability at least 1 -2δ, Lemma H.17 (Corde's inequality, [18] ). For any positive definite symmetric matrices 16 whereΣ def. = 1 n X ⊤ X.Proof. By definition, rewrite the bias into:EQUATIONDenote P λ def.= X ⊤ (XX ⊤ + nλI n ) -1 X ∈ R p×p . By Sherman-Morrison-Woodbury formula,I p -P λ = I p -(nλ) -1 X ⊤ I n + (nλ) -1 XX ⊤ -1 X = λ λI p + 1 n X ⊤ X -1= λ λI p + Σ . 16 Or equivalently positive definite self-adjoint operator in a Hilbert space.Proof. By definition,V = E ϵ θ(ϵ) 2 Σ = E ϵ ϵ ⊤ (XX ⊤ + nλI n ) -1 XΣX ⊤ (XX ⊤ + nλI n ) -1 ϵ = E ϵ Tr[(XX ⊤ + nλI n ) -1 XΣX ⊤ (XX ⊤ + nλI n ) -1 ϵϵ ⊤ ] = Tr[(XX ⊤ + nλI n ) -1 XΣX ⊤ (XX ⊤ + nλI n ) -1 E ϵ ϵϵ ⊤ ] = σ 2 Tr[(XX ⊤ + nλI n ) -1 XΣX ⊤ (XX ⊤ + nλI n ) -1 ] = σ 2 Tr[X(X ⊤ X + nλI p ) -1 Σ(X ⊤ X + nλI p ) -1 X ⊤ ] = σ 2 n Tr 1 n X ⊤ X + λI p -1 Σ 1 n X ⊤ X + λI p -1 1 n X ⊤ X = σ 2 n Tr Σ + λI p -1 E x∼µ xx ⊤ Σ + λI p -1 Σ = σ 2 n E x∼µ Tr Σ + λI p -1 xx ⊤ Σ + λI p -1 Σ = σ 2 n E x∼µ x ⊤ Σ + λI p -1 Σ Σ + λI p -1 x = σ 2 n E x∼µ Σ + λI p -1 x 2 Σ.• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment 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 a 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 to 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 as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).For p = ∞, we regard x as a vector of an infinite dimensional Hilbert space and Σ as a Hilbert Schmidt operator, meaning Tr[Σ] < ∞. With abuse of notation, we write x as vector and Σ as matrix throughout the paper. In some proofs, we would apply some linear algebraic results on some R p×p matrices. When dealing with p = ∞, replace those results with their Hilbert space counterparts.For λ without subscript, we mean the ridge regularization coefficient; for λ k with subscript k, we mean the eigenvalues of the covariance Σ = E xx ⊤ .The condition a + 2 ̸ = 2r is purely technical and aims to simplify the results.Similar as above.Here we only concern the upper bound of the asymptotic learning rate for GEP. As far as we know, there is 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 Table2below.https://vectorinstitute.ai/partnerships/current-partners/Rotational invariant, and respectively anti-concentration property, are crucial in some literature using Gaussian Design Assumption, for example[44], and respectively[14].H .which minimum admits the form:f (x) = K ⊤ x (K + nλI n ) -1 y, ∀x ∈ X , where K x = (K(x, x i )) n i=1 ∈ R n , K = [K(x i , x j )] n i,j=1 ∈ R n×n and y = (y i ) n i=1 . Note that if we write ψ x = (ψ k (x)) p k=1 ∈ R p , Ψ = [ψ k (x i )] ik ∈ R n×p and Λ = diag{λ k } p k=1 ∈ R p×p, by Mercer decomposition, we have K x = ΨΛψ x , K = ΨΛΨ ⊤ . We are ready to translate our linear ridge regression to the KRR setting. See Table5for details.Meaning that, there exist constants 0 < c ≤ C such that: for each u ∈ H s (S d ) we have c∥u∥H ≤ ∥ • ∥ H s (S d ) ≤ C∥ • ∥H.See[6] for details.The extra 1 n factor serves only for simplification purpose and has no effect on the choice of b. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

Recently, there is a growing interest in studying the KRR when the output is infinite-dimensional, see e.g. 
"Towards Optimal Sobolev Norm Rates for the Vector-Valued Regularized Least-Squares Algorithm." (2024)
&"Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms." (2024)

I 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.
questions: questions: See weakness
limitations: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.
questions: questions: Does the result hold under the assumptions used in the related work, e.g., Embedding Condition?
limitations: limitations: N/A
paper_summary: paper_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.

The 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.
strength_weakness: strength_weakness: 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
questions: 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.

- 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?

- 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?

- 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].

- Can you please elaborate on Remark A.5?

[DLM] https://arxiv.org/abs/2405.15699

**Minor points**:

- 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.

- 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.

- Unpublished pre-prints in the bibliography are missing the arXiv identifiers.

- L110, define $\succeq$ in the notation section.

- L597, maybe $\psi_{k}$ and $\phi_{k}$ are switched?

- L634, "*Consider a kernel $\kappa:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$ be a kernel with [...]*"

- Eq. below L651, missing right bracket.

- 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.

- L679, precise what "$\lambda$" in $||\bar{\psi}_{i,j}||\lesssim \lambda^{(d-1)/4}$ is.
limitations: limitations: Limitations are discussed in the "Future potential work" section.
paper_summary: paper_summary: This paper conducts a comprehensive study of the learning curves of kernel ridge regression (KRR) under minimal assumptions
strength_weakness: strength_weakness: The learning curves of kernel ridge regression have been extensively studied in recent literature. e.g.,  
1. "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.", 
2. "Yicheng Li, Haobo Zhang, and Qian Lin. On the asymptotic learning curves of kernel ridge  regression under power-law decay.", and 
3.  "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."

It is really hard for me to understand the difference between the current paper with the above papers.
questions: 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. 

For 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: limitations: NONE

Comments: title: After rebuttal
comment: Thanks for addressing my comments, I've raised my score accordingly.
Thank you for your rebuttal, which address my main concerns. I maintain my score and recommendation towards acceptance.
Dear reviewer,

Thank you for your constructive feedback! We sincerely appreciate your insights and we will reframe the results to improve their clarity. Since Neurips allows for an additional content page for the camera-ready version, we will move the most important theorem statements from the appendix to the main paper. We will then refer to the summary in the table as you suggested. Thank you once again.

Best regards,
The authors
Thanks for clearing that up. It makes me feel more comfortable knowing the paper has not been written by an agent.

I apologize if my previous comments were too harsh regarding the current presentation. The results are indeed interesting. Could you please revise your statement in a more formal manner? For example, you might present it as follows: 'Theorem: Under [specific assumptions], our results can be summarized in the following table...' Then, provide a brief description of the table. The current presentation might lead to unnecessary confusion regarding your results.

I will increasing my score.
Thanks for replying. I will maintain my score.