Demystifying the Myths and Legends of Nonconvex Convergence of SGD
Not on the map. Why?
Abstract (arXiv)
Stochastic gradient descent (SGD) and its variants are the main workhorses for solving large-scale optimization problems with nonconvex objective functions. Although the convergence of SGDs in the (strongly) convex case is well-understood, their convergence for nonconvex functions stands on weak mathematical foundations. Most existing studies on the nonconvex convergence of SGD show the complexity results based on either the minimum of the expected gradient norm or the functional sub-optimality gap (for functions with extra structural property) by searching the entire range of iterates. Hence the last iterations of SGDs do not necessarily maintain the same complexity guarantee. This paper shows that an ε-stationary point exists in the final iterates of SGDs, given a large enough total iteration budget, T, not just anywhere in the entire range of iterates -- a much stronger result than the existing one. Additionally, our analyses allow us to measure the density of the ε-stationary points in the final iterates of SGD, and we recover the classical O(frac1√T) asymptotic rate under various existing assumptions on the objective function and the bounds on the stochastic gradient. As a result of our analyses, we addressed certain myths and legends related to the nonconvex convergence of SGD and posed some thought-provoking questions that could set new directions for research.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 44 of its 64 references that are in the map. First posted on arXiv 19 Oct 2023.
Builds on
44 of 64 references.
References · 44
- 2015Deep Residual Learning for Image Recognitioncited by 51,809
- 2019Advances and Open Problems in Federated Learningcited by 3,021
- 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
- 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
- 2019On the Convergence of Adam and Beyondcited by 834
- 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
- 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
- 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
- 2018Sparsified SGD with Memorycited by 373
- 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
- 2019SGD: General Analysis and Improved Ratescited by 206
- 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
32 more
- 2020A Simple Convergence Proof of Adam and Adagradcited by 169
- 2020Better Theory for SGD in the Nonconvex Worldcited by 156
- 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
- 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 142
- 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
- 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 132
- 2017Lower Bounds for Finding Stationary Points Icited by 125
- 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
- 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 112
- 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 94
- 2018On the Convergence of Adaptive Gradient Methods for Nonconvex Optimizationcited by 91
- 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
- 2015Why Random Reshuffling Beats Stochastic Gradient Descentcited by 78
- 2019Convergence rates for the stochastic gradient descent method for non-convex objective functionscited by 66
- 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 66
- 2020A Unified Convergence Analysis for Shuffling-Type Gradient Methodscited by 57
- 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
- 2019Stochastic Gradient Descent for Nonconvex Learning without Bounded Gradient Assumptionscited by 48
- 2020An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Biascited by 45
- 2021Rethinking gradient sparsification as total error minimizationcited by 41
- 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
- 2016Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimizationcited by 34
- 2018A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimizationcited by 33
- 2019On the Discrepancy between the Theoretical Analysis and Practical Implementations of Compressed Communication for Distributed Deep Learningcited by 31
- 2014Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problemscited by 25
- 2019Simple and optimal high-probability bounds for strongly-convex stochastic gradient descentcited by 25
- 2021On the Convergence of Step Decay Step-Size for Stochastic Optimizationcited by 21
- 2023A Stochastic Proximal Polyak Step Sizecited by 15
- 2019Non-asymptotic Analysis of Stochastic Methods for Non-Smooth Non-Convex Regularized Problemscited by 14
- 2023Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learningcited by 10
- 2017Stochastic Nonconvex Optimization with Large Minibatchescited by 7
- 2022On the Convergence of mSGD and AdaGrad for Stochastic Optimizationcited by 7
Built on by
Citing papers per year: 2025: 1; 2026: 1.
2 papers.