- 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 is shared by all coordinates and dominates the second moment when . 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 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 . The descent Lemma E.2 with and gives , and for a tuned . 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 with (eq. (88)). Second, decoupling the denominator from the current sample (Lemma G.9) produces the term with in (10), which does not depend on and cannot be reduced by tuning. As a result, Corollary 5.6 gives , a factor 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, and should be and , since the update uses the projected gradients at (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
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 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 , 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 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 and . Unlike the standard analysis of ZO-SGD of Ghadimi and Lan (2013), our schedules in Cor. 5.6 for , and do not depend on the smoothness constant or the uniform bound of the gradient .
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.
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 and ζ=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).
ZO-ClipSGD takes a ZO-SGD step and clips it when ∣gt∣>c. We calibrated c from a short unclipped ZO-SGD run on the same task: c=4 is the median of ∣gt∣ (about 50% of steps clipped) and c=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.1L, where L is the best validation loss.
We model independent random search from the shared log-uniform prior [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,i denotes the resulting weight of run i, 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.
E[Nm]=pm1.
- 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/pm. 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.