Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization

Abstract

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.

References in corpus (9)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• How to Escape Saddle Points Efficiently
• Learning One-hidden-layer Neural Networks with Landscape Design
• A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization
• Gradient Descent Can Take Exponential Time to Escape Saddle Points
• Accelerated Methods for Non-Convex Optimization
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Finding Local Minima via Stochastic Nested Variance Reduction

Cited by in corpus (10)

• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
• Tracking Performance of Online Stochastic Learners
• Stochastic Gradient Hamiltonian Monte Carlo with Variance Reduction for Bayesian Inference
• Variance Reduction on General Adaptive Stochastic Mirror Descent
• A Fast Anderson-Chebyshev Acceleration for Nonlinear Optimization
• Distributed Policy Gradient with Variance Reduction in Multi-Agent Reinforcement Learning