# The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares

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

## Key facts

- Cited by 68 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Apr 2019.

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

- [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)
- [Optimal Linear Decay Learning Rate Schedules and Further Refinements](https://mlsanity.com/paper/2310.07831/) (2023)
- [Last iterate convergence of SGD for Least-Squares in the Interpolation regime](https://mlsanity.com/paper/2102.03183/) (2021)
- [Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression](https://mlsanity.com/paper/2110.06198/) (2021)
- [Straight to Zero: Why Linearly Decaying the Learning Rate to Zero Works Best for LLMs](https://mlsanity.com/paper/2502.15938/) (2025)
- [Overcoming Catastrophic Forgetting in Massively Multilingual Continual Learning](https://mlsanity.com/paper/2305.16252/) (2023)
- [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)
- [AdaGrad under Anisotropic Smoothness](https://mlsanity.com/paper/2406.15244/) (2024)
- [On the Convergence of Step Decay Step-Size for Stochastic Optimization](https://mlsanity.com/paper/2102.09393/) (2021)
- [A Biased Graph Neural Network Sampler with Near-Optimal Regret](https://mlsanity.com/paper/2103.01089/) (2021)
- [On the Role of Server Momentum in Federated Learning](https://mlsanity.com/paper/2312.12670/) (2023)
- [Eigencurve: Optimal Learning Rate Schedule for SGD on Quadratic Objectives with Skewed Hessian Spectrums](https://mlsanity.com/paper/2110.14109/) (2021)
- [Acceleration via Fractal Learning Rate Schedules](https://mlsanity.com/paper/2103.01338/) (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)
- [Training Dynamics of the Cooldown Stage in Warmup-Stable-Decay Learning Rate Scheduler](https://mlsanity.com/paper/2508.01483/) (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)
- [An Automatic Learning Rate Schedule Algorithm for Achieving Faster Convergence and Steeper Descent](https://mlsanity.com/paper/2310.11291/) (2023)
- [Accelerated Convergence of Stochastic Heavy Ball Method under Anisotropic Gradient Noise](https://mlsanity.com/paper/2312.14567/) (2023)
- [From Spikes to Heavy Tails: Unveiling the Spectral Evolution of Neural Networks](https://mlsanity.com/paper/2406.04657/) (2024)
- [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)
- [Learning Rate Schedules in the Presence of Distribution Shift](https://mlsanity.com/paper/2303.15634/) (2023)
- [Unbiased Gradient Low-Rank Projection](https://mlsanity.com/paper/2510.17802/) (2025)
- [Adaptive Differentially Private Empirical Risk Minimization](https://mlsanity.com/paper/2110.07435/) (2021)

## Abstract (arXiv)

Minimax optimal convergence rates for classes of stochastic convex optimization problems are well characterized, where the majority of results utilize iterate averaged stochastic gradient descent (SGD) with polynomially decaying step sizes. In contrast, SGD's final iterate behavior has received much less attention despite their widespread use in practice. Motivated by this observation, this work provides a detailed study of the following question: what rate is achievable using the final iterate of SGD for the streaming least squares regression problem with and without strong convexity? First, this work shows that even if the time horizon T (i.e. the number of iterations SGD is run for) is known in advance, SGD's final iterate behavior with any polynomially decaying learning rate scheme is highly sub-optimal compared to the minimax rate (by a condition number factor in the strongly convex case and a factor of √T in the non-strongly convex case). In contrast, this paper shows that Step Decay schedules, which cut the learning rate by a constant factor every constant number of epochs (i.e., the learning rate decays geometrically) offers significant improvements over any polynomially decaying step sizes. In particular, the final iterate behavior with a step decay schedule is off the minimax rate by only log factors (in the condition number for strongly convex case, and in T for the non-strongly convex case). Finally, in stark contrast to the known horizon case, this paper shows that the anytime (i.e. the limiting) behavior of SGD's final iterate is poor (in that it queries iterates with highly sub-optimal function value infinitely often, i.e. in a limsup sense) irrespective of the stepsizes employed. These results demonstrate the subtlety in establishing optimal learning rate schemes (for the final iterate) for stochastic gradient procedures in fixed time horizon settings.