Accelerated Methods for Non-Convex Optimization
  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 $\|\nabla f(x)\| \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) \succeq -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. 
Yair Carmon, John C. Duchi, Oliver Hinder and Aaron Sidford
math.OC cs.DS