Pith. sign in

REVIEW 3 major objections 5 minor 60 references

Learning Curves of Stochastic Gradient Descent in Kernel Regression

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper claims that single-pass SGD with an exponentially decaying step size reaches the minimax-optimal excess risk in kernel regression on the sphere, across all sample-size scales in high dimensions and for all but the roughest…

desk verdict Solid high-dimensional SGD rates with a systematic overclaim: the proved bounds are only log-factor optimal, so the abstract's 'up to constants' minimax statement needs correction. read the letter →

arxiv 2505.22048 v1 pith:GDMAXDRW submitted 2025-05-28 stat.ML cs.LG

Haihan Zhang , Weicheng Lin , Yuanshi Liu , Cong Fang This is my paper
classification stat.MLcs.LG
keywords stochasticgradientdescentkernelregressionminimaxoptimalitysaturationeffectexcessrisksourceconditiondot-productonsphereneuraltangent
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper is about the learning curves of single-pass stochastic gradient descent (SGD) in kernel regression on the sphere, and its central claim is that SGD is not merely a cheap approximation to kernel ridge regression: with the right step-size schedule it reaches the minimax-optimal excess risk at every sample-size scale. In the high-dimensional regime $n\asymp d^{\gamma}$, the paper proves that SGD with an exponentially decaying step size achieves rate $d^{-\min\{\gamma-p,\,s(p+1)\}}$ up to logarithmic factors for well-specified problems $s\ge1$, and that averaged-iterate SGD achieves the same rate for misspecified problems $00$. In the asymptotic regime $n\gg d$ with the ReLU neural tangent kernel, decaying-step SGD matches the lower bound $n^{-s(d+1)/(s(d+1)+d)}$ for $s\ge1$ and averaged SGD does so for $1/(d+1)\le s\le1$, so optimality holds for all but the roughest targets. The central mechanism is the exponentially decaying step-size schedule, which acts as an implicit regularizer and avoids the saturation effect that makes ridge regression suboptimal for smooth targets. As a byproduct, the paper claims the first provable advantage of decaying step sizes over iterate averaging in this common setting.

What carries the argument

The load-bearing object is the exponentially decaying step-size schedule $\eta_t=\eta_0/2^{\ell-1}$ on blocks of length $m=\lceil n/\log_2 n\rceil$: the early constant-size steps shrink the bias along the large-eigenvalue directions, while the later halving steps keep the variance contribution from growing, producing an implicit regularization that needs no explicit ridge penalty. The proof decomposes the error into population bias and variance terms driven by the covariance operator $\Sigma$, and fluctuation terms driven by $K_x\otimes K_x-\Sigma$, then balances them by choosing a cutoff $k^*=\Theta(d^p)$ with $p=\lceil\gamma/(s+1)\rceil-1$; the balance works because Assumption 3 gives $\mu_k=\Theta(d^{-k})$ and $N(d,k)=\Theta(d^k)$ for the eigenvalues and multiplicities of the dot-product kernel on $S^d$. For the averaged-iterate variant used at $0<s<1$, a residual inequality from the online-learning literature controls the difference between the true bias and its population version, which is what makes the misspecified case tractable.

What would settle it

Take a dot-product kernel on $S^d$ with a zero or negative Maclaurin coefficient at degree $j\le\lfloor\gamma\rfloor+3$, set $n\asymp d^{\gamma}$, generate $y=f_\rho^*(x)+\epsilon$ with $f_\rho^*\in[H]^s$, $s\ge1$, and run decaying-step SGD; if the excess risk still decays like $d^{-\min\{\gamma-p,\,s(p+1)\}}$, then Assumption 3 is not the controlling factor, while a visible change or plateau would confirm the assumed spectral concentration. For the asymptotic claim, estimate the eigenvalue decay of the ReLU NTK on $S^d$ directly: if $\lambda_j$ deviates from $j^{-(d+1)/d}$, the paper's rate $n^{-s(d+1)/(s(d+1)+d)}$ should fail in that regime.

Watch

Extended reading notes

Core claim

The paper's discovery, stated on its own terms, is that single-pass online SGD on dot-product kernels over $S^d$ attains the minimax lower bounds for kernel regression under source condition $s>0$ in the high-dimensional scaling $n\asymp d^{\gamma}$, and for $s\ge 1/(d+1)$ in the asymptotic scaling $n\gg d$. For well-specified targets ($s\ge1$), the final iterate of SGD with an exponentially decaying step size has excess risk $\mathcal{O}(d^{-\gamma+p}\log^2 d)$ when $\gamma\in(ps+p,\,ps+p+s]$ and $\mathcal{O}(d^{-(p+1)s})$ when $\gamma\in(ps+p+s,\,(p+1)s+p+1]$, where $p=\lceil\gamma/(s+1)\rceil-1$; these match the minimax bound $\Omega(d^{-\min\{\gamma-p,\,s(p+1)\}})$ up to constants. For misspecified targets ($0<s<1$), constant step size with averaged iterates attains the same rates. In the asymptotic regime the same two schedules match $\Omega(n^{-s(d+1)/(s(d+1)+d)})$ for $s\ge1$ and $1/(d+1)\le s\le1$, respectively; the loss of optimality below $s<1/(d+1)$ is attributed to the optimization capacity of plain SGD. The paper interprets this as showing that SGD does not suffer the saturation of kernel ridge regression, and that the exponentially decaying schedule is the reason.

Load-bearing premise

The rate balances are tuned to spectral scalings that are assumed or imported rather than proved here: in high dimensions every Maclaurin coefficient of the kernel up to order $\lfloor\gamma\rfloor+3$ must be positive so that eigenvalues and multiplicities scale as $d^{-k}$ and $d^k$, and in the asymptotic regime the ReLU neural-tangent-kernel eigenvalues must obey the cited decay $\lambda_j\asymp j^{-(d+1)/d}$.

Editorial extensions

If this is right

  • In high dimensions ($n\asymp d^{\gamma}$), the two schedules together cover all source-condition smoothness levels $s>0$ at the minimax-optimal rate, so a single-pass online algorithm is statistically as good as offline ridge regression up to constants.
  • The exponentially decaying schedule eliminates the saturation effect for smooth targets: in the high-dimensional setting it is optimal for arbitrarily large $s$, where kernel ridge regression is provably suboptimal for $s>1$.
  • The asymptotic regime shows the same conclusion for the ReLU neural tangent kernel whenever $s\ge1/(d+1)$; since this threshold shrinks as the input dimension grows, heavy overparameterization makes even very rough targets learnable at the optimal rate.
  • Averaged-iterate SGD is not merely equivalent to decaying-step SGD: the paper proves a lower bound showing it loses optimality for $s>1$ in high dimensions and $s>2$ asymptotically, giving the first provable advantage of decaying step sizes over averaging.
  • For any bounded kernel with polynomially decaying eigenvalues that satisfies the same spectral scalings, the same decaying-step schedule should reach the corresponding minimax rate; the appendix carries a general bound that only needs boundedness of the kernel.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the implicit-regularization story is as general as the paper suggests, the same exponentially decaying schedule should yield minimax rates for Sobolev-space regression targets, since Sobolev kernels have polynomial eigenvalue decay; the paper states this expectation in its discussion but does not prove it.
  • The dimension-dependent threshold $1/(d+1)$ implies that averaged SGD becomes optimal for a wider range of rough targets as dimension grows; a natural testable prediction is that learning curves for $s$ slightly below $1/(d+1)$ interpolate smoothly rather than dropping off a cliff.
  • A direct way to stress-test Assumption 3 is to replace the dot-product kernel by one whose Maclaurin coefficient at degree $\lfloor\gamma\rfloor+3$ is zero or negative; the predicted plateau and rate structure should change, which would confirm that the positive-coefficient condition is doing the work.
  • The paper's ReLU-NTK asymptotic claims inherit the cited eigenvalue decay $\lambda_j\asymp j^{-(d+1)/d}$; if that decay law were shown to fail for deep NTKs at finite width, only the high-dimensional theorems would remain fully self-contained.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper analyzes single-pass SGD for kernel regression on the sphere, covering both the high-dimensional regime n≍d^γ and the asymptotic regime n≫d. Under a source condition with smoothness s, it proposes exponentially decaying step sizes for well-specified problems (s≥1) and averaged SGD for misspecified problems (0<s<1). The main results are upper bounds on the excess risk that match the exponents of quoted minimax lower bounds (d^{-min{γ-p,s(p+1)}} in high dimensions and n^{-s(d+1)/(s(d+1)+d)} asymptotically), with additional logarithmic factors in some regimes. The paper further argues that the decaying step size avoids the saturation effect of kernel ridge regression and provides a lower bound showing that averaged SGD is suboptimal for large s. The high-dimensional proofs are self-contained, relying on a bias-variance decomposition and eigenvalue scaling of dot-product kernels; the asymptotic results use the NTK eigenvalue decay λ_j≍j^{-(d+1)/d} and quoted minimax bounds.

Significance. If the claims were fully established, the paper would be a valuable contribution: it would show that a practical single-pass algorithm matches minimax rates across a range of scalings and avoids the saturation phenomenon, with the first provable separation between decaying and averaged step schedules. The technical machinery in Proposition 4 and Corollary 5 is coherent, and the high-dimensional analysis (Theorems 1 and 2) is, apart from the logarithmic gaps discussed below, internally consistent. I do not reproduce the concern that the step size in Theorem 3 grows; for s≥1, η0=Θ(n^{(1-s(d+1))/(s(d+1)+d)}) is o(1), so the boundedness condition η0≤1/λ1 is eventually satisfied. The central weakness is that the paper claims optimality 'up to constants' while the proved upper bounds in Theorem 1(i) and Theorem 3 contain logarithmic factors that diverge from the quoted lower bounds. The results are thus better characterized as optimality up to logarithmic factors rather than up to constants.

major comments (3)
  1. [Theorem 1(i) and Abstract] The upper bound in Theorem 1(i) is E[||f_n^dec − f*_ρ||^2_{L2}] ≲ d^{−γ+p} log_2^2 d, while the quoted minimax lower bound in Proposition 1 is Ω(d^{−γ+p}). Since log_2^2 d is unbounded, the abstract's claim that SGD is min-max optimal 'up to constants among all the scales' is not established. The logarithmic factor is structural rather than an artifact of a loose step: it arises from the variance estimate k* log_2^2 n/n in Lemma 7 and survives the balancing with k*=Θ(d^p). The theorem and the abstract should either be sharpened to remove the log factor or restated as optimality up to logarithmic factors.
  2. [Theorem 3 and Section 5.2] Theorem 3 states E ≲ log^{s/2} n · n^{−α} with α=s(d+1)/(s(d+1)+d), while the lower bound in Proposition 2 is Ω(n^{−α}). The text immediately after the theorem says it 'demonstrates that SGD ... can achieve optimality for any s>1', which does not follow because the multiplicative log^{s/2} n diverges. The log factor comes from the bias bound in Lemma 6, (log_2 n/(nη0))^s, and from the variance term in Lemma 7; both survive the final balancing. The 'up to constants' optimality claim in the abstract is therefore unsupported in the asymptotic regime.
  3. [Sections 5, 6 and Table 1] The narrative in Sections 5 and 6 and the summary Table 1 repeatedly state that SGD is 'optimal' in high-dimensional settings for all s>0 and in asymptotic settings for s≥1/(d+1). Given the logarithmic gaps in Theorem 1(i) and Theorem 3, these statements should explicitly read 'optimal up to logarithmic factors' unless the theorems are strengthened. The abstract's phrase 'exact orders of the excess risk curves' is likewise too strong in the regimes where the upper bound carries a logarithmic factor and no matching lower bound for the specific SGD algorithm is provided.
minor comments (5)
  1. [Proofs of Theorems 1 and 3] The step 'η0 σ^2 κ^2/(2−η0 κ^2) ≤ η0 σ^2 κ^2 ≤ σ^2 = 1' assumes σ=1, which is not stated in the theorem hypotheses. Since σ is treated as a constant, this does not affect the rates, but the assumption should be stated or the equality should be replaced by a constant bound.
  2. [Theorems 1 and 2] The integer p is introduced as 'for some p∈N' without an explicit connection to p=⌈γ/(s+1)⌉−1 used in Proposition 1. The interval partition is correct, but making the connection explicit would help the reader verify that the exponent in the upper bound matches the exponent in the lower bound.
  3. [Theorems 3 and 4] The asymptotic results rely on the NTK eigenvalue decay λ_j≍j^{−(d+1)/d} and on the minimax lower bound of Caponnetto and De Vito [2007], both of which concern a fixed dimension d. The phrase 'n≫d' does not specify whether d is fixed or growing with n; if d may grow, the constants in the eigenvalue decay and the validity of the quoted lower bound require qualification.
  4. [Lemma 7] In the proof of Lemma 7, the displayed bound replaces (2/(em))^2 by (4 log_2 n/(en))^2, which is a factor of 4 larger than the preceding line. This is a harmless constant-factor typo but should be corrected for consistency.
  5. [Appendix E] There are small typographical issues in Appendix E, including the heading 'Lemma 21.2' and the cross-reference 'according to the proof of Lemma 2' where Lemma 21 is meant.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the upper bounds are derived in-paper and the lower bounds are quoted from external work; only minor non-load-bearing self-citations appear.

full rationale

The paper's derivation chain is not circular. The upper-bound analyses in Appendix B (Lemmas 4-13 and Proposition 4) and Appendix C (Lemmas 14-17 and Corollary 5) are self-contained under Assumptions 1-3, using bias-variance decompositions, step-size balancing, and the external spectral scaling Lemma 3 borrowed from Ghorbani et al. 2021 and Lu et al. 2023. No parameter is fitted to data, and no claimed prediction is defined in terms of the quantity it predicts. The minimax lower bounds in Propositions 1-2 and Theorems 6 and 9 are quoted from Lu et al. 2024a and Caponnetto and De Vito 2007; these are independent external results, not derived from the authors' upper-bound argument. Matching the upper bounds to these lower bounds is a genuine comparison, not a self-referential reduction. The source condition and kernel assumptions are the standard minimax setup shared by both bounds, which is how optimality is normally established. Self-citations such as Zhang et al. 2024a in Section 2 are contextual and are not load-bearing in any proof. There are correctness concerns -- the abstract's 'up to constants' claim is weakened by the logarithmic factors in Theorems 1 and 3, and the NTK extension of Assumption 3 is cited rather than proved -- but these are not instances of a result reducing to its own inputs. The paper's central claim therefore has independent content, and the circularity score is low.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

No invented entities. The free parameters are step-size and cutoff choices made in the proof, not fitted to data. All substantive assumptions are standard source and noise conditions plus spectral properties of inner-product kernels and NTK; the spectral assumptions are the most fragile because the NTK extension is only cited.

free parameters (4)
  • eta0 in Theorem 1 (step decay, well-specified high-dimensional) = Theta(d^{-gamma+p} log2 n ln d)
    Initial step size chosen by hand to balance the bias term (log n/(n eta0))^s against the variance terms k*/n and n eta0^2 sum lambda_k^2; not fitted to data.
  • eta0 in Theorem 2 (averaged SGD, misspecified high-dimensional) = Theta(d^{-gamma+p+s/2}) for p>=1, Theta(d^{-gamma/2}) for p=0
    Initial step size chosen so that the population bias and residual bias terms match the target rate; not fitted to data.
  • k* eigenvalue cutoff = Theta(d^p) in high-dimensional theorems; Theta(n^{d/(s(d+1)+d)}) in asymptotic proofs
    Threshold splitting the variance bound into leading and tail eigendirections; chosen to minimize the bound.
  • eta0 in Theorems 3 and 4 (asymptotic) = Theta(n^{1 - s(d+1)/(s(d+1)+d)}) (grows with n)
    This choice violates the proof's requirement eta0 <= min{1/kappa^2, 1/lambda_1}; if corrected to a decaying power of n it would be a hand-chosen balance point, but as written it is inconsistent.
assumptions (5)
  • domain assumption Source condition: f*_rho lies in the unit ball of the interpolation space [H]^s (Assumption 2)
    Defines the smoothness class over which the rates are measured; standard in kernel regression.
  • domain assumption Noise and residual condition: E[Xi tensor Xi] <= sigma^2 Sigma (Assumption 1)
    Controls the variance terms in the bias-variance decomposition.
  • domain assumption Uniform distribution on the sphere and dot-product kernel satisfying Assumption 3
    Supplies the eigenvalue and multiplicity scalings mu_k = Theta(d^{-k}) and N(d,k)=Theta(d^k) through Lemma 3, which all high-dimensional rate balances depend on.
  • domain assumption NTK eigenvalue decay lambda_j = Theta(j^{-(d+1)/d}) in the asymptotic regime (Bietti and Bach 2021)
    Used in Theorems 3 and 4 and in the asymptotic lower bound; not re-derived.
  • standard math Quoted minimax lower bounds from Lu et al. 2024a and Caponnetto and De Vito 2007
    The paper relies on these external lower bounds to claim optimality; they are not proved in this paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Learning Curves of Stochastic Gradient Descent in Kernel Regression." pith.science (2026). https://pith.science/paper/GDMAXDRW

@misc{pith2026250522048,
  author       = {Pith},
  title        = {Pith review of: Learning Curves of Stochastic Gradient Descent in Kernel Regression},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GDMAXDRW}},
  note         = {Machine review of arXiv:2505.22048}
}
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 \emph{first} provable advantage of the scheme over the iterative averaging method in the common setting.

Figures

Figures reproduced from arXiv: 2505.22048 by the authors.

Figure 1
Figure 1. Log excess risk decay curves of SGD with the two schedules. The blue curves represent [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Convergence Rate of SGD and KRR with respect to [PITH_FULL_IMAGE:figures/full_fig_p046_2.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

60 extracted references · 55 canonical work pages

  1. [1]

    Advani, Andrew M

    Madhu S. Advani, Andrew M. Saxe, and Haim Sompolinsky. High-dimensional dynamics of generalization error in neural networks. Neural Networks, 2020

    work page 2020

  2. [2]

    Zico Kolter, and Ryan J

    Alnur Ali, J. Zico Kolter, and Ryan J. Tibshirani. A continuous-time view of early stopping for least squares regression. In International Conference on Artificial Intelligence and Statistics, 2019

    2019

  3. [3]

    Theory of reproducing kernels

    Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American Mathematical Society, 1950

    work page 1950

  4. [4]

    On exact computation with an infinitely wide neural net

    Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Neural Information Processing Systems, 2019

    work page 2019

  5. [5]

    Non-strongly-convex smooth stochastic approximation with convergence rate o (1/n)

    Francis Bach and Eric Moulines. Non-strongly-convex smooth stochastic approximation with convergence rate o (1/n). In Neural Information Processing Systems, 2013

    work page 2013

  6. [6]

    Benign overfitting in linear regression

    Peter L Bartlett, Philip M Long, G \'a bor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 2020

    work page 2020

  7. [7]

    Generalization in kernel regression under realistic assumptions

    Daniel Barzilai and Ohad Shamir. Generalization in kernel regression under realistic assumptions. In International Conference on Machine Learning, 2024

    work page 2024

  8. [8]

    On regularization algorithms in learning theory

    Frank Bauer, Sergei Pereverzev, and Lorenzo Rosasco. On regularization algorithms in learning theory. Journal of Complexity, 2007

    work page 2007

Show all 60 references
  1. [9]

    Yoshua Bengio. 2009. doi:10.1561/2200000006

    2009 doi

  2. [10]

    Reproducing kernel H ilbert spaces in probability and statistics

    Alain Berlinet and Christine Thomas-Agnan. Reproducing kernel H ilbert spaces in probability and statistics . Springer Science & Business Media, 2011

    2011

  3. [11]

    Deep equals shallow for R e LU networks in kernel regimes

    Alberto Bietti and Francis Bach. Deep equals shallow for R e LU networks in kernel regimes. In International Conference on Learning Representations, 2021

    2021

  4. [12]

    On the inductive bias of neural tangent kernels

    Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. In Neural Information Processing Systems, 2019

    2019

  5. [13]

    Optimal rates for regularization of statistical inverse learning problems

    Gilles Blanchard and Nicole M \"u cke. Optimal rates for regularization of statistical inverse learning problems. Foundations of Computational Mathematics, 2018

    2018

  6. [14]

    Spectrum dependent learning curves in kernel regression and wide neural networks

    Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning, 2020

    2020

  7. [15]

    Optimal rates for the regularized least-squares algorithm

    Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 2007

    2007

  8. [16]

    On lazy training in differentiable programming

    L\' e na\" c Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Neural Information Processing Systems, 2019

    2019

  9. [17]

    Generalization error rates in kernel regression: T he crossover from the noiseless to noisy regime

    Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborov\' a . Generalization error rates in kernel regression: T he crossover from the noiseless to noisy regime. In Neural Information Processing Systems, 2021

    2021

  10. [18]

    Kernel ridge vs

    Lee H Dicker, Dean P Foster, and Daniel Hsu. Kernel ridge vs. principal component regression: M inimax bounds and the qualification of regularization operators. Electronic Journal of Statistics, 2017

    2017

  11. [19]

    Nonparametric stochastic approximation with large step-sizes

    Aymeric Dieuleveut and Francis Bach. Nonparametric stochastic approximation with large step-sizes . The Annals of Statistics, 2016

    2016

  12. [20]

    Harder, better, faster, stronger convergence rates for least-squares regression

    Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach. Harder, better, faster, stronger convergence rates for least-squares regression. Journal of Machine Learning Research, 2017

    2017

  13. [21]

    How rotational invariance of common kernels prevents generalization in high dimensions

    Konstantin Donhauser, Mingqi Wu, and Fanny Yang. How rotational invariance of common kernels prevents generalization in high dimensions. In International Conference on Machine Learning, 2021

    2021

  14. [22]

    Sobolev norm learning rates for regularized least-squares algorithms

    Simon Fischer and Ingo Steinwart. Sobolev norm learning rates for regularized least-squares algorithms. Journal of Machine Learning Research, 2020

    2020

  15. [23]

    Notes on spherical harmonics and linear representations of L ie groups

    Jean Gallier. Notes on spherical harmonics and linear representations of L ie groups. preprint, 2009

    2009

  16. [24]

    The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares

    Rong Ge, Sham M Kakade, Rahul Kidambi, and Praneeth Netrapalli. The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares. In Neural Information Processing Systems, 2019

    2019

  17. [25]

    Linearized two-layers neural networks in high dimension

    Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension . The Annals of Statistics, 2021

    2021

  18. [26]

    Neural tangent kernel: Convergence and generalization in neural networks

    Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Neural Information Processing Systems, 2018

    2018

  19. [27]

    Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford

    Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Parallelizing stochastic gradient descent for least squares regression: Mini-batching, averaging, and model misspecification. Journal of Machine Learning Research, 2018

    2018

  20. [28]

    On the saturation effect of kernel ridge regression

    Yicheng Li, Haobo Zhang, and Qian Lin. On the saturation effect of kernel ridge regression. In International Conference on Learning Representations, 2023

    2023

  21. [29]

    On the eigenvalue decay rates of a class of neural-network related kernel functions defined on general domains

    Yicheng Li, Zixiong Yu, Guhan Chen, and Qian Lin. On the eigenvalue decay rates of a class of neural-network related kernel functions defined on general domains. Journal of Machine Learning Research, 2024

    2024

  22. [30]

    Optimal rates for regularized conditional mean embedding learning

    Zhu Li, Dimitri Meunier, Mattes Mollenhauer, and Arthur Gretton. Optimal rates for regularized conditional mean embedding learning. In Neural Information Processing Systems, 2022

    2022

  23. [31]

    ridgeless

    Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel “ridgeless” regression can generalize. The Annals of Statistics, 2020

    2020

  24. [32]

    On the multiple descent of minimum-norm interpolants and restricted lower isometry of kernels

    Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the multiple descent of minimum-norm interpolants and restricted lower isometry of kernels. In Conference on Learning Theory, 2020

    2020

  25. [33]

    Optimal rates for multi-pass stochastic gradient methods

    Junhong Lin and Lorenzo Rosasco. Optimal rates for multi-pass stochastic gradient methods. Journal of Machine Learning Research, 2017

    2017

  26. [34]

    Optimal rates for spectral algorithms with least-squares regression over H ilbert spaces

    Junhong Lin, Alessandro Rudi, Lorenzo Rosasco, and Volkan Cevher. Optimal rates for spectral algorithms with least-squares regression over H ilbert spaces. Applied and Computational Harmonic Analysis, 2020

    2020

  27. [35]

    Statistical optimality of divide and conquer kernel-based functional linear regression

    Jiading Liu and Lei Shi. Statistical optimality of divide and conquer kernel-based functional linear regression. Journal of Machine Learning Research, 2024

    2024

  28. [36]

    Optimal rate of kernel regression in large dimensions

    Weihao Lu, Haobo Zhang, Yicheng Li, Manyun Xu, and Qian Lin. Optimal rate of kernel regression in large dimensions. arXiv preprint arXiv:2309.04268, 2023

    2023 arXiv

  29. [37]

    On the P insker bound of inner product kernel regression in large dimensions

    Weihao Lu, Jialin Ding, Haobo Zhang, and Qian Lin. On the P insker bound of inner product kernel regression in large dimensions. arXiv preprint arXiv:2409.00915, 2024 a

    2024 arXiv

  30. [38]

    On the saturation effects of spectral algorithms in large dimensions

    Weihao Lu, Haobo Zhang, Yicheng Li, and Qian Lin. On the saturation effects of spectral algorithms in large dimensions. In Neural Information Processing Systems, 2024 b

    2024

  31. [39]

    Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression

    Theodor Misiakiewicz. Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression. arXiv preprint arXiv:2204.10425, 2022

    2022 arXiv

  32. [40]

    On converse and saturation results for T ikhonov regularization of linear ill-posed problems

    Andreas Neubauer. On converse and saturation results for T ikhonov regularization of linear ill-posed problems. SIAM Journal on Numerical Analysis, 1997

    1997

  33. [41]

    Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes

    Loucas Pillaud-Vivien, Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes. In Neural Information Processing Systems, 2018

    2018

  34. [42]

    Acceleration of stochastic approximation by averaging

    Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 1992

    1992

  35. [43]

    Early stopping and non-parametric regression: A n optimal data-dependent stopping rule

    Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Early stopping and non-parametric regression: A n optimal data-dependent stopping rule. Journal of Machine Learning Research, 2014

    2014

  36. [44]

    Learning theory estimates via integral operators and their approximations

    Steve Smale and Ding-Xuan Zhou. Learning theory estimates via integral operators and their approximations. Constructive Approximation, 2007

    2007

  37. [45]

    On regularization via early stopping for least squares regression

    Rishi Sonthalia, Jackie Lok, and Elizaveta Rebrova. On regularization via early stopping for least squares regression. arXiv preprint arXiv:2406.04425, 2024

    2024 arXiv

  38. [46]

    Mercer’s theorem on general domains: O n the interaction between measures, kernels, and RKHS s

    Ingo Steinwart and Clint Scovel. Mercer’s theorem on general domains: O n the interaction between measures, kernels, and RKHS s. Constructive Approximation, 2012

    2012

  39. [47]

    Optimal rates for regularized least squares regression

    Ingo Steinwart, Don R Hush, Clint Scovel, et al. Optimal rates for regularized least squares regression. In Conference on Learning Theory, 2009

    2009

  40. [48]

    Charles J. Stone. Optimal global rates of convergence for nonparametric regression. The Annals of Statistics, 1982

    1982

  41. [49]

    Benign overfitting in ridge regression

    Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. Journal of Machine Learning Research, 2023

    2023

  42. [50]

    Generalization error of spectral algorithms

    Maksim Velikanov, Maxim Panov, and Dmitry Yarotsky. Generalization error of spectral algorithms. In International Conference on Learning Representations, 2024

    2024

  43. [51]

    Last iterate risk bounds of SGD with decaying stepsize for overparameterized linear regression

    Jingfeng Wu, Difan Zou, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Last iterate risk bounds of SGD with decaying stepsize for overparameterized linear regression. In International Conference on Machine Learning, 2022

    2022

  44. [52]

    Precise learning curves and higher-order scalings for dot-product kernel regression

    Lechao Xiao, Hong Hu, Theodor Misiakiewicz, Yue Lu, and Jeffrey Pennington. Precise learning curves and higher-order scalings for dot-product kernel regression. In Neural Information Processing Systems, 2022

    2022

  45. [53]

    Information-theoretic determination of minimax rates of convergence

    Yuhong Yang and Andrew Barron. Information-theoretic determination of minimax rates of convergence. The Annals of Statistics, 1999

    1999

  46. [54]

    On early stopping in gradient descent learning

    Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On early stopping in gradient descent learning. Constructive approximation, 2007

    2007

  47. [55]

    The optimality of (accelerated) SGD for high-dimensional quadratic optimization, 2024 a

    Haihan Zhang, Yuanshi Liu, Qianwen Chen, and Cong Fang. The optimality of (accelerated) SGD for high-dimensional quadratic optimization, 2024 a

    2024

  48. [56]

    On the optimality of misspecified spectral algorithms

    Haobo Zhang, Yicheng Li, and Qian Lin. On the optimality of misspecified spectral algorithms. Journal of Machine Learning Research, 2024 b

    2024

  49. [57]

    Optimal rates of kernel ridge regression under source condition in large dimensions

    Haobo Zhang, Yicheng Li, Weihao Lu, and Qian Lin. Optimal rates of kernel ridge regression under source condition in large dimensions. arXiv preprint arXiv:2401.01270, 2024 c

    2024 arXiv

  50. [58]

    The phase diagram of kernel interpolation in large dimensions

    Haobo Zhang, Weihao Lu, and Qian Lin. The phase diagram of kernel interpolation in large dimensions. Biometrika, 2025

    2025

  51. [59]

    The benefits of implicit regularization from SGD in least squares problems

    Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, Dean P Foster, and Sham Kakade. The benefits of implicit regularization from SGD in least squares problems. In Neural Information Processing systems, 2021 a

    2021

  52. [60]

    Benign overfitting of constant-stepsize SGD for linear regression

    Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Benign overfitting of constant-stepsize SGD for linear regression. In Conference on Learning Theory, 2021 b

    2021

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.