SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points
This provides a simpler and more efficient method for training nonconvex models like deep neural networks by avoiding unstable saddle points, though it is incremental relative to prior work.
The paper tackles the problem of escaping saddle points in nonconvex optimization by proposing SSRGD, a simple perturbed stochastic recursive gradient descent algorithm that finds second-order stationary points with near-optimal stochastic gradient complexity, such as Õ(√n/ε² + √n/δ⁴ + n/δ³) for finite-sum problems.
We analyze stochastic gradient algorithms for optimizing nonconvex problems. In particular, our goal is to find local minima (second-order stationary points) instead of just finding first-order stationary points which may be some bad unstable saddle points. We show that a simple perturbed version of stochastic recursive gradient descent algorithm (called SSRGD) can find an $(ε,δ)$-second-order stationary point with $\widetilde{O}(\sqrt{n}/ε^2 + \sqrt{n}/δ^4 + n/δ^3)$ stochastic gradient complexity for nonconvex finite-sum problems. As a by-product, SSRGD finds an $ε$-first-order stationary point with $O(n+\sqrt{n}/ε^2)$ stochastic gradients. These results are almost optimal since Fang et al. [2018] provided a lower bound $Ω(\sqrt{n}/ε^2)$ for finding even just an $ε$-first-order stationary point. We emphasize that SSRGD algorithm for finding second-order stationary points is as simple as for finding first-order stationary points just by adding a uniform perturbation sometimes, while all other algorithms for finding second-order stationary points with similar gradient complexity need to combine with a negative-curvature search subroutine (e.g., Neon2 [Allen-Zhu and Li, 2018]). Moreover, the simple SSRGD algorithm gets a simpler analysis. Besides, we also extend our results from nonconvex finite-sum problems to nonconvex online (expectation) problems, and prove the corresponding convergence results.