Pith. sign in

REVIEW 4 minor 16 references

Zeroth-Order Optimization at the Edge of Stability

T0 review · 0 major / 4 minor · reviewed 2026-07-12 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Zeroth-order optimizers train at a mean-square edge of stability set by the full Hessian spectrum, not just its top eigenvalue.

desk verdict Clean first exact mean-square stability theory for practical ZO methods, with matching full-batch EoS evidence that the governing quantity is the Hessian trace rather than λ_max. read the letter →

arxiv 2604.14669 v2 pith:ZS2SKAOO submitted 2026-04-16 cs.LG math.DSmath.OCstat.ML

Minhak Song , Liang Zhang , Bingcong Li , Niao He , Michael Muehlebach , Sewoong Oh This is my paper · ORCID
classification cs.LGmath.DSmath.OCstat.ML
keywords zeroth-orderoptimizationedgeofstabilitymean-squarelinearHessianspectrumtracetwo-pointestimatorZO-GDZO-Adam
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Zeroth-order (ZO) optimizers update parameters from function values alone, via random two-point probes. Their short-term stability cannot be read from the familiar first-order rule that depends only on the largest Hessian eigenvalue. This paper derives the exact step-size threshold that keeps the second-moment of the linearized ZO iterates bounded; that threshold is an explicit spectral equation involving every eigenvalue. Tractable bounds that use only the trace and the top eigenvalue follow at once. Full-batch experiments on CNNs, ResNets, ViTs and sequence models show that ZO-GD, ZO-GDM and ZO-Adam settle so that the theoretical threshold remains inside those bounds throughout training. Large step sizes therefore push ZO trajectories toward small-trace Hessians, an implicit bias distinct from the sharpness control seen in first-order training.

What carries the argument

A cone-preserving linear covariance operator with a rank-one global coupling term that evolves the second-moment blocks of the ZO iterates; its spectral radius is characterized by the Krein–Rutman theorem and yields the exact mean-square stability condition.

What would settle it

Train full-batch ZO-GD on a neural net and track Hessian trace and top eigenvalue: if the fixed threshold 2/η systematically leaves the interval [Tr(Ht), Tr(Ht)+2λ max(Ht)] for a sustained portion of training, the mean-square edge-of-stability claim fails.

Watch

Extended reading notes

Core claim

For the standard Gaussian two-point estimator the mean-square critical step size of ZO-GD, ZO-GDM and frozen ZO-Adam is the unique positive root of an explicit equation that involves the entire spectrum of the (preconditioned) Hessian; the same methods empirically stabilize so that this threshold stays inside the computable interval built from the Hessian trace and top eigenvalue.

Load-bearing premise

The exact thresholds are derived for the local quadratic Taylor model of the loss, and for ZO-Adam the frozen preconditioner is assumed to commute with the Hessian.

Editorial extensions

If this is right

  • Large ZO step sizes primarily regularize Hessian trace rather than top eigenvalue.
  • Increasing momentum shrinks the ZO mean-square stable region, the opposite of its effect on first-order momentum methods.
  • Practical ZO training can monitor only trace and top eigenvalue to stay near the stability boundary without computing the full spectrum.
  • The same covariance-operator framework extends immediately to forward differences, non-Gaussian directions and multi-query averages.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Mini-batch ZO-SGD should inherit a hybrid stability threshold that mixes estimator noise with sampling noise and may settle at still flatter trace values.
  • A central-flow description of ZO training could be obtained by replacing the FO sharpness flow with the mean-square spectral equation derived here.
  • Because ZO fine-tuning already reduces memory, the trace bias may offer a free generalization knob that FO memory-efficient methods do not share.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper derives exact mean-square linear stability conditions for ZO-GD, ZO-GDM, and frozen ZO-Adam under the standard two-point Gaussian estimator applied to the local quadratic model of the loss. Unlike FO methods, whose critical step size depends only on λ_max, the ZO mean-square critical step size is the unique positive root of an explicit spectral equation involving the full Hessian (or preconditioned Hessian) spectrum; tractable bounds depending only on Tr(H) and λ_max are also obtained. Empirically, full-batch ZO-GD, ZO-GDM, and ZO-Adam on CNN/ResNet/ViT (CIFAR-10 subset) and on LSTM/Mamba sorting tasks stabilize so that the predicted thresholds 2/η, 2(1-β)/η, and 2/η remain inside the corresponding [Tr, Tr+2λ_max]-type intervals throughout training, indicating a mean-square edge-of-stability regime that primarily regularizes the Hessian trace.

Significance. The work supplies a clean, FO-contrasting stability theory for the ZO estimators used in MeZO-style LLM fine-tuning, together with complete second-moment recursions, a cone-preserving covariance operator analyzed via Krein–Rutman (Theorem 4 / Appendix A), and matching tractable bounds that are directly plotted against independently estimated curvature. The empirical mean-square EoS observation across architectures, the opposite momentum dependence relative to FO-GDM, and the explicit link to trace regularization are new and practically relevant. Strengths include machine-checkable spectral characterizations, falsifiable threshold predictions with no free fit parameters, and supporting commutator measurements (Appendix D.3).

minor comments (4)
  1. [§4.2, Remark 2] In §4.2 / Remark 2 the commutativity assumption PH=HP is load-bearing for the exact spectral formula of frozen ZO-Adam; while Appendix D.3 shows the relative commutator drops below 0.05, a short forward pointer in the main text would help readers who skip the appendix.
  2. [Figure 1, §1] Figure 1 caption and the surrounding text state that the ZO-GD trace stabilizes 'slightly below 2/η'; the later theory (Eq. (5)) places the threshold inside [Tr, Tr+2λ_max]. Aligning the early narrative with the precise interval would avoid a minor inconsistency of language.
  3. [Appendix B] Appendix B sketches extensions to forward differences, non-Gaussian directions, and multi-query averages; a one-sentence pointer in the main text (e.g., after Theorem 1) would make these results more discoverable.
  4. [§5.2] The squared-loss / one-hot CIFAR-10 subset protocol is standard for EoS studies but should be flagged more prominently when claiming relevance to cross-entropy LLM fine-tuning.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: mean-square thresholds are derived from the covariance operator spectral radius under the linearized quadratic model, and empirical EoS plots overlay those fixed theoretical constants on independently estimated curvature.

full rationale

The central claims are obtained by constructing the second-moment recursion for the two-point ZO updates on the local quadratic (Definition 1), reducing it to a cone-preserving linear covariance operator T (Lemma 1 / Theorems 4–5), and characterizing ρ(T)<1 via Krein–Rutman, which yields the exact spectral equations of Theorems 1–3 and the tractable [Tr, Tr+2λ_max]-style bounds. Those bounds are then used only as fixed horizontal thresholds (2/η, 2(1−β)/η, etc.) against Hutchinson/power-iteration estimates of Tr(H_t) and λ_max(H_t) that are not fitted to the thresholds. FO baselines are taken from external literature (Cohen et al.). The commutativity assumption for frozen ZO-Adam is stated and empirically checked (Appendix D.3) rather than smuggled in as a uniqueness theorem. No free parameter is fitted to data and then re-presented as a prediction; no load-bearing uniqueness result is imported from overlapping authors; the derivation is self-contained under the stated linearized full-batch setting. Score 0 is therefore appropriate.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The central claims rest on standard dynamical-systems linearization, Gaussian moment calculations, and one technical commutativity hypothesis for the Adam case; no free parameters are fitted to produce the stability thresholds themselves. Empirical step sizes and momentum values are chosen by the experimenter but are not part of the theoretical statements.

free parameters (2)
  • smoothing parameter μ
    Fixed at the conventional value 10^{-3} for all main experiments; larger μ is shown to suppress curvature growth, but the theory is stated for the unsmoothed quadratic model.
  • step-size and momentum schedules used in figures
    Chosen by hand so that the predicted thresholds lie in a convenient numerical range; they do not enter the derivation of the critical-step-size formulae.
assumptions (4)
  • domain assumption Local quadratic Taylor approximation of the loss about a minimizer is sufficient to characterize short-term linear stability (Definition 1).
    Standard in the EoS literature; justified by classical Lyapunov linearization but leaves higher-order terms unanalyzed.
  • domain assumption Search directions are i.i.d. standard Gaussian (or, more generally, isotropic with finite fourth moments).
    Used to close the second-moment recursion via Isserlis’ theorem; Appendix B sketches extensions.
  • ad hoc to paper For frozen ZO-Adam, the preconditioner P and Hessian H commute (P H = H P).
    Required for simultaneous diagonalization and block-wise decoupling (Remark 2); empirically supported by relative commutator <0.05 after early training, but not proved.
  • standard math Krein–Rutman theorem applies to the cone-preserving covariance operator on the finite-dimensional product of positive-semidefinite 2×2 blocks.
    Invoked to guarantee a positive leading eigenpair; standard finite-dimensional corollary.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Zeroth-Order Optimization at the Edge of Stability." pith.science (2026). https://pith.science/paper/ZS2SKAOO

@misc{pith2026260414669,
  author       = {Pith},
  title        = {Pith review of: Zeroth-Order Optimization at the Edge of Stability},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZS2SKAOO}},
  note         = {Machine review of arXiv:2604.14669}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2604.14669 by the authors.

Figure 1
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 η on a CNN for CIFAR-10. For GD, the largest eigenvalue of the Hessian λmaxpHtq stabilizes near 2{η. For ZO-GD, the trace of the Hessian TrpHtq instead stabilizes slightly below 2{η. els (LLMs) with competitive accuracy while substantially reducing m… view at source ↗
Figure 2
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, var… view at source ↗
Figure 3
Figure 3. Catapult dynamics in ZO-GD. We train ZO-GD on CNN and increase the step size midway through training (from η1 to η2 and then to η3). Top: the training loss exhibits a pronounced spike after each step size increase, consistent with catapult dynam￾ics. Bottom: the Hessian trace TrpHtq drops sharply during the catapult phase and then rises again, re-equilibrating near the new stability threshold 2{η. 5.3. Main experime… view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: Effect of the smoothing parameter µ. We train ZO-GD on a CNN with a fixed step size and vary the smoothing parameter µ in the two-point estimator. For moderate and small smoothing (µ ď 10´3 ), ZO-GD operates at the mean-square EoS. For larger smoothing (µ ě 3 ˆ 10´3 ),…
Figure 5
Figure 5. Figure 5: Effect of batch size in mini-batch ZO-SGD. We train mini-batch ZO-SGD on a CNN with a fixed step size and vary the batch size. Compared to full-batch ZO-GD, mini-batch ZO-SGD trains in a lower-curvature regime with a smaller Hessian trace. iterate, so the dynamics beco…
Figure 6
Figure 6. Figure 6: Mean-square EoS for full-batch ZO methods on ResNet. We train full-batch ZO-GD, ZO-GDM, and ZO-Adam on ResNet20 for CIFAR-10 and track the corresponding mean-square stability bounds and threshold in Section 5.1. 0 100000 200000 300000 400000 500000 Iteration 0 2000 400…
Figure 7
Figure 7. Figure 7: Mean-square EoS for full-batch ZO methods on Vision Transformer. We train full-batch ZO-GD, ZO-GDM, and ZO-Adam on a Vision Transformer for CIFAR-10 and track the corresponding mean-square stability bounds and threshold in Section 5.1. second moments, this extra accumu…
Figure 8
Figure 8. Figure 8: Mean-square EoS on a synthetic sorting task with an LSTM. On the synthetic sorting task described in Karpathy (2020), using the setup adopted by Cohen et al. (2025, Appendix B.3), we train full-batch ZO-GD, ZO-GDM, and ZO-Adam and track the corresponding mean-square st…
Figure 9
Figure 9. Figure 9: Mean-square EoS on a synthetic sorting task with Mamba. On the synthetic sorting task described in Karpathy (2020), using the setup adopted by Cohen et al. (2025, Appendix B.3), we train full-batch ZO-GD, ZO-GDM, and ZO-Adam and track the corresponding mean-square stab…
Figure 10
Figure 10. Figure 10: ZO-Adam sweep over β1 and η. Full-batch ZO-Adam on a CNN trained on CIFAR-10 with β1 P t0.1, 0.5, 0.9u (left to right) and multiple step sizes η per setting. Top: training loss. Middle: preconditioned curvature statistics TrpP ´1 t Htq and TrpP ´1 t Htq ` 2 1`β1 λmaxp…
Figure 11
Figure 11. Figure 11: CNN: same experiments as [PITH_FULL_IMAGE:figures/full_fig_p037_11.png]
Figure 12
Figure 12. Figure 12: ResNet: same experiments as [PITH_FULL_IMAGE:figures/full_fig_p037_12.png]
Figure 13
Figure 13. Figure 13: Vision Transformer: same experiments as [PITH_FULL_IMAGE:figures/full_fig_p038_13.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 4 linked inside Pith

  1. [1]

    and Beneventano, P

    Andreyev, A. and Beneventano, P. Edge of stochastic sta- bility: Revisiting the edge of stability for SGD.arXiv preprint arXiv:2412.20553,

    arXiv

  2. [2]

    E., et al

    Cohen, J., Ghorbani, B., Krishnan, S., Agarwal, N., Medap- ati, S., Badura, M., Suo, D., Cardoze, D., Nado, Z., Dahl, G. E., et al. Adaptive gradient methods at the edge of stability.arXiv preprint arXiv:2207.14484,

    arXiv

  3. [3]

    The large learning rate phase of deep learning: the catapult mechanism.arXiv preprint arXiv:2003.02218,

    Lewkowycz, A., Bahri, Y ., Dyer, E., Sohl-Dickstein, J., and Gur-Ari, G. The large learning rate phase of deep learning: the catapult mechanism.arXiv preprint arXiv:2003.02218,

    arXiv 2003

  4. [4]

    Evolution strategies as a scalable alternative to rein- forcement learning.arXiv preprint arXiv:1703.03864,

    Salimans, T., Ho, J., Chen, X., Sidor, S., and Sutskever, I. Evolution strategies as a scalable alternative to rein- forcement learning.arXiv preprint arXiv:1703.03864,

    arXiv

  5. [5]

    Type-ii saddles and probabilistic stability of stochastic gradient descent

    Ziyin, L., Li, B., Galanti, T., and Ueda, M. Type-ii saddles and probabilistic stability of stochastic gradient descent. arXiv preprint arXiv:2303.13093,

    arXiv

  6. [6]

    Applyings Σp¨qand cancellings ‹ ą0gives r“˜η 2 sΣ ˆ´ Id´ 1 r M ¯´1 sQΣ ˙

    The bounds ρp 1 r Miq ă1 imply ρp 1 r Mq ă1 , so Id´ 1 r M is invertible by the Neumann series and W ‹ “ ˜η2s‹ r ´ Id´ 1 r M ¯´1 sQΣ. Applyings Σp¨qand cancellings ‹ ą0gives r“˜η 2 sΣ ˆ´ Id´ 1 r M ¯´1 sQΣ ˙ . Using the Neumann series andră1, ˜η2 sΣ ˆ´ Id´ 1 r M ¯´1 sQΣ ˙ ě˜η2 sΣ ` pId´Mq ´1 sQΣ ˘ “˜η2 dÿ i“1 ˜λ2 i γi “S adampη, β1q. HenceS adampη, β1q ďră...

    1948

  7. [7]

    Experimental details In this section, we provide additional experimental details

    33 Zeroth-Order Optimization at the Edge of Stability C. Experimental details In this section, we provide additional experimental details. Our dataset construction, preprocessing, and model architectures follow the setup of Cohen et al. (2025). Dataset.We train on a subset of CIFAR-10 consisting of 1,000 training examples drawn from the first four CIFAR-1...

    2025

  8. [8]

    • Vision Transformer (ViT).A Vision Transformer (Dosovitskiy et al.,

    with GeLU activations and GroupNorm (Wu & He, 2018). • Vision Transformer (ViT).A Vision Transformer (Dosovitskiy et al.,

    2018

Show all 16 references
  1. [9]

    Top eigenvalue and trace estimation.During training, we log curvature statistics every 1,000 iterations

    with depth 3, embedding dimension 64, 8 attention heads, MLP dimension256, and patch size4. Top eigenvalue and trace estimation.During training, we log curvature statistics every 1,000 iterations. Specifically, we compute the largest eigenvalue and trace of the Hessian (or the...

    2020

  2. [10]

    34 Zeroth-Order Optimization at the Edge of Stability 0 100000 200000 300000 400000 500000 Iteration 0 1000 2000 3000 4000 5000Hessian Trace 2/ = 3000 2/ = 2000 2/ = 1000 ZO-GD (varying ) = 2/3000 : Tr(Ht) = 2/2000 : Tr(Ht) = 2/1000 : Tr(Ht) = 2/3000 : Tr(Ht) + 2 max(Ht) = 2/2...

    2000

  3. [11]

    = 2/2000 : Tr( ) + 2 max( )/(1 +

    2000

  4. [12]

    (2025, Appendix B.3), we train full-batch ZO-GD, ZO-GDM, and ZO-Adam and track the corresponding mean-square stability quantities

    Figure 8.Mean-square EoS on a synthetic sorting task with an LSTM.On the synthetic sorting task described in Karpathy (2020), using the setup adopted by Cohen et al. (2025, Appendix B.3), we train full-batch ZO-GD, ZO-GDM, and ZO-Adam and track the corresponding mean-square st...

    2020

  5. [13]

    (2025, Appendix B.3), we train full-batch ZO-GD, ZO-GDM, and ZO-Adam and track the corresponding mean-square stability quantities

    Figure 9.Mean-square EoS on a synthetic sorting task with Mamba.On the synthetic sorting task described in Karpathy (2020), using the setup adopted by Cohen et al. (2025, Appendix B.3), we train full-batch ZO-GD, ZO-GDM, and ZO-Adam and track the corresponding mean-square stab...

    2020

  6. [14]

    Appendix D.3)

    0 100000 200000 300000 400000 500000 Iteration 0.00 0.20 0.40 0.60 0.80 1.00 0.05Relative Commutator Ratio = 2/40000 = 2/20000 = 2/10000 0 100000 200000 300000 400000 500000 Iteration 0.00 0.20 0.40 0.60 0.80 1.00 0.05Relative Commutator Ratio = 2/40000 = 2/20000 = 2/10000 0 1...

  7. [15]

    Figure 11.CNN: same experiments as Figure 2, with training loss.Top:training loss.Bottom:the stability-band plots from Figure 2 for ZO-GD (left), ZO-GDM (middle), and ZO-Adam (right). 0.0 0.1 0.2 0.3 0.4 0.5Training Loss ZO-GD (varying ) = 2/5000 = 2/4000 = 2/3000 0.0 0.1 0.2 ...

    2000

  8. [16]

    Figure 12.ResNet: same experiments as Figure 6, with training loss.Top:training loss.Bottom:the stability-band plots from Figure 6 for ZO-GD (left), ZO-GDM (middle), and ZO-Adam (right). 37 Zeroth-Order Optimization at the Edge of Stability 0.0 0.1 0.2 0.3 0.4 0.5Training Loss...

    2000

Pith tools

Reviewed July 12, 2026 · model on record in the stance chip above.