The Complexity of Finding Stationary Points with Stochastic Gradient Descent

Abstract

We study the iteration complexity of stochastic gradient descent (SGD) for minimizing the gradient norm of smooth, possibly nonconvex functions. We provide several results, implying that the $\mathcal{O}({\epsilon }^{-4})$ upper bound of Ghadimi and Lan~\cite{ghadimi2013stochastic} (for making the average gradient norm less than $\epsilon$) cannot be improved upon, unless a combination of additional assumptions is made. Notably, this holds even if we limit ourselves to convex quadratic functions. We also show that for nonconvex functions, the feasibility of minimizing gradients with SGD is surprisingly sensitive to the choice of optimality criteria.

arXiv commentCorrected the attribution of Ghadimi and Lan's result

References in corpus (6)

• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
• How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• The Complexity of Making the Gradient Small in Stochastic Convex Optimization
• On the Gap Between Strict-Saddles and True Convexity: An Omega(log d) Lower Bound for Eigenvector Approximation

Cited by in corpus (8)

• Better Theory for SGD in the Nonconvex World
• Random Reshuffling: Simple Analysis with Vast Improvements
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions
• Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning
• Adaptive Gradient Descent for Convex and Non-Convex Stochastic Optimization
• Improved Analysis of Clipping Algorithms for Non-convex Optimization
• Learning Halfspaces with Massart Noise Under Structured Distributions
• Random Reshuffling with Variance Reduction: New Analysis and Better Rates