Stochastic Gradient Descent Escapes Saddle Points Efficiently

Abstract

This paper considers the perturbed stochastic gradient descent algorithm and shows that it finds \(\epsilon\)-second order stationary points (\(\left\|\nabla f(x)\right\|\leq \epsilon\) and \(\nabla^2 f(x) \succeq -\sqrt{\epsilon} \mathbf{I}\)) in \(\tilde{O}(d/\epsilon^4)\) iterations, giving the first result that has linear dependence on dimension for this setting. For the special case, where stochastic gradients are Lipschitz, the dependence on dimension reduces to polylogarithmic. In addition to giving new results, this paper also presents a simplified proof strategy that gives a shorter and more elegant proof of previously known results (Jin et al. 2017) on perturbed gradient descent algorithm.