mlsanityData to 14 Oct 2026

Bandwidth-based Step-Sizes for Non-Convex Stochastic Optimization

arXiv 2106.02888 ↗First posted 5 Jun 2021cs.LG math.OCcited by 2

Not on the map. Why?

Abstract (arXiv)

Many popular learning-rate schedules for deep neural networks combine a decaying trend with local perturbations that attempt to escape saddle points and bad local minima. We derive convergence guarantees for bandwidth-based step-sizes, a general class of learning rates that are allowed to vary in a banded region. This framework includes many popular cyclic and non-monotonic step-sizes for which no theoretical guarantees were previously known. We provide worst-case guarantees for SGD on smooth non-convex problems under several bandwidth-based step sizes, including stagewise 1/√t and the popular step-decay (constant and then drop by a constant), which is also shown to be optimal. Moreover, we show that its momentum variant converges as fast as SGD with the bandwidth-based step-decay step-size. Finally, we propose novel step-size schemes in the bandwidth-based family and verify their efficiency on several deep neural network training tasks.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 34 of its 55 references that are in the map. First posted on arXiv 5 Jun 2021.

Builds on

34 of 55 references.

References · 34

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  3. 2016Densely Connected Convolutional Networkscited by 6,720
  4. 2016SGDR: Stochastic Gradient Descent with Warm Restartscited by 5,045
  5. 2016Wide Residual Networkscited by 3,070
  6. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  7. 2015Cyclical Learning Rates for Training Neural Networkscited by 629
  8. 2019SGD: General Analysis and Improved Ratescited by 207
  9. 2020An Improved Analysis of Stochastic Gradient Descent with Momentumcited by 119
  10. 2015Beyond Convexity: Stochastic Quasi-Convex Optimizationcited by 76
  11. 2013Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programmingcited by 75
  12. 2019The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squarescited by 68
22 more
  1. 2014Global convergence of the Heavy-ball method for convex optimizationcited by 61
  2. 2018A Unified Analysis of Stochastic Momentum Methods for Deep Learningcited by 55
  3. 2013Loss minimization and parameter estimation with heavy tailscited by 50
  4. 2019Understanding the Role of Momentum in Stochastic Gradient Methodscited by 44
  5. 2016Stochastic Heavy Ballcited by 42
  6. 2014Empirical risk minimization for heavy-tailed lossescited by 37
  7. 2019The Complexity of Finding Stationary Points with Stochastic Gradient Descentcited by 35
  8. 2020On Learning Rates and Schr"odinger Operatorscited by 33
  9. 2020Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimizationcited by 32
  10. 2020A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performancecited by 26
  11. 2015Robust Optimization for Deep Regressioncited by 22
  12. 2021On the Convergence of Step Decay Step-Size for Stochastic Optimizationcited by 21
  13. 2018Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergencecited by 16
  14. 2013Relative Deviation Learning Bounds and Generalization with Unbounded Loss Functionscited by 15
  15. 2019Stochastic algorithms with geometric step decay converge linearly on sharp functionscited by 14
  16. 2019Using Statistics to Automate Stochastic Optimizationcited by 12
  17. 2017A Stochastic Trust Region Algorithm Based on Careful Step Normalizationcited by 10
  18. 2018Universal Stagewise Learning for Non-Convex Problems with Convergence on Averaged Solutionscited by 9
  19. 2021On the Convergence of Stochastic Gradient Descent with Bandwidth-based Step Sizecited by 9
  20. 2020Statistical Adaptive Stochastic Gradient Methodscited by 8
  21. 2018Learning with Non-Convex Truncated Losses by SGDcited by 7
  22. 2019On the Convergence of (Stochastic) Gradient Descent with Extrapolation for Non-Convex Optimizationcited by 6

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 1.

2 papers.

  1. 2023Accelerated Convergence of Stochastic Heavy Ball Method under Anisotropic Gradient Noisecited by 9
  2. 2022On Uniform Boundedness Properties of SGD and its Momentum Variantscited by 2