Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization

• Main Authors: GE, Rong, LI, Zhize, WANG, Weiyao, WANG, Xiang
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2019
• Subjects: Databases and Information Systems
• Online Access: https://ink.library.smu.edu.sg/sis_research/8677; https://ink.library.smu.edu.sg/context/sis_research/article/9680/viewcontent/COLT19_stabilizedsvrg.pdf
• Institution: Singapore Management University

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 $\tilde{O}(n^{2/3}/\epsilon^2 + n/\epsilon^{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 $\epsilon$-first-order stationary points.