# How to escape sharp minima with random perturbations

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 64 references that are in the map.
- First posted on arXiv 25 May 2023.

## Builds on (most cited first, 30 of 49)

- [Sharpness-Aware Minimization for Efficiently Improving Generalization](https://mlsanity.com/paper/2010.01412/) (2020)
- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Averaging Weights Leads to Wider Optima and Better Generalization](https://mlsanity.com/paper/1803.05407/) (2018)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNs](https://mlsanity.com/paper/1802.10026/) (2018)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Sharp Minima Can Generalize For Deep Nets](https://mlsanity.com/paper/1703.04933/) (2017)
- [Entropy-SGD: Biasing Gradient Descent Into Wide Valleys](https://mlsanity.com/paper/1611.01838/) (2016)
- [Essentially No Barriers in Neural Network Energy Landscape](https://mlsanity.com/paper/1803.00885/) (2018)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Empirical Analysis of the Hessian of Over-Parametrized Neural Networks](https://mlsanity.com/paper/1706.04454/) (2017)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stability](https://mlsanity.com/paper/2209.15594/) (2022)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Understanding Gradient Descent on Edge of Stability in Deep Learning](https://mlsanity.com/paper/2205.09745/) (2022)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process](https://mlsanity.com/paper/1904.09080/) (2019)
- [Label Noise SGD Provably Prefers Flat Global Minimizers](https://mlsanity.com/paper/2106.06530/) (2021)
- [An Alternative View: When Does SGD Escape Local Minima?](https://mlsanity.com/paper/1802.06175/) (2018)
- [Sharpness-Aware Minimization Improves Language Model Generalization](https://mlsanity.com/paper/2110.08529/) (2021)
- [What Happens after SGD Reaches Zero Loss? --A Mathematical Framework](https://mlsanity.com/paper/2110.06914/) (2021)
- [A Modern Look at the Relationship between Sharpness and Generalization](https://mlsanity.com/paper/2302.07011/) (2023)
- [Asymmetric Valleys: Beyond Sharp and Flat Local Minima](https://mlsanity.com/paper/1902.00744/) (2019)
- [Hessian-based Analysis of Large Batch Training and Robustness to Adversaries](https://mlsanity.com/paper/1802.08241/) (2018)
- [Same Pre-training Loss, Better Downstream: Implicit Bias Matters for Language Models](https://mlsanity.com/paper/2210.14199/) (2022)
- [Regularizing Neural Networks via Adversarial Model Perturbation](https://mlsanity.com/paper/2010.04925/) (2020)

## Built on by (most cited first, 13 of 13)

- [Does SGD really happen in tiny subspaces?](https://mlsanity.com/paper/2405.16002/) (2024)
- [Sharpness-Aware Minimization Efficiently Selects Flatter Minima Late in Training](https://mlsanity.com/paper/2410.10373/) (2024)
- [Explicit Eigenvalue Regularization Improves Sharpness-Aware Minimization](https://mlsanity.com/paper/2501.12666/) (2025)
- [Zeroth-Order Optimization Finds Flat Minima](https://mlsanity.com/paper/2506.05454/) (2025)
- [Gradient Extrapolation for Debiased Representation Learning](https://mlsanity.com/paper/2503.13236/) (2025)
- [On the Trade-off between Flatness and Optimization in Distributed Learning](https://mlsanity.com/paper/2406.20006/) (2024)
- [TRACE for Tracking the Emergence of Semantic Representations in Transformers](https://mlsanity.com/paper/2505.17998/) (2025)
- [Unveiling m-Sharpness Through the Structure of Stochastic Gradient Noise](https://mlsanity.com/paper/2509.18001/) (2025)
- [Generalization at the Edge of Stability](https://mlsanity.com/paper/2604.19740/) (2026)
- [Flatness-Aware Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2510.02174/) (2025)
- [X-SAM: Boosting Sharpness-Aware Minimization with Dominant-Eigenvector Gradient Correction](https://mlsanity.com/paper/2601.10251/) (2026)
- [Optimizing Server Placement for Vertical Federated Learning in Dynamic Edge/Fog Networks](https://mlsanity.com/paper/2605.09813/) (2026)
- [FedFFT: Taming Client Drift in Federated SAM via Spectral Perturbation Filtering](https://mlsanity.com/paper/2607.04170/) (2026)

## Abstract (arXiv)

Modern machine learning applications have witnessed the remarkable success of optimization algorithms that are designed to find flat minima. Motivated by this design choice, we undertake a formal study that (i) formulates the notion of flat minima, and (ii) studies the complexity of finding them. Specifically, we adopt the trace of the Hessian of the cost function as a measure of flatness, and use it to formally define the notion of approximate flat minima. Under this notion, we then analyze algorithms that find approximate flat minima efficiently. For general cost functions, we discuss a gradient-based algorithm that finds an approximate flat local minimum efficiently. The main component of the algorithm is to use gradients computed from randomly perturbed iterates to estimate a direction that leads to flatter minima. For the setting where the cost function is an empirical risk over training data, we present a faster algorithm that is inspired by a recently proposed practical algorithm called sharpness-aware minimization, supporting its success in practice.