Faster Perturbed Stochastic Gradient Methods for Finding Local Minima
  Escaping from saddle points and finding local minimum is a central problem in
nonconvex optimization. Perturbed gradient methods are perhaps the simplest
approach for this problem. However, to find $(\epsilon,
\sqrt{\epsilon})$-approximate local minima, the existing best stochastic
gradient complexity for this type of algorithms is $\tilde O(\epsilon^{-3.5})$,
which is not optimal. In this paper, we propose LENA (Last stEp shriNkAge), a
faster perturbed stochastic gradient framework for finding local minima. We
show that LENA with stochastic gradient estimators such as SARAH/SPIDER and
STORM can find $(\epsilon, \epsilon_{H})$-approximate local minima within
$\tilde O(\epsilon^{-3} + \epsilon_{H}^{-6})$ stochastic gradient evaluations
(or $\tilde O(\epsilon^{-3})$ when $\epsilon_H = \sqrt{\epsilon}$). The core
idea of our framework is a step-size shrinkage scheme to control the average
movement of the iterates, which leads to faster convergence to the local
minima.
