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.

Author's Response to Suggestion:

1. "Maybe a summarising table about the results on each combination of settings could help the presentation."

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

Author's Response to Questions

Author's Response to Question 1:

"1. What would be the technical difficulties to extend the result to non-dot-product kernels?"

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

Author's Response to Question 2:

2. "Could one extend the analysis of the online SGD training to other spectral algorithms mentioned in [1]?"

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

References:

[1] Lu et al. "On the Saturation Effects of Spectral Algorithms in Large Dimensions." Advances in Neural Information Processing Systems 37 (2025): 7011-7059.

Thank you for your constructive comments and recognition of our contributions. Below, we address your concerns and questions in detail.

Author's Response to Essential References:

1. "Related References Bordelon et al. (2020) and Cui et al. (2021)":

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

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

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

2. "Mentioning Pillaud-Vivien et al. (2018) in the Related Works":

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

Author's Response to Suggestions:

Thank you for pointing out the typos, which definitely helps us improve the paper in a concrete way. We have made the following revisions:

• Revised L069 right column as $n^{-\frac{s\alpha}{s\alpha+1}}$.
• Revised L127 right column as $T^{\ast}: \mathcal{H}\rightarrow L^2$.
• Revised 1st equation of Section 6.2 as $f^{b} _0=f _{\rho}^{\ast}$ ,$\tilde{f} _{0}^{b}=f _{\rho}^{\ast}$.
• Revised 2nd equation of Section 5.2 as $n^{-\frac{2d+2}{3d+2}}$.

Author's Response to Questions

Author's Response to Question 1:

1. "What are the challenges of stating the results of Section 5.2. for general source and capacity conditions of the kernel?"

Thank you for raising the question of whether our asymptotic results can be extended to general source and capacity conditions of the kernel. First, 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. Once the target kernel satisfies certain capacity conditions, along with a distributional condition that controls the residual noise of $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$, our analysis can be directly applied to obtain corresponding convergence rates.

2. "What is exactly the role played by the spherical data here?"

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

Author's Response to Question 2:

"Addition of a plot summarizing the behavior of the error curve of SGD."

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

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.

Response to Questions:

1. 164R: $N(d,k)$.

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

2. Online algorithm.

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

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

This is a typo, but the conclusion $\mathrm{tr} (T )=\mathbb{E}{K(X,X)}$ still holds. A revised proof is provided below: \begin{aligned} \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}}， \end{aligned} where $(a)$ follows from the reproducing property, $(b)$ follows from Parseval's identity.

4. 589, (10): Typo in Equa.

We have corrected this.

5. 667, (23): Why positive definiteness of $\boldsymbol{\Sigma}$ imply (23)?

6. 671, (24): $i$ and $j$?

7. 719, (31): $i$ and $j$?

We 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: By 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}$. Based on this, we can obtain the desired result in Lemma B.1. The proofs of Lemma B.2 and (76) follow the same reasoning.

8. 712, 733, 744, 748, 753, etc.: $\mathbb{E}$?

We have removed the expectation where no randomness is involved.

9. 761: (37)?

Below is an explanation of (37). Due 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}$. For all $i$, $\boldsymbol{I} - \eta _i\boldsymbol{\Sigma}$ and $\boldsymbol{\Sigma}$ are positive semidefinite, self-adjoint and mutually commuting operators. Denote $\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.$

10. 424, 813: What is $k^{\ast}$?

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

11. 790, (42): $\mathbb{E}[ \Xi _{t} ]=0$?

We apologize for the confusion caused by the improper definition of $f _{\rho}^{\ast}$ in Line 630. Although 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.

Response to Suggestions:

We appreciate your constructive writing suggestions. All points have been addressed, and we have further refined the manuscript.

Response to Related Works:

Thank you for sharing the references. They have been included in the revised version. Additionally, we have expanded our discussion of the KRR literature.

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.

Author's Response to Essential References:

Thank you for sharing these important related works with us, which have helped us to improve the completeness of our discussion.

1. "Import paper on dot product kernel regression":

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.

2. "Related works on early stopped GD":

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.

Specifically, 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$.

3. "Related works on early stopped SGD":

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.

Author's Response to Comments or Suggestions:

Thank you for your suggestions and for pointing out the typos. We have made the following revisions accordingly.

1. "The embedding operator in Line 126 (Right)":

Our Response: We have made the revision $T^{\ast}: \mathcal{H}\rightarrow L^2$.

2. "Clarify of $s$ in Assumption 4.3":

Our Response: We have now clarified in Assumption 4.3 that the source condition is specified for a given $s$.

3. "Explicit Definition of $f_{\rho}^{\ast}$ in Theorem 5.1":

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.

4. "Write 4.7 and 5.1 in the same language":

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.

Author's Response to Question 1:

1. "Do you what happens if instead of stopping early the algorithms are run until convergence? Do they converge to the KKR solutions?"

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