Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima

Abstract

We propose stochastic optimization algorithms that can find local minima faster than existing algorithms for nonconvex optimization problems, by exploiting the third-order smoothness to escape non-degenerate saddle points more efficiently. More specifically, the proposed algorithm only needs $\tilde{O}({\epsilon }^{-10/3})$ stochastic gradient evaluations to converge to an approximate local minimum $\mathbf{x}$, which satisfies $\Vert \nabla f(\mathbf{x}){\Vert }_2\le \epsilon$ and ${\lambda }_{\min }({\nabla }^{2}f(\mathbf{x}))\ge -\sqrt{\epsilon }$ in the general stochastic optimization setting, where $\tilde{O}(\cdot )$ hides logarithm polynomial terms and constants. This improves upon the $\tilde{O}({\epsilon }^{-7/2})$ gradient complexity achieved by the state-of-the-art stochastic local minima finding algorithms by a factor of $\tilde{O}({\epsilon }^{-1/6})$. For nonconvex finite-sum optimization, our algorithm also outperforms the best known algorithms in a certain regime.

25 pages

References in corpus (16)

• The Loss Surfaces of Multilayer Networks
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• How to Escape Saddle Points Efficiently
• Stochastic Variance Reduction for Nonconvex Optimization
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Variance Reduction for Faster Non-Convex Optimization
• Efficient approaches for escaping higher order saddle points in non-convex optimization
• The Power of Normalization: Faster Evasion of Saddle Points
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Accelerated Methods for Non-Convex Optimization
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Stochastic Cubic Regularization for Fast Nonconvex Optimization
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
• Faster Eigenvector Computation via Shift-and-Invert Preconditioning
• First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently

Cited by in corpus (2)

• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Finding Local Minima via Stochastic Nested Variance Reduction