Learning Curves of Stochastic Gradient Descent in Kernel Regression
Authors: Haihan Zhang
Weicheng Lin
Yuanshi Liu
Cong Fang
Venue: ICML 2025 poster (2025)
Keywords: Stochastic Gradient Descent
Large Dimension
Minimax Optimality
Primary area: optimization->stochastic

Abstract: This paper considers a canonical problem in kernel regression: how good are the model performances when it is trained by the popular online first-order algorithms, compared to the offline ones, such as ridge and ridgeless regression? In this paper, we analyze the foundational single-pass Stochastic Gradient Descent (SGD) in kernel regression under source condition where the optimal predictor can even not belong to the RKHS, i.e. the model is misspecified. Specifically, we focus on the inner product kernel over the sphere and characterize the exact orders of the excess risk curves under different scales of sample sizes $n$ concerning the input dimension $d$. Surprisingly, we show that SGD achieves min-max optimal rates up to constants among all the scales, $without$ suffering the saturation, a prevalent phenomenon observed in (ridge) regression, except when the model is highly misspecified and the learning is in a final stage where $n\gg d^\gamma$ with any constant $\gamma >0$. The main reason for SGD to overcome the curse of saturation is the exponentially decaying step size schedule, a common practice in deep neural network training. As a byproduct, we provide the $first$ provable advantage of the scheme over the iterative averaging method in the common setting.

Learning Curves of Stochastic Gradient Descent in Kernel Regression
Haihan Zhang" *1
Weicheng Lin
Yuanshi Liu Cong Fang
Abstract
est in kernel methods driven by the neural tangent kernel (NTK) theory (Jacot et al., 2018; Arora et al., 2019), which states that sufficiently wide neural networks, under specific initialization, can be well approximated by a deterministic kernel model derived from the network architecture. Though deep learning often operates in regimes beyond the tradi- tional statistical mindset, recent advances demonstrate that these generalization mysteries are not peculiar neural net- works and the phenomena are also present in kernel regres- sion, particularly in the high-dimensional regime (Ghorbani et al., 2021; Liang & Rakhlin, 2020; Zhang et al., 2024b).
This paper considers a canonical problem in ker- nel regression: how good are the model perfor- mances when it is trained by the popular online first-order algorithms, compared to the offline ones, such as ridge and ridgeless regression? In this paper, we analyze the foundational single- pass Stochastic Gradient Descent (SGD) in kernel regression under source condition where the opti- mal predictor can even not belong the RKHS, i.e. the model is misspecified. Specifically, we focus on the inner product kernel over the sphere and characterize the exact orders of the excess risk curves under different scales of sample sizes n concerning the input dimension d. Surprisingly. we show that SGD achieves min-max optimal rates up to constants among all the scales, without suffering the saturation, a prevalent phenomenon observed in (ridge) regression, except when the model is highly misspecified and the learning is in a final stage where n >> d' with any constant y > O. The main reason for SGD to overcome the curse of saturation is the exponentially decaying step size schedule, a common practice in deep neural network training. As a byproduct, we pro- vide the first provable advantage of the scheme over the iterative averaging method in the com- mon setting.
Substantial studies have been made in the related regimes for kernel ridge or ridgeless methods. For instance, Liang & Rakhlin (2020) demonstrates the existence of benign overfitting for ridgeless regression, a phenomenon where the model interpolates data yet still generalizes well. In large-dimension regime where x d, Ghorbani et al. (2021) provably shows the double descent phenomenon. In more general regimes, Zhang et al. (2024b) characterizes the exact orders of the excess risk curves, i.e., learning curves where the sample size scales polynomially with the input dimension n d' with y > 0 and elaborates the interplay of the regularization parameter, 7 and the source condition.
On the other hand, in practice, dominant algorithms are implemented in an online fashion to reduce computation costs, with iterative updates relying on stochastic gradients (single-pass or minibatch) as estimates of the population counterpart. Stochastic gradient descent (SGD), one of the foundational online algorithms, admits the simplest updates and receives abundant theoretical analysis in general opti- mization. However, its learning dynamics over specific ker- nels remains underexplored. Existing theoretical results are either inapplicable or leave room for improvement. Specif- ically, the pioncering work of (Dieuleveut & Bach, 2016) considers the optimality of Lingle-pass SGD with iterate averaging, yet their optimality results do not demonstrate clear improvement over ridge regression. Another thread of work analyses single-pas. SGD in the linear regression framework (Jain et al., 2018; Zou et al., 2021b; Wu et al., 2022). Although insightful, their decisive assumption on the concentration effect deviates from that in kernel regression, resulting in entirely different learning dynamics.
1. Introduction
Non- con-parametric caas-- regression within the RKHS framework represents cornerstone of statistical learning theory. One mainstream method to solve the problem is ker- nel ridge regression (KRR) with optimality analysis (Capon- netto & De Vito, 2007; Smale & Zhou, 2007; Zhang et al., 2024a). Recent years have witnessed a renaissance of inter-
'Equal contribution 'Natinnal Key Lab of General Artificial In- lelligence, School of Intelligence Science and Technology, Peking University "Institute Artificial Intelligence, Peking University. Correspondence to: Cong Fang <fangcong @ @ku..du.cn.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
In this study, we investigate a fundamental question to fill

---

Learning Curves of Stochastic Gradient Deseent in Kernel Regression
the abovementioned gap: how does model performance, when trained using popular online first-order algorithms, compare to that of offline ridge and ridgeless regression? We analyze the single-pan pass SGD that incorporates the expo- nentially decaying step size schedule, common practice in deep neural network training (Bengio, 2009; Ge et al., 2019). The analysis is conducted within the framework of kernel regression, considering the source condition that allows for potential model misspecification. We precisely characterize the order of learning curves in the high-dimensional setting, where n = d' with y > 0 treated as a constant. Our focus is on the inner product kernel over the sphere, which encom- passes NTK with ReLu activation as a special case (Bietti & Bach, 2021; Bietti& & Mairal, 2019). For functions satisfying the source condition with s > 0, we establish excess risk convergence rates given by Q miu(==p.s(pt11)) where
specified problems without suffering from the satura- tion effect.
2. Related Work
Kernel Regression. In the asymptotic setting, when n >> d, the eigenvalues of the RKHS kernel often exhibit polyno- mial decay X x i= (Bietti & Mairal, 2019; Bietti & Bach, 2021; Li et al., 2024), which is an extensively studied set- ting in the RKHS framework. Under a source condition of smoothness (which will be specified later in Section 1) Caponnetto & De Vito (2007) establishs a minimax lower bound of n I For offline algorithms,, KRR has been shown to achieve optimality for 0 < 8 S (Caponnetto & De Vito, 2007; Smale & Zhou, 2007: Steinwart et al., 2009; Dicker et al., 2017: Blanchard & Mücke, 2018; Fis- cher & Steinwart, 2020; Lin et al., 2020; Li et al., 2022; Liu & Shi, 2024; Zhang et al., 2024a), but suffers from the saturation effect when $ >> 2 (Neubauer, 1997; Bauer et al., 2007; Dicker et al., 2017; Cui et al., 2021; Li et al., 2023). Gradient descent (GD) with early stopping has been shown to achieve the minimax optimal rate for all 8 > (Yao et al., 2007; Raskutti al., 2014; Lin et al., 2020). Several studies have also revealed connections between the optimal stopping time in early-stopped GD and the regularization in KRR (Ali et al., 2019; Sonthalia et al., 2024). Velikanov et al. (2024) further demonstrates that spectral algorithms with finite qualification t experience saturation and fail to achieve optimality for s > 2r, with only GF with early stopping able to achieve optimality (Raskutti et al.. 2014). For online algorithms, Dieuleveut & Bach (2016) shows that single-pass SGD with constant step size and averaged iterates can achieve optimality for 2-1 < s S 2.
p ]. These derived rates surprisingly match the minimax lower bounds up to constants, thereby establish- ing minimax optimality across all sampling scales in high- dimensional settings and throughout the spectrum of source condition smoothness (Zhang et al., 2024b). Notably, the result circumvents the saturation effect inherent to the KRR the fundamental limitation where it fails to attain optimality for the smooth problems regardless of the ridge regulariza- tion parameter (Neubauer, 1997; Li et al., 2023; Lu et al., 2024b), which persists under the current online analysis.
With the above optimality analysis, two follow-up questions naturally arise. (i) Can the SGD algorithm consistently be optimal across all scalings of n, particularly when liberated from the n dl constraints? (ii) Why can SGD overcome the curse of saturation?
For question (i), the claim does not hold in the asymptotic regime where n >> d": we demonstrate that SGD loses its optimality when the model is highly misspecified. Specifi- cally, our analysis shows that SGD can only reach optimality for s Z+1
In the high-dimensional setting, where n x d', ",, 7 > 0, the eigenvalues of the RKHS kernel decay at a rate that is not polynomial depending on d, leading to the ineffec- tiveness of asymptotic analysis. Recently, several works have investigated the excess risk of offline algorithms in this setting. It has been proven that KRR and kernel gradient flow are capable of achieving convergent excess risk for certain regression functions (Advani et al., 2020; Bordelon et al., 2020; Ghorbani et al., 2021; Donhauser et al., 2021; Xiao et al., 2022; Misiakiewicz, 2022; Tsigler & Bartlett, 2023). Kernel interpolation is shown to exhibit the benign overfitting phenomenon, which allows generalization under certain values of y and (Liang & Rakhlin, 2020; Liang et al., 2020; Bartlett et al., 2020; Barzilai & Shamir, 2024; Zhang et al., 2025). Both the excess risk and minimax rate have been shown to exhibit periodic plateau behavior and multiple descent behaviors in the high-dimensional set- ting (Bordelon et al., 2020; Ghorbani et al., 2021; Xiao et al., 2022; Lu et al., 2023; Zhang et al., 2024b). For the minimax optimality analysis in high-dimensional settings,
For question (ii), we demonstrate that the exponentially de- caying step size schedule serves as the critical mechanism for eliminating the saturation effect. To illustrate our argu- ments, we study a class of SGD with averaged iterates. Our result establishes a lower bound on this scheme, and as a byproduct, firstly demonstrates the provable advantage of decaying step sizes over iterate averaging.
To summarize contribution:
We establish the optimality condition of SGD in both nigh-dimensional and asymptotic settings under the source condition.
We demonstrate the advantages of SGD with expo- nentially decaying step size over iterative averaging methods, highlighting the former's efficiency in well-
2

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
KRR has been demonstrated roughly achieve optimality for 8 S and 7 > 2[ while experiencing saturation effects in the remaining range (Zhang et al., 2024b). Lu al. (2024b) further demonstrates that offline algorithms with finite qualification experience saturation and fail to achieve optimality for s > т, with only gradient flow with early stopping able to achieve optimality for all s > 0 and > 0. However, in nigh-dimensional settings, the excess risk curve and optimality analysis for online algorithms remain an open area of research.
relationship, that is: for any / E H. (J, Af) For any f, 9 H. define the operator g H - H by f & (h) = (f,h) 9.
H S (J,
3s
3.1. Regression in RKHS
We consider the regression problem of minimizing the pre- diction error for a function f E L2, defined as
(f) = Ep (x)
v)² (x)-
SGD over Linear Model. SGD in linear regression has been extensively studied. When the RKHS is finite- dimensional, it has been shown that single-pass pass SGD, with either an exponentially decaying step size or a constant step size with averaged iterates, achieves the minimax optimal rate (a) (Bach & Moulines, 2013; Jain et al., 2018; Ge et al., 2019). In overparameterized linear regression, single- pass SGD exhibits benign overfitting behavior (Zou et al., 2021a;b; Wu et al., 2022), with Zou et al. (2021b) and Wu et al. (2022) establishing excess risk bounds for SGD under both constant step sizes with iterate averaging and exponen- tially decaying step size schedules. These results crucially rely on a fourth-moment condition on the covariates to en- sure sufficient concentration, in addition to depending on the spectral properties of the covariates and the target pa- rameters. Under the source condition with s and polynomial eigenvalue decay of the covariance matrix X; x i-0 Zhang et al. (2024c) showed that SGD with an exponentially de- caying step size can attain the minimax optimal rate for all 2 2=1, For general kernel regression problems, under the source condition with s and the spectrum of the kernel operator that decays polynomially X i- Dieuleveut & Bach (2016); Dieuleveut al. (2017) demonstrated that SGD achieves optimal performance when -سم S 2, while failing to reach optimality and encountering satura- tion for > 2. In the low-regularity regime 8 < a-1 single-pass SGD is limited by its optimization capacity and cannot reach optimality; in such cases, momentum accelera- tion (Zhang et al., 2024c: Diculeveut et al., 2017) or multiple passes over the data (Lin & Rosasco, 2017; Hillaud-Vivies et al., 2018) are required.
where the optimal predictor f (x) = =E, [y|x] achieves the minimal error. The prediction error of f can be equivalently
measured by the excess risk || ff
In this paper, we investigate regression problems within the framework of the Reproducing Kernel Hilbert Space (RKHS) (Berlinet & Thomas-Agnan, 201 I). Let H denote the RKHS associated with a continuous kernel K defined on the input space X. The covariance operator T': L2² - H associated with the kernel K and the marginal distribution px is defined as:
(2) (x) (x).
By Mercer's 's theorem (Aronszajn, 1950; Steinwart & Scovel, 2012),
T
Σ No 11)
1=1
a
K (x,
Σ
Aoos (x) di (y),
where {}:};- are the eigenvalues of T' in non-increasing order, and {6r J are the corresponding eigenfunctions of T which form an orthonormal basis of L Let Kx denote the short hand of the function Kx = ((x,)) -). If the em- bedding operator T : H + L satisfies Ran(T*) C L2, then Σ H. + H defined as Σ E[Kx @ Kx] admits the decomposition of
Σ= Ar /1/xx/////////
3. Preliminaries
Notations. In this paper, we consider the input space X S Rd+1 and the output space y S R, with prob- ability distribution o on X' x y. Let px denote the marginal probability distribution
00
1-1 forming an orthonormal basis of H (Dieuleveut & Bach, 2016).
with (AP
X, Pyjx the condi- tional distribution of y given x. 1a denotes the norm 1f.2 = fx If (x))² dpx (x) where 2 represents the - space La (2',,, px). Denote Sd as the unit sphere in 1 In a Hilbert space H. when A and B are self-adjoint oper- ators, the symbol A < B denotes positive semi-definite
To quantify the regularity of the optimal predictor fa. we introduce the interpolation space [H]] For any s 2 0. the s-th power of T is defined as
T (*) ( (f
3

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
The interpolation space [H]] is defined by
n >> d, the decay rate of the eigenvalues of KYTK is given by
[H]*
Σ acd sb {aili E e
(1)
indicating that the eigenvalues of KNTK decay polynomi- ally. This decay rate is consistent with the standard capacity condition typically employed to assess the optimality of algorithms in the RKHS framework (Caponnetto & De Vito, 2007; Steinwart al., 2009).
with the inner product (/. = (T- 12
3.2. Dot-Product Kernels on the Sphere
dot- dot-product kernel K' is defined as [(x, y) = ((x,y) y)), for any x, E 84, where & E C [-1,1] is fixed func- tion independent of d. The Mercer's decomposition for K (Gallier, 2009) can be written
4. Setup
4.1. SGD for Kernel Regression
leveraging the properties of RKHS, for any function f E
(d.k)
y(x,y) Σ pk Σ j=1
(x)()))
L recall that the prediction error of f is expressed as
Ef) = E, ly - fx))]
k==0
where (Yr,) j==1 are spherical harmonic polynomials of degree and p4,8 are the eigenvalues of K with multiplicity 0) = 1, N(d, k) = 2k+d-1 (k+d-2) for k 2 1.
((d.))
We then employ stochastic gradient descent (SGD) to solve the kernel regression problem. Starting from an initial func- tion fo, the SGD updates are performed recursively as fol- lows:
& (d-1)((k-)))
The smoothness of & E C [-1, 1] and compactness of sd ensure that the dot-product kernel K is bounded kernel. For any dimension d, the dot-product kernel K exhibits the following properties:
fi= n (fi-1(x,) y1) - Kx,
At the I-th iteration, we observe fresh data (x ye) from p. and n) denotes the step size. Assuming the initialization starts from f = 0, fe can be expressed as:
Property 1. There exists O, such that
ft Σ ax
(a) The dot dot-product kernel K bounded, that is suPxex xxx,x) S x².
where (a)) is given by the following iteration, starting from ag 0:
(bb The trace of the covariance operator T is bounded, that is, Lr(T)= S x
Σ Ca,K(xx, (x), -
at -1ft
(c) The marginal probability distribution Px satisfies
E [K (x, Xxx 2 Kx] = x²
When the kernel is chosen as the NTK, the dynamics of SGD for kernel regression exactly coincide with the training process of an infinitely wide neural network under gradient descent (Jacot et al., 2018). For finite-width networks, this correspondence holds approximately in the early training phase (Chizat et al., 2019). In this paper, we investigate two types of step size schedules: an exponentially decaying step size schedule (Bengio, 2009; Ge et al., 2019) and a constant step size with averaged iterates (Polyak & Juditsky, 1992; Dieuleveut & Bach, 2016).
The NTK of a ReLU network with L layers with inputs Sd is specific dot-product kernel (Jacot et al., 2018; Bietti & Bach, 2021), which is defined as
KNTK yx = KiiTK y)).
KNTTK is defined recursively, starting with kt) = n. (t) = f, and for 2 < e
n² (t) = 11 (t)), (1) = NNTK(())s (1)50 (0) (L),
Exponentially Decaying Step Size Schedule. Given total of n iterations, the step size is piecewise constant and decays by a factor after each stage, as defined by
where (t) = 1 ( - arccos(t)) and (t) =
(1 arecos(()) +Vi 12). Let the Mercer decompo- sition of KNTK be KNTK (x,y) E X (x) (y), where {M are the eigenvalues of KNTK in non- increasing order, and [ are the corresponding eigen- functions. As demonstrated in Bietti & Bach (2021), when
if m(e - 1) + 1 1 t ml, n7 = 2
T0
(2)
for 1 < f [log2]], where [log2n] is the total num- ber of stages, and m = ing The final iterate fdee fn considered the output.

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
Constant Step Size with Averaged Iterates. In this schedule, the step size remains constant, and the output is given by the average of the n iterates: fn Er= ft.
4.3. Minimax Lower Bound
The minimax lower bound serves as a fundamental criterion for evaluating statistical optimality in learning algorithms. An algorithm achieves minimax optimality if its worst-case excess risk upper bound matches the corresponding mini- max lower bound over a given function class. Formally, for a family of distributions P and estimators trained on n Denote E(x,y) - (v- (v-1x(x)) Kx the residual of (x, y), where fz (x) can be regarded as the noise of data. To con- trol the interaction between bias and variance in the RKHS, we assume the residual's 's covariance structure satisfies the following assumption.
4.2. Assumptions
4.2.1. DATA NOISE ASSUMPTION
i.d. samples {(x; y:)) the minimax lower bound is defined as:
[x))
| ( l:
inf sup
f pEP
characterizing the irreducible statistical error in the worst- case distributional setting. The minimax lower bound for some kernel methods has been extensively studied (Yang & Barron, 1999; Caponnetto & De Vito, 2007; Lu et al., 2023; 2024a). Below, we now present two key minimax lower bounds under distinet scaling regimes. The first re- sult, adapted from Lu al. (2024a), addresses the high- dimensional setting under source condition with > 0. Proposition 4.7 (Minimax Lower Bound in High-Dimen- sional Setting). In high-dimensional settings, where n is bounded by c,d" < n. < czd" for some fixed ry > O and constants C C22 consider X = The marginal distribu- tion Px is assumed to be the uniform distribution on St. Let K denote a dot-product kernel on the sphere, which satisfies Assumption 4.5. Let P consist of all distributions on X x y given by y = [x + e, where ~ NN (0, 1) is independent of x Suppose Assumption 4.3 holds with O. Let
0 such that the residual E (x.g) satisfies E [E(x,r X Ex.,)) 3 o²Σ and B( 0.
Assumption 4.1. There exists
Remark 4.2. This assumption holds when the data is bounded or fo (x) is sub-Gaussian conditioned on x. It does not require E = x] = O, thus encompassing a broader class of problems. This assumption is also adopted by sev- eral works (Bach & Moulines, 2013; Dieuleveut & Bach, 2016; Dieuleveut al., 2017).
4.2.2. SOURCE CONDITION
The source condition assumes that the optimal predictor J lies within a bounded ball in [H]].
Assumption 4.3. For a given s >> O, we assume that fō belongs to the unit ball in [H]], that is,
1htn we have:
inf sup E. f soll = 2 (a (d-min(o--na---)) f PEP
f [ag- I 1.
Remark 4.4, The source condition serves as a criterion for evaluating optimality in the RKHS framework. It charac- terizes the smoothness of fü: a larger s implies a faster decay of the Fourier coefficients of 1 in I.2, indicating higher smoothness and an intrinsically simpler learning problem. This condition further categorizes the problem settings: 0 < < is called the misspecified problem, and 2 1 is called the well-specified problem.
The second result pertains to the asymptotic setting n >> leveraging the spectral properties of NTK for ReLU net- works and the optimality analysis in Caponnetto & De Vito (2007):
Proposition 4.8 (Minimax Lower Bound in Asymptotic
Settings). In asymptotic settings, where n >> d, consider == The marginal distribution px is assumed to be the uniform distribution S3. Let KNTK the NTK of ReLU network with L layers with inputs on @d. Let P consist of all distributions on X x y given by y fp (x) + where <~ N' (0, 1) is independent of x. Suppose Assumption 4.3 holds with s > 0. Then we have:
4.2.3. ASSUMPTION ON THE DOT- KERNEL
For the digh-dimenssonal settings, where ejd? < n < o2d" for some fixed γ > and absolute constants 01. C22 we adopt the assumption for & as stated in Lu et al. (2023).
inf sup Ep || f pEP
p/ 112
1 (n
e(d+1)
add+1)+a
12
Assumption 4.5. There exists nen-negative sequence of absolute constants {a, ) oo = such that & (1) = E a
5. Main Result
where aj 0 for any [r] +.
5.1. Convergence Rates in High-Dimensiona Settings
Remark 4.6. This assumption is made to maintain the clarity of the main results and proofs, and it can be extended to the NTK as discussed in Lu al. (2023).
We first present the convergence rates of the excess risk for SGD in high-dimensional settings where n. x d'. The-
5

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
orem 5.1 shows that SGD with exponentially decaying step size is efficient for well-specified problems, and Theo- rem 5.2 shows that SGD with averaged iterates is efficient for mis-specified problems.
0 1, supposing that Assumption 4.3 holds with s, and treating 7 o, Ri C1, 02 and as constants, the excess risk of the output of SGD with averaged iterates faeg satisfies:
(i) When y E
some E N, with initial
Theorem 5.1 (Convergence Rate for Well-Specified Prob- lems). In nigh-dimensione settings, where n is bounded by c,d" < n < c2d' for some fixed y > 0 and constants C1 C2 consider X = Sa. The marginal distribution px is assumed to be the uniform distribution on S Let K denote the dot- dot-product kernel on S which satisfies Assumption 4.5. Given s 2 1, supposing that Assumption 4.3 holds with and treating 7; G, K, K,C1. O2 and as constants, the excess risk of the output of SGD with exponentially decaying step size ficee satisfies:
step size ?o = O(d- (p > 0) or do = O $
(p = 0), there exists a constant dg such that for any d 2 do.
we have:
E [I - f/ S <d
(i) When y E (ps + + + + 1] for some E N, with initial step size 1/n = O (d- there exists a constant dg such that for any d 2 do. we have:
E [I 1 f 1 x d=+1))
(i) When 7 E + p s) for some p E N, with initial step size noo = O(d r log, nln d), there exists constant do such that for any d 2 do. we have:
Compared the minimax lower bound in Proposition 4.7, Theorem 5.2 demonstrates that SGD with averaged iterates can achieve optimality for any 7 0 and 0 << s < 1. In contrast, when 0 < 8 Σ and n x d'' Zhang et al. (2024a) shows that KRR only achieves optimality if 2(s+1) This indicates that, for high-dimennsionl problems, SGD has an advantage over KRR when dealing with mis-specified problems.
E [[l 1 S d TP log2 d.
39
(ii) When Y E (ps + p + s, (p + 1)s + + 1] for some E N. with initial step size no pp loga n In d), there exists a constant do such that for any d 2 do, we have:
E [1]
rdee - f11 S (0+1)e
5.2. Convergence Rates in Asymptotic Settings
Compared to the minimax lower bound in Proposition 4.7, Theorem 5.1 demonstrates that SGD with exponentially decaying step size can achieve optimality for any y > and 1. Notably, this theorem illustrates that SGD with exponentially decaying step size does not suffer from the sat- uration effect encountered by KRR when n x dd (Neubauer, 1997; Bauer et al., 2007). Specifically, when n x d', Lu et al. (2024h) shows that if Assumption 4.3 holds with & > 1, the convergence rate of the excess risk for KRR can be bounded from below by
In this section, we present the convergence rates of the excess risk for SGD in asymptotic settings where n >> d. Theorem 5.3 (Convergence Rate for Well-Specified Prob- lems). In asymptotic settings, where n >> d, consider == The marginal distribution px is assumed to be the uniform distribution on Sd. Let KNTK denote the NTK of ReLU network with L layers with inputs on Sd. For 2 1, supposing that Assumption 4.3 holds for with initial step 1 1--(d:1) the excess risk of the output of =(4+14+
size 110 = θ n
SGD with exponentially decaying step size fdee satisfies:
pKRR 8 $:1l3e)
E
E [lI
ddc
ff112a] S log² n SOFiTd
= ( mini
--p, 2
poly (In(d),,
Compared to the minimax lower bound in Proposition 4.8, Theorem 5.3 demonstrates that SGD with exponentially decaying step size can achieve optimality for any >> 1. This further indicates that in asymptotic settings, SGD with exponentially decaying step size does not encounter the saturation effect. In contrast, Cui et al. (2021) and Li et al. (2023) show that if Assumption 4.3 holds with s > 2, the convergence rate of the excess risk for KRR is bounded from below by:
where 3 = min {s, 2}. and no choice of the regularization parameter x = A(d, n) leads to an improvement in the ex- cess risk. This result suggests that when n x d' and s > 1, there exists a region in which KRR fails to achieve optimal- ity. Therefore, for high-dimensional problems, SGD with an exponentially decaying step size matches or outperforms KRR in well-specified problems.
Theorem 5.2 (Convergence Rate for Mis- Mis-Specified Prob- lems). In high--dimensional settings, where is bounded by cid' < n < e2d" for some fixed v >> 0 and constants C1, C22 consider X = -dd The marginal distribution Px is assumed to be the uniform distribution on Sd. Let K denote the dot- product kernel on Sd, which satisfies Assumption 4.5. Given
E (1 PKRR 1
O₂
2d+2
3242
This result suggests that for s > 2, KRR becomes subopti- mal. Consequently, we argue that SGD with exponentially
6

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
decaying step size is more effective for problems where fğ is sufficiently smooth.
implicit regularization effect induced by the exponentially decaying step size. For well-specified problems, the excess risk of SGD with exponentially decaying step size can be approximated as the sum of the bias and variance terms in the population, which are
Theorem 5.4 (Convergence Rate for Mis-Specified Prob- lems), In asymptotic settings, where n >> d, consider X = =S". The marginal distribution px is assumed to be the uniform distribution on Sd, Let KNTK denote the NTK of a ReLU network with L layers with inputs on St. For J+I S 1, supposing that Assumption 4.3 holds for s, with initial step size T/o- = -
Bias ~
)
[ I)
Σ (fo - -fp)
(n
H
the excess risk of the output of SGD with averaged iterates fang satisfies:
Var = 0²
>' nttr
II j=it1
(I- n, 2)
E²
E [1 fA1liA] S n 11(+1++
In the first phase, a constant step size induces exponential shrinkage of the coefficients along the top eigendirections with large eigenvalues. The subsequent decaying step sizes reduce the variance and ensure that the bias does not increase further. Since the coefficients of f along the eigendirec- tions in the well-specified setting exhibit decaying trend with respect to the eigenvalues, SGD implicitly balances the remaining bias and the resulting variance, enabling it to achieve optimality. In contrast, the explicit regularization added in offline algorithms cannot eliminate the impact of the coefficients corresponding to the large eigenvalues on the bias. As a result, these algorithms fail to achieve op- timality when fø is sufficiently smooth. Velikanov al. (2024) and Lu et al. (2024b) further analyze the offline algorithms constructed using certain analytic filter func- tions, which are characterized by qualification 2 1. For high-dimensional settings, the saturation effect of offline algorithms arises when $ 2 T. For asymptotic settings, the saturation effect arises when $ 2 2T. KRR corresponds to the case where 7 and offline algorithms do not exhibit saturation effects only when 7 = oo, which corresponds to the kernel gradient flow with early stopping. Consequently, when dealing with problems where fü is relatively smooth, SGD outperforms most offline algorithms.
Compared to the minimax lower bound in Proposition 4.8, Theorem 5.4 demonstrates that SGD with averaged iterates can achieve optimality for Z+1 S S 1. Unfortunately, in asymptotic settings, SGD with averaged iterates cannot achieve optimality for all mis-specified problems. This is because, in the asymptotic regime, the eigenvalues of the NTK exhibit polynomial decay, making optimization more challenging for fo in mis-specified problems. Due to the limitations in SGI's 's optimization capabilities, optimality 1 can only be achieved within the range s 2 d+1- To achieve optimality over a broader range of problems, the introduc- tion of other techniques such as momentum (Dieuleveut et al., 2017) 7) or multi-pase palli-passssss strategies (Pillaud-Vivia Vivien et al., 2018) is necessary. The differences in generalization perfor- mance of SGD in high-dimensional and asymptotic settings highlight the role of overparamelerriation..
We provide a graphical illustration of Theorem 5.1 and Theorem 5.2 and summary table of the optimality regions of SGD, KRR, and GD with early stopping in Appendix F.
6. Discussion
6.1. SGD is Efficient for Well-Specified Problems
It is worth noting that the implicit regularization effect of SGD allows the excess risk convergence analysis to depend solely on the boundedness of the kemel. This contrasts with offline algorithms, which typically require matrix con- centration results specific to the kernels in use. In fact, as demonstrated in Proposition B.11 in the appendix. we estab- lish a general convergence rate for the excess risk of SGD with exponentially decaying step sizes, which applies to any bounded kernel. It is straightforward to verify that for any RKHS associated with bounded kernel whose eigen- values exhibit polynomial decay, SGD with exponentially decaying step size can achieve optimal performance for well-specified problems. Given this implicit regularization effect exhibited by SGD in well-specified problems, it is reasonable to expect that SGD will also perform effectively when f is a smooth function in a Sobolev space. As dis- cussed in Steinwart & Scovel (2012); Fischer & Steinwart
As demonstrated in Section 5.1, SGD with exponentially decaying step size achieves optimality for all well-specified problems in both high-dimensional and asymptotic settings. This indicates that SGD with exponentially decaying step size is not subject to the saturation effect encountered by offline algorithms such as KRR. The saturation effect refers to a situation where the algorithm fails to reach optimal- ity when fü is sufficiently Neuoth(N, 1997; Bauer et al., 2007: Dicker et al., 2017; Cui et al., 2021; Li et al., 2023). Specifically, this occurs when source condition holds with large value of s, the algorithm results in suboptimal performance. For instance, KRR is suboptimal for s >1 1 in high-dimensional settings (Zhang et al., 2024b) and > 2 in asymptotic settings Li et al. (2023).
The theoretical efficiency of SGD with exponentially de- caying step size for well-specified problems arises from the
7

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
y= 1.5,5=1 1
y= 2.0,5=
y= 2.0,s= 2.0
-10
lifrr -1911ge -121
-30
-02
b -1071pne- 121
-12
-4.
-0.5
-0.3
-12
444
-14
-92
10
33
82
14
25
34
1.2
34
37
13
41
0.1
2.4
25
1g
1g m
1g
(a) d Y 1.5
(b) d = 26 8 0.5
(c) d = 11
Figure 1. Log excess risk decay curves of SGD with the two schedules. The blue curves represent SGD with exponentially decaying step size schedule, and the red curves represent SGD with constant step size and averaged iterates.
(2020). consider RKHS H. as the Sobolev space H" (x)) of order r > 2 a smooth boundary. The integral operator of the associ- ated kernel admits eigenvalues that polynomially decay as X xi= (Stone, 1982). Under such spectral decay, SGD is expected to attain the optimal rate n æनीर. Moreover, holds that [H]" = (X). Given this equivalence, we expect SGD to exhibit similar regularization benefits for Sobolev smooth functions.
For the bound of [|r.ll22. we only require that ||اع|| 1.2 < oo, which holds for mis-specified problems. This condition en- ables us to derive the excess risk convergence analysis for SGD in mis- mis-specified problems. Furthermore, when the kernel has additional properties, such as a bounded kurto- sis for the projection of Kx onto any function f. that is, E Kx) S Il.l we can demonstrate that SGD with exponentially decaying step size achieves the same effec- tiveness in handling mis-specified problems as SGD with averaged iterates.
d where X' S TR is a bounded domain with
6.2. Comparison of Two Types of SGD
Iterate averaging suffers from the saturation effect. SGD with averaged iterates can handle mis-specified problems under Property 1. However, it faces the saturation effect when f is relatively smooth. We prove that the excess risk of SGD with constant step size and averaged iterates can be bounded from below by
Iterafe averaging is effective for mis-specified problems. We primarily use SGD with averaged iterates for mis- specified problems because we only have Property 1. (c) of the kernel. When analyzing the error of the SGD algorithm using the common biri-vari decomposition, it is essen- tial to estimate the residuals between the actual bias f and the population-level bias fú, where
max {(1 - (1 - {cTo)"))(A(n))
1= x
fo
f = (I Kx Kx,) 12-1, f8 fz.
n2ng iEN+
H
j = (I -) P 1, N - lp-
+ 002
1 k*
+ 1
Σ
to0
m/a
16 n
64
For mis-specified problems, when only Property holds, the error for the residual ||-- f may not converge. Fortunately, the following property from Bach & Moulines (2013) supports the convergence of the residuals when using constant step size and averaged iterates.
i=k
where A:" = max (A: : d 2 (164)-1) often referred to as the effective dimension. This implies that the optimization ability of SGD with averaged iterates with respect to the bias is inherently limited by ". When is large, optimality cannot be achieved. As demonstrated in the Appendix E, we show that in high-dimensional settings, when 1, there exists a region where SGD with averaged iterates cannot achieve optimality. Furthermore, in asymptotic settings, SGD with averaged iterates fails to achieve optimality for any $ > 2. This demonstrates that SGD with exponentially decaying step size has an advantage over SGD with averaged iterates when f is relatively smooth.
Pt. (Kx, & Kx. - Σ) Ir-1, the following inequality holds:
Proposition 6.1. Let 9:
1 E. 11 1124 S 2n((1 m)x2))
[E 119:-1112.
E. 11ga 12
+2n² E l|r: 112z2
which implies that E 11 S T- DE En ||re [1:]
8

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
7. Simulations
Ali, A., Kolter, J. Z., and Tibshirani, R. J. A continuous- time view of early stopping for least squares regression. In International Conference on Artificial Intelligence and Statistics, 2019.
In this section, we show our experiments with the NTK kernel < which shows that the convergence rate of SGD matches our theoretical result.
Aronszajn, N. Theory of reproducing kernels. Transactions of the American Mathematical Society, 1950.
The data is generated as follows with fixed fp:
y: = (x,) + C, i = 1,...,
Arora, S., Du, S. S., Hu, W., Li, Z., Salakhutdinov, R. R., and Wang, R. On exact computation with an infinitely wide neural net. Neural Information Processing Sys- lems, 2019.
where vi is i.idd sampled from the uniform distribution on sphere 8 and 6; ~ N (0, 1).
In experiment with = 1, we generate the regression func- tion by:
Bach, F. and Moulines, E. Non-stronglyycoovee smooth stochastic approximation with convergence rate o (1/n). In Neural Information Processing Systems, 2013.
(x))= K (x, un) K(x, u2) + K(x,
where each u, (i = 2,2,3) 3) is ii.d. sampled from the uni- form distribution on sphere $4
Bartlett, P. L., Long, P. M.. Lugosi, G., and Tsigler, A. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 2020.
In experiment with * 1, we retain the settings above but replace the regression function with (x) ug (d, 2) à x),, where P2(x) ب is the Gegenbauer polynomial, and is i.i.d. sampled from the uniform distribution on sphere Sd.
Barzilai, D. and Shamir, O. Generalization in kernel re- gression under realistic assumptions. In International Conference on Machine Learning, 2024.
Bauer, F., Pereverzev, S., and Rosasco, L.. On regularization algorithms in learning theory. Journal of Complexity, 2007.
We conduct these experiments to simulate our results under different high- high-dimensional settings n x d:: (1) ς = 1.5, $ = 1, n from 1000 to 2000, with intervals 200, d = 3 7 7 = 2, = 0.5, n from 1000 to 2000, with intervals n from 1000 to 2000,
Bengio, Y. 2009. doi: 10.1561/2200000066
200, d n (3) 7 1.5, with intervals 200, d = na.
Berlinet, A. and Thomas-Agnan, C. Reproducing kernel
Hilbert spaces in probability and statistics. Springer Science & Business Media, 2011.
We numerically approximate the excess risk by the empirical excess risk on 1000 i.i.d. sampled data from the uniform distribution on the sphere Sd. As shown in Figure 1, the results support our thcoretical findings and indicate that SGD with an exponentially decaying step size does not suffer from the saturation effect.
Bietti, A. and Bach, F. Deep equals shallow for ReLU networks in kernel regimes. In International Conference on Learning Representations, 2021.
Bietti, A. and Mairal, J. On the inductive bias of neural tan- gent kernels. In Neural Information Processing Systems, 2019.
Acknowledgements
This work supported by the NSF China (No.s 92470117 and 62376008).
Blanchard, G. and Mücke, N. Optimal rates for regulariza- tion of statistical inverse learning problems. Foundations of Computational Mathematics, 2018.
Impact Statement
Bordelon, B., Canatar, A., and Pehlevan, C. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning, 2020.
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Caponnetto, A. and De Vito, E. Optimal rates for the regu- larized least- squares algorithm. Foundations of Computa- tional Mathematics, 2007.
References
Advani, M. S., Saxe, A. M., and Sompolinsky, H. High- dimensional dynamics generalization error in neural networks. Neural Networks, 2020.
Chizat, L.,, Oyallon, E., and Bach, On lazy training in differentiable programming. In Neural Information Processing Systems, 2019.

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
Cui, H., Loureiro, B., Krzakala, F,, and Zdeborová, L. Gen- eralization error rates in kernel regression: The crossover from the noiseless to noisy regime. In Neural Information Processing Systems, 2021.
Li, Z.,, Meunier, D., Mollenhauer, M., and Gretton, A. Op- timal rates for regularized conditional mean embedding learning. In Neural Information Processing Systems, 2022.
Dicker, L. H., Foster, D. P., and Hsu, D. Kernel ridge vs. principal component regression: Minimax bounds and the qualification of regularization operators. Electronic Journal of Statistics, 2017.
Liang, T. and Rakhlin, A. Just interpolate: Kernel "ridge- less" regression can generalize. The Annals of Statistics, 2020.
Liang, T., Rakhlin, A., and Zhai, X. On the multiple de- scent of minimum-norm interpolants and restricted lower isometry of kernels. In Conference on Learning Theory, 2020.
Dieuleveut, A. and Bach, F. Nonparametric stochastic ap- proximation with large step-sizes. The Annals of Statis- tics, 2016.
Dieuleveut, A., Flammarion, N., and Bach, Harder, bet- ter, faster, stronger convergence rates for least-squares regression. Journal of Machine Learning Research, 2017.
Lin, J. and Rosasco, L. Optimal rates for multi-pass stochas- tic gradient methods. Journal of Machine Learning Re- search, 2017.
Donhauser, K., Wu, M., and Yang. F. How rotational invari- ance of common kernels prevents generalization in high dimensions. In International Conference on Machine Learning, 2021.
Lin, J., Rudi, A., Rosasco, L.., and Cevher, V. Optimal rates for spectral algorithms with least-squares regression over Hilbert spaces. Applied and Computational Harmonic Analysis, 2020.
Fischer, S. and Steinwart, I. Sobolev norm learning rates for regularized least-squares algorithms. Journal of Machine Learning Research, 2020.
Liu, J. and Shi, L. Statistical optimality of divide and con- quer kernel-based functional linear regression. Journal of Machine Learning Research, 2024.
Gallier, J. Notes on spherical harmonics and linear repre- sentations of Lie groups. preprint, 2009.
Lu, W., Zhang, H., Li, Y., Xu, M., and Lin, Q. Optimal rate of kernel regression in large dimensions. arXiv preprint arXiv:2309.04268. 2023.
Ge, R., Kakade, S. M., Kidambi, R., and Netrapalli, P. The step decay schedule: A near optimal, geometrically de- caying learning rate procedure for least squares. In Neural Information Processing Systems, 2019.
Lu, W., Ding. J., Zhang, H., and Lin, Q. On the Pinsker bound of inner product kernel regression in large dimen- sions. arXiv preprint 240.009900000915, 2024a.
Ghorbani, B., Mei, S., Misiakiewicz, T., and Montanari, A. Linearized two-layers neural networks in high dimension. The Annals of Statistics, 2021.
Lu, W., Zhang, H., Li, Y., and Lin, Q. On the saturation effects of spectral algorithms in large dimensions. In Neural Information Processing Systems, 2024b.
Jacot, A., Gabriel, F., and Hongler, C. Neural tangent kernel: Convergence and generalization in neural networks. In Neural Information Processing Systems, 2018.
Misiakiewicz, T. Spectrum of inner-product kernel trices in the polynomial regime and multiple descent phenomenon in kernel ridge regression. arXiv preprint MrXiv:2204.10455, 2022.
Jain, P., Kakade, S. M., Kidambi, R., Netrapalli, P., and Sidford, A. Parallelizing stochastic gradient descent for least squares regression: Mini-batching, averaging, and model misspecification. Journal of Machine Learning Research, 2018.
Neubauer, A.
On converse and saturation results for Tikhonov regularization of linear ill- ill-posed problems. SIAM Journal on Numerical Analysis, 1997.
Langley, P. Crafting papers machine learning. In Inter- national Conference on Machine Learning, 2000.
Pillaud-Vivien, I.., Rudi, A., and Bach, F. Statistical op- timality of stochastic gradient descent on hard learning problems through multiple passes. In Neural Information Processing Systems, 2018.
Li, Y., Zhang, H., and Lin, Q. On the saturation effect of kernel ridge regression. In International Conference Learning Representations, 2023.
Li, Y., Yu, Z., Chen, G., and Lin, Q. On the eigenvalue decay rates of a class of neural-network related kernel functions defined on general domains. Journal of Machine Learning Research, 2024.
Polyak, B. T. and Juditsky, A. B. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 1992.
10

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
Raskutti, G., Wainwright, M. J., and Yu, B. Early stop- ping and non- con-parametric regression: An optimal data- dependent stopping rule. Journal of Machine Learning Research, 2014.
Zhang, H., Lu, W., and Lin, Q. The phase diagram of kernel interpolation in large dimensions. Biometrika, 2025.
Zou, D., Wu, J., Braverman, V., Gu, Q., Foster, D. P., and Kakade, S. The benefits of implicit regularization from SGD in least squares problems. Neural Information Processing systems, 2021a.
Smale, S. and Zhou, D.-X. Learning theory estimates via integral operators and their approximations. Constructive Approximation, 2007.
Zou, D., Wu, J., Braverman, V., Gu, Q. and Kakade, Benign overfitting of constant-stepsize SGD for linear regression. Conference on Learning Theory, 2021b.
Sonthalia, R., Lok, J., and Rebrova, E. On regularization via early stopping for least squares regression. arXiv preprint arXiv:2406.04425, 2024.
Steinwart, I. and Scovel, C. Mereer's 's theorem on general domains: On the interaction between measures, kernels, and RKHSs. Constructive Approximation, 2012.
Steinwart, I., Hush, D. R., Scovel, C., et al. Optimal rates for regularized least squares regression. In Conference on Learning Theory, 2009.
Stone, J. Optimal global rates convergence for non- parametric regression. The Annals of Statistics, 1982.
Tsigler, A. and Bartlett, P. L. Benign overfitting in ridge regression. Journal of Machine Learning Research, 2023.
Velikanov, M., Panov, M., and Yarotsky, D. Generalization error of spectral algorithms. In International Conference on Learning Representations, 2024.
Wu, J., Zou, D., Braverman, V., Gu, Q., and Kakade, S. Last iterate risk bounds of SGD with decaying stepsize for overparameterrzed linear regression. In International Conference Machine Learning, 2022.
Xiao, L., Hu, H., Misiakiewicz, T., Lu, Y., and Pennington, J. Precise learning curves and higher-order scalings for dot-product kernel regression. In Neural Information Processing Systems, 2022.
Yang. Y. and Barron, A. Information-thhorrtic determina- tion of minimax rates of convergence. The Annals of Statistics, 1999.
Yao, Y., Rosasco, L., and Caponnetto, A. On early stopping in gradient descent learning. Constructive approximation, 2007.
Zhang. H., Li, Y., and Lin, Q. On the optimality of misspec- ified spectral algorithms. Journal of Machine Learning Research, 2024a.
Zhang, H. Li, Y., Lu, W., and Lin, Q. Optimal rates of kernel ridge regression under source condition in large dimensions. arXiv preprint arXiv:2401. 0122700, 2024b.
Zhang, H., Liu, Y., Chen, Q. and Fang, C. The optimal- ity of (accelerated) SGD for nigh-dimensional quadratic optimization, 2024c.

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
A. Basic Properties of the Dot-Product Kernel K
Recall our notation defined in Section 3.1 and 3.2. This section provides some basic properties of the dot-product kernel K.
A.1. Proof of Property
Proof. (a) By the boundedness property of continuous functions, and given that + E c= 1J. we obtain that there exists a constant & > 0 such that
sup ((x) n². ==[0.1]
Since K (x, = T ((xx x)) and (x, x) 1 for any x E X, obtain that
sup K(x x) x) S.? xEx
(3)
(b) By the definition of T, we have
tr(T)) = Σ (or, (o.))o 1=1
20
EE(A @
EE
20
2 ( E(x, Kx)x 1
EK X)
S R2,
where and (iii) follow the reproducing property, and (ii) follows from Parseval's identity.
(c) From (a) and [Kx Kx] Σ, we obtain that
EK (x, x)
Kx Kx]
Kx]
Kx 2 Kx] =
A.2. Covariance Operator T In this section, we prove that Tlx Σ. Based on this, we can express || by (f. E8)n for any f E H in subsequent
sections.
Lemma A.1. The Reproducing Kernel Hilbert Space H. is subspace of L?
Proof. From Property ((a), and given that ||f]| < +oo for any f E H. we have
(II) EE [f(x)]] @ EE K S E[K(x,))IIIII
(II)
S x311fI <
+00,
where (i) follows from the reproducing property, (ii) from the Cauchy-Schward inequality, and (iii) from Property 1(a), along with || +0. This implies that H is subspace of T.2.
Lemma A.2. The restriction of the covariance operator T to H coincides with E.
Proof. Recall that (ʃ @ g)hgh (S, H..
Thus for any function f E H. and any z E X, we have
E K (x, 2) (x) = =E [[KKx, J'x Kx (2)) = @ Kx)(())= (E/)
where in the first equality, we use the reproducing property of H. This equation can be cquivalently expressed as
(z) / (x) (x, (x, (x),
whose form is the same as the definition of T'.
That is to say, the restriction of T HL coincides with Σ.
12

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
A.3. Eigenvalue Decay Rate of the Dot-Product Kernel K
We borrowed the following lemma from Ghorbani et al. (2021) and Lu al. (2023):
Lemma A.3. Suppose n x d² Assumption 4.5 holds. Suppose p > O is any fixed integer. There exist C, C₁ C2 C3 C4 > that depend on P. such that for any d > C, we have
Cid k S ph S O2d
p 1; = 0, p
k = 0, 0, P ++ Czd S (((, S Cad
B. General Bound for SGD with Exponentially Decaying Step Sizes in Well-Specified Problems
B.1. Bias- Variance Decomposition
Our goal is to minimize the prediction error
E,( = -
(4)
using the stochastic gradient oracles. Minimizing the prediction error in (4) is equivalent to minimizing the excess risk, given by
-()) = = 5
where f2 (x) Ep [y|x] denotes the optimal predictor in I For well-specified problems, the source condition 4.3 assumes that f [H]* for 1, which implies S E H. By Lemma A.2, the excess risk can be equivalently expressed as
E [olle = B ( E2 E(S [5)))
The iterative update of SGD given by
1 Jo-1 + ne(ve [x) fo = O,
where 7/2 E R is the step size at iteration t, and (x,, ve) is fresh data from We write the update rule of fc - J in the recursive form:
ft -I- Kx, @ Kx 1 + +m
where E, (y/+ (x:) represents the residual (xr, y).
We first apply the commonly used bias-variance decomposition, expressing f. f as as bias term, which demonstrates the decline of the initial error, and fr stands for the variance term, capturing the influence of the noise. Their recursive updates are given by:
ft ff stands for the
1 = (I T4. Kx, @ Kx) = So Sg.
(5)
fr = =I -I Kx, & Kz, )F- + ME fö 0.
(6)
Consequently, the excess risk admits a decomposition as stated Lemma B.I. Lemma B.1 (Bias-Variance Decomposition). For any iteration t, we have
E
(fe f f2. E(, f3)) f())
Proof. By Lemma A.2, we have
( + fr, E ( + f()) = =115t f: 12
= -
(f', Efi = 1/
1
13

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
By Minkowski's Inequality, we have
|| A'llis S (IINIIA)) (1rRBE))) s (1..)1 + +1151122)
Consequently, by the decomposition ft fp. it follows that
IE [Je fp. E(ʃe = -2 +2))
=
(2 +BISE MfT)))
Then we can bound the excess risk by bounding E [12) Eft R] and E( xl. respectively.
Our second effort isolate the stochastic effect analyzing the concentration effect of the data-dependent operator Kx, @ Kx, its population counterpart Σ.
We decompose the bias f into two terms: ft + St. (b(1) where fo describes the expected behavior and is recursively defined as
= (I- fo
St quantifies the deviation of empirical fluctuations from jt. Its recursive form follows
((1)
f ft ftt
= (I nr.., 2 - f
= (I nx,x, @ 1x, 1 (I- 1)
(Ji-1 - -
= (I 1) (+ + T/| (E Kx @ Kx )/-1
Summarizing, we have
b(1) = (I Σ) ( + iΣ - Kx @ Kx, Kx, M fo (2))) = =0
Similarly, we split the variance ft into two components: dynamics and is recursively defined as:
fr = ft + (1())
where fr captures the expected variance
- + m= fc 0.
Meanwhile, (2( accounts for deviations of empirical fluctuations from fr. following the recursion
fe ((L) = - f 7 Kx. & Kx)fE fo fe(1) O.
(8)
To bound IE (Lf,) Lemma B.2. For any iteration t, we have
n and E [KfT. x1 we have the following lemma:
E [ E1 m 2
( E(:)
+E (
6(1) E 1)) 1 + (re 2)((1) 1
H jrx
E KJZ. ΣF 22
E
[jx:
Σイ
#
We omit the proof of the lemma since follows similar argument to that of Lemma B.I. Therefore, have
E [| 1-01122
< 4 ( MP:)
+ ((100)
( )x1 [ Eτ²) 2 + (+ (1e0) 25 1.)
Therefore, we only need to bind these four terms individually the final iteration n.
14

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
B.2. Analysis of SGD with Exponentially Decaying Step Size Schedule
In this section, we demonstrate the analysis of SGD with exponentially decaying step size schedule. The exponentially decaying step size schedule takes the form
do ?e = 2 im - +15 ml, where m and 1 $ [logan]
(9)
log2
B.2.1. POPULATION UPPER BOUND
In this section, we provide the upper bounds for (ih, -))) and E (f%
By unrolling the recursive definitions of fa and fn we obtain the following expressions:
Ph = II 1:2i)
(So - fp); (50=5
fm
II (I n) E, -=
f/1
i=1
The following lemma gives the upper bound of (fh:
Lemma B.3. Consider SGD with exponentially decaying step size schedule defined (9). Suppose that no S X1
Then we
have
( 5
5 (Ge))
logz 11
Σ 1 (fo - f2)
12110
Proof. By the definition of fhx we have
Phr )
[1- [ (So -0), E
II n223)
(So
fo) ( 7
H
(10)
2
n II n1 (fo fg)
Since 7o S 2,2 and 17 S Noo it follows that 0 n 3 I. Moreover, for any i and j. the operators E, I n3 E and E are positive semidefinite, self-adjoint operators and mutually commuting operators. As result, the following operator inequality holds:
T2
m
m II -00))
II [[-- n
[ n R
Σ [I ([(--1>) 1)
(1 -)- - - ~) (11)
Substituting (11) into (10), we have
Ph
E 7b
< ( "M 11,1'²
H
(12)
([
-
-
Σ) | >
(fo 53 12
where the second inequality uses the operator norm bound [f , |TlIl|llH
To bound the operator norm [|TT -
|. we use the inequality
sup (1 - x² < sup exp(-mx)) )x < 05251
2em
05
15

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
which leads the bound
Pr. )
-
- 2e
|
1 (fo - |3) _
(
log2 n1 1u70
)
|| | (fo -fp) |
1-
mi7o
[is 2mzi m
The following lemma gives the upper bound of E
Lemma B.4. Consider SGD with exponentially decaying step size schedule defined in (9). Suppose that S d Then, for any integer k* 2 1, the following bound holds:
E
n2
50 Ei
0²²
((
(1610gá n c²2
16 log,
76
k*
+
k=
+1
Proof. Notice that for any S jj j S n, E, and E are independent. Moreover, under Assumption 4.1, we have E [:]] = 0. Therefore
E & B
Consequently, we obtain the following expression for E
(J Σイ
E (
]
=
Σ 7k II (I (1-n,
E,, Σ Σ
II (1-n;22) 3
1
1=1
j=i+1
==1
j=it1
Σ 1=
tr
II (I (I- 1,,)² j=i+1
EE, O
(13)
vetr
II (I n; /=++1
EE 80 =.]
1=0
where the second equality follows from the mutual independence and orthogonality of each E,, and from the commutativity of the self-adjoint operators I - 71 E.
Under Assumption 4.1 we have EE E E 3 O²E, for any 1 isis n. Therefore, we obtain
(ii [
+00
n
n
Σイ n
S
[I (I-11, Σ)² 11)
Σ
II j=++1
(1 (1-nn) [a-))))))) X2.
split the summation on the RHS into two parts: S k* and k > k*, We then bound each term individually by analyzing the contribution of each eigendirection.
For direction k < k", the inequality
-I- )2)) X2 ( 2m X2 SsSIA m;
(I
πI (1 )=da)) /=+11
2
Yn m <is n.
This leads to the bound:
II (1
2
2 02
Σ
1
(mide)2 o²
Ag.
2
j=i+1
$= m+1
16

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
For direction k k*, we simply use the bound:
+ X s 0²
II j=++
(1 n)Ao))
k= +1
Combining the two bounds, we obtain
m
Nx) 2m
+000
E
ju Σ f
1
(1126))+
+
+ +o²
Σ
n
(14)
7L
m+
k=b++1
For j > m, we note that
7/0
170
170
1/0
f/
S
<
2
2
S
2108 n
I
4n
(15)
2
For j S n m, we use the following inequality to bound (1 A1) 2
2m (n1
sup 0. 21
1
2
x)
sup 05
exp( sxp(=mx)=²
=
=12
2
(16)
em
Finally, substituting (15) and (16) into (14), we have
E
S
0²
Σ
E*
(n-m) m)
2
2
m
170
2
+
o²
to0
n 12
#1
em
4n
k=1
k=k +1
< 2²
4 logg n
n
170
+ 0²
en
log2
4n
k= +1
((
(66 logž n
k*
to0
0²
+
Σ
nn 2
c²
16 loga
n
n
k=
+1
B.2.2. EFFECT OF REPLACING Kx & Kx WITH Σ
In this section, we incorporate the operator Kx @ Kx into the analysis, and provide upper bounds for IE (1,00) EE ()(()
H
and E ( Σ)((1) > 1. These results will be used to provide the upper bounds of the bias term E (J I1 xel the variance term E [ H]
and
Recalling the recursive definitions in (7) and (8), and solving the resulting expressions of f( (b(1)) and ft (,(1)
we obtain
((1)
Σ 171
II (I m)
M fiO) Σ T 1=1
πI (I nn =:0 |=++1
1=1
j=i+1
where
=X(0 (E- Kn, @ Knd Si Ey(U)) E
Kr, 8 K2,) fm
To bound the quantities E (x)) Σイ²(1))
> and E [ WS (1) )x]] { He
We derive upper bounds for the operators
b(1) and E
@ ["] as stated in Lemma B.6 and Lemma B.8.
The following lemma provides a key auxiliary result used in proving Lemma B.6. It shows that E [1]]]]]]]]]] can be uniformly bounded by the initial error Ilfo - 1/ throughout the iteration.
17

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
Lemma B.5, Consider SGD with exponentially decaying step size schedule defined in (9). Suppose that no S a.. Then for any iterafion we have
E [1[5211 - Il ffllbe.
Proof. Firstly, it is obvious that E |118811+ - fl - f/1122
Notice that for any 1 S t S n, Kx, and 1 are independent, then for any 1 S t S n, we have
B [ [
E [I[ [ nx Xx, [b
E [[]/[-11]]] Rr [Vp-1 (Kx, 80 Kx Kxx (.)) + t [[Kx, @ Kx Kx))fi (Kx, @ (x,)5(-1)71]
E [[]]]=11]]]] 2n [Vs EE [[Kx, @ Kxx )1 f/-1m] + ne [ (xx, @ 1xx1 f4-1)1]
S E [112--1 [ + (-27; + V/ x² E (fb-1- Σ 7
where in the inequality, we use E Kx & Kx.] = E and E |K [x, Xx Xx @ Kx,1 1 k²
Since the function g(x) = 2x + x² R² is non-positive for 0 I x S N2 we have 27, + 11 12? - 0.
Therefore, for any S 1. S 71, we have
E [1
s 111 l1
By recursion, for any 0 S t S n, we have
E [1181111]
S 115o 1 1ix
=
The following lemma gives the upper bound of E
Lemma B.6. Consider SGD with exponentially decaying step size schedule defined in (9). Suppose that no S 3. Then for any iteration we have
E D @ x = llfo - 1
Proof. Notice that for any 1 1sts n, Kx, and fh-1 are independent, then we have
b(1)
= E[[E - Kx @ K2, 15 & p2 10-1)(E Kx, & Kx,)
E [(E Kx, 8 Kx E [1 @ p2i)) (Σ Kx 6 Kxx)]
2 E [[152_ - |I| E زي² Σki, @ -xx- Kxi & Kx E + K K(x,,x,, Kx Kxi]
= E [11 11%e| (IE [K (xe, Xx Kr, @ Kx,] -2²)
I fl ( -- >²
< 11/o fo 1
The following lemma provides key auxiliary result used in proving Lemma B.8. It shows that the operator E|SF & fi] can be uniformly bounded by a I with a constant a throughout the iteration.
Lemma B.7. Consider SGD with exponentially decaying step size schedule defined in (9). Suppose that no < 2. Then for any iteration we have
7002
BiS² < MT 3 aT, where a n)
Proof. We prove this by induction.
For the base case, F[f s f8] = 0 3 of naturally holds.
18

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
Suppose that [ @ f8-1]= 3 al. We aim show that the same inequality holds for I.
Notice that for any 15t 1 n., Kx, and fi-1 are independent, then we have
| [/'
B [ 7/6 Xx ( fi-1)(1 Ti xx 00 xxx) + 1 60 E.]
= E [I n xx @ Kx 3 [fii1 s s--1)
1/t Kx @ Kx,) of 8 E.]
3 E [I m Kx, @ Kx I n xx @ Kx,) + _ X E
= aE
[ 27y Kx
@ Kx
1/ K (x, x, Kx, @ kx + क E E E.
Using E [Kx, & Kx,]= = Σ, R E X
Σ and E K (x Kx @ Kx 3 L we have
E [f f a I - 27, Σ + 1)) + N
1 al + 10 2 1AAn )
nt
Since the function g(x) = 2-0x" is monotonically decreasing, we have
2 - 2
2 - 7a
0²
a² a
S 0² - 0
02 8- --=-00 0.
17
170
Therefore, we conclude that
2
Ef & ffl + 1 α
> ニ aI,
770
completing the inductive step. This proves the lemma.
( @ =
The following lemma gives the upper bound of E
Lemma B.8. Consider SGD with exponentially decaying step size schedule defined in (9). Suppose that no < 2. Then for any iteration i, we have
E E (1) @ =X"] 3 Ix where a 2 - 10
10002
Proof. Notice that for any 1 t n, Kx, and fil are independent, then we have
(1) E
E
EE{E Kx, & Kx (fi @ fi-1( Kx, @ Kx.]]
E[ Kx, @ Kx, B [fi- 8 fi-1)] ( Kx, & Kx,)]
3 [ Kx, @ Kx, I Kx, @ Kx,)]
aBIE² EEKi, Kxi -xi xxx E + K (xx, x Kx 8 Kxi]
2 a(k² )²
3 anx Σ.
Then we can bound ( (())) E (2(11)
and E [ fz(() manner similar to Lemma B.4.
We have the following results: Lemma B.9 (Residual Bias Upper Bound). Consider SGD with exponentially decaying step size schedule defined in (9).
Suppose that to0 I min
{ 2 1
x2 X }. Then, for any integer k. 2 1, we have
E (M E
1 s Ilfo - 12
((550gg)
[161033 n e2
n
k'
+
Σ
+00
m
16 16log
n
k= +1
19

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
Proof. Notice that for any i S n, Kx and fi-1 independent. Under Assumption 4.1, have E [ 0. Thus when
have
E
((1)
@ =
= =E
Kx; & Kx,) (Ji @ (2-1) (Σ - Kx, @ Kx,)]
E [E Kx; @ Kx,) (Ji 8 -)1 TF [[E Kx, 8 Kx,)]
0.
Therefore, according to the proof of Lemma B.4, we have
E (1=t)) Efa 1 >x] S 11 fb
logg ((100e2)
(1010g2
16
-
kt
Σ k=k' +1
mox
e2
16 1ogg22
11
n
Lemma B.10 (Residual Variance Upper Bound), Consider SGD with exponentially decaying step size schedule defined in (9). Suppose that t/u S min
k 21 Then, for any integer k 2 1, we have
E
(1a E)e(2))
), 1
S 2 non?" x²
1002
(
16 logg 16logg"
7
k
+
Ton A
62
16 log,
n1
A=
+11
Proof. Notice that for any when j, we have
< 1 < n, Kx, and fi-1 are independent. Under Assumption 4.1, we have E [[=:] = 0. Thus,
E 3
| = = - Kx. Kx.) (fi @ fÿ-1) (Σ Kx, 2 Kxx)] E [[E Kx Kx;) (Ji-1 @ أy-1) E [ Kx; 8 Kx,)]
Therefore, according the proof of Lemma B.4, we have
E (Fa()) E)a())
1 - 2 noxk
7oo2
x²
(
[16logā
1
2
k-
+
Σ
min
e²
16 log, n1
k=
+1
Combining Lemma B.1, B.2, B.3, B.4, B.9 and B.10, we have the following proposition:
Proposition B.11 (Upper Bound for SGD with Exponentially Decaying Step Size Schedule). Consider SGD with expo- nentially decaying step size schedule defined in (9). Suppose that Tjo I min have
2 R }. Then, for any integer k*
we
E [11h- 1ol122]
5 54 (4)))
(log2 n 117/o
1 | (fo
40²
(
16 [66ogg]
1o
k²
+
Σ
mun x
e2
16
logg n
n
Am k
++
ff + [15o (1.60 (1150-1 fz
?10022²
) ((
16 16log3 n e2
h=*
+o0
12
+
vnn X
2 - m0m
16 logg
n
R=
20

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
C. General Bound for SGD with Averaged Iterates
In this section, we demonstrate the analysis SGD with averaged iterates, which is:
n-1 n2 Σ ft.
0A A0 n, Tr = To with fn
In this section, we need address the misspecified setting, where fo may not lie in H. Specifically, consider the case where the source condition 4.3 holds with some 0 < S 1. To accommodate this broader setting, we extend the operator framework developed in Appendix B.1 to act on functions outside of H. Following Dieuleveut & Bach (2016), define Xx @ Kx I
by Kx Xx o f = Kx This extension satisfies that Xx @ Kx1æ = Kx @ Kx and Kx T. For notational simplicity, we will continue write Kx & Kx instead of Kx Kx and denote its
Kx
Σ / in the following. With these conventions, the notation used in this section remains fully consistent with that of Appendix B.1. For convenience, we defined
expectation by E. Additionally, denote (f, Σ5 by
M= 1 JH
6(1)
(2(1)
(()
n
t=0
0=0
t=
By Lemma B.I, B.2 and Minkovski inequality, we have
(Ta - fo: Σ Jn [p))m
2ツ E [f: + E (MOO)
> + EE (fa E5: , 1):(0)))
which means we only need to bound these four terms individually.
The following analysis based on Dieuleveut & Bach (2016), which provides the following results:
Lemma C.1 (Population Bias Upper Bound). Consider SGD with averaged iterates defined in (17). Suppose that no 3/-
Then we have
1
Σ
(I- - 15) min (s.2 (s.2)
Σ - (So
87) 1
(17)
n
i=0
Lemma C.2 (Residual Bias Upper Bound). Consider SGD with averaged iterates defined in (17). Suppose that no S
min R X 1 Then, for any integer k 2 we have
$1²
E (b
b(1)
nox
1
n- Σ (I - 1) - (mo2)"
| (So- (55-55)6 15)1
<
Tá
(18)
2x²
Σ 1-a (fo - ff) 1z
<
Tox
(s,11ss
H
Meanwhile, Dieuleveut& Bach (2016) provides the following expression E
[ix: Esa H
which is
2
カ-
n-1
E
Σ
Th j=1
7)
(19)
74
n
Lemma C.3 (Population Variance Upper Bound). Consider SGD with averaged iterates defined in (17). Suppose that Noo < N. Then, for any integer k* > 1, we have
+
5
0
Tuni
H
i 1=*
21

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
Proof. According the form in (19), we have
E
12
E
(1-
[I -
H
16
R-
n-1
E
tr
Σ 7
Σ - 1-
ME, 8
n1
n-1
Σ
Σ I
3E
n²a
where in the second equality, we use the commutativity of each I - 2, and from the fact that for any Si j S n, 3,
and E, are independent, and under Assumption 4.1 EE [ = O.
Using the property that for any S i < n,
E
E 3
Σ, we have
E
S
lr
Σ
Σ
(I- - E)- E²
n
Similar to the proof of Lemma B.4. we split the summation on the RHS into two parts: S k- and ls >> k* The resulting upper bound is summarized in the following:
2
E
n
%
Σ (1
-oo
X
n
+00
(1 7)
Σ
(1 (1 modn)))²
n
k= +1
j=1
(imodaa)
n
n2 j=1
toc
2
non
X
n
k= +1
where in the second inequality, we use nx S (1 - x)" S 1 for any < x < and n N.
Besides, we have the following lemma: Lemma C.4 (Residual Variance Upper Bound). Consider SGD with averaged iterates defined in (17). Suppose that No < min
2 x 3,} Then, for any integer k** 2 1, we have
b+
E
(1((
222
Σ
mm
H
2
k=
We omit the proof since it follows a similar argument to that of Lemma 10 Combining Lemma C. C.2, C.3, and C.4, we have the following corollary.
22

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
Corollary C.5 (Upper Bound for SGD with Averaged Iterates). Consider SGD with averaged iterates defined in (17).
X1 }. Then, for any integer k* 2 1, we have
Suppose that no & min
h +
E [15m - fplliz]]
I 4 nmin (222))
Σ' (fo - f/)
+ +o²
Σ
k
k=
+ 4 2x²
1
Σ 2 (fo
-fr
+
4 2
7
h
+
1
NoR²
n m1
71
T)
n
k=
D. Proof of Optimal Rate
In this section, discuss the optimality of SGD for kernel regression with the dot-product kernel K under high-dimensional and asymptotic settings, respectively.
D.1. fiigh-Dimensional Setting
Under this setting, we consider sufficient large which satisfies cıd2 < o2d2 for some fixed 7 0 and absolute constants c1, C2-
To demonstrate the optimal rate, here we borrowed minimax lower bound of - fp from Lu et al. (2024a).
Theorem D.1 (Minimax Lower Bound, from Lu et al. (2024a)). In high-dimensional settings, where n is bounded by cid' < n < Czd" for some fixed y > 0 and constants Cı Cz. consider X = =d. The marginal distribution px assumed to be the uniform distribution on Sa. Let K denote a dot dot-product kernel on the sphere, which satisfies Assumption 4.5, Let P consist of all distributions p on X x Y given by y S (x) 6, where J E [H]* and N (0, 1) is independent of x. Let
p
++1
1, then we have:
inf sup E, PEP f 12 = Ω (0d-min(7-..o(p-1))
f f- 1:112
The well-specified case corresponds to > 1, and the mis-specified case corresponds to < 1.
In this section, we use different schedules to reach the minimax lower bound in the well-specified and mis-specified cases.
1. WELL-SPEEIFIED CASE
In the well-specified case, we use SGD with exponentially step decay schedule to reach the minimax lower bound.
Theorem D.2 (Theorem 5.1). In high-dimensional settings, where n is bounded by e didd n < cad" for some fixed 7y O and constants C1 C2. consider X = =S. The marginal distribution px is assumed to be the uniform distribution on Sd. Let K denote the dot-product kernel on Sd, which satisfies Assumption 4.5. Given 8 2 1, supposing that Assumption 4.3 holds with s, and treating R, K, C1. 02 and as constants, the excess risk of the output of SGD with exponentially decaying step size fdee satisfies:
(i) When 7 E (ps + p.ps + p s) for some p E N, with initial step size rjo = (dd 7+p log, n ludd) S min { } and k* (ddP), there exists a constant do such that for any 2 do, we have:
Ill - 1111aa1 S d 7+P log? d.
(ii) When 7 (ps+p+s, for some p E with initial step size noo (d n In S min + }
and k* (dP), there exists constant do such that for any d 2 dg. have:
E pdec f S dp+11)e
23

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
Proof. According (12) in Lemma B.3, we have
(no (|)
(So - [3) |
- S
%
(I-n0
H
max (1 mm 2m (mnda))) |> (So- k21
%
Select k* such that dg. = Mp and Ag-+1 = 1p+1, so that h:* = -(dP), Ar- = O)d and Ak+ = P(d-P-1) by Lemma A.3.
We take 7/0 O(d-2+P log, d). Then for & S k", we have log d d= x node no. Recall O(d)), let
No 2 C' log2 2 n for some constant C >> O. we obtain:
Tl (1 - -=) 2m (mnAAa**
(1 - 17022) 2m X
S Sexp( 12mmo
2 exp -2 lo82 n
log2 n n
exp( logg ni.
When 20'> (p+1)s
we have 7o (1 mo)2))m 2m (noAc) S d (0+1))s Therefore.
max (1 - no 2m (mnde))) S d dd(ttl)s kSk
To
(20)
For h: 2 k- + 1, we have d S 11++1) This implies that
11o"
max k2k*+1
(1 )odd2)2 2m (nodae))
S
max X S dx++1)s k2k++1
(21)
Combining (20) and (21), we have
E 1- (fo fj) [,)|
FF H
S $d-(x+1)s
(22)
H
Combining (22) with Lemma B.4, B.9 and 10, we derive the total excess risk bound:
[[llrdee rdee Sillia]] a d (0+1)s
Σ IJ - -5o)
1
20026² x2
hst logg n
+00 Σ 1=
+ 02 + 2 nont
+ 11fo - fo 12()2)
nnh
Since no S min
1
we have 2n²
2- I 10 2 02 Additionally, by the source condition with s 2 we
R. Ai f.
have I15o 1 Σ E (So 13) 1|2 S 1. Hence, the bound simplifies to:
E || - s3ll S d (x+1)s dd-(pt)) +
ke logg n n
k= +1
Since Eter X2 S dx 41 do S x22 x we further obtain:
E [| - 13 12 s d (x+1) An log? n
+
2 A +1-
24

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
We then set =
1, which ensures p + ps < 7 S (p + 1) + (p + 1)s.
Given n = (d)) and
++1
%o = ( log2 n In dnd,
d (0+1)0 hat 1o12 n
E
||| paee
101:3 62
+ 1o16 +1
n
d (0+1)s
+ d log
d 1-
logg dlnn d
2 d (0+1)0 d log d
10(d-10tD0) (ot))))))
0ld
7 7 (p ps 8, (p + + (p+ + 1)s]
Oldrr d)
7 E (p + p
D.1.2. MIS-SPECIFIED CASE
In the mis-specified case, we use SGD with averaged iterates to reach the minimax lower bound.
Theorem D.3 (Theorem 5.2). In high-dimenssoonal settings, where n. is bounded by d < n < c2d" for some fixed 7 0 and constants Cı C22 consider X' = =t. The marginal distribution px is assumed to be the uniform distribution on Sd. Let K denote the dot-p dot-product kernel on S which satisfies Assumption 4.5. Given 0 < < 1, supposing that Assumption 4.3 holds with and treating 7, G, C1, C2 and as constants, the excess risk of the output of SGD with averaged iterates fa satisfies:
C1,
(i) When 7 (ps + p,ps + p p s] for some p E with initial step size no O S min { x for p 2 1
and no θ (d-3) 3) S min 2 X1 } for p 0. there exists a constant do such that for any 2 do, we have:
E [I1 521laal S d
(ii) When 7 E (ps + p + 8, (p + 1)s + p 1) for some p E N. with initial step size 170 = θ (d- S min { x2 }
for 2 1 and n/u = θ (d- 3) s min
1 n X
1 for 0, there exists a constant do such that for any d 2 du we have:
E [Il - ffllba] S d (0+1)s
Proof. According to (17) in Lemma C.I, we have
Ph. Ef
pb
< n
n1
Σ
n-1
- -T--o-) 7) ()
| (So 1:31
H
i=0
n-1
2 n10
Σ (1 mode)
(nodaaz) | (50 - -5,11
n
max 121
Select k* such that dg- Mp and AR-+1 Mpt1, so that A =
d Odd-)), and Au+41 O(d- by
Lemma A.3.
For < k*, recall n = =dd').
1 In the case p Z 1, we take i/u θ (d- z min { (: x1 }. then n C. [xtt1)>
n n-1 for some constant C > 0,
so we obtain:
255
[Eu- mdde)) (node)) 1=0
=n (1- (1=((1-o>a)")) no 2 2x
2
-2 \/=
n100
d (p+1)s
<
C
25

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
In the case p = O, we take noo = + 3) & min R2 Xi
11 J. so we obtain:
2 Σ (1 - mAdet ) (noda)))
n 2100" =
S n 3010 321
2x=
S dd²
d=-1
Therefore, we have
n- l
Σ (1 mda))) ) (mnde))) ) S <d-ottlo+ + d- 1=0
n- no=" x
max
(23)
kskk"
For k 2 K- + 1, we have
(node)) (
n-1
)
)²
n 22200
-n- (1 -n~2(1- (1 (1=dd-no))'"")
)0 no 222
1=0
(1)
S n (nopodss) 2 2xx=² 2
Nh:
where inequality (i) uses the fact that if 0 S no S we have (1 - x= S nx. This condition is satisfied since amod S dd $1 (s S 1). Therefore, we have
a-1 ((1-mde)))) (nnda)) x
n 2m0"
max k2
max A S dp++1)) +2
(24)
1=0
Combining (23) and (24), we have
Σ
tb
- (fo f9p
2
(25)
H
H
According to in (18) Lemma C.2, we have
//2
E
In
b())
E
b(1)
S
no 2 1
n-1
Σ (I (1- 70
(1- 24 (1022)')
| x (fo - f/) 1
H
n no
7
k==
nou 2 1
n-1
Σ (1 - nod (node))) (Tod))))
|| (fo f;>112 11122
max
1 noR2
no
1=
max (1 - (1 - 11 Xa )x=1) ) >>> (Jo 1;>) k21
S n- -1
For l: k*, we have n 11 (1- (1 - node) (1= )2n) 1 < 2o= n and < 1. This implies that
n
max kSc
(1 - (1 2m)) 2a <
max X 8- in -1 S d pstppp S d=
(26)
MSkk
For k 2 k+ + 1, we have
(1)
n1
1 < n' 1=-((2nod==)
s Xi.
26

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
where inequality (i) the fact that if 0 S na S we have (1 x)" na. This condition is satisfied since nnja & dd=-1 1 (s < 1). Therefore, have
n-! max (1- (1 -o 22-1 x max X - d (0+1) 12
(27)
12
Combining (26) and (27), we have
E
b(1)
nn
b11
2 (d-(ot))s + dp-)) (/-))|1=1 =
-===('0 (fo fp) H
(28)
H
Combining (25) and (28) with Lemma C.2, C.3, and C.4, we derive the total excess risk bound:
E
Favg
x d (o(+))) + dl +de
Σ
2
(fo
f2) 1|
+ o² 2
t00
with
mork?
7
k=
1 1 } have moonn² 2-nox3 S 2 xx S 0² 1. Additionally, by the source condition with 2
Since no V min
n 2 f.
Σ 3''' (fo - f2) 11 S 1. Hence, the bound simplifies to:
have llfo f -
lill S do+tl) + -=- k
+
E
|| fa
nnz A2
n
k= +1
Since +00 +1= 23 S Nk-+1 41 d S x² Ag- we further obtain:
+1
[|| paog - fp [/ll S do(+++ + do + h + A
n
[
We then set p
1, which ensures p + ps 7
(p + 1) + (0 + 1)s.
Given
O(dr) and
s+1
. 2 1
770
3)
ip =
22 "7 d (p+1)s -- + k' + m
E 1a f;11
n
(p+1) 1)e d-y + --1-1
d (++1) d--
0(d-10+1))) 0((8-)
7 E (p + ps + (p + 1)s]
7 E (p + p
D.2. Asymptotic Setting
In the asymptotic setting, n > d, the decay rate of the kernel is A 0(-11))). We obtain the rate O nn ..न.गरग when क < < 2. This implies SGD with exponentially decaying step size schedule achieves optimally for > 1, and SGD with averaged iterates achieves optimality for a+1 < s 2.
[(d+1)
Similarly, we also borrowed a minimax lower bound for asymptotic setting from Caponnetto De Vito (2007).
27

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
Theorem D.4 (Minimax Lower Bound, from Caponnetto & De Vito (2007)). In asymplotic settings, where > d consider X' St. The marginal distribution px is assumed be the uniform distribution St. Let KNTK the NTK of a ReLU network with L layers with inputs S4. Let P consist of all distributions p X x 3 given by y fg (x) + where f E [H]] and E ~ N (0, 1) is independent of x, then we have:
inf sup Eo 1|5 1-lll -2 - o(d+a)
add-1)t))
f PEP
In the well-specified case, SGD with exponentially step decay schedule to reach the minimax lower bound. Theorem D.5 (Theorem 5.3). In asymptotic settings, where n > consider assumed to be the uniform distribution on S². Let KYTK denote the NTK of a ReLU network with L layers with inputs on
Sd. The marginal distribution px
Sd. For 1, supposing that Assumption 4.3 holds for s, with initial step size 7o0 θ
L-rid+1) aaatited
I min
[1 1 } the
k2 X
excess risk of the output of SGD with exponentially decaying step size fdee satisfies:
[I
ola+1) 1/112a] S logg n n 1(4+3)-0
In the mis-specified case, we use SGD with averaged iterates to reach the minimax lower bound.
Proof. Combining Lemma B.3, B.4, B.9 and B.10, we obtain the following bound:
|| pdec - 1/1/221 62 x
s log, n
| (fo -1>11(
E
1770
1000 2 k²
hh* loog n
+ Σ k=
)
0² +
+ 1150 - S/ 112))2))
2 17
Since 1o < min
1 1
we have
2 2-non² I noo S 02 Additionally, by the source condition with s 2 we
k 21 f.
have Il.o fill
< 1. Hence, the bound simplifies to: E (fo f2)
7t
logz n
k² logz v
+oc nn A
E [|stec
1770
k=
Since 2
x S
41 2-2 S -
too
3/2 we further obtain:
E
||
- fp 12:2 1.2
x
loga n
+
htt loog n
+ +mgg 11---118
12770
Select 1s* and no such that h-- θ (
and no = O
1-x(d+1) (
S 1, we have:
E [| - foll(2] S log n- n -(+1){+
Theorem D.6 (Theorem 5.4). In asymptotic settings, where n. >> d, consider X = gd. The marginal distribution px is assumed to be the uniform distribution on Sd. Let KNTK denote the NTK of a ReLU network with L layers with inputs on Sd
1-aid+11
For शमा S 8 < 1, supposing that Assumption 4.3 holds for s, with initial step size 110 = O (n=aar1) the excess risk of the output of SGD with averaged iterates fava satisfies:
min xo
gavg S11122]] S n. (d+1)-a
o(a+1)
28

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
Proof. Combining Lemma C.I, C.3, C.2 and C.A, we obtain the following bound:
E
||
5/ L2
2x²
76
|
(Jo - 55) |
107ju
7
"7002 22
(
k2
400
+
0² +
Σ
nn
1
2 - mnx2
i=
Since no I min
{1 1 1 11 {x²1 X, f. have Noo 2- I 210 162 I 0² 1 and
Non 1/u
x²²
1- n S (luu)
Additionally, by the
source condition with s 2 1, we have llfo - fillit I
D (fo
?
S 1. Hence, the bound simplifies to:
|| - s/l123] x
+
k*
neno 1
107
Y2
Since +1= X S
+1= k --2 S k -1- we further obtain:
+00
k-
favg - 1 1.3
2 km 2--1-
+ n17
12770
Noticing that 2 d+ select he and no such that k- =
O n
and n70 - (n
S 1, we have:
E
gan
foll
S n =(d-1)+2
E. Lower Bound of SGD with Averaged Iterates
In this section, we give a lower bound of SGD with averaged iterates, which helps to explain why it is not optimal when
8 >>> 2.
In this section, let o be a distribution satisfying that
y = (x) + where e ~ 02) is a independent variable for any x,
which implies
[xx [ = 0, F(xx))) & ( = ~.
To get a lower bound, we have the following lemmas:
Lemma E.1. Consider SGD with averaged iterates defined in (17). Then for any 0 Siiss S n, we have
-) (f. (f-- -f)) E [(G; - (2) (f-- = E [II (J+ (/) s (Ji []]]
E [f f2) @ - = [ [ @
Proof. We prove more generalized version: For any fixed operator A : H H.
E [ff ([fi-fj) f5) 3 A(, f2] [(ft- < A(I x) (fi (f- [2]
(J f:) @ (f-- [;]] = E [I 1 A (fs - 15) @ (fi (fi- f;]]
For the base case i = j. it naturally holds. Now we assume the lemma holds for j = i k 2 1, then we prove it for j = i + k 1.
29

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
Notice that Xx, and E are independent of J; f for any < < I, we have
E [Ji - (2) @ A (fi+++1 - [f)1 = E [[i - f2) @ A ((1 no (x 8 (x + ==++x+1) (Fitk- [/)
= E [[{: [f)) @ AE [ -100 -10 8 (xnrn)) + =++++++1] (Jo+k - [2)]
E [(f -f() @ (1]-)) (fi+x -f))
= E [[+ - (57) @ - ()
kt2 (ss 1..-pp -[p]]-
Similarly, we have
E [[++++1 (7) s (ʃ: {5)] E [A[T- In (Ji-Jz (1--5) S/) 8 (fi-
from which the lemma is proved.
Lemma E.2. Consider SGD with averaged iterates defined in (17). Suppose p satisfy (29). Then for any S S n, we have
O.
Proof. Solving the recursion of S and fi defined in (5) and (6), have
: = I Kx @ (xx) fo = Do0 Σ II (I
mx @ Kxx)) s
-=++1
By the special property of p. we have - (So: kxiX H is independent to Kx; for any 0 S 1 S n, thus we have
E E
2
f=
E
[I [I Kxx @ (xi) fo mm 70
II noxx, @ (x,) j=++1
E.
1=1
1=1
E
- no Kxi 2 [ku)) fo fm0ml
Σ
II (I - no Kx 2 Kxz)
(ui (f%, (xi) Bxs
1=1
1=1
jmit1
t
Y/0
Σ
E
[ [I--ooxy @ @Kxi) 50
II (I - mxx, @ @Kx))
Kx. E (v6p
(Jz (x))))))))
1=1
|=++1
0.
Lemma E.3. Consider SGD with averaged iterates defined in (17). Then for any S t S n, we have
[
E
o
E [
+ ft
fi
Proof. We prove this by induction on f. The base case naturally holds. Assuming the lemma holds for t 1, we prove this also holds for t.
Notice that y KKx,Kii)) 2 Kx, and fi are independent to each other for any 0 S i < t, thus we have
E [f & fi]
E [[I Kx, 8 (x,) + & ((I Kx. @
= E [I - E) (fr- @ ft-1) (I (I- nh =) + (Kx, & Kx.) (f'-1 @ ff- (Kx, & Kx.). + ne [E, & Ei]
= E [I - E) (fin @ fr (I- + LE E & E.]
E j Φ J
30

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
Similarly, we have E [ M = f @ ft from which the lemma is proved.
Combining the three lemmas above, we have
- 12)
Σ
17))
1 n-1 ( )
R-1
E
lr
Σ Σ
(Ji- (2)
71
1=0
1=
n-In-1
tr
Σ
E (f
f
2 (f) f))1
n
tr
Σ Σ
Σ
E
no Σ) (1) +
B E (()+ - (5. + /3)]
1=0
tr
Σ n1
E
1=0
+ir
Σ n
Σ
i=
j=it1
n-1
2r
Σ
11 1=0 j=0
+tr
Σ
B
l:]
n2
|=f+1
n-ln-1
tr
Σ 1
|=
E
Thus, we have the following lower bound:
Lemma E.4, Consider SGD with averaged iterates defined in (17). Suppose that 170 S
1.
Then we have
x
max E (x.))~= 12
max {(1 - (1- -,00)" | (So 11>1' +02 IEN+
1 kk
+
1
Σ
400
n
nnng
16 n
64
i=
where k* maxieN, (k: noAa 2 ).
Proof. Recall the proof of Lemma C.I, we have
Σ Σ (So {2) 2
jh tb
Σ
I x)
2
1=0
when we choose fü that makes
a-1 1
Σ [1- -
(0 f2)
Σ
(I - ))
| (So 1511 x
=
1=0
72
0=0
31

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
That is, choose f = fo - > (fo (fo-f fo) foll x Recalling the proof of Lemma C.3, we have
(fo-fa)le
Ag eq. where q = arg max,EN, {(1- -(1-011 - {
E
tr
n-1
1
R-1
Σ
I - (1-
ΣE BE 8E
H
11
0²
E I E)
E²
1:00
2
(1- mobo)² (1-(11-a)))))
i=
1=1
(1- exp
2)
+
Σ
(1 (1- (1 mdd)3)
n2 -=1
-=1
*=*+1
1 n
2
to0
1 n
( no>s)) )
1 exp
n2 4
12 2
n² 4
202
Σ
mm ?
16
64
im
+1
when we choose h- = arg maxie__ {k: : Ao 2 }. Thus, we have proved there exists p satisfying the inequality in the lemma, from which the lemma is proved.
In the following, we show that in high-dimensional settings, when s > L, there exists region where SGD with averaged iterates cannot achieve optimality.
Lemma E.5. Let ejd" < < ezd" for some fixed y >> O and absolute constants C1 02 Consider X = Sdt and the marginal distribution z to be the uniform distribution. Let K be the inner product kernel on the sphere. Consider y,, o, n. C12 02 and 1 as constants, the excess risk of the output of SGD averaged iterates faed cannot achieve optimality.
Proof. According to Lemma E.4, we have
max (xx))>>> pang follss
P
= Ω
1 max {(1 (1 Armo)") - (So [5]
2
+ 0
kz +
Σ t=
mixi?))
)
n2ng
TEN+
where h* arg maxieN, {k: no 11
Under kernel K, kst defined above satisfies A = O (A so we assume ks (PP), E N. then Too (dd+tnn-)) where 0 < r < min(1,7 > - p} is a arbitrary constant.
In the case 0 < s < 2, using the inequality 1 (1 11--- -x)" 2 1 min(1, nx), according to the proof of Lemma 5.2, we have
inf max { fx--2 n ( (0)1) St cun
max 1EN+
{(1 - (1 - \ (Ammo) Ω
where Zo = arg max min (1, nzx 2 -1 1
05
32

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
We know
max {11 (1 A (Ar70) - =a(a(-1))n IEN+
if and only if no ( p N and p 7 2.
When 7/u = ((d++n==1) with 0 < < min { [2r p}. we know
{(L (1 >mmo) (Amm)) - -0(16-22))
max sEN+
When 77u O(drtnn-)) with //2 < min (1, p}. we know
{(1 - (1 (1))))))))(()))))) = @ (16--1)8125
max SEN+
By contrast, in the case s > 2, we have
max
(1 - ((x)))))) Q1).
Using o² (2)) E 1- (fo "Fo
-f)
(21),
(()), Ei=k41 =2==O(++++).oom and n O(d?), we have
7
max (xx.s)) ~pp 11000 17112.2
Ω (d)
Ω d (1++))))
(dp-)))
(29)
|<=<2]][/[++)==][[6=+]] + 22 1)
Ω (d (d-(xt1)))
1<== +
Ω (d
$ 2 5-1 8-1
p(s+1)+5
Ω p 1
2o 12
8 222,E p(st1)+ p(a+1)+stl
+1
Similarly, we can prove that when n > d, SGD with averaged iterates suboptimal for any s >
33

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
F. Graphical illustration and Summary of Optimal Region
E1. Graphical illustration of Theorem 5.1 and Theorem 5.2
In Figure 2, we provide a visual illustration of the convergence rate curves of the excess risk for SGD in the high-dimensional setting n d', under source conditions with s 0.5, 1,5. For comparison, we also include KRR convergence curves and the minimax optimal rate eurves. These references highlight the saturation phenomenon of KRR for large 8, and the 0.
optimality of SGI) across
F.2. Summary of Optimal Region
In Table 1, we summarize the optimality regions (with respect to the source condition parameter s) of various algorithms, including SGD, KRR, and GD with early stopping under both high-dimensional and asymptotic settings.
In the high-dimensional setting:
SGD is optimal for > 0 (Theorem 5.1 and Theorem 5.2).
KRR is optimal for < s S (Zhang et al., 2024b), but for s > 1, there exists a range of where it fails to be
optimal (Zhang et al., 2024b).
GD with early stopping is optimal for all > 0 (Lu et al., 2024b).
In the asymptotic setting:
SGD is optimal for s 2 7+1 (Theorem 5.3 and Theorem 5.4).
KRR is optimal for 0 < < 2 (Caponnetto & De Vito, 2007; Smale & Zhou, 2007; Blanchard & Mücke, 2018; Li et al., 2022; Zhang et al., 2024a), but not for 2 (Cui al., 2021; Li et al., 2023).
GD with early stopping is optimal for all s (Raskutti et al., 2014).
High--Dimesiones Setting(n x d'))
Asymptotic Setting(n >> d)
SGD
$ >> 0
d+
KRR
0 < S 1
< S
GD with Early Stopping
8 >>> 0
> 0
Table 1. Optimal Region for Algorithms mentioned.
34

---

Learning Curves of Stochastic Gradient Descent in Kernel Regression
V Vvs. a.5. E[H
y vs. B, 30,5=05, f E [[H]
-0.3
SGD rate KRR rate
-0.4
-1
a, rarate = n
-0.5
B, r.rate = dB
-2
-0.6
-0.7
-4
00.8
-5
-0.9
minimax rate
-6
SGO rate
-1.0
0.0
2.5
5.0
10.0
12.5
15.0
17.5
20.0
0.0
2.5
5.0
7.5
10.0
12.5
15.0
17.5
20.0
Y, d
Y, n dv
(a)
(b)
Vvs. a, = 1, fg [[H]
vs. B, 1, f E [H]
minimax rate
SGD rate
KRR rate
00.6
-2
a, ratae = n
B. rate = d/B
-0.7
-0.8
-0.9
-8
minimax rate
SGD rate
-1.0
-10
2.5
5.0
10.0
12.5
15.0
17.5
20.0
2.5
5.0
10.0
12.5
15.0
17.5
20.0
Y, d
V, n dv
(c)
(d)
V vs. a, 5, f. [[H]
-0.65
Vs. B, 5= 5, [
-0.75
5CD
K, rataee = n
-25
KBR rate
B, rate dp
-5.0
-0.85
-0.90
-12.5
-0.95
SGD rate
15.0
-1.00
KRR rate
15.0
17.5
0.0
2.5
5.0
7.5
10.0
12.5
15.0
17.5
20.0
V, n = Y
V. n dY
(e)
(I)
Figure Convergence Rate of SGD and KRR with respect to n and d, we present graphs corresponding to source conditions with 0.5, 1, 5. The x-axis represents the asymptotic scaling 7 se df the y-axis represents the convergence rate of excess risk: excess risk x n or excess risk d
35


Reviews:
[{"review_id": "6sRCjEYOPP", "reviewer": "Reviewer_bPCa", "summary": "This paper examines the problem of using SGD to train a kernel regressor. In particular, the paper considers the dot product kernel with input data that is uniformly distributed on the sphere. Assuming that the targets $y = f_*(x) + \\varpepsilon$ for $f_*$ with certain smoothness properties, the paper shows that different forms of SGD can achieve the minimax optimality rate. \n\nThe paper empirically verifies this in a couple of situations.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your careful review and positive feedback on our work. Your comments have provided concrete guidance for improving the paper and have been a great source of motivation for us. Below, we address your questions and concerns in detail.\n***\n#  Author's Response to Essential References:\nThank you for sharing these important related works with us, which have helped us to improve the completeness of our discussion.\n> *1. \"Import paper on dot product kernel regression\":*\n\n**Our Response:** [E] is indeed a key reference in the high-dimensional dot-product kernel regression. We have now added them in the revision of the paper. It studies the setting where $n\\asymp d^{\\gamma}$, provides a precise closed form formula for learning curves of dot-product KRR, and identifies the multiple descent phenomenon of KRR. The techniques presented in this paper are also highly beneficial for analyzing optimal convergence rates in high-dimensional scenarios.\n\n>*2. \"Related works on early stopped GD\":*\n\n**Our Response:** Thank you for providing references on early stopped GD, which enables readers to gain a more comprehensive understanding of the related techniques. We have incorporated a more detailed comparison with early stopped GD in the revision of the paper. In the following, we discuss the contributions and connections to our current work of the papers you shared.\n\nSpecifically, references [A–D] examine the generalization performance of early stopped GD in kernel regression, collectively highlighting the close connection between early stopping and ridge regularization. They analyze early stopped GD under scaling conditions such as $n\\asymp m$ or $n\\asymp d$, where $n$ denotes the sample size, $d$ the input dimension, and $m$ the number of model parameters, emphasizing optimal stopping rules and generalization performance. Our paper complements these studies by considering single pass SGD within the NTK framework (infinite width, $m=\\infty$), and explores the optimal learning curves under various ratios between sample size $n$ and input dimension $d$.\n\n>*3. \"Related works on early stopped SGD\":*\n\n**Our Response:** The single pass SGD we consider can be viewed as a form of early stopping, where each observation is used only once, and overfitting is avoided by making only a single pass through the data. Following your suggestion, we will expand the discussion with related works.\n***\n# Author's Response to Comments or Suggestions:\nThank you for your suggestions and for pointing out the typos. We have made the following revisions accordingly.\n\n> *1. \"The embedding operator in Line 126 (Right)\":*\n\n **Our Response:**  We have made the revision $T^{\\ast}:  \\mathcal{H}\\rightarrow L^2 $.\n\n> *2. \"Clarify of $s$ in Assumption 4.3\":*\n\n**Our Response:** We have now clarified in Assumption 4.3 that the source condition is specified for a given $s$.\n\n> *3. \"Explicit Definition  of  $f_{\\rho}^{\\ast}$ in Theorem 5.1\":* \n\n**Our Response:** We now consistently use the notation $f_{\\rho}^{\\ast}\\left ( \\mathbf{x}  \\right )=\\mathbb{E}_{(\\mathbf{x},y)\\sim \\rho} \\left [ y| \\mathbf{x}\\right ]$. In addition, we have clarified the definition of the joint distribution $\\rho$ of $(\\mathbf{x},y)$  in theorems.\n\n> *4. \"Write 4.7 and 5.1 in the same language\":*\n\n**Our Response:** Although the rates in Theorems 4.7 and 5.1 match for given $s$ and $\\gamma$, we agree that the use of $p$ could cause confusion at the boundary cases. We have revised the statements accordingly to ensure consistent language throughout.\n***\n# Author's Response to Question 1:\n\n>*1. \"Do you what happens if instead of stopping early the algorithms are run until convergence? Do they converge to the KKR solutions?\"*\n\n**Our Response:** I think what you may be referring to is a scenario different from the single pass SGD we consider: specifically, when a fixed dataset is given and the algorithm performs infinitely many iterations over this fixed sample set, the resulting function tends to $f_{\\infty }(\\mathbf{x} )=K(\\mathbf{x},\\mathbf{X})K(\\mathbf{X},\\mathbf{X})^{-1}\\mathbf{y}$, which corresponds to the kernel interpolation solution. \nIf we consider single-pass SGD with an infinite stream of i.i.d. samples, the procedure falls under the asymptotic setting, and the excess risk of the solution will converge at the asymptotic convergence rate.", "claims_and_evidence": "The paper is primarily theoretical, with some experiments reinforcing their theoretical claims. The theoretical statements are detailed and rigorously written and have corresponding proofs. The results from the paper are convincing. \n\nThe importance of the upper bounds is also well justified.", "methods_and_evaluation_criteria": "The experiments are appropriate to support the theory.", "theoretical_claims": "I read the proof for property one and the beginning of the proof for Theorem 5.1. They look correct to me.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper mostly situated itself very well with respect to broader literature. They provide comprehensive cases against which to compare their results. Specifically, the lower bounds from prior works, as well as the fact that KRR does not meet these lower bounds. This helps strengthen their results, showing that the method they consider achieves the optimal rates.", "essential_references_not_discussed": "In essence, the paper does not consider SGD until convergence. But an early stopped version of SGD. It would be beneficial for the paper to discuss related works on early stopped SGD (or even GD). I am more familiar with the GD literature so I list some here [A,B,C,D]. \n\nI think this is also an import paper on dot product kernel regression that is missing [E]\n\n[A] Madhu S. Advani, Andrew M. Saxe, and Haim Sompolinsky. High-dimensional dynamics of generalization\nerror in neural networks. Neural Networks, 132:428–446, 2020.\n\n[B] Alnur Ali, J. Zico Kolter, and Ryan J. Tibshirani. A Continuous-Time View of Early Stopping for Least\nSquares Regression. In International Conference on Artificial Intelligence and Statistics, pages 1370–1378,\n2019.\n\n[C] Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Early Stopping and Non-parametric Regression: An\nOptimal Data-dependent Stopping Rule. Journal of Machine Learning Research, 15(11):335–366, 2014.\n\n[D] Rishi Sonthalia, Jackie Loh, Elizaveta Rebrova. On regularization via early stopping for least squares regression. arXiv preprint arXiv:2406.04425. 2024.\n\n[E] Xiao L, Hu H, Misiakiewicz T, Lu YM, Pennington J. Precise learning curves and higher-order scaling limits for dot product kernel regression. arXiv preprint arXiv:2205.14846. 2022 May 30:3.", "other_strengths_and_weaknesses": "**Strengths**\n\nThe results from the paper are quite strong. They show that optimal minimax rates can be achieve for a variety of well specified and mis-specified problems. This is quite a strong result and I think is sufficient for the paper to be published.", "other_comments_or_suggestions": "**Typos**\n\nThe embedding operator Line 126 (Right) should map from $\\mathcal{H} \\to L^2$. \n\nIn Assumption 4.3 it should be clarified for a given $s$ and not for all $s$. \n\nIn Theorem 5.1 $f_\\rho$ should be explicity defined. It would also be helpful to write 4.7 and 5.1 in the same lanague. Specifically, so that the conditions on $p$ and $\\gamma$ are easier to compare. Currently they look similar, but I think there is a difference of $\\pm 1$.", "questions_for_authors": "Do you what happens if instead of stopping early the algorithms are run until convergence? Do they converge to the KKR solutions?", "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": "Rv9icJNnbZ", "reviewer": "Reviewer_sxnu", "summary": "This paper proves 4 results about the excess risks of least squares RKHS regression optimised by stochastic gradient descent. The settings of the four results are divided along two axes: firstly, the high-dimensional regime, in which the input dimension grows with the sample size, versus the fixed dimension regime, where the only the sample size grows, and secondly, the well-specified and misspecified settings. Comparing with lower bounds in existing works, optimality of their results are investigated in each case.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for taking the time to carefully review our paper and for providing detailed and highly valuable feedback. Below, we respond to your questions and concerns one by one.\n***\n# Response to Questions:\n>*1. 164R: $N(d,k)$.*\n\nThe confusion stems from a typo in Line 142L, where we mistakenly wrote $\\mathbb{R}^{d}$ instead of $\\mathbb{R}^{d+1}$. In our paper, $\\mathbb{S}^d$ actually denotes the unit sphere in $\\mathbb{R}^{d+1}$. We have corrected this and confirm that the difference only introduces a constant factor, which does not affect the validity of our rates.\n\n>*2. Online algorithm.*\n\nWe refer to SGD as an \"online algorithm\" to emphasize that it can process data in an i.i.d. streaming fashion, in order to distinguish it from \"offline algorithm\", which operates on a fixed dataset. We have now reduced the use of \"online\", only when we mention \"offline\". We have also added a clarification of \"offline\" to ensure the meanings of both terms are clear.\n\n>*3. 567, (7): $\\sum _{i=1}^{\\infty}\\langle\\phi _i,T\\phi _i\\rangle _{L^2} =\\sum _{i=1}^{\\infty} \\mathbb{E}\\left[\\left\\langle\\phi _i,K _{\\mathbf{x}}\\right\\rangle _{L^2}^2\\right]$?*\n\nThis is a typo, but the conclusion $\\mathrm{tr} (T )=\\mathbb{E}{K(X,X)}$ still holds. A revised proof is provided below: \n\\begin{aligned}\n\\sum _{i=1}^{\\infty}\\langle\\phi _i,T \\phi _i\\rangle _{L^2}=\\sum _{i=1}^{\\infty} \\mathbb{E} \\left( \\lambda _i^{1/2}\\phi _i(X)\\right)^2\\overset{(a)}{=}\\sum _{i=1}^{\\infty} \\mathbb{E} \\left\\langle K _X, \\lambda _i^{1/2} \\phi _i \\right\\rangle _{\\mathcal{H}}^2\\overset{(b)}{=}\\mathbb{E}\\left\\langle K _X, K _X \\right\\rangle _{\\mathcal{H}}，\n\\end{aligned}\nwhere $(a)$ follows from the reproducing property, $(b)$ follows from Parseval's identity. \n\n>*4. 589, (10): Typo in Equa.*\n\n We have corrected this.\n\n>*5. 667, (23): Why positive definiteness of $\\boldsymbol{\\Sigma}$ imply (23)?*\n\n>*6. 671, (24): $i$ and $j$?*\n\n>*7. 719, (31): $i$ and $j$?*\n\nWe address Questions 5, 6 and 7 together. Thank you for pointing out the typo, that we mistakenly used subscript $i$ and $j$ instead of the iteration $t$. All $i$ and $j$ should be replaced by $t$ in Lemma B.1, Lemma B.2 and (76). We have corrected this, and it does not affect the validity, as only the decomposition at the $t$-th iteration are used. The key steps are provided below:\nBy the positive definiteness of $\\boldsymbol{\\Sigma}$, $\\left\\langle f _{t}^{b} - f _{t}^{v}, \\boldsymbol{\\Sigma}\\left(f _{t}^{b} - f _t^v\\right)\\right\\rangle _\\mathcal{H}\\ge0$. This implies $\\left\\langle f _t^b,\\boldsymbol{\\Sigma}f _t^v\\right\\rangle _\\mathcal{H}+\\left\\langle f _t^v , \\boldsymbol{\\Sigma}f _t^b\\right\\rangle _\\mathcal{H}\\le \\left\\langle f _t^b , \\boldsymbol{\\Sigma}f _t^b\\right\\rangle _\\mathcal{H}+\\left\\langle f _t^v , \\boldsymbol{\\Sigma}f _t^v\\right\\rangle _\\mathcal{H}$. \nBased on this, we can obtain the desired result in Lemma B.1. The proofs of Lemma B.2 and (76) follow the same reasoning.\n\n>*8. 712, 733, 744, 748, 753, etc.: $\\mathbb{E}$?* \n\nWe have removed the expectation where no randomness is involved.\n\n>*9. 761: (37)?*\n\nBelow is an explanation of (37). \nDue to $\\eta _0 \\le \\frac{1}{\\lambda _1}$ and $\\eta _i\\le \\eta _0$, it follows that $\\mathbf{0} \\preceq  \\boldsymbol{I} -\\eta _i\\boldsymbol{\\Sigma}\\preceq \\boldsymbol{I}$. \nFor all $i$, $\\boldsymbol{I} - \\eta _i\\boldsymbol{\\Sigma}$ and $\\boldsymbol{\\Sigma}$ are positive semidefinite, self-adjoint and mutually commuting operators. \nDenote $\\mathcal{M} _n= \\prod _{i=1}^{n} (\\mathbf{I} - \\eta _i \\boldsymbol{\\Sigma})$, then $\\mathcal{M} _n \\boldsymbol{\\Sigma} \\mathcal{M} _n\\preceq\\cdots\\preceq\\mathcal{M} _m \\boldsymbol{\\Sigma}\\mathcal{M} _m.$\n\n>*10. 424, 813: What is $k^{\\ast}$?*\n\nThank you for pointing out the inconsistent use of $k^{\\ast}$. In Line 424, $k ^{\\ast} = \\max _{i\\in\\mathbb{N} _+} \\lbrace k:\\eta _0\\lambda _k\\ge \\frac{1}{n}\\rbrace $, which serves as an effective dimension (see Lemma D.4). While in Appendix B, $k^{\\ast}$ can be any positive integer in order to present a more general result. The specific value is clarified in Appendix C and D. We have revised the paper to clearly indicate whether $k^{\\ast}$ refers to.\n\n>*11. 790, (42): $\\mathbb{E}[ \\Xi _{t} ]=0$?*\n\nWe apologize for the confusion caused by the improper definition of $f _{\\rho}^{\\ast}$ in Line 630.\nAlthough under the source condition given $s$, $f _{\\rho}^*$ in line 630 is intended to refer to $\\mathbb{E} [ y| \\mathbf{x} ]$, this expression used was inappropriate. We have revised the paper to ensure consistent use of $f _{\\rho}^*=\\mathbb{E} [ y| \\mathbf{x} ]$ throughout. Under this definition, $\\mathbb E[\\Xi _t ]=0$ is a mild assumption. \n***\n# Response to Suggestions:  \nWe appreciate your constructive writing suggestions. All points have been addressed, and we have further refined the manuscript.\n***\n# Response to Related Works:\nThank you for sharing the references. They have been included in the revised version. Additionally, we have expanded our discussion of the KRR literature.", "claims_and_evidence": "This is a theoretical paper, and hence the presentation of the mathematics and the correctness of the proofs are needed as evidence for the theoretical claims. I do not have big doubts that the results are correct, but the proofs are presented in a way that is rather hard to follow and I have doubts on the correctness of some parts of it. I gave up reading the proofs in the Appendix some way in, and I unfortunately can only think that there will be many more places where corrections or clarifications have to be made. See \"Questions\" sections for details.", "methods_and_evaluation_criteria": "This is a theoretical paper.", "theoretical_claims": "See \"Questions\" section for details.", "experimental_designs_or_analyses": "This is a theoretical paper.", "relation_to_broader_scientific_literature": "The results would be interesting in the community of learning theory in RKHSs, the attention on which have been recently revived with connections to neural networks via NTKs and the study of benign overfitting. The study of properties of SGDs is much less explored than the closed form solutions, and if it can be shown that SGDs have provable advantages over closed form solutions, as this paper claims, that would be interesting.", "essential_references_not_discussed": "There are some related papers that the authors have not discussed in the KRR literature, for example, [Blanchard and Mücke, 2018, Optimal Rates For Regularization Of Statistical Inverse Learning Problems], [Li et al., 2023, Optimal Rates for Regularized Conditional Mean Embedding Learning].", "other_strengths_and_weaknesses": "I think the writing could be very much improved - see Section \"Other Comments Or Suggestions\". The English is not such a big problem, as it cannot be expected that non-native speakers write in perfect English, but there are some inconsistencies with mathematical notations too.\n\nAll the results are given in expectation, and I think in general high-probability bounds are stronger, and personally preferred. This is a minor point.", "other_comments_or_suggestions": "10R: \"which states sufficiently wide neural network\" -> \"which states that sufficiently wide neural networks\"\n\n35R: \"via an online fashion\" -> \"in an online fashion\"\n\n43R: \"In specific\" -> \"Specifically\"\n\n51R: \"resulting entirely different learning dynamics\" -> \"resulting in entirely different learning dynamics\"\n\n87L: \"Why SGD can overcome\" -> \"Why can SGD overcome\"\n\n77R, 104R: \"early stop\" -> \"early stopping\"\n\n138L: For consistency, $\\rho_X$ should be $\\rho_\\mathcal{X}$. \n\n146L: \"denote ... be the operator\" -> \"denote by ... the operator\"\n\n114R: \"By the Mercer's theorem\" -> \"By Mercer's theorem\"\n\n118R, 125R, 142R, 232L: For consistency, $L_2$ should be $L^2$. \n\n195R: Seems a space is missing between the definition of $m$ and the next sentence?\n\n287L: \"optimaly\" -> \"optimally\"\n\n284R: space needed after \"s,\"\n\n559: The subscript for $\\langle\\mathbf{x},\\mathbf{x}\\rangle$ should not be $L^2$, as $\\mathbf{x}$ are not functions. \n\n577: In (9), the second inequality is an equality. \n\n636, (16): $f_t$ is only introduced later in (18), so it doesn't look good to use it here. If $f_t$ is replaced by general $f$ here, then the outer expectation should not be there, since $f$ would not be random and there is no other source of randomness. \n\n686: $f^{(1)}_t$ should be $f^{b(1)}_t$. \n\n768, 770: The operator does not live in $\\mathcal{H}$, so you cannot take the $\\mathcal{H}$-norm of the operators, you should take the operator norm.", "questions_for_authors": "164R: I thought the multiplicities were $N(d,k)=\\frac{(2h+d-2)(h+d-3)!}{h!(d-2)!}$? See [Müller, 1998, Analysis of Spherical Symmetries in Euclidean Spaces, p.28, Exercise 6]. Why are your multiplicities different?\n\nThe authors repeatedly refer to SGD as an \"online algorithm\", but this is very different to the usual usage of the word \"online learning\", whereby the data is fed to the algorithm sequentially, and one is concerned with the regret. I have personally never seen the term \"online algorithm\" being used for variants of gradient descent. If the authors and the other reviewers agree, I would strongly suggest to remove the word \"online\" to avoid confusion. The authors also repeatedly use the term \"offline\" for learning with explicit regularisation, or anything that is not based on variants of gradient descent, but I would consider their SGD set-up also as \"offline\", as we only have one static dataset. \n\n567, (7): Are you sure that $\\sum^\\infty_{i=1}\\langle\\phi_i,T\\phi_i\\rangle_{L^2}=\\sum^\\infty_{i=1}\\mathbb{E}[\\langle\\phi_i,K_\\mathbf{x}\\rangle^2_{L^2}]$? I get that $\\sum^\\infty_{i=1}\\langle\\phi_i,T\\phi_i\\rangle_{L^2}=\\sum^\\infty_{i=1}\\mathbb{E}[K(\\mathbf{x},\\mathbf{x}')\\phi_i(\\mathbf{x})\\phi_i(\\mathbf{x}')]$ and $\\sum^\\infty_{i=1}\\mathbb{E}[\\langle\\phi_i,K_\\mathbf{x}\\rangle^2_{L^2}]=\\sum^\\infty_{i=1}\\mathbb{E}[K(\\mathbf{x},\\mathbf{x}')\\phi_i(\\mathbf{x}')K(\\mathbf{x},\\mathbf{x}'')\\phi_i(\\mathbf{x}'')]$, which are not the same. However, from $\\sum^\\infty_{i=1}\\langle\\phi_i,T\\phi_i\\rangle_{L^2}=\\sum^\\infty_{i=1}\\mathbb{E}[K(\\mathbf{x},\\mathbf{x}')\\phi_i(\\mathbf{x})\\phi_i(\\mathbf{x}')]$, you can proceed with the reproducing property and the Cauchy-Schwarz inequality to get the desired bound. \n\n589, (10): The second equality should be an inequality arising from the Cauchy-Schwarz inequality. They are not the same. \n\n667, (23): I'm sorry if I'm missing something, but how does the positive definiteness of $\\boldsymbol{\\Sigma}$ here imply (23)?\n\n671, (24): On the first line, shouldn't it be $\\mathbb{E}[\\langle f_i-f^*_\\rho,\\boldsymbol{\\Sigma}(f_j-f^*_\\rho)]\\rangle_\\mathcal{H}=\\mathbb{E}[\\langle f^v_i+f^b_i,\\boldsymbol{\\Sigma}(f^b_j+f^v_j)\\rangle_\\mathcal{H}]$ instead of $\\mathbb{E}[\\langle f_i-f^*_\\rho,\\boldsymbol{\\Sigma}(f_j-f^*_\\rho)]\\rangle_\\mathcal{H}=\\mathbb{E}[\\langle f^v_i+f^b_j,\\boldsymbol{\\Sigma}(f^b_i+f^v_j)\\rangle_\\mathcal{H}]$? How is it that $i$ and $j$ switch? \n\n712, 733, 744, 748, 753, etc.: In the first term on the right hand side on the first line, what is random inside the expectation here? It seems to me that nothing is random, so you shouldn't be writing expectations right?\n\n719: I don't understand (31). On the left-hand side we have subscript $t$, but on the right-hand side we have $i$ and $j$. Where do $i$ and $j$ come from? Does this bound hold for all $t$, $i$ and $j$? The preceding proofs suggest that all $i$ and $j$ should be replaced by $t$, see comment above for 671. \n\n761: How do you obtain (37)? I guess you use $\\eta_t=\\frac{\\eta_0}{2^{l-1}}$ and $m=\\lceil\\frac{n}{\\log_2(n)}\\rceil$ somehow? I'm sorry that I couldn't immediately see how this leads to (37). Is this obvious?\n\n424: Where was $k^*$ defined? This seems to be the only place in the main body where $k^*$ is used, and it is not introduced. It is used quite heavily in the appendix but it is not introduced there either. \n\n790, (42): Why is $\\mathbb{E}[\\Xi_i]=0$? On 630, $f^*_\\rho$ was defined to be $\\text{argmin}_{f\\in[\\mathcal{H}]^s}\\mathcal{E}(f)$, not $\\mathbb{E}[y\\mid\\cdot]$, so I don't think you can assume $\\mathbb{E}[\\Xi_i]=0$. Am I missing something? This has repercussions, e.g. in (43), where the cross-terms should not disappear. \n\n813: Again, what is $k^*$?", "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": "KjX5uTrhNy", "reviewer": "Reviewer_6fC3", "summary": "This paper studies the generalization performance of kernel regression trained by online / single-pass SGD and compares it with offline methods such as ridge regression. Specifically, the analysis is conducted under a standard source condition assumption on the target (including the misspecified case) and focuses on dot-product kernels with uniform data on the sphere.\n\nUnder these assumptions, the authors derive excess risk decay rates in the input dimension $d$ under two scalings of sample size $n$: polynomial $n=\\Theta(d^{\\gamma})$ and assymptotic $n\\gg d$. The main results are:\n\n- Optimality of SGD in well-specified regimes: They show that using exponentially decaying step sizes allows SGD to achieve minimax-optimal rates for smooth targets $s\\geq 1$, avoiding the so-called saturation effect that plagues certain offline algorithms.\n\n- Efficiency in misspecified problems. For problems where the target is less smooth $s\\in(0,1)$, a constant step size with iterates averaged is proven to match the minimax lower bounds in high dimensions.\n\nThey also provide a comparison with offline KRR under both scalings, showing that SGD can outperform KRR, especially when the target is sufficiently smooth.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and recognition of our contributions. Below, we address your concerns and questions in detail.\n***\n# Author's Response to Essential References:\n\n>*1. \"Related References Bordelon et al. (2020) and Cui et al. (2021)\":*\n\nThank you for sharing these important and relevant works in this area. They proposed the description of learning curve's exact order and have inspired subsequent efforts toward the characterization of the optimal learning curve. We have now included Bordelon et al. (2020) and Cui et al. (2021) in the revised version of the paper. We discuss the contributions of these works and their connections to our research below.\n\nBordelon et al. (2020) studied the learning curves of dot-product kernels on spherical data in the high-dimensional regime $n\\asymp d^{\\gamma}$. They observed that errors in spectral modes associated with large eigenvalues decrease more rapidly as the sample size $n$ increases, while the errors in spectral modes with small eigenvalues remain nearly constant until $n$ reaches the degeneracy of the corresponding mode. \n\nCui et al. (2021) provided a comprehensive characterization of the asymptotic rates of KRR with respect to the capacity and source conditions, the regularization parameter, and the noise level in the Gaussian design setting. Their analysis implies that KRR is suboptimal when $s>2$. Li et al. (2023) further proved this conclusion for general continuous positive-definite kernels. \n\n>*2. \"Mentioning Pillaud-Vivien et al. (2018) in the Related Works\":* \n\nThank you for this suggestion. We have now mentioned it in the related works when discussing the suboptimality of SGD, noting that the introduction of multi-pass strategies can lead to a broader region of optimality. \n\n***\n# Author's Response to Suggestions:\n\nThank you for pointing out the typos, which definitely helps us improve the paper in a concrete way. We have made the following revisions:\n- Revised L069 right column as $n^{-\\frac{s\\alpha}{s\\alpha+1}}$.\n- Revised L127 right column as $T^{\\ast}:  \\mathcal{H}\\rightarrow L^2 $.\n- Revised 1st equation of Section 6.2 as $f^{b} _0=f _{\\rho}^{\\ast}$ ,$\\tilde{f} _{0}^{b}=f _{\\rho}^{\\ast}$.\n- Revised 2nd equation of Section 5.2 as $n^{-\\frac{2d+2}{3d+2}}$.\n***\n# Author's Response to Questions\n## Author's Response to Question 1: \n\n>*1. \"What are the challenges of stating the results of Section 5.2. for general source and capacity conditions of the kernel?\"* \n\nThank you for raising the question of whether our asymptotic results can be extended to general source and capacity conditions of the kernel.\nFirst, we note that the excess risk bound derived in Appendix B relies only on the assumption that the kernel is bounded, and it already provides a general formulation.\nOnce the target kernel satisfies certain capacity conditions, along with a distributional condition that controls the residual noise of \n$f_t^{b(1)}$ and $f_t^{v(1)}$, such as the boundedness of the kernel, or conditions like $\\mathbb{E}[K(\\mathbf{x},\\mathbf{x} )K_{\\mathbf{x}}\\otimes K_{\\mathbf{x}}]\\preceq \\kappa \\mathbb{E}[K_{\\mathbf{x}}\\otimes K_{\\mathbf{x}}]$, or $\\mathbb{E} \\left \\langle f,K_{\\mathbf{x} } \\right \\rangle ^4\\le \\kappa \\left \\Vert f \\right \\Vert _{\\mathcal{H} } ^2$,\nour analysis can be directly applied to obtain corresponding convergence rates. \n\n>*2. \"What is exactly the role played by the spherical data here?\"* \n\nWe did not present the general conclusion separately, but continued using spherical data in order to maintain focus on the central theme of our paper. The main goal of this work is to understand the generalization curve of SGD under the NTK. Our analysis in the asymptotic setting aims to answer the following question: Can the SGD algorithm consistently achieve optimality across all scalings of $n$, particularly when liberated from the $n\\asymp d^{\\gamma}$ constraints? For this reason, we adopted the assumptions in $n\\asymp d^{\\gamma}$ setting throughout the paper.\nWe acknowledge that the assumption of a uniform input distribution on spheres is restrictive in high-dimensional scenarios. Our primary motivations for adopting this setting are that the harmonic analysis in the sphere is clearer and more concise, the analysis of Mercer’s decomposition for general kernels in high-dimensional settings is challenging, and few results are available. Due to these reasons, most existing analyses in high-dimensional setting also utilize spherical data.\nYour suggestion to extend our analysis to more general kernels is indeed a valuable and challenging direction, and we will pursue this in our future research.\n\n## Author's Response to Question 2:\n\n>*\"Addition of a plot summarizing the behavior of the error curve of SGD.\"*\n\nThis is a valuable suggestion. We have now included in the appendix the curves of the convergence rate on the excess risk of SGD as $\\gamma$ increases, under different values of $s$.", "claims_and_evidence": "The claims in this paper are rigorous mathematical results. Numerical simulations are also provided as an illustration of the mathematical results.", "methods_and_evaluation_criteria": "N/A.", "theoretical_claims": "I skimmed through the proofs of the results and did not spot any issue. The proofs are standard, and consist in bounding the bias and variance decomposition of the predictor by leveraging previous results in the literature.", "experimental_designs_or_analyses": "N/A.", "relation_to_broader_scientific_literature": "- The study of excess risk rates for kernel regression is a classical topic in machine learning theory, with an extensive literature. The goal of this work is comparing the rates obtained by training a kernel method using one-pass SGD with two benchmarks: the minimax rates by and the KRR rates with a given regularisation. These have been derived in previous works both under generic source and capacity conditions e.g. (Caponnetto & De Vito, 2007; Cui et al. 2021; Lu et al. 2024), but also specifically for dot product kernels in the sphere (Bordelon et al. 2020; Bietti & Bach, 2021; Misiakiewicz, 2022)\n\n- The proofs also leverage previous results on the analysis of SGD for kernel methods (Dieuleveut & Bach 2016).", "essential_references_not_discussed": "1. While the authors properly acknowledge the related literature which is closest to their work on the technical side, there are major omissions concerning related results which are directly relevant to this discussion, both when it comes to the learning curves of dot-product kernel on spherical data in the regime $n=\\Theta(d^{\\gamma})$ (Bordelon et al. 2020) and to the learning curves of KRR under source and capacity conditions in the $n\\gg d$ regime (Cui et al. 2021).\n\n    Indeed, these contain results which are discussed here, but that precede other references used by the authors. For example, Cui et al. (2021) provided a full picture of the rates of the asymptotic rates of KRR as a function of the noise level and regularization, including the suboptimal rate of KRR when $s>2$ at optimal quoted from Li et al. (2023).   \n\n2. Although you cite (Pillaud-Vivien et al., 2018) in the end of Section 5, it would be good to also mention it in the related works, when discussing SGD being suboptimal.\n\n- [Bordelon et al. 2020] Bordelon, Blake, Abdulkadir Canatar, and Cengiz Pehlevan. \"Spectrum dependent learning curves in kernel regression and wide neural networks.\" In International Conference on Machine Learning, pp. 1024-1034. PMLR, 2020.\n\n- [Cui et al. 2021] Cui, H., Loureiro, B., Krzakala, F., & Zdeborová, L. (2021). Generalization error rates in kernel regression: The crossover from the noiseless to noisy regime. Advances in Neural Information Processing Systems, 34, 10131-10143.", "other_strengths_and_weaknesses": "The paper is well-written and easy to follow. The results are interesting. The major weaknesses is that the discussion is specified to dot-product kernels in the sphere, while I believe that part of the discussion should generalize to more general settings. I also consider the omission of relevant related literature as an important weakness.", "other_comments_or_suggestions": "The absence of numbers in the equations make it hard to refer to them. But here are a list of possible typos:\n\n- Related work, L069 right column, I think there is a $-$ sign missing in $n^{\\frac{s\\alpha}{s\\alpha+1}}$\n- Section 3, L127 right column: the adjoint should be $T^{\\star}:\\mathcal{H}\\to L^{2}$.\n- 1st equation of Section 6.2: $f^{b}=f_{\\star}$ and $\\tilde{f}^{b}=f_{\\star}$.\n- 2nd equation of Section 5.2: double check the rate $\\frac{2d+2}{3d+1}$, I think it might be $\\frac{2d+2}{3d+2}$ instead.", "questions_for_authors": "- What are the challenges of stating the results of Section 5.2. for general source and capacity conditions of the kernel? What is exactly the role played by the spherical data here?\n\n- I think it would be a nice addition to the manuscript to have either a plot or a schematic drawing summing the behaviour of the error curve of SGD in the different polynomial regimes $n=\\Theta(d^{\\gamma})$ at increasing $\\gamma$.", "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": "zkv1NrLgwo", "reviewer": "Reviewer_2WFu", "summary": "This paper analyzes the excess risk and the minimax lower bound of single-pass stochastic gradient descent (SGD) in kernel regression under the combinations of the following settings:\n\n1) the model is well-specified or misspecified ( the source condition constant $s<1$ or $s\\geq 1$ );\n\n2) the number of data is in proportional/large-dimension regime ($n\\sim d^\\gamma$ or $n\\gg d^\\gamma$ for some constant $\\gamma>0$);\n\n3) the online (single-batch) SGD is run on exponentially decaying step size schedule or constant step size with averaged iterates.\n\nThere are several implications from the above results, for example, SGD achieves min-max optimal rate in almost all the cases, in contrast to the saturation effect on the kernel ridge regression (KRR), and it is also the first theoretical proof showing exponential decaying step size schedule is better than iterative averaging method in the context of kernel setting.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to extend our sincere appreciation to you for the thorough review and valuable feedback. We are grateful that you not only accurately summarized our contributions but also expressed strong appreciation. We would like to address your suggestion and the question you raised regarding possible extensions of our research. \n***\n# Author's Response to Suggestion: \n\n>*1. \"Maybe a summarising table about the results on each combination of settings could help the presentation.\"*\n\nThis is a meaningful suggestion. We will include tables both summarizing our results and comparing them with prior work to facilitate a better understanding of this paper. Due to space constraints, this content will be added to the Appendix.\n***\n# Author's Response to Questions\n## Author's Response to Question 1:\n\n>*\"1. What would be the technical difficulties to extend the result to non-dot-product kernels?\"*\n\nExtending our proof to general kernels only requires verifying two conditions: (1) capacity condition or the eigenvalue decay rate (EDR) of the target kernel, and (2) a distributional condition controlling the residual noise $f _t^{b(1)}$ and $f _t^{v(1)}$, such as the kernel is bounded, or $\\mathbb{E}[K(\\mathbf{x},\\mathbf{x} )K _{\\mathbf{x}}\\otimes K _{\\mathbf{x}}]\\preceq \\kappa \\mathbb{E}[K _{\\mathbf{x}}\\otimes K _{\\mathbf{x}}]$, or $\\mathbb{E} \\left \\langle f,K _{\\mathbf{x} } \\right \\rangle ^4\\le \\kappa \\left \\Vert f \\right \\Vert _{\\mathcal{H} } ^2$. \n Once the EDR of the target kernel is known and the kernel satisfies the required distributional condition, our analysis can be applied by analyzing the iterative behavior of the residual noise under these corresponding conditions.\n\n## Author's Response to Question 2:\n\n>*2. \"Could one extend the analysis of the online SGD training to other spectral algorithms mentioned in [1]?\"*\n\nThis is a deep and interesting question that points to a promising direction for future work. Spectral algorithms construct the estimator $\\hat{f} _{\\lambda}=\\phi _{\\lambda}(T _X)g _Z$ using the sample basis function $g _Z=\\frac{1}{n}\\sum _{i=1}^{n}y _iK(x _i,\\cdot)$, the sample covariance operator $T _X=\\frac{1}{n}\\sum _{i=1}^{n}K _{x _i}K _{x _i}^{\\ast}$, and a filter function $\\phi _{\\lambda}$. To obtain a stochastic version of the corresponding spectral algorithm, one may first reformulate the spectral estimator as the solution to a variational problem on a functional manifold. Then, by selecting an appropriate Bregman divergence, the stochastic approximation to the spectral method can be obtained by stochastic mirror descent. This perspective enables the analysis of the implicit regularization induced by stochastic mirror descent on the functional manifold. Furthermore, by examining how the data structure constrains the optimization trajectory, one can derive generalization bounds.\n\n**References:**\n\n[1] Lu et al. \"On the Saturation Effects of Spectral Algorithms in Large Dimensions.\" Advances in Neural Information Processing Systems 37 (2025): 7011-7059.", "claims_and_evidence": "Yes, the theoretical claims are proved in the paper and validation experiments are shown.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I check the proof from the main text as well as the proof in the appendix up to section B. I might have time to proof-read the rest, but the proof seems correct so far. The technique is a standard bias-variance decomposition with a careful modification for the settings in interest.", "experimental_designs_or_analyses": "Yes, they are sound and valid.", "relation_to_broader_scientific_literature": "The contribution is significant in kernel method, online learning and also to the broader scope of neural network training under the neural tangent kernel (NTK) framework. \n\nAs pointed out in the paper, saturation effect and the learning curve for KRR / kernel gradient flow is known. But such results on online SGD setting is novel and brings important insights to the field.", "essential_references_not_discussed": "Most relevant related works are cited.", "other_strengths_and_weaknesses": "The paper is written in a precise and concise way, the concepts and intuitions are well-elaborated, so the paper is easy to follow.", "other_comments_or_suggestions": "Maybe a summarising table about the results on each combination of settings could help the presentation. This would offer a more macroscopic view on the contributions/findings of the paper.", "questions_for_authors": "I am interested in potential extensions of the current results presented in this paper:\n\n1. What would be the technical difficulties to extend the result to non-dot-product kernels?\n\n2. Could one extend the analysis of the online SGD training to other spectral algorithms mentioned in [1]?\n\n\n---\n[1] Lu, Weihao, Yicheng Li, and Qian Lin. \"On the Saturation Effects of Spectral Algorithms in Large Dimensions.\" Advances in Neural Information Processing Systems 37 (2025): 7011-7059.", "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:

Meta-review: This paper studies the generalization performance of kernel regression trained by single-pass SGD and compares the method to ridge regression. The analysis is conducted under the standard source condition assumption on the target. Two scaling are considered the 'high-dimensional' setting where number of sample (n) is proportional to (d) number of parameters and $n = d^{\eta}$.  The results show that exponentially decaying step sizes allow SGD to achieve minimax optimal rates and a constant stepsize with iterate averaging is proven to match the minimax lower bounds in high-dimensions. 

The results are interesting as shared by the reviewers and extends a long history of research in this area. I suggest that the authors take into consideration the concerns of the reviewers particularly including references and cleaning up the proofs in the appendix.
Decision: Accept (poster)