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 (2)

• How to Escape Saddle Points Efficiently
• Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary