Zeroth-Order Optimization at the Edge of Stability

• URL: http://arxiv.org/abs/2604.14669v1
• Date: Thu, 16 Apr 2026 06:23:18 GMT
• Title: Zeroth-Order Optimization at the Edge of Stability
• Abstract summary: We provide an explicit step size condition that captures the (mean-square) linear stability of a family of Zeroth-order (ZO) methods.<n>Our results highlight an implicit regularization effect specific to ZO methods, where large step sizes primarily regularize the Hessian trace.
• Score: 59.54782674222443
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• The Road Taken: The Role of Optimizers at the Edge of Stability [53.81268610971847]
  edge of stability refers to a phenomenon in deep learning where the Hessian eigenvalues of the loss remain stable above a threshold that the classical descent predicts to be unstable.<n>Previous works formulate the edge of stability with respect to the maximum Hessian eigenvalue and the learning rate.<n>We observe that many first-order methods, including gradient descent, significantly violate the stability bound predicted by these theories by a factor as large as $times 21.1$.
  arXiv  Detail & Related papers  (2026-08-19T01:03:34Z)
• Statistical Inference for Stochastic Gradient Descent Beyond Finite Variance [10.36372217426986]
  gradient descent (SGD) is a foundational algorithm for large-scale statistical learning and optimization.<n>We develop an efficient, model-agnostic methodology for constructing confidence regions from SGD trajectories.
  arXiv  Detail & Related papers  (2026-05-25T16:18:39Z)
• Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimization [71.33048115652474]
  Bilevel optimization (SBO) has been integrated into many machine learning paradigms recently.<n>In this paper, we provide a systematic analysis of bilevel optimization methods.<n>Results do not require re-reading and are applicable to more general objective functions.
  arXiv  Detail & Related papers  (2026-04-05T12:12:58Z)
• Efficient Inference after Directionally Stable Adaptive Experiments [47.32051320630248]
  We study inference on pathwise differentiable targets after adaptive data collection, such as a bandit.<n>We introduce a novel target-specific condition, directional stability, which is strictly weaker than previously imposed target-aparametric stability conditions.
  arXiv  Detail & Related papers  (2026-02-25T01:09:18Z)
• On the Benefits of Accelerated Optimization in Robust and Private Estimation [2.209921757303168]
  We study the advantages of accelerated gradient methods, specifically based on the Frank-Wolfe method and projected descent.<n>For the Frank-Wolfe method, our technique is based on a tailored iteration learning rate and a uniform lower bound on the gradient of the $ell$-norm over the constraint set.<n>For accelerating projected descent, we use the popular variant based on Nesterov's momentum.
  arXiv  Detail & Related papers  (2025-06-03T16:26:30Z)
• Exact Mean Square Linear Stability Analysis for SGD [28.65663421598186]
  We provide an explicit condition on the step size that is both necessary and sufficient for linear stability of gradient descent (SGD) We show that SGD's stability threshold is equivalent to that of a mixture process which takes in each a full batch gradient step w.p. $1-p$, and a single sample gradient step w.p. $p$.
  arXiv  Detail & Related papers  (2023-06-13T15:29:23Z)
• Log Barriers for Safe Black-box Optimization with Application to Safe Reinforcement Learning [72.97229770329214]
  We introduce a general approach for seeking high dimensional non-linear optimization problems in which maintaining safety during learning is crucial. Our approach called LBSGD is based on applying a logarithmic barrier approximation with a carefully chosen step size. We demonstrate the effectiveness of our approach on minimizing violation in policy tasks in safe reinforcement learning.
  arXiv  Detail & Related papers  (2022-07-21T11:14:47Z)
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent [55.85456985750134]
  We introduce a new stability measure called on-average model stability, for which we develop novel bounds controlled by the risks of SGD iterates. This yields generalization bounds depending on the behavior of the best model, and leads to the first-ever-known fast bounds in the low-noise setting. To our best knowledge, this gives the firstever-known stability and generalization for SGD with even non-differentiable loss functions.
  arXiv  Detail & Related papers  (2020-06-15T06:30:19Z)
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
  We provide sharp upper and lower bounds for several forms of gradient descent (SGD) on arbitrary Lipschitz nonsmooth convex losses. Our bounds allow us to derive a new algorithm for differentially private nonsmooth convex optimization with optimal excess population risk.
  arXiv  Detail & Related papers  (2020-06-12T02:45:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.