Accelerated Methods for NonConvex Optimization
提出一种无需计算海森矩阵的加速梯度方法，能在O(ε^{-7/4} log(1/ε))时间内找到非凸问题的ε-平稳点，并保证海森矩阵的最小特征值不低于-ε^{1/2}，适用于大规模应用。
We present an accelerated gradient method for nonconvex optimization problems with Lipschitz continuous first and second derivatives. In a time $O(\epsilon^{-7/4} \log(1/ \epsilon) )$, the method finds 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 $\lambda_{\min}(\nabla^2 f(x)) \gtrsim -\epsilon^{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.