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
$(\epsilon,\delta)$-second-order stationary point with
$\widetilde{O}(\sqrt{n}/\epsilon^2 + \sqrt{n}/\delta^4 + n/\delta^3)$
stochastic gradient complexity for nonconvex finite-sum problems. As a
by-product, SSRGD finds an $\epsilon$-first-order stationary point with
$O(n+\sqrt{n}/\epsilon^2)$ stochastic gradients. These results are almost
optimal since Fang et al. [2018] provided a lower bound
$\Omega(\sqrt{n}/\epsilon^2)$ for finding even just an $\epsilon$-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.

我们分析了用于优化非凸问题的随机梯度算法及其中简单的 SSROD 算法，在此基础上证明了 SSROD 算法可以有效地寻找非凸问题中的局部最小值点，并给出了相关的复杂度分析。