Sharp Analysis for Nonconvex SGD Escaping from Saddle Points

Abstract

In this paper, we give a sharp analysis for Stochastic Gradient Descent (SGD) and prove that SGD is able to efficiently escape from saddle points and find an $(\epsilon ,O({\epsilon }^{0.5}))$-approximate second-order stationary point in $\tilde{O}({\epsilon }^{-3.5})$ stochastic gradient computations for generic nonconvex optimization problems, when the objective function satisfies gradient-Lipschitz, Hessian-Lipschitz, and dispersive noise assumptions. This result subverts the classical belief that SGD requires at least $O({\epsilon }^{-4})$ stochastic gradient computations for obtaining an $(\epsilon ,O({\epsilon }^{0.5}))$-approximate second-order stationary point. Such SGD rate matches, up to a polylogarithmic factor of problem-dependent parameters, the rate of most accelerated nonconvex stochastic optimization algorithms that adopt additional techniques, such as Nesterov's momentum acceleration, negative curvature search, as well as quadratic and cubic regularization tricks. Our novel analysis gives new insights into nonconvex SGD and can be potentially generalized to a broad class of stochastic optimization algorithms.

References in corpus (11)

• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Guaranteed Matrix Completion via Non-convex Factorization
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Neon2: Finding Local Minima via First-Order Oracles
• Near-Optimal Stochastic Approximation for Online Principal Component Estimation
• How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
• On the Local Minima of the Empirical Risk
• A Generic Approach for Escaping Saddle points
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Finding Local Minima via Stochastic Nested Variance Reduction
• A Stochastic Trust Region Method for Non-convex Minimization

Cited by in corpus (22)

• Better Theory for SGD in the Nonconvex World
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Mathematical Models of Overparameterized Neural Networks
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks
• Stochastic Conditional Gradient++
• The Complexity of Finding Stationary Points with Stochastic Gradient Descent
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics
• Distributed Deep Learning with Event-Triggered Communication
• Global Convergence and Stability of Stochastic Gradient Descent
• Escaping Saddle Points Faster with Stochastic Momentum
• Recht-Ré Noncommutative Arithmetic-Geometric Mean Conjecture is False
• On the Convergence of SARAH and Beyond
• Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms
• Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent
• Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization
• Stochastic Approximation for Online Tensorial Independent Component Analysis
• Momentum Improves Normalized SGD
• Second-Order Convergence of Asynchronous Parallel Stochastic Gradient Descent: When Is the Linear Speedup Achieved?
• Characterization of Excess Risk for Locally Strongly Convex Population Risk