Faster Perturbed Stochastic Gradient Methods for Finding Local Minima
This work addresses a central challenge in nonconvex optimization for machine learning practitioners, offering incremental improvements in computational efficiency for finding local minima.
The paper tackles the problem of escaping saddle points and finding local minima in nonconvex optimization by proposing LENA, a perturbed stochastic gradient framework, which reduces the stochastic gradient complexity to $ ilde O(ε^{-3} + ε_{H}^{-6})$ for finding $(ε, ε_{H})$-approximate local minima, improving upon the previous best of $ ilde O(ε^{-3.5})$.
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 $(ε, \sqrtε)$-approximate local minima, the existing best stochastic gradient complexity for this type of algorithms is $\tilde O(ε^{-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 $(ε, ε_{H})$-approximate local minima within $\tilde O(ε^{-3} + ε_{H}^{-6})$ stochastic gradient evaluations (or $\tilde O(ε^{-3})$ when $ε_H = \sqrtε$). 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.