Zeroth-Order Optimization at the Edge of Stability
Minhak Song, Liang Zhang, Bingcong Li, Niao He, Michael Muehlebach, Sewoong Oh · 2026
Read Zeroth-Order Optimization at the Edge of Stability by Minhak Song, Liang Zhang, Bingcong Li, Niao He, Michael Muehlebach, Sewoong Oh (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-14669.txt.
Introduction
Song and five colleagues characterize when gradient-free zeroth-order methods stay stable while training deep networks, using the standard two-point gradient estimate. Unlike first-order methods, whose stability hinges only on the largest Hessian eigenvalue, mean-square stability here depends on the whole Hessian spectrum. Since that spectrum cannot be computed in practice, they derive usable bounds from the top eigenvalue and the trace alone. Experiments found full-batch zeroth-order methods sitting at the predicted stability edge, with large steps quietly regularizing the trace.
Catalog record
| CREATOR | Minhak Song, Liang Zhang, Bingcong Li, Niao He, Michael Muehlebach, Sewoong Oh |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 132209 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.14669
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Zeroth-Order Optimization at the Edge of Stability Minhak Song, Liang Zhang, Bingcong Li, Niao He, Michael Muehlebach, Sewoong Oh Abstract 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. 1 Introduction Figure 1 : EoS behaviors of FO and ZO methods are captured by different spectral quantities of the Hessian. We train full-batch GD (left) and ZO-GD (right) with varying step sizes \eta on a CNN for CIFAR-10. For GD, the largest eigenvalue of the Hessian \lambda_{\max}({\bm{H}}_{t}) stabilizes near 2/\eta . For ZO-GD, the trace of the Hessian \Tr({\bm{H}}_{t}) instead stabilizes slightly below 2/\eta . Figure 2 : Zeroth-order methods operate at the mean-square edge of stability. We train full-batch ZO methods on a CNN for CIFAR-10 and track the curvature terms defining the mean-square stability interval from Section 4.2 . Across all panels, each color denotes one run; the solid curve is the lower-band term, the dash-dotted curve is the upper-band term, and the dashed line is the predicted stability threshold. Left (ZO-GD, varying \eta ): lower \Tr({\bm{H}}_{t}) , upper \Tr({\bm{H}}_{t})+2\lambda_{\max}({\bm{H}}_{t}) , threshold 2/\eta in Eq. equation 23 . Middle (ZO-GDM, varying \beta with fixed \eta=10^{-4} ): lower \Tr({\bm{H}}_{t}) , upper \Tr({\bm{H}}_{t})+\frac{2}{1+\beta}\lambda_{\max}({\bm{H}}_{t}) , threshold 2(1-\beta)/\eta in Eq. equation 24 . Right (ZO-Adam, varying \eta with fixed (\beta_{1},\beta_{2})=(0.9,0.999) ): lower \Tr({\bm{P}}_{t}^{-1}{\bm{H}}_{t}) , upper \Tr({\bm{P}}_{t}^{-1}{\bm{H}}_{t})+\frac{2}{1+\beta_{1}}\lambda_{\max}({\bm{P}}_{t}^{-1}{\bm{H}}_{t}) , threshold 2/\eta in Eq. equation 25 . Across all methods, the threshold stays within (or very close to) the stability interval throughout training, indicating mean-square EoS behavior. Zeroth-order (ZO) optimization methods, which rely only on function evaluations, are widely used when gradients are unavailable, unreliable, or expensive to compute. Such a setting arises in black-box learning, derivative-free control, and increasingly in modern large-model pipelines, where memory and systems constraints can make backpropagation costly. Recent work shows that ZO methods based on two-point function evaluations can fine-tune large language models (LLMs) with competitive accuracy while substantially reducing memory usage and compute overhead ( Malladi et al. 2023 ; Zhang et al. 2024b ) . Despite their growing practical relevance, the training dynamics of ZO methods in deep learning remain far less understood than those of first-order (FO) optimizers. For FO optimization in deep learning, one prominent empirical phenomenon is the edge of stability (EoS). In full-batch gradient descent (GD) with step size \eta on a quadratic objective f_{\mathrm{quad}}({\bm{x}})=\tfrac{1}{2}{\bm{x}}^{\top}{\bm{H}}{\bm{x}} , the iterates diverge when \eta>2/\lambda_{\max}({\bm{H}}) . In neural network training, however, optimization often remains well-behaved even at step sizes beyond this local quadratic threshold. Along the training trajectory \{{\bm{x}}_{t}\} , the top eigenvalue of the Hessian \lambda_{\max}({\bm{H}}_{t}) increases early in training and then stabilizes near the threshold 2/\eta over long horizons ( Cohen et al. 2021 ) . This phenomenon has motivated a growing line of work aimed at understanding its mechanism and its connections to stability, curvature, and implicit regularization in deep learning optimization dynamics ( Ahn et al. 2022 ; Arora et al. 2022 ; Damian et al. 2023 ; Cohen et al. 2025 ) . In this work, we ask whether a similar phenomenon arises in zeroth-order training. At first glance, this is far from obvious: ZO methods update parameters by drawing random search directions at every iteration, and their stability cannot be understood through the deterministic arguments typically used to explain FO dynamics and stability. As a preliminary experiment, Figure 1 compares full-batch (first-order) GD and zeroth-order gradient descent (ZO-GD) with varying step sizes \eta . For GD, the top Hessian eigenvalue \lambda_{\max}({\bm{H}}_{t}) stabilizes near 2/\eta , consistent with the behavior predicted by standard EoS theory. For ZO-GD, however, \lambda_{\max}({\bm{H}}_{t}) does not exhibit the same trend; instead, perhaps surprisingly, the Hessian trace \Tr({\bm{H}}_{t}) stabilizes slightly below 2/\eta . This suggests that ZO training may be governed by a different stability mechanism than FO training, and that ZO methods may exhibit their own EoS phenomenon in deep learning. These observations motivate the following fundamental questions: ( i ) do ZO methods operate at the edge of stability in neural network training , and ( ii ) if so, which curvature-related quantity governs their stability ? We introduce a mean-square linear stability theory for ZO methods to investigate these questions. In Section 4 , we provide an exact step size characterization of mean-square linear stability under the linearized dynamics for a family of ZO optimizers, including ZO-GD and its momentum and preconditioned variants. Unlike FO methods, whose stability is governed solely by the largest Hessian eigenvalue, mean-square stability of ZO methods depends on the entire Hessian spectrum. Moreover, momentum affects stability in opposite ways: increasing \beta enlarges the stable regime for GD with momentum (GDM), but shrinks it for ZO-GD with momentum (ZO-GDM). Since computing the full spectrum is typically infeasible, we also derive tractable bounds that depend only on the Hessian trace and the largest eigenvalue (summarized in Table 1 ). Technically, our analysis introduces a cone-preserving linear covariance operator with a rank-one global coupling term to capture the dynamics of the ZO second-moment recursion. This reduction allows one to characterize its spectral radius using the Krein–Rutman Theorem and derive the explicit mean-square stability conditions. In Section 5 , we empirically find that full-batch ZO methods operate at the mean-square edge of stability across architectures and tasks: ZO methods (ZO-GD, ZO-GDM, and ZO-Adam) consistently stabilize near the predicted mean-square stability boundary. Notably, this behavior is governed primarily by trace-based curvature quantities, providing new insight into how large step sizes implicitly bias ZO training toward solutions with small (preconditioned) Hessian trace. Table 1 : Summary of linear stability conditions for FO and ZO methods under the linearized dynamics ( Definition 1 ). For FO methods of GD, GDM, and Adam, we report the exact critical step size \eta^{\star} , and the mean and mean-square thresholds coincide. For ZO methods, we report lower and upper bounds on the mean-square critical step size \eta^{\star}_{\mathrm{ms}} ; the critical step size in the mean, \eta^{\star}_{\mathrm{mean}} , matches the corresponding FO threshold. For Adam and ZO-Adam, the reported conditions correspond to the frozen-preconditioner variants and are governed by the spectrum of the preconditioned Hessian {\bm{P}}^{-1}{\bm{H}} . See Section 4 for details. Method Linear Stability Condition GD \eta^{\star}_{\mathrm{mean}}=\eta^{\star}_{\mathrm{ms}}=\dfrac{2}{\lambda_{\max}({\bm{H}})} GDM ( Cohen et al. 2021 ) \eta^{\star}_{\mathrm{mean}}=\eta^{\star}_{\mathrm{ms}}=\dfrac{2(1+\beta)}{\lambda_{\max}({\bm{H}})}