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

Abstract

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 $\text{global minimum}$ to within $\epsilon$ accuracy in $O({\epsilon }^{-1}\log (1/\epsilon ))$ steps for large $\epsilon$ and $O(\log (1/\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.

Corrected Lemma 4.6(iii) and changed the title and some notation to match the journal version of the paper