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

2019/02/13 by Chi Jin, Praneeth Netrapalli, Jin, Chi +7 · 58 citations
Computer Science · Engineering · Mathematics · #Applied mathematics #Artificial intelligence #Artificial neural network #Combinatorics #Computer science #Descent (aeronautics) #Dimension (graph theory) #FOS: Computer and information sciences #FOS: Mathematics #Geometry #Gradient descent #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Mathematical analysis #Mathematical optimization #Mathematics #Optimization and Control (math.OC) #Order (exchange) #Physics #Polynomial #Regular polygon #Saddle #Saddle point #Sparse and Compressive Sensing Techniques #Stationary point #Stochastic Gradient Optimization Techniques #Stochastic gradient descent #cs.LG #math.OC #stat.ML

paper · pdf · doi:10.48550/arxiv.1902.04811

published in arXiv (Cornell University) (Cornell University) · A 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)

openalex publication_date 2019/02/13 · arxiv created 2019/09/04 · arxiv updated 2019/09/05 · openalex created_date 2019/09/12 · openalex updated_date 2026/07/28

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.

Citations

• How to Escape Saddle Points Efficiently
• A Stochastic Approximation Method
• The Power of Normalization: Faster Evasion of Saddle Points
• A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics
• Lower bounds for finding stationary points I
• Neon2: Finding Local Minima via First-Order Oracles
• Escaping Saddles with Stochastic Gradients
• Finding Local Minima via Stochastic Nested Variance Reduction
• A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Accelerated Methods for Non-Convex Optimization
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition

Cited by

• Sensor network localization has a benign landscape after low-dimensional relaxation
• Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework
• Distributed Deep Learning with Event-Triggered Communication

Related

• The Impact of Local Geometry and Batch Size on Stochastic Gradient Descent for Nonconvex Problems
• Tackling benign nonconvexity with smoothing and stochastic gradients
• Better Theory for SGD in the Nonconvex World
• A Novel Unified Parametric Assumption for Nonconvex Optimization
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points