mlsanityData to 7 Oct 2026

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

arXiv 2102.09393 ↗First posted 18 Feb 2021math.OC cs.LG stat.MLcited by 21

Not on the map. Why?

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.

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

Builds on

25 of 54 references.

References · 25

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  3. 2016Densely Connected Convolutional Networkscited by 6,691
  4. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  5. 2016TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systemscited by 660
  6. 2019SGD: General Analysis and Improved Ratescited by 206
  7. 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 142
  8. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  9. 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
  10. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 94
  11. 2015Beyond Convexity: Stochastic Quasi-Convex Optimizationcited by 75
  12. 2019The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squarescited by 67
13 more
  1. 2019The Complexity of Finding Stationary Points with Stochastic Gradient Descentcited by 34
  2. 2020On Learning Rates and Schr"odinger Operatorscited by 33
  3. 2020A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performancecited by 26
  4. 2019Simple and optimal high-probability bounds for strongly-convex stochastic gradient descentcited by 25
  5. 2018Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergencecited by 16
  6. 2013Relative Deviation Learning Bounds and Generalization with Unbounded Loss Functionscited by 15
  7. 2019Stochastic algorithms with geometric step decay converge linearly on sharp functionscited by 14
  8. 2019Using Statistics to Automate Stochastic Optimizationcited by 12
  9. 2018Universal Stagewise Learning for Non-Convex Problems with Convergence on Averaged Solutionscited by 9
  10. 2020Statistical Adaptive Stochastic Gradient Methodscited by 8
  11. 2018Learning with Non-Convex Truncated Losses by SGDcited by 7
  12. 2019On the Convergence of (Stochastic) Gradient Descent with Extrapolation for Non-Convex Optimizationcited by 6
  13. 2020Revisiting SGD with Increasingly Weighted Averaging: Optimization and Generalization Perspectivescited by 3

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 1; 2023: 5; 2024: 10; 2025: 4.

21 papers.

Sort:

  1. 2023Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methodscited by 23
  2. 2024ADOPT: Modified Adam Can Converge with Any β2 with the Optimal Ratecited by 18
  3. 2023On the Role of Server Momentum in Federated Learningcited by 16
  4. 2024Increasing Both Batch Size and Learning Rate Accelerates Stochastic Gradient Descentcited by 11
  5. 2023End-to-End Learning for Stochastic Optimization: A Bayesian Perspectivecited by 6
  6. 2024Iteration and Stochastic First-order Oracle Complexities of Stochastic Gradient Descent using Constant and Decaying Learning Ratescited by 5
  7. 2024Provably Scalable Black-Box Variational Inference with Structured Variational Familiescited by 4
  8. 2021Bandwidth-based Step-Sizes for Non-Convex Stochastic Optimizationcited by 2
  9. 2022On Uniform Boundedness Properties of SGD and its Momentum Variantscited by 2
  10. 2023Demystifying the Myths and Legends of Nonconvex Convergence of SGDcited by 2
  11. 2024Parallel Momentum Methods Under Biased Gradient Estimationscited by 2
  12. 2024On the Convergence of Federated Learning Algorithms without Data Similaritycited by 2
9 more
  1. 2025Localized Physics-informed Gaussian Processes with Curriculum Training for Topology Optimizationcited by 2
  2. 2025Optimal Transceiver Design in Over-the-Air Federated Distillationcited by 2
  3. 2024A Generalized Version of Chung's Lemma and its Applicationscited by 1
  4. 2024Convergence of Sharpness-Aware Minimization Algorithms using Increasing Batch Size and Decaying Learning Ratecited by 1
  5. 2023Modified Step Size for Enhanced Stochastic Gradient Descent: Convergence and Experimentscited by 0
  6. 2024New logarithmic step size for stochastic gradient descentcited by 0
  7. 2024Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descentcited by 0
  8. 2025Communication-Learning Co-Design for Differentially Private Over-the-Air Federated Distillationcited by 0
  9. 2025Explainable Learning Rate Regimes for Stochastic Optimizationcited by 0