On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points

Abstract

Gradient descent (GD) and stochastic gradient descent (SGD) are the workhorses of large-scale machine learning. While classical theory focused on analyzing the performance of these methods in convex optimization problems, the most notable successes in machine learning have involved nonconvex optimization, and a gap has arisen between theory and practice. Indeed, traditional analyses of GD and SGD show that both algorithms converge to stationary points efficiently. But these analyses do not take into account the possibility of converging to saddle points. More recent theory has shown that GD and SGD can avoid saddle points, but the dependence on dimension in these analyses is polynomial. For modern machine learning, where the dimension can be in the millions, such dependence would be catastrophic. We analyze perturbed versions of GD and SGD and show that they are truly efficient---their dimension dependence is only polylogarithmic. Indeed, these algorithms converge to second-order stationary points in essentially the same time as they take to converge to classical first-order stationary points.

arXiv commentA preliminary version of this paper, with a subset of the results that are presented here, was presented at ICML 2017 (also as arXiv:1703.00887)

References in corpus (17)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Efficient approaches for escaping higher order saddle points in non-convex optimization
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• Escaping Saddles with Stochastic Gradients
• The Power of Normalization: Faster Evasion of Saddle Points
• Neon2: Finding Local Minima via First-Order Oracles
• A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics
• Accelerated Methods for Non-Convex Optimization
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm
• A Generic Approach for Escaping Saddle points
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Finding Local Minima via Stochastic Nested Variance Reduction

Cited by in corpus (34)

• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
• Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval
• Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima
• A semigroup method for high dimensional committor functions based on neural network
• On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics
• Towards Understanding Hierarchical Learning: Benefits of Neural Representations
• Distributed Deep Learning with Event-Triggered Communication
• Replica Exchange for Non-Convex Optimization
• Stochastic Training is Not Necessary for Generalization
• Continuous-time Lower Bounds for Gradient-based Algorithms
• Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
• Escape saddle points faster on manifolds via perturbed Riemannian stochastic recursive gradient
• Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms
• Efficient Gradient Approximation Method for Constrained Bilevel Optimization
• Multichannel Sparse Blind Deconvolution on the Sphere
• Representation Learning Beyond Linear Prediction Functions
• Properties of Discrete Sliced Wasserstein Losses
• Law of large numbers and central limit theorem for wide two-layer neural networks: the mini-batch and noisy case
• The loss landscape of deep linear neural networks: a second-order analysis
• FourierSAT: A Fourier Expansion-Based Algebraic Framework for Solving Hybrid Boolean Constraints
• On the global convergence of randomized coordinate gradient descent for non-convex optimization
• Quantum algorithm for finding the negative curvature direction in non-convex optimization
• Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methods
• Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization
• GO Hessian for Expectation-Based Objectives
• Characterization of Excess Risk for Locally Strongly Convex Population Risk
• Escaping Saddle Points for Zeroth-order Nonconvex Optimization using Estimated Gradient Descent
• The Confluence of Networks, Games and Learning
• On the Second-order Convergence Properties of Random Search Methods