# On the Convergence of Step Decay Step-Size for Stochastic Optimization

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 54 references that are in the map.
- First posted on arXiv 18 Feb 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems](https://mlsanity.com/paper/1603.04467/) (2016)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates](https://mlsanity.com/paper/1905.09997/) (2019)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [Beyond Convexity: Stochastic Quasi-Convex Optimization](https://mlsanity.com/paper/1507.02030/) (2015)
- [The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares](https://mlsanity.com/paper/1904.12838/) (2019)
- [The Complexity of Finding Stationary Points with Stochastic Gradient Descent](https://mlsanity.com/paper/1910.01845/) (2019)
- [On Learning Rates and Schr"odinger Operators](https://mlsanity.com/paper/2004.06977/) (2020)
- [Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent](https://mlsanity.com/paper/1909.00843/) (2019)
- [A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance](https://mlsanity.com/paper/2002.05273/) (2020)
- [Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergence](https://mlsanity.com/paper/1811.11829/) (2018)
- [Relative Deviation Learning Bounds and Generalization with Unbounded Loss Functions](https://mlsanity.com/paper/1310.5796/) (2013)
- [Stochastic algorithms with geometric step decay converge linearly on sharp functions](https://mlsanity.com/paper/1907.09547/) (2019)
- [Using Statistics to Automate Stochastic Optimization](https://mlsanity.com/paper/1909.09785/) (2019)
- [Universal Stagewise Learning for Non-Convex Problems with Convergence on Averaged Solutions](https://mlsanity.com/paper/1808.06296/) (2018)
- [Statistical Adaptive Stochastic Gradient Methods](https://mlsanity.com/paper/2002.10597/) (2020)
- [Learning with Non-Convex Truncated Losses by SGD](https://mlsanity.com/paper/1805.07880/) (2018)
- [On the Convergence of (Stochastic) Gradient Descent with Extrapolation for Non-Convex Optimization](https://mlsanity.com/paper/1901.10682/) (2019)
- [Revisiting SGD with Increasingly Weighted Averaging: Optimization and Generalization Perspectives](https://mlsanity.com/paper/2003.04339/) (2020)

## Built on by (most cited first, 21 of 21)

- [Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods](https://mlsanity.com/paper/2305.12475/) (2023)
- [ADOPT: Modified Adam Can Converge with Any β2 with the Optimal Rate](https://mlsanity.com/paper/2411.02853/) (2024)
- [On the Role of Server Momentum in Federated Learning](https://mlsanity.com/paper/2312.12670/) (2023)
- [Increasing Both Batch Size and Learning Rate Accelerates Stochastic Gradient Descent](https://mlsanity.com/paper/2409.08770/) (2024)
- [End-to-End Learning for Stochastic Optimization: A Bayesian Perspective](https://mlsanity.com/paper/2306.04174/) (2023)
- [Iteration and Stochastic First-order Oracle Complexities of Stochastic Gradient Descent using Constant and Decaying Learning Rates](https://mlsanity.com/paper/2402.15344/) (2024)
- [Provably Scalable Black-Box Variational Inference with Structured Variational Families](https://mlsanity.com/paper/2401.10989/) (2024)
- [Bandwidth-based Step-Sizes for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/2106.02888/) (2021)
- [On Uniform Boundedness Properties of SGD and its Momentum Variants](https://mlsanity.com/paper/2201.10245/) (2022)
- [Demystifying the Myths and Legends of Nonconvex Convergence of SGD](https://mlsanity.com/paper/2310.12969/) (2023)
- [Parallel Momentum Methods Under Biased Gradient Estimations](https://mlsanity.com/paper/2403.00853/) (2024)
- [On the Convergence of Federated Learning Algorithms without Data Similarity](https://mlsanity.com/paper/2403.02347/) (2024)
- [Localized Physics-informed Gaussian Processes with Curriculum Training for Topology Optimization](https://mlsanity.com/paper/2503.15561/) (2025)
- [Optimal Transceiver Design in Over-the-Air Federated Distillation](https://mlsanity.com/paper/2507.15256/) (2025)
- [A Generalized Version of Chung's Lemma and its Applications](https://mlsanity.com/paper/2406.05637/) (2024)
- [Convergence of Sharpness-Aware Minimization Algorithms using Increasing Batch Size and Decaying Learning Rate](https://mlsanity.com/paper/2409.09984/) (2024)
- [Modified Step Size for Enhanced Stochastic Gradient Descent: Convergence and Experiments](https://mlsanity.com/paper/2309.01248/) (2023)
- [New logarithmic step size for stochastic gradient descent](https://mlsanity.com/paper/2404.01257/) (2024)
- [Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descent](https://mlsanity.com/paper/2412.11341/) (2024)
- [Communication-Learning Co-Design for Differentially Private Over-the-Air Federated Distillation](https://mlsanity.com/paper/2508.06557/) (2025)
- [Explainable Learning Rate Regimes for Stochastic Optimization](https://mlsanity.com/paper/2508.13639/) (2025)

## Abstract (arXiv)

The convergence of stochastic gradient descent is highly dependent on the step-size, especially on non-convex problems such as neural network training. Step decay step-size schedules (constant and then cut) are widely used in practice because of their excellent convergence and generalization qualities, but their theoretical properties are not yet well understood. We provide the convergence results for step decay in the non-convex regime, ensuring that the gradient norm vanishes at an O(ln T/√T) rate. We also provide the convergence guarantees for general (possibly non-smooth) convex problems, ensuring an O(ln T/√T) convergence rate. Finally, in the strongly convex case, we establish an O(ln T/T) rate for smooth problems, which we also prove to be tight, and an O(ln2 T /T) rate without the smoothness assumption. We illustrate the practical efficiency of the step decay step-size in several large scale deep neural network training tasks.