Variance Reduction for Faster Non-Convex Optimization

Abstract

We consider the fundamental problem in non-convex optimization of efficiently reaching a stationary point. In contrast to the convex case, in the long history of this basic problem, the only known theoretical results on first-order non-convex optimization remain to be full gradient descent that converges in $O(1/\epsilon )$ iterations for smooth objectives, and stochastic gradient descent that converges in $O(1/{\epsilon }^2)$ iterations for objectives that are sum of smooth functions. We provide the first improvement in this line of research. Our result is based on the variance reduction trick recently introduced to convex optimization, as well as a brand new analysis of variance reduction that is suitable for non-convex optimization. For objectives that are sum of smooth functions, our first-order minibatch stochastic method converges with an $O(1/\epsilon )$ rate, and is faster than full gradient descent by $\Omega (n^{1/3})$. We demonstrate the effectiveness of our methods on empirical risk minimizations with non-convex loss functions and training neural nets.

polished writing

References in corpus (8)

• A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Stochastic Variance Reduction for Nonconvex Optimization
• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
• SDCA without Duality
• Fast Incremental Method for Nonconvex Optimization

Cited by in corpus (49)

• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
• The Power of Normalization: Faster Evasion of Saddle Points
• Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Accelerated Methods for Non-Convex Optimization
• NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization
• Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
• SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
• Analysis of nonsmooth stochastic approximation: the differential inclusion approach
• Asynchronous Stochastic Gradient Descent with Variance Reduction for Non-Convex Optimization
• Fast Stochastic Variance Reduced Gradient Method with Momentum Acceleration for Machine Learning
• Stochastic Variance-Reduced Cubic Regularized Newton Method
• Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity
• Scaling-up Distributed Processing of Data Streams for Machine Learning
• An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient
• 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
• VR-SGD: A Simple Stochastic Variance Reduction Method for Machine Learning
• Finding Local Minima via Stochastic Nested Variance Reduction
• Stochastic Alternating Direction Method of Multipliers with Variance Reduction for Nonconvex Optimization
• Riemannian stochastic variance reduced gradient on Grassmann manifold
• Compositional ADAM: An Adaptive Compositional Solver
• Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradient
• A Convergence Analysis for A Class of Practical Variance-Reduction Stochastic Gradient MCMC
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• Almost Tune-Free Variance Reduction
• Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization
• A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity
• Deep Online Convex Optimization with Gated Games
• Stochastic quasi-Newton with adaptive step lengths for large-scale problems
• Variance Reduction with Sparse Gradients
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• k-SVRG: Variance Reduction for Large Scale Optimization
• Variance-Reduced Proximal Stochastic Gradient Descent for Non-convex Composite optimization
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima
• SAGA and Restricted Strong Convexity
• Sample Efficient Stochastic Variance-Reduced Cubic Regularization Method
• Non-convex Conditional Gradient Sliding
• Linear Convergence of Accelerated Stochastic Gradient Descent for Nonconvex Nonsmooth Optimization
• Larger is Better: The Effect of Learning Rates Enjoyed by Stochastic Optimization with Progressive Variance Reduction
• Stochastic Variance Reduction Gradient for a Non-convex Problem Using Graduated Optimization
• Stochastic Gradient Langevin Dynamics with Variance Reduction
• Training L1-Regularized Models with Orthant-Wise Passive Descent Algorithms
• Improved Oracle Complexity of Variance Reduced Methods for Nonsmooth Convex Stochastic Composition Optimization
• Stochastic Doubly Robust Gradient