Accelerated Methods for NonConvex Optimization

We present an accelerated gradient method for nonconvex optimization problems with Lipschitz continuous first and second derivatives. In a time O (^-7/4 (1/) ), the method finds an -stationary point, meaning a point x such that \| f (x) \|. The method improves upon the O (^-2) complexity of gradient descent and provides the additional second-order guarantee that _ (² f (x) ) -^1/2 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.