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 log(1/ ε) ), the method finds an ε-stationary point, meaning a point x such that \|∇ f(x)\| ≤ ε. The method improves upon the O(ε⁻² ) 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.