Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization

Understand

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 $\epsilon$-second-order stationary point using only $\widetilde{O}(n^{2/3}/\epsilon^2+n/\epsilon^{1.5})$ stochastic gradients.