mlsanityData to 7 Oct 2026

Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime

arXiv 2203.03159 ↗First posted 7 Mar 2022cs.LG math.OC stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

Stochastic gradient descent (SGD) has achieved great success due to its superior performance in both optimization and generalization. Most of existing generalization analyses are made for single-pass SGD, which is a less practical variant compared to the commonly-used multi-pass SGD. Besides, theoretical analyses for multi-pass SGD often concern a worst-case instance in a class of problems, which may be pessimistic to explain the superior generalization ability for some particular problem instance. The goal of this paper is to sharply characterize the generalization of multi-pass SGD, by developing an instance-dependent excess risk bound for least squares in the interpolation regime, which is expressed as a function of the iteration number, stepsize, and data covariance. We show that the excess risk of SGD can be exactly decomposed into the excess risk of GD and a positive fluctuation error, suggesting that SGD always performs worse, instance-wisely, than GD, in generalization. On the other hand, we show that although SGD needs more iterations than GD to achieve the same level of excess risk, it saves the number of stochastic gradient evaluations, and therefore is preferable in terms of computational time.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 33 of its 46 references that are in the map. First posted on arXiv 7 Mar 2022.

Builds on

33 of 46 references.

References · 33

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  2. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  3. 2019Benign Overfitting in Linear Regressioncited by 544
  4. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 508
  5. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 259
  6. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  7. 2020Benign overfitting in ridge regressioncited by 152
  8. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  9. 2015High-Dimensional Asymptotics of Prediction: Ridge Regression and Classificationcited by 146
  10. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  11. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 132
  12. 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
21 more
  1. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  2. 2020On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regressioncited by 97
  3. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 90
  4. 2013Early stopping and non-parametric regression: An optimal data-dependent stopping rulecited by 86
  5. 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
  6. 2018Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passescited by 69
  7. 2018A Continuous-Time View of Early Stopping for Least Squarescited by 67
  8. 2019The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squarescited by 67
  9. 2018Random Shuffling Beats SGD after Finite Epochscited by 66
  10. 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
  11. 2019How Good is SGD with Random Shuffling?cited by 63
  12. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 57
  13. 2018Stability and Convergence Trade-off of Iterative Optimization Algorithmscited by 53
  14. 2021Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regressioncited by 37
  15. 2018On exponential convergence of SGD in non-convex over-parametrized learningcited by 33
  16. 2021Stability of SGD: Tightness Analysis and Improved Boundscited by 33
  17. 2021The Benefits of Implicit Regularization from SGD in Least Squares Problemscited by 32
  18. 2017Early stopping for kernel boosting algorithms: A general analysis with localized complexitiescited by 27
  19. 2018Iterate averaging as regularization for stochastic gradient descentcited by 27
  20. 2017A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)cited by 25
  21. 2019Beating SGD Saturation with Tail-Averaging and Minibatchingcited by 21

Built on by

Cited by year

Citing papers per year: 2022: 4; 2023: 0; 2024: 1; 2025: 3.

8 papers.

  1. 2022Homogenization of SGD in high-dimensions: Exact dynamics and generalization propertiescited by 26
  2. 2022Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensionscited by 23
  3. 2024How Transformers Utilize Multi-Head Attention in In-Context Learning? A Case Study on Sparse Linear Regressioncited by 13
  4. 2022Provable Generalization of Overparameterized Meta-learning Trained with SGDcited by 9
  5. 2025Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regressioncited by 9
  6. 2025Improved Scaling Laws in Linear Regression via Data Reusecited by 7
  7. 2025Towards Theoretical Understanding of Transformer Test-Time Computing: Investigation on In-Context Linear Regressioncited by 1
  8. 2022Local SGD in Overparameterized Linear Regressioncited by 0