mlsanityData to 14 Oct 2026

Learning Curves of Stochastic Gradient Descent in Kernel Regression

arXiv 2505.22048 ↗First posted 28 May 2025stat.ML cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

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 ngg dγ with any constant γ >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.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 40 of its 58 references that are in the map. First posted on arXiv 28 May 2025.

Builds on

40 of 58 references.

References · 40

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2018On Lazy Training in Differentiable Programmingcited by 675
  3. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 573
  4. 2019Benign Overfitting in Linear Regressioncited by 549
  5. 2017High-dimensional dynamics of generalization error in neural networkscited by 241
  6. 2020Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networkscited by 200
  7. 2018Just Interpolate: Kernel "Ridgeless" Regression Can Generalizecited by 190
  8. 2019On the Inductive Bias of Neural Tangent Kernelscited by 177
  9. 2019Linearized two-layers neural networks in high dimensioncited by 155
  10. 2020Benign overfitting in ridge regressioncited by 153
  11. 2017Sobolev Norm Learning Rates for Regularized Least-Squares Algorithmcited by 114
  12. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 111
28 more
  1. 2021Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regimecited by 96
  2. 2013Early stopping and non-parametric regression: An optimal data-dependent stopping rulecited by 89
  3. 2020Deep Equals Shallow for ReLU Networks in Kernel Regimescited by 85
  4. 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
  5. 2018Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passescited by 69
  6. 2018A Continuous-Time View of Early Stopping for Least Squarescited by 69
  7. 2016Optimal Rates For Regularization Of Statistical Inverse Learning Problemscited by 68
  8. 2019The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squarescited by 68
  9. 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
  10. 2018Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spacescited by 59
  11. 2022Optimal Rates for Regularized Conditional Mean Embedding Learningcited by 50
  12. 2022Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regressioncited by 45
  13. 2021Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regressioncited by 38
  14. 2021How rotational invariance of common kernels prevents generalization in high dimensionscited by 32
  15. 2021The Benefits of Implicit Regularization from SGD in Least Squares Problemscited by 32
  16. 2023On the Eigenvalue Decay Rates of a Class of Neural-Network Related Kernel Functions Defined on General Domainscited by 31
  17. 2023On the Optimality of Misspecified Spectral Algorithmscited by 28
  18. 2023Generalization in Kernel Regression Under Realistic Assumptionscited by 27
  19. 2024On the Saturation Effect of Kernel Ridge Regressioncited by 13
  20. 2023Optimal Rate of Kernel Regression in Large Dimensionscited by 11
  21. 2024Optimal Rates of Kernel Ridge Regression under Source Condition in Large Dimensionscited by 11
  22. 2024On Regularization via Early Stopping for Least Squares Regressioncited by 11
  23. 2024The phase diagram of kernel interpolation in large dimensionscited by 9
  24. 2022Statistical Optimality of Divide and Conquer Kernel-based Functional Linear Regressioncited by 8
  25. 2024The Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimizationcited by 8
  26. 2024On the Pinsker bound of inner product kernel regression in large dimensionscited by 2
  27. 2025On the Saturation Effects of Spectral Algorithms in Large Dimensionscited by 2
  28. 2024Generalization error of spectral algorithmscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Accelerating Single-Pass SGD for Generalized Linear Predictioncited by 0
  2. 2026Learning Curves and Benign Overfitting of Spectral Algorithms in Large Dimensionscited by 0
  3. 2026Implicit Target Shift in Online Learning: Characterization and Correctioncited by 0
  4. 2026What Makes a Strong Model? A Unified Spectral Analysis of Knowledge Transfer over High-dimensional Linear Regressioncited by 0