mlsanityData to 14 Oct 2026

How to escape sharp minima with random perturbations

arXiv 2305.15659 ↗First posted 25 May 2023cs.LG cs.AI math.OCcited by 13

Not on the map. Why?

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.

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

49 of 64 references.

References · 49

  1. 2020Sharpness-Aware Minimization for Efficiently Improving Generalizationcited by 1,417
  2. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,352
  3. 2018Averaging Weights Leads to Wider Optima and Better Generalizationcited by 1,209
  4. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  5. 2017Exploring Generalization in Deep Learningcited by 600
  6. 2018Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNscited by 588
  7. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  8. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 533
  9. 2017Sharp Minima Can Generalize For Deep Netscited by 466
  10. 2016Entropy-SGD: Biasing Gradient Descent Into Wide Valleyscited by 359
  11. 2018Essentially No Barriers in Neural Network Energy Landscapecited by 330
  12. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
37 more
  1. 2017Empirical Analysis of the Hessian of Over-Parametrized Neural Networkscited by 290
  2. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  3. 2017How to Escape Saddle Points Efficientlycited by 285
  4. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 243
  5. 2022Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stabilitycited by 155
  6. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 145
  7. 2022Understanding Gradient Descent on Edge of Stability in Deep Learningcited by 128
  8. 2017Lower Bounds for Finding Stationary Points Icited by 126
  9. 2019Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like processcited by 123
  10. 2021Label Noise SGD Provably Prefers Flat Global Minimizerscited by 121
  11. 2018An Alternative View: When Does SGD Escape Local Minima?cited by 115
  12. 2021Sharpness-Aware Minimization Improves Language Model Generalizationcited by 108
  13. 2021What Happens after SGD Reaches Zero Loss? --A Mathematical Frameworkcited by 107
  14. 2023A Modern Look at the Relationship between Sharpness and Generalizationcited by 92
  15. 2019Asymmetric Valleys: Beyond Sharp and Flat Local Minimacited by 90
  16. 2018Hessian-based Analysis of Large Batch Training and Robustness to Adversariescited by 87
  17. 2022Same Pre-training Loss, Better Downstream: Implicit Bias Matters for Language Modelscited by 84
  18. 2020Regularizing Neural Networks via Adversarial Model Perturbationcited by 78
  19. 2022When Do Flat Minima Optimizers Work?cited by 78
  20. 2018Escaping Saddles with Stochastic Gradientscited by 66
  21. 2022How Does Sharpness-Aware Minimization Minimize Sharpness?cited by 65
  22. 2021On Linear Stability of SGD and Input-Smoothness of Neural Networkscited by 63
  23. 2019Normalized Flat Minima: Exploring Scale Invariant Definition of Flat Minima for Neural Networks using PAC-Bayesian Analysiscited by 59
  24. 2017Lower Bounds for Finding Stationary Points II: First-Order Methodscited by 58
  25. 2022On the Maximum Hessian Eigenvalue and Generalizationcited by 57
  26. 2022The Dynamics of Sharpness-Aware Minimization: Bouncing Across Ravines and Drifting Towards Wide Minimacited by 51
  27. 2022Learning threshold neurons via the "edge of stability"cited by 51
  28. 2021Large Learning Rate Tames Homogeneity: Convergence and Balancing Effectcited by 50
  29. 2017Natasha 2: Faster Non-Convex Optimization Than SGDcited by 49
  30. 2019Bad Global Minima Exist and SGD Can Reach Themcited by 49
  31. 2019The Complexity of Finding Stationary Points with Stochastic Gradient Descentcited by 35
  32. 2022Flat minima generalize for low-rank matrix recoverycited by 28
  33. 2023Why (and When) does Local SGD Generalize Better than SGD?cited by 26
  34. 2023The Crucial Role of Normalization in Sharpness-Aware Minimizationcited by 26
  35. 2023An SDE for Modeling SAM: Theory and Insightscited by 22
  36. 2019Diametrical Risk Minimization: Theory and Computationscited by 15
  37. 2019Stochastic Recursive Variance-Reduced Cubic Regularization Methodscited by 12

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 6; 2026: 4.

13 papers.

Sort:

By area:

  1. 2024Does SGD really happen in tiny subspaces?cited by 36
  2. 2024Sharpness-Aware Minimization Efficiently Selects Flatter Minima Late in Trainingcited by 24
  3. 2025Explicit Eigenvalue Regularization Improves Sharpness-Aware Minimizationcited by 21
  4. 2025Zeroth-Order Optimization Finds Flat Minimacited by 6
  5. 2025Gradient Extrapolation for Debiased Representation Learningcited by 4
  6. 2024On the Trade-off between Flatness and Optimization in Distributed Learningcited by 3
  7. 2025TRACE for Tracking the Emergence of Semantic Representations in Transformerscited by 3
  8. 2025Unveiling m-Sharpness Through the Structure of Stochastic Gradient Noisecited by 2
  9. 2026Generalization at the Edge of Stabilitycited by 2
  10. 2025Flatness-Aware Stochastic Gradient Langevin Dynamicscited by 0
  11. 2026X-SAM: Boosting Sharpness-Aware Minimization with Dominant-Eigenvector Gradient Correctioncited by 0
  12. 2026Optimizing Server Placement for Vertical Federated Learning in Dynamic Edge/Fog Networkscited by 0
1 more
  1. 2026FedFFT: Taming Client Drift in Federated SAM via Spectral Perturbation Filteringcited by 0