mlsanityData to 14 Oct 2026

Zeroth-Order Optimization Finds Flat Minima

arXiv 2506.05454 ↗First posted 5 Jun 2025cs.LG cs.AI math.OCcited by 6

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Zeroth-order methods are extensively used in machine learning applications where gradients are infeasible or expensive to compute, such as black-box attacks, reinforcement learning, and language model fine-tuning. Existing optimization theory focuses on convergence to an arbitrary stationary point, but less is known on the implicit regularization that provides a fine-grained characterization on which particular solutions are finally reached. We show that zeroth-order optimization with the standard two-point estimator favors solutions with small trace of Hessian, which is widely used in previous work to distinguish between sharp and flat minima. We further provide convergence rates of zeroth-order optimization to approximate flat minima for convex and sufficiently smooth functions, where flat minima are defined as the minimizers that achieve the smallest trace of Hessian among all optimal solutions. Experiments on binary classification tasks with convex losses and language model fine-tuning support our theoretical findings.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 79 of its 107 references that are in the map. First posted on arXiv 5 Jun 2025.

Builds on

79 of 107 references.

References · 79

  1. 2019RoBERTa: A Robustly Optimized BERT Pretraining Approachcited by 13,372
  2. 2020Sharpness-Aware Minimization for Efficiently Improving Generalizationcited by 1,417
  3. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,352
  4. 2018Averaging Weights Leads to Wider Optima and Better Generalizationcited by 1,209
  5. 2022Fine-Tuning can Distort Pretrained Features and Underperform Out-of-Distributioncited by 739
  6. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  7. 2019Square Attack: a query-efficient black-box adversarial attack via random searchcited by 685
  8. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 666
  9. 2017Exploring Generalization in Deep Learningcited by 600
  10. 2017Evolution Strategies as a Scalable Alternative to Reinforcement Learningcited by 574
  11. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 533
  12. 2017Sharp Minima Can Generalize For Deep Netscited by 466
38 more
  1. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 427
  2. 2016Entropy-SGD: Biasing Gradient Descent Into Wide Valleyscited by 359
  3. 2023Fine-Tuning Language Models with Just Forward Passescited by 345
  4. 2021ASAM: Adaptive Sharpness-Aware Minimization for Scale-Invariant Learning of Deep Neural Networkscited by 293
  5. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  6. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 198
  7. 2022Surrogate Gap Minimization Improves Sharpness-Aware Trainingcited by 172
  8. 2022Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stabilitycited by 155
  9. 2022Towards Understanding Sharpness-Aware Minimizationcited by 146
  10. 2022Towards Efficient and Scalable Sharpness-Aware Minimizationcited by 129
  11. 2022Understanding Gradient Descent on Edge of Stability in Deep Learningcited by 128
  12. 2019Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like processcited by 123
  13. 2021Label Noise SGD Provably Prefers Flat Global Minimizerscited by 121
  14. 2024Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmarkcited by 114
  15. 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 111
  16. 2018Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimizationcited by 111
  17. 2021What Happens after SGD Reaches Zero Loss? --A Mathematical Frameworkcited by 107
  18. 2022Sharpness-Aware Training for Freecited by 95
  19. 2019Asymmetric Valleys: Beyond Sharp and Flat Local Minimacited by 90
  20. 2022Understanding the Generalization Benefit of Normalization Layers: Sharpness Reductioncited by 86
  21. 2022Same Pre-training Loss, Better Downstream: Implicit Bias Matters for Language Modelscited by 84
  22. 2020Regularizing Neural Networks via Adversarial Model Perturbationcited by 78
  23. 2022When Do Flat Minima Optimizers Work?cited by 78
  24. 2019ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimizationcited by 76
  25. 2022Analyzing Sharpness along GD Trajectory: Progressive Sharpening and Edge of Stabilitycited by 63
  26. 2022Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learningcited by 59
  27. 2023Gradient Norm Aware Minimization Seeks First-Order Flatness and Improves Generalizationcited by 57
  28. 2023Federated Full-Parameter Tuning of Billion-Sized Language Models with Communication Cost under 18 Kilobytescited by 55
  29. 2024Sparse MeZO: Less Parameters for Better Performance in Zeroth-Order LLM Fine-Tuningcited by 54
  30. 2024Variance-reduced Zeroth-Order Methods for Fine-Tuning Language Modelscited by 54
  31. 2024Second-Order Fine-Tuning without Pain for LLMs:A Hessian Informed Zeroth-Order Optimizercited by 53
  32. 2022The Dynamics of Sharpness-Aware Minimization: Bouncing Across Ravines and Drifting Towards Wide Minimacited by 51
  33. 2022Learning threshold neurons via the "edge of stability"cited by 51
  34. 2024Enhancing Zeroth-order Fine-tuning for Language Models with Low-rank Structurescited by 50
  35. 2019Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimizationcited by 47
  36. 2016A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Ordercited by 44
  37. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 43
  38. 2023Sharpness Minimization Algorithms Do Not Only Minimize Sharpness To Achieve Better Generalizationcited by 39

50 most cited of 79 All 79 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 4; 2026: 2.

6 papers.

  1. 2025More Than Memory Savings: Zeroth-Order Optimization Mitigates Forgetting in Continual Learningcited by 1
  2. 2026Aligned but Fragile: Enhancing LLM Safety Robustness via Zeroth-Order Optimizationcited by 1
  3. 2025Flatness-Aware Stochastic Gradient Langevin Dynamicscited by 0
  4. 2025Zeroth-Order Sharpness-Aware Learning with Exponential Tiltingcited by 0
  5. 2025ConMeZO: Adaptive Descent-Direction Sampling for Gradient-Free Finetuning of Large Language Modelscited by 0
  6. 2026Zeroth-Order Optimization at the Edge of Stabilitycited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Explicit and Non-asymptotic Query Complexities of Rank-Based Zeroth-order Algorithm on Stochastic Smooth Functions
  2. 2021Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problems
  3. 2026On the Stability and Generalization of First-order Bilevel Minimax Optimization
  4. 2026A Flatness-Generalization Relation in the Teacher-Student Tree-Committee Machine
  5. 2025Improving the Straight-Through Estimator with Zeroth-Order Information
  6. 2025Understanding Flatness in Generative Models: Its Role and Benefits
  7. 2024Bilateral Sharpness-Aware Minimization for Flatter Minima
  8. 2024Revisiting Scalable Hessian Diagonal Approximations for Applications in Reinforcement Learning