On the Saturation Effects of Spectral Algorithms in Large Dimensions
Authors: Weihao Lu
Haobo Zhang
Yicheng Li
Qian Lin
Venue: NeurIPS 2024 poster (2024)
Keywords: reproducing kernel Hilbert space
spectral algorithm
high-dimensional statistics
minimax rates
Primary area: learning_theory
TL;DR: We fully depict the saturation effects of spectral algorithms and reveal a new phenomenon in large dimensional settings.

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

On the Saturation Effects of Spectral Algorithms in Large Dimensions
Weihao Lu
Haobo Zhang
Department of Statistics and Data Science Tsinghua University Beijing, China 100084
Department of Statistics and Data Science
Tsinghua University Beijing, China 100084
1ush190mails tsinghua, edu. cn
zhang-hb21 @mails...mmmmmmmmmmmmmmmmmmmllll tsinghua...... edu. cn
Yicheng Li
Qian Lin"
Department of Statistics and Data Science Tsinghua University Beijing, China 100084
Department of Statisties and Data Science
Tsinghua University Beijing, China 100084
liyc220mails, www.sssssstnntt..ee edu. en
qianlin@tsinghua edu. on
Abstract
The saturation effects, which originally refer to the fact that kernel ridge regression (KRR) fails achieve the information-theoretion sion 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 X d?, More precisely, we first propose an improved minimax lower bound for the kernel regres- sion 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 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 r's. In particular, we find that these exact rate curves (varying along 7) exhibit the periodic plateau behavior and the polynomial approximation barrier. Consequently, we can fully depict the saturation effects of the spectral algorithms and reveal new phenomenon large dimensional settings (i.c., the saturation effect occurs in large dimensional setting as long as the source condition > T while it occurs in fixed dimensional setting long 2T).
lower bound when the regres-
Introduction
Let's assume we have n i.i.d. samples (I;, V:) from a joint distribution supported on Id. x R. The regression problem, one of the most fundamental problems in statistics, aims to find a function based on these samples such that the excess risk, |l f= = E, ( ((x)) is small, where fx) E|Y[ar] [x]] is the regression function. Many non- par-metriae 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.
"Coresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Spectral algorithms, as classical topic, have been studied since the 1990s. Early works treated certain types of spectral algorithms in their theoretical analysis (Caponnetio (2006); Caponnetto and De Vito (207)); Raskutti et al. 22044); Lin et al.] 2020)). These works often consider d as fixed constant and impose the polynomial eigenvalue decay assumption under kernel (i.e., there exist constants 0 < с S C < oc, such that the eigenvalues of the kernel satisfy cj I > S Cj- j 2 1 depending on the fixed d). They further assume that f. belongs to the reproducing kernel Hilbert space (RKHS) H. associated with the kernll. Under the above assumptions, they then showed that the minimax rate of the excess risk of regression over the corresponding RKHS lower bounded by n -B/(++1) and that some (regularized) spectral algorithmss, e.g., the kernel ridge regression (KRR) and the kernel gradient flow, can produce estimators achieving this minimax optimal rate.
for certain
However, subsequent studies have revealed that when higher regularity (or smoothness) of fa is assumed, KRR fails to achieve the information-theoretiinn kernel gradient flow can do so. Specifically, let's assume that f. belongs to the interpolation space [H1]* of the RKHS H. with s > (see, e.g., Steinwart et al. (2009); Dieuleveut et al. (2017): Dicker et al. (2017); [Pillaud- Vivien et al. (2018); ; Lin et al. (2220) Fischer and Steinwart (2020): Celisse and Wahl (202T)) It is then shown that the information
lower bound on the excess risk, while
coemmatioo-thooretice.. theoretical lower bound on the excess risk is (1111 When 0 < S 2. |Caponnetto and De Vito (2007); Yao et al. (2007); Lin et al.
(2020); ; /hhng et al. (2023) have already shown that the upper bound of the excess risks of both KRR and the kernel gradient flow is -+/((=++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 $37 (=; while the best upper bound of the excess risks of KRR is n -228/(28+1) CCpponnetto and De Vito (2007)) Bauer et al. 2007 : Gerfo et al. (2008 Dicker et al.
(0177)
conjectured that the convergence rate of KRR is bounded below by n 2D (2)(2 and et al.
2022 rigorously proved it. The above phenomenon is often referred to the saturation effect of
KRR:
KRR is inferior to certain spectral algorithms, such as kernel gradient flow, when $ >>> 2.
In recent years, neural network methods have gained tremendous success in many dinge-dimensionll problems, such as computer vision He 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 karge-dimensional data from the aspects of "lazy regime" (Arora al. (2019): Du
et al. 20199 2018); Li and Liang (2018)). They noticed that, when the width of neural network is 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. (202T); (Suh et al. (202T); Lai et al. (203); [i 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'.
sufficienlly large, its parameters/weigeeeeeee
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
al. (2020 202T :: Mei et al. [022 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 = I. Then, Zhang et al. (024)) provided upper and lower bounds on the convergence rate on the excess risk of KRR for any O. Surprisingly, they discovered that for > 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 '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.
If Zhang et al. 2024)* 's conjecture is true, then we can safely conclude that: when the regression function /. is smooth enough, KRR inferior to kernel gradient flow in large dimensions as well. Consequently, previous results on large-dimensional KRR may not be directly extendable to large-

---

dimensional neural networks, even if the neural networks are in the 'layy regime'. The main focus of this paper prove this conjecture by showing that kernel gradient flow minimax optimal in large dimensions.
1.1 Related work
Saturation effects of exee-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 [. [H] with 8 2. It is shown that: (i) the minimax
optimal rate is 20/lap+>
(Rastogi and Sampath 2017); Yao et al.
2007); Lin al. (2200));
and (ii) the convergence rate on the excess risk of KRR is 20/(24+))
(Li et al. (2022)) ). More
recently, 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 r (see, e.g. Appendix C : suppose S+ E [H] with 8 > 2r, then the convergence rate on
the excess risk of the above spectral algorithms is n -2
New phenomena in large-dimensional spectral algorithms. In the large-dimensional setting where n x d' with y > 0, new phenomena exhibited in spectral algorithms are popular topics in recent muachine-learning research. A line of work focused the polynomial approximation barrier phenomenon B......Goorbai et al. (202T); Donhauser et al. (202I): Mei et al. (2022); )); Xiao
et al. 2023); MMisakieewizz 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 polynomial with low degree. Another line of work considered the benign overfitting of
kernel interpolation (i.e., kerne interpolation can generalize) (c.g., Liang and Rakhlin (020)): Liang
al. 2200 Aerni al. (2023); Barzilai and Shamir (2023); [hhng 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 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 of the optimal excess risk has constant values when is within certain intervals. Finally, ZZang 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 to provide unified explanation of these new phenomena.
1.2 Our contributions
In this paper, we focus on the sige-dimmnsiooal spectral algorithms with inner product kernels, and we assume that the regression function falls into interpolation space [H]] with > We state our main results as follows:
Theorem 1.1 (Restate Theorem 4.1 and 4.2, non-rigorous). Let 8 > 0, 2 1, and r > be fixed real numbers. Denote p as the integer satisfying E [p(s + 1), (p 1)(s 1)). Then under certain conditions, the excess risk of large-dimensional spectral algorithm with qualification T satisfies
E (16--
x) =
O= (d min(7- Op (d min (d-imnt
-poly (In(d),, SST
- S.
rir e s(pt1))) poll (In(d)), 8 T,
where $ = min(s. 2T
More specifically, we list the main contributions of this paper follows:
(I) In Theorem 3.1 we show that the convergence rate on the excess risk of (optimally-tuned) kernel gradient flow in large dimensions is Oz(dd min(1-p..(7++ 1)) poly(In which matches the lower bound on the minimax rate given in Theorem B.3 (up to logarithmic factor). We find that kernel gradient flow minimax optimal for any s >> 0 and any > > 0, and KRR is not minimax optimal for > 1 and for certain ranges of (We provide visual illustration Figure 2 Consequently, we rigorously prove that the saturation effect of KRR occurs in large dimensions.
3

---

(2) In Theorem 3.3
we enhanced the previous minimax lower bound results given in Lu et al. (023) and Zhang et (2024). Specifically, we show that the minimax lower bound is (ol)y(l((d)) In comparison, the previous minimax lower bound is Odd (td=mmi(--ppe(et)) / for any ε O, and the additional term de changes the desired
(dd Didd-mul(y p.s.pp p.sppltpt-p
convergence rate.
(3) In Section 4 we determine the convergence rate on the excess risk large-dimensional spectral algorithms. From our results, we find several new phenomena exhibited in spectral algorithms in large-dimensions, settings. We provide a visual illustration of the above phenomena in Figure i) The first phenomenon is the polynomial approximation barrier, and as shown in Figure [(a) when s is close to zero, the curve of the convergence rate of spectral algorithm drops when Y = p for any integer p and will stay invariant for most of the other y ii) The second one is the periodic plateau behavior, and as shown in Figure ((b) and Figure ((e) when 0 < 8 < 27 and y [p(s -1 s+ (max T} -T//T, (p++ () 1)) for an integer 2 O, the convergence rate does not change when 7 varies; iii) The final one is the saturation effect, and as shown in Figure [[c] and Figure I(d) when s T, the convergence rate of spectral algorithm can not achieve the minimax lower bound for certain
ranges of y. A detailed discussion about the above three phenomena can be found in Section
Dican nANe
(b)
(c)
(d)
Figure 1: Convergence rates of spectral algorithm with qualification T = 2 in Theorem 4.1 Theorem
and corresponding minimax lower rates Theorem 3.3 with respect to dimension d. We present four graphs corresponding to four kinds of source conditions: s = 0.01, 1, 5. The x-axis represents asymptotic scaling, 7 n x d";; the y-axis represents the convergence rate of excess risk, Excess risk x d'.
2 Preliminaries
Suppose that we have observed n i.i.d. samples (I; Ut), i e [r]] from the model:
fx) +
(I)
where 's are sampled from px, Px is the marginal distribution on X c RRd+1 E C RR, fs some function defined compact set X, and
Px-ace x X [22 x S0²
E (xzy))~
for some fixed constant a >> O, where p is the joint distribution of (z, y) on X x y. Denote the n x 1 data vector of y 's and the d data matrix of x; 'ss by Y and X respectively.
2.1 Kernel ridge regression and kernel gradient flow
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 X IR and there exists constant satisfying
max K (x, x) < x x

---

Kernel ridge regression Kernel ridge regression (KRR) constructs an estimator 2RRR by solving the penalized least square problem
arg min JEH
y
(x+)) + Al1f1
72
where > referred to as the regularization parameter. The representer theorem (see, e.g.. Steinwart and Christmann (2008)) gives explicit expression of the KRR estimator, i.c.,
PERR
x = (x, () + +nAI)
(2)
Kernel gradient flow The gradient flow of the loss function C gradient flow in H which is given by
2n E, fxx))² induced
dt fth (x) = -- Kx= (){ (x)-Y) Y).
n
we further assume that jar (x) = 0, then we can also give an explicit expression of the kernel gradient flow estimator
AGP (z) = ( -
(4)
2.2 The interpolation space
Define the integral operator Tк as (x) / dpx(x'). Is well known that Tk is a positive, self-adjoint, trace-class, and hence a compact operator (Steinwart and Scovel (2012)). The celebrated Mercer's theorem further assures that
K(x, x²) Σ, (,0)(=)00
(5)
where the eigenvalues {Ag.j 1.., is non-increasing sequence, and the corresponding cigenfunctions {o,(-),} 1, 1,2, ...} are orthonormal in L2XXX function space.
The interpolation space [H] with source condition is defined
[|] = E, a,5gg' by (a,), E 22) C px),
(6)
with the inner product deduced from
2 Σ j=1
1/2
2, 03
2
It is easy to show that [H]* is also separable Hilbert space with orthonormal basis (2//2 33 Generally speaking, functions in [H] become smoother increases (see, e.g., the example of Sobolev RKHS Edmunds and Triebel (1966); Zhang et al. (2023).
2.3 Assumptions
In this subsection, list the assumptions that we need for main results.
To avoid potential confusion, we specify the following large-dimensional scenario for kernel regres- sion where we perform our analysis: suppose that there exist three positive constants C1, and such that
cnd S n S c2d"
and 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 kernel function K defined gd such that there exists function + [-1, + R independent of d satisfying that for any x' sd. we have K K(x, 2²) = (((z,=')). If we further
5

---

assume that the marginal distribution Px is the uniform distribution on X' = S then the Mercer's decomposition for K can be rewritten as
N(d.k)
K(x,x') Σ μE Σ
(k.( (z))
where Yk.j for j -, .d k) are spherical harmonic polynomials of degree it and μu 's are the eigenvalues of K with multiplicity N(d, 0) = 1; (dd, k.) 2k+d-1 (k+d-2))
(d-n k 1, ....
For more details of the inner product kernels, readers refer to Gallier (2009).
Remark 2.1. We consider the inner product kernels 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 '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 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 only determined for the spheres. Restricted by this technical reason, most works analyzing the spectral algorithm in large- srnge-dimessionall settings focus on the inner product kernels on spheres (Liang al., 2020 Ghorbani 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 near-spherical assumption; (ii) adopted strong assumptions on the regression function, e.g., f. (a) ==1|=[[]- .... x z[L] for an integer L > 0, where a[i] denotes the i-th component of 2; or (iii) can not determine the convergence rate on the excess risk 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]) fixed function independent of and there exists a non- negative sequence of absolute constants {az 2 0bj20, such that we have
(t) Σ j=0 asti,
where aj 0 for any by] 3.
The purpose of Assumption ! to keep the main results and proof's clean. Notice that, by Theorem 1.b in [Gneiting 20133) the inner product kernel K on the sphere is semi-positive definite for all dimensions if and only if all coefficients {aj. = 0, 1, ...} are non-negative. One can easily extend our results in this paper when certain coefficients 0g 's are zero (e.g., one can consider the two-layer NTK defined in Section 5 of Lu et al. (202)), with a, 0 for any 3, ..
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.) = - f.)((z).
(a) f. E [H]* for some 0, and there exists constant R.y only depending on 7, such that I || S R.y.
(10)
(b) Denote g as the smallest integer such that q >> y and f2 # O. Define IJ the index set satisfying A = pk, E Ta,k- Further suppose that there exists an absolute constant co > such that for any d and & E 10,1, .4) with Mk # 0, we have
E Me f 2 cu-
(11)
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), Eq.(8)
in Cui et al. 202T), Assumption 3 in Li et al. (2024). and Assumption 5 in Zhang et al. (2024)
Assumption implies that the regression function exactly falls into the interpolation space H 8 that
is, f. E [H] and f. & [H]' for any t For example, from the proof part I of Lemma
D.14 one
can check that f. with EiEIa, Up f2 = Eietepm M 0 can have a faster convergence rate
on the excess risk.

---

Notations. Let's denote the norm in L2(x,px) as || 11,.. For a vector H, we use x/i] to de- note its i-th component. We use asymptotic notations O(-), o(), ((-) and ( For instance. we say two (deterministic) quantities (d), V(d) satisfy U(d) = (d))) if and only if for any & > 0, there exists a constant D. that only depends on e and the absolute positive constants Ki, 8; 7, Co, C2, E,,-.. Es
> 0, such that for any d > De. we have (d) < <d)... We also
write O₂ poly(b,)) if there exist a constant 0 2 0, such that On (())). We use the probability versions of the asymptotic notations such as Op(+). (p(+), (p)(), Op(-). For instance, we say the random variables Xn, Yn satisfying Xn Op(Yn) if and only if for any > O, there exist constants C₂ and N₂ such that P ([x,, 2 YY I E, Vn N₂.
2.4 Review of the previous results
The following two results are restatements of Theorem 2 and Theorem 5 in Zhang et al. (2024).
Proposition 2.2. Let 8 2 and > be fixed real numbers. Denote p as the integer satisfying
Y E [p(s + 1), 1)(s + 1)). Suppose that Assumption Aand Assumption 2 hold for and 7. Let
EEAR be the function defined in (2). Define 5 = min(s, 2}. then there exists X > 0, such that we have
E
PXRR 1
f. 1|
x)= OF (d min ( m M6ot1)) poly (In(d))
V Co. K, and In addition, the convergence rates of the generalization evvor can not be faster than above for any choice of regularization parameter X = Mdd + O.
where Op only involves constants depending on 8, o,
Proposition 2.3 (Lower bound on the minimax rate). Let > O and y > O be fixed real numbers. Denote p as the integer satisfying y E 1): () 1)). Let P consist of all the distributions on X x y such that Assumption [ and Assumption 2 hoold and Then for any >> O, we have:
|| 1-
Ω (d miult--p.(ptt))) .ddc)d)) dd)
PEP min max (X,Y)~
where Ω only involves constants depending s, 0, Y: Co K, C12 and E.
From the above two propositions, we can find that when & > 1, the convergence rate on the excess risk of KRR does not always match the lower bound on the minimax optimal rate. (Zhang al. (2024) further conjectured that the lower bound on the minimax optimal rate provided in Proposition 2.3 is tight (ignoring the additional term 5) Hence, they believed that the saturation effect exists for large- mige-dimensional KRR.
3 Main results
In this section, we determine the convergence rate on the excess risk of kernel gradient flow as d= mui(t--.-ipp-);; poly (In(d)), which differs from the lower bound on the minimax rate provided in Proposition 2.3 by d' for any > O. We then tighten the lower bound on the minimax rate to d- p..map-p..tttt)) /poly (In(d). Based on the above results, we find that KRR is not minimax optimal for and for certain ranges of y. Therefore, we show that the saturation effect of KRR occurs in large dimensions.
3.1 Exact convergence rate on the excess risk of kernel gradient flow
We first state our main results in this paper.
Theorem 3.1 (Kernel gradient flow). Let >> 0 and 7 0 be fixed real numbers. Denote p as the integer satisfying 7 E [p(s + 1), (p + 1)(s + 1)). Suppose that Assumption] 7 and Assumption hold for and 7. Let fcF be the function defined in ④ Then there exists t" > 0, such that we have
E
for - fa
X
(d-
O:
(d-min(r--naall ((-min((-nnno0-1)))) poly (In(d)),
(12)
where O₂ only involves constants depending on s, o, 7, Co, K, and oz.
7

---

Theorem 3.1 is 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 > 0 and any 7 > 0. More importantly, the convergence rate of kernel gradient flow faster than that of KRR given in Proposition 2.2 when (i) 1 < 8 S 2 and E (p(s +1 + 1, p(s (s + 1) + 2s 1) for some p E N, or (ii) s > 2 and 7 E (p(s + 1) + 1, (p + () + 1)) for some p E N. Therefore, we have proved the saturation effect of KRR in large dimensions.
Remark 3.2. When p 2 1, the logarithm term (oly(In(d)) in 12 can be removed. When p 0, have (oly(In(d)) = (In (2) in 12). See Appendix D.4 for details.
3.2 Improved minimax lower bound
Recall that Proposition 2.3 gave lower bound on the minimax rate as d= minmm>-n.e(+1)) d==., - The following theorem replaces the additional term d= (which has changed the convergence rate) into logarithm term poly (In(d)) (which does not change the desired convergence rate).
Theorem 3.3 (Improved minimax lower bound). Let s >> O and ry >> O be fixed real numbers. Denote p as the integer satisfying 7 E (p(s + 1): (p + (s + 1)). Lei P consist of all the distributions on X' x y such that Assumption and Assumption 2 hold for and y. Then we have;
min max (xx f PEP
-
Ω min()
poly (In(d)),
(13)
where Qt only involves constants depending 8, 0, 7, Co, N; C12 and c2.
4 Exact convergence rate on the excess risk of spectral algorithms
In 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 7 2 1 (refer to Appendix C for the definitions of analytic filter function and its qualification), we can define spectral algorithm in the following way (see, e.g., Bauer et al. (2007)). For any E IR let K2 IR + H be given by Kz(v) y y-KK (xx, -), whose adjoint K H is given by (f) = (x f) h = f(x). Moreover, we denote by Tr K2KY and Tx Σ Tx,, We also define the sample basis function
Oz Σ 1=1 Kr, (v:) (v))= E"
R 1=1 K (x.))).
(14)
Now, the estimator of the spectral algorithm is defined by
fa 4x (Tx)92
(15)
Many commonly used spectral algorithms can 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) Appendix C proof for these examples in Lemma C.3
We provide rigorous
Example (Kernel ridge regression). The filter function of kernel ridge regression (KRR) well- known to be
XBR
==1.
(16)
+
2 ++
Example 2 (Kernel gradient flow). The filter functiin is
e- -tz
Px (2)
( -= 00.
(17)
For any analytic filter function yo with qualification 7 2 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 S т. and (ii) s > т, where
is the source condition coefficient of the regression function given in Assumption 2
8

---

Theorem 4.1. Ler < $ S and > O be fixed real numbers. Denote as the integer satisfying
Y E [p(s + (p 1)(s 1)). Suppose that Assumption [and Assumption 2 hold for and n
Let (px(2) be an analytic filter function and fx be the function defined in 15 Suppose one of the following conditions holds:
(i) 00, (ii) > 1/(2r), (ii) ((27 (2))))227((1++
then there exists X 0, such that we have
E (1 f.
x (d minl (0-mm((-=)((+t))) poly (In(d)),
where Op only involves constants depending on 8, J, Co2 K, C1 and c2-
Theorem 4.2. Let s > T and & > be fixed real numbers. Denote p as the integer satisfying E [p((s + 1), (v +)((s + 1)). Suppose that Assumption I [and Assumption hold for and 7. Let (xx(2) be an analytic filter function and fx be the function defined in (15). Define ă = min 27). then there exists X > 0, such that we have
E (11A- L2 X
1x= -0 (d (d-minff (
- ((p+))))) poly (In(d))
where Op only involves constants depending on S,0,", Co2 R, C1 and cz. In addition, the convergence rates of the generalization error not be faster than above for any choice of regularization parameter X == A(d,n) + O.
Remark 4.3. These theorems substantially generalize the results on exact generalization error bounds of analytic spectral algorithms under the fixed- diee-diieniional setting given in Li et al. (2024). Although deal with the
the "analytic functional argument" introduced in their proof is still vital for general spectral algorithms, their proof has to rely on the polynomial eigendecay assumption that \3 x -ー (Assumption I), which does not hold in large dimensions since the hidden constant factors in the assumption vary with d1 1 (Lu et al. (2023). ) Hence, their proof is not easy to generalize to large-dimensional spectral algorithms.
We provide some graphical illustrations of Theorem and Theorem in Figure (with 2) and in Appendix A (with 7 = =,, T = 2, r = 4, and DC, corresponding to KRR, iterated ridge regression in Example and kernel gradient flow).
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 S and the conditions in Theorem hold. Moreover, these results show several phenomena for large-dimensional spectral algorithms.
As direct consequence of Theorem 3.3
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 > T. As shown in Figure I(c) and Figure [[d] when s > т, no matter how carefully one tunes the regularization parameter A. the convergence rate
not be faster than d min(y-p r65 ii 1(p+1)) thus can not achieve the minimax lower bound d= min (t--pp--pp))) p))(p+1)).
Periodic plateau behavior of spectral algorithms when 8 S 2r. When 0 < < 2r and Y E [p(s + + s + max(s, //T 1, (p+ ()(s +)) for an integer p 2 0, from Theorem 4.1 and Theorem 4.2 the convergence rate on the excess risk of spectral algorithm d= The above rate does not change when y varies, which can also be found in Figure (bb and Figure BIn other words, if we fix a large dimension and increase 7 (or equivalently, increase the sample size ni,, the optimal rate of excess risk of 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 + O. From Theorem when is close zero, the convergence rate d min()=p.<(p+1)) is unchanged in the range Y E [p(s + 1) + s. (p + (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 7 exceeds p(s + 1) Rs p for any integer p and will stay invariant for most of the other 7. We term the above phenomenon as the polynomial
approximation barrier of spectral algorithms (borrowed from Ghorbani al. (20TT) )) and it can be illustrated by Figure
((a) with 0.01.

---

Remark 4.4. Ghorbani et al. (2021) discovered the polynomial approximation barrier of KRR. As shown by Figure and Theorem 4 Ghorbani et al. (202T), if 0 and the true function falls into 1,2 [ then with high probability we have
B PAR 1.113
| Sp | S se([1e112 +
2
(18)
where p is the integer satistying 7 E 1 1), X. is defined as in Theorem 4 in Ghorbani et al. (202I), P>t means the projection onto polynomials with degree > L, and is any positive real number. Notice that (18) implies that the excess risk of KRR will drop when 7 exceeds any integer and will stay invariant for other y, and is consistent with our results for spectral algorithms.
5 Conclusion
In this paper, we rigorously prove the saturation effect of KRR in large dimensions. Let and y 0 be fixed real numbers, denote p the integer satisfying 7 E [p(s + 1), (p( 1)). Given that the kernel an inner product kernel defined on the sphere and that f. falls into the interpolation space [H] we first show that the convergence rate on the excess risk of large-dimensional kernel gradient flow is Op (d- min(---..((-t)))
poly (In(d) (Theorem 3.1 b. which is faster than that of KRR given in Zhang et al. (2024). We then determine the improved minimax lower bound as Ω (d min(m minn)>-p><(++1))) /poly (In(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 aage-ddimensioal neural networks if the regression function is over-smooth.
In Section 4 we generalize our results certain spectral algorithms. We determine the convergence rate on the excess risk of large-diin -inge--dmeiiinal spectral algorithms (Theorem J. [and Theorem 4.2). From these results, 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 large- dimensional 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 al. (2024) [ al. (2024)) can indeed be extended to large-dimensional settings, although must carefully consider the constants that depend on d. Furthermore, we believe that by considering the learning curve of dine--dimesioonll 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 nine-ddimensioall kernel interpolation (i.e.. KRR with 0), further research can find a wealth of new phenomena compared with the fixed-dimensional setting.
Acknowledgments and Disclosure of Funding
Lin's research was supported in part by the National Natural Science Foundation of China (Grant 92370122, Grant 11971257). The authors are grateful to the reviewers for their constructive comments that greatly improved the quality and presentation of this paper.
References
Aemii, M., M. Milanta, K. Donhauser, and F. Yang (2023). Strong inductive biases provably prevent harmless interpolation. arXiv preprint arXiv:2301.07600
Arora, S., S. Du, W. Hu, Z. Li, and R. Wang (2019). Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332. PMLR.
Arora, S., S. S. Du, W. Hu, Z. Li, R. R. Salakhutdinov, and R. Wang (2019). On exact computation with an infinitely wide neural net. Advances in Neural Information Processing Systems 32.
Barzilai, D. and O. Shamir (2023). Generalization in kernel regression under realistic assumptions. arXiv preprint arXiv:2312.159%
10

---

Bauer, F., S. Pereverzev, and L. Rosasco (2007). On regularization algorithms in learning theory. Journal of Complexity 23(1), 52-72.
Caponnetto, A. (2006, September). Optimal rates for regularization operators in learning theory. Technical Technical Report CBCL Paper Tecnial Report #062, Massachusetts Institute of Tech- nology.
Caponnetto, A. and De Vito (2007). Optimal rates for the regularized least-squares algorithm.
Foundations of Computational Mathematics 7(3), 331-368.
Caponnetto, A. and Y. Yao (2010). Cross-validation based adaptation for regularization operators in learning theory. Analysis and Applications 8(02), 161-183.
Celisse, A. and M. Wahl (2021). Analyzing the discrepancy principle for kernelized spectral filter learning algorithms. Journal of Machine Learning Research 22(76), 1-59.
Cleveland, W. S. (1979). Robust locally weighted regression and smoothing scatterplots. Journal of the American Statistical Association 74(368), 829-836.
Cui, H.,, B. Loureiro, F. Krzakala, and L. Zdeborová (2021). Generalization error rates in kernel regression: The crossover from the noiseless to noisy regime. Advances Neural Information Processing Systems 34, 10131-10143.
Devlin, J. (2018). Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint
Dicker, L. H., D. P. Foster, and D. Hsu (2017). Kernel ridge vs. principal component regression: Mini- max bounds and the qualification of regularization operators. Electronic Journal of Statisties 1/(1), 1022 1047.
Dieuleveut, A., N. Flammarion, and F. Bach (2017). Harder, better, faster, stronger convergence rates for least-squares regression. Journal of Machine Learning Research 18(101), 1-51.
Donhauser, K., M. Wu, and F. Yang (2021). How rotational invariance common kernels prevents generalization in high dimensions. In International Conference on Machine Learning, pp. 2804- 2814. PMLR.
Du, S. J. Lee, H. Li, L. Wang, and X. Zhai (2019). Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675-1685. PMLR.
Du, S. S., X. Zhai, B. Poczos, and A. Singh (2018). Gradient descent provably optimizes over- parameterized neural networks. arXiv preprint arXiv:1810.0205:
Edmunds, D. E. and H. Triebel (1996). Function Spaces, Entropy Numbers, Differential Operators. Cambridge: Cambridge University Press.
Fischer, S. and I. Steinwart (2020). Sobolev norm learning rates for regularized least-squares algorithms. Journal of Machine Learning Research 2205), 1-38.
Gallier, J. (2009). Notes on spherical harmonics and linear representations of lie groups preprint.
Gerfo, I. I.., L. Rosasco, F. Odone, F. D. Vito, and A. Verri (2008, 07). Spectral Algorithms for Supervised Learning. Neural Computation 20(7), 1873-1897.
Ghorbani, B., S. Mci, T. Misiakiewicz, and A. Montanari (2020). When do neural networks outperform kernel methods? Advances in Neural Information Processing Systems 33, 14820- 14830.
Ghorbani, B., S. Mci. T. Misiakiewicz, and A. Montanari (2021). Linearized two-layers neural networks in high dimension. The Annals of Statistics 49(2), 1029 1054.
Ghosh, N., S. Mei, and B. (2021). The three stages of learning dynamics in high-dimensional kernel methods. arXiv preprint 27100721

---

Gneiting, T. (2013). Strictly and non-strictly positive definite functions on spheres. Bernoulli 19(4). 1327 1349.
Haas, M., D. Holzmüller, U. Luxburg, and I. Steinwart (2024). Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension. Advances Neural Information Processing Systems 36.
Hc, K., X. Zhang, S. Ren, and J. Sun (2016). Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778.
Hu, H. and Y. M. Lu (2022). Sharp asymptotics of kernel ridge regression beyond the linear regime. arXiv preprint ar arXiv:2005.06795
Hu, T., W. Wang, C. Lin, and G. Cheng (2021). Regularization matters: A nonparametric perspective overparametrized neural network. In International Conference Artificial Intelligence and Statistics, pp. 829-837. PMLR.
Jacot, A., F. Gabriel, and C. Hongler (2018). Neural tangent kernel: Convergence and generalization in neural networks. Advances in Neural Information Processing Systems 31.
Krizhevsky, A., Sutskever, and E. Hinton (2017). Imagenet classification with deep convolutional neural networks. Communications of the ACM 60(6), 84-90.
Lai, J., M. Xu, R. Chen, and Q. Lin (2023). Generalization ability of wide neural networks on I. arXiv preprint arXiv:2302.05933
Li, Y., W. Gan, Z. Shi, and Q Lin (2024). Generalization error curves for analytic spectral algorithms under power-law decay. arXiv preprint arXiv:2401.01599
Li, Y. and Y. Liang (2018). Learning overparameterized neural networks via stochastic gradient descent structured data. Advances in Neural Information Processing Systems 31.
Li, Y., Z. Yu, G. Chen, and Q. Lin (2024), On the eigenvalue decay rates of a class of neural-network related kernel functions defined general domains. Journal of Machine Learning Research 25(82), 1-47.
Li, Y., H. Zhang, and Q. Lin (2022). On the saturation effect of kernel ridge regression. In The Eleventh International Conference on Learning Representations.
Li, Y., H. Zhang, and Q. Lin (2024). On the asymptotic learning curves of kernel ridge regression under power-law decay. Advances in Neural Information Processing Systems 36.
Liang, T. and A. Rakhlin (2020). Just interpolate: Kernel "Ridgeless" regression can generalize. The Annals of Statistics 48(3), 1329 1347.
Liang, T., A. Rakhlin, and X. Zhai (2020). On the multiple descent of minimum-nonee -oom interpolants and restricted lower isometry of kernels. In Conference Learning Theory, pp. PMLR.
Lin, J., A. Rudi, L. Rosasco, and V. Cevher (2020). Optimal rates for spectral algorithms with least-squares regression over hilbert spaces. Applied and Computational Harmonic Analysis 48(3), 868-890.
Lu, W., H. Zhang, Li, M. Xu. and Q. Lin (2023). Optimal rate of kernel regression in large dimensions. arXiv preprint arXiv:2309.04226 04068.428.......
Mei, S., T. Misiakiewicz, and A. Montanari (2021). Learning with invariances in random features and kernel models. Conference on Learning Theory, pp. 3351-3418. PMLR.
Mei, S., T. Misiakiewicz, and A. Montanari (2022). Generalization enror of random feature and kernel methods: Hypercontractivity and kernel matrix concentration. Applied and Computational Harmonic Analysis 59, 3-84.
12

---

Mei, S. and A. Montanari (2022). The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathemat- ics 75(,,, 667-766.
Misiakiewicz, T. (2022). Spectrum inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression. arXiv preprint arXiv:2204.
Misiakiewicz. T. and S. Mei (2022). Learning with convolution and pooling operations in kernel methods. Advances in Neural Information Processing Systems 35, 29014-29025.
Liviin,, I.., A. Rudi, and F. Bach (2018). Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes. Advances in Neural Information Processing Systems 3/.
Raskutti, G., M. Wainwright, and B. Yu (2014). Early stopping and non non-parametric regression: An optimal data-dependent stopping rule. Journal of Machine Learning Research 15(11), 335-366.
Rastogi, A. and S. Sampath (2017). Optimal rates for the regularized learning algorithms under general source condition. Frontiers in Applied Mathematics and Statistics 3, 3.
Steinwart, I. and A. Christmann (2008). Support vector machines. Springer Science & Business Media.
Steinwart, I., D. Hush, and C. Scovel (2009). Optimal rates for regularized least squares regression. In Conference on Learning Theory, pp. 93. PMLR.
Steinwart, I. and C. Scovel (2012). Mercer's theorem on general domains: On the interaction between measures, kernels, and rkhss. Constructive Approximation 35, 363-417.
Stone, C. J. (1977). Consistent Nonparametric Regression. The Annals of Statistics 5(4), 595 620.
Stone, C. J. (1994). The Use of Polynomial Splines and Their Tensor Products in Multivariate Function Estimation. The Annals of Statistics 22(1), 118 - 171.
Suh, N., H. Ko, and X. Huo (2021). A non-parametric regression viewpoint: Generalization of overparametrized deep relu network under noisy observations. In International Conference on Learning Representations.
Xiao, I.., H. Hu, T. Misiakiewicz, Y. M. Lu, and J. Pennington (2023). Precise learning curves and higher-order scaling limits for dot product kernel regression. Journal of Statistical Mechanics: Theory and Experiment 2023(11), 114005.
Yang. Y. and A. Barron (1999). Information eeformation-thhoretie determination of minimax rates convergence. The Annaly of Statistics 27(5), 1564 1.599.
Yao, Y., L. Rosasco, and A. Caponnetto (2007). On early stopping in gradient descent learning. Constructive Approximation 26, 215-315.
Zhang, H., Li, W. Lu, and Q. Lin (2023). On the optimality of misspecified kernel ridge regression.
In International Conference on Machine Learning, pp. 41331-41353, PMLR.
Zhang, H., Y. Li. W. Lu, and Q Lin (2024). Optimal rates of kernel ridge regression under source condition in large dimensions. arXiv preprint arXiv:2401.01277
Zhang, H., W. Lu, and Q Lin (2024). The phase diagram of kernel interpolation in large dimensions. arXiv preprint 2xXiv2244.11553
13

---

A Graphical illustration and numerical experiments of main results
A.1 Graphical illustration of Theorem 3.1 Theorem 4.1, and Theorem 4.2
Recall 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 > O; (ii) large-dimensional spectral algorithm with 7 2 and 8 S T; and (iii) large-dimensional spectral algorithm with 7 2 1 and
$ >> T.
In Figure we have provided a visual illustration of Theorem 4.1 and Theorem 4.2 when T = 2. Now, in Figure we provide more visual illustrations of the results of spectral algorithms with 7 1, = 2, r 4, and T = oc, which correspond to kernel ridge regression (KRR), iterated ridge regression in Example B] and kernel gradient flow.
c-000
or ant
(a)
(b)
(c)
(d)
1-0 1m2
(f)
(h)
SCOMA
(m)
(n)
(0)
(p)
Figure 2: Convergence rates of spectral algorithms with qualification 7 -= 1 (KRR), T = 2 (iterated ridge regression), 7 = 4 (iterated ridge regression), and
(kernel gradient flow) in Theorem 4.1 Theorem 4.2 and corresponding minimax lower rates in Theorem 3.3 with respect to dimension
d. We present four graphs corresponding to four kinds of source conditions: 0,01, 1,3,5 5. The x-axis represents asymptotic scaling, n x d²: the y-axis represents the convergence rate of excess risk, Excess risk = d'
14

---

A.2 Numerical experiments
We conducted two experiments using two specific kernll:: the RBF kernel and the NTK kernel. Experiment 1 was designed to confirm the optimal rate of kernel gradient flow and KRR when 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:
R (xr, x²) =exp (- | x' 12 }}
x, x' E
2
(ii) Neural Tangent Kernel (NTK) of a two-layer ReLU neural network:
K (x, x²) (((xx x'),, x' E s",
where (t) = [sin (arccost) t) + 2(T arccos t)t (2T))
The RBF kernel satisfies Assumption [ For the NTK, the coefficients of 2(-). {a satisfy aj 0.j E f0, 1 22,4, 4, 4,6,...) and a = 0, E {3. 5, .....) (see, e.g., Lu et al. (2023). As noted after Assumption I our results can be extended to inner product kernels with certain zero coefficients aj. Specifically, for any 7 > 0, as long as aj > for j = [>]: [>] + 1, the proof and convergence rate remain the same. Therefore, for y < 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:
1/4 = fx;) + i i= 1.1,...,"
where each x; is i.i.d. sampled from the uniform distribution on s4, and et Lid ~ (O0 1).
We selected the training sample sizes with corresponding dimensions d such that = d% 7 0.5, 1.0, 1.5, 1.8. For each kernel and dimension d, we consider the following regression function f::
fa (x) = (x) + K (w2,,x) x) + K (ug, #), for some W1, U2, E Sd.
(19)
This function is in the RKHS H. and it is easy to prove that, for any the E s Assumption (b) holds for K ((ug.) with s 1. Therefore, Assumption hholds for
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 Jnd Figure 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
changed to fx) = (dgN(d, P) E, >) with = 1.9, P2(t) == (dt² - 1)/ 1) the Gegenbauer polynomial, and & E Sd. Notice that the addition formula Pa(< E, >) =
N(d22 Nd..2 Y2, (E), (x) implies that
N(d.2)
ll || = N(d,2)
Σ
(2) Pa(1) 11
hence f- E [H] and satisfies Assumption 2
Our experiment settings are similar to those on page 30 of Li et al. (002).. We choose the regulariza- tion parameter for KRR and kernel gradient flow as X 0.05 d For KRR, since Corollary 1.16 suggests that the optimal regularization parameter is À x d-0.7 we set 0 = 0.7. Similarly, based on Corollary D.1 we 0 = 0.5 for kernel gradient flow. Additionally, indicate that the best convergence rate of KRR is slower than that of kernel gradient flow, implying that KRR inferior to kernel gradient flow when the regression function is sufficiently smooth.
y 1.8. The results
B Proof of Theorem
We first restate Theorem 3.3
15

---

O.S. theretical
NTK theratical rata-.]
KRR, parameters chosen by CV
KRR, parameters chosen CV
-1.70
loquerr - -103loguh 0.37
loqudrr -0.84-0uuh 0.38
-1.5
Kernil iegresiin
Ker
-1.00
-1.0
10gge
-190
-1.95
-20
-2.0
-2.05
-21
-2.10
2.00
2.05
2.10
2.15
2.20
2.25
2.30
2.70
2.75
2.50
2.55
2.50
2.55
3.00
logos n
logto
(a)
(b)
NTK. y 15, theretical rate--203
NTK y 1.8, theretical ratem-559
log -0
1.
lng -.566lg
Karmel regression
Kernel regrew om
log -0.660g 0.21
log -0.56ogg.n 0.34
-19
log Crr
-20
-14-
33
(c)
(d)
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 "kereel regression" in our reports) and (b) kernel ridge regression (KRR) on 1000 test samples. We randomly selected U1, U2 U3 and kept them fixed for each repeat. We choose the stopping time f in kernel gradient flow Cin where G E (0.001, 0.01, 0.1, 1, 10, 100, 1000]. We use 5-fold valsdvvaliaiionn to select the regularization parameter À in kernel ridge regression. The alternative values of X in cross-validation are C2n Cs, where C22 E {0.001, 0.005, 0.01, 0.1, 0.5, 1, 2,5, 5, 10, 40, 100, 300, 1000}, C3 E (0.1, 00.,,
Theorem B.1 (Restate Theorem 3.3 Let > and x > be fixed real numbers. Denote p as the integer satisfying Ip(s + 1), (p (s + 1)). Let P consist of all the distributions X x y such that Assumption I and Assumption 2 hold for s and 7. Then for any d 2 C, sufficiently large constant only depending s, % C1, and Cz2 have the following claims:
(i) When y E (p(s + 1),
+ s). we have
d min max (x, jmon f S. 1.1122 2 50(7 p(s + (n(()) PEP
In In(d)
(ii) When E (p ps + s, (p () + 1)}, we have
min max (xx | f S. 1 =S2 =(((d-(o-11)
PEP
where Q only involves constants depending on 8, s, 7, Co. R, C₁. and Co.
Proof of Theorem B. The item (ii) is direct corollary of Theorem Zhang et al. 2024). Now begin to proof the item (i). We need the following lemma.
16

---

y theretical
theratical rate-.]
KRR, parameters chosen by CV
-200
KRR, parameters chosen
loqudrr -12330gud 0.55
lotudrrr -1.11000 11.06l0uuh 0.76
Kermil
Ker
19
-215
200
105
-2.30
-2.
-2.40
-2.
2.00
2.05
2.10
2.15
2.20
2.25
2.30
2.70
2.75
2.50
2.55
2.50
2.95
3.00
logos n
logto
(a)
(b)
RDF. y= 1.5, theretical rate--223
RBF y 1.8, theretical ratem-559
Ing -0.05agun
-19
lng off 0.55909,
Kernel regressior
Kernel regrewiin
yog -0.720g::0 -0.09
10g yer -0.610g).n 0.22
-22
-23
-24
-25
-23-
-24
-25
(c)
(d)
Figure 4: A similar plot Figure but with the RBF kernel.
Lemma B.2 (Restate Lemma 4.1 in Lu et al. (2023) ). For any 8 (0,1) and any E1,82 < 00 only depending on n, d, {}y), C1 c2. and y and salisfying
Vx D) + nzz + In(2)
5.
(20)
V2(51,
have
| f- 12 2
1-5
min max E () PEP
(21)
4 11
where Ps. is the joint-p.d.f. of a, given by with f = f.. B { E H [lf] s R.)
D = {pr joint distribution of (y, x) where px,y f(x) e N(0, SEB
and V,, Vx are the e-covering entropies ( as defined in Yang and Barron 1999) Lu el al 2023 of
(B, = -1E2)) and (D,d= KLL divergence )
Suppose y E (p(s + 1), + ps + s). Let C(p) C12/10 110 be constant only depending on 7, where E2 are given in Lemma D.13 Then we introduce
EL d=- In(d) and E C(p) d
Im In().
(22)
17

---

NTK, y=
-20
235
Kernel gradient flow, 0 0.5
log Err
log = -0.89logian + -1.37
KRR, e 0.7
logr - -0. 0.522lagann 0.09
-4.0
-4.5
3.0
3.1
3.2
3.3
3.4
logio
Figure 5: Results of Experiment 2. It can be seen that the best rate of excess risk for KRR is slower than that of kernel gradient flow.
Let us further assume that d 2 e, where C is sufficiently large constant only depending on 8, and cr. By Lemma D.IT and Lemma D.13 we have
Eg dns S 1
= (n(())
c(p) d In (nd s C(p)
11 < 8
r In <
(23)
n
Delinition of C12 1
ns
N(d, p) In
10
Therefore, for any d 2 C, where is sufficiently large constant only depending on 7, and e₁ have
Lemma A.5 in La al 2023
V2(51,B)
K ( 2 クリ2 (dd In
Definition E?
N(d, In
Cgd p(s+1) In(d))
(24)
2 マタ
N(d.p) p)
(7 - p(s + 1)) [n(d) + In In(d)
2
On the other hand, from Lemma D.II Lemma D.13 and Lemma D.12 one can check the following claim:
Claim 1. Suppose E (p(s + 1),p ps + s). For any d 2 C, where & is a sufficiently large constant only depending on s, 7,, Ct. and 0z, have
18p
K (V20ē2/6) < (d. In
In(d)
2
22
18

---

Therefore, for any d 2 e, where e is a sufficiently large constant only depending on s, 7/ e1, and c2. we have
Vx ($2, D)
(2(V220ě2, B)
Lemma A.5 in Luctal 2023
K (V20ε2/6)
Claim 1
18 Iu(d)
NN,, p) In
626
(25)
Definition 2/
2 Ndd p) In
(188 [|]())] (C(())]'c2dt--00 (cddi-p(ot))
$ N(d. p) (x p(s ()) + In In
Combining 23
24 and 25 we finally have:
Vx (6,, D) + ne3 + ln(2)
10(7 p(s + 1)) In(d + 41nl(()
<
V2 B)
[0(7 p(s In) + 5lmln())
and from Lemma B.2 we get
f f. 2 4ln(d) [10(7 p(s 1)) In(d) + 5 ll
In
min max E
f J.BB (x
In In
50(7-p(8+ - 1))(n(d))
finishing the proof.
C Definition of analytic filter functions
We first introduce the following definition of analytic filter functions (Bauer et al. (0077 Li et al. (2024)).
Definition C.1 (Analytic filter functions). Let { { [0, x²] - Rz0 A (0, 1)} be family of functions indexed with regularization parameter À and define the remainder function
xx))) == 1 (x)(2).
(26)
We say that { A E (0) (or simply (x))) an analytic filter function if:
(1) 22x(2) [0, is non non-decreasing with respect to and non-increasing with respect to A.
(2) The qualification of this filter function is E [1, such that V 0 S 7' S T (and also
T' < 20), there exist positive constants only depending on 7' = 1, 3, 4, 5, such that we have
(x(2) 2 Ciz vx(=) s -==AA)-- AA (0,1), C3 S Apx(2) S C4, (b(2)) Cs, Vλ 10, A.
(27)
(28)
(3) If < oc, then there exists positive constant Cg only depending and λ₁ such that we have
xix 2 CoA",
(29)
where A₁ is the largest eigenvalue K defined in 5 and there exist positive constants C and Es only depending on T, such that we have
( > E,, (=/A) (2),)()),
AY (0,1), AA (0,1),
(30)
(31)
(4) Let
Dx = f=EC Re ((-x k3). |Im 2| < Re + X/2] U c = N² A/2, Re 2 x²):
Then (2) can be extended be an analytic function on some domain containing Dx and the following conditions holds for all À (0, 1):
19

---

(CI) I( + ())x - E for all & E Dxi (C2) 1( ((xx))) - FA for all & E Dx;
where F, are positive constants.
Remark C.2. We remark that some of the above properties 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. (0024) 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 2 be fixed. We define
(2) = 1
A (1
X9
(2)
T= q.
(32)
Example 4 (Kernel gradient descent). The gradient descent method is the discrete version of gradient flow. Let 1J > 0 be a fixed step size. Then, iterating gradient descent with respect to the empirical loss t steps yields the filter function
(2) =1 (1-n2)) 1- (1 n2)5
(1-n2)
x (nt)
(33)
2
(z) (1-12)², nz)2, =0.
(34)
Moreover, when 7, is small enough, say < 1/(2k²), we have Re(1-12 n2) > 0forr E Dx. can take the single-valued branch of (1-11a) nz)r* even when is not an integer. Therefore, we can extend the definition of the filter function so that À can be arbitrary and t = (11))-
Lemma C.3.
xxx
KRR
Px
FT.g
xx. and x are analytic functions.
Proof. Notice that (i) < = + A S 2z when z >> A; and that (ii)
X Hence, the constants C₁, C2. Cz. C,. and Eo are given in Li et al. 2024)
z + S 2A when S X.
For Cs, when S A, can take Cs minm1/21
,e- 0.
For E7, when A, we have
KRR (2)) = (2/A) (VX (WX
2
2 1/4
+ X
2q
(z/A)² (v .Tg (3))²
2 2- 24
2 X
For Cg, when S X, we have
2
(QMRR (2))
2 2+ト <
2 SORR
27
(N (TTTT
22
(z + 2)29 - [N(z + 1)]o <
1 IT.00 (2)
22
29
D Proof of Theorem 4.1 and Theorem 4.2
D.1 Bias-variance decomposition
We first apply a standard bias-variance decomposition on the excess risk of spectral algorithms, and readers can also refer to Zhang et al. (2023 2024) for more details.
20

---

Recall the definition of Åz and fx in 14 and 15
Let's define their conditional expectations as
(xx)) H;;
(35)
and
A = == (fixx) px (Tx) 9z H.
(36)
Let's also define their expectations as
/ ((xx))f(xx) dpx(x) e H,
g = Egz
(37)
and
= (T)
(38)
Then we have the decomposition
1 fa f. -PX (Tx)
a
Σ
Kr.yi 1/1 fa
71
1
fx (Tx)
Kr (f%(21) +G))
=xx gz + Σ
Sx (Tx) K2, - f.
1=1
= (f. + 1 7i Σ Φx (Tx) Kn
(39)
Taking expectation over the noise e conditioned on X and noticing that e e| are independent noise with mean O and variance o², we obtain the bias-variance decomposition:
E
f - f.
xx) = Bias (A) - Var(A),
(40)
where
5 - s.1le= L2?
o² n Σ (Tx) ((;,, (1.
Bias (AA==(A)==
Var(A)
(T)
(41)
Given the decomposition 440 we next derive the upper and lower bounds of Bias? (A) and Var(A) 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. = Σ fr6,(z), let's define the following quantities:
(A) = Σ (y)a(A,)l:: (2, Σ ()spa(A)))::
f=1
(42)
M1, ess sup TEX
Σ (WX(A)) (2) = Σ (vx(A))))
j=1
moreover, when 4A = SRRRR ity, where lo = 1,2. Assumption 3. Suppose that
KRR, we denote N&(A) NN (A) and Mz(A) Ma (A) for simplic-
OSS sup xEX
()px)()))) (z))) s N2,
(43)
1=1
21

---

and
sup
Σ (ASPA(A)) (x(x) s (A),
(44)
TE
and
00
ess sup xE
Dypp KRR
SN(()).
(45)
For simplicity of notations, we denote h.(.)) K k(x, ), x X in the rest of the proof. Moreover, we denote T3 == (T'
+T+ + +)-1 and Txx = (Tx + A)
D.2
Variance term
The following proposition rewrites the variance term using the empirical semi-norm.
Proposition D.1 (Restate Lemma 9 in Zhang al. (2024)) The variance term in satisfies that
Var(A) o² / 1ipx (Tx) h2 dpx(x).
(46)
The operator form (46) allows us to apply concentration inequalities and establish the following two-step approximation.
1 1px hux) dpx(x) 2 / 11ia (T) hells,, dpx(x) E
/ 11ox (T) h 11: (2x
(47)
Approximation B The following lemma characterizes the magnitude of Approximation in high probability. Recall the definitions of N (A) and N2 (A) in 44).
Lemma D.2 (Approximation B). Suppose that (43) in Assumption holds. Then, for any fixed E (0, 1), with probability at least 1 ō, we have
1|xx (T) h 2 dpx(x)) Ra
(48)
2 x
/ ||xx (T) hr Mr.1, dpx(x)
(49)
Jx
3
||ıx (T) /x 11 dpx (x) + Ro.
(50)
2
where
(N2
R₂
In
(51)
3n
Proof. Define a function
f(z) / (T) dpx(xx)
/ (A)p)(),))) (f (=)x)0()))
= Σ ()px)d)))) oz(2).
(52)
Since 43 in Assumption 3 Tholds, we have
[l (2) lIfllr (2).
22

---

Applying Proposition 34 in Zhang et al. (2024) for vf and noticing that lIv (A) we have
= Vff
(
In S VJ 12,
2
3
VJ
(1)
2
$
+
In
(53)
3n
3n
8¹
with probability at least 1 8. On the one hand, we have
M P.M = Stx s())dP(())= Ux ( (T) dPr(z)
Jxx Us (ex (T) (T) dPa(2) dpx(x)
/x 1kex (T) Ne M dpx(x).
On the other hand, we have
|v - - flz)dpx(2)
-
x [/ (pxx (Px (T) dpx(as) dpx(2)
J (T) dpx(x))
Therefore,
53 implies the desired results.
Approximation
Lemma D.3. Suppose that (43) and (45) in Ceampptionhhole Suppose that there exists a constant only depending on and 7,, such that X Mnn, d) satisfies (A - 0. Then there exists an absolute constant C₁, such that for any fixed ō (0, 1), when sufficiently large, with probability at least - 5, we have
1s 11pa (Tx) dpx(x) / 11sx (T) hollin, dpx(x) SQ
(54)
+ (/NEp(l)++VVWMN))
VuNi(A)lAA
(55)
where u Ni(A) Inn.
Remark D.4. The proof of Lemma D.3 mainly based on Lemma 4.18 in Li et (0024). Notice
that we replace the Assumption 2 in Li et al. (2024) by (45) in Assumption (borrowed from Zhang
al. (2024)) since both of them can deduce same results given by Lemma 4.2 Li al. (2024) or
Lemma 37 in Zhang et al. (2024).
Proof. We start with
D = Illyx (Txxx(Tx)/aae (hxl) -lexx))allll s | (ex(T)) s0 (x(TT))]
Using operator calculus, we get
T (T) - (xx]])]
=T T
2mi f RTy -T)) hn
1
f (T - -) [T)(T - 2) hx)p)22dz
2 Jr,
f TiT x
- -1 b
T 2 (T -T (2 TT h))x2
2mi Jrx
23

---

Therefore, taking the norms yields
T
-
Tx)7 || (
< 2m
T z Ie L (xa(2)dal
II IVI L. ((x())dz
2m
(N(
Inn C. (N1(A) f. (ex(2)dz), n
< 2m
.1. VBC
where 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) et al. 2024) we get
f. (ex(2)da) s C'IA
(56)
and thus there exists an absolute constant C1, such that we have
D = [llxx((xx)aalll ||xx hzz)llleell s CI)
In
On the other hand, combining 52) and (43) in Assumption 3 we have (1 I (A), and hence
+ I1xxx (Ix)(T))
s $ (T) +D
$ +G
Finally,
= =IIlax(Tx)hulle= - ||lxx(T)h ( + (TTall))al
<ci (V (A) (A) +CIVON(())AA-)) - VUNI(A))mA
and hence
1/8 11 hT dpx(x)) f 11sa (T) hullie dpx(s))
|1 h.. 11,2 11 (T)) 11:2
< sup zEă
- -12x
+ +GVeNN)+ VENG(A)mAX
<Q
Final proof of the variance term
Now we are ready to state the theorem about the variance term.
Theorem D.S. Suppose that (43) and 45 in Assumption 3 hold. Suppose there exists constant
c > 0 only depending on s and 7, such that X ((n, satisfies
N1(A): n n +0
(57)
NP(()) (A)
(n(n) A 1112 0;
(58)
then we have
Var(A) = [1 op()) 0² (2,
(59)
n
24

---

Proof. Recall that Var(A) = 3² x 1l (Tx) Mxlle,,, (px(2)) Hence, when is large enough,
with probability at least - 5 we have
1 (Tx) Ne LA, dpx(x) - /1ex(T)aall
J/x 1lex (Tx) ho 12 dpx(x) / 11ix (T) (T) helli dpx(x)
J 11ia (T) Nx 12 L2, dpx(x) / 11xx (
Lemma 12.2
1lpx (Tx) ho 20 dpx(x) / 11ex (T) holli dpx(xx)
+ 5.22
In
3n
N
Lemma D33
(1) C. (FUN(())( + (N)
2
In
3n
Delinition of (2)
NG(A) C. Ci NP(A)
N2,
5
2
(1 +
In
3
5
2
= =I.CG/m(())X-- +II (ln) ) + III
- in
3 8
When n 2 C. a sufficiently large constant only depending on and C1, we have
I I-C1v 1.Civi((n)ma-- InX & (2,
Furthermore, when (A) o (X]
nz O, have I G In
and II
+. O.
Finally, from (2) we have
(T) Σ (App)()))) (z)=)
and thus the deterministic term writes
J (llx(()aalladdox) (2)
D.3
Bias term
In this subsection, our goal is to determine the upper and lower bounds of bias under some approxi- mation conditions.
The triangle inequality implies that
Bias( ()= = | - -sa 2 115A f-ll1 - JA - 1A/12
(60)
Bias(X) < IIfA - f+llee + ||Ax -Allea-
The following lemma characterizes the dominant term of Bias X).
Lemma D.6. For any À O, we have
lIf fal122 (A)
(61)
25

---

Proof. We have
06 ((Px(A))ioo(())
IIf fall22
Σ f(01(z)
12
Σ (x(Aa)
Σ (+)():)(i)²
(2)
The following lemma bounds the remainder term of (ias(A) when 2 1.
Lemma D.7. Suppose that (45) in Assumption 3 holdd. Suppose that there exist constants and e only depending on 8 and y, such that X = A(n, d) satisfies
n (A) - 0, M(AAM (1)
(62)
(M2r0(A) o² Nen(1))
(63)
n²
n
(A) (m
22 X2 (Ai) x+1
f. = (MaspA)+ + (aop(A)+NVpp -2
(64)
ni
j=1
then we have
| | = oz (Merl(A) + o²
New((a)
(65)
n
Proof. Do the decomposition,
f fa (x(x))xx (dX(Tx) + P
= (x(Tx (0x - Txfa) - (X(TT)TTXN(TA
=Xx(Tx) - Txfa)
= =Xx(TX) [āx - -TxfA- -
=Px(Tx) -TxfA- 9 +T7 (Fx()))))))))) (x(Tx))xxxx)
IIIII.
(66)
Bound on I: For the first term in 66 we have
[
(xxx(Tx)(xx Tx fa 9 +TWille
( Txfa 9 T
T #1 TT (T | 1(xx Txf22) - - -Q-TTaill 12
(72) Zhnng al.
T Tx (Tx 77,
1 1/2 [(āx - Tx/2) - (g -TSW)
Proposition 1.
T
- || 1 1oxx Tx/2)= -gg (T-NTa
71
62 and (73) in Zhang al. 2024
12|| 11xx - Tx/A) - -G--TA))
26

---

Denote & = m-th moment of E(x)):
(Ka: - Ax) To use Bernstein inequality, we need bound the
E |1(())) = E I $ - (x
-
E b K(x,)) +) m
10)) (67)
*
Note that Lemma 37 in Zhang et al. 2024 shows that
| K(, :)
SNi()) prace x
By definition of M (A), we also have
I f+llz= (A)(S() =M)
(68)
In addition, we have proved in Lemma D.6 that
[fx((z) - = (2)
So get the upper bound of 67 i.e.,
67
NG Ilfa - f= Bl(f(()) fx(1)))
=M(A) (1)
(N) (Ni())
Using Lemma 36 in Zhang et al. (024) with therein notations: L = -N() M (A) and M2, 2 for any fixed (0, 1). with probability least - 5, we have
2 xh | S 12 4volog
M1 M1,
(69)
vn
Bound on II: For the second term in (66). we have
1.a
< - 1H
(70)
+ (VX((X))TT - -TTTTTTT))T((TTT))))X)))))))")))
For the first term in 70
we still employ the analytic functional argument:
-A =
-1 1
f Ti -))
2xi Jr,
1 o T
(Tx -
(T-
2 Jry
(T) - wtw.rtt.t........cc....... (T)
27

---

Therefore,
2T 2
/ | $ | - | 3 (T Tx))x $1
|| (T 2) -) - | (T
2 (ex(2)dz)
(72) Zhang al. 2024
A |Tx (Tx - - $1 $1
[ - -2)- - 1xxx))
15
and Proposition E.8
VOC² f. 1|T5 } (T- (Tx)) $1
(71)
|| xx |px(=)dz
Lemma 120r
Voca vo ff [ f. I (x))dl
Delinition of (A)
voca (oMB(ol) of (ox())de)
56
VoCa (UMB
where V == A112) In n.
For the second term in 70 we have
T (b (T)) (X)T)
1 of Rix (x) T(X(T))))
= -
fr.
T(P(T))S
2Ti
1
f
-
2τ Jrx
1
[ T+I 3/2 b (Tx 3T
2τi
T (T - 2) - (T)
Hence, similar to 71
we have
2T 7 PAAAAATTTTTTTTTT-TTTTTTTTTTTTA
7
< / | || | (1x 1 (( $||
- -) I TT (1 (xx=))a=1
(72)
V60 vollas b & 11 / Wx(2)d2l
Definition of analyric filter functions
VBC² V x TTX CFXIIX1
28

---

Combining (6).
669
77pp.
71
and (22).
there exists a constant E₁ only depending on å and F.
such that we have
f
11
(1
Ma
ei
n
vn
+ (IVEMM + CIVo Tx 3 TT (2T). AlnA
62
(n (n- 1/2
E1 (M22 (M2
(73)
+ (n 1/2
-I (M2ip ()))112
+ (n
1/2 .6 .I. (M)2 N2
+ o² + (Mao(A)+
1/2
When < 1, we can use the following lemma to bound the remainder term of Bias This lemma a modification of Lemma D.7 and its proof is partly based on Lemma 26 Zhang.
Lemma D.8. Suppose that 45 in Assumption 3 holds. Suppose that there exist constants and e only depending on s and 7, such that X A(n, d) satisfies
n NG) - 0. 22A (Ar)
(74)
(i(A) (m n
f. << (M2,(A)+ + σ² Ne
(75)
X A
1/2
~-ANG(A) (ILFallen +n tettt)) =0 (MaLs())++ N2
(76)
then we have
1 o0 (Map(A) + o² Neno(1))
(77)
n
Proof. Similar to the proof in Lemma
D.7
we have the decomposition fa fA = II with
| - 12? T 1(xx - -xffa) -g - Tfall -T-Tfa)
H
0² |I 122= (A)
n
Denote & = E(x;) = T 3 (K2,)a(1,) - T2) Further consider the subset Q2 = for E X : [f)( 1) and f2 = Xi where t will be chosen appropriately later. Decompose & as Ellz,en, + Eid,, en, and we have the following decomposition:
|
| i [0xx Txfx) (g - --TTIl
Ec,
(78)
74
Ele,ea BEoloEn
+11
1
Σ
n
n
14
III.
(79)
Next we choose = - , = 1-s
2
Ey such that
1-s
2 1/
6, < 5 and
+ E
>
Eg
(80)
1-8
29

---

Then we can bound the three terms in 78 as follows:
For the first term in 788 denoted as I, notice that
11(A f.) Ta,enill 11 S I1fllle + -n"
(81)
Imitating (67 in the proof of Lemma D.7 we have
1/2
I 1= op (22 N22
(82)
(ii) For the second term in 788 denoted as II. Since 2 (024) shows that,
I-8
Eq
I-s-
2
Lemma 42 in Zhang et al.
[H]* + (x),
(83)
with embedding nomn less than constant Cs,e. Then Assumption < Cg < only depending on 7, and such that ( inequality, we have
(a) implies that there exists
Cq. Using the Markov
(x)
(C₂)
P(x E 92) = P(((((()))
4q
Further, since
80
guarantees 1a n,, have
== P (II > 0)
(84)
$ P Br, s.t. I2 E S22.) = 1 P(225 $ S2, Vz,, i = 1.2,...,,,
1 - ( (I $ 02))
P (()) st)
$ $1-(1-1 (C,) +
(85)
(iii) For the third term in 778 denoted III. Since Lemma 37 in Zhang al. 2024 implies that [T k(xx,))lx S A (A) a.a.e. X,
III - E La xl - E ||T k(x,)) I(f 1ff-l(ff.ffl fx(x)) Leeazl
$ MG & B (J+ - fx(x)) T
$ (1)) 1 - P (xr 22)
S & (A)
(86)
where we use Cauchy-Schwee inequality for the third inequality and Lemma D.6 for the fourth inequality. Recalling that the choices of t, q satisfy t < n and we have assumed n M (A) + have
III o (A)+t)))
(87)
Plugging
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 2 1). Suppose that (45) in Assumption 3 holds. Suppose that there exist constants and C only depending on and 7, such that A(n, d) satisfies
n NN 0,
Mi n² < (Mzr(A) + 0² -evo(a))
n
(A) In
X A p < (Meno()+ Nevo(A)) n
o²
X+ X
then we have
Bias? - (2) = Op (M) @²
(M -NNoraaa)
(88)
30

---

Theorem D.10 (s < 1), Suppose that (45) in Assumption 3 holds. Suppose that there exist constants e and E only depending on and 7, such that A(n, d) satisfies
n (2) 0, X X (1i)
(1 (n
o² le << (Map)()) (aao(a)):
x+ A
" NNNNG (I1AllE>+ni) = (M2zel)+ ( o² 1/2
n Nevo(Al) )
then have
0² Bias (2)) OP (M
n -
(89)
D.4 Quantity calculations and conditions verification for the inner product kernels
In the previous two sections, we have successfully bounded the bias and the variance terms by the quantities (A) and 22, (A). In this subsection, will focus the inner product kernels 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 μl and (dd, 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 ct al. (2023) give concise characterizations of μt and [d, k), which is sufficient for the analysis in this paper.
Lemma D.11. For any fixed integer 2 0, there exist constants C, Eg and Eıo only depending on and (as)i such that for any 2 E, we have
Eqd k S μh S Ciod
(90)
Lemma D.12. For any fixed integer p 2 O. there exist constants e only depending on and {azlisp+i, such that for any d C, we have
E10 d'' Ups Cg
Pk <
h: -=p+1.p+3
where Eg and E10 are constants given in Lemma D.IT
Lemma D.13. For any fixed integer p 2 0, there exist constants C11, E12 and e only depending such that for any d 2 E, we have
En S k() S Ei2d",
k: == 1,0,,.... . .pt.
(91)
With these lemmas, we can begin to bound the quantities M2 (A) and No (A).
Lemma D.14, Suppose that Assumption land Assumption 2 hold for s and an integer p. Suppose f < p. t= x-1 E (d', 11, Then we have the following bound.
+ (d=
== x
M2 =
+ (t d + +d ((+))))
8 5 2T < 00
+ (A2r)
8 8> 2T
N2 =
de
(92)
Id
n
N(d.)
Σ
P2 0 ( (p(2 s).0) + d dds((tt))
+ 14
K=U
J=1
and thus Assumption 3 Shold.. Moreover when 2 1, We have
O (d-(44+1xx-1) (122-11 10x1x=000//000/00000
T 00
(2)
+ (6+1))(()111) (22--1)
3 $ 2T < 00
(93)
$ > 2T
31

---

Proof. I. We begin with M2,((A). If I 2T and T < oc, then we have
2
N(d.))
(2) = Σ
Σ
Pbi
k=
==1
N(d,k)
0c
((dA)
c3(()s))
25 (1x)
Σ
(ma)
"Pes
+ Σ (x((K)
Σ PEs
j=1
k=(+1
==1
N(d.k)
N(d.k)
((ppc) (00u)--2(((10 (1x))
Σ (m=)
(nx)==Pes .Rh +
(Nx)
Σ
(mx)=*
PPis
0=
j=1
k=(+1
Nid,a)
N(d.k)
et 25 (Cgd 1)0-2r Σ
Σ (ux)=
[kaj + 111
(uz)
Phis
j=1
k=
= 0 2r ((22-))) + d
and when 7 = oc, similar argument (taking T' and let 7' - oc, then we have (td (td--))-r'-_ 0)
shows that M22 (A) = O(d-
Similarly, if S 2T, then we have
N(d.))
(2
2 <0) Σ
(((m)) (Ta)²
Σ (#x)~* P
k=0
N(d.))
+ Σ (px))
Σ
Pb.
k=t+1
2 1 < <0
(
N(d.k)
(((p))*
Σ
(1x))
8 fh.
km8+1
j=1
2 fT < oc s2
(1-2
N(d.e)
+ c3
Σ (we) $2.
IT <of (- ((( + St (d-oletz)).
If 1r < s, then
00
N(d.A)
(2 = Σ (Hx)
Σ Ph.
k=
==1
(d.k)
Lomma 23
ks
(
2r
M P2.
k=
1=1
-0(2?)
Similarly, 27 < s, then we have
(2 2 (2(o))ff
2 e/ 12 22
= 2 (127).
32

---

II. Now let's bound the second term (A)/n. We have
(1)
1
00
Ndd k) [mx)))(1=)]
71
7
k=0
N(d, R:) +
Σ
N(d, k) [uaS)((N))
k=t+1
((d,)) + GB
8
(94)
Σ
M(d,k)
n
k=t+1
2d,
pet1
d
t2
11
nd
Similarly, we have
(A)
C
kdd +
Σ
((d,))(ua)²
k=
k=t+1
E(d.
(95)
C
pe+1
n
n
d
1
nd
III. For the third term, we have
X (p ((d.))
Σ f2g I R²
Σ k=
1 + +x-1 Σ
Mk m 1 -2
A+
0=0
j=1
k=p+1
= = (1 (22 0).03 + - ---o--0+)))441)
= 0 (2²x mmxx ())00 d=
IV. Now we show that Assumption 3 holds. Notice that (5 has been verified in Lemma 20 of Zhang ctt al. (2024). Similarly, one can prove (43 and (44) hold using a similar proof as that for Lemma 20 of Zhang et al. 22024).
V. For the final term, when s 2 we have
M2 My (A) ess sup mE
(a(A)
sup DEX
Assumption
(a(A ((pa()))
Avp)(A1s)
:= Qi, (A).
(96)
33

---

For (2), when 7 72 2/22 and r < 00, we have
Aiunnun N(d.)
() = Σ
Σ
pa(l(s))
k=0
j=1
N(d.k) Σ
-2
Shi
1/
Mk
k=0
(97)
00
N(d.k)
+ (Ca) -1
UB
k=t+1
j=l
= =0 (xxx20 (x () 5) + Ad (e+ ((+1)))11))
Similarly, when 5 = oo, we can show that 11, = O(dd 0(dd-(++1xa-1)) And when T < s/2, we have
M(x))n N(d,))
(1) =
Σ
Mx
Jk.j
(2(()))
k=
Lemmi
Cg 2r)
N(d.k)
C1
k=
j=1
1 N(d.))
Σ Me fh.
(a(UE))
k=p+1
p N(d.k)
30
X27
Σ
El
km0
j=1
N(d.k)
+
C3A2T 2T
Σ
Mk f2.
k=pt1
j=1
0 (X²7).
For (A),, we have
(1) = Σ
N(d,k) (MNPP(()))
K=
<
kdd
+
Σ
Níd,k) k) [MA))
0=
k=t+1
(98)
8
< Σ N(dkk)+ + eGt
Σ ((d,k)us
K=
k=t+1
< (d( + Est
= 0 (d + x = 0 =0++ (2-1)
Therefore, when s > 1, we have
() 10
- ()(2 + +o ((+())((--1)
0 (11-442)6)1)
T=
8 27 < $> 27
(99)
0 (127-1)
34

---

From Lemma D.14 we have the following three corollaries.
Corollary D.15. Lei < 8 S and > O be fixed real numbers. Denote p as the integer
satisfying 7 [p(s 1), (w + () 1)). Suppose one of the following cases holds for X dt or X d pply (In(d)):
(1) p0p2,,,0 < x
3 < ps p (7 - (p+ 1)(s 1))/2
(3) < 1]/2
(4) 8 (7 18-11)/2
Then we have
d (2 x N2, = (d- +
n ))
(100)
n
or
dP) M2 (X*) x (2,p(>)) = (d-obtt))
poly (In(d).
(101)
n
Corollary D.16, Lett < 8 S 2T and y > 0 be fixed real numbers. Denote p as the integer satisfying 1I, 1) ()(s+ 1)). Denote A y p(s + 1). Suppose of the following cases holds Y for x² d or x* d poly (In(d)):
(1) <
(2) =
(A 1)/(27 (2(+22+++))) +2
(3) 1..24422 1 (A + s)/2
(4) 1
Then we have
(2 x (2 1 (a -. 2(2- =(o+1)))
(102)
n
or
(2t x (2** A min ( pt 741
s(pt1))) poly (In(d)).
(103)
Proof. Denote I -2r + 2pr ps. == ss III = p and IV = 28 - 1. From
Lemma D.14 we have
M2, x d= + N2 x II LV
We can verify that:
(I) When S S r and p p/(r)) we have
IV and min { - -(7-p+1) + ps
ssp + (0++1) -7 p.
T+1
(2) When 7 A + S/T and
p (A + 12/ + 2), we have
T(7 + 1) + ps
, + 11) 7(7 - p 1) + ps
= IV > III and min 7 p,
sss
T +
T +
33) When A 2 s + S/T and
p (A + s) we have
I == = IV and min { - 7(? - p
ps
s(p + 1) = s(p + 1);
T ++1
35

---

(4) When < and = 7/2, we have
2 max (I, IV)..
Corollary D.17. Let s <, and 7 > be fixed real numbers. Denote p as the integer satisfying
E [p(s + 1), (p + 1)(s = 1)). Suppose one of the following cases holds for X = d or
A = d= poly (In(d)):
(1) - x., p >
5T< |,=
(2) 7 x.,
ps+
8))/2
(3) 7 00, <
( - 7/23
(6) 7 < ps + + ps -p
Then we have
(2* + (22 = (d-(oot)) + dp
(104)
n
or
(2* (12) = ( +
dp
- n2
poly (In(d))
(105)
n
D.4.1 Verification of variance conditions
Lemma D.18 (Verification of variance conditions for inner-product kernels). Suppose n d' and 8 2 1, for E [p(s + 1), (p + (s + 1)). For any given f 2 0, if
d In (d) d $ In (d)
13) 1, 26 < max 7, (p 1)(s 1)}
p 0, 7 1, 28 m
d
p= 0=0,7 1, 5
then there exists constant
0 only depending on and 7, such that À = A(n, d) satisfies
NG n-
N7( 22 (A)
In(n) X-102 +
Proof. From Lemma 21 in Zhang et al. 20024), we have (1 x X-1. When p 0, have - 8>> 0. When 2 1, we have
1/2 2 ps 1/2 > 0. Therefore, there exists a constant
é <> 0 only depending on s and 7, such that we have
Mi(A m--1 0.
Denote q : [d]. From Lemma D.14 we further have (A) S (d' 2d Hence, we
have
AP(A) In(n) In(n) X nnX2dd + d d
(In(d))3
2
Denote A
(Ia(d)) ( nx2
do v then when A o(1) or A' = o(1), we have:
NF(A) (nnn))1 - 0.
(A)
Now show that A = o(1):
36

---

When p 2 3 and 2, > since - 9 A (11.
> 0, we have
When p 8 1, since - - < 4 7, we have o(1).
When p = 2, 8 1, since - < 4 <45 7, we have = o(1).
When p - 7 > 2x since f < hence - < S 7, we have = o(1).
When p = 1, 5 1, < 2s or p = 1, = 1,7 2, since 2/ - S < 7, we have
A o(1).
When p
? 2, since 2 - 7, have A 0((n(()))))
When p since 7 26 2 0, we have A ((IIndd))
Lemma D.19 (Verification of variance conditions for inner-product kernels: saturation case). Suppose
< < 2r. Suppose x d", y E 1) +
S/T 1]. For any given 0, if
d' p p(s + 1) + 1) 2);
then there exists constant
0 only depending on and y,. such that À = X(n, d) satisfies
NG(A) n= +
N7(A)
In(n) - 112 + O.
(A)
Proof. From Lemma 21 in Zhang et al.
2024
we have N1 x -_1
Notice that we have
27 ps p
p21 > p 0
2(r 1)(7 p)
(T-
Therefore, there exists constant
0 only depending on T, s, and n, such that we have
Mi(A) n-
Denote = [[]. From Lemma D.14 we further have No (A) = (d9 + - Hence, we have
AP(A) 1m())((1x113--00
(Indd)3
22
n(X2dd9 + +d---1)
(In(d))3
(In(d))
=0
+
nd7dd
d--9-1
(In(d))²
A (In(d)) d5 We have:
Denote A
When p 2 since
2(7 1)
28 28 + 9) 2 2( 1)[(7 (- (q 1-1) f)]
p8-2
p> 2
2( + 1)( -1) 2/78 p=1
0,
we have A o(1).
When p since 7 1, we have A' o(1).
37

---

Lemma D.20 (Verification of variance conditions for inner- -rnor-product kernels: misspecified case).
Suppose n x d' and 1. E [p(s 1), (p+ (s + 1)). For any given é 2 0. if
d' p21, 28 < max + p(11=)) - 8)}
d d In(d)
p = 0, > s, 28 7
p= 0, s, 2 m
then there exists a constant e only depending on and 7,. such that = M(n, d) satisfies
N1(A): n== + 0,
(A(1 (nnn)(( O. (A)
Proof. When p 2 1. it is direct result of step 2 (the verification of the second condition in (146) of Zhang et al. (2024)) in the proof of Theorem in Zhang et al. (2024) and the fact that (A) (2))..
When p 0, similar argument as the proof for Lemma D.I8 give the desired results.
D.4.2 Verification of bias conditions
Lemma D.21 (Verification of bias conditions). Suppose [p(s + 1), (p + 1)(s + 1)). For any given 2 0, if
S 8 S T. Suppose n d", for
d (1 + In2 (d) = 22 13)
p 2 1, 28 S max 1.7 (p 1)(s 1)}
x
In (d)
E [1,8 + 1), 28 S m1xx11,7 (8-
d=
TE (0, 21 2
then there exists a constant e only depending on and 7, such that A(n, d) satisfies
(1 < (Mana()) +
0² N2s((A))
n
(106)
(1) In(n)(n
X A
f < (Men(A))
a² + (evpl(a))
A+ A
n
Proof. When 1 SSS from Lemma D.14 we have
(Maz)(A) 0² m
N2 Ω (d) ((0+)())1) + +d²)
(1(AM (A) (1)(--1) 8 + + (--------
n
17 ((n(d))))) 0 0 (1(2-x (A) (Ax)
+ x + x-!d-<(ot1)).
X A
Denote 22(= 78 II (0t III Xd (In(d))3 and IV
For any p 2 0 and any $ 2 1:
From Lemma D.18 we have IV & (
When y 2 1, we have 2 + 1, and hence II & IV & (=(+11)) when < 1, we have
& d with g =
When p > or 7 E (s.8 + 1), since -fs + qs < we have 1/di-s(q+1)
0(d-2()=(-</2)) < 1; when 7 E (0, s), we have O(d-2e(+21-)) (d < d with 0.
38

---

When 2 2, we have III < d"; when < 2 and 0, we have III < d"; when < 2
and p 2 and q 2 1, since 7 L > min (s 1)q ps 1/2] > 0, we have III III/d>~a(o+]
d (>-((-))) 2(8-4) < III / d < 1; when s < and p 2 and
q = 0. we have III < d
Combining all these, we get the desired results.
Lemma D.22. /Verification of bias conditions: saturation case] Suppose T < S 2T. Suppose x for E (p(s + 1), (p () + 13). For any given E 2 0, if
d' d (n d
p L max 62, E3]
A2
7 118 1), l E max (11, E2, f3}
E (0, 1), 20 S:
where T, A, E1, lz, and Eg are given in Lemma on 8 and ", such that Mn, d) satisfies
D.16 then there exists constant c > 0 only depending
o² M1 (2) < (Mane(A++ Navo(a)):
n2
n
(107)
(2) In
o² ft < (Mene() + -Nao(aa) A+
n
Proof. When v <85 s 2r, from Lemma D.14 we have
(M2z + o²
(2 = s 2227 (1(2r=)) + dr x (3
NG(AMMP (2)
(1 9(2 -d
n
(A)= (A:) A A
l2 O ((n(d))²) O 0 (1 s),0) - a((t))))))
Denote I' = 1 d (ta(2r-s) 5) II = -d III Ad m) (In(d)) and
IV X -d (In(d))s
For any p 2 0 and any 1 S 2T:
From Lemma D.18 and Lemma D.19 since N1(A) n + have IV d
When y 2 1, we have 2 p + 1, and hence II < IV < d when < 1, we have
II d with q =
When p 2 since -er q7 < and
0- s-2/
(22p 1)
(2r + 1) + ps)
-(r 1)s ps-1
8(7 + 1) .ps +
max
1
2
2
27
0,
we have 1//d--5(9+) < when p = 0, we have I' O(d 2-1+28-7) d with g =
When 7 - - ps E 7 U( + s/r - 1, 8 1). we have s max (b, {3). Similar the proof in Lemma D.21 we can show that III < d + da
Finally, consider the case 7 - p ps E |7, + S/T 1). When 2, we have III < d9; 1, we have III/d Ad 4 <<
when 2, since
Combining all these, get the desired results.
39

---

Lemma D.23 (Verification of bias conditions: misspecified case). Suppose 0 <
< 1. Suppose
. for E [p(s + (p. ()(s + 1)). Suppose one of the following holds:
(1) 7 00
(2) 8 > 12TT))
(3) 7 > ((2T+ + (2)))(2T(1++0))
Suppose one of the following cases holds for d or (l(()d
(1) r == oc, p(s +) 5 +
E p.p min (1/22
(2) +=
E (
s(p + 1)Hl
(3) r <<< 0c, s
8= (- - (2T)
(4) T < x,, ps + < ps +p+s+1
8= p + (2T)
then there exists a constant c > only depending on and 7, such that X(n, d) satisfies
(1) (1n
x x+ l3 < (22p(A) + Nanp(A))
o² n (i (ILAAI1 + +n +e²) = (Maro(A)
n (2
Proof. When 0 < < 1, from Lemma D.14 we have
(M2z + N2 = S 10:00000000 (d-- + dD)
n N 0 (A- (A-1)-70)
In()))n (A) f2 O ((n(dd)*)) (2 + )-1d))(ot))) A+
and the convergence rate of [l can be attained similar to Lemma 25 in Zhang et (024).
Since + 2 1, similar to the proof of Theorem 3 of Zfang et al. (2024). when 1 < 8 < 1, we have
n (A (1ISAlle> + +n m = (M)
r² - N2,
and when s 1/2, we have
n (A) = (Masll))+ 0² " Noip(1))
n
Denote == 22 II ((n(2)))((n(d))) and III =-I= (lm (In(
For any p 2 0 and any 0 < 8 <
From Lemma D.20 we have III < d)-
When 7 < ps + p + 8, we can show I & d when: (1) 2 1, or (2) p = and >> 1/(2r) > 0. or (3) = =0,
When 7 >> ps + p s, we can show < (p++()+1) holds if and only r 0 or
(2T + 1)s + 27(1 + s)p
T=T< 00:
2r(1 + s)
40

---

and the above inequality holds when ( > or (2) 0,s > 1/(2T) > 0. or (3)
p y > ((27 + 1)s) (2T +
When 7 ps + + s, since 2 p > p ps, have II dd;
When 7 ps + 8, since f 2 p p ps, have II d)~
Combining all these, we get the desired results.
D.5 Final proof of Theorem 4.1 and Theorem 4.2
For each case, the proof can be done in the following steps:
When A > A and < 2r, where the definition of the balanced parameter X can be found in Corollary D.15 and Corollary D.16 we have
a² M2 +
N2 (1*) =Op (d--))) poly (In(d))
N2
n
o² (2) (A) = Op (d= poly (In(d)),
where d d= is the desired convergence rate given in Theorem 4. or Theorem 4.2 and
B S 3r, Similarly, when 2T, by taking = 2r in Corollary D.16 also have
(2* - (A*) )+=) Op (d-0*) poly (In(d))
n
(2) + ( Op (d- poly (In(d)).
(ii) When À > X², from Lemma D.14
Lemma D.18 Lemma D.19 Lemma D.20
Lemma D.21
Lemma D.22 and Lemma D.23 we know that conditions Theorem D.5 and Theorem D.10 are satisfied. Therefore, we have
Theorem D.9
E
[
fa
X
Op (d (d=0*) poly (In(d)
L2
E (1
f. ||
X
Op (d poly (In(d)).
(iii) Finally, when s > we can further show that: the convergence rates of the generalization
eтrоr can not be faster than above for any choice of regularization parameter X(d, n)
0. Notice that, when 2 1, for any À < X*, from the monotonicity of Var (A) (see, e.g..
et
(004h; /Zhng al. 2024)), we have
|| f.
Var(A) 2 Var(A*) x E |1 - fa 2
E
X
X
and hence
(11 Sa
S2r (d-o-) poly (In(d)).
I
x)
E Auxiliary lemmas
Proposition E.1. For any analytic filter function 4x, we have (2 N)px(22 s 4 and (2+1)xb(22
4A.
Proof. From 28 we have (a + ())x(2) S maxx (2) < 2 max(1, S 4. From 27 we have (z (z) < maxx22, (1(x(=)) S max (2,, 1} 4A.
Lemma E.2. Let x be analytic filter function defined in Defimition C.I Then, for any [0.1]. we have
sup (2x(2)2 S 41 =E(0,x3)
41

---

Proof. For any 2 E [0, K² from Proposition E.1 we have (= A)px(2) S 4. Therefore, from
Proposition B.3 in Li et al. 2024). have
42* S
px(2)=* 41a11
Y+
Lemma E.3. Let 1/x be defined Definition
Then, for any > 27, we have
2² xx(x) s e3 X²5
sup =E[0,x41
Proof. For any 2, we have
(a(=) S + SCCC/AA
hence
2 x003(2) 232²= 2r 23,((5-27)
E.1 Analytic functional calculus
The "analytic functional argument" introduced Li et al. (2024) is vital in our proof for Theorem
For readers' convenience, we collect some of the main ingredients here, see Li al. (2024) for
details.
Definition E.4. Let A be linear operator on Banach space X. The resolvent set p(A) is given by
P(A) = {) E C A - À invertible).
and we denote RA(A) = (A 1) The spectrum of A is defined by
( = C\p(A)
simple but key ingredient in the analytic functional calculus is the following resolvent identity:
RA(A) RB(A) (B (A) = (B AA).(
(108)
The resolvent allows define the value of f(A) in analog to the form of Cauchy integral formula, where A is an operator and is an analytic function. The following two propositions are well-known results operator calculus.
Proposition E.5 (analytic functional calculus), Let A be operator Hilbert space H and be an analytic function defined on Dj C. Let be a contour contained D, surrounding (A). Then,
- A) 1 1 f f(=)(2-
f Jr f())RA(z)de,
f(A) = 2τi
(109)
2ri
and it independent of the choice T.
Now, let I' be contour contained in D, surrounding both (AA and (BB. Using 108
we get
1 f f(=) [R((2) d=(=)]d= 2ni f
2xi & RB(=) ())
1
S(A) S(B)
(110)
Proposition F.6 (Spectral mapping theorem). Let A be bounded self-adjoint operator and f be continuous function a (A). Then
of(()) (f(A) ((E)(
(111)
Consequently, [[f(A)] (up |f(A)] S llfll
42

---

Let us define the contour A'x considered in Li et al. (0244) by
a = Tx,1 U
Σx,1 { (z+ n) x [-n. 0}}
(112)
Tx,2 {a + n)+ e 6 (0,
Tx,3 [= x² 2² + Re(z) x.2
where / 2/2. Then, since T and 7x are positive self-adjoint operators with ||7 ||xx| < x² we have ( (Tx) [0, Therefore, Fx is indeed contour satisfying the requirement in Proposition E.5
Proposition E.7. Suppose that (45) in Assumption 3 holds. Suppose that x = M(n, d) satisfies (A) In = o(1). Then for any fixed ò E (0, 1). when is sufficiently large, with probability at least i 6, we have
IT (T - Tx 1 Vo.
| . 1| 32
(113)
| 33
(114)
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 al. (024) with only the constant modified), When 113 holds, there is absolute constant that for any = E T'x.
2) sc sc
(115)
-T) -> VoC.
43

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: 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 large class of (optimal tuned) spectral algorithms with different qualification r's, and provide discussion new phenomena we find in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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 other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: 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-tune 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 encouraged to create separate "I "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results 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 the scope of the claims made, e.g., if the approach only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails 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, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
44

---

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

---

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

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no socictal impact of the work performed.
Guidelines:
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.
47

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses 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 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
48

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
49


Reviews:
[{"review_id": "thFgz6wo7q", "reviewer": "Reviewer_QpMc", "summary": "### Summary:\n\n \n\nThe 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. \nTheorem 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$.", "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.\n\n- line 200 -- what does $f_\\star$ mean? It is only defined in the next page.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "### Pros:\n\n- very well-written\n- tightening previous results on the minimax rate of kernel GF in high dimensions\n- proving the saturation of KRR in high dimensions", "weaknesses": "### Cons:\n \n - the main results of this paper are stated on page 7, the presentation of the results is  slow", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your detailed review and thoughtful comments. We are grateful that you found our paper well-written and technically solid. Below, we address your concerns and questions in detail.\n\n\n**Author's response to Concern 1:**\nWe appreciate your suggestion to present our results earlier in the paper. We agree that, in a 9-page conference paper, it is crucial to present the main results as early as possible. Therefore, we followed your recommendation and added a non-rigorous version of our main results (Theorem 4.1 and Theorem 4.2) in the contribution part (page 2 in our manuscript). For your convenience, we restate the non-rigorous version as follows:\n\n### Theorem (Restate Theorem 4.1 and 4.2, non-rigorous)\nLet $s>0$, $\\tau \\geq 1$, and $\\gamma>0$ be fixed real numbers. Denote $p$ as the integer satisfying $\\gamma \\in [p(s+1), (p+1)(s+1))$. Then under certain conditions, the excess risk of large-dimensional spectral algorithm with qualification $\\tau$ is of order: \n$$\n\\Theta_{\\mathbb{P}} ( d^{-\\min ( \\gamma-p, s(p+1) )} ) , \\quad s \\leq \\tau\n$$\n$$\n\\Theta_{\\mathbb{P}} ( d^{-\\min ( \\gamma-p, \\frac{\\tau(\\gamma-p+1)+p\\tilde{s}}{\\tau+1}, \\tilde{s}(p+1) )} ), \\quad s > \\tau,\n$$\nwhere $\\tilde{s} = \\min ${$s, 2\\tau $}.\n\nWe would greatly appreciate your further advice on how to better organize our paper.\n\n\n**Author's response to Question 1:**\nThank you for highlighting this point. We will clarify the definition of $f_{\\star}(x) = x[1]x[2]\\cdots x[L]$ in line 200. Here, $f_{\\star}$ represents the regression function, where $x[i]$ denotes the $i$-th component of $x$. We will ensure this definition is included in the revised manuscript.\n\n---\n\nWe thank you once again for your expertise and valuable feedback. Please let us know if you have any further questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DhxdeFNRfE", "reviewer": "Reviewer_JAP1", "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.", "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?\n2. 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?\n3. 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": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Identify several phenomena in large-dimensional spectral algorithms based on the derived rates. These phenomena are also illustrated by figures, making the explanations easy to follow.\n\n2. Discovered the thresholding for igniting saturation effect is different for large-dimensional and fixed-dimensional settings. Specifically, in a large-dimensional setting, the saturation effect occurs when the interpolation index exceeds the qualification, whereas in a fixed-dimensional setting, it must be more than twice the qualification.", "weaknesses": "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]. \n   \n   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.\n   \n   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.\n\n2. 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. \n\n\n[1] Lu, Weihao, et al. \"Optimal rate of kernel regression in large dimensions.\" _arXiv preprint arXiv:2309.04268_ (2023).\n\n[2] Zhang, Haobo, et al. \"Optimal Rates of Kernel Ridge Regression under Source Condition in Large Dimensions.\" _arXiv preprint arXiv:2401.01270_ (2024).\n\n[3] Zhang, Haobo, et al. \"On the optimality of misspecified kernel ridge regression.\" _International Conference on Machine Learning_. PMLR, 2023.\n\n[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.\n\n[5] Li, Yicheng, Haobo Zhang, and Qian Lin. \"On the Saturation Effect of Kernel Ridge Regression.\" International Conference on Learning Representations. (2024)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review and valuable comments. Below, we address your concerns and questions in detail.\n\nConcern 1: Please let us clarify our novelties and contributions below.\n\n- Although the saturation effect has been observed for kernel ridge regression in a large-dimensional setting [2], its persistence for other spectral algorithms was unclear. We determine the exact rate of excess risk for analytic spectral algorithms with qualification $\\tau$. Key outcomes include:\n  - Kernel gradient flow is minimax optimal in large dimensions, with an excess risk rate of $d^{-\\min(\\gamma-p, s(p+1))}$.\n  - We proved the saturation effect for large-dimensional KRR when $s>1$ and for spectral algorithms with $\\tau$ when $s>\\tau$.\n\nRegarding your concerns on the technical contributions:\n- [3][4] addressed the convergence rate for fixed-dimensional spectral algorithms when $0<s\\leq 2\\tau$, focusing on non-saturated cases where KRR and kernel gradient flow are rate-optimal. In contrast, they did not consider the saturation effect of spectral algorithms when $s > 2\\tau$.\n- [1] determined the minimax rate of kernel regression for $f \\in [\\mathcal{H}] ^ s$ where $s=1$. The proof in [1] relies heavily on empirical process theory, requiring bounds on the empirical loss and its difference from the expected loss (excess risk). This approach does not generalize to cases where $s \\neq 1$.\n- [2] provided a minimax lower bound for $s>0$ using integral operator techniques for KRR, hinting at a saturation effect but not generalizing to other spectral algorithms.\n\nWe extended results to general spectral algorithms in large dimensions using complex variable analysis (Appendix E.1 and [6]) to match upper and lower bounds. Large dimensions introduce unique challenges:\n  - The polynomial eigendecay assumption that $\\lambda_j \\asymp j^{-\\beta}$ does not hold in large dimensions, since the hidden constant factors in the assumption vary with $d$.\n  - The embedding index assumption in [6] does not hold either. We develop a new condition in (63) and (74) to replace the embedding index assumption, and we verify this new condition in Appendix D.4.\n\nWe believe our contributions are novel and valuable for the machine learning community, meriting publication at NeurIPS.\n\n**Reference: [6]** Li, Yicheng, et al. \"Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decay.\"\n\n---\n\nConcern 2: Thank you for your suggestion. We agree that conducting thorough numerical investigations can be challenging due to the extremely large dimensionality $d$. Following your recommendation, we conducted two preliminary experiments. We will follow your advice to conduct more comprehensive experiments later and report the results in the updated manuscript.\n\n---\n\nQuestion 1: In this paper, we consider the asymptotic framework $n \\asymp d^\\gamma$ with $\\gamma>0$. As discussed in lines 97-115, many studies focus on the performance of spectral algorithms within this asymptotic framework. By comparing our work with these studies, we highlight the novelty and contributions of our results to the field. In contrast, we were not aware of similar studies under ultra-high-dimensional settings, hence we did not explore this scenario in our manuscript.\n\nYour insightful suggestion implies that this could be an interesting avenue for future research. When $n \\asymp d^{\\gamma}$ and $\\gamma$ is sufficiently small, the excess risk in our results is of rate $d^{-\\gamma}$. If we consider $\\log(d)$ as a limiting case of $d^{\\gamma}$, we might conjecture that the correct rate of the excess risk when $n \\asymp \\log(d)$ is $\\log^{-1}(d)$.\n\nWe believe your suggestion is promising, and we will consider conducting a similar analysis under ultra-high-dimension settings in future work.\n\n---\n\nQuestion 2: Thank you for your question. We guess that there might be some typos in your expression, and we guess that you wanted to state the distinction between our results and existing results in fixed-dimension settings as follows:\n- Our results, Theorems 4.1 and 4.2, demonstrate that the saturation effect occurs in large-dimensional settings if and only if $s > \\tau$. In Figure 2 (on page 13), we illustrate this with the spectral algorithm rate (blue line) and the minimax rate (orange line). The blue and orange lines exhibit non-overlapping regions if and only if $s > \\tau$. Therefore, Figure 2 aligns with our claims.\n- In contrast, in fixed dimension settings, the saturation effect occurs if and only if $s > 2\\tau$.\n\nThen let us provide you with some intuition behind the consequence of the derived rate. We highlight that the periodic behavior of the rates with respect to $ \\gamma $ in Theorem 4.1 and 4.2 is closely related to the spectral properties of inner product kernels for uniformly distributed data on a large-dimensional sphere. In Lemmas D.11 and D.13, we show that $\\mu_k= \\Theta(d^{-k})$ and $N(d, k) = \\Theta(d^{k})$ for $k \\leq p+1$. Moreover, recall that the leading terms for the bias and variance are given by $M_{2, \\varphi}(\\lambda) + \\frac{\\sigma^2}{n} N_{2,\\varphi}(\\lambda)$ (see Appendices D.1-D.3). Therefore, by comparing between $M_{2, \\varphi}(\\lambda)$ and $\\frac{\\sigma^2}{n} N_{2,\\varphi}(\\lambda)$ (with calculations detailed in Lemma D.14) under the strong block structure of the spectrum, we found that the rate of excess risk behaves periodically for each period $\\gamma \\in [p(s+1),(p+1)(s+1))$, $p = 0, 1, \\cdots$, and that the saturation effect occurs when $s > \\tau$.\n\n---\n\nQuestion 3: The intervals $[p(s+1),(p+1)(s+1))$, $p=0, 1, \\cdots$ naturally from our derivation process. Thus, we may focus on $\\gamma\\in [p(s+1),(p+1)(s+1))$. Regarding your second question about why this ratio is an integer, we are not entirely certain whether you are referring to the constant $\\gamma$ or the integer $p=\\lfloor\\frac{\\gamma}{s+1} \\rfloor$. For further clarification, please let us know.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Vapd38MTh0", "reviewer": "Reviewer_XV4b", "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.", "questions": "I appreciate the result of this paper and hence look for any possible extension from the current result.\n\nThis paper focuses on dot-product kernels $K=\\Phi(\\langle \\cdot, \\cdot \\rangle)$ with inputs distributed uniformly on a hypersphere and with polynomial spectral decay. \n\n1. 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?\n\n2. 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?\n\nAlso, I have some technical questions concerning the appendix.\n\n3. 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)?\n\n4. 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?\n\nReference:\n- 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).\n- Belkin, Mikhail. \"Approximation beats concentration? An approximation view on inference with smooth radial kernels.\" Conference On Learning Theory. PMLR, 2018.", "limitations": "All assumptions and conditions are stated clearly in the paper.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper offers solid theoretical results which improve over previous literature or reveal novel phenomenon. It offers important insights on spectral algorithms in large input dimensional setting, for example the interpolation (with different qualification $\\tau$) of the learning rate between KRR and KGF, the exact description of the phenomena *periodic plateau behaviour* and *polynomial approximation barrier*.\nThis paper also offers numerical validations on their claim.", "weaknesses": "There is no major weakness spotted in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for taking the time to read our paper and for providing valuable feedback. We are pleased to see that you not only accurately described the contributions of our work but also gave it high praise. We would like to address the questions and comments you raised regarding possible extensions of our research.\n\n**Author's response to Question 1:**\n\nThank you for suggesting checking our assumptions on two specific kernels. After a careful check on the paper [Belkin2018] and [Haas2024], we find that $\\Phi$ for both ReLU-NTK and the Gaussian kernel are analytic, with all coefficients $a_j>0$, thus satisfying Assumption 1. Therefore, the results of this paper apply to both ReLU-NTK and the Gaussian kernel. Please let us clarify in detail:\n\n- From the definition of ReLU-NTK in [Bietti2021], $\\Phi$ for ReLU-NTK is analytic (see, e.g., page 6 in [Bietti2021]). Moreover, Corollary 3 of [Bietti2021] as well as Lemma B.2 of [Haas2024] both imply that we have all coefficients $a_j>0$. Notice that the proof for the positive-definiteness of the kernel in the above studies relies on [Gneiting2013], hence they also require that $\\Phi$ is analytic.\n\n- From the definition of the Gaussian kernel defined on the sphere, we can show that $\\Phi$ for the Gaussian kernel is analytic, with all coefficients $a_j>0$.\n\nSince both kernels satisfy Assumption 1, we have the following claims:\n\n- You are right. When $d$ is fixed dimensions, [Bietti2021] showed that the eigenvalues of ReLU-NTK satisfy $ \\mu_k \\asymp k^{-d} $ and $ N(d, k) \\asymp k^d $ for large $k$, leading to $\\lambda_j \\asymp j^{-\\beta}$ with $\\beta = (d+1)/d$; whereas it is known that the eigenvalues of the Gaussian kernel defined on sphere decay exponentially (see, e.g, [Amnon2020]). Therefore, we may need different tools to deal with the rate of the excess risk of fixed-dimensional spectral algorithms with ReLU-NTK and the one with the Gaussian kernel.\n\n- In large dimensions, the spectra of both ReLU-NTK and the Gaussian kernel exhibit a strong block structure as follows: $ \\mu_k = \\Theta(d^{-k}) $ and $ N(d, k) = \\Theta(d^{k}) $ for $ k \\leq p+1 $ (see, e.g., Lemmas D.11 and D.13). Therefore, our results hold for both ReLU-NTK and the Gaussian kernel in large dimensions without any adaptation.\n\n---\n\n\n**Author's response to Question 2:**\n\nWe agree that a uniform input distribution on spheres is too restrictive. As noted in Remark 2.1, most studies analyzing spectral algorithms in large-dimensional settings concentrate on inner product kernels on spheres for two main reasons:\n\n- Firstly, harmonic analysis on the sphere is clearer and more concise. For example, the properties of spherical harmonic polynomials are simpler than those of orthogonal series on general domains. This clarity makes Mercer’s decomposition of the inner product more explicit, avoiding several abstract assumptions.\n\n- Secondly, there are few results available for Mercer’s decomposition of kernels on general domains, especially when considering the domain’s dimension. For example, no results determine the eigenvalues of Sobolev space in large dimensions.\n\nThus, if we believe that large-dimensional KRR and KGF exhibit some new phenomena, it would be prudent to start with a more tractable setting, and then extend the results to general domains.\n\nRegarding your second question, thank you for bringing up the interesting work [Haas2024] and suggesting an extension of our analysis. We believe that the results in [Haas2024] can indeed be extended to large-dimensional settings, although we must carefully consider the constants that depend on $d$. For example, the density in Lemma D.7 of [Haas2024] is lower and upper bounded by two constants depending on $d$.\n\nWe appreciate your insightful suggestion. We will add the paper [Haas2024] to the discussion section of our manuscript, and we will consider extending our results to general domains in future work.\n\n---\n\n\n**Author's response to Question 3:**\nThank you for pointing out the potential issue in Eq (62). We have revised our manuscript and updated Eq (62) to the following version :\n$$\n\\frac{ N_1 (\\lambda) M_{1, \\varphi}^2 (\\lambda)}{n^2} = o( M_{2, \\varphi} (\\lambda) + \\frac{\\sigma^2}{n} N_{2,\\varphi} (\\lambda) );\n$$\nMoreover, we followed your suggestion and added a rigorous definition of $o(1)$ in our manuscript: We say two (deterministic) quantities $U(d), V(d)$ satisfy $U(d) =  o(V(d))$ if and only if for any $\\varepsilon > 0$, there exists a constant $D_{\\varepsilon}$ that only depends on $\\varepsilon$ and the absolute positive constants $\\sigma, \\kappa, s, \\gamma, c_0, c_1, c_2, C_1, \\cdots, C_8 > 0$, such that for any $d > D_{\\varepsilon}$, we have $U(d)< \\varepsilon V(d)$.\n\nWe hope that the updated definitions clarify that Eq (62) is correct when $\\sigma>0$ is an absolute constant defined in (1).\n\n---\n\n\n**Author's response to Question 4:**\n\nThank you for your careful reading of our proof and for pointing out the typo in Eq (42). We will correct it in the updated manuscript. Regarding your comment about Eq (44), we believe it is not redundant. In Eq (44), $\\varphi_{\\lambda}$ refers to the filter function of a specific spectral algorithm (not necessarily KRR), while $\\varphi_{\\lambda}^{\\text{KRR}}$ in (43) specifically denotes the filter function for KRR.\n\n### Reference:\n- Alberto Bietti and Francis Bach. \"Deep equals shallow for ReLU networks in kernel regimes.\" In International Conference on Learning Representations (ICLR), 2021.\n- Tilmann Gneiting. \"Strictly and non-strictly positive definite functions on spheres.\" Bernoulli, 19(4): 1327–1349, 2013.\n- Geifman, Amnon, et al. \"On the similarity between the Laplace and neural tangent kernels.\" Advances in Neural Information Processing Systems 33 (2020): 1451-1461.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Following the recommendation of the Reviewer JAP1, we conducted two preliminary 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:

1. **RBF kernel with a fixed bandwidth:**

   $$
   K^{\mathrm{rbf}}(x,x^{\prime}) = \exp{\left(-\frac{\|x-x^{\prime}\|_{2}^{2}}{2}\right)}, ~~x, x^{\prime} \in \mathbb{S}^{d}.
   $$

2. **Neural Tangent Kernel (NTK) of a two-layer ReLU neural network:**

   $$
   K^{\mathrm{ntk}}(x, x^\prime) := \Phi(\langle x, x^{\prime} \rangle), ~~x, x^{\prime} \in \mathbb{S}^{d},
   $$

   where $\Phi(t)=\left[\sin{(\arccos t)}+2(\pi-\arccos t)t\right]/ (2 \pi)$.

The RBF kernel satisfies Assumption 1. For the NTK, the coefficients of $\Phi(\cdot)$, $(a_{j}) _ {j=0} ^ {\infty}$, satisfy $a_{j} > 0, j \in \{0, 1\} \cup \{2,4,6,\ldots\}$ and $a_{j} = 0, j \in \{3,5,7,\ldots\}$ (see, e.g., [Lu2023]). As noted after Assumption 1, our results can be extended to inner product kernels with certain zero coefficients $a_j$. Specifically, for any $\gamma>0$, as long as $a_{j} > 0$ for $j = \lfloor \gamma \rfloor, \lfloor \gamma \rfloor+1$, the proof and convergence rate remain the same. Therefore, for $\gamma<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}) + \epsilon_{i}, ~~ i = 1, \ldots, n,
$$

where each $x_{i}$ is i.i.d. sampled from the uniform distribution on $\mathbb{S} ^ {d}$, and $\epsilon_{i} \overset{\text{i.i.d.}}{\sim} \mathcal{N}(0,1)$.

We selected the training sample sizes $n$ with corresponding dimensions $d$ such that $n = d^{\gamma}, \gamma = 0.5, 1.0, 1.5, 1.8$. For each kernel and dimension $d$, we consider the following regression function $f_{*}$:

$$
f_{*}(x) = K(u_{1},x) + K(u_{2},x) + K(u_{3},x), \quad \text{for some}\quad u_{1}, u_{2}, u_{3} \in \mathbb{S}^{d}.
$$

This function is in the RKHS $\mathcal{H}$, and it is easy to prove that, for any $u \in \mathbb{S} ^ {d}$, Assumption 2 (b) in our revision holds for $K(u, \cdot)$ 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$. 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) = \sqrt{\mu_2^{s}N(d, 2)} P_2(\langle \xi, x \rangle)$ with $s=1.9$, $P_2(t) := (d t^2-1)/(d-1)$ the Gegenbauer polynomial, and $\xi \in \mathbb{S}^{d}$. Notice that the addition formula $P_2(\langle \xi, x \rangle) = \frac{1}{N(d, 2)}\sum_{j=1}^{N(d, 2)}Y_{2, j}(\xi)Y_{2, j}(x)$ implies that 

$$
||f_{*}|| _ {[\mathcal{H}] ^ {s}}^2 = \frac{1}{N(d, 2)} \sum _ {j=1} ^ {N(d, 2)} Y_{2, j} ^ 2 (\xi) = P _ 2(1) = 1,
$$

hence $f_{*} \in [\mathcal{H}]^{s}$ and satisfies Assumption 2.

Our experiment settings are similar to those on page 30 of [5]. We choose the regularization parameter for KRR and kernel gradient flow as $\lambda=0.05 \cdot d^{-\theta}$. For KRR, since Corollary D.16 suggests that the optimal regularization parameter is $\lambda \asymp d^{-0.7}$, we set $\theta=0.7$. Similarly, based on Corollary D.16, we set $\theta=0.5$ for kernel gradient flow. Additionally, we set $\gamma = 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.

### References

- Lu, Weihao, et al. "Optimal rate of kernel regression in large dimensions." arXiv preprint arXiv:2309.04268 (2023).

- Li, Yicheng, Haobo Zhang, and Qian Lin. "On the Saturation Effect of Kernel Ridge Regression." International Conference on Learning Representations. (2024)

Meta-review: 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.
Decision: Accept (poster)