mlsanityData to 14 Oct 2026

Stochastic gradient descent with initial regularization

arXiv 2608.22953 ↗First posted 24 Aug 2026cs.LG math.OC stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

We analyze a variant of stochastic gradient descent with initial regularization (SGDIR) and derive dimension-free upper bounds on its expected excess risk for the squared loss. In the noiseless case, we obtain new bounds for both averaged and non-averaged SGDIR under moment, source, and capacity assumptions. For a particular value of the source parameter, these bounds are of order m-2log2m, where the number of training samples is of order m. For another value of the source parameter, we obtain, for any ε>0, bounds of order m-3+ε, provided that the capacity parameter exceeds ε-1. We also establish a lower bound that matches our upper bounds in certain regimes up to a polylogarithmic factor. In the noisy case, we provide an instance-based comparison between SGDIR and ridge regression. Under general assumptions and a mild lower bound on the regularization parameter, we show that the expected excess risk of SGDIR is no larger than that of ridge regression, up to a polylogarithmic factor. Numerical experiments on synthetic and real data are consistent with our theoretical findings.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 22 of its 32 references that are in the map. First posted on arXiv 24 Aug 2026.

Builds on

22 of 32 references.

References · 22

  1. 2019Benign Overfitting in Linear Regressioncited by 549
  2. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 513
  3. 2016Generalization Properties of Learning with Random Featurescited by 164
  4. 2020Benign overfitting in ridge regressioncited by 153
  5. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  6. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 111
  7. 2021Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regimecited by 96
  8. 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
  9. 2018Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passescited by 69
  10. 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
  11. 2024Scaling Laws in Linear Regression: Compute, Parameters, and Datacited by 57
  12. 2021Last iterate convergence of SGD for Least-Squares in the Interpolation regimecited by 42
10 more
  1. 2020Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Modelcited by 39
  2. 2018Learning with SGD and Random Featurescited by 33
  3. 2021The Benefits of Implicit Regularization from SGD in Least Squares Problemscited by 32
  4. 2019Beating SGD Saturation with Tail-Averaging and Minibatchingcited by 21
  5. 2022An elementary analysis of ridge regression with random designcited by 15
  6. 2019Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Accelerationcited by 12
  7. 2025Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regimecited by 12
  8. 2023Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Samplingcited by 10
  9. 2025Risk Comparisons in Linear Regression: Implicit Regularization Dominates Explicit Regularizationcited by 8
  10. 2024Unbiased least squares regression via averaged stochastic gradient descentcited by 1

Built on by

Not cited yet.