acceptodds
Under review as a conference paper at ICLR 2027

Adaptive Zeroth-Order Optimization via Sample-Wise Second Moments

Abstract

Zeroth-order optimization (ZO) estimates gradients using function evaluations without requiring access to first-order derivatives. Existing ZO methods either rely on isotropic perturbations or require additional function evaluations to obtain adaptive curvature information, introducing extra computation overhead and slowing the convergence. We propose two adaptive ZO optimizers that share an efficient diagonal second-moment estimator built from per-sample gradient surrogates. This state shapes both perturbations and updates, with distinct update scalings and shared adaptive damping for stability and perturbation-scale control. We provide convergence proofs for both variants and demonstrate the first variant’s superior performance on test functions with heterogeneous curvature. Experiments on both full-model and parameter-efficient language-model fine-tuning show that standard and adaptive ZO baselines require up to as many forward passes as our methods, while our methods achieve competitive final performance.

Primary area:
optimization
Keywords:
Zeroth-order Optimization

Reviews

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

This paper propose two ZO method to introduce the online sample-wise second-moment estimate to scale the vanilla ZO perturbations to achieve updates with curvature information. It provides both theoretical analysis and empirical studies to validate their efficiency. For the modern LLM models, the fine-tuning performance can achieve better than several classical baselines.

Critical strengths
  1. The paper writing and total organization is good. Each key factors and points are claimed clearly and can be easily understood in the detailed operations.

  2. It brings several novel and interesting perspectives into the ZO community, enriching the insights for the algorithm designing.

Critical weaknesses
  1. The motivation of adopting average of the squared per-sample gradients surrogate is unclear. The authors claimed that squaring the mini-batch averaged gradient discards the variation among individual sample gradients and may yield a small value. I do not believe this is a weakness which should be resolved in the training. Since in the FO method, this is a classical and widely adopted operation. Also, the empirical advantages are unclear between these two cases.

  2. The calculation of ss terms adopt z⊙zz\odot z instead of Az⊙AzAz \odot Az. The authors claim δ\delta term has included the information of AA. However, it is a loss gap, which means a scaler to determine the strength of perturbation. The true direction of ZO gradient is AzAz (or A−1zA^{-1}z). Thus simply ignoring the term in second order momenta does not make sense enough. More discussions should be added to claim the motivation.

  3. Assumption 1 seems too strong that for the general Gaussian sampling its upper and lower bound may divergent. The proofs seems only consider them as constants in the final bounds.

  4. Lack of key ablation studies. It's not clear the improvements come from which component primarily.

Questions for authors
  1. Why and how the assumption 1 is satisfied under z∼N(0,I)z\sim N(0,I)?

  2. We usually use batch-wise gradient in practice. Why is adopting sample-wise gradient important?

  3. What is the theoretical impacts between these two cases, batch-wise and sample-wise? If we use the sample-wise gradient, can it converge faster or better?

  4. Why the second-order momenta is calculated only on zz instead of AzAz or A−1zA^{-1}z? Can authors provide the detailed studies between these cases?

  5. Can authors provide a detailed ablation on each component in the proposed method? As my current understanding, the method mainly adopts the curvature matrix to revise the perturbations and uses sample-wise gradient for second-order momenta. So which is the key contributor for the accuracy compared to MeZO or HiZOO? I am not quite clear the source of the improvements.

  6. Can authors provide a detail comparison to illustrate the differences of calculation among the baselines and the proposed method? If possible, please survey more related baselines. Experiments are not important, while the difference and insight is.

  7. What is the training profiles on memory and calculations?

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

This paper proposes two adaptive zeroth-order optimizers, SWIZO and SWIZO*, which extract a diagonal sample-wise second-moment signal from per-example finite-difference coefficients obtained during standard two-point ZO evaluations. The resulting state is maintained with an exponential moving average and combined with adaptive damping to control the perturbation geometry and update scaling without additional function evaluations. The paper provides convergence analyses for both variants and evaluates them on synthetic objectives and language-model fine-tuning with OPT-1.3B and Llama-3.2-3B.

Critical strengths
  1. The main idea of reusing per-sample loss differences from the standard two-point ZO evaluations is interesting and computationally attractive. The proposed second-moment statistic does not require additional model queries beyond those already needed for the ZO update. The method is simple to integrate into memory-efficient ZO fine-tuning. Both variants require only one additional diagonal state, which is cheaper than adaptive-moment methods that maintain both first- and second-moment states.

  2. The adaptive damping mechanism addresses an important practical issue: directly using the accumulated second moment can shrink the effective perturbation radius excessively. Anchoring the smallest diagonal entry provides a simple way to stabilize the perturbation scale. The paper provides convergence analyses for both proposed update variants and includes synthetic experiments specifically designed to test optimization under heterogeneous curvature.

Critical weaknesses
  1. The comparison with recent adaptive and curvature-aware ZO methods is incomplete. The main experiments compare only against MeZO, R-AdaZO, and HiZOO. However, the paper itself discusses several additional closely related approaches, including ZO-AdaMU, ZOHA, PaZO, LOREN, and DiZO. In particular, ZOHA and LOREN are directly relevant because they also introduce Hessian/curvature-aware perturbation mechanisms, while PaZO explicitly studies the role of preconditioning in ZO. Since the main contribution of SWIZO is an alternative way to obtain and use second-moment/curvature information, comparison only with HiZOO as the explicit curvature-aware baseline is insufficient to establish the advantage over the current literature.

  2. The empirical evaluation is too narrow to support the generality and scalability claims. The LLM experiments use only three classification datasets, SST-2, WiC, and CB. These tasks cover a relatively narrow set of downstream behaviors and do not include reasoning, generation, instruction following, or other more challenging LLM adaptation settings. In addition, the largest evaluated model is only Llama-3.2-3B, while LoRA experiments are restricted to OPT-1.3B. The paper does not appear to report results over multiple random seeds or provide standard deviations. This is particularly concerning for ZO optimization because both the perturbation directions and the optimization trajectories are stochastic. Several of the accuracy differences in Table 1 are only around one percentage point or less. Without repeated runs, it is difficult to determine whether these gains are statistically meaningful or caused by random variation.

Questions for authors
  1. Why are ZOHA, PaZO, LOREN, ZO-AdaMU, or other recent curvature/adaptive ZO methods not included in the experimental comparison? Could the authors provide comparisons with at least the most closely related curvature-aware methods under the same query, memory, and model settings?

  2. Could the authors extend the evaluation to larger models, e.g., 7B/8B-scale LLMs, and to a broader set of tasks beyond SST-2, WiC, and CB? In particular, reasoning, instruction-following, or generation tasks would make the scalability and generality claims more convincing.

  3. How many random seeds are used for Tables 1 and 2 and Figures 2--4? If the current results are single-run results, could the authors report means and standard deviations over multiple independent runs?

  4. Could the authors derive the expectation of the proposed second-moment statistic explicitly? For ϵ→0\epsilon \rightarrow 0, it appears that

E[δt,i2zj2]=∥Atgi∥2+2(At,jjgi,j)2\mathbb{E}[\delta_{t,i}^2 z_j^2]=\|A_tg_i\|^2+2(A_{t,jj}g_{i,j})^2.

How does this quantity relate quantitatively to the desired diagonal sample-wise second moment? In particular, how does the adaptive damping interact with the shared isotropic term?

  1. Could the authors provide a bias/variance or concentration analysis for StS_t and Σt\Sigma_t? How many ZO iterations are required before the relative coordinate-wise second moments become reliable in a model with billions of parameters?
Reviewer_xqJuOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes SWIZO and SWIZO*, two zeroth-order optimizers for fine-tuning. Both keep a diagonal EMA state Σt\Sigma_t of st(zt⊙zt)s_t (z_t \odot z_t), where sts_t is the mean squared per-sample finite difference from the two forward passes already used for the gradient estimate (Eqs. 3 to 6). The damping λt=1−min⁡jΣt,j\lambda_t = 1 - \min_j \Sigma_{t,j} caps every perturbation radius at ϵ\epsilon (Eq. 8). Both variants perturb along (Σt+λtI)−1/2zt(\Sigma_t + \lambda_t I)^{-1/2} z_t. SWIZO scales the update by the same matrix and SWIZO* by its inverse. Theorems 1 and 2 give O(1/T)O(1/\sqrt{T}) stationarity bounds. Experiments cover two 2D test functions and full and LoRA fine-tuning of OPT-1.3B and Llama-3.2-3B on SST-2, WiC and CB. The paper reports accuracy close to HiZOO, with the baselines needing up to 3.3×3.3\times as many forward passes.

Critical strengths
  1. The second-moment statistic costs no extra queries. Eq. (5) writes the batch statistic as BB scalar finite differences times one shared dd-vector, and the scalars come from the per-sample losses of the two forward passes that MeZO already runs. HiZOO needs a third forward pass per step for its curvature estimate. The change to a MeZO implementation is small: per-sample losses, one extra dd-dimensional state and a few elementwise operations.

  2. The damping in Eq. (8) is a simple fix with no new hyperparameter. Shifting the smallest diagonal entry to one caps every perturbation radius at ϵ\epsilon and removes a common offset that would otherwise shrink all radii as Σt\boldsymbol{\Sigma}_t grows. Fig. 3 supports it on SST-2: at the same learning rate, runs without damping converge more slowly, and the gap widens as 1−ρ1-\rho grows.

Critical weaknesses
  1. The paper does not show that Σt\boldsymbol{\Sigma}_t captures per-coordinate curvature at LLM scale. In Eq. (5) the per-step coordinate pattern is zt⊙zt\mathbf{z}_t \odot \mathbf{z}_t, and sample-wise information enters only through the scalar sts_t. To first order, for a per-sample gradient g\mathbf{g}, E[δ2zj2]=∥Ag∥2+2Aj2gj2\mathbb{E}[\delta^2 z_j^2] = \|\mathbf{A}\mathbf{g}\|^2 + 2A_j^2 g_j^2. The coordinate signal is on average 2/d2/d of a shared offset, while the one-step noise from zj2z_j^2 is of the order of the offset. With d≈1.3×109d \approx 1.3\times 10^9 and a few thousand steps, I expect At\mathbf{A}_t to be mostly noise, and Fig. 4 (SWIZO* flat for 1−ρ1-\rho from 10−410^{-4} to 10−810^{-8}) is consistent with this. Three checks would settle it: replace zt⊙zt\mathbf{z}_t \odot \mathbf{z}_t in Eq. (4) by an independent z′⊙z′\mathbf{z}' \odot \mathbf{z}', use δˉt2\bar\delta_t^2 in place of sts_t, and correlate diag(Σt)\mathrm{diag}(\boldsymbol{\Sigma}_t) with a backprop diagonal Fisher.

  2. The forward-pass claims (up to 3.3×3.3\times in the abstract, up to 2.8×2.8\times against HiZOO in Sec. 4.2) rest on curve end points whose stopping rule is stated neither in Sec. 4.2 nor in App. E. In Fig. 2 the runs stop at different counts, and Fig. 6 seems to take the ratio at the baseline's last point, which inflates it when the baseline has plateaued (R-AdaZO on Llama SST-2). In full fine-tuning the MeZO curves overlap ours on SST-2 for both models, and on Llama CB MeZO stops first, so the gain over MeZO shows up only on WiC. All results are single runs without standard deviations. Please fix a budget or target loss in advance, report at least three seeds, and plot accuracy against forward passes.

Questions for authors

See weakness

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.