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

arXiv: https://arxiv.org/abs/2110.06198 · HTML: https://mlsanity.com/paper/2110.06198/

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 36 references that are in the map.
- First posted on arXiv 12 Oct 2021.

## Builds on (most cited first, 17 of 17)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Two models of double descent for weak features](https://mlsanity.com/paper/1903.07571/) (2019)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Benign Overfitting of Constant-Stepsize SGD for Linear Regression](https://mlsanity.com/paper/2103.12692/) (2021)
- [The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares](https://mlsanity.com/paper/1904.12838/) (2019)
- [Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression](https://mlsanity.com/paper/1602.05419/) (2016)
- [Last iterate convergence of SGD for Least-Squares in the Interpolation regime](https://mlsanity.com/paper/2102.03183/) (2021)
- [Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model](https://mlsanity.com/paper/2006.08212/) (2020)
- [The Benefits of Implicit Regularization from SGD in Least Squares Problems](https://mlsanity.com/paper/2108.04552/) (2021)
- [Iterate averaging as regularization for stochastic gradient descent](https://mlsanity.com/paper/1802.08009/) (2018)
- [A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)](https://mlsanity.com/paper/1710.09430/) (2017)
- [Beating SGD Saturation with Tail-Averaging and Minibatching](https://mlsanity.com/paper/1902.08668/) (2019)
- [A Universally Optimal Multistage Accelerated Stochastic Gradient Method](https://mlsanity.com/paper/1901.08022/) (2019)
- [Stochastic algorithms with geometric step decay converge linearly on sharp functions](https://mlsanity.com/paper/1907.09547/) (2019)
- [A Generic Acceleration Framework for Stochastic Composite Optimization](https://mlsanity.com/paper/1906.01164/) (2019)

## Built on by (most cited first, 30 of 38)

- [How Many Pretraining Tasks Are Needed for In-Context Learning of Linear Regression?](https://mlsanity.com/paper/2310.08391/) (2023)
- [Scaling Laws in Linear Regression: Compute, Parameters, and Data](https://mlsanity.com/paper/2406.08466/) (2024)
- [Understanding Forgetting in Continual Learning with Linear Regression](https://mlsanity.com/paper/2405.17583/) (2024)
- [The Power and Limitation of Pretraining-Finetuning for Linear Regression under Covariate Shift](https://mlsanity.com/paper/2208.01857/) (2022)
- [Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensions](https://mlsanity.com/paper/2206.07252/) (2022)
- [Eigencurve: Optimal Learning Rate Schedule for SGD on Quadratic Objectives with Skewed Hessian Spectrums](https://mlsanity.com/paper/2110.14109/) (2021)
- [From Continual Learning to SGD and Back: Better Rates for Continual Linear Models](https://mlsanity.com/paper/2504.04579/) (2025)
- [Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime](https://mlsanity.com/paper/2507.11274/) (2025)
- [Improved Scaling Laws in Linear Regression via Data Reuse](https://mlsanity.com/paper/2506.08415/) (2025)
- [Anytime Pretraining: Horizon-Free Learning-Rate Schedules with Weight Averaging](https://mlsanity.com/paper/2602.03702/) (2026)
- [Provable Generalization of Overparameterized Meta-learning Trained with SGD](https://mlsanity.com/paper/2206.09136/) (2022)
- [Accelerated Convergence of Stochastic Heavy Ball Method under Anisotropic Gradient Noise](https://mlsanity.com/paper/2312.14567/) (2023)
- [Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression](https://mlsanity.com/paper/2502.13283/) (2025)
- [Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime](https://mlsanity.com/paper/2203.03159/) (2022)
- [Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuron](https://mlsanity.com/paper/2303.02255/) (2023)
- [The Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimization](https://mlsanity.com/paper/2409.09745/) (2024)
- [Optimal Learning Rate Schedules under Functional Scaling Laws: Power Decay and Warmup-Stable-Decay](https://mlsanity.com/paper/2602.06797/) (2026)
- [Seesaw: Accelerating Training by Balancing Learning Rate and Batch Size Scheduling](https://mlsanity.com/paper/2510.14717/) (2025)
- [Fast Catch-Up, Late Switching: Optimal Batch Size Scheduling via Functional Scaling Laws](https://mlsanity.com/paper/2602.14208/) (2026)
- [On the Double Descent of Random Features Models Trained with SGD](https://mlsanity.com/paper/2110.06910/) (2021)
- [Learning Curves of Stochastic Gradient Descent in Kernel Regression](https://mlsanity.com/paper/2505.22048/) (2025)
- [SGD with memory: fundamental properties and stochastic acceleration](https://mlsanity.com/paper/2410.04228/) (2024)
- [Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size](https://mlsanity.com/paper/2604.09909/) (2026)
- [Compute Efficiency and Serial Runtime Tradeoffs for Stochastic Momentum Methods](https://mlsanity.com/paper/2606.19179/) (2026)
- [Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regression](https://mlsanity.com/paper/2302.09727/) (2023)
- [Understanding SGD with Exponential Moving Average: A Case Study in Linear Regression](https://mlsanity.com/paper/2502.14123/) (2025)
- [Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δ](https://mlsanity.com/paper/2510.19734/) (2025)
- [Hard labels sampled from sparse targets mislead rotation invariant algorithms](https://mlsanity.com/paper/2603.20967/) (2026)
- [Local SGD in Overparameterized Linear Regression](https://mlsanity.com/paper/2210.11562/) (2022)
- [Mutual Information Learned Regressor: an Information-theoretic Viewpoint of Training Regression Systems](https://mlsanity.com/paper/2211.12685/) (2022)

## 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.