Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
This provides a method for nonconvex optimization problems where second-order guarantees are crucial, representing an incremental advance over existing first-order techniques.
The paper tackles the problem of finding second-order stationary points in nonconvex optimization, showing that Stabilized SVRG achieves this with a stochastic gradient complexity of $\widetilde{O}(n^{2/3}/ε^2+n/ε^{1.5})$, which nearly matches first-order guarantees.
Variance reduction techniques like SVRG provide simple and fast algorithms for optimizing a convex finite-sum objective. For nonconvex objectives, these techniques can also find a first-order stationary point (with small gradient). However, in nonconvex optimization it is often crucial to find a second-order stationary point (with small gradient and almost PSD hessian). In this paper, we show that Stabilized SVRG (a simple variant of SVRG) can find an $ε$-second-order stationary point using only $\widetilde{O}(n^{2/3}/ε^2+n/ε^{1.5})$ stochastic gradients. To our best knowledge, this is the first second-order guarantee for a simple variant of SVRG. The running time almost matches the known guarantees for finding $ε$-first-order stationary points.