Zeroth-Order Optimization at the Edge of Stability

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 CNNs, ResNets, and Transformers on vision tasks. 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.

Modern AI models are usually trained with gradients: signals from backpropagation that tell each model parameter how to change. But in settings such as black-box learning or memory-efficient fine-tuning, gradients may be unavailable or too expensive, so practitioners use zeroth-order optimization, which learns by trying small random changes and checking whether the loss improves. Our paper asks why these gradient-free methods remain stable when their steps are large, and whether they also train at the edge of stability: the boundary between smooth progress and unstable updates. We show that zeroth-order methods do operate near this boundary, but for a different reason than standard gradient-based training. While gradient-based methods are mainly limited by the single sharpest direction of the loss landscape, we find that zeroth-order methods are limited by the combined curvature across many directions. Because measuring all directions is too expensive in real neural networks, we derive practical stability tests using two easier quantities: the largest curvature direction and the total curvature. Across CNNs, ResNets, vision transformers, LSTMs, and Mamba models, we observe that common zeroth-order optimizers naturally settle near the stability boundary predicted by our theory. Our results give researchers a clearer way to understand and tune gradient-free training, especially for memory-efficient fine-tuning of large models.