mlsanityData to 7 Oct 2026

Zeroth-Order Optimization at the Edge of Stability

arXiv 2604.14669 ↗First posted 16 Apr 2026cs.LG math.DS math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

Zeroth-order (ZO) methods are widely used when gradients are unavailable or prohibitively expensive, including black-box learning and memory-efficient fine-tuning of large models, yet their optimization dynamics in deep learning remain underexplored. In this work, we provide an explicit step size condition that exactly captures the (mean-square) linear stability of a family of ZO methods based on the standard two-point estimator. Our characterization reveals a sharp contrast with first-order (FO) methods: whereas FO stability is governed solely by the largest Hessian eigenvalue, mean-square stability of ZO methods depends on the entire Hessian spectrum. Since computing the full Hessian spectrum is infeasible in practical neural network training, we further derive tractable stability bounds that depend only on the largest eigenvalue and the Hessian trace. Empirically, we find that full-batch ZO methods operate at the edge of stability: ZO-GD, ZO-GDM, and ZO-Adam consistently stabilize near the predicted stability boundary across a range of deep learning training problems. Our results highlight an implicit regularization effect specific to ZO methods, where large step sizes primarily regularize the Hessian trace, whereas in FO methods they regularize the top eigenvalue.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 38 of its 47 references that are in the map. First posted on arXiv 16 Apr 2026.

Builds on

38 of 47 references.

References · 38

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 29,915
  3. 2018Group Normalizationcited by 1,514
  4. 2020Sharpness-Aware Minimization for Efficiently Improving Generalizationcited by 1,404
  5. 2019Square Attack: a query-efficient black-box adversarial attack via random searchcited by 682
  6. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 656
  7. 2017Evolution Strategies as a Scalable Alternative to Reinforcement Learningcited by 555
  8. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 413
  9. 2023Fine-Tuning Language Models with Just Forward Passescited by 337
  10. 2020The large learning rate phase of deep learning: the catapult mechanismcited by 206
  11. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 190
  12. 2024The Road Less Scheduledcited by 158
26 more
  1. 2022Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stabilitycited by 151
  2. 2024Adam-mini: Use Fewer Learning Rates To Gain Morecited by 134
  3. 2022Understanding Gradient Descent on Edge of Stability in Deep Learningcited by 126
  4. 2024Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmarkcited by 113
  5. 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 105
  6. 2022Adaptive Gradient Methods at the Edge of Stabilitycited by 88
  7. 2022Understanding the unstable convergence of gradient descentcited by 84
  8. 2017Stochastic Zeroth-order Optimization in High Dimensionscited by 62
  9. 2021On Linear Stability of SGD and Input-Smoothness of Neural Networkscited by 61
  10. 2022Analyzing Sharpness along GD Trajectory: Progressive Sharpening and Edge of Stabilitycited by 61
  11. 2022Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learningcited by 59
  12. 2024Understanding Optimization in Deep Learning with Central Flowscited by 57
  13. 2023Federated Full-Parameter Tuning of Billion-Sized Language Models with Communication Cost under 18 Kilobytescited by 55
  14. 2022Understanding Edge-of-Stability Training Dynamics with a Minimalist Examplecited by 54
  15. 2020Learning Rates as a Function of Batch Size: A Random Matrix Theory Approach to Neural Network Trainingcited by 50
  16. 2020Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectivescited by 27
  17. 2023DPZero: Private Fine-Tuning of Language Models without Backpropagationcited by 26
  18. 2023Trajectory Alignment: Understanding the Edge of Stability Phenomenon via Bifurcation Theorycited by 24
  19. 2024Edge of Stochastic Stability: Revisiting the Edge of Stability for SGDcited by 24
  20. 2023Sharpness-Aware Minimization and the Edge of Stabilitycited by 16
  21. 2022A view of mini-batch SGD via generating functions: conditions of convergence, phase transitions, benefit from negative momentacited by 11
  22. 2023Exact Mean Square Linear Stability Analysis for SGDcited by 10
  23. 2023Type-II Saddles and Probabilistic Stability of Stochastic Gradient Descentcited by 8
  24. 2025Through the River: Understanding the Benefit of Schedule-Free Methods for Language Model Trainingcited by 8
  25. 2025Zeroth-Order Optimization Finds Flat Minimacited by 6
  26. 2025Understanding Sharpness Dynamics in NN Training with a Minimalist Example: The Effects of Dataset Difficulty, Depth, Stochasticity, and Morecited by 5

Built on by

Not cited yet.