Stochastic Nested Variance Reduction for Nonconvex Optimization

Abstract

We study finite-sum nonconvex optimization problems, where the objective function is an average of $n$ nonconvex functions. We propose a new stochastic gradient descent algorithm based on nested variance reduction. Compared with conventional stochastic variance reduced gradient (SVRG) algorithm that uses two reference points to construct a semi-stochastic gradient with diminishing variance in each iteration, our algorithm uses $K+1$ nested reference points to build a semi-stochastic gradient to further reduce its variance in each iteration. For smooth nonconvex functions, the proposed algorithm converges to an $\epsilon$-approximate first-order stationary point (i.e., $\Vert \nabla F(\mathbf{x}){\Vert }_2\le \epsilon$) within $\tilde{O}(n\wedge {\epsilon }^{-2}+{\epsilon }^{-3}\wedge n^{1/2}{\epsilon }^{-2})$ number of stochastic gradient evaluations. This improves the best known gradient complexity of SVRG $O(n+n^{2/3}{\epsilon }^{-2})$ and that of SCSG $O(n\wedge {\epsilon }^{-2}+{\epsilon }^{-10/3}\wedge n^{2/3}{\epsilon }^{-2})$. For gradient dominated functions, our algorithm also achieves better gradient complexity than the state-of-the-art algorithms. Thorough experimental results on different nonconvex optimization problems back up our theory.

26 pages, 4 figures, 4 tables. In NeurIPS 2018

Cited by in corpus (28)

• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Why gradient clipping accelerates training: A theoretical justification for adaptivity
• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
• A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization
• Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization
• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions
• Finding Local Minima via Stochastic Nested Variance Reduction
• Adam${}^{+}$: A Stochastic Method with Adaptive Variance Reduction
• Efficient Privacy-Preserving Stochastic Nonconvex Optimization
• ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning
• ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
• A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learning
• A Stochastic Extra-Step Quasi-Newton Method for Nonsmooth Nonconvex Optimization
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations
• On the Convergence of SARAH and Beyond
• Variance Reduction with Sparse Gradients
• Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent
• Faster Stochastic Quasi-Newton Methods
• A Fast Anderson-Chebyshev Acceleration for Nonlinear Optimization
• Understanding the Role of Adversarial Regularization in Supervised Learning
• SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points
• Tight Lower Complexity Bounds for Strongly Convex Finite-Sum Optimization