Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
[edit]
Proceedings of the ThirtySecond Conference on Learning Theory, PMLR 99:13941448, 2019.
Abstract
Variance reduction techniques like SVRG provide simple and fast algorithms for optimizing a convex finitesum objective. For nonconvex objectives, these techniques can also find a firstorder stationary point (with small gradient). However, in nonconvex optimization it is often crucial to find a secondorder 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 $\epsilon$secondorder stationary point using only $\widetilde{O}(n^{2/3}/\epsilon^2+n/\epsilon^{1.5})$ stochastic gradients. To our best knowledge, this is the first secondorder guarantee for a simple variant of SVRG. The running time almost matches the known guarantees for finding $\epsilon$firstorder stationary points.
Related Material


