Tackling benign nonconvexity with smoothing and stochastic gradients
Not on the map. Why?
Abstract (arXiv)
Non-convex optimization problems are ubiquitous in machine learning, especially in Deep Learning. While such complex problems can often be successfully optimized in practice by using stochastic gradient descent (SGD), theoretical analysis cannot adequately explain this success. In particular, the standard analyses do not show global convergence of SGD on non-convex functions, and instead show convergence to stationary points (which can also be local minima or saddle points). We identify a broad class of nonconvex functions for which we can show that perturbed SGD (gradient descent perturbed by stochastic noise -- covering SGD as a special case) converges to a global minimum (or a neighborhood thereof), in contrast to gradient descent without noise that can get stuck in local minima far from a global solution. For example, on non-convex functions that are relatively close to a convex-like (strongly convex or PL) function we show that SGD can converge linearly to a global optimum.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 51 of its 85 references that are in the map. First posted on arXiv 18 Feb 2022.
Builds on
51 of 85 references.
References · 51
- 2015Deep Residual Learning for Image Recognitioncited by 51,809
- 2014Adam: A Method for Stochastic Optimizationcited by 36,960
- 2020Sharpness-Aware Minimization for Efficiently Improving Generalizationcited by 1,404
- 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,337
- 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
- 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
- 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
- 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
- 2017Sharp Minima Can Generalize For Deep Netscited by 462
- 2016Entropy-SGD: Biasing Gradient Descent Into Wide Valleyscited by 357
- 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
- 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
38 more
- 2017How to Escape Saddle Points Efficientlycited by 284
- 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
- 2017Three Factors Influencing Minima in SGDcited by 270
- 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
- 2017Parameter Space Noise for Explorationcited by 158
- 2015Adding Gradient Noise Improves Learning for Very Deep Networkscited by 144
- 2016Matrix Completion has No Spurious Local Minimumcited by 124
- 2018An Alternative View: When Does SGD Escape Local Minima?cited by 115
- 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
- 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 81
- 2013Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programmingcited by 74
- 2017A Hitting Time Analysis of Stochastic Gradient Langevin Dynamicscited by 70
- 2017Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descentcited by 66
- 2018Escaping Saddles with Stochastic Gradientscited by 66
- 2017Non-convex Finite-Sum Optimization Via SCSG Methodscited by 61
- 2017Stochastic Cubic Regularization for Fast Nonconvex Optimizationcited by 55
- 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 55
- 2017Natasha 2: Faster Non-Convex Optimization Than SGDcited by 49
- 2018On the Ineffectiveness of Variance Reduced Optimization for Deep Learningcited by 48
- 2017"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functionscited by 46
- 2017Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Informationcited by 41
- 2019Sharp Analysis for Nonconvex SGD Escaping from Saddle Pointscited by 40
- 2019SGD Converges to Global Minimum in Deep Learning via Star-convex Pathcited by 39
- 2017Neon2: Finding Local Minima via First-Order Oraclescited by 36
- 2019Near-Optimal Methods for Minimizing Star-Convex Functions and Beyondcited by 36
- 2015On Graduated Optimization for Stochastic Non-Convex Problemscited by 34
- 2017First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Timecited by 29
- 2018SmoothOut: Smoothing Out Sharp Minima to Improve Generalization in Deep Learningcited by 25
- 2019SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Pointscited by 25
- 2020Extrapolation for Large-batch Training in Deep Learningcited by 25
- 2016Accelerated Methods for Non-Convex Optimizationcited by 20
- 2017A Generic Approach for Escaping Saddle pointscited by 13
- 2018On the Local Minima of the Empirical Riskcited by 12
- 2015Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functionscited by 9
- 2015Optimizing Star-Convex Functionscited by 9
- 2017NEON+: Accelerated Gradient Methods for Extracting Negative Curvature for Non-Convex Optimizationcited by 9
- 2020On The Convergence of First Order Methods for Quasar-Convex Optimizationcited by 8
- 2019Gradient Noise Convolution (GNC): Smoothing Loss Function for Distributed Large-Batch SGDcited by 7
50 most cited of 51 All 51 (JSON)
Built on by
Citing papers per year: 2022: 1; 2023: 1.
2 papers.