Accelerated Methods for Non-Convex Optimization

Abstract

We present an accelerated gradient method for non-convex optimization problems with Lipschitz continuous first and second derivatives. The method requires time $O({\epsilon }^{-7/4}\log (1/\epsilon ))$ to find an $\epsilon$-stationary point, meaning a point $x$ such that $\Vert \nabla f(x)\Vert \le \epsilon$. The method improves upon the $O({\epsilon }^{-2})$ complexity of gradient descent and provides the additional second-order guarantee that ${\nabla }^{2}f(x)⪰-O({\epsilon }^{1/2})I$ for the computed $x$. Furthermore, our method is Hessian free, i.e. it only requires gradient computations, and is therefore suitable for large scale applications.

References in corpus (2)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization

Cited by in corpus (9)

• How to Escape Saddle Points Efficiently
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Stochastic Cubic Regularization for Fast Nonconvex Optimization
• On Noisy Negative Curvature Descent: Competing with Gradient Descent for Faster Non-convex Optimization
• Variance Reduced methods for Non-convex Composition Optimization
• Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima
• Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary