Gradient Descent Finds the Cubic-Regularized Non-Convex Newton Step

We consider the minimization of non-convex quadratic forms regularized by a cubic term, which exhibit multiple saddle points and poor local minima. Nonetheless, we prove that, under mild assumptions, gradient descent approximates the $\mathit{\text{global}}\mathit{\text{minimum}}$ to within $\epsilon$ accuracy in $O({\epsilon }^{-1}\log (1\mathrm{/}\epsilon ))$ steps for large $\epsilon$ and $O(\log (1\mathrm{/}\epsilon ))$ steps for small $\epsilon$ (compared to a condition number we define), with at most logarithmic dependence on the problem dimension. When we use gradient descent to approximate the cubic-regularized Newton step, our result implies a rate of convergence to second-order stationary points of general smooth non-convex functions.