# An Alternative View: When Does SGD Escape Local Minima?

arXiv: https://arxiv.org/abs/1802.06175 · HTML: https://mlsanity.com/paper/1802.06175/

## Key facts

- Cited by 115 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2018.

## Built on by (most cited first, 30 of 115)

- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [When Vision Transformers Outperform ResNets without Pre-training or Strong Data Augmentations](https://mlsanity.com/paper/2106.01548/) (2021)
- [Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity](https://mlsanity.com/paper/2106.09524/) (2021)
- [Sharpness-Aware Minimization Improves Language Model Generalization](https://mlsanity.com/paper/2110.08529/) (2021)
- [Reasonable Effectiveness of Random Weighting: A Litmus Test for Multi-Task Learning](https://mlsanity.com/paper/2111.10603/) (2021)
- [Improving Generalization in Federated Learning by Seeking Flat Minima](https://mlsanity.com/paper/2203.11834/) (2022)
- [Understanding Gradient Orthogonalization for Deep Learning via Non-Euclidean Trust-Region Optimization](https://mlsanity.com/paper/2503.12645/) (2025)
- [Understanding the Generalization Benefit of Normalization Layers: Sharpness Reduction](https://mlsanity.com/paper/2206.07085/) (2022)
- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [When Do Flat Minima Optimizers Work?](https://mlsanity.com/paper/2202.00661/) (2022)
- [In Defense of the Unitary Scalarization for Deep Multi-Task Learning](https://mlsanity.com/paper/2201.04122/) (2022)
- [Open-set Label Noise Can Improve Robustness Against Inherent Label Noise](https://mlsanity.com/paper/2106.10891/) (2021)
- [Beyond the Quadratic Approximation: the Multiscale Structure of Neural Network Loss Landscapes](https://mlsanity.com/paper/2204.11326/) (2022)
- [Anticorrelated Noise Injection for Improved Generalization](https://mlsanity.com/paper/2202.02831/) (2022)
- [No Train No Gain: Revisiting Efficient Training Algorithms For Transformer-based Language Models](https://mlsanity.com/paper/2307.06440/) (2023)
- [Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency](https://mlsanity.com/paper/2102.13152/) (2021)
- [Stochastic Collapse: How Gradient Noise Attracts SGD Dynamics Towards Simpler Subnetworks](https://mlsanity.com/paper/2306.04251/) (2023)
- [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022)
- [(S)GD over Diagonal Linear Networks: Implicit Regularisation, Large Stepsizes and Edge of Stability](https://mlsanity.com/paper/2302.08982/) (2023)
- [Revisiting the Noise Model of Stochastic Gradient Descent](https://mlsanity.com/paper/2303.02749/) (2023)
- [Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization](https://mlsanity.com/paper/2103.04564/) (2021)
- [Taxonomizing local versus global structure in neural network loss landscapes](https://mlsanity.com/paper/2107.11228/) (2021)
- [Revisiting Some Common Practices in Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2206.07505/) (2022)
- [Momentum Provably Improves Error Feedback!](https://mlsanity.com/paper/2305.15155/) (2023)
- [Catapults in SGD: spikes in the training loss and their impact on generalization through feature learning](https://mlsanity.com/paper/2306.04815/) (2023)
- [The Phenomenon of Policy Churn](https://mlsanity.com/paper/2206.00730/) (2022)
- [Consistent Sparse Deep Learning: Theory and Computation](https://mlsanity.com/paper/2102.13229/) (2021)
- [Decentralized Local Stochastic Extra-Gradient for Variational Inequalities](https://mlsanity.com/paper/2106.08315/) (2021)
- [Mind Mappings: Enabling Efficient Algorithm-Accelerator Mapping Space Search](https://mlsanity.com/paper/2103.01489/) (2021)
- [Exact Solutions of a Deep Linear Network](https://mlsanity.com/paper/2202.04777/) (2022)

## Abstract (arXiv)

Stochastic gradient descent (SGD) is widely used in machine learning. Although being commonly viewed as a fast but not accurate version of gradient descent (GD), it always finds better solutions than GD for modern neural networks. In order to understand this phenomenon, we take an alternative view that SGD is working on the convolved (thus smoothed) version of the loss function. We show that, even if the function f has many bad local minima or saddle points, as long as for every point x, the weighted average of the gradients of its neighborhoods is one point convex with respect to the desired solution x^*, SGD will get close to, and then stay around x^* with constant probability. More specifically, SGD will not get stuck at "sharp" local minima with small diameters, as long as the neighborhoods of these regions contain enough gradient information. The neighborhood size is controlled by step size and gradient noise. Our result identifies a set of functions that SGD provably works, which is much larger than the set of convex functions. Empirically, we observe that the loss surface of neural networks enjoys nice one point convexity properties locally, therefore our theorem helps explain why SGD works so well for neural networks.