acceptodds
Under review as a conference paper at ICLR 2027

On Adaptivity in Zeroth-Order Optimization

Abstract

We investigate the effectiveness of adaptive zeroth-order (ZO) optimization for memory-constrained fine-tuning of large language models (LLMs). Contrary to prior claims, we show that adaptive ZO methods such as ZO-Adam provide no performance or convergence advantage over well-tuned ZO-SGD, while incurring significant memory overhead due to optimizer state. We provide theoretical justification for why Adam-like adaptivity is less effective in large-scale ZO settings, and confirm this through both synthetic and LLM fine-tuning experiments. Importantly, we show empirically that adaptivity can still provide a practical benefit in ZO optimization by improving robustness to step-size selection. To retain this robustness without incurring the memory cost of optimizer state, we propose MEAZO, a Memory-Efficient Adaptive ZO optimizer that tracks only a single scalar to adapt the global step size. We support our method with theoretical convergence guarantees under standard smoothness assumptions. Experiments on synthetic quadratic problems, multiple LLM families, and diverse fine-tuning tasks demonstrate that MEAZO performs comparably to competing methods while matching the robustness gains of ZO-Adam over ZO-SGD, without additional memory or latency overhead.

Primary area:
optimization
Keywords:
zeroth order, adaptive optimization, LLM fine-tuning

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_ax4nOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper addresses the practical problem of memory-efficient LLM fine-tuning with zeroth-order (ZO) methods. Adam-type coordinate-wise adaptivity is well established in the first-order setting, while struggling to reach advantage under ZO setup. The authors give a theory-grounded explanation of why this idea is problematic in the ZO setting and confirm it in controlled experiments. This motivates the proposed scheme, MEAZO. It keeps the effective behavior of ZO-Adam and its robustness to the step-size choice, but stores a single scalar and has no memory overhead compared with ZO-SGD.

Critical strengths

In my view, the main contribution of the paper is a transparent, theory-grounded and empirically supported view of coordinate-wise adaptivity in the ZO setting. Proposition 3.1 explains exactly why coordinate-wise adaptivity fails here: the term 1q∥∇f(x)∥2\frac{1}{q}\Vert\nabla f(x)\Vert^2 is shared by all coordinates and dominates the second moment when q≪dq \ll d. The experiments that target this effect confirm it (Figure 2a, Table 8).

The second strength is the scope of the experiments. The paper covers several models and tasks, LoRA and full fine-tuning, and dense step-size sweeps with three seeds per step size to study robustness.

Critical weaknesses

W1. The paper does not compare MEAZO with other techniques that improve robustness to the step-size choice, such as normalized ZO-SGD or gradient clipping. Both have no memory overhead. Also, the experiments do not show a concrete practical gain in tuning time (e.g. n% less time to find appropriate lr in average), the robustness score in Table 2 does not answer this question directly.

W2. Theory. Assumption 5.4 is common in the analysis of adaptive methods, but it is restrictive and unrealistic. It must hold for all perturbation directions, including the one aligned with the gradient, so it effectively bounds ∥∇f(xt)∥2\Vert\nabla f(x_t)\Vert_2 along the trajectory. It does not hold even for the quadratic objectives used in the paper unless the iterates stay bounded. Under this assumption ZO-SGD also has a bound for any η>0\eta > 0. The descent Lemma E.2 with ∥Gt∥2≤d2B2\Vert G_t\Vert^2 \le d^2B^2 and η=η0/T\eta = \eta_0/\sqrt{T} gives (Δ/η0+Lη0d2B2/2)/T(\Delta/\eta_0 + L\eta_0 d^2B^2/2)/\sqrt{T}, and O(d/T)O(d/\sqrt{T}) for a tuned η0\eta_0. Therefore, the assumption does not allow the theory to show any effect of stability gain from adaptivity.

In addition, two places in the analysis make the MEAZO bound worse than this. First, in the descent term the adaptive step is lower-bounded by the worst case 1/Rd1/R_d with Rd=ζ+dBR_d = \sqrt{\zeta} + dB (eq. (88)). Second, decoupling the denominator from the current sample (Lemma G.9) produces the term with 8Rd2/1−β8R_d^2/\sqrt{1-\beta} in (10), which does not depend on η\eta and cannot be reduced by tuning. As a result, Corollary 5.6 gives O~(d2/T)\tilde O(d^2/\sqrt{T}), a factor dd worse than tuned ZO-SGD under the same assumptions.

Minor issues:

  • The paper often switches between perturbations sampled from the unit sphere and from the Gaussian distribution. In particular, the guarantees of Theorem 5.5 are given for the uniform distribution on the sphere, and Proposition 3.1 is stated for Gaussian perturbations, experiments use Gaussian perturbations as well. For clarity of presentation, this requires a separate discussion, or all experiments and statements should use one perturbation distribution.
  • In Algorithm 1, Line 10, xtx_t and xt−1x_{t-1} should be xt+1x_{t+1} and xtx_t, since the update uses the projected gradients at xtx_t (Lines 6 and 10). The analysis uses the correct indices.
Questions for authors

Q1. Regarding W1, could the authors add gradient clipping and normalized ZO-SGD to the robustness comparison? Could the authors measure the concrete gain in tuning budget from using MEAZO compared with MeZO?

Q2. Could the authors show or derive a theoretical gain from adaptivity, or point out the fundamental difficulties in obtaining it?

4 comments

We thank reviewer ax4n for their careful review of our submission and for acknowledging our controbutions are both "theory-grounded" and backed up with a strong "scope of experiments".

W1.a / Q1 "Comparison to other techniques improving robustness"

As requested, we conducted additional experiments with ZO-NSGD and ZO-ClipSGD alongside other relevant baselines (full details in the general comment).

  • ZO-NSGD is a special case of MEAZO, with β=0\beta = 0 and ζ=0\zeta = 0. The experiments show that he two methods reach similar accuracy, but MEAZO is significantly more robust. This shows that the robustness gain comes from averaging across steps (β>0\beta > 0).

  • ZO-ClipSGD takes a ZO-SGD step and clips it when ∣gt∣>c|g_t| > c. We calibrated cc from a short unclipped ZO-SGD run on the same task: c=4c = 4 is the median of ∣gt∣|g_t| (about 50% of steps clipped) and c=10c = 10 its 90th percentile (about 10%). Both improve robustness only slightly over ZO-SGD, whereas MEAZO is significantly more robust. All baselines achieve similar accuracies.


W1.b "Practical time gain"

We agree that Table 2 does not directly quantify tuning time. Using the same random-search procedure done for the CPE metric (see general comment G.5), we estimated the expected number of trials needed to find an acceptable learning rate for each task/method, as follows:

  • A trial succeeds if its best validation loss is at most C=1.1LC=1.1L, where LL is the best validation loss.

  • We model independent random search from the shared log-uniform prior [10−6,10−2][10^{-6}, 10^{-2}]. To account for the uneven spacing of our existing sweeps, each measured learning rate receives the prior probability mass of its nearest-neighbour cell in log space, with boundaries at the midpoints between adjacent measured log learning rates. Endpoint cells extend to the prior boundaries. This mass is divided equally among the available seeds. If wm,iw_{m,i} denotes the resulting weight of run ii, the estimated single-trial success probability is

\hat p_{m}=\sum_i w_{m,i}\mathbf 1\left\\{\ell_{m,i}\leq C_t\right\\}, \quad \sum_i w_{m,i}=1.

  • For independent trials with success probability pmp_m, the number of trials until the first success follows a geometric distribution, giving

E[Nm]=1pm.\mathbb E[N_{m}]=\frac{1}{p_{m}}.

  • All trials use a budget of 10,000 training steps, and our benchmarks show comparable per-step runtimes. Under the equal-trial-cost approximation, expected sequential tuning time is therefore proportional to 1/pm1/p_{m}. We calculate MEAZO's percentage reduction relative to ZO-SGD separately for each task:
1-\frac{1/\hat p_{\mathrm{MEAZO}}}{1/\widehat p_{\mathrm{SGD}}}\right) =100\left(1-\frac{\hat p_{\mathrm{SGD}}}{\widehat p_{\mathrm{MEAZO}}}\right).$$ The resulting estimated reductions are: | Dataset | Llama-3.2 1B | Qwen-3 0.6B | Qwen-3 8B | |---|---:|---:|---:| | XSum | -4.9% | 7.8% | 22.6% | | SST-2 | -2.2% | 38.9% | 34.4% | | SQuAD | 21.3% | 30.3% | 33.4% | Positive values indicate less expected tuning time with MEAZO; negative values indicate more. MEAZO improves the estimated tuning time in **seven of nine settings**, with a **20.2% mean per-setting reduction** under this protocol.

W2. "No visible gain from adaptivity in the convergence rate"

We thank Reviewer ax4n for carefully reading the details of our assumptions and convergence proof.

  • Our general comment G.1 explains that our convergence analysis of MEAZO was to check the validity of the algorithm, not to improve on baselines. Although our rate for uniform perturbations has worse dimension dependence, it matches the O(1/T)O(1/\sqrt{T}) rate of ZO-SGD.
  • We agree with Rev. ax4n that the bounded projected gradient Assumption 5.4 is not realistic, but it is analoguous to the bounded stochastic gradient assumption commonly made in the optimization community (cf general comment G.1). As noticed by Rev. zyf6, W.2b, Assumption 5.4, which implies gt2≤d2B2g_t^2 \leq d^2 B^2, is the reason of the pessimistic dimension dependence in our rate.
  • Following the suggestion of Rev. n8y5, we extended our proof to Gaussian perturbations and got a rate that recovers the O(d/T)O(\sqrt{d}/\sqrt{T}) rate of ZO-SGD. We achieve this improvement via the standard bounded stochastic gradient and a sharper control of Gaussian moments and adaptive denominator control via concentration inequalities (cf App. I).

Minor issues

We thank Reviewer ax4n for their suggestions. We have clarified the perturbations we used and corrected the typo in Algo. 1.


Q2. Improvement due to adaptivity vs ZO-SGD

We explain in our response to W2.c of Rev. zfy6, that the benefits of adaptivity relies in the robustness w.r.t. the problem's constants LL and BB. Unlike the standard analysis of ZO-SGD of Ghadimi and Lan (2013), our schedules in Cor. 5.6 for η\eta, ε2\varepsilon^2 and β\beta do not depend on the smoothness constant LL or the uniform bound of the gradient BB.

Thank you again for your review. If your main concerns are now resolved, we would appreciate if you could consider revising your score. Please let us know if any significant concerns remain.

Thank you for your detailed responses. They have increased my confidence in a positive evaluation of the paper.

Reviewer_Tz53OpenReview ↗
Rating
3(+2)
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper explores adaptive approaches in zeroth order optimization. Authors claim the improvements of adaptive methods, e.g. ZO-Adam, is negligible compared to ZO-SGD if the latter is well-tuned. The paper proposes an explanation to this experimental observation in directional homogeneity. The random direction of ZO optimization creates a heavy bias in coordinate-wise gradient, which leads to the second momentum of adaptive methods being approximately constant. Thus, adaptivity provides little improvement while creating a significant memory overhead, which clashes with the purposes of the ZO paradigm. However, the authors argue that the strength of adaptivity is not the improvement in metrics, but rather convergence stability. The paper introduces Robustness score as a combined score of all runs with stepsizes in a tight logarithmic grid. Adaptive ZO methods are shown to have higher Robustness value, meaning, more of the initial stepsizes yield a competitive solution. Authors further propose MEAZO - a new method, which only uses a single scalar value to employ adaptivity to the updates. Theory states the convergence bound for MEAZO, which matches the standard ZO rates

Critical strengths
  1. The paper highlights the misconception about the purpose of adaptivity in ZO optimization and attempts to explain its origins.
  2. The proposed MEAZO achieves the metrics of ZO-Adam and retains its robustness score, while reducing the memory footprint. From theoretical point of view, convergence matches the classic ZO rates up to logarithmic factor, and the proof seems to be correct.
  3. Experimental section is comprehensive: the validation spans across various architectures and tasks. The experiments are well tuned and averaged over 3 seeds.
Critical weaknesses
  1. One of the main contributions of the paper is the low memory footprint of MEAZO. However, other memory-efficient approaches are absent in the baselines, e.g. ZO-SignSGD [2], LOZO [3], Sparse-MeZO [4] - all from A* conferences . The comparison of the approaches in terms of convergence, space usage and robustness is crucial to ensure the significance of MEAZO. The paper presents a comparison to FZOO, yet it is limited. As both algorithms pose as memory-efficient approaches, it is important to provide a memory usage analysis.

  2. The key feature of MEAZO is normalization of the step. However, close techniques are present in the literature. Notably, ZO-NSGD [5] is a close competitor. The discussion of their differences is necessary. Moreover, the introduced Robustness Score is not a novel idea, and prior studies (for example, see [6], [7]) proposed similar metrics of robustness to hyperparameter choice. These raise a concern about the novelty of the paper, as its key parts have a close resemblance present in the literature. The discussion of MEAZO unique results and distinctions is missing.

  3. Proposition 3.1 is provided in the limit form as ε→0\varepsilon \rightarrow 0. However, in practice epsilon does not approach zero, especially in the stochastic setting under consideration. It is important to estimate the approximation error of the equation for finite ε\varepsilon.

  4. In theoretical analysis, the target function is considered stochastic. Moreover, for a fixed sample ξ\xi, function f(⋅,ξ)f(\cdot, \xi) is assumed to be LL-smooth and BB-Lipschitz (equivalent to the bounded ZO-gradient approximation). These are stricter than those adopted in the foundational works [1]. The papers explicitly study the trade-off of epsilon, while Theorem 5.5 holds for any arbitrary small ε\varepsilon. The extension of the proof should be technical and not challenging, while this would strengthen the result.

  5. The smoothing parameter of ZO-gradients ε\varepsilon is an important hyperparameter in practice and affects the convergence. The authors state the constant choice of ε\varepsilon=1e-6, but it is not motivated or explained


References:

[1] Nesterov, Yurii, and Vladimir Spokoiny. "Random gradient-free minimization of convex functions." Foundations of Computational Mathematics 17.2 (2017): 527-566.

[2] Liu, Sijia, et al. "signSGD via zeroth-order oracle." International conference on learning representations. 2019.

[3] Chen, Yiming, et al. "Enhancing zeroth-order fine-tuning for language models with low-rank structures." International Conference on Learning Representations. Vol. 2025. 2025.

[4] Liu, Yong, et al. "Sparse mezo: Less parameters for better performance in zeroth-order llm fine-tuning." Advances in Neural Information Processing Systems 38 (2026): 21139-21169.

[5] Lobanov, Aleksandr, and Alexander Gasnikov. "Power of generalized smoothness in stochastic convex optimization: First-and zero-order algorithms." arXiv preprint arXiv:2501.18198 (2025).

[6] McCoppin, Ryan, et al. "Evaluating Adversarial Robustness with Expected Viable Performance." 2023 International Conference on Machine Learning and Applications (ICMLA). IEEE, 2023.

[7] Aiyappa, Rachith, et al. "Implicit degree bias in the link prediction task." arXiv preprint arXiv:2405.14985 (2024).

Questions for authors
  1. How does the choice of epsilon affect convergence for both MEAZO and the baselines?

  2. How Proposition 3.1 can be stated with arbitrary epsilon? What is the approximation error?

  3. Could you provide analysis for Theorem 5.5 in the case when q>1q>1< i.e. where there is a trade-off on the choice of ε\varepsilon, and ε→0\varepsilon\to0 is not appropriate tuning.

9 comments

We thank reviewer Tz53 for their detailed review. We appreciate that they recognize the paper's broader contribution beyond MEAZO, namely clarifying the misconception about the purpose of adaptivity in ZO optimization. We also appreciate that they checked our convergence proof and found it correct, and that they found our experiments comprehensive and well tuned. We believe the concerns raised below are concrete and addressable, and we answer each of them in turn, with new experiments where needed.

W1. Absent Baselines

Memory. We would first like to clarify that our main contribution is about what adaptivity does and does not provide in ZO optimization (C1–C3): no gain in performance or convergence over well-tuned ZO-SGD, but a gain in robustness to the step size. MEAZO's memory claim is therefore relative to per-coordinate adaptive ZO methods: MEAZO gets the robustness of ZO-Adam at the memory cost of ZO-SGD.

New Results. The methods suggested by the reviewer are variants of ZO-SGD (apart from LOZO) that change the gradient estimator, and they already have the memory footprint of MeZO, so MEAZO cannot be expected to save memory relative to them. They are also orthogonal to MEAZO, since they change which direction is estimated, while MEAZO changes how the step is scaled, so they could be combined with it. Still, we agree that comparing against them is informative, which is why we conducted thorough comparison swith Sparse-MeZO, ZO-SignSGD, ZO-NSGD, and ZO-ClipSGD. In fact we even combine Sparse-MeZO with MEAZO to obtain Sparse-MEAZO, an even more robust method, highlighting that these techniques are indeed orthogonal. For more details see the general comment G.4.

LOZO. This method is a non-adaptive variant of ZO-SGD that uses low-rank perturbations; LOZO-M adds a low-rank momentum. Its memory use is slightly below MeZO's (2.83 GB vs. 3.00 GB on RoBERTa-large, their Table 1). The authors leave combining LOZO with Adam as an open problem. MEAZO is a natural fit here, since it adds only one scalar of optimizer state. Unfortunately, we could not run this combination in the rebuttal period and leave it to future work.

FZOO. We respectfully disagree that our comparison (Table 3 & App. D.8) with FZOO is limited. We not only compare against FZOO as published, but also introduced MEAZO-Fwd, which uses exactly FZOO's estimator (Rademacher perturbations, one-sided differences with a shared baseline, and the same q+1q+1 forward passes per step), so the two methods differ only in how the step is normalized. Table 3 compares them for q sweep q∈{1,2,8}q \in \{1, 2, 8\}, with full step-size sweeps. FZOO is undefined at q=1q = 1 and collapses to near-chance accuracy at q=2q = 2 (49.8%), while MEAZO-Fwd reaches 88.6% and 89.1% at q=1q = 1 and q=2q = 2. At q=8q = 8, the two methods are close in accuracy (89.6% vs 90.7%) and robustness (1.71 vs 1.73). Regarding memory, neither method stores per-coordinate state, so at equal qq the two have the same footprint.


W2-a. Comparison with ZO-NSGD

ZO-NSGD is a special case of MEAZO, with β=0\beta = 0 and ζ=0\zeta = 0. We have added it to our comparison, for now only on Llama-3.2 1B SST-2 because of limited time (full details in the general comment G.4). In short, the two methods reach similar accuracy, but MEAZO is significantly more robust. This shows that the robustness gain comes from averaging across steps (β>0\beta > 0).

W2-b. Robustness Score

We agree that measuring robustness to hyperparameters is not new, and we do not claim the score as a contribution (it is not among C1–C4). We use AτA_\tau only to quantify our finding C3: adaptivity makes ZO methods more robust to the choice of step size, without improving final performance.

That said, we do not think [6] and [7] are close to what we do. [6] evaluates how robust a trained classifier is to adversarial input perturbations, by integrating accuracy over the perturbation budgets where it stays above a viability threshold. [7] shows that AUC-based evaluation in link prediction is biased by node degree. Neither looks at how sensitive an optimizer is to its hyperparameters.

The closest prior work on benchmarking optimizer robustness to hyperparameters is Sivaprasad et al. (2020), "Optimizer Benchmarking Needs to Account for Hyperparameter Tuning". We adopted their CPE metric, which measures the expected regret of a random step-size search on a small budget, and computed it from our existing LoRA sweeps (general comment G.5). In 7 of 9 settings, both adaptive methods have lower regret than ZO-SGD, in line with AτA_\tau. This independently proposed metric thus supports the same conclusion, and agrees with AτA_\tau on where the effect is weaker. We will add these results to the revised paper.

W3. Proposition 3.1 with finite ε\varepsilon

Intuitively, a small but finite ε\varepsilon cannot be expected it to create the per-coordinate structure that Adam's second moment would need. The upper bound on ∣r(u)∣=∣Δfε(x;u)−∇f(x)⊤u∣≤ε2L∥u∥2|r(\mathbf{u})| = |\Delta f_\varepsilon(\mathbf{x};\mathbf{u}) - \nabla f(\mathbf{x})^\top \mathbf{u}| \leq \varepsilon^2L \|\mathbf{u}\|^2 (used by Prop 3.1) due to the smoothness of ff along the random direction u\mathbf{u} does not single out any particular coordinate.

Empirially, our LLM experiments (Appendix D.1) support this. For Llama-3.2 1B fine-tuned on XSum with ε=10−6\varepsilon = 10^{-6}, ZO-Adam's second moment after 10k steps is nearly uniform across d≈1.7d \approx 1.7M coordinates (Table 8). FO-Adam's spans 15 orders of magnitude. This is the same collapse that Proposition 3.1 predicts in the limit.

For completeness, we also derived finite-ε\varepsilon versions of Proposition 3.1 and of its uniform counterpart, which we added to the revised paper as Appendix F.3 (Propositions F.3 and F.4, highlighted in cyan). For Gaussian perturbations, write g=∇f(x)\mathbf{g} = \nabla f(\mathbf{x}) and let Pk=1q(∥g∥2+gk2)+gk2P_k = \frac{1}{q}(\|\mathbf{g}\|^2 + g_k^2) + g_k^2 be the ε→0\varepsilon \to 0 value from Proposition 3.1. Then, for every ε>0\varepsilon > 0 and every coordinate kk,

∥Eu[∇^f(x)2]k−Pk∥≤eˉ(ε)\left \| E_{\mathbf{u}}[\hat{\nabla} f(\mathbf{x})^2]_k - P_k \right \| \le \bar{e}(\varepsilon) where \bar{e}(\varepsilon) = \frac{1}{q} \tau_2\big(2\sqrt{3}\|\mathbf{g}\| + \tau_2\big) + \frac{q-1}{q} \tau_1\big �0�,

with τ1=Lε22/π (d+1)\tau_1 = \frac{L\varepsilon}{2}\sqrt{2/\pi}\,(d+1) and τ2=Lε2(d+2)(d+4)\tau_2 = \frac{L\varepsilon}{2}\sqrt{(d+2)(d+4)}, both O(Lεd)O(L\varepsilon d). The uniform case has the same form, with τ1=dd+1Lε\tau_1 = \frac{d}{d+1}L\varepsilon and τ2=Lεd2\tau_2 = \frac{L\varepsilon\sqrt{d}}{2}. The bound eˉ(ε)\bar{e}(\varepsilon) is the same for every coordinate kk, so this makes the intuition above precise. Dividing it by the isotropic term 1q∥g∥2\frac{1}{q}\|\mathbf{g}\|^2, the relative error is at most

eˉ(ε)1q∥g∥2=τ2∥g∥(23+τ2∥g∥)+(q−1) τ1∥g∥(2+τ1∥g∥).\frac{\bar{e}(\varepsilon)}{\frac{1}{q}\|\mathbf{g}\|^2} = \frac{\tau_2}{\|\mathbf{g}\|}\Big(2\sqrt{3} + \frac{\tau_2}{\|\mathbf{g}\|}\Big) + (q-1)\,\frac{\tau_1}{\|\mathbf{g}\|}\Big(2 + \frac{\tau_1}{\|\mathbf{g}\|}\Big).

The conclusion of Proposition 3.1 therefore holds whenever max⁡(τ1,τ2)≪∥g∥\max(\tau_1, \tau_2) \ll \|\mathbf{g}\| if q=O(1)q=O(1), e.g., if ϵ\epsilon is small enough compared to ∥g∥/dL\|\mathbf{g}\| / d L for the Gaussian case where both τ1,τ2=O(Lεd)\tau_1, \tau_2 = O(L\varepsilon d), not only in the limit. The new bound recovers Proposition 3.1 exactly as ε→0\varepsilon \to 0 (τ1,τ2→0\tau_1, \tau_2 \to 0).


W4.a Stricter Assumptions

Our assumptions are indeed stronger than those of [1], but [1] analyses a different class of methods: non-adaptive random search, mostly on convex functions. Adaptive methods are harder to analyse, because the step size itself depends on the history of gradient estimates. We therefore need some uniform control on the stochastic gradients, and the standard way to get it is a bound on the sample gradients. Reviewer ax4n also notes that Assumption 5.4 "is common in the analysis of adaptive methods". The closest prior analyses all make assumptions of the same type:

  • Adam / AdaGrad (Défossez et al., 2020), whose proof we adapt: the sample gradients are bounded almost surely, ∥∇f(x;ξ)∥∞≤R\|\nabla f(\mathbf{x};\xi)\|_\infty \le R.
  • ZO-AdaMM (Chen et al., 2019): each sample loss f(⋅;ξ)f(\cdot;\xi) is LL-smooth and has bounded gradients.
  • R-AdaZO (Shu et al., 2025) assum bounded sample loss values, ∣f(x;ξ)∣≤C|f(\mathbf{x};\xi)| \le C, coordinate-wise smoothness of the population loss, and bounded variance of the function values. The first assumption is not a mild one: it already fails for a quadratic, or for the cross-entropy loss over unbounded parameters.
  • FZOO (Dang et al., 2025): Also assume LL-smooth sample loss f(⋅;ξ)f(\cdot;\xi).

Our Assumption 5.4 is of the same kind. A bounded stochastic gradient implies a bounded directional finite difference of the sample loss (see Rev. n8y5 W3).

W4.b Tradeoff in ε\varepsilon

In smooth non-convex ZO optimization, it is standard to set ε=O(T−n)\varepsilon = O(T^{-n}) so that the smoothing bias vanishes asymptotically (Ghadimi and Lan, 2013, Eq. (3.25)). Otherwise, the method generally converges only to a neighborhood of a stationary point. By contrast, in the convex setting, this smoothing bias can be eliminated, as shown in Ghadimi and Lan (2013, Eq. (3.27)) and Nesterov [1].

W5. Choice of ε\varepsilon

We respectfully disagree, the ZO LLM fine-tuning community and our experiments show no significant effect of the smoothing ε\varepsilon on the performance nor on the convergence, as long as it is small enough (within [1e−2,1e−7][1e-2, 1e-7], see ablation below). Fixing ε\varepsilon is standard practice in ZO fine-tuning of LLMs, and we follow it:

  • MeZO (Malladi et al., 2023): fixed, 10−310^{-3} for full fine-tuning, and 10−310^{-3} / 10−210^{-2} for LoRA on RoBERTa / OPT. They also note that "the choice of ε\varepsilon seemed to not significantly impact performance" (their Appendix E.3)
  • R-AdaZO (Shu et al., 2025): fixed, μ=10−3\mu = 10^{-3} "for all methods" in the LLM experiments.
  • HiZOO (Zhao et al., 2025): fixed per tuning mode, 10−310^{-3} for full fine-tuning and 10−210^{-2} for LoRA on OPT.
  • Sparse-MeZO [4]: fixed, 10−310^{-3}, reusing MeZO's settings.
  • LOZO [3]: fixed for all baselines. Only LOZO itself is given a two-value sweep, {10−3,10−4}\{10^{-3}, 10^{-4}\}, on OPT.
  • FZOO (Dang et al., 2025): fixed on RoBERTa-large, and a three-value sweep for FZOO only on OPT.

In all of these works, the step size is swept and ε\varepsilon is either fixed or tuned over at most two or three values. To show We ran an ε\varepsilon sweep for ZO-SGD, ZO-Adam, and MEAZO on 16-rank LoRA fine-tuning of Llama-3.2 1B on SST-2. Each method keeps the optimal step size from our main results (obtained at ε=10−6\varepsilon = 10^{-6}), and only ε\varepsilon varies:

Best validation loss (mean ± std across 3 seeds, lower is better) for 16-rank LoRA fine-tuning of Llama-3.2 1B on SST-2. Each method uses its optimal step size from the ε\varepsilon = 1e-6 sweep (ZO-SGD 1e-4, ZO-Adam 3e-4, MEAZO 3e-4):

Methodε\varepsilon = 1e-8ε\varepsilon = 1e-7ε\varepsilon = 1e-6ε\varepsilon = 1e-5ε\varepsilon = 1e-4ε\varepsilon = 1e-3ε\varepsilon = 1e-2ε\varepsilon = 1e-1
ZO-SGD1.2100 ± 0.00000.0854 ± 0.00250.0455 ± 0.00070.0456 ± 0.00200.0456 ± 0.00160.0455 ± 0.00150.0433 ± 0.00151.0922 ± 0.0885
ZO-Adam0.2228 ± 0.01460.0557 ± 0.00280.0450 ± 0.00170.0444 ± 0.00200.0443 ± 0.00210.0443 ± 0.00210.0415 ± 0.00101.1379 ± 0.0595
MEAZO0.2716 ± 0.03680.0632 ± 0.00610.0467 ± 0.00200.0453 ± 0.00080.0454 ± 0.00060.0453 ± 0.00060.0417 ± 0.00091.1385 ± 0.0603

All methods are quite robust to the choice of ε\varepsilon.

Q1. choice of epsilon affect convergence

see W5

Q2. Prop 3.1

See W3

Q3. q>1q>1

We provide a convergence proof for MEAZO in the (q=1) setting, which is the setting used in our experiments. Extending the analysis to (q>1) is an interesting direction that we leave for future work

Reviewer_n8y5OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates whether adaptive zeroth-order (ZO) optimizers provide meaningful advantages over well-tuned ZO-SGD for memory-efficient fine-tuning of large models. The authors theoretically and empirically argue that random-direction ZO gradient estimates become increasingly homogeneous in high-dimensional settings, limiting the benefits of coordinate-wise adaptivity, although adaptive methods improve robustness to learning-rate selection. Based on this observation, they propose MEAZO, which replaces coordinate-wise second-moment estimates with a single scalar statistic to adapt the global step size, and establish a convergence guarantee under smoothness and bounded directional finite-difference assumptions. The method is evaluated on synthetic quadratic objectives and across multiple LLM families, fine-tuning tasks, and additional vision and multimodal settings, with comparisons against ZO-SGD, ZO-Adam, R-AdaZO, and FZOO. The results show that MEAZO generally achieves performance comparable to existing methods while improving learning-rate robustness and retaining memory usage close to ZO-SGD.

Critical strengths
  1. The paper uses extensive step-size sweeps and multi-seed experiments across different model families and fine-tuning tasks to distinguish final performance from robustness to hyperparameter selection.

  2. MEAZO replaces coordinate-wise second-moment tracking with a single scalar while achieving performance and step-size robustness comparable to ZO-Adam. The full-model fine-tuning results show that MEAZO retains approximately the memory footprint of ZO-SGD and can fine-tune models that exceed the available GPU memory under ZO-Adam.

Critical weaknesses
  1. Limited algorithmic novelty. MEAZO replaces coordinate-wise second-moment estimates with a single scalar statistic to adapt the global step size, a relatively simple modification of existing adaptive zeroth-order optimization methods. Given the existence of related global step-size adaptation approaches, including FZOO(ICLR2026, the paper does not fully establish a sufficiently substantial algorithmic advance beyond its empirical findings.

  2. Mismatch between the theoretical guarantees and experimental settings. The convergence theorem assumes uniform-sphere perturbations with (q=1) and bounded directional finite differences, whereas the main experiments use Gaussian perturbations and fixed hyperparameter schedules. The convergence-rate corollary further requires specific decaying schedules for the learning rate, perturbation scale, and momentum parameter, limiting the direct applicability of the theoretical results to the practical configurations evaluated.

  3. Restrictive assumptions and limited theoretical improvement. The convergence analysis relies on a dimension-independent bound on directional finite differences, which may be difficult to justify for general high-dimensional objectives. Moreover, the resulting dimension dependence is (O(d)), compared with the (O(d^{3/4})) bound reported for R-AdaZO(ICML 2025) in the variance-dominated setting, so the theoretical contribution does not establish a stronger convergence guarantee than the relevant existing method.

  4. The proposed robustness score depends on a selected loss ceiling and a finite learning-rate sweep, which may affect the resulting comparison despite the sensitivity analyses provided in the appendix. Since the practical benefit of adaptive zeroth-order optimization is primarily its robustness to step-size selection, the evaluation would be more convincing with a prespecified learning-rate protocol or a comparable tuning budget across methods.

Reference:

  1. FZOO: Fast Zeroth-Order Optimizer for Fine-Tuning Large Language Models towards Adam-Scale Speed Dang, Sizhe and Guo, Yangyang etl , ICLR 2026, https://openreview.net/forum?id=NMlF3YjS8E

  2. Refining Adaptive Zeroth-Order Optimization at Ease Yao Shu, Qixin Zhang, Kun He, Zhongxiang Dai https://proceedings.mlr.press/v267/shu25b.html ICML 2025

Questions for authors
  1. Can the authors extend the convergence analysis to Gaussian perturbations, which are used in the main experiments, or explain why the existing guarantee remains informative for this setting??

  2. How realistic is the dimension-independent bound on directional finite differences in Assumption 5.4 for high-dimensional LLM fine-tuning, and can the authors provide empirical evidence supporting this assumption?

  3. How sensitive are the conclusions about step-size robustness to the choice of loss ceiling, learning-rate sweep range, and boundary censoring? Can the authors establish that the observed robustness gains persist under a prespecified evaluation protocol?

  4. Can the authors compare MEAZO, ZO-SGD, ZO-Adam, R-AdaZO, and FZOO under a comparable hyperparameter-tuning budget and matched function-evaluation costs, to establish whether MEAZO offers a practically meaningful advantage beyond reducing optimizer-state memory?

8 comments

We thank reviewer n8y5 for their review of our submission, especially of our theoretical results.

We would like to kindly emphasizes our contributions in this paper do not limit to MEAZO. But also to highlight the non-effectiveness of adaptive ZO methods in terms of performance and convergence, backed up with related theorey (Prop 3.1) and exhaustive experiments, beyond most ZO papers. Even if Adaptive methods can help for robustness (shown empirically).

W1. "Limited algorithmic novelty of MEAZO"

We agree that MEAZO boils down to a simple modification of ZO-Adam. However, we see this as a strength rather than a weakness: the simplicity of a method should not count against its novelty. This is especially true in our case, since the scalarization is not ad hoc but follows from our theory. Proposition 3.1 shows that in high dimension, ZO-Adam's second-moment estimate is dominated by ∥∇f∥2/q\|\nabla f\|^2/q, a term shared by all coordinates. This allowed us to predict that a single scalar EMA would match per-coordinate ZO-Adam even in LLM fine-tuning, which our experiments confirm, at the memory cost of ZO-SGD.

Although FZOO also adapts a single global step size, it normalizes by the standard deviation of the qq perturbed losses within a step, which is undefined at q=1q=1 and unstable at small qq, whereas MEAZO uses an EMA of gt2g_t^2 across steps and works for any qq, including MeZO's default q=1q=1. In a controlled comparison with FZOO's exact estimator and forward-pass budget (Table 3 & App. D.8), FZOO cannot run at q=1q=1 and collapses to chance at q=2q=2 (49.8%), while MEAZO reaches 88.6% and 89.1%; at q=8q=8 the two are comparable.

Furthermore, the central claim of our work is not the algorithm itself; MEAZO is a byproduct of our work. Our core contribution is an understanding of what adaptivity actually does in ZO optimization: against a well-tuned ZO-SGD, adaptive ZO methods bring no gain in convergence speed or final performance (C1), because in high dimension per-coordinate normalization has no structure to exploit (C2). Their real benefit is robustness to the choice of step size (C3).

We believe these findings will change how adaptivity in ZO is studied and used. We kindly ask the reviewer to weigh them alongside the algorithm itself.

W2. "Mismatch in theory vs experiments settings"

Sampling distribution. The reviewer is right that most of our experiments use Gaussian perturbations, while Thm. 5.5 assumes uniform perturbations. Thm. 5.5 is meant only to establish that MEAZO converges. For that purpose, we adopt the uniform-sphere assumption, as is standard in ZO analyses (Flaxman et al., 2004; Nazari et al., 2020; R\mathcal{R}-AdaZO, Shu et al., 2025), because unit-norm perturbations keep the proof clean without changing its conclusions.

Empirically, we find that choice of the sampling distribution barely matters. Appendix D.7 compares Gaussian, uniform-sphere, Rademacher, and ternary perturbations for ZO-SGD, ZO-Adam, R\mathcal{R}-AdaZO, and MEAZO. The training curves are essentially the same. Therefore we chose to use Gaussian noise for the bulk of our experiments to make it easier to compare with some foundational ZO LLM fine-tuning work: MeZO (Malladi et al., 2023) and ZO-Bench (Zhang et al., 2024).

Furtheremore, we would like to emphasize that Prop. 3.1 & F.1, which drive our theory and intuition, are stated for both distributions: Gaussian and uniform. Both give the same coordinate-agnostic bias term.

Finally, during the rebuttal period we extended the convergence analysis of Thm. 5.5 to Gaussian perturbations and proved an improved rate of O(d/T)O(\sqrt{d/T}), which closes this gap entirely (see general comment G.2). We thank the reviewer for this feedback, which strengthened our claims.

No hyperparameter schedules. We would like to clarify that all of our LLM experiments use q=1q=1 by default, exactly as assumed in Thm. 5.5. The choices in Cor. 5.6 (η=η0/T\eta=\eta_0/\sqrt{T}, ε2=ε02/T\varepsilon^2=\varepsilon_0^2/\sqrt{T}, β=1−b/T\beta=1-b/T) are constants that depend on the total budget TT, not decaying schedules: they do not change across iterations. Since the training budget is fixed in practice, our experiments satistfy conditions in the corollary: T=10,000T=10{,}000, our β=0.999\beta=0.999 corresponds to b=10b=10 (which satisfies T≥2bT\ge 2b), ε=10−6\varepsilon=10^{-6} corresponds to ε0=10−5\varepsilon_0=10^{-5}, and every step size η\eta in our sweep corresponds to η0=100 η\eta_0=100\,\eta.

W3. "Restrictive assumptions and not better convergence rate"

  • Assumptions. Our assumptions are quite standard when analyzing adaptive methods (as pointed out by Rev. ax4n). Bounded directional finite differences can be derived from bounded gradient assumptions (proof sketh below) also assumed by FO-Adam (Défossez et al., 2020) and ZO-AdaMM (Chen et al., 2019). FZOO also assumed LL smooth sample losses, whereas R\mathcal{R}-AdaZO assume bounded sample functions (cf general comment G.1).

Claim. If ∥∇f(x;ξ)∥≤G\|\nabla f(\mathbf{x};\xi)\| \le G for all x\mathbf{x} and ξ\xi, then Assumption 5.4 holds with B=GB = G.

Proof sketch. By the mean value theorem, δt=∇f(zt;ξt)⊤ut\delta_t = \nabla f(\mathbf{z}_t;\xi_t)^\top \mathbf{u}_t for some zt∈[xt−εut, xt+εut]\mathbf{z}_t \in [\mathbf{x}_t - \varepsilon\mathbf{u}_t,\, \mathbf{x}_t + \varepsilon\mathbf{u}_t]. Since ∥ut∥=1\|\mathbf{u}_t\| = 1, Cauchy–Schwarz gives ∣δt∣≤∥∇f(zt;ξt)∥≤G|\delta_t| \le \|\nabla f(\mathbf{z}_t;\xi_t)\| \le G. □\square

  • Rate. We would like to emphasize that the goal of Thm 5.5 is a sanity check of convergence for MEAZO. That being said, and based on reviewer feedback, we have extended the proof of convergence for MEAZO to the Gaussian perturbtation setting (see general comment G.2), whose rate of O(d/T)\mathbf{O(\sqrt d / \sqrt T)} matches that of ZO-SGD and improves on that of R\mathcal{R}-AdaZO.

W4. "Robustness score depends on the ceiling"

Protocol. We agree that any robustness score depends on the sweep it is computed from, and we would like to clarify that our evaluation already follows a prespecified step size protocol with a comparable tuning budget across methods. Every method is tuned with the same two-stage procedure, described in Appendix C.2.

The protocol yields the same number of runs per method, 18 step sizes ×\times 3 seeds == 54 runs.

Ceiling and finite sweep. The ceiling τ\tau is not tuned. It is fixed by one rule shared by all methods within a setting: the largest ceiling under which no method's curve is truncated by the edges of its sweep, capped at the common initial validation loss. This choice directly addresses the finite-sweep concern, because no method's score is cut short by where its sweep happens to end. We plot every resulting loss-vs-step-size curve in Appendix D, so the scores can be checked against the raw sweeps.

Measures that do not depend on a single ceiling. To further reduce the dependence on τ\tau, we report an additional measure in our general comment G.5: the expected regret of random step size search of Sivaprasad et al. (2020), which uses no ceiling; It leads to the same conclusion as AτA_\tau: adaptive methods are at least as robust as ZO-SGD, and often substantially more.


Q1. "Convergence analysis extension to Gaussian?"

See W2.

Q.2 "Dimension-independent bound on directional finite differences justified?"

Linked to above W.3 and reviewer zfy6 W2.

Q.3 "Sensitivity of Robustness"

See W4.

Q.4 "Budget comparison experiment"

Matched costs and budget. We already benchmark MEAZO against all the baselines under comparable hypermater-tuing budget and matched function evaluation cost. Table 1 reports: ZO-SGD, ZO-Adam, R\mathcal{R}-AdaZO and MEAZO use the same estimator (same function evaluations per step) and the same step size protocol (Appendix C.2, comparable tuning budget). We update Table 2 below to include R\mathcal{R}-AdaZO' robustness score:

Step size robustness score (mean ± std over 3 seeds), LoRA fine-tuning (L: Llama-3.2, Q: Qwen-3).

MethodL1BQ0.6BQ8B
——————————XSum————————
ZO-SGD1.03 ± 0.011.23 ± 0.010.37 ± 0.01
ZO-Adam1.10 ± 0.011.62 ± 0.010.55 ± 0.01
R-AdaZO1.01 ± 0.021.56 ± 0.010.52 ± 0.00
MEAZO1.09 ± 0.011.63 ± 0.010.55 ± 0.01
——————————SST-2————————
ZO-SGD4.03 ± 0.224.61 ± 0.23102.71 ± 0.77
ZO-Adam4.87 ± 0.165.62 ± 0.51152.34 ± 3.00
R-AdaZO4.85 ± 0.155.34 ± 0.82149.74 ± 2.38
MEAZO4.65 ± 0.164.81 ± 0.00155.96 ± 1.95
——————————SQuAD————————
ZO-SGD4.96 ± 0.0411.36 ± 0.175.24 ± 0.04
ZO-Adam5.69 ± 0.0711.54 ± 0.258.61 ± 0.44
R-AdaZO5.59 ± 0.0512.59 ± 0.047.87 ± 0.14
MEAZO5.63 ± 0.0511.77 ± 0.168.69 ± 0.02

As for FZOO, we do the same comparison in Table 3 against MEAZO-Fwd, which matches FZOO's estimator, perturbation distribution and forward-pass budget. There, FZOO is undefined at q=1q=1 and collapses at q=2q=2, while MEAZO-Fwd is stable at every qq.

Advantage beyond memory: robustness. MEAZO's advantage is delivering the step-size robustness of ZO-Adam over ZO-SGD at ZO-SGD's memory cost. In practice, this is what makes adaptivity available at scale: on full-model fine-tuning of Qwen-3 8B, ZO-Adam runs out of memory, while MEAZO runs and is more robust than ZO-SGD on all three tasks (see general comment G.3).

Reviewer_zfy6OpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper asks whether Adam-style coordinate-wise adaptivity helps zeroth-order (ZO) fine-tuning of LLMs. Proposition 3.1 shows that with q perturbations per step and q much smaller than d, the expected squared ZO estimate is dominated by an isotropic term, so per-coordinate second moments collapse to a common value. Empirically, well-tuned ZO-SGD matches ZO-Adam in final metrics (Table 1), while adaptive methods score higher on a new cup-area step-size robustness measure (Table 2). The authors propose MEAZO, which keeps one scalar EMA of the squared averaged projected gradient to normalize the global step, and prove a convergence bound that scales as d2/Td^2/\sqrt{T} under bounded finite differences (Theorem 5.5). Experiments cover synthetic quadratics, LoRA and full-model fine-tuning of Llama-3.2 and Qwen-3 on SST-2, XSum and SQuAD, ViT-B/16, Ministral 14B, and FZOO.

Critical strengths
  1. Proposition 3.1 gives a short, checkable reason why per-coordinate second moments carry little coordinate-specific information when q is much smaller than d: the expected squared estimate is the isotropic term ∥∇f∥2/q\Vert \nabla f \Vert^2/q plus a per-coordinate term of order gk2g_k^2. I checked the proof in Appendix F.1 and it is correct. Figure 2 and Table 8 show the predicted collapse on synthetic quadratics and on Llama-3.2 1B. This settles a question the MeZO line of work left open.

  2. The empirical protocol is more careful than in most ZO papers: two-stage dense step-size sweeps (roughly 18 step sizes and 3 seeds per setting, Section 4 and Appendix C.2), three seeds, a controlled FZOO comparison (MEAZO-Fwd, Appendix D.8) that isolates the normalization from the estimator, ablations of the ceiling τ\tau (D.2), of β1\beta_1 (D.6) and of the perturbation distribution (D.7), and measured memory and latency up to Qwen-3 8B (Table 11). The negative result on ZO-Adam is credible because of this.

Critical weaknesses
  1. The robustness effect is smaller than the text claims, and smallest where MEAZO's memory saving matters. For full-model fine-tuning (Table 4) the scores are 56.41 (ZO-SGD), 57.11 (ZO-Adam) and 57.47 (MEAZO), a 2% spread, yet Section 6.2 reports "improved robustness for adaptive methods". In Figure 5 the caption gives 9.21e4 (ZO-SGD) and 9.46e4 (MEAZO), a 3% gap, while Section 6.1 calls this "a significant improvement". Table 2 shows larger gains, above 50% in some cells, but reports no seed variability for the score. Claim C3 rests on this score, so I would like to see uncertainty for every score, text that matches the numbers, and a second measure such as the largest stable step size relative to the optimum, since AτA_\tau is invariant to rescaling and gives no credit for tolerating large step sizes.

  2. The theory does not support the property MEAZO is built for. Theorem 5.5 and Corollary 5.6 give a rate of order d2/Td^2/\sqrt{T} for the averaged squared gradient norm, worse than the d/T\sqrt{d/T}-type rate of plain ZO-SGD (Ghadimi and Lan, 2013), and the term 2RdLη/(1−β)2R_dL\eta/(1-\beta) grows with η\eta exactly as for SGD, so the bound says nothing about step-size robustness. The d2d^2 seems to come from using Assumption 5.4 as an almost-sure bound gt2≤d2B2g_t^2 \le d^2B^2 (Eq. 9) in (80) and (88), where a bound on the conditional expectation, of order dB2dB^2 for uniform perturbations, appears to suffice. An AdaGrad-Norm style analysis (Ward et al., 2020), valid for any step size, would speak to robustness directly. Corollary 5.6 uses β=1−b/T\beta=1-b/T while Corollary G.6 uses β=1−1/T\beta=1-1/T.

Questions for authors

See Weakness.

4 comments

We thank Reviewer zfy6 for their in depth review of our work including checking the correctness of our theory.

W1. "Robustness"

First, we would like to point out that since the submission, we also ran full-model fine-tuning of the larger Qwen-3 8B on all three tasks (see General comment G.3). In this setting, ZO-Adam runs out of memory on an 80GB A100, while MEAZO maintains the same peak memory and iteration latency as ZO-SGD. The table shows that MEAZO is more robust than ZO-SGD on all three tasks, more prominently on SST-2.

Uncertainty for every score. We agree. In the original manuscript, we averaged the loss-vs-step-size curves over the 3 seeds and computed AτA_\tau on the averaged curve, so no seed variability was provided. We now compute AτA_\tau separately for each seed and report mean ±\pm std. The ceiling τ\tau and normalizer LL are the same as before, so the std reflects only seed-to-seed variation. This yields the following updated Table 2:

Step size robustness score AτA_\tau, 16-rank LoRA fine-tuning (L: Llama-3.2, Q: Qwen-3).

MethodXSum L1BXSum Q0.6BXSum Q8BSST-2 L1BSST-2 Q0.6BSST-2 Q8BSQuAD L1BSQuAD Q0.6BSQuAD Q8B
ZO-SGD1.03 ± 0.011.23 ± 0.010.37 ± 0.014.03 ± 0.224.61 ± 0.23102.71 ± 0.774.96 ± 0.0411.36 ± 0.175.24 ± 0.04
ZO-Adam1.10 ± 0.011.62 ± 0.010.55 ± 0.014.87 ± 0.165.62 ± 0.51152.34 ± 3.005.69 ± 0.0711.54 ± 0.258.61 ± 0.44
MEAZO1.09 ± 0.011.63 ± 0.010.55 ± 0.014.65 ± 0.164.81 ± 0.00155.96 ± 1.955.63 ± 0.0511.77 ± 0.168.69 ± 0.02

Additionally, the full-model fine-tuning results (Table 4, Llama-3.2 1B on SST-2) with seed variability are below:

Full-model fine-tuning of Llama-3.2 1B on SST-2: AτA_\tau.

MethodRobustness score
ZO-SGD56.50 ± 0.19
ZO-Adam57.43 ± 0.25
MEAZO57.61 ± 0.40

Text that matches the numbers. We will revise Sections 6.1 and 6.2, and the caption of Figure 5, to state what the numbers show:

  • Adaptive methods are never less robust than ZO-SGD.
  • In some settings the gain is marginal or within seed variability, e.g. full-model fine-tuning of Llama-3.2 1B on SST-2, or LoRA on Qwen-3 0.6B for SST-2 and SQuAD.
  • In others it is large: LoRA - SQuAD - Q8B, LoRA - SST-2 - Q8B and full-model fine-tuning - SST-2 - Q8B.

A second measure: largest tolerated step size relative to the optimum. We agree that AτA_\tau gives the same credit for tolerating step sizes 10×10\times smaller than the optimum as 10×10\times larger, even though only the latter risks divergence.

Following the reviewer's suggestion, we add a one-sided measure. Let η∗\eta_* be a method's best swept step size, with loss ℓ∗\ell_*. For a relative tolerance ρ\rho, ηR(ρ)\eta_R(\rho) is the largest step size above η∗\eta_* at which the validation loss stays within (1+ρ) ℓ∗(1+\rho)\,\ell_*. We compute it by linear interpolation in log⁡10η\log_{10}\eta between swept step sizes. We report log⁡10(ηR/η∗)\log_{10}(\eta_R/\eta^*) as mean ±\pm std over seeds. The updated manuscript (Appendix H1) plots this as a function of ρ∈[2%,100%]\rho \in [2\%, 100\%] for all settings. For ease of exposition, here is an excerpt at ρ=25%\rho = 25\%:

Largest tolerated η\eta above the optimum at ρ\rho=25%, log⁡10(ηR/η∗)\log_{10}(\eta_R/\eta_*) (higher is better), LoRA fine-tuning (L: Llama-3.2, Q: Qwen-3).

MethodXSum L1BXSum Q0.6BXSum Q8BSST-2 L1BSST-2 Q0.6BSST-2 Q8BSQuAD L1BSQuAD Q0.6BSQuAD Q8B
ZO-SGD0.84 ± 0.010.31 ± 0.000.30 ± 0.010.14 ± 0.000.28 ± 0.030.15 ± 0.120.48 ± 0.030.25 ± 0.010.20 ± 0.07
ZO-Adam1.03 ± 0.010.99 ± 0.020.81 ± 0.040.28 ± 0.060.59 ± 0.090.20 ± 0.080.63 ± 0.020.43 ± 0.030.48 ± 0.06
MEAZO1.00 ± 0.011.00 ± 0.000.86 ± 0.020.30 ± 0.060.40 ± 0.090.23 ± 0.070.63 ± 0.060.46 ± 0.050.43 ± 0.06

Same measure at ρ\rho=25%, full-model fine-tuning (ZO-Adam runs out of memory on Qwen-3 8B).

MethodSST-2 L1BXSum Q8BSST-2 Q8BSQuAD Q8B
ZO-SGD0.37 ± 0.020.28 ± 0.020.15 ± 0.010.17 ± 0.02
ZO-Adam0.35 ± 0.00OOMOOMOOM
MEAZO0.44 ± 0.150.48 ± 0.140.52 ± 0.040.55 ± 0.02

These results strengthen our original claim C3 significantly, we appreciate this suggestion.

W2.a "[MEAZO] rate is worse than the one of ZO-SGD"

We would like to emphasize that our Thm 5.5 and Cor. 5.6, initially given as sanity check of the convergence of MEAZO, actually prove it matches the convergence rate O(1/T)O(1/\sqrt{T}) of ZO-SGD for nonconvex smooth problems. We nevertheless agree that our O~(d2/T)\widetilde{\mathcal O}(d^2/\sqrt T) rate for uniform perturbation leaves room for improvement, which is also the case for other relevant adaptive ZO methods (cf general comment G.1). We leave tightening it for future work.

However, during the rebuttal period, we proved an improved rate of O(d/T)O(\sqrt{d/T}) for Gaussian perturbation (cf general comment G.2).

W2.b "Bound [..] of order dB2dB^2 [..] appears to suffice"

Thank you for pointing this out. Indeed, in the extended (see general comment G.2) MEAZO proof with Guassian perturbations, we have that gt2≤dB2g_t^2 \leq d B^2, which improves our final rate by a factor of dd.

W2.c "The theory does not support the [robustness] theory MEAZO"

In the FO setting, Ward et al. (2020), Thm. 2.1, prove convergence of AdaGrad-Norm for any fixed η>0\eta>0, without prior knowledge of problem constants.

In the ZO setting, our guarantee is weaker in this respect: Cor. 5.6 uses η=η0/T\eta=\eta_0/\sqrt{T}, ε2=ε02/T\varepsilon^2=\varepsilon_0^2/\sqrt{T} and β=1−b/T\beta=1-b/T. However, these values require no knowledge of unknown problem constant (LL or BB) and guarantee vanishing stationarity error for every fixed problem satisfying our assumptions. Thus, our convergence analysis of MEAZO provides robustness to unknown problem constants.

Similar horizon-dependent choices appear in adaptive ZO analyses:

  • ZO-AdaMM: αt=1/dT\alpha_t=1/\sqrt{dT} (Prop. 2, Thm. 1).
  • Projected ZEMA: αt=α/T+1\alpha_t=\alpha/\sqrt{T+1}, for any α>0\alpha>0 (Cor. 19).

Other guarantees involve problem-dependent tuning or restrictions:

  • ZO-SGD’s eq. (3.24) uses (L,σ)(L,\sigma)
  • R-AdaZO’s choices after eq. (58) involve LL and initial suboptimality of the smoothed objective
  • proximal ZEMA restricts α≤/(2ρ)\alpha \leq /(2\rho)
  • FZOO assumes η/σt≤N/(16dL)\eta/\sigma_t\le N/(16dL)

Convergence for an arbitrary fixed positive base step size remains an interesting direction for future work.

W2.d Typo in setting β\beta

We thank reviewer zfy6 for spotting this typo. We fixed it in updated version for β=1−b/T\beta = 1 - b/T.

Thank you again for your review. If your main concerns are now resolved, we would appreciate if you could consider revising your score. Please let us know if any significant concerns remain.

Thank you for the additional experiments. They address some of my concerns about step-size robustness and give me more confidence in the empirical results. The analysis still does not establish convergence for an arbitrary fixed positive base step size. I hope the final version can clarify this limitation and, if possible, strengthen the guarantee. I will keep my rating .

Comments on the paper

6 comments
AuthorsOpenReview ↗

General answer to all reviewers

We thank all the reviewers for their careful reading of our paper, confirming the "correctness" (Rev. zfy6 & Tz53) theoretical results, going into the details of our experiments confirming their "comprehensiveness" (Rev. zfy6, n8y5, Tz53 & ax4n) and acknowledging the overall "transparency" (Rev. ax4n) of our submission. We are grateful for the comments, suggestions and questions provided by Reviewers zfy6, n8y5, Tz53 and ax4n.

This general comment consolidates our responses to several recurring points. Remaining questions are addressed individually.

We have uploaded an updated manuscript, with the following changes marked in cyan:

  • Additional robustness results (App. H1)
  • Derivation for modified Propoistion 3.1 with finite ε\varepsilon (App. H2)
  • Convergence proof for Gaussian perturbation (App. I)

G1. Assumptions and convergence rate

We would like to emphasize that our submission provides a convergence theorem of MEAZO, as a sanity check of convergence. We decided to follow the proof of Defossez et al, ``A Simple Convergence Proof of Adam and Adagrad" (2020) for its i) standard assumptions and its ii) simplicity allowing reviewers to verify its soundness.

  1. Our smoothness and bounded gradient assumptions are standard in the optimization literature. Moreover, it is an orthogonal and active theoretical domain of research to lift them. Cf. Table 1 in Zhang et al., "Convergence Guarantees for RMSProp and Adam in Generalized-smooth Non-convex Optimization with Affine Noise Variance" (TMLR, 2025).
  2. We never claimed MEAZO was achieving faster or equal convegence speed than ZO-SGD. Here is a comparison of stationarity measure, convergence rates and assumptions of relevant works:
  • ZO-SGD (Ghadimi and Lan, 2013): O(d/T)\mathcal O(\sqrt{d/T}) for the expected squared gradient norm, under smooth population losses and unbiased stochastic gradients with bounded variance (Cor. 3.3, eq. (3.30)). Its step size is tuned using LL and σ\sigma.
  • ZO-AdaMM: O~(d/T)\widetilde{\mathcal O}(d/\sqrt T) for the expected squared gradient norm, under smooth, Lipschitz sample losses (Thm. 1 and eq. (13)).
  • ZEMA: O(d2/T)\mathcal O(d^2/\sqrt T) for an adaptive Moreau-envelope squared gradient, under weak-convexity, Lipschitz sample losses, and a bounded domain (Cors. 19 and 22).
  • R-AdaZO: T−1/4T^{-1/4} dependence for the average expected gradient norm, plus smoothing bias, under bounded sample losses, bounded function-value variance, and coordinate-wise population smoothness (Thm. 5.9). Note that its d3/4d^{3/4} variance factor does not imply a d3/2/Td^{3/2}/\sqrt T expected squared norm gradient rate.
  • FZOO: O(d/T)\mathcal O(d/\sqrt T) for the average expected squared gradient norm when under sample loss smoothness, bounded stochastic gradient variance, and η/σt≤N/(16dL)\eta/\sigma_t\leq N/(16dL) (Thm. 3.6).

These comparisons illustrate the difficulty of obtaining sharp dimension dependence in adaptive ZO analyses. We will summarize the above comparison in a table in the appendix of the camera-ready version.


G2. Improved rate O(d/T)O(\sqrt{d/T}) for Gaussian perturbations

As suggested by Reviewer n8y5 we have extended our convergence analysis to Gaussian perturbations.

We prove a improved convergence rate for the average expected squared gradient norm of O(d/T)\mathbf{O(\sqrt{d/T})}, which matches the one of ZO-SGD.

Proof sketch.The proof (Appendix I) follows the uniform perturbation analysis but requires i) Gaussian moments for the adaptive linear term and ii) concentration inequalities to control the random adaptive denominator.

Assumptions. We assume LL-smoothness and bounded stochastic gradients ∣∣∇f(x;ξ)∣∣≤B||\nabla f(\mathbf{x}; \xi)|| \leq B. Note that for a normal distribution, we have Eu∼N(0,Id)[∣∣u∣∣2]=dE_{\mathbf{u} \sim \mathcal{N}(0,I_d)} [||\mathbf{u}||^2] = d, which implies Et−1[gt2]≤dB2E_{t-1}[g_t^2]\le dB^2. This indicates that our previous bounded projected gradient asssumption for uniform perturbation impliying gt2≤d2B2g_t^2 \leq d^2 B^2, was probably too pessimistic, as suggested by Reviewers zfy6 and axn4.

G3. New results on full model finetuning of Qwen3 8B

We would like to point the reviewers to the new results below, which extend our full-model fine-tuning setting beyond Llama-3.2 1B on SST-2 (Table 4 in the main paper) to Qwen-3 8B on XSum, SQuAD, and SST-2. These experiments were completed after the submission deadline, in time for the rebuttal.

Full-model fine-tuning of Qwen-3 8B on XSum, SQuAD, and SST-2

MethodMetricAvg. latency (s/step)Peak memory (GB)Robustness score
———————————XSum: ROUGE-L————————————————
ZO-SGD25.20 ± 0.546.4467.900.87
MEAZO25.45 ± 0.196.4867.901.04
———————————SQuAD: F1 (%)————————————————
ZO-SGD82.10 ± 0.515.8866.207.01
MEAZO83.18 ± 0.315.9166.208.15
———————————SST-2: Accuracy (%)————————————————
ZO-SGD93.58 ± 0.561.8565.676.71
MEAZO93.96 ± 0.301.8865.6711.20

These results further support our central claim: when properly tuned, ZO-SGD performs well, and MEAZO matches it (slightly exceeding it on all three datasets here) while being consistently more robust to the choice of step size. Both methods have the same peak memory and near-identical per-step latency. ZO-Adam runs out of memory in this setting and is therefore not reported.

Note: For Qwen-3 8B on XSum, we reduced the batch size from 8 to 4 due to memory constraints. This explains why the ROUGE-L scores are lower than the LoRA fine-tuning results in Table 1.

G4. Comparison with ZO-ClipSGD, ZO-NSGD, Sign-ZO-SGD, Sparse-MeZO

Following feedback from Reviewers Tz53 and ax4n, we used our remaining time and compute budget to run additional experiments on Llama-3.2 1B on SST-2 for the most relevant baselines, using the same full step-size selection protocol as before.

Minor correction to Table 4: The reported latency and peak-memory measurements were obtained with q=5q=5. We will update these entries with the corresponding q=1q=1 measurements reported below, ensuring consistency across methods. This correction does not change any of the paper's conclusions.

G.4.1 Comparison with Sparse-MeZO

Sparse-MeZO (Liu et al., 2026) computes static thresholds at initialization, making it incompatible with LoRA, as the BB matrix would remain masked throughout training. We therefore evaluate Sparse-MeZO (r=0.8r=0.8, i.e., 80%80\% sparsity) exclusively in the full-model fine-tuning setting, extending Table 4 of the main paper as follows:

[UPDATED] Full-model fine-tuning of Llama-3.2 1B on SST-2

MethodAccuracy (%)Avg. latency (s/step)Peak memory (GB)Robustness score
ZO-SGD88.99 ± 0.410.365.5959.48
Sparse-MeZO (r=0.8r=0.8)89.22 ± 1.060.505.7874.24
ZO-Adam88.99 ± 0.820.4115.7860.43
MEAZO89.64 ± 0.940.385.5960.53
Sparse-MEAZO (r=0.8r=0.8)88.61 ± 0.520.525.7881.56

Sparsity improves both ZO-SGD and MEAZO. Sparsity acts as variance reduction for the ZO gradient estimate: perturbing only 20% of the coordinates shrinks the effective dimension that drives the estimator's variance. The benefit is independent of the optimizer underneath. Sparsity raises the robustness score of ZO-SGD from 59.48 to 74.24 and of MEAZO from 60.53 to 81.56. Sparse-MEAZO has the highest robustness of all methods. Accuracy stays within seed-to-seed variation. Sparsity and MEAZO's update rule therefore improve robustness in complementary ways. The cost is about 40% more time per step for both sparse methods and +0.19 GB of peak memory at q=1q=1, to store the sparse mask at 1 bit per weight.

Note: The robustness scores here differ slightly from those in Table 4 of the main paper. The score is normalized by the best validation loss LL across all methods, and adding Sparse-MeZO lowers LL a little. This rescales every method's score by the same factor, so the ranking and the relative gaps between methods don't change.

[UPDATE]: updated memory numbers to account for unreleased noise buffers (affecting all baselines).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.