Stochastic Variance Reduction for Nonconvex Optimization

Abstract

We study nonconvex finite-sum problems and analyze stochastic variance reduced gradient (SVRG) methods for them. SVRG and related methods have recently surged into prominence for convex optimization given their edge over stochastic gradient descent (SGD); but their theoretical analysis almost exclusively assumes convexity. In contrast, we prove non-asymptotic rates of convergence (to stationary points) of SVRG for nonconvex optimization, and show that it is provably faster than SGD and gradient descent. We also analyze a subclass of nonconvex problems on which SVRG attains linear convergence to the global optimum. We extend our analysis to mini-batch variants of SVRG, showing (theoretical) linear speedup due to mini-batching in parallel settings.

Minor feedback changes

References in corpus (10)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Optimal Distributed Online Prediction using Mini-Batches
• Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• Beyond Convexity: Stochastic Quasi-Convex Optimization
• An optimal randomized incremental gradient method
• SDCA without Duality
• A Stochastic PCA and SVD Algorithm with an Exponential Convergence Rate
• A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach

Cited by in corpus (87)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• A Decentralized Federated Learning Framework via Committee Mechanism with Convergence Guarantee
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Adaptive Federated Optimization
• Variance Reduction for Faster Non-Convex Optimization
• Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization
• Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks
• SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient
• Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
• Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport
• High-Accuracy Low-Precision Training
• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Accelerated Methods for Non-Convex Optimization
• Improved asynchronous parallel optimization analysis for stochastic incremental methods
• Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
• Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• Stochastic, Distributed and Federated Optimization for Machine Learning
• SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
• Towards Riemannian Accelerated Gradient Methods
• On the Adaptivity of Stochastic Gradient-Based Optimization
• R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
• Characterization of Gradient Dominance and Regularity Conditions for Neural Networks
• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• Asynchronous Stochastic Gradient Descent with Variance Reduction for Non-Convex Optimization
• Differentially Private Empirical Risk Minimization Revisited: Faster and More General
• Fast Stochastic Variance Reduced Gradient Method with Momentum Acceleration for Machine Learning
• Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
• Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method
• Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization
• Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization
• Global Convergence of Arbitrary-Block Gradient Methods for Generalized Polyak-Łojasiewicz Functions
• Convergence Rate Analysis of a Stochastic Trust Region Method via Submartingales
• Vector Transport-Free SVRG with General Retraction for Riemannian Optimization: Complexity Analysis and Practical Implementation
• Stochastic Zeroth-order Optimization via Variance Reduction method
• Inertial Stochastic PALM (iSPALM) and Applications in Machine Learning
• Variance Reduced methods for Non-convex Composition Optimization
• Finding Local Minima via Stochastic Nested Variance Reduction
• Stochastic Alternating Direction Method of Multipliers with Variance Reduction for Nonconvex Optimization
• Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradient
• Stochastically Controlled Stochastic Gradient for the Convex and Non-convex Composition problem
• Stochastic Second-order Methods for Non-convex Optimization with Inexact Hessian and Gradient
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• A Convergence Analysis for A Class of Practical Variance-Reduction Stochastic Gradient MCMC
• A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints
• Almost Tune-Free Variance Reduction
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity
• An Analysis of Stochastic Variance Reduced Gradient for Linear Inverse Problems
• Random Shuffling Beats SGD after Finite Epochs
• Uniform Convergence of Gradients for Non-Convex Learning and Optimization
• Deep Online Convex Optimization with Gated Games
• Taming Convergence for Asynchronous Stochastic Gradient Descent with Unbounded Delay in Non-Convex Learning
• A universal framework for learning the elliptical mixture model
• Implicit Regularization Properties of Variance Reduced Stochastic Mirror Descent
• Stochastic Algorithms for Self-consistent Calculations of Electronic Structures
• Stochastic quasi-Newton with adaptive step lengths for large-scale problems
• Generalized Left-Localized Cayley Parametrization for Optimization with Orthogonality Constraints
• On Sampling Strategies for Neural Network-based Collaborative Filtering
• Stochastic Variance Reduced Riemannian Eigensolver
• k-SVRG: Variance Reduction for Large Scale Optimization
• Variance Reduction with Sparse Gradients
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• Variance-Reduced Proximal Stochastic Gradient Descent for Non-convex Composite optimization
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima
• Deeply Supervised Semantic Model for Click-Through Rate Prediction in Sponsored Search
• Linear Convergence of Accelerated Stochastic Gradient Descent for Nonconvex Nonsmooth Optimization
• Non-convex Conditional Gradient Sliding
• Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds
• On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization
• DEAM: Adaptive Momentum with Discriminative Weight for Stochastic Optimization
• Predictive Local Smoothness for Stochastic Gradient Methods
• Stochastic Variance Reduction Gradient for a Non-convex Problem Using Graduated Optimization
• Stochastic Gradient Langevin Dynamics with Variance Reduction
• Stochastic Gradient Descent for Stochastic Doubly-Nonconvex Composite Optimization
• Efficient preconditioned stochastic gradient descent for estimation in latent variable models
• Fast Global Convergence via Landscape of Empirical Loss
• Stochastic Approximate Gradient Descent via the Langevin Algorithm
• Training L1-Regularized Models with Orthant-Wise Passive Descent Algorithms
• A Stochastic Gradient Method with Biased Estimation for Faster Nonconvex Optimization
• Accelerated Stochastic Quasi-Newton Optimization on Riemann Manifolds
• Towards Better Generalization: BP-SVRG in Training Deep Neural Networks
• Improved Oracle Complexity of Variance Reduced Methods for Nonsmooth Convex Stochastic Composition Optimization
• Generalization Error Bounds for Optimization Algorithms via Stability
• Stochastic Doubly Robust Gradient