On the Saturation Effects of Spectral Algorithms in Large Dimensions

Authors: weihao  lu
haobo  zhang
yicheng  li
qian  lin
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 06:22:07

Abstract: The saturation effects, which originally refer to the fact that kernel ridge regression (KRR) fails to achieve the information-theoretical lower bound when the regression function is over-smooth, have been observed for almost 20 years and were rigorously proved recently for kernel ridge regression and some other spectral algorithms over a fixed dimensional domain. The main focus of this paper is to explore the saturation effects for a large class of spectral algorithms (including the KRR, gradient descent, etc.) in large dimensional settings where $n \asymp d^{\gamma}$. More precisely, we first propose an improved minimax lower bound for the kernel regression problem in large dimensional settings and show that the gradient flow with early stopping strategy will result in an estimator achieving this lower bound (up to a logarithmic factor). Similar to the results in KRR, we can further determine the exact convergence rates (both upper and lower bounds) of a large class of (optimal tuned) spectral algorithms with different qualification $\tau$'s. In particular, we find that these exact rate curves (varying along $\gamma$) exhibit the periodic plateau behavior and the polynomial approximation barrier. Consequently, we can fully depict the saturation effects of the spectral algorithms and reveal a new phenomenon in large dimensional settings (i.e.,  the saturation effect occurs in large dimensional setting as long as the source condition $s>\tau$ while it occurs in fixed dimensional setting as long as $s>2\tau$).

Main paper: 
 introduction: 
 Let's assume we have n i.i.d. samples (x i , y i ) from a joint distribution supported on R d × R. The regression problem, one of the most fundamental problems in statistics, aims to find a function f based on these samples such that the excess risk,∥ f -f ⋆ ∥ 2 L 2 = E x [(f ⋆ (x) -f (x)) 2 ],is small, where f ⋆ (x) = E[Y |x] is the regression function. Many non-parametric regression methods are proposed to solve the regression problem by assuming that f ⋆ falls into certain function classes, including polynomial splines Stone (1994) , local polynomials Cleveland (1979) ; Stone (1977) , the spectral algorithms Caponnetto (2006) ; Caponnetto and De Vito (2007) ; Caponnetto and Yao (2010) , etc. Spectral algorithms, as a classical topic, have been studied since the 1990s. Early works treated certain types of spectral algorithms in their theoretical analysis (Caponnetto (2006) ; Caponnetto and De Vito (2007) ; Raskutti et al. (2014) ; Lin et al. (2020) ). These works often consider d as a fixed constant and impose the polynomial eigenvalue decay assumption under a kernel (i.e., there exist constants 0 < c ≤ C < ∞, such that the eigenvalues of the kernel satisfy cj -β ≤ λ j ≤ Cj -β , j ≥ 1 for certain β > 1 depending on the fixed d). They further assume that f ⋆ belongs to the reproducing kernel Hilbert space (RKHS) H associated with the kernel. Under the above assumptions, they then showed that the minimax rate of the excess risk of regression over the corresponding RKHS is lower bounded by n -β/(β+1) and that some (regularized) spectral algorithms, e.g., the kernel ridge regression (KRR) and the kernel gradient flow, can produce estimators achieving this minimax optimal rate. However, subsequent studies have revealed that when higher regularity (or smoothness) of f ⋆ is assumed, KRR fails to achieve the information-theoretical lower bound on the excess risk, while kernel gradient flow can do so. Specifically, let's assume that f ⋆ belongs to the interpolation space [H] s of the RKHS H with s > 0 (see, e.g., Steinwart et al. (2009) ; Dieuleveut et al. (2017) ; Dicker et al. (2017) ; Pillaud-Vivien et al. (2018) ; Lin et al. (2020) ; Fischer and Steinwart (2020) ; Celisse and Wahl (2021) ). It is then shown that the information-theoretical lower bound on the excess risk is n -sβ/(sβ+1) . When 0 < s ≤ 2, Caponnetto and De Vito (2007) ; Yao et al. (2007) ; Lin et al. (2020) ; Zhang et al. (2023) have already shown that the upper bound of the excess risks of both KRR and the kernel gradient flow is n -sβ/(sβ+1) , and hence they are minimax optimal. On the contrary, when s > 2, Yao et al. (2007) ; Lin et al. (2020) showed that the upper bound of the excess risks of kernel gradient flow is n -sβ/(sβ+1) while the best upper bound of the excess risks of KRR is n -2β/(2β+1) (Caponnetto and De Vito (2007) ). Bauer et al. (2007) ; Gerfo et al. (2008) ; Dicker et al. (2017) conjectured that the convergence rate of KRR is bounded below by n -2β/(2β+1) and Li et al. (2022) rigorously proved it. The above phenomenon is often referred to as the saturation effect of KRR:KRR is inferior to certain spectral algorithms, such as kernel gradient flow, when s > 2.In recent years, neural network methods have gained tremendous success in many large-dimensional problems, such as computer vision He et al. (2016) ; Krizhevsky et al. (2017) and natural language processing Devlin (2018) . Several groups of researchers tried to explain the superior performance of neural networks on large-dimensional data from the aspects of "lazy regime" (Arora et al. (2019) ; Du et al. (2019 Du et al. ( , 2018)) ; Li and Liang (2018) ). They noticed that, when the width of a neural network is sufficiently large, its parameters/weights stay in a small neighborhood of their initial position during the training process. Later, Jacot et al. (2018) ; Arora et al. (2019) ; Hu et al. (2021) ; Suh et al. (2021) ; Lai et al. (2023) ; Li et al. (2024) proved that the time-varying neural network kernel (NNK) converges (uniformly) to a time-invariant neural tangent kernel (NTK) as the width of the neural network goes to infinity, and thus the excess risk of kernel gradient flow with NTK converges (uniformly) to the excess risk of neural networks in the 'lazy regime'.Inspired by the concepts of the "lazy regime" and the uniform convergence of excess risk, the machine learning community has experienced a renewed surge of interest in large-dimensional spectral algorithms. The earliest works focused on the consistency of two specific types of spectral algorithms: KRR and kernel interpolation (Liang and Rakhlin (2020) ; Liang et al. (2020) ; Ghorbani et al. (2020 Ghorbani et al. ( , 2021)) ; Mei et al. (2021 Mei et al. ( , 2022)) ; Misiakiewicz and Mei (2022) ; Aerni et al. (2023) ; Barzilai and Shamir (2023) ). In comparison, results on large-dimensional kernel gradient flow were somewhat scarce, and these results largely mirrored those associated with KRR (e.g., Ghosh et al. (2021) ). Recently, Lu et al. (2023) proved that large-dimensional kernel gradient flow is minimax optimal when s = 1. Then, Zhang et al. (2024) provided upper and lower bounds on the convergence rate on the excess risk of KRR for any s > 0. Surprisingly, they discovered that for s > 1, the convergence rate of KRR did not match the lower bound on the minimax rate. Unfortunately, they didn't prove that certain spectral algorithms can reach the lower bound on the minimax rate they provided, and hence they didn't rigorously prove that the saturation effect of KRR occurs in large dimensions. Instead, Zhang et al. (2024) only conjectured that certain spectral algorithms (e.g., kernel gradient flow) can provide minimax optimal estimators after their main results. dimensional neural networks, even if the neural networks are in the 'lazy regime'. The main focus of this paper is to prove this conjecture by showing that kernel gradient flow is minimax optimal in large dimensions.Saturation effects of fixed-dimensional spectral algorithms. When the dimension d of the data is fixed, the saturation effect of KRR has been conjectured for decades and is rigorously proved in the recent work Li et al. (2022) . Suppose f ⋆ ∈ [H] s with s > 2. It is shown that: (i) the minimax optimal rate is n -sβ/(sβ+1) (Rastogi and Sampath (2017) ; Yao et al. (2007) ; Lin et al. (2020) ); and (ii) the convergence rate on the excess risk of KRR is n -2β/(2β+1) (Li et al. (2022) ). More recently, Li et al. (2024) determined the exact generalization error curves of a class of analytic spectral algorithms, which allowed them to further show the saturation effect of spectral algorithms with finite qualification τ (see, e.g., Appendix C): suppose f ⋆ ∈ [H] s with s > 2τ , then the convergence rate on the excess risk of the above spectral algorithms is n -2τ β/(2τ β+1) .New phenomena in large-dimensional spectral algorithms. In the large-dimensional setting where n ≍ d γ with γ > 0, new phenomena exhibited in spectral algorithms are popular topics in recent machine-learning research. A line of work focused on the polynomial approximation barrier phenomenon (e.g., Ghorbani et al. (2021) ; Donhauser et al. (2021) ; Mei et al. (2022) ; Xiao et al. (2023) ; Misiakiewicz (2022) ; Hu and Lu (2022) ). They found that, for the square-integrable regression function, KRR and kernel gradient flow are consistent if and only if the regression function is a polynomial with a low degree. Another line of work considered the benign overfitting of kernel interpolation (i.e., kernel interpolation can generalize) (e.g., Liang and Rakhlin (2020) ; Liang et al. (2020) ; Aerni et al. (2023) ; Barzilai and Shamir (2023) ; Zhang et al. (2024) ). Moreover, two recent work (Lu et al. (2023) ; Zhang et al. (2024) ) discussed two new phenomena exhibited in large-dimensional KRR and kernel gradient flow: the multiple descent behavior and the periodic plateau behavior. The multiple descent behavior refers to the phenomenon that the curve of the convergence rate ( with respect to n ) of the optimal excess risk is non-monotone and has several isolated peaks and valleys; while the periodic plateau behavior refers to the phenomenon that the curve of the convergence rate ( with respect to d ) of the optimal excess risk has constant values when γ is within certain intervals. Finally, Zhang et al. (2024) conjectured that the saturation effect of KRR occurs in large dimensions. The above works imply that these phenomena occur in many spectral algorithms in large dimensions, hence encouraging us to provide a unified explanation of these new phenomena.In this paper, we focus on the large-dimensional spectral algorithms with inner product kernels, and we assume that the regression function falls into an interpolation space [H] s with s > 0. We state our main results as follows: Theorem 1.1 (Restate Theorem 4.1 and 4.2, non-rigorous). Let s > 0, τ ≥ 1, and γ > 0 be fixed real numbers. Denote p as the integer satisfying γ ∈ [p(s + 1), (p + 1)(s + 1)). Then under certain conditions, the excess risk of large-dimensional spectral algorithm with qualification τ satisfiesE fλ ⋆ -f ⋆ 2 L 2 X = Θ P d -min{γ-p,s(p+1)} • poly (ln(d)) , s ≤ τ Θ P d -min{γ-p, τ (γ-p+1)+ps τ +1 ,s(p+1)} • poly (ln(d)) , s > τ,where s = min{s, 2τ }.More specifically, we list the main contributions of this paper as follows:(1) In Theorem 3.1, we show that the convergence rate on the excess risk of (optimally-tuned) kernel gradient flow in large dimensions is Θ P (d -min{γ-p,s(p+1)} ) • poly(ln(d)), which matches the lower bound on the minimax rate given in Theorem 3.3 (up to a logarithmic factor). We find that kernel gradient flow is minimax optimal for any s > 0 and any γ > 0, and KRR is not minimax optimal for s > 1 and for certain ranges of γ (We provide a visual illustration in Figure 2 ). Consequently, we rigorously prove that the saturation effect of KRR occurs in large dimensions.(2) In Theorem 3.3, we enhanced the previous minimax lower bound results given in Lu et al. (2023) and Zhang et al. (2024) . Specifically, we show that the minimax lower bound is Ω(d -min{γ-p,s(p+1)} )/poly(ln(d)). In comparison, the previous minimax lower bound is Ω(d -min{γ-p,s(p+1)} )/d ε for any ε > 0, and the additional term d ε changes the desired convergence rate. (3) In Section 4, we determine the convergence rate on the excess risk of large-dimensional spectral algorithms. From our results, we find several new phenomena exhibited in spectral algorithms in large-dimensional settings. We provide a visual illustration of the above phenomena in Figure 1 : i) The first phenomenon is the polynomial approximation barrier, and as shown in Figure 1 (a), when s is close to zero, the curve of the convergence rate of spectral algorithm drops when γ ≈ p for any integer p and will stay invariant for most of the other γ; ii) The second one is the periodic plateau behavior, and as shown in Figure 1 The "analytic functional argument" introduced in Li et al. ( 2024) is vital in our proof for Theorem 4.1. For readers' convenience, we collect some of the main ingredients here, see Li et al. (2024) for details. Definition E.4. Let A be a linear operator on a Banach space X. The resolvent set ρ(A) is given byρ(A) := {λ ∈ C | A -λ is invertible} ,and we denote R A (λ) := (A -λ) -1 . The spectrum of A is defined by σ(A) := C\ρ(A).A simple but key ingredient in the analytic functional calculus is the following resolvent identity:EQUATIONThe resolvent allows us to define the value of f (A) in analog to the form of Cauchy integral formula, where A is an operator and f is an analytic function. The following two propositions are well-known results on operator calculus. Proposition E.5 (analytic functional calculus). Let A be an operator on a Hilbert space H and f be an analytic function defined on D f ⊂ C. Let Γ be a contour contained in D f surrounding σ(A). Then,EQUATION)and it is independent of the choice of Γ.Now, let Γ be a contour contained in D f surrounding both σ(A) and σ(B). Using (108), we getEQUATIONProposition E.6 (Spectral mapping theorem). Let A be a bounded self-adjoint operator and f be a continuous function on σ(A). ThenLet us define the contour Γ λ considered in Li et al. (2024) by (112) where η = λ/2. Then, since T and T X are positive self-adjoint operators with ∥T ∥, ∥T X ∥ ≤ κ 2 , we have σ(T ), σ(T X ) ⊂ [0, κ 2 ]. Therefore, Γ λ is indeed a contour satisfying the requirement in Proposition E.5. Proposition E.7. Suppose that (45) in Assumption 3 holds. Suppose that λ = λ(n, d) satisfies v := N1(λ) n ln n = o(1). Then for any fixed δ ∈ (0, 1), when n is sufficiently large, with probability at least 1 -δ, we have ∥TΓ λ = Γ λ,1 ∪ Γ λ,2 ∪ Γ λ,3 Γ λ,1 = {x ± (x + η)i ∈ C | x ∈ [-η, 0]} Γ λ,2 = x ± (x + η)i ∈ C | x ∈ (0, κ 2 ) Γ λ,3 = z ∈ C | z -κ 2 = κ 2 + η, Re(z) ≥ κ 2 ,EQUATION)Proof. These inequalities are direct results of ( 56), (58), and (59) in Zhang et al. (2024) . ■ Proposition E.8 (Restate Proposition 4.13 in Li et al. (2024) with only the constant modified). When (113) holds, there is an absolute constant that for any z ∈ Γ λ ,EQUATIONNeurIPS Paper Checklist 1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: We first propose an improved minimax lower bound for the kernel regression problem in large dimensional settings in Theorem 3.3 and show that the gradient flow with early stopping strategy will result in an estimator achieving this lower bound (up to a logarithmic factor) in Theorem 3.1. We further determine the exact convergence rates of a large class of (optimal tuned) spectral algorithms with different qualification τ 's, and provide a discussion on new phenomena we find in Section 4. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
preliminaries: 
 Suppose that we have observed n i.i.d. samples (x i , y i ), i ∈ [n] from the model:EQUATIONwherex i 's are sampled from ρ X , ρ X is the marginal distribution on X ⊂ R d+1 , y ∈ Y ⊂ R, f⋆ is some function defined on a compact set X , andE (x,y)∼ρ ϵ 2 x ≤ σ 2 , ρ X -a.e. x ∈ X ,for some fixed constant σ > 0, where ρ is the joint distribution of (x, y) on X × Y. Denote the n × 1 data vector of y i 's and the n × d data matrix of x i 's by Y and X respectively.In this subsection, we introduce two specific spectral algorithms, kernel ridge regression and kernel gradient flow, which produce estimators of the regression function f ⋆ . A further discussion on general spectral algorithms will be provided in Section 4.Throughout the paper, we denote H as a separable RKHS on X with respect to a continuous and positive definite kernel function K(•, •) : X × X → R and there exists a constant κ satisfyingmax x∈X K(x, x) ≤ κ 2 .Kernel ridge regression Kernel ridge regression (KRR) constructs an estimator f KRR λ by solving the penalized least square problemf KRR λ = arg min f ∈H 1 n n i=1 (y i -f (x i )) 2 + λ∥f ∥ 2 H ,where λ > 0 is referred to as the regularization parameter. The representer theorem (see, e.g., Steinwart and Christmann (2008) ) gives an explicit expression of the KRR estimator, i.e.,EQUATION)Kernel gradient flow The gradient flow of the loss functionEQUATIONIf we further assume that f GF 0 (x) = 0, then we can also give an explicit expression of the kernel gradient flow estimatorf GF t (x) = K(x, X)K(X, X) -1 (I -e -1 n K(X,X)t )Y. (4)Define the integral operatorT K as T K (f )(x) = K(x, x ′ )f (x ′ ) dρ X (x ′ ).It is well known that T K is a positive, self-adjoint, trace-class, and hence a compact operator (Steinwart and Scovel (2012) ).The celebrated Mercer's theorem further assures thatEQUATIONwhere the eigenvalues {λ j , j = 1, 2, ...} is a non-increasing sequence, and the corresponding eigenfunctions {ϕ j (•), j = 1, 2, ...} are orthonormal in L 2 (X , ρ X ) function space.The interpolation space [H] s with source condition s is defined asEQUATIONwith the inner product deduced fromEQUATION)It is easy to show that [H] s is also a separable Hilbert space with orthonormal basis {λ s/2 j ϕ j } j . Generally speaking, functions in [H] s become smoother as s increases (see, e.g., the example of Sobolev RKHS in Edmunds and Triebel (1996) ; Zhang et al. (2023) .In this subsection, we list the assumptions that we need for our main results.To avoid potential confusion, we specify the following large-dimensional scenario for kernel regression where we perform our analysis: suppose that there exist three positive constants c 1 , c 2 and γ, such thatEQUATIONand we often assume that d is sufficiently large.In this paper, we only consider the inner product kernels defined on the sphere. An inner product kernel is a kernel function K defined on S d such that there exists a function Φ : [-1, 1] → R independent of d satisfying that for any x, x ′ ∈ S d , we have K(x, x ′ ) = Φ(⟨x, x ′ ⟩). If we further assume that the marginal distribution ρ X is the uniform distribution on X = S d , then the Mercer's decomposition for K can be rewritten asEQUATIONwhere Y k,j for j = 1, • • • , N (d, k) are spherical harmonic polynomials of degree k and µ k 's are the eigenvalues of K with multiplicityN (d, 0) = 1; N (d, k) = 2k+d-1 k • (k+d-2)! (d-1)!(k-1)! , k = 1, 2, • • • .For more details of the inner product kernels, readers can refer to Gallier (2009) . Remark 2.1. We consider the inner product kernels on the sphere mainly because the harmonic analysis is clear on the sphere ( e.g., properties of spherical harmonic polynomials are more concise than the orthogonal series on general domains). This makes Mercer's decomposition of the inner product more explicit rather than several abstract assumptions ( e.g., Mei and Montanari (2022) ). We also notice that very few results are available for Mercer's decomposition of a kernel defined on the general domain, especially when the dimension of the domain is taking into consideration. e.g., even the eigen-decay rate of the neural tangent kernels is only determined for the spheres. Restricted by this technical reason, most works analyzing the spectral algorithm in large-dimensional settings focus on the inner product kernels on spheres (Liang et al., 2020; Ghorbani et al., 2021; Misiakiewicz, 2022; Xiao et al., 2023; Lu et al., 2023, etc.) . Though there might be several works that tried to relax the spherical assumption (e.g., Liang et al. (2020) ; Aerni et al. (2023) ; Barzilai and Shamir (2023) , we can find that most of them (i) adopted a near-spherical assumption; (ii) adopted strong assumptions on the regression function, e.g.,f ⋆ (x) = x[1]x[2] • • • x[L]for an integer L > 0, where x[i] denotes the i-th component of x; or (iii) can not determine the convergence rate on the excess risk of the spectral algorithm.To avoid unnecessary notation, let us make the following assumption on the inner product kernel K.Assumption 1. Φ(t) ∈ C ∞ ([-1, 1]) is a fixed function independent of d and there exists a nonnegative sequence of absolute constants {a j ≥ 0} j≥0 , such that we haveΦ(t) = ∞ j=0 a j t j ,where a j > 0 for any j ≤ ⌊γ⌋ + 3.The purpose of Assumption 1 is to keep the main results and proofs clean. Notice that, by Theorem 1.b in Gneiting (2013) , the inner product kernel K on the sphere is semi-positive definite for all dimensions if and only if all coefficients {a j , j = 0, 1, 2, ...} are non-negative. One can easily extend our results in this paper when certain coefficients a k 's are zero (e.g., one can consider the two-layer NTK defined as in Section 5 of Lu et al. (2023) , with a i = 0 for any i = 3, 5, 7, • • • ).In the next assumption, we formally introduce the source condition, which characterizes the relative smoothness of f ⋆ with respect to H. Assumption 2 (Source condition). Suppose that f⋆ (x) = ∞ i=1 f i ϕ i (x).(a) f ⋆ ∈ [H] s for some s > 0, and there exists a constant R γ only depending on γ, such thatEQUATION)(b) Denote q as the smallest integer such that q > γ and µ q ̸ = 0. Define I d,k as the index set satisfying λ i ≡ µ k , i ∈ I d,k . Further suppose that there exists an absolute constant c 0 > 0 such that for any d and k ∈ {0, 1, • • • , q} with µ k ̸ = 0, we haveEQUATION)Assumption 2 is a common assumption when one is interested in the tight bounds on the excess risk of spectral algorithms (e.g., Caponnetto and De Vito (2007) ; Fischer and Steinwart (2020) Notations. Let's denote the norm in L 2 (X , ρ X ) as ∥ • ∥ L2 . For a vector x, we use x[i] to denote its i-th component. We use asymptotic notations O(•), o(•), Ω(•) and Θ(•). For instance, we say two (deterministic) quantities U (d), V (d) satisfy U (d) = o(V (d)) if and only if for any ε > 0, there exists a constant D ε that only depends on ε and the absolute positive constants σ, κ, s, γ, c 0 , c 1 , c 2 , C 1 , • • • , C 8 > 0, such that for any d > D ε , we have U (d) < εV (d). We also write a n = poly(b n ) if there exist a constant θ ≥ 0, such that a n = Θ(b θ n ). We use the probability versions of the asymptotic notations such as O P (•), o P (•), Ω P (•), Θ P (•). For instance, we say the random variables X n , Y n satisfying X n = O P (Y n ) if and only if for any ε > 0, there exist constants C ε and N ε such thatP (|X n | ≥ C ε |Y n |) ≤ ε, ∀n > N ε .The following two results are restatements of Theorem 2 and Theorem 5 in Zhang et al. (2024) . Proposition 2.2. Let s ≥ 1 and γ > 0 be fixed real numbers. Denote p as the integer satisfying γ ∈ [p(s + 1), (p + 1)(s + 1)). Suppose that Assumption 1 and Assumption 2 hold for s and γ. Let f KRR λ be the function defined in (2). Define s = min{s, 2}, then there exists λ ⋆ > 0, such that we haveE f KRR λ ⋆ -f ⋆ 2 L 2 X = Θ P d -min{γ-p, γ-p+ps+1 2 ,s(p+1)} • poly (ln(d)) ,where Θ P only involves constants depending on s, σ, γ, c 0 , κ, c 1 and c 2 . In addition, the convergence rates of the generalization error can not be faster than above for any choice of regularization parameter λ = λ(d, n) → 0. Proposition 2.3 (Lower bound on the minimax rate). Let s > 0 and γ > 0 be fixed real numbers. Denote p as the integer satisfying γ ∈ [p(s + 1), (p + 1)(s + 1)). Let P consist of all the distributions ρ on X × Y such that Assumption 1 and Assumption 2 hold for s and γ. Then for any ε > 0, we have:min f max ρ∈P E (X,Y )∼ρ ⊗n f -f ⋆ 2 L 2 = Ω d -min{γ-p,s(p+1)} • d -ε ,where Ω only involves constants depending on s, σ, γ, c 0 , κ, c 1 , c 2 and ε.From the above two propositions, we can find that when s > 1, the convergence rate on the excess risk of KRR does not always match the lower bound on the minimax optimal rate. Zhang et al. (2024) further conjectured that the lower bound on the minimax optimal rate provided in Proposition 2.3 is tight (ignoring the additional term d -ε ). Hence, they believed that the saturation effect exists for large-dimensional KRR.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We explain the reason for considering spherical data in Remark 2.1. We point out in the Conclusion section that our work only considers the optimal-tuned spectral algorithms.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.• 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). 
main results: 
 In this section, we determine the convergence rate on the excess risk of kernel gradient flow as d -min{γ-p,s(p+1)} poly (ln(d)), which differs from the lower bound on the minimax rate provided in Proposition 2.3 by d ε for any ε > 0. We then tighten the lower bound on the minimax rate to d -min{γ-p,s(p+1)} /poly (ln(d)). Based on the above results, we find that KRR is not minimax optimal for s > 1 and for certain ranges of γ. Therefore, we show that the saturation effect of KRR occurs in large dimensions.We first state our main results in this paper. Theorem 3.1 (Kernel gradient flow). Let s > 0 and γ > 0 be fixed real numbers. Denote p as the integer satisfying γ ∈ [p(s + 1), (p + 1)(s + 1)). Suppose that Assumption 1 and Assumption 2 hold for s and γ. Let f GF t be the function defined in (4). Then there exists t ⋆ > 0, such that we haveEQUATIONwhere Θ P only involves constants depending on s, σ, γ, c 0 , κ, c 1 and c 2 .Theorem 3.1 is a direct corollary of Theorem 4.1 and Example 2. Combining with the previous results in Proposition 2.3, or our modified minimax rate given in Theorem 3.3, we can conclude that large-dimensional kernel gradient flow is minimax optimal for any s > 0 and any γ > 0.More importantly, the convergence rate of kernel gradient flow is faster than that of KRR given in Proposition 2.2 when (i) 1 < s ≤ 2 and γ ∈ (p(s + 1) + 1, p(s + 1) + 2s -1) for some p ∈ N, or (ii) s > 2 and γ ∈ (p(s + 1) + 1, (p + 1)(s + 1)) for some p ∈ N. Therefore, we have proved the saturation effect of KRR in large dimensions. Remark 3.2. When p ≥ 1, the logarithm term poly(ln(d)) in ( 12) can be removed. When p = 0, we have poly(ln(d)) = (ln(d)) 2 in (12). See Appendix D.4 for details.Recall that Proposition 2.3 gave a lower bound on the minimax rate as d -min{γ-p,s(p+1)} • d -ε . The following theorem replaces the additional term d -ε (which has changed the convergence rate) into a logarithm term poly -1 (ln(d)) (which does not change the desired convergence rate). Theorem 3.3 (Improved minimax lower bound). Let s > 0 and γ > 0 be fixed real numbers. Denote p as the integer satisfying γ ∈ [p(s + 1), (p + 1)(s + 1)). Let P consist of all the distributions ρ on X × Y such that Assumption 1 and Assumption 2 hold for s and γ. Then we have:EQUATIONwhere Ω only involves constants depending on s, σ, γ, c 0 , κ, c 1 , and c 2 .4 Exact convergence rate on the excess risk of spectral algorithmsIn this section, we will give tight bounds on the excess risks of certain types of spectral algorithms, such as kernel ridge regression, iterated ridge regression, kernel gradient flow, and kernel gradient descent.Given an analytic filter function φ λ (•) with qualification τ ≥ 1 (refer to Appendix C for the definitions of analytic filter function and its qualification), we can define a spectral algorithm in the following way (see, e.g., Bauer et al. (2007) ). For any y ∈ R, let K x : R → H be given by Kx (y) = y • K(x, •), whose adjoint K * x : H → R is given by K * x (f ) = ⟨K(x, •), f ⟩ H = f (x). Moreover, we denote byT x = K x K * x and T X = 1 n n i=1 T xi .We also define the sample basis functionEQUATIONNow, the estimator of the spectral algorithm is defined byEQUATIONMany commonly used spectral algorithms can be constructed by certain analytic filter functions. We provide two examples (kernel ridge regression and kernel gradient flow) as follows, and put two more examples (iterated ridge regression and kernel gradient descent) in Appendix C. We provide rigorous proof for these examples in Lemma C.3.Example 1 (Kernel ridge regression). The filter function of kernel ridge regression (KRR) is wellknown to beEQUATION)Example 2 (Kernel gradient flow). The filter function isEQUATION)For any analytic filter function φ λ with qualification τ ≥ 1 and the corresponding estimator of the spectral algorithm defined in (15), the following two theorems provide exact convergence rates on the excess risk when (i) the regression function is less-smooth, i.e., we have s ≤ τ , and (ii) s > τ , where s is the source condition coefficient of the regression function given in Assumption 2.Theorem 4.1. Let 0 < s ≤ τ and γ > 0 be fixed real numbers. Denote p as the integer satisfying γ ∈ [p(s + 1), (p + 1)(s + 1)). Suppose that Assumption 1 and Assumption 2 hold for s and γ.Let φ λ (z) be an analytic filter function and fλ be the function defined in (15). Suppose one of the following conditions holds:(i) τ = ∞, (ii) s > 1/(2τ ), (iii) γ > ((2τ + 1)s)/(2τ (1 + s));then there exists λ ⋆ > 0, such that we haveE fλ ⋆ -f ⋆ 2 L 2 X = Θ P d -min{γ-p,s(p+1)} • poly (ln(d)) ,where Θ P only involves constants depending on s, σ, γ, c 0 , κ, c 1 and c 2 . Theorem 4.2. Let s > τ and γ > 0 be fixed real numbers. Denote p as the integer satisfying γ ∈ [p(s + 1), (p + 1)(s + 1)). Suppose that Assumption 1 and Assumption 2 hold for s and γ. Let φ λ (z) be an analytic filter function and fλ be the function defined in (15). Define s = min{s, 2τ }, then there exists λ ⋆ > 0, such that we haveE fλ ⋆ -f ⋆ 2 L 2 X = Θ P d -min{γ-p, τ (γ-p+1)+ps τ +1 ,s(p+1)} • poly (ln(d)) ,where Θ P only involves constants depending on s, σ, γ, c 0 , κ, c 1 and c 2 . In addition, the convergence rates of the generalization error can not be faster than above for any choice of regularization parameter λ = λ(d, n) → 0. Remark 4.3. These theorems substantially generalize the results on exact generalization error bounds of analytic spectral algorithms under the fixed-dimensional setting given in Li et al. (2024) . Although the "analytic functional argument" introduced in their proof is still vital for us to deal with the general spectral algorithms, their proof has to rely on the polynomial eigendecay assumption that λ j ≍ j -β (Assumption 1), which does not hold in large dimensions since the hidden constant factors in the assumption vary with d11 (Lu et al. (2023) ). Hence, their proof is not easy to generalize to large-dimensional spectral algorithms.We provide some graphical illustrations of Theorem 4.1 and Theorem 4.2 in Figure 1 (with τ = 2) and in Appendix A (with τ = 1, τ = 2, τ = 4, and τ = ∞, corresponding to KRR, iterated ridge regression in Example 3 and kernel gradient flow).As a direct consequence of Theorem 3.3, Theorem 4.1, and Theorem 4.2, we find that for the spectral algorithm with estimator defined in (15), it is minimax optimal if s ≤ τ and the conditions in Theorem 4.1 hold. Moreover, these results show several phenomena for large-dimensional spectral algorithms.Saturation effect of large-dimensional spectral algorithms with finite qualification. In the large-dimensional setting and for the inner product kernel on the sphere, our results show that the saturation effect of spectral algorithms occurs when s > τ . As shown in Figure 1 (c) and Figure 1(d) , when s > τ , no matter how carefully one tunes the regularization parameter λ, the convergence rate can not be faster than d -min{γ-p, τ (γ-p+1)+ps τ +1,s(p+1)} , thus can not achieve the minimax lower bound d -min{γ-p,s(p+1)} .Periodic plateau behavior of spectral algorithms when s ≤ 2τ . When 0 < s ≤ 2τ and γ ∈ [p(s + 1) + s + max{s, τ }/τ -1, (p + 1)(s + 1)) for an integer p ≥ 0, from Theorem 4.1 and Theorem 4.2, the convergence rate on the excess risk of spectral algorithm d -s(p+1) . The above rate does not change when γ varies, which can also be found in Figure 1(b) and Figure 1(c) . BIn other words, if we fix a large dimension d and increase γ (or equivalently, increase the sample size n), the optimal rate of excess risk of a spectral algorithm stays invariant in certain ranges. Therefore, in order to improve the rate of excess risk, one has to increase the sample size above a certain threshold.Polynomial approximation barrier of spectral algorithms when s → 0. From Theorem 4.1, when s is close to zero, the convergence rate d -min{γ-p,s(p+1)} is unchanged in the range γ ∈ [p(s + 1) + s, (p + 1)(s + 1)), and increases in the short range γ ∈ [p(s + 1), p(s + 1) + s). In other words, the excess risk of spectral algorithms will drop when γ exceeds p(s + 1) ≈ p for any integer p and will stay invariant for most of the other γ. We term the above phenomenon as the polynomial approximation barrier of spectral algorithms (borrowed from Ghorbani et al. ( 2021)), and it can be illustrated by Figure 1 (a) with s = 0.01.Remark 4.4. Ghorbani et al. (2021) discovered the polynomial approximation barrier of KRR. As shown by Figure 5 and Theorem 4 in Ghorbani et al. (2021) , if s = 0 and the true function falls into L 2 = [H] 0 , then with high probability we haveEQUATION)where p is the integer satisfying γ ∈ [p, p + 1), λ ⋆ is defined as in Theorem 4 in Ghorbani et al. (2021) , P >ℓ means the projection onto polynomials with degree > ℓ, and ε is any positive real number. Notice that (18) implies that the excess risk of KRR will drop when γ exceeds any integer and will stay invariant for other γ, and is consistent with our results for spectral algorithms. 
conclusion: 
 In this paper, we rigorously prove the saturation effect of KRR in large dimensions. Let s > 0 and γ > 0 be fixed real numbers, denote p as the integer satisfying γ ∈ [p(s + 1), (p + 1)(s + 1)). Given that the kernel is an inner product kernel defined on the sphere and that f ⋆ falls into the interpolation space [H] s , we first show that the convergence rate on the excess risk of large-dimensional kernel gradient flow is Θ P d -min{γ-p,s(p+1)} • poly (ln(d)) (Theorem 3.1), which is faster than that of KRR given in Zhang et al. (2024) . We then determine the improved minimax lower bound as Ω d -min{γ-p,s(p+1)} /poly (ln(d)) (Theorem 3.3). Combining these results, we know that kernel gradient flow is minimax optimal in large dimensions, and KRR is inferior to kernel gradient flow in large dimensions. Our results suggest that previous results on large-dimensional KRR may not be directly extendable to large-dimensional neural networks if the regression function is over-smooth.In Section 4, we generalize our results to certain spectral algorithms. We determine the convergence rate on the excess risk of large-dimensional spectral algorithms (Theorem 4.1 and Theorem 4.2). From these results, we find several new phenomena exhibited in large-dimensional spectral algorithms, including the saturation effect, the periodic plateau behavior, and the polynomial approximation barrier.In this paper, we only consider the convergence rate on the excess risk of optimal-tuned largedimensional spectral algorithms with uniform input distribution on a hypersphere. We believe that several results in fixed-dimensional settings with input distribution on more general domains (e.g., Haas et al. (2024) ; Li et al. ( 2024)) can indeed be extended to large-dimensional settings, although we must carefully consider the constants that depend on d. Furthermore, we believe that by considering the learning curve of large-dimensional spectral algorithms (i.e., the convergence rate on the excess risk of spectral algorithms with any regularization parameter λ > 0) or the convergence rate on the excess risk of large-dimensional kernel interpolation (i.e., KRR with λ = 0), further research can find a wealth of new phenomena compared with the fixed-dimensional setting. 
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: The paper poses no such risks.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: The 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.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: A.1 Graphical illustration of Theorem 3.1, Theorem 4.1, and Theorem 4.2Recall that Theorem 3.1, Theorem 4.1, and Theorem 4.2 determined the convergence rate on the excess risk of: (i) large-dimensional kernel gradient flow with s > 0; (ii) large-dimensional spectral algorithm with τ ≥ 1 and s ≤ τ ; and (iii) large-dimensional spectral algorithm with τ ≥ 1 and s > τ .In Figure 1 , we have provided a visual illustration of Theorem 4.1 and Theorem 4.2 when τ = 2. Now, in Figure 2 , we provide more visual illustrations of the results of spectral algorithms with τ = 1, τ = 2, τ = 4, and τ = ∞, which correspond to kernel ridge regression (KRR), iterated ridge regression in Example 3, and kernel gradient flow. (a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) (l) (m) (n) (o) (p)We conducted two experiments using two specific kernels: the RBF kernel and the NTK kernel. Experiment 1 was designed to confirm the optimal rate of kernel gradient flow and KRR when s = 1.Experiment 2 was designed to illustrate the saturation effect of KRR when s > 1.Experiment 1: We consider the following two inner product kernels:(i) RBF kernel with a fixed bandwidth:K rbf (x, x ′ ) = exp - ∥x -x ′ ∥ 2 2 2 , x, x ′ ∈ S d .(ii) Neural Tangent Kernel (NTK) of a two-layer ReLU neural network:K ntk (x, x ′ ) := Φ(⟨x, x ′ ⟩), x, x ′ ∈ S d ,whereΦ(t) = [sin (arccos t) + 2(π -arccos t)t] /(2π).The RBF kernel satisfies Assumption 1. For the NTK, the coefficients of Φ(•), {a j } ∞ j=0 , satisfy a j > 0, j ∈ {0, 1} ∪ {2, 4, 6, . . .} and a j = 0, j ∈ {3, 5, 7, . . .} (see, e.g., Lu et al. (2023) ). As noted after Assumption 1, our results can be extended to inner product kernels with certain zero coefficients a j . Specifically, for any γ > 0, as long as a j > 0 for j = ⌊γ⌋, ⌊γ⌋ + 1, the proof and convergence rate remain the same. Therefore, for γ < 2 in our experiments, the convergence rates for NTK will be the same as for the RBF kernel. We used the following data generation procedure:y i = f * (x i ) + ϵ i , i = 1, . . . , n,where each x i is i.i.d. sampled from the uniform distribution on S d , andϵ i i.i.d.∼ N (0, 1).We selected the training sample sizes n with corresponding dimensions d such that n = d γ , γ = 0.5, 1.0, 1.5, 1.8. For each kernel and dimension d, we consider the following regression function f * :EQUATION)This function is in the RKHS H, and it is easy to prove that, for any u 0 ∈ S d , Assumption 2 (b) holds for K(u 0 , •) with s = 1. Therefore, Assumption 2 holds for s = 1. We used logarithmic least squares to fit the excess risk with respect to the sample size, resulting in the convergence rate r. As shown in Figure 3 and Figure 4 , the experimental results align well with our theoretical findings.Experiment 2: We use most of the settings from Experiment 1, except that the regression function is changed to f * (x) = µ s 2 N (d, 2)P 2 (< ξ, x >) with s = 1.9, P 2 (t) := (dt 2 -1)/(d -1) the Gegenbauer polynomial, and ξ ∈ S d . Notice that the addition formulaP 2 (< ξ, x >) = 1 N (d,2) N (d,2) j=1 Y 2,j (ξ)Y 2,j (x) implies that ∥f * ∥ 2 [H] s = 1 N (d, 2) N (d,2) j=1 Y 2 2,j (ξ) = P 2 (1) = 1, hence f * ∈ [H]s and satisfies Assumption 2.Our experiment settings are similar to those on page 30 of Li et al. (2022) . We choose the regularization parameter for KRR and kernel gradient flow as λ = 0.05 • d -θ . For KRR, since Corollary D.16 suggests that the optimal regularization parameter is λ ≍ d -0.7 , we set θ = 0.7. Similarly, based on Corollary D.16, we set θ = 0.5 for kernel gradient flow. Additionally, we set γ = 1.8. The results indicate that the best convergence rate of KRR is slower than that of kernel gradient flow, implying that KRR is inferior to kernel gradient flow when the regression function is sufficiently smooth.We first restate Theorem 3.3. Figure 3 : Results of Experiment 1. We repeated each experiment 50 times and reported the average excess risk for (a) kernel gradient flow (labeled as "kernel regression" in our reports) and (b) kernel ridge regression (KRR) on 1000 test samples. We randomly selected u 1 , u 2 , u 3 and kept them fixed for each repeat. We choose the stopping time t in kernel gradient flow as C 1 n 0.5 , where C 1 ∈ {0.001, 0.01, 0.1, 1, 10, 100, 1000}. We use 5-fold cross-validation to select the regularization parameter λ in kernel ridge regression. The alternative values of λ in cross-validation are C 2 n -C3 , where C 2 ∈ {0.001, 0.005, 0.01, 0.1, 0.5, 1, 2, 5, 10, 40, 100, 300, 1000}, C 3 ∈ {0.1, 0.2, . . . , 1.5}.Theorem B.1 (Restate Theorem 3.3). Let s > 0 and γ > 0 be fixed real numbers. Denote p as the integer satisfying γ ∈ [p(s + 1), (p + 1)(s + 1)). Let P consist of all the distributions ρ on X × Y such that Assumption 1 and Assumption 2 hold for s and γ. Then for any d ≥ C, a sufficiently large constant only depending on s, γ, c 1 , and c 2 , we have the following claims:(i) When γ ∈ (p(s + 1), p + ps + s], we havemin f max ρ∈P E (X,Y )∼ρ ⊗n f -f ⋆ 2 L 2 ≥ ln ln(d) 50(γ -p(s + 1))(ln(d)) 2 d p-γ .(ii) When γ ∈ (p + ps + s, (p + 1)(s + 1)], we havemin f max ρ∈P E (X,Y )∼ρ ⊗n f -f ⋆ 2 L 2 = Ω d -s(p+1) ,where Ω only involves constants depending on s, σ, γ, c 0 , κ, c 1 , and c 2 .Proof of Theorem B.1. The item (ii) is a direct corollary of Theorem 5 in Zhang et al. (2024) . Now we begin to proof the item (i). We need the following lemma. 2023)). For any δ ∈ (0, 1) and any 0 < ε1 , ε2 < ∞ only depending on n, d, {λ j }, c 1 , c 2 , and γ and satisfyingEQUATIONwe haveEQUATIONwhere ρ f⋆ is the joint-p.d.f. of x, y given by ( 1) (with f = f ⋆ , B := f ∈ H, ∥f ∥ [H] s ≤ R γ D := ρ f joint distribution of (y, x) where x ∼ ρ X , y = f (x) + ϵ, ϵ ∼ N (0, σ 2 ), f ∈ B ,EQUATIONTherefore, for any d ≥ C, where C is a sufficiently large constant only depending on s, γ, and c 1 , we haveEQUATION)On the other hand, from Lemma D.11, Lemma D.13, and Lemma D.12, one can check the following claim:Claim 1. Suppose γ ∈ (p(s + 1), p + ps + s]. For any d ≥ C, where C is a sufficiently large constant only depending on s, γ, c 1 , and c 2 , we haveK √ 2σ ε2 /6 ≤ 1 2 N (d, p) ln 18µ s p σ 2 ε2 2 ln ln(d) .Therefore, for any d ≥ C, where C is a sufficiently large constant only depending on s, γ, c 1 , and c 2 , we haveEQUATIONCombining ( 23), ( 24), and (25), we finally have: EQUATIONWe say that {φ λ | λ ∈ (0, 1)} (or simply φ λ (z)) is an analytic filter function if:(1) zφ λ (z) ∈ [0, 1] is non-decreasing with respect to z and non-increasing with respect to λ.(2) The qualification of this filter function is τ ∈ [1, ∞] such that ∀ 0 ≤ τ ′ ≤ τ (and also τ ′ < ∞), there exist positive constants C i only depending on τ ′ , i = 1, 2, 3, 4, 5, such that we haveEQUATION(3) If τ < ∞, then there exists a positive constant C 6 only depending on τ and λ 1 , such that we haveEQUATIONwhere λ 1 is the largest eigenvalue of K defined in (5); and there exist positive constants C 7 and C 8 only depending on τ , such that we haveEQUATION(4) LetD λ = z ∈ C : Re z ∈ [-λ/2, κ 2 ], |Im z| ≤ Re z + λ/2 ∪ z ∈ C : z -κ 2 ≤ κ 2 + λ/2, Re z ≥ κ 2 ;Then φ λ (z) can be extended to be an analytic function on some domain containing D λ and the following conditions holds for all λ ∈ (0, 1):(C1) |(z + λ)φ λ (z)| ≤ Ẽ for all z ∈ D λ ; (C2) |(z + λ)ψ λ (z)| ≤ F λ for all z ∈ D λ ;where Ẽ, F are positive constants. Remark C.2. We remark that some of the above properties are not essential for the definition of filter functions in the literature (Bauer et al., 2007; Gerfo et al., 2008) , but we introduce them to avoid some unnecessary technicalities in the proof. The requirements of analytic filter functions are first considered in Li et al. (2024) and used for their "analytic functional argument", which will also be vital in our proof.The following examples show many commonly used analytic filter functions and their proofs can be found in Lemma C.3, see also Li et al. (2024) . Example 3 (Iterated ridge regression). Let q ≥ 1 be fixed. We defineEQUATION)Example 4 (Kernel gradient descent). The gradient descent method is the discrete version of gradient flow. Let η > 0 be a fixed step size. Then, iterating gradient descent with respect to the empirical loss t steps yields the filter functionEQUATIONEQUATIONMoreover, when η is small enough, say η < 1/(2κ 2 ), we have Re(1 -ηz) > 0 for z ∈ D λ , so we can take the single-valued branch of (1 -ηz) t even when t is not an integer. Therefore, we can extend the definition of the filter function so that λ can be arbitrary and t = (ηλ) -1 .Lemma C.3. φ KRR λ , φ IT,q λ , φ GF λ , and φ GD λ are analytic filter functions.Proof. Notice that (i) z ≤ z + λ ≤ 2z when z > λ; and that (ii) λ ≤ z + λ ≤ 2λ when z ≤ λ.Hence, the constants C 1 , C 2 , C 3 , C 4 , and C 6 are given in Li et al. (2024) .For C 5 , when z ≤ λ, we can take C 5 = min{1/2, 2 -q , e -1 , e -1 } > 0.For C 7 , when z > λ, we have(z/λ) 2τ (ψ KRR λ (z)) 2 = z z + λ 2 ≥ 1/4 (z/λ) 2τ (ψ IT,q λ (z)) 2 = z z + λ 2q ≥ 2 -2q .For C 8 , when z ≤ λ, we havez 2τ -1 (ψ KRR λ (z)) 2 λ 2τ φ KRR λ (z) = z z + λ ≤ 1 2 z 2τ -1 (ψ IT,q λ (z)) 2 λ 2τ φ IT,q λ (z) = z 2q (z + λ) 2q -[λ(z + λ)] q ≤ 1 2 2q -2 q .■ D Proof of Theorem 4.1 and Theorem 4.2We first apply a standard bias-variance decomposition on the excess risk of spectral algorithms, and readers can also refer to Zhang et al. (2023 Zhang et al. ( , 2024) ) for more details.Recall the definition of ĝZ and fλ in ( 14) and ( 15). Let's define their conditional expectations asEQUATIONandEQUATIONLet's also define their expectations asEQUATIONandEQUATION)Then we have the decompositionEQUATIONTaking expectation over the noise ϵ conditioned on X and noticing that ϵ|X are independent noise with mean 0 and variance σ 2 , we obtain the bias-variance decomposition:EQUATIONwhereEQUATION)Given the decomposition (40), we next derive the upper and lower bounds of Bias 2 (λ) and Var(λ) in the following two subsections.Before we close this subsection, let's introduce some quantities and an assumption that will be used frequently in our proof later. Denote the true function as f ⋆ = ∞ i=1 f i ϕ i (x), let's define the following quantities:EQUATIONandEQUATIONandEQUATIONFor simplicity of notations, we denote h x (•) = K(x, •), x ∈ X in the rest of the proof. Moreover, we denote T λ := (T + λ) -1 and T Xλ := (T X + λ) -1 .The following proposition rewrites the variance term using the empirical semi-norm. Proposition D.1 (Restate Lemma 9 in Zhang et al. ( 2024)). The variance term in (41) satisfies thatEQUATIONThe operator form (46) allows us to apply concentration inequalities and establish the following two-step approximation.EQUATIONApproximation B The following lemma characterizes the magnitude of Approximation B in high probability. Recall the definitions of N 1,φ (λ) and N 2,φ (λ) in (42). Lemma D.2 (Approximation B). Suppose that (43) in Assumption 3 holds. Then, for any fixed δ ∈ (0, 1), with probability at least 1 -δ, we haveEQUATIONwhereEQUATIONProof. Define a functionEQUATIONSince (43) in Assumption 3 holds, we have∥f ∥ L ∞ ≤ N 2,φ (λ); ∥f ∥ L 1 = N 2,φ (λ).Applying Proposition 34 in Zhang et al. (2024) forEQUATIONwith probability at least 1 -δ.On the one hand, we havef 2 L 2 ,n = X f (z)dP n (z) = X X (φ λ (T ) h x (z)) 2 dρ X (x) dP n (z) = X X (φ λ (T ) h x (z)) 2 dP n (z) dρ X (x) = X ∥φ λ (T ) h x ∥ 2 L 2 ,n dρ X (x).On the other hand, we havef 2 L 2 = X f (z)dρ X (z) = X X (φ λ (T ) h x (z)) 2 dρ X (x) dρ X (z) = X ∥φ λ (T ) h x ∥ 2 L 2 dρ X (x).Therefore, (53) implies the desired results. ■Approximation A Lemma D.3. Suppose that ( 43) and ( 45) in Assumption 3 hold. Suppose that there exists a constant ϵ only depending on s and γ, such that λ = λ(n, d) satisfies n ϵ-1 N 1 (λ) → 0. Then there exists an absolute constant C 1 , such that for any fixed δ ∈ (0, 1), when n is sufficiently large, with probability at least 1 -δ, we have Proof. We start withEQUATIOND = |∥φ λ (T X )h x ∥ L 2 -∥φ λ (T )h x ∥ L 2 | ≤ T 1 2 [φ λ (T ) -φ λ (T X )] h x H .Using operator calculus, we getT 1 2 [φ λ (T ) -φ λ (T X )] h x = T 1 2 1 2πi Γ λ R T X (z)(T -T X )R T (z)φ λ (z)dz h x = 1 2πi Γ λ T 1 2 (T X -z) -1 (T -T X )(T -z) -1 h x φ λ (z)dz = 1 2πi Γ λ T 1 2 T -1 2 λ • T 1 2 λ (T X -z) -1 T 1 2 λ • T -1 2 λ (T -T X )T -1 2 λ • T 1 2 λ (T -z) -1 T 1 2 λ • T -1 2 λ h x φ λ (z)dz.Therefore, taking the norms yieldsD ≤ 1 2π T 1 2 T -1 2 λ • T 1 2 λ (T X -z) -1 T 1 2 λ • T -1 2 λ (T -T X )T -1 2 λ • T 1 2 λ (T -z) -1 T 1 2 λ • T -1 2 λ h x H Γ λ |φ λ (z)dz| = 1 2π • I • II • III • IV • V • Γ λ |φ λ (z)dz| ≤ 1 2π • 1 • √ 6C • N 1 (λ) n ln n • C • N 1 (λ) Γ λ |φ λ (z)dz|,where in the second estimation, we use (I) operator calculus, (II and IV) Proposition E.8, (III) Lemma E.7, and (V) Lemma 37 in Zhang et al. (2024) for each term respectively. Finally, from (63) in Li et al. (2024) , we getEQUATIONand thus there exists an absolute constant C 1 , such that we haveD = |∥φ λ (T X )h x ∥ L 2 -∥φ λ (T )h x ∥ L 2 | ≤ C 1 vN 1 (λ) ln λ -1 .On the other hand, combining ( 52) and ( 43) in Assumption 3, we have∥φ λ (T )h x ∥ 2 L 2 ≤ N 2,φ (λ), and hence ∥φ λ (T X )h x ∥ L 2 + ∥φ λ (T )h x ∥ L 2 ≤ 2∥φ λ (T )h x ∥ L 2 + D ≤ N 2,φ (λ) + C 1 vN 1 (λ) ln λ -1 .Finally,∥φ λ (T X )h x ∥ 2 L 2 -∥φ λ (T )h x ∥ 2 L 2 = |∥φ λ (T X )h x ∥ L 2 -∥φ λ (T )h x ∥ L 2 | (∥φ λ (T X )h x ∥ L 2 + ∥φ λ (T )h x ∥ L 2 ) ≤ C 1 N 2,φ (λ) + C 1 vN 1 (λ) ln λ -1 • vN 1 (λ) ln λ -1 ,and henceX ∥φ λ (T X ) h x ∥ 2 L 2 ,n dρ X (x) - X ∥φ λ (T ) h x ∥ 2 L 2 ,n dρ X (x) ≤ 1 n n i=1 ∥φ λ (T X )h xi ∥ 2 L 2 -∥φ λ (T )h xi ∥ 2 L 2 ≤ sup x∈X ∥φ λ (T X )h x ∥ 2 L 2 -∥φ λ (T )h x ∥ 2 L 2 ≤ C 1 N 2,φ (λ) + C 1 vN 1 (λ) ln λ -1 • vN 1 (λ) ln λ -1 ,Final proof of the variance term Now we are ready to state the theorem about the variance term. Theorem D.5. Suppose that ( 43) and (45) in Assumption 3 hold. Suppose there exists a constant ϵ > 0 only depending on s and γ, such that λ = λ(n, d) satisfiesEQUATIONEQUATIONthen we haveEQUATION) Proof. Recall that Var(λ) = σ 2 n X ∥φ λ (T X ) h x ∥ 2 L 2 ,n dρ X (x).Hence, when n is large enough, with probability at least 1 -δ we haveX ∥φ λ (T X ) h x ∥ 2 L 2 ,n dρ X (x) -∥φ λ (T )h x ∥ 2 L 2 dρ X (x) ≤ X ∥φ λ (T X ) h x ∥ 2 L 2 ,n dρ X (x) - X ∥φ λ (T ) h x ∥ 2 L 2 ,n dρ X (x) + X ∥φ λ (T ) h x ∥ 2 L 2 ,n dρ X (x) - X ∥φ λ (T )h x ∥ 2 L 2 dρ X (x) Lemma D.2 ≤ X ∥φ λ (T X ) h x ∥ 2 L 2 ,n dρ X (x) - X ∥φ λ (T ) h x ∥ 2 L 2 ,n dρ X (x) + 5N 2,φ (λ) 3n ln 2 δ Lemma D.3 ≤ N 2,φ (λ) • C 1 vN 1 (λ) ln λ -1 + C 2 1 vN 1 (λ)(ln λ -1 ) 2 + 5N 2,φ (λ) 3n ln 2 δ Definition of v = N 2,φ (λ) n N 1 (λ) • C 1 ln(n) ln λ -1 + N 2 1 (λ) n • C 2 1 ln(n)(ln λ -1 ) 2 + N 2,φ (λ) n • 5 3 ln 2 δ = I • C 1 ln(n) ln λ -1 + II • C 2 1 ln(n)(ln λ -1 ) 2 + III • 5 3 ln 2 δ .When n ≥ C, a sufficiently large constant only depending on γ and C 1 , we haveI • C 1 ln(n) ln λ -1 ≤ 1 6 N 2,φ (λ).Furthermore, whenN 2 1 (λ) nN2,φ(λ) • n ϵ → 0, we have I • C 1 ln(n) ln λ -1 /N 2,φ (λ) → 0 and II • C 2 1 ln(n)(ln λ -1 ) 2 /N 2,φ (λ) → 0. Finally, from (52) we have ∥φ λ (T )h x ∥ 2 L 2 = ∞ i=1 (λ j φ λ (λ j )) 2 ϕ 2 i (z),and thus the deterministic term writesEQUATION.In this subsection, our goal is to determine the upper and lower bounds of bias under some approximation conditions.The triangle inequality implies thatEQUATION)The following lemma characterizes the dominant term of Bias(λ).Lemma D.6. For any λ > 0, we haveEQUATION)Proof. We have∥f λ -f ⋆ ∥ 2 L 2 = ∞ i=1 λ i φ λ (λ i )f i ϕ i (x) - ∞ i=1 f i ϕ i (x) 2 L 2 = ∞ i=1 ψ λ (λ i )f i ϕ i (x) 2 L 2 = ∞ i=1 (ψ λ (λ i )f i ) 2 = M 2,φ (λ).The following lemma bounds the remainder term of Bias(λ) when s ≥ 1.Lemma D.7. Suppose that (45) in Assumption 3 holds. Suppose that there exist constants ϵ and C only depending on s and γ, such that λ = λ(n, d) satisfiesEQUATIONEQUATIONEQUATIONthen we haveEQUATION)Proof. Do the decomposition,EQUATION)Bound on I: For the first term in (66), we have∥I∥ L 2 = ∥φ λ (T X )(g X -T X f λ -g + T f λ )∥ L 2 = T 1 2 φ λ (T X )(g X -T X f λ -g + T f λ ) H ≤ T 1 2 T -1 2 λ • T 1 2 λ φ λ (T X )T 1 2 λ • T -1 2 λ [(g X -T X f λ ) -(g -T f λ )] H (72) in Zhang et al. (2024) ≤ T 1 2 λ φ λ (T X )T 1 2 λ • T -1 2 λ [(g X -T X f λ ) -(g -T f λ )] H Proposition E.1 ≤ 4 T 1 2 λ T -1 Xλ T 1 2 λ • T -1 2 λ [(g X -T X f λ ) -(g -T f λ )] H (62) and (73) in Zhang et al. (2024) ≤ 12 T -1 2 λ [(g X -T X f λ ) -(g -T f λ )] H , Denote ξ i = ξ(x i ) = T -1 2 λ (K xi f ⋆ (x i ) -T xi f λ ).To use Bernstein inequality, we need to bound the m-th moment of ξ(x):EQUATION)Note that Lemma 37 in Zhang et al. (2024) shows thatT -1 2 λ K(x, •) H ≤ N 1 (λ) 1 2 , µ-a.e. x ∈ X ;By definition of M 1,φ (λ), we also haveEQUATION)In addition, we have proved in Lemma D.6 thatE|(f λ (x) -f ⋆ (x))| 2 = M 2,φ (λ).So we get the upper bound of (67), i.e.,(67) ≤ N 1 (λ) m 2 • ∥f λ -f ⋆ ∥ m-2 L ∞ • E|(f λ (x) -f ⋆ (x))| 2 = N 1 (λ) m 2 M 1,φ (λ) m-2 M 2,φ (λ) = N 1 (λ) 1 2 M 1,φ (λ) m-2 N 1 (λ) 1 2 M 2,φ (λ) 1 2 2 .Using Lemma 36 in Zhang et al. (2024) with therein notations: L = N 1 (λ)1 2 M 1,φ (λ) and σ = N 1 (λ) 1 2 M 2,φ (λ)1 2 , for any fixed δ ∈ (0, 1), with probability at least 1 -δ, we haveEQUATION)Bound on II: For the second term in (66), we haveEQUATION)For the first term in (70), we still employ the analytic functional argument:T 1 2 (φ λ (T X )T ψ λ (T ) -ψ λ (T )T φ λ (T ))f ⋆ = T 1 2 (φ λ (T X ) -φ λ (T ))T ψ λ (T )f ⋆ = 1 2πi Γ λ T 1 2 (T X -z) -1 (T X -T )(T -z) -1 φ λ (z)T ψ λ (T )f ⋆ dz = 1 2πi Γ λ T 1 2 T -1 2 λ • T 1 2 λ (T X -z) -1 T 1 2 λ • T -1 2 λ (T -T X )T -1 2 λ • T 1 2 λ (T -z) -1 T 1 2 λ • T -1 2 λ T 1 2 • T 1 2 ψ λ (T )f ⋆ φ λ (z)dz.Therefore,EQUATIONwhere v = N1(λ) n ln n.For the second term in (70), we haveT 1 2 (ψ λ (T X )T φ λ (T ) -ψ λ (T )T φ λ (T ))f ⋆ = T 1 2 1 2πi Γ λ R T X (z)(T -T X )R T (z)ψ λ (z)dz T φ λ (T )f ⋆ = 1 2πi Γ λ T 1 2 (T X -z) -1 (T -T X )(T -z) -1 ψ λ (z)T φ λ (T )f ⋆ dz = 1 2πi Γ λ T 1 2 T -1 2 λ • T 1 2 λ (T X -z) -1 T 1 2 λ • T -1 2 λ (T -T X )T -1 2 λ • T 1 2 λ (T -z) -1 T 1 2 λ • T -1 2 λ T φ λ (T )f ⋆ ψ λ (z)dz.Hence, similar to (71), we haveEQUATION)Combining ( 66), ( 69), ( 70), ( 71), and ( 72), there exists a constant C 1 only depending on δ and F , such that we have fλ -EQUATION)When s < 1, we can use the following lemma to bound the remainder term of Bias(λ). This lemma is a modification of Lemma D.7, and its proof is partly based on Lemma 26 in Zhang.Lemma D.8. Suppose that (45) in Assumption 3 holds. Suppose that there exist constants ϵ and C only depending on s and γ, such that λ = λ(n, d) satisfiesEQUATIONEQUATIONEQUATION)EQUATION)Proof. Similar to the proof in Lemma D.7, we have the decomposition fλ -f λ = I + II, with∥I∥ 2 L 2 ≤ 12 2 T -1 2 λ [(g X -T X f λ ) -(g -T f λ )] 2 H , ∥II∥ 2 L 2 = o M 2,φ (λ) + σ 2 n N 2,φ (λ) . Denote ξ i = ξ(x i ) = T -1 2 λ (K xi f ⋆ (x i ) -T xi f λ ). Further consider the subset Ω 1 = {x ∈ X : |f ⋆ (x)| ≤ t} and Ω 2 = X \Ω 1, where t will be chosen appropriately later. Decompose ξ i as ξ i I xi∈Ω1 + ξ i I xi∈Ω2 and we have the following decomposition:EQUATION)Next we choose t = n 1-s 2 +ϵt , q = 2 1-s -ϵ q such that ϵ t < ϵ; andEQUATION)Then we can bound the three terms in (78) as follows:(i) For the first term in (78), denoted as I, notice that∥(f λ -f ⋆ ) I xi∈Ω1 ∥ L ∞ ≤ ∥f λ ∥ L ∞ + n 1-s 2 +ϵt .(81) Imitating (67) in the proof of Lemma D.7, we haveEQUATION)(ii) For the second term in (78), denoted as II. Since q = 2 1-s -ϵ q < 2 1-s , Lemma 42 in Zhang et al. (2024) shows that,[H] s → L q (X , µ), (83) with embedding norm less than a constant C s,κ . Then Assumption 2 (a) implies that there exists 0 < C q < ∞ only depending on γ, s and κ such that ∥f ⋆ ∥ L q (X ,µ) ≤ C q . Using the Markov inequality, we haveP (x ∈ Ω 2 ) = P |f ⋆ (x)| > t ≤ E|f ⋆ (x)| q t q ≤ (C q ) q t q .Further, since (80) guarantees t q ≫ n, we haveEQUATIONEQUATION(iii) For the third term in (78), denoted as III. Since Lemma 37 in Zhang et al. (2024) implies thatEQUATIONwhere we use Cauchy-Schwarz inequality for the third inequality and Lemma D.6 for the fourth inequality. Recalling that the choices of t, q satisfy t -q ≪ n -1 and we have assumedEQUATION)Plugging ( 82), ( 84) and ( 87) into (78), we finish the proof. ■Final proof of the bias term Now we are ready to state the theorem about the bias term. Theorem D.9 (s ≥ 1). Suppose that (45) in Assumption 3 holds. Suppose that there exist constants ϵ and C only depending on s and γ, such that λ = λ(n, d) satisfiesn ϵ-1 N 1 (λ) → 0, N 1 (λ)M 2 1,φ (λ) n 2 ≪ M 2,φ (λ) + σ 2 n N 2,φ (λ) , N 1 (λ) n ln(n)(ln λ -1 ) 2 • ∞ j=1 λ 2 λ i φ 2 λ (λ i ) λ + λ i f 2 i ≪ M 2,φ (λ) + σ 2 n N 2,φ (λ) ;then we haveEQUATIONTheorem D.10 (s < 1). Suppose that (45) in Assumption 3 holds. Suppose that there exist constants ϵ and C only depending on s and γ, such that λ = λ(n, d) satisfiesn ϵ-1 N 1 (λ) → 0, N 1 (λ) n ln(n)(ln λ -1 ) 2 • ∞ j=1 λ 2 λ i φ 2 λ (λ i ) λ + λ i f 2 i ≪ M 2,φ (λ) + σ 2 n N 2,φ (λ) ; n -1 N 1 (λ) 1 2 ∥f λ ∥ L ∞ + n 1-s 2 +ϵ = o M 2,φ (λ) + σ 2 n N 2,φ (λ)1/2; then we haveEQUATIOND.4 Quantity calculations and conditions verification for the inner product kernelsIn the previous two sections, we have successfully bounded the bias and the variance terms by the quantities M 2,φ (λ) and N 2,φ (λ). In this subsection, we will focus on the inner product kernels on the sphere. We will (i) determine the rates for the above quantities, and (ii) verify all the conditions in Theorem D.5, Theorem D.9 and Theorem D.10.Recall that µ k and N (d, k), defined in (9), are the eigenvalues of the inner product kernel K defined on the sphere and the corresponding multiplicity. The following three lemmas (mainly cited from Lu et al. ( 2023)) give concise characterizations of µ k and N (d, k), which is sufficient for the analysis in this paper. Lemma D.11. For any fixed integer p ≥ 0, there exist constants C, C 9 and C 10 only depending on p and {a j } j≤p+1 , such that for any d ≥ C, we haveEQUATIONLemma D.12. For any fixed integer p ≥ 0, there exist constants C only depending on p and {a j } j≤p+1 , such that for any d ≥ C, we haveµ k ≤ C 10 C 9 d -1 µ p , k = p + 1, p + 2, • • •where C 9 and C 10 are constants given in Lemma D.11. Lemma D.13. For any fixed integer p ≥ 0, there exist constants C 11 , C 12 and C only depending on p, such that for any d ≥ C, we haveEQUATIONWith these lemmas, we can begin to bound the quantities M 2,φ (λ) and N 2,φ (λ). Lemma D.14. Suppose that Assumption 1 and Assumption 2 hold for s and an integer p. Supposeℓ ≤ p, t = λ -1 ∈ (d ℓ , d ℓ+1 ].Then we have the following bound.EQUATIONand thus Assumption 3 holds. Moreover, when s ≥ 1, We haveEQUATIONProof. I. We begin with M 2,φ (λ). If s ≤ 2τ and τ < ∞, then we haveM 2,φ (λ) = ∞ k=0 ψ 2 λ (µ k ) N (d,k) j=1 f 2 k,j ≤ ℓ k=0 C 2 2 (tµ k ) -2τ (µ k ) s N (d,k) j=1 (µ k ) -s f 2 k,j + ∞ k=ℓ+1 ψ 2 λ (µ k ) N (d,k) j=1 f 2 k,j ≤ ℓ k=0 C 2 2 (tµ k ) -2τ (µ k ) s N (d,k) j=1 (µ k ) -s f 2 k,j + ∞ k=ℓ+1 (µ k ) s N (d,k) j=1 (µ k ) -s f 2 k,j ≤ C 2 2 t -2τ (C 9 d -ℓ ) s-2τ ℓ k=0 N (d,k) j=1 (µ k ) -s f 2 k,j + (C 10 d -ℓ-1 ) s ∞ k=ℓ+1 N (d,k) j=1 (µ k ) -s f 2 k,j = O t -2τ d ℓ(2τ -s) + d -s(ℓ+1) ;and when τ = ∞, a similar argument ( taking τ ′ < τ and let τ ′ → ∞, then we have(td -ℓ ) -2τ ′ → 0) shows that M 2,φ (λ) = O(d -s(ℓ+1) ).Similarly, if s ≤ 2τ , then we haveM 2,φ (λ) ≥ 1 {τ < ∞} ℓ k=0 C 2 7 (tµ k ) -2τ (µ k ) s N (d,k) j=1 (µ k ) -s f 2 k,j + ∞ k=ℓ+1 ψ 2 λ (µ k ) N (d,k) j=1 f 2 k,j ≥ 1 {τ < ∞} Ω t -2τ d ℓ(2τ -s) + ∞ k=ℓ+1 C 2 5 (µ k ) s N (d,k) j=1 (µ k ) -s f 2 k,j ≥ 1 {τ < ∞} Ω t -2τ d ℓ(2τ -s) + C 2 5 (C 10 d -ℓ-1 ) s N (d,ℓ) j=1 (µ ℓ ) -s f 2 ℓ,j = 1 {τ < ∞} Ω t -2τ d ℓ(2τ -s) + Ω d -s(ℓ+1) . If 2τ < s, then M 2,φ (λ) = ∞ k=0 ψ 2 λ (µ k ) N (d,k) j=1 f 2 k,j Lemma E.3 ≤ κ 2(s-2τ ) λ 2τ ∞ k=0 N (d,k) j=1 µ -s k f 2 k,j = O λ 2τ .Similarly, if 2τ < s, then we haveM 2,φ (λ) ≥ ψ 2 λ (µ 0 )f 2 0,1 ≥ C 2 6 f 2 0,1 • λ 2τ = Ω λ 2τ .II. Now let's bound the second term N 2,φ (λ)/n. We haveN 2,φ (λ) n = 1 n ∞ k=0 N (d, k) [µ k φ λ (µ k )] 2 ≤ 1 n ℓ k=0 N (d, k) + 1 n ∞ k=ℓ+1 N (d, k) [µ k φ λ (µ k )] 2 ≤ 1 n ℓ k=0 N (d, k) + C 2 4 t 2 n ∞ k=ℓ+1 N (d, k)(µ k ) 2 ≤ ℓ N (d, ℓ) n + C 2 4 t 2 n µ ℓ+1 = O d ℓ n + t 2 nd ℓ+1 . (94)Similarly, we haveN 2,φ (λ) n ≥ C 2 1 n ℓ k=0 N (d, k) + C 2 3 t 2 n ∞ k=ℓ+1 N (d, k)(µ k ) 2 ≥ C 2 1 N (d, ℓ) n + C 2 3 t 2 n µ ℓ+1 = Ω d ℓ n + t 2 nd ℓ+1 .(95) III. For the third term, we have∞ k=0 λ 2 µ k φ 2 λ (µ k ) λ + µ k N (d,k) j=1 f 2 k,j ≤ λ 2 R 2 γ   p k=0 µ s k φ 2 λ (µ k ) + λ -1 ∞ k=p+1 µ s+1 k C 2 4 λ -2   = O λ 2 d max{p(2-s),0} + λ -1 d -(s+1)(ℓ+1) = O λ 2 d max{p(2-s),0} + d -s(ℓ+1)IV. Now we show that Assumption 3 holds. Notice that (45) has been verified in Lemma 20 of Zhang et al. (2024) . Similarly, one can prove ( 43) and ( 44) hold using a similar proof as that for Lemma 20 of Zhang et al. (2024) .V. For the final term, when s ≥ 1, we haveEQUATIONFor Q 1,φ (λ), when τ ≥ s/2 and τ < ∞, we haveEQUATIONSimilarly, when τ = ∞, we can show thatQ 1,φ (λ) = O(λd -(ℓ+1)(s-1) ).And when τ < s/2, we haveEQUATION≤ C 2 2 κ 2(s-2τ ) C 1 λ 2τ p k=0 N (d,k) j=1 µ -s k f 2 k,j + ∞ k=p+1 C 8 λ 2τ N (d,k) j=1 µ -s k f 2 k,j = O λ 2τ .For N 1,φ (λ), we haveN 1,φ (λ) = ∞ k=0 N (d, k) [µ k φ λ (µ k )] ≤ ℓ k=0 N (d, k) + ∞ k=ℓ+1 N (d, k) [µ k φ λ (µ k )] ≤ ℓ k=0 N (d, k) + C 4 t ∞ k=ℓ+1 N (d, k)µ k ≤ ℓN (d, ℓ) + C 4 t = O d ℓ + λ -1 = O λ -1 .(98) Therefore, when s ≥ 1, we haveEQUATION■ From Lemma D.14, we have the following three corollaries. Corollary D.15. Let 1 ≤ s ≤ τ and γ > 0 be fixed real numbers. Denote p as the integer satisfying γ ∈ [p(s + 1), (p + 1)(s + 1)). Suppose one of the following cases holds for λ ⋆ = d -ℓ or λ ⋆ = d -ℓ • poly (ln(d)):(1) p ≥ 1, p(s + 1) ≤ γ < ps + p + s, ℓ = p + 1/2(2) p ≥ 1, ps + p + s ≤ γ < ps + p + s + 1, ℓ = (γ -(p + 1)(s -1))/2(3) γ < s, ℓ = min{γ, 1}/2(4) s ≤ γ < s + 1, ℓ = (γ -(s -1))/2Then we haveEQUATIONorEQUATION)Corollary D.16. Let τ < s ≤ 2τ and γ > 0 be fixed real numbers. Denote p as the integer satisfying γ ∈ [p(s + 1), (p + 1)(s + 1)). Denote ∆ = γ -p(s + 1). Suppose one of the following cases holds for λ ⋆ = d -ℓ or λ ⋆ = d -ℓ • poly (ln(d)):(1) γ ≥ 1, 0 ≤ ∆ ≤ τ , ℓ = ℓ 1 := p + ∆/(2τ ) (2) γ ≥ 1, τ ≤ ∆ ≤ s + s/τ -1, ℓ = ℓ 2 := p + (∆ + 1)/(2τ + 2) (3) γ ≥ 1, ∆ ≥ s + s/τ -1, ℓ = ℓ 3 := p + (∆ + 1 -s)/2 (4) γ < 1, ℓ = γ/2Then we haveEQUATIONorM 2,φ (λ ⋆ ) ≍ N 2,φ (λ ⋆ ) n = Θ d -min{γ-p, τ (γ-p+1)+ps τ +1,s(p+1)} • poly (ln(d)) .Proof. Denote I = -2ℓτ + 2pτ -ps, II = -sp -s, III = p -γ, and IV = 2ℓ -γ -p -1. From Lemma D.14 we haveM 2,φ (λ ⋆ ) ≍ d I + d II , N 2,φ (λ ⋆ ) n ≍ d III + d IV .We can verify that:(1) When 0 ≤ ∆ ≤ τ and ℓ = p + ∆/(2τ ), we haveII ≤ I = III ≥ IV and min γ -p, τ (γ -p + 1) + ps τ + 1 , s(p + 1) = γ -p;(2) When τ ≤ ∆ ≤ s + s/τ -1 and ℓ = p + (∆ + 1)/(2τ + 2), we have II ≤ I = IV ≥ III and min γ -p, τ (γ -p + 1) + ps τ + 1 , s(p + 1) = τ (γ -p + 1) + ps τ + 1 ;(3) When ∆ ≥ s + s/τ -1 and ℓ = p + (∆ + 1 -s)/2, we have I ≤ II = IV ≥ III and min γ -p, τ (γ -p + 1) + ps τ + 1 , s(p + 1) = s(p + 1);(4) When γ < 1 and ℓ = γ/2, we have III ≥ max{I, II, IV}.Corollary D.17. Let s < 1 and γ > 0 be fixed real numbers. Denote p as the integer satisfying γ ∈ [p(s + 1), (p + 1)(s + 1)). Suppose one of the following cases holds for λ ⋆ = d -ℓ or λ ⋆ = d -ℓ • poly (ln(d)):(1) τ = ∞, p ≥ 1, p(s + 1) ≤ γ < ps + p + s, ℓ = p + s/2(2) τ = ∞, p ≥ 1, ps + p + s ≤ γ < ps + p + s + 1, ℓ = (γ + p(1 -s))/2 (3) τ = ∞, γ < s, ℓ = min{γ, 1, 2γs}/2 (4) τ = ∞, s ≤ γ < s + 1, ℓ = min{(γ + (1 -s))/2, γ(1 + s) -s, γ/2} (5) τ < ∞, p(s + 1) ≤ γ < ps + p + s, ℓ = (γ + 2τ p -sp -p)/(2τ ) (6) τ < ∞, ps + p + s ≤ γ < ps + p + s + 1, ℓ = p + s/(2τ )Then we haveEQUATIONorEQUATIONLemma D.18 (Verification of variance conditions for inner-product kernels). Suppose n ≍ d γ and s ≥ 1, for γ ∈ [p(s + 1), (p + 1)(s + 1)). For any given ℓ ≥ 0, ifλ ≥    d -ℓ 1 + ln 2 (d)1{γ = 2, s = 1} p ≥ 1, 2ℓ ≤ max{2p + 1, γ -(p + 1)(s -1)} d -ℓ ln 2 (d) p = 0, γ ≥ 1, 2ℓ ≤ max{1, γ -(s -1)} d -ℓ p = 0, γ < 1, 2ℓ ≤ γ;then there exists a constant ϵ > 0 only depending on s and γ, such that λ = λ(n, d) satisfiesN 1 (λ) • n ϵ-1 → 0, N 2 1 (λ) nN 2,φ (λ)• ln(n)(ln λ -1 ) 2 → 0.Proof. From Lemma 21 in Zhang et al. (2024) , we have N 1 (λ) ≍ λ -1 . When p = 0, we have γ -ℓ > 0. When p ≥ 1, we have γ -p -1/2 ≥ ps -1/2 > 0. Therefore, there exists a constant ϵ > 0 only depending on s and γ, such that we haveN 1 (λ) • n ϵ-1 → 0.Denote q := ⌊ℓ⌋. From Lemma D.14, we further have N 2,φ (λ) = Ω d q + λ -2 d -q-1 . Hence, we haveN 2 1 (λ) nN 2,φ (λ) • ln(n)(ln λ -1 ) 2 = O (ln(d)) 3 n(λ 2 d q + d -q-1 ).Denote ∆ := (ln(d)) 3 nλ 2 d q , ∆ ′ := (ln(d)) 3 d γ-q-1 , then when ∆ = o(1) or ∆ ′ = o(1), we have:N 2 1 (λ) nN 2,φ (λ)• ln(n)(ln λ -1 ) 2 → 0.Now we show that ∆ = o(1):• When p ≥ 3 and p = 2, s > 1, since γ -2ℓ + q ≥ (γ -ℓ -1) + (q + 1 -ℓ) > 0, we have ∆ = o(1).• When p = 2, s = 1, since 2ℓ -q < ℓ + 1 < 4 ≤ γ, we have ∆ = o(1).• When p = 2, s = 1, since 2ℓ -q < ℓ + 1 < 4 ≤ γ, we have ∆ = o(1).• When p = 1, γ > 2s + 1, since ℓ < 2 and hence 2ℓ -q < 3 ≤ γ, we have ∆ = o(1).• When p = 1, s > 1, γ ≤ 2s + 1, or p = 1, s = 1, γ > 2, since 2ℓ -q ≤ 2 < γ, we have ∆ = o(1).• When p = 1, s = 1, γ = 2, since 2ℓ -q ≤ 2 ≤ γ, we have ∆ = O((ln(d)) -1 ).• When p = 0, since γ -2ℓ ≥ 0, we have ∆ = O((ln(d)) -1 ). then there exists a constant ϵ > 0 only depending on s and γ, such that λ = λ(n, d) satisfiesN 1 (λ) • n ϵ-1 → 0, N 2 1 (λ) nN 2,φ (λ) • ln(n)(ln λ -1 ) 2 → 0.Proof. From Lemma 21 in Zhang et al. (2024) , we have N 1 (λ) ≍ λ -1 . Notice that we have2(τ + 1)(γ -p) ≥ ps -1 p ≥ 1 2τ 2 + (τ -1) p = 0 > 0;Therefore, there exists a constant ϵ > 0 only depending on τ , s, and γ, such that we haveN 1 (λ) • n ϵ-1 → 0.Denote q := ⌊ℓ⌋. From Lemma D.14, we further have N 2,φ (λ) = Ω d q + λ -2 d -q-1 . Hence, we haveN 2 1 (λ) nN 2,φ (λ) • ln(n)(ln λ -1 ) 2 = O (ln(d)) 3 n(λ 2 d q + d -q-1 ) = O (ln(d)) 3 nλ 2 d q + O (ln(d)) 3 d γ-q-1 .Denote ∆ := (ln(d)) 3 nλ 2 d q , ∆ ′ := (ln(d)) 3 d γ-q-1 . We have:• When p ≥ 1, since 2(τ + 1)[γ -2ℓ + q] ≥ 2(τ + 1)[(γ -ℓ -1) + (q + 1 -ℓ)] ≥ ps -2 p ≥ 2 2(τ + 1)(τ -1) + 2[τ s + s -1] p = 1 > 0,we have ∆ = o(1).• When p = 0, since γ > 1, we have ∆ ′ = o(1).Lemma D.20 (Verification of variance conditions for inner-product kernels: misspecified case). Suppose n ≍ d γ and 0 < s < 1, for γ ∈ [p(s + 1), (p + 1)(s + 1)). For any given ℓ ≥ 0, ifλ ≥    d -ℓ p ≥ 1, 2ℓ ≤ max{2p + s, γ + p(1 -s)} d -ℓ p = 0, γ > s, 2ℓ ≤ γ d -ℓ ln(d) p = 0, γ ≤ s, 2ℓ ≤ γ;then there exists a constant ϵ > 0 only depending on s and γ, such that λ = λ(n, d) satisfiesN 1 (λ) • n ϵ-1 → 0, N 2 1 (λ) nN 2,φ (λ)• ln(n)(ln λ -1 ) 2 → 0.Proof. When p ≥ 1, it is a direct result of step 2 (the verification of the second condition in (146) of Zhang et al. (2024) ) in the proof of Theorem 3 in Zhang et al. (2024) and the fact that N 2,φ (λ) ≍ N 2 (λ).When p = 0, a similar argument as the proof for Lemma D.18 give the desired results. ■ D.4.2 Verification of bias conditions Lemma D.21 (Verification of bias conditions). Suppose 1 ≤ s ≤ τ . Suppose n ≍ d γ , for γ ∈ [p(s + 1), (p + 1)(s + 1)). For any given ℓ ≥ 0, ifλ ≥    d -ℓ 1 + ln 2 (d)1{γ = 2, s = 1} p ≥ 1, 2ℓ ≤ max{2p + 1, γ -(p + 1)(s -1)} d -ℓ ln 2 (d) γ ∈ [1, s + 1), 2ℓ ≤ max{1, γ -(s -1)} d -ℓ γ ∈ (0, 1), 2ℓ ≤ γ;then there exists a constant ϵ > 0 only depending on s and γ, such that λ = λ(n, d) satisfiesEQUATIONProof. When 1 ≤ s ≤ τ , from Lemma D.14, we have q+1) , 1) , III = λd max{q(2-s),0} (ln(d)) 3 , andn M 2,φ (λ) + σ 2 n N 2,φ (λ) = Ω d γ-s(q+1) + d q N 1 (λ)M 2 1,φ (λ) n = O λ 2(s-1) d -γ+qs + λ -1 d -γ-(q+1)(s-1) N 1 (λ) ln(n)(ln λ -1 ) 2 • ∞ j=1 (λ) 2 λ i φ 2 λ (λ i ) λ + λ i f 2 i = O (ln(d)) 3 • O λd max{q(2-s),0} + λ -1 d -s(Denote I = λ 2(s-1) d -γ+qs , II = λ -1 d -γ-(q+1)(s-IV = λ -1 d -s(q+1) (ln(d)) 3 .For any p ≥ 0 and any s ≥ 1:• From Lemma D.18, we have IV ≪ d γ-s(q+1) .• When γ ≥ 1, we have γ ≥ p + 1, and hence II ≪ IV ≪ d γ-s(q+1) ; when γ < 1, we have II ≪ d q with q = 0.• When p ≥ 1 or γ ∈ (s, s + 1), since -ℓs + qs ≤ 0, we have I/d γ-s(q+1) = O(d -2(γ-ℓ-s/2) ) ≪ 1; when γ ∈ (0, s], we haveI = O(d -2sℓ+2ℓ-γ ) = O(d -2sℓ) ≪ d q with q = 0.• When s ≥ 2, we have III ≪ d q ; when s < 2 and p = 0, we have III ≪ d q ; when s < 2 and p ≥ 1 and q ≥ 1, since γ -ℓ -s > min{(s + 1)q -ℓ, ps -1/2} > 0, we have III/d γ-s(q+1) = d -(γ-ℓ-s)-2(ℓ-q) ≪ 1 or III/d q ≪ 1; when s < 2 and p ≥ 1 and q = 0, we have III ≪ d q .Combining all these, we get the desired results. ■ Lemma D.22. [Verification of bias conditions: saturation case] Suppose τ < s ≤ 2τ . Suppose n ≍ d γ , for γ ∈ [p(s + 1), (p + 1)(s + 1)). For any given ℓ ≥ 0, ifλ ≥    d -ℓ p ≥ 1, ℓ ≤ max{ℓ 1 , ℓ 2 , ℓ 3 } d -ℓ ln 2 (d) γ ∈ [1, s + 1), ℓ ≤ max{ℓ 1 , ℓ 2 , ℓ 3 } d -ℓ γ ∈ (0, 1), 2ℓ ≤ γ,where τ , ∆, ℓ 1 , ℓ 2 , and ℓ 3 are given in Lemma D.16; then there exists a constant ϵ > 0 only depending on s and γ, such that λ = λ(n, d) satisfiesEQUATIONProof. When τ < s ≤ 2τ , from Lemma D.14, we have q+1) .n M 2,φ (λ) + σ 2 n N 2,φ (λ) = Ω λ 2τ d q(2τ -s) + d γ-s(q+1) + d q N 1 (λ)M 2 1,φ (λ) n = O λ 2(τ -1) d -γ+q(2τ -s) + λ -1 d -γ-(q+1)(s-1) N 1 (λ) ln(n)(ln λ -1 ) 2 • ∞ j=1 (λ) 2 λ i φ 2 λ (λ i ) λ + λ i f 2 i = O (ln(d)) 3 • O λd max{q(2-s),0} + λ -1 d -s(Denote I ′ = λ 2(τ -1) d -γ+q(2τ -s) , II = λ -1 d -γ-(q+1)(s-1) , III = λd max{q(2-s),0} (ln(d)) 3 , andIV = λ -1 d -s(q+1) (ln(d)) 3 .For any p ≥ 0 and any 1 ≤ τ < s ≤ 2τ :• From Lemma D.18 and Lemma D.19, since N 1 (λ) • n ϵ-1 → 0, we have IV ≪ d γ-s(q+1) .• When γ ≥ 1, we have γ ≥ p + 1, and hence II ≪ IV ≪ d γ-s(q+1) ; when γ < 1, we have II ≪ d q with q = 0.• When p ≥ 1, since -ℓτ + qτ ≤ 0 andγ -ℓ -s/2 ≥ max s(2p -1) 2 , (2τ + 1)(τ + ps) -(τ + 1)s + ps -1 2(τ + 1 , ps + s(τ + 1) 2τ -1 > 0,we have I ′ /d γ-s(q+1) ≪ 1; when p = 0, we haveI ′ = O(d -2τ ℓ+2ℓ-γ ) ≪ d q with q = 0. • When γ -p -ps ∈ [0, τ ] ∪ [s + s/τ -1, s + 1],we have ℓ ≤ max{ℓ 1 , ℓ 3 }. Similar to the proof in Lemma D.21, we can show that III ≪ d γ-s(q+1) + d q .• Finally, consider the case γ -p -ps ∈ [τ, s + s/τ -1]. When s ≥ 2, we have III ≪ d q ; when s < 2, since s > 1, we have III/d q = λd -q(s-1) ≪ 0.Combining all these, we get the desired results. ■ Lemma D.23 (Verification of bias conditions: misspecified case). Suppose 0 < s < 1. Suppose n ≍ d γ , for γ ∈ [p(s + 1), (p + 1)(s + 1)). Suppose one of the following holds:(1) τ = ∞.(2) s > 1/(2τ ),(3) γ > ((2τ + 1)s)/(2τ (1 + s)).Suppose one of the following cases holds for λ = d -ℓ or λ = d -ℓ (ln(d)) 2 :(1) τ = ∞, p(s + 1) ≤ γ ≤ ps + p + s, ℓ ∈ [p, p + min{1/2, γs}] (2) τ = ∞, ps + p + s < γ < ps + p + s + 1, ℓ ∈ [p, min{(γ -(p + 1)(s -1))/2, γ(1 + s) -s(p + 1)}] (3) τ < ∞, p(s + 1) ≤ γ ≤ ps + p + s, ℓ = (γ + 2τ p -sp -p)/(2τ ) (4) τ < ∞, ps + p + s < γ < ps + p + s + 1, ℓ = p + s/(2τ ).then there exists a constant ϵ > 0 only depending on s and γ, such that λ = λ(n, d) satisfiesN 1 (λ) n ln(n)(ln λ -1 ) 2 • ∞ j=1 λ 2 λ i φ 2 λ (λ i ) λ + λ i f 2 i ≪ M 2,φ (λ) + σ 2 n N 2,φ (λ) ; n -2 N 1 (λ) ∥f λ ∥ L ∞ + n 1-s 2 +ϵ 2 = o M 2,φ (λ) + σ 2 n N 2,φ (λ) .Proof. When 0 < s < 1, from Lemma D.14, we haven M 2,φ (λ) + σ 2 n N 2,φ (λ) = Ω d γ-s(p+1) + d p n -1 N 1 (λ)n 1-s = O λ -1 d -γs N 1 (λ) ln(n)(ln λ -1 ) 2 • ∞ j=1 (λ) 2 λ i φ 2 λ (λ i ) λ + λ i f 2 i = O (ln(d)) 3 • O λd max{p(2-s),0} + λ -1 d -s(p+1) ,and the convergence rate of ∥f λ ∥ L ∞ can be attained similar to Lemma 25 in Zhang et al. (2024) . Since τ ≥ 1, similar to the proof of Theorem 3 of Zhang et al. (2024) , when 1/2 < s < 1, we haven -2 N 1 (λ) ∥f λ ∥ L ∞ + n 1-s 2 +ϵ 2 = o M 2,φ (λ) + σ 2 n N 2,φ (λ) ,and when s ≤ 1/2, we haven -2 N 1 (λ) ∥f λ ∥ 2 L ∞ = o M 2,φ (λ) + σ 2 n N 2,φ (λ) . Denote I = λ -1 d -γs , II = λd p(2-s) (ln(d)) 3 , and III = λ -1 d -s(p+1) (ln(d)) 3 .For any p ≥ 0 and any 0 < s < 1:• From Lemma D.20, we have III ≪ d γ-s(p+1) ,• When γ ≤ ps + p + s, we can show I ≪ d p when: (1) p ≥ 1, or (2) p = 0 and s > 1/(2τ ) > 0, or (3) τ = ∞,• When γ > ps + p + s, we can showI ≪ d γ-s(p+1) holds if and only if τ = ∞ or γ > (2τ + 1)s + 2τ (1 + s)p 2τ (1 + s) , τ = τ < ∞;and the above inequality holds when (1) p > 0 or (2) p = 0, s > 1/(2τ ) > 0, or (3) p = 0, γ > ((2τ + 1)s)/(2τ (1 + s));• When γ ≤ ps + p + s, since ℓ ≥ p > p -ps, we have II ≪ d p ;• When γ > ps + p + s, since ℓ ≥ p > p -ps, we have II ≪ d γ-s(p+1) .Combining all these, we get the desired results. ■ D.5 Final proof of Theorem 4.1 and Theorem 4.2For each case, the proof can be done in the following steps:(i) When λ ≥ λ ⋆ and s ≤ 2τ , where the definition of the balanced parameter λ ⋆ can be found in Corollary D.15 and Corollary D.16, we haveM 2,φ (λ ⋆ ) + σ 2 n N 2,φ (λ ⋆ ) = Θ P d -β ⋆ • poly (ln(d)) M 2,φ (λ) + σ 2 n N 2,φ (λ) = Θ P d -β • poly (ln(d)) ,where d -β ⋆ is the desired convergence rate given in Theorem 4.1 or Theorem 4.2 and β ≤ β * . Similarly, when s > 2τ , by taking s = 2τ in Corollary D.16, we also have .14, Lemma D.18, Lemma D.19, Lemma D.20, Lemma D.21, Lemma D.22, and Lemma D.23 , we know that conditions in Theorem D.5, Theorem D.9, and Theorem D.10 are satisfied. Therefore, we haveM 2,φ (λ ⋆ ) + σ 2 n N 2,φ (λ ⋆ ) = Θ P d -β ⋆ • poly (ln(d)) M 2,φ (λ) + σ 2 n N 2,φ (λ) = Θ P d -β • poly (ln(d)) . (ii) When λ ≥ λ ⋆ , from Lemma DE fλ ⋆ -f ⋆ 2 L 2 X = Θ P d -β ⋆ • poly (ln(d)) E fλ -f ⋆ 2 L 2 X = Θ P d -β • poly (ln(d)) .(iii) Finally, when s > τ , we can further show that: the convergence rates of the generalization error can not be faster than above for any choice of regularization parameter λ = λ(d, n) → 0. Notice that, when s ≥ 1, for any λ < λ ⋆ , from the monotonicity of Var(λ) (see, e.g., Li et al. (2024) ; Zhang et al. ( 2024)), we haveE fλ -f ⋆ 2 L 2 X ≥ Var(λ) ≥ Var(λ ⋆ ) ≍ E fλ ⋆ -f ⋆ 2 L 2 X ,and henceE fλ -f ⋆ 2 L 2 X = Ω P d -β ⋆ • poly (ln(d)).Proposition E.1. For any analytic filter function φ λ , we have (z + λ)φ λ (z) ≤ 4 and (z + λ)ψ λ (z) ≤ 4λ.Proof. From (28), we have (z + λ)φ λ (z) ≤ 2 max{z, λ}φ λ (z) ≤ 2 max{1, C 4 } ≤ 4. From (z s ψ 2 λ (z) ≤ C 2 2 κ 2(s-2τ ) λ 2τ .Proof. For any z, we haveψ λ (z) ≤ C 2 (z/λ) -τ 1{z > λ} + 1{z ≤ λ} ≤ C 2 (z/λ) -τ , hence z s ψ 2 λ (z) ≤ C 2 2 z s z -2τ λ 2τ ≤ C 2 2 κ 2(s-2τ ) λ 2τ . ■ E.σ(f (A)) = {f (λ) | λ ∈ σ(A)} .(111)Consequently, ∥f (A)∥ = sup λ∈σ(A) |f (λ)| ≤ ∥f ∥ ∞ . 


Decision: A very solid contribution on the saturation effect of spectral learning algorithms in high dimension (dimension grows as a power of the sample size), a setting that has generated a lot of attention and investigation in recent years, while the saturation effect had only been studied in fixed dimension. The concern of possibly only technically incremental results with respect to previous work raised by one reviewer has been answered convincingly by the authors in the discussion, pointing out novelties in results and techniques used. All reviews lauded the paper for its quality of writing and presentation.

Reviews: review: paper_summary: paper_summary: ### Summary:

 

The authors study  the saturation of spectral algorithms (KRR & GF) in high-dimensions where $n,d$ are both large,  meaning that when KRR can't achieve information theoretic lower bounds with over smooth the regression functions while kernel Gradient Flow (GF) can. 
Theorem 3.1 states the optimal convergence rate of kernel GF which matches the provided minimax lower bound in Theorem 3.3. Moreover, they find that KRR is unableto achieve this lower bound (being suboptimal) for interpolation spaces with $s >1$.
strength_weakness: strength_weakness: ### Cons:
 
 - the main results of this paper are stated on page 7, the presentation of the results is  slow
questions: questions: This is an interesting paper about the saturation of KRR in high dimensions. The authors provide several new results and the paper is well written and organized.

- line 200 -- what does $f_\star$ mean? It is only defined in the next page.
limitations: limitations: N/A
paper_summary: paper_summary: In a large-dimension setting, i.e., the dimension $d$ of the input grows polynomially with respect to the sample size $n$, this manuscript rigorously proves upper and lower bounds for spectral algorithms and shows the dependence on the qualification and the interpolation index. Consequently, the manuscript proves the saturation effect in spectral algorithms for large-dimensional data.
strength_weakness: strength_weakness: 1. By checking previous work [1,2] and the proofs in these works, it looks like Theorem 3.1 has been established in Section 4 of [1], while Theorem 4.1 and Theorem 4.2 are the direct extensions of partial results in Theorem 2 and Theorem 3 from [2]. For instance, the proofs of Theorems 4.1 and 4.2 are obtained by replacing the Tikhonov regularized filter function in the variance and bias decomposition of [2] with a general filter function satisfying specific conditions such as C1 and C2. Such a proof trick has been used in previous extend from KRR (Tikhonov regularization) to general spectral algorithms, i.e., [3] to [4]. 
   
   However, unlike the extension from [3] to [4], the current manuscript seems to be a partial extension of [2] with a similar proof trick as I mentioned before. Therefore, I have concerns about the technical contribution and novelty of this manuscript as a submission to a conference. This work seems more like an extension to a journal like JMLR, etc.
   
   I am just not sure whether such a partial extension of a previous article with almost the same proof technique is suitable for conference publication or whether it would be better evaluated in a journal. I defer this justification to the AC. Please disregard this comment if the AC deems the current context appropriate for conference publication.

2. I noticed there are some simulation experiments to confirm the saturation effect in fixed dimension KRR; see [5]. Is it possible to confirm the results in this manuscript? I understand given the rates are asymptotic, it might be hard to have thorough investigations due to the extremely large $d$. But I'm still curious if any preliminary experiments can be done. 


[1] Lu, Weihao, et al. "Optimal rate of kernel regression in large dimensions." _arXiv preprint arXiv:2309.04268_ (2023).

[2] Zhang, Haobo, et al. "Optimal Rates of Kernel Ridge Regression under Source Condition in Large Dimensions." _arXiv preprint arXiv:2401.01270_ (2024).

[3] Zhang, Haobo, et al. "On the optimality of misspecified kernel ridge regression." _International Conference on Machine Learning_. PMLR, 2023.

[4] Zhang, Haobo, Yicheng Li, and Qian Lin. "On the optimality of misspecified spectral algorithms." _Journal of Machine Learning Research_ 25.188 (2024): 1-50.

[5] Li, Yicheng, Haobo Zhang, and Qian Lin. "On the Saturation Effect of Kernel Ridge Regression." International Conference on Learning Representations. (2024)
questions: questions: 1. I'm curious to know if it is possible to conduct a similar analysis under ultra-high-dimension settings like the dimension grows exponentially fast as the sample size $d = \exp\{n^{\gamma}\}$. Do we need additional techniques to conduct these analyses?
2. Based on the figure, it looks like even when $s> 2\tau$, as long as $d$ grows with $n$, the saturation effect will not happen, which is different from the fixed dimension setting. While this may be the consequence of the derived rate, can authors provide some intuition behind this?
3. Is there a particular reason that the authors concern $\gamma \in p(s+1),(p+1)(s+1))$ with $p$ as integer to derive the rates? Why is this ratio an integer?
limitations: limitations: Yes.
paper_summary: paper_summary: This paper concerns the convergence rate of spectral methods, particularly kernel ridge regression (KRR) and kernel gradient flow (KGF), in large-dimensional settings where the sample size $n$ is of the same magnitude as a power $\gamma$ of the input dimension $ d $, i.e., $ n \asymp d^\gamma $. It reveals a new phenomenon of the saturation effect in large dimensions, which is different from its fixed-dimensional counterpart. Specifically, it shows that in large dimensions, KRR still suffers from the saturation effect while KGF does not. The key techniques involve the use of analytic filter functions to characterize the regressors from different spectral algorithms, followed by standard concentration results on the bias-variance decomposition of the excess risk.
strength_weakness: strength_weakness: There is no major weakness spotted in this paper.
questions: questions: I appreciate the result of this paper and hence look for any possible extension from the current result.

This paper focuses on dot-product kernels $K=\Phi(\langle \cdot, \cdot \rangle)$ with inputs distributed uniformly on a hypersphere and with polynomial spectral decay. 

1. By [Belkin2018] and [Haas2024], it simply seems the function $\Phi$ cannot be smooth but at least 1-differentiable, say $\Phi$ is induced by the ReLU-NTK. If $\Phi$ is smooth, for example $K$ is the Gaussian kernel, then the spectral decay is exponential. Can the result in this paper extend to this case? If yes, where is the adaptation? If no or not obvious, what would be the main technical difficulties?

2. In realistic setting, uniform input distribution on a hypersphere is too restrictive. Could one relax the condition to the distributions which have support on the whole sphere instead? I recall Lemma Lemma F.9 in [Haas2024] stating the spectral decay is still polynomial in this case. Could one extend the analysis in this case?

Also, I have some technical questions concerning the appendix.

3. In Eq (62) in Lemma D.7, the left hand side (LHS) should be independent to the noise, but why is there a term with $\sigma^2$ on the right hand side (RHS)?

4. Less like a question but more like a comment: I think that there is a typo in Eq (42): it should be $... \phi\_j^2(x)\leq ...$ instead of $... \phi\_i^2(x)\leq ...$. Also, is Eq (44) actually redundant as a special case of Eq (43) given the notation mentioned in line 602 - 603?

Reference:
- Haas, Moritz, et al. "Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension." Advances in Neural Information Processing Systems 36 (2024).
- Belkin, Mikhail. "Approximation beats concentration? An approximation view on inference with smooth radial kernels." Conference On Learning Theory. PMLR, 2018.
limitations: limitations: All assumptions and conditions are stated clearly in the paper.

Comments: comment: We are pleased that you recognize the technical contributions of our paper and the additional experiments we conducted. We will follow your suggestion to include these experiments in the updated manuscript. Thank you for raising your score.
I appreciate the detailed response and explanation that confirms the technical contribution of this paper. Also, thanks for the additional experiments that enhanced the content of the manuscript.

I have adjusted my rating, good luck!
Thank you as well! We are pleased that the changes you suggested have enhanced the clarity and presentation of our work. We sincerely appreciate your positive assessment of our paper.
Thank you! I appreciate the authors' response. It is really helpful to have such non-rigorous versions of the results earlier in the paper, and I'm happy that the authors included this to improve the presentation of their draft. I continue supporting this paper so I keep my score positive.
Thank you very much for your positive feedback. We are pleased that you find the results valid in high dimensions. Your support and recommendation to accept the paper are greatly appreciated.
Thank you very much for your detailed response. I am content to see that the results are valid for various kernels in high-dimensional setting. I would lean to accept this paper.