mlsanityData to 7 Oct 2026

Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression

arXiv 2110.06198 ↗First posted 12 Oct 2021cs.LG math.OC stat.MLcited by 37

Not on the map. Why?

Abstract (arXiv)

Stochastic gradient descent (SGD) has been shown to generalize well in many deep learning applications. In practice, one often runs SGD with a geometrically decaying stepsize, i.e., a constant initial stepsize followed by multiple geometric stepsize decay, and uses the last iterate as the output. This kind of SGD is known to be nearly minimax optimal for classical finite-dimensional linear regression problems (Ge et al., 2019). However, a sharp analysis for the last iterate of SGD in the overparameterized setting is still open. In this paper, we provide a problem-dependent analysis on the last iterate risk bounds of SGD with decaying stepsize, for (overparameterized) linear regression problems. In particular, for last iterate SGD with (tail) geometrically decaying stepsize, we prove nearly matching upper and lower bounds on the excess risk. Moreover, we provide an excess risk lower bound for last iterate SGD with polynomially decaying stepsize and demonstrate the advantage of geometrically decaying stepsize in an instance-wise manner, which complements the minimax rate comparison made in prior works.

Key facts. Cited by 37 papers in the map (data through 7 Oct 2026). Builds on 17 of its 36 references that are in the map. First posted on arXiv 12 Oct 2021.

Builds on

17 of 36 references.

References · 17

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2019Benign Overfitting in Linear Regressioncited by 544
  3. 2019Two models of double descent for weak featurescited by 194
  4. 2020Benign overfitting in ridge regressioncited by 152
  5. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  6. 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
  7. 2019The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squarescited by 67
  8. 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
  9. 2021Last iterate convergence of SGD for Least-Squares in the Interpolation regimecited by 41
  10. 2020Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Modelcited by 39
  11. 2021The Benefits of Implicit Regularization from SGD in Least Squares Problemscited by 32
  12. 2018Iterate averaging as regularization for stochastic gradient descentcited by 27
5 more
  1. 2017A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)cited by 25
  2. 2019Beating SGD Saturation with Tail-Averaging and Minibatchingcited by 21
  3. 2019A Universally Optimal Multistage Accelerated Stochastic Gradient Methodcited by 17
  4. 2019Stochastic algorithms with geometric step decay converge linearly on sharp functionscited by 14
  5. 2019A Generic Acceleration Framework for Stochastic Composite Optimizationcited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 6; 2023: 4; 2024: 5; 2025: 10; 2026: 10.

37 papers.

Sort:

By area:

  1. 2023How Many Pretraining Tasks Are Needed for In-Context Learning of Linear Regression?cited by 93
  2. 2024Scaling Laws in Linear Regression: Compute, Parameters, and Datacited by 54
  3. 2024Understanding Forgetting in Continual Learning with Linear Regressioncited by 26
  4. 2022The Power and Limitation of Pretraining-Finetuning for Linear Regression under Covariate Shiftcited by 25
  5. 2022Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensionscited by 23
  6. 2021Eigencurve: Optimal Learning Rate Schedule for SGD on Quadratic Objectives with Skewed Hessian Spectrumscited by 15
  7. 2025From Continual Learning to SGD and Back: Better Rates for Continual Linear Modelscited by 10
  8. 2025Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regimecited by 10
  9. 2022Provable Generalization of Overparameterized Meta-learning Trained with SGDcited by 9
  10. 2023Accelerated Convergence of Stochastic Heavy Ball Method under Anisotropic Gradient Noisecited by 9
  11. 2025Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regressioncited by 9
  12. 2022Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regimecited by 8
25 more
  1. 2023Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuroncited by 8
  2. 2026Anytime Pretraining: Horizon-Free Learning-Rate Schedules with Weight Averagingcited by 8
  3. 2025Improved Scaling Laws in Linear Regression via Data Reusecited by 7
  4. 2024The Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimizationcited by 6
  5. 2021On the Double Descent of Random Features Models Trained with SGDcited by 5
  6. 2025Seesaw: Accelerating Training by Balancing Learning Rate and Batch Size Schedulingcited by 5
  7. 2026Optimal Learning Rate Schedules under Functional Scaling Laws: Power Decay and Warmup-Stable-Decaycited by 4
  8. 2026Fast Catch-Up, Late Switching: Optimal Batch Size Scheduling via Functional Scaling Lawscited by 4
  9. 2025Learning Curves of Stochastic Gradient Descent in Kernel Regressioncited by 3
  10. 2024SGD with memory: fundamental properties and stochastic accelerationcited by 2
  11. 2026Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Sizecited by 2
  12. 2023Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regressioncited by 1
  13. 2025Understanding SGD with Exponential Moving Average: A Case Study in Linear Regressioncited by 1
  14. 2025Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δcited by 1
  15. 2026Compute Efficiency and Serial Runtime Tradeoffs for Stochastic Momentum Methodscited by 1
  16. 2022Local SGD in Overparameterized Linear Regressioncited by 0
  17. 2022Mutual Information Learned Regressor: an Information-theoretic Viewpoint of Training Regression Systemscited by 0
  18. 2024Stochastic Gradient Descent for Nonparametric Additive Regressioncited by 0
  19. 2025Learning Rate Annealing Improves Tuning Robustness in Stochastic Optimizationcited by 0
  20. 2025High-Dimensional Privacy-Utility Dynamics of Noisy Stochastic Gradient Descent on Least Squarescited by 0
  21. 2026Accelerating Single-Pass SGD for Generalized Linear Predictioncited by 0
  22. 2026Hard labels sampled from sparse targets mislead rotation invariant algorithmscited by 0
  23. 2026Near-optimal and Efficient First-Order Algorithm for Multi-Task Learning with Shared Linear Representationcited by 0
  24. 2026What Makes a Strong Model? A Unified Spectral Analysis of Knowledge Transfer over High-dimensional Linear Regressioncited by 0
  25. 2026How AI settled the complexity of the oldest SGD algorithmcited by 0