acceptodds
Under review as a conference paper at ICLR 2027

MAPS: Momentum-Aware Perturbation Sampling for Zeroth-Order Optimization

Abstract

Zeroth-order (ZO) optimization enables memory-efficient LLM fine-tuning through gradient estimation by forward-only function queries, but most existing methods sample queries based on random isotropic perturbations on parameters that ignore informative optimization states accumulated during training. We introduce **Momentum-Aware Perturbation Sampling (MAPS)**, a plug-and-play framework that uses momentum state to guide subsequent ZO queries. MAPS first calibrates the momentum state to the scale of isotropic perturbations and then mixes momentum-guided directions with stochastic exploration. It further balances the momentum-driven exploitation with random exploration through block-wise gating and temporal scheduling, controlling when and where the momentum-guided queries are applied. Our theoretical analysis establishes the convergence guarantee for MAPS. Since MAPS only modifies perturbation sampling without changing subsequent operations or introducing any additional function evaluation budget, it is generally applicable and extensively evaluated on various base ZO methods, foundation models and tasks. Our extensive experiments show that MAPS improves downstream performance and achieves lower training loss, demonstrating the effectiveness of reusing optimizer states in perturbation sampling.

Primary area:
optimization
Keywords:
Large language model fine-tuning, 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_tVySOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper uses a ZO optimizer's existing momentum to guide subsequent random perturbations, and the experiment section evaluates the proposed method on up to 30B models.

Critical strengths

The paper evaluates the proposed method on 10 tasks, multiple model architectures, and model sizes up to 30B.

Critical weaknesses
  1. Using momentum-like information to guide ZO perturbations is not fundamentally new. For example, ConMeZO (2026) samples perturbations from a cone centered on a momentum-based direction. The paper acknowledges closely related work, such as ZO-AdaMU and Guided Evolutionary Strategies, but its distinction from existing momentum-guided sampling methods needs further clarification and experimental demonstration.
  2. The convergence shows that MAPS converges, but it is not shown to converge faster than LOZO-M. It also seems that the displayed upper-bound constants become less favorable as the guidance parameter increases.
Questions for authors
  1. Since MAPS's improvements are generally modest, could the author supply multiple-seed results to showcase the statistical significance of performance improvements?

  2. The theoretical convergence bound becomes looser with increasing momentum guidance, while the empirical results suggest that momentum guidance improves optimization. Could the authors measure the alignment between the accumulated momentum and the true gradient during training, and provide theoretical or empirical evidence connecting this alignment to the observed convergence improvements?

7 comments

Thank you for highlighting the breadth of our evaluation and raising specific questions about the method. We address the concerns below, focusing on clarifying our contributions, theoretical analysis, and experimental evidence.

R3-W1 & R3-Q1

Thank you for the suggestions. In addition to the previously discussed ZO-AdaMU and Guided Evolutionary Strategies, we also consider the recently proposed ConMeZO. We clarify the methodological differences and provide additional experimental evidence below.

  1. Relationship to and Differences from Existing Guided Sampling Methods.

    ZO-AdaMU jointly designs the perturbation history state, sampling mechanism, and adaptive parameter updates. Its Eq. (4) combines two Gaussian samples, one centered at zero and the other centered at the historical perturbation state, to update the perturbation history.

    z˙t+1∼N(0,αt+1),z¨t+1∼N(mt,1−αt+1),\dot{\mathbf{z}}_{t+1} \sim \mathcal{N}(\mathbf{0}, \sqrt{\alpha_{t+1}}), \qquad \ddot{\mathbf{z}}_{t+1} \sim \mathcal{N}(\mathbf{m}_t, \sqrt{1-\alpha_{t+1}}),

    mt+1=β1z˙t+1+(1−β1)z¨t+1.\mathbf{m}_{t+1} = \beta_1\dot{\mathbf{z}}_{t+1} + (1-\beta_1)\ddot{\mathbf{z}}_{t+1}.

    Here, mt\mathbf{m}_t is its perturbation history state. ZO-AdaMU also constructs an adaptive scaling term from the squared samples. Its simulated annealing schedule controls αt\alpha_t, β1,t\beta_{1,t}, and β2,t\beta_{2,t}. These mechanisms form a dedicated ZO optimizer[1].It can be viewed as a specific improved version of zeroth-order Adam. MAPS directly reuses the directional state already maintained by the base optimizer, without introducing a separate perturbation history recurrence.

    ConMeZO obtains its momentum direction from an exponential moving average of past ZO gradient estimates[2],

    mt+1=βmt+(1−β)g(xt,zt).\mathbf{m}_{t+1}=\beta \mathbf{m}_t+(1-\beta)\mathbf{g}(\mathbf{x}_t,\mathbf{z}_t).

    ConMeZO then uses the normalized momentum direction as the axis of its cone sampler. This concentrates subsequent perturbations around that direction in the high-dimensional parameter space. MAPS directly reuses the momentum already maintained by the base ZO optimizer, such as the first moment of ZO-Adam or the low-rank momentum of LOZO-M. This avoids maintaining a separate state to track past ZO gradient estimates for sampling.

    Guided ES relies on additional surrogate gradients as guidance signals, using them to construct a guiding subspace and modify the covariance of the search distribution[3]. MAPS follows a different design. MAPS does not introduce an additional surrogate model or an independent guiding subspace. It directly uses the momentum state already maintained by the base optimizer to construct guided perturbations. This allows historical optimization information to be incorporated into subsequent sampling without additional gradient computations or function evaluations.

  2. MAPS uses the base optimizer states to guide sampling in its native perturbation space

    ZO-AdaMU maintains a history of sampled perturbations. ConMeZO uses a moving average of ZO gradient estimates to define its cone axis. MAPS takes the momentum state P\mathbf{P} already available in the base optimizer and mixes it with a random perturbation R\mathbf{R} in the same representation. Eq. (5) defines the guided perturbation as $\widetilde{\mathbf{P}} = \sqrt d\,\frac{\mathbf{P}}{\max\{\|\mathbf{P}\|_F,\epsilon\}}, ~ \mathbf{S} = \sqrt{1-\lambda}\,\mathbf{R} + \sqrt{\lambda}\,\widetilde{\mathbf{P}}, ~ \mathbf{R}\sim\mathcal N(\mathbf{0},\mathbf{I}_d).$ And the guided perturbation has the same expected squared norm as the original Gaussian perturbation. This sampling mechanism can be instantiated with different optimizers by reusing their momentum states and perturbation representations. MAPS-ZO-Adam uses the existing first moment to guide the dense perturbation. ZO-Adam then applies its standard first-moment, second-moment, and parameter updates. We also evaluate this sampler in the LoRA setting. MAPS-LOZO-M uses the existing low-rank momentum N\mathbf{N} to guide the left factor U\mathbf{U} of the perturbation UV⊤\mathbf{U}\mathbf{V}^\top.

  1. MAPS guides selected parameter blocks at selected training steps

    Section 4.2 introduces two gates. The temporal gate determines when to use momentum guidance. During warmup, all blocks use the base optimizer’s random sampler. After warmup, each step activates guidance with probability qq. At an active step, the block-wise gate applies guidance to a randomly selected subset of eligible blocks. The parameter pp controls the fraction selected. The remaining blocks use random perturbations. At an inactive step, all blocks use random perturbations.

    ConMeZO uses the cone angle θ\theta to control directional bias. Its warmup schedule adjusts the momentum coefficient βt\beta_t used to estimate the cone axis. ZO-AdaMU anneals αt\alpha_t, β1,t\beta_{1,t}, and β2,t\beta_{2,t} to control perturbation sampling and step size. The two MAPS gates determine whether a given block uses a guided or random perturbation at the current step.

  2. Multiple-seed results on OPT-1.3B and the comparison on OPT-13B

    We compared three methods on WiC under a common training protocol. All methods fine-tuned OPT-1.3B on the same GPU with the same data splits and evaluation protocol. We used a batch size of 16 and trained for 10K steps. The table reports accuracy (%) for each training seed and the sample standard deviation across seeds.

    MethodRun 1Run 2Run 3Mean ± SD
    MAPS-LOZO-M59.7257.3758.9358.67 ± 1.20
    ZO-AdaMU57.6857.9955.6457.11 ± 1.28
    ConMeZO56.9058.9357.2157.68 ± 1.10

    MAPS-LOZO-M achieves the highest mean accuracy. Using unrounded scores, its mean gain is 0.99% over ConMeZO, and 1.57% over ZO-AdaMU.

    We further compare the reported OPT-13B results across seven shared tasks. For each method, we use its best reported results under the experimental protocol and hyperparameter configuration.

    MethodSQuADSST-2WiCBoolQReCoRDRTEMultiRC
    MAPS-LOZO-M84.193.361.671.282.074.064.1
    MAPS-ZO-Adam85.193.263.873.681.274.765.7
    ZO-AdaMU82.492.160.773.083.072.963.0
    ConMeZO83.792.458.369.380.964.558.3

    Overall, the multi-seed results show that MAPS-LOZO-M achieves the better performance among the compared methods on OPT-1.3B. Moreover, the OPT-13B comparisons demonstrate consistent competitive performance across seven tasks: MAPS-LOZO-M outperforms ConMeZO on all seven tasks and ZO-AdaMU on five, while MAPS-ZO-Adam outperforms ZO-AdaMU on six. Notably, MAPS uses only 20K training steps, compared with the larger training budget 100K used by ZO-AdaMU. These results further support the effectiveness and applicability of MAPS across different model scales and optimizer configurations.

R3-W2 & R3-Q2

We thank the reviewer for this suggestion. Our main theorem shows that MAPS-LOZO-M retains the O(T−1/2)O(T^{-1/2}) convergence rate of LOZO-M under the stated assumptions. This guarantee holds for arbitrary orientation of the historical momentum relative to the current gradient, including when they are orthogonal. Importantly, the theorem establishes the same asymptotic convergence order, rather than a faster convergence guarantee than LOZO-M. The effect of momentum guidance on practical optimization progress depends on whether the historical momentum provides useful directional information.

The convergence analysis in the appendix gives an exact expression for Et⟨A,St⟩F2\mathbb E_t\langle\mathbf{A},\mathbf{S}_t\rangle_F^2. Applying this identity to the current subspace gradient A=∇gk(Bks)\mathbf{A}=\nabla g_k(\mathbf{B}_k^s) shows when guidance from Nt−1\mathbf{N}_{t-1}, the accumulated ZO momentum transported to the current subspace, can be beneficial. Specifically, if ⟨A,Nt−1∣Nt−1∣F⟩F2>∣A∣F2d,\left\langle \mathbf{A},\frac{\mathbf{N}_{t-1}}{\\|\mathbf{N}_{t-1}\\|_F}\right\rangle_F^2 > \frac{\\|\mathbf{A}\\|_F^2}{d}, then the squared projection of the gradient onto the momentum direction exceeds its expected squared projection onto an isotropically sampled random unit direction in the d=mrd=mr dimensional subspace. Under this condition, momentum guidance increases the expected squared directional derivative relative to Gaussian sampling, providing a more informative perturbation direction and making the descent term in the one-step bound more favorable, all else being equal.

The main theorem does not require this condition to hold. Instead, its proof uses the uniform lower bound Et⟨A,St⟩F2≥(1−λ~)∣A∣F2,\mathbb E_t\langle\mathbf{A},\mathbf{S}_t\rangle_F^2\geq(1-\widetilde\lambda)\\|\mathbf{A}\\|_F^2, which remains valid regardless of the momentum orientation, including when momentum is orthogonal to the current gradient. This conservative bound does not exploit the additional directional benefit when historical momentum is well aligned with the current gradient. As λ~\widetilde\lambda increases, the lower bound becomes weaker, resulting in a looser convergence upper bound. This reflects the worst case nature of the theoretical guarantee, rather than implying that stronger momentum guidance necessarily harms practical optimization. The empirical benefit depends on the directional information provided by historical momentum along the actual training trajectory.

The practical benefit of momentum guidance also depends on its strength. Table 9 illustrates this effect. At a fixed block ratio of p=0.5p=0.5, the highest WiC accuracy is obtained with λmax⁡=0.3\lambda_{\max}=0.3, while the lowest training loss was obtained with λmax⁡=0.5\lambda_{\max}=0.5. Increasing guidance strength further did not consistently improve either metric, suggesting that excessively strong guidance can limit the benefit of random exploration.

To examine the directional alignment during training, we extracted the accumulated zeroth-order momentum available before the current update at different OPT-1.3B/WiC training checkpoint. For each evaluation minibatch, we computed the first-order reference gradient gtrefg_t^{\mathrm{ref}} by backpropagation and measured its signed cosine similarity with the historical momentum, cos⁡(mt−1,gtref)\cos(m_{t-1},g_t^{\mathrm{ref}}). We also compared the alignment of the standard ZO and MAPS gradient estimates, cos⁡(g^tZO,gtref)\cos(\widehat g_t^{\mathrm{ZO}},g_t^{\mathrm{ref}}) and cos⁡(g^tMAPS,gtref)\cos(\widehat g_t^{\mathrm{MAPS}},g_t^{\mathrm{ref}}), using the same setting. Run 1 and Run 2 evaluate the same training checkpoints using different evaluation samples and perturbations. Cosines are reported in units of 10−510^{-5}. Small cosine values are plausible in a high-dimensional parameter space, so we focus on relative differences in alignment. Gain is the percentage increase in average cosine for MAPS relative to standard ZO within each run.

Run 1Run 2
Stepcos⁡(mt−1,gtref)\cos(m_{t-1},g_t^{\mathrm{ref}})cos⁡(g^tZO,gtref)\cos(\widehat g_t^{\mathrm{ZO}},g_t^{\mathrm{ref}})cos⁡(g^tMAPS,gtref)\cos(\widehat g_t^{\mathrm{MAPS}},g_t^{\mathrm{ref}})Gaincos⁡(mt−1,gtref)\cos(m_{t-1},g_t^{\mathrm{ref}})cos⁡(g^tZO,gtref)\cos(\widehat g_t^{\mathrm{ZO}},g_t^{\mathrm{ref}})cos⁡(g^tMAPS,gtref)\cos(\widehat g_t^{\mathrm{MAPS}},g_t^{\mathrm{ref}})GainMean gain
525−0.712.312.36+2.22%+0.042.252.27+1.27%+1.75%
1025+1.152.122.18+3.12%−0.721.972.06+4.67%+3.90%
1525−0.492.432.45+0.63%−1.042.242.30+2.95%+1.79%
2025+3.102.262.36+4.30%+0.862.232.26+1.24%+2.77%
Mean+0.762.282.34+2.57%−0.222.172.22+2.53%+2.55%

The results show that the alignment between ZO accumulated momentum and the current gradient is not stable. Both the magnitude and sign of this alignment vary across checkpoints and evaluation samples. At step 1525, the momentum cosine is negative in both runs, yet incorporating momentum improved gradient estimate alignment by 0.63% and 2.95%, respectively. MAPS mixes normalized momentum into selected parameter blocks, and the two-point finite-difference estimator is used to estimate the gradient. Consequently, cos⁡(mt−1,gtref)\cos(m_{t-1},g_t^{\mathrm{ref}}) alone does not determine whether guidance improves the estimated direction. Across these results, MAPS improved gradient estimate alignment relative to standard ZO by an average of 2.57% and 2.53%. These results provide empirical evidence that momentum-guided sampling can improve estimator alignment, although the magnitude of the improvement varies across training states.

This alignment improvement also provides an explanation for the observed optimization progress. At a given checkpoint and for a fixed step size along the negative normalized gradient estimate, closer alignment with the gradient implies a larger first order predicted decrease in the same minibatch loss. This is consistent with the lower training loss observed with MAPS under the same query budget in Figure 1.

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

This paper proposes Momentum-Aware Perturbation Sampling (MAPS), a framework that reuses an optimizer’s existing momentum to guide zeroth-order perturbations. It combines norm-calibrated momentum with Gaussian exploration and selectively activates guidance across parameter blocks and iterations. The framework preserves the base optimizer’s update rules and per-iteration function-query budget. The authors instantiate MAPS with LOZO-M and ZO-Adam, provide a convergence analysis for MAPS-LOZO-M under stated assumptions, and report improvements across several language models and downstream tasks.

Critical strengths
  1. A lightweight and reusable design. MAPS offers a practical way to incorporate historical optimization information into perturbation sampling without redesigning the base optimizer. Reusing existing momentum and preserving the two-query budget are attractive properties. The measured memory and runtime results in Table 7 also help substantiate its implementation cost.
  2. Empirical evaluation across multiple settings. The experiments cover low-rank and dense perturbations, full-parameter and LoRA fine-tuning, and multiple model families and scales. The generally favorable results suggest that the complete framework has practical utility. The component ablations, limited five-seed experiments, and small-to-large model hyperparameter transfer provide useful additional evidence.
Critical weaknesses
  1. The contribution of random gating is not sufficiently isolated. Table 5 shows that removing temporal activation or block-wise gating reduces performance. However, these changes also increase the frequency or coverage of momentum guidance. Consequently, the experiments do not distinguish the benefit of random selection from the benefit of using momentum guidance less extensively. Moreover, the central explanation in Section 4.2—that selective exploration mitigates a feedback loop caused by unreliable momentum—is not directly examined through directional diagnostics or controlled momentum-error experiments.
  2. The end-to-end efficiency trade-off remains unclear. Figure 1 provides favorable training-loss curves, and Table 7 reports the additional per-iteration runtime. These are useful measurements, but they do not directly establish the total time required to reach a common quality target. In particular, the efficiency contribution of random gating itself remains unclear relative to guidance schedules with matched activation frequency. This matters because improved query efficiency is an important motivation for the method.
  3. The operating range of the exploration controls is only partially characterized. Table 8 studies the block ratio and guidance strength in one setting, while the activation probability and warmup ratio are fixed throughout the reported experiments. Table 6 provides encouraging evidence for transferring the two searched hyperparameters from a smaller model, but does not establish the robustness of the fixed exploration settings. The practical search burden and the conditions under which exploration helps or reduces optimization efficiency therefore remain uncertain.
Questions for authors
  1. Could you compare random temporal activation and block selection against deterministic periodic activation and block rotation, while matching guidance strength, total activation counts, and block coverage? Such controls would help establish whether randomness itself contributes beyond reducing momentum-guidance exposure.
  2. Could you provide a direct diagnostic of the feedback mechanism described in Section 4.2? For example, a small-model experiment could track gradient-estimate alignment or recovery from deliberately perturbed momentum. It would also be informative to distinguish the effects of random gating when momentum is reliable versus unreliable.
  3. Could you report the optimization steps and wall-clock time required to reach common, attainable loss or validation-performance targets under the same model and hardware configuration? Including activation-frequency-matched controls would clarify whether the gains from selective exploration outweigh its computational and optimization costs.
  4. What empirical basis supports fixing the activation probability at 0.5 and the warmup ratio at 0.05? Representative sensitivity checks would help assess whether these are robust defaults. Please also clarify the actual number of hyperparameter-search trials and their total computational cost, including the small-model proxy search.
7 comments

We sincerely appreciate the reviewer’s detailed and constructive feedback. The points raised are valuable for improving the clarity of our work, and we are glad to aprovide a thorough discussion.

R2-W1 (Part I) & R2-Q1

Thank you for suggesting these controlled comparisons. To investigate the effect of the selection strategy while keeping momentum-guidance exposure fixed, we evaluated two deterministic alternatives. Deterministic temporal activation: Guidance activations are distributed uniformly across post-warmup iterations, with their total count exactly matching that generated by the original MAPS gate at the same seed. Random block selection is retained. Deterministic block rotation: The original random temporal activation sequence is retained, while random block selection is replaced with two fixed, equally sized block groups that alternate at successive active iterations.

Using the hyperparameter configuration of Table 5, deterministic temporal activation and deterministic block rotation achieve 59.72% and 60.19% accuracy, respectively, compared with the 60.50% MAPS result reported in Table 5. MAPS achieves the highest reported accuracy in this comparison, exceeding the two deterministic alternatives by 0.78 and 0.31 percentage points, respectively. Together with the original component ablations, these observations strengthen the empirical motivation for retaining both stochastic temporal activation and random block selection in MAPS. The additional controls extend the ablation study by explicitly evaluating regular selection policies with matched activation counts, per-iteration block coverage, and guidance strength.

R2-W1 (Part II) & R2-Q2

  1. Directional alignment of MAPS perturbations.

    To assess whether the momentum of MAPS is useful for the current sampling step, we computed a first-order reference gradient gtrefg_t^{\mathrm{ref}} by backpropagation on the same OPT-1.3B/WiC minibatch used for the ZO queries. This reference gradient was used only for evaluation. We compared cos⁡(g^tZO,gtref)\cos(\widehat g_t^{\mathrm{ZO}},g_t^{\mathrm{ref}}) and cos⁡(g^tMAPS,gtref)\cos(\widehat g_t^{\mathrm{MAPS}},g_t^{\mathrm{ref}}) at four checkpoints. Our results indicate that the average relative gain in alignment for MAPS over standard ZO was 2.57% and 2.53% in the two paired evaluations.

  2. Directional reliability of momentum and the effect of random gating.

    We further conduct diagnostic experiments to examine how the reliability of historical momentum affects the current ZO estimate and whether random gating can mitigate the negative effects of unreliable guidance.

    We keep all settings identical, including p=0.5. We vary only the temporal activation probability qq, considering three settings: no guidance q=0q=0, always-on guidance q=1q=1, and random gating q=0.5q=0.5, as in MAPS.

    To quantify momentum reliability, we compare the accumulated momentum direction with the current reference gradient on the selected blocks. We classify momentum as more reliable if its squared projection onto the reference gradient exceeds the expected squared projection of a standard Gaussian perturbation, and less reliable otherwise.

    At nine checkpoints, we evaluated eight minibatches using 32 Gaussian perturbations per minibatch shared across gating settings. The following table reports average cosine similarities with gtrefg_t^{\mathrm{ref}}, in units of 10−510^{-5}.

    Momentum reliabilityTrialsNo guidance (q=0)Always-on (q=1)Random gating (q=0.5)
    More reliable7652.242562.428532.35919
    Less reliable15392.154142.030192.09338

    Small cosine values are plausible in a high-dimensional parameter space, so we focus on relative differences in alignment across gating strategies under the same evaluation setup. The results reveal two complementary effects:

    • When momentum was more reliable, guiding the selected blocks at every step gave the highest alignment. Relative to the no guidance of 2.24256, always-on guidance increased the average cosine by 0.1860, while random gating increased it by 0.1166. Thus, with a 50% activation probability, MAPS retained approximately 63% of the alignment gain achieved by always-on guidance.

    • When momentum was less reliable, the unguided Gaussian sampler gave the highest alignment. Relative to its average cosine of 2.15414, always-on guidance reduced alignment by 0.1239, while random gating reduced it by 0.0608. MAPS therefore avoided approximately 51% of the alignment loss incurred by always-on guidance.

These results directly examine the feedback mechanism described in Section 4.2. When momentum is reliable, it provides useful directional information for subsequent sampling. However, when momentum is unreliable, repeatedly using it can bias subsequent perturbations toward a less informative direction. Since the resulting ZO estimate contributes to the next momentum update, this bias can be reinforced over successive iterations. Random gating mitigates this effect by occasionally replacing momentum-guided sampling with a fresh Gaussian perturbation independent of the historical momentum direction.

  1. Why retaining random exploration is important.

    The above mechanism can be illustrated by an extreme case. Suppose the initial perturbation is a direction R0\mathbf{R}_0, and the resulting momentum is aligned with it. If all subsequent perturbations fully follow the momentum (λt=1\lambda_t=1) without random exploration or temporal gating, the sampling and momentum updates become St=P~t−1, Pt=βPt−1+(1−β)ctSt.\mathbf{S}_t=\widetilde{\mathbf{P}}_{t-1},~ \mathbf{P}_t=\beta\mathbf{P}_{t-1}+(1-\beta)c_t\mathbf{S}_t. Consequently, all subsequent perturbations remain within the subspace spanned by the initial direction, i.e., St∈span⁡(R0).\mathbf{S}_t\in\operatorname{span}(\mathbf{R}_0).

    The search is then restricted to directions determined by the initial perturbation, preventing exploration of other potentially useful directions. Although this is an extreme case, it illustrates how repeatedly relying on historical momentum can reinforce directional bias. MAPS avoids this extreme behavior by retaining fresh random perturbations through periodically disabling momentum guidance through random temporal gating. Block-wise gating further preserves unguided exploration across parameter block.

    This interpretation is also supported by our existing sensitivity results. In Table 8, setting λmax⁡=1\lambda_{\max}=1 does not achieve the best accuracy or training loss. The highest accuracy is obtained with λmax⁡=0.3\lambda_{\max}=0.3, while the lowest training loss is obtained with λmax⁡=0.5\lambda_{\max}=0.5. This indicates that stronger momentum guidance does not necessarily lead to better optimization, highlighting the importance of balancing momentum exploitation with random exploration.

    Finally, the matched frequency controls in our response to Q1 address a complementary question: does the choice of when and where to apply guidance affect final accuracy when the number of activations is fixed? Under the Table 5 configuration, evenly deterministic temporal activation yielded 59.72% accuracy, and deterministic block rotation yielded 60.19%, compared with the 60.50% MAPS. These comparisons show that the benefit of MAPS is not explained solely by applying momentum guidance less frequently or to fewer blocks.

In general, these results support the role of random gating in balancing momentum exploitation and stochastic exploration.

R2-W2 & R2-Q3

To assess whether MAPS’s additional per-step computational overhead is offset by fewer optimization steps and shorter training time, we provide additional comparisons of the steps and cumulative training time required to reach common training loss and downstream-performance targets.

The experiments use SQuAD with OPT-1.3B, a batch size of 16, and the same RTX PRO6000 GPU. All methods share the same data splits and evaluation protocol, with an input sequence-length cap of 2048 tokens. We use the performance of the MAPS-LOZO-M reference run at 10K steps to define two common targets: F1 ≥ 76.0764 and training loss ≤ 0.5222. All times below represent cumulative training time, excluding initialization, evaluation, and checkpoint saving. The MAPS-LOZO-M result at 10K steps is a reference point at which the targets have been reached. For the other methods, we report the first checkpoint observed to reach each target. The results are presented below:

MethodSteps to F1 targetTraining timeSteps to loss targetTraining timePeak memory (GiB)
LOZO-MNot reached by 2000056.81 min1610045.78 min3.1
MAPS-LOZO-M1000029.77 min1000029.77 min3.1
ZO-Adam2000077.58 min1070041.49 min12.9
MAPS-ZO-Adam1900076.97 min970039.31 min12.9
  • MAPS demonstrates a clear advantage in reaching the targets with the low-rank ZO optimizer.

    For the F1 target, MAPS-LOZO-M achieves 76.0764 at 10K steps, with 29.77 minutes of cumulative training time. Under the same 10K-step budget, LOZO-M achieves an F1 score of 70.1734. Even after extending training to 20K steps and 56.81 minutes, LOZO-M still does not reach the target. Both methods have the same peak memory usage of approximately 3.1 GiB, showing that MAPS improves downstream performance within a limited training budget while preserving the same memory footprint.

    For the training loss target, MAPS-LOZO-M has already reached the threshold at its 10K-step reference point, taking 29.77 minutes. LOZO-M is first observed to reach it at 16100 steps, taking 45.78 minutes. Comparing these two results, MAPS uses approximately 37.9% fewer update steps and 35.0% less cumulative training time. This demonstrates that, for this target, the optimization progress enabled by MAPS offsets its additional per-step overhead and translates into actual training-time savings.

  • This benefit also extends to dense ZO-Adam.

    To reach the same training loss threshold, MAPS-ZO-Adam requires 9700 steps and 39.31 minutes, compared with 10700 steps and 41.49 minutes for ZO-Adam. These correspond to approximately 9.3% fewer training steps and 5.3% less training time, with both methods using 12.9 GiB of peak memory.

    For the common F1 target, MAPS-ZO-Adam is first observed to reach it at 19K steps, compared with 20K steps for ZO-Adam, with cumulative training times of 76.97 and 77.58 minutes, respectively. Thus, the magnitude of the benefit varies with the base optimizer and target metric. Both MAPS instances improve the number of steps and training time required to reach the common training loss target.

Regarding the deterministic controls with matched activation frequency, our response to Q1 includes experiments with deterministic temporal activation and fixed block rotation, matching the guidance strength, activation count, and number of guided blocks per active iteration. These experiments examine the final performance of different gating strategies under a fixed training budget, while the SQuAD experiments above measure the target-reaching efficiency of the complete MAPS framework relative to its base optimizers.

Taken together, these additional experiments extend the evidence for MAPS’s benefits from training loss curves and per-step overhead to the training steps, function query budgets, and cumulative training time required to reach common targets. In particular, MAPS-LOZO-M achieves higher downstream performance and reduces the training time required to reach the common training loss target while maintaining the same memory footprint, demonstrating the practical optimization value of the improved perturbation sampling strategy.

R2-W3 & R2-Q4

We thank the reviewer for highlighting the need to clarify the empirical basis for the fixed exploration parameters and the cost of hyperparameter search. We provide further clarification and corresponding empirical evidence below.

  1. Empirical justification of the default exploration settings.

    In MAPS, the activation probability qq controls how frequently momentum guidance is activated after warmup, while the warmup ratio ρ\rho determines the initial training period used to accumulate momentum before applying guidance. Our default settings, q=0.5q=0.5 and ρ=0.05\rho=0.05, allow both momentum-guided sampling and random exploration throughout training, while providing an initial period for momentum accumulation.

    To evaluate these defaults, we conducted a sensitivity analysis on WiC with OPT-1.3B, varying one parameter at a time while fixing the other at its default value. Each configuration was trained for 10K steps using three random seeds.

    Fixed ρ=0.05\rho=0.05Fixed q=0.5q=0.5
    Parameter valueq=0.2q=0.2q=0.5q=0.5q=0.6q=0.6ρ=0\rho=0ρ=0.05\rho=0.05ρ=0.1\rho=0.1ρ=0.5\rho=0.5
    Average Acc. (%)57.9958.2058.0557.5258.2057.3157.63

    As shown in this table, q=0.5q=0.5 achieves the highest average accuracy among the tested activation probabilities, with the three configurations differing by at most 0.21%. Similarly, ρ=0.05\rho=0.05 achieves the highest average accuracy among the tested warmup ratios. These results support q=0.5q=0.5 and ρ=0.05\rho=0.05 as the optimal defaults within the evaluated ranges.

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

The paper proposes MAPS, a momentum-based zeroth-order optimizer. It normalizes the existing momentum to the Gaussian perturbation scale, mixes it with random exploration, and selectively activates guidance across blocks and iterations. It is tested with LOZO-M and ZO-Adam, including LoRA, on OPT, Qwen, and Llama models. The method achieves considerable gains over ZO baselines. The reported peak memory stays the same, while each step takes longer.

Critical strengths
  1. The idea is simple and makes good use of information the optimizer already has. It does not require extra loss evaluations, and it works with both low-rank and dense perturbations. This seems like a useful change for someone already using a momentum-based ZO optimizer.
  2. The gains are reasonably consistent across the settings tested.
Critical weaknesses
  1. My main question is when the improved ZO optimizer becomes a useful training choice in practice. Saving memory is one of the possible motivations. Table 7 reports memory and step time against the ZO baselines, but it does not show the comparison with first-order full fine-tuning or LoRA. Table 1 includes first-order scores from prior work, with 2,000 training steps versus 20,000 for ZO. These numbers do not tell the time needed to reach a similar score, or how much memory is saved under a common setup. The improvement over existing ZO methods is useful, but the practical usefulness is still hard to judge.
  2. The paper discusses prior guided sampling methods, including ZO-AdaMU, which already uses momentum to shape perturbations. The innovation of the method is hard to evaluate.
  3. According to Table 4, the mean gains are fairly small relative to the run-to-run variation.
Questions for authors
  1. Could you show a representative setting, with a stated GPU memory limit, model size, and sequence length, where MAPS can fine-tune the model but first-order LoRA or full fine-tuning cannot? If both fit, what are their peak memory and total time to reach a comparable downstream score? It's true that ZO cannot win in every setting; I would like a clearer picture of when it is worth using.
  2. Compared to prior guided sampling methods, such as ZO-AdaMU, I see the main contribution of this method as making the "momentum-guided sampling" idea easy to reuse across optimizers. Could the authors further clarify which part gives the improvement over existing momentum-guided sampling, and compare them under the same training setting?
6 comments

Thank you for the thoughtful and balanced assessment of our work. Your comments on applicability, the distinction from prior methods are valuable, and we address them below.

R1-W1 & R1-Q1

Both questions involve the practical trade-off between memory efficiency and training performance. To address this concern, we provide two complementary evaluations: a comparison with first-order full-parameter fine-tuning and LoRA under a common hardware and training setup, focusing on peak memory and per-step runtime; and a comparison of the time required by different methods to reach matched downstream performance and training-loss targets.

  1. We have added a comparison with first-order full-parameter fine-tuning and LoRA under the same settings. We chose OPT-13B and OPT-30B with batch size 4 and no gradient accumulation on one 96 GB NVIDIA RTX PRO 6000. The sequence length cap is 1024 for MultiRC. We report peak allocated GPU memory and per-iteration wall-clock time.

    OPT-13BOPT-30B
    MethodMem. (GiB)Time (ms/step)Mem. (GiB)Time (ms/step)
    LOZO-M25.0970.457.32237.9
    MAPS-LOZO-M25.0975.757.32240.8
    ZO-Adam72.51602.7OOM—
    MAPS-ZO-Adam72.51694.4OOM—
    ZO-Adam (LoRA)24.8712.057.01526.9
    MAPS-ZO-Adam (LoRA)24.8719.457.01531.4
    AdamOOM—OOM—
    Adam (LoRA)58.2729.9OOM—

    On OPT-13B, all six ZO methods and first-order LoRA completed the benchmark. Full-parameter Adam ran out of memory. First-order LoRA was faster per step than MAPS-LOZO-M (729.9 vs. 975.7 ms), but used more than twice the peak memory (58.2 vs. 25.0 GiB).

    On OPT-30B, MAPS-LOZO-M and MAPS-ZO-Adam (LoRA) achieved peak memory usage of 57.3 GiB and 57.0 GiB, respectively. In contrast, both full-parameter Adam and first-order LoRA ran out of memory on a single GPU. This demonstrates that both MAPS variants can operate within the memory budget of a single GPU, whereas the first-order baselines exceed it.

    MAPS adds negligible peak memory overhead to its ZO backbones. On a single 96 GB GPU, this allows MAPS-LOZO-M to fine-tune OPT-30B, where even first-order LoRA runs out of memory. The memory savings become especially valuable for larger models.

  2. We also measure training time to common F1 and training loss targets on SQuAD. We use OPT-1.3B, batch size 16, and the same GPU. All methods share the data splits and evaluation protocol. The sequence-length cap is 2048 tokens.

    The targets are F1 ≥ 76.0764 and training loss ≤ 0.5222.

    MethodSteps to F1 targetTraining timeSteps to loss targetTraining timePeak memory (GiB)
    LOZO-MNot reached by 2000056.81 min1610045.78 min3.1
    MAPS-LOZO-M1000029.77 min1000029.77 min3.1
    ZO-Adam2000077.58 min1070041.49 min12.9
    MAPS-ZO-Adam1900076.97 min970039.31 min12.9
    Adam256.00 s256.00 s38.0
    Adam (LoRA)20024.98 s20024.98 s20.6

    For F1, MAPS-LOZO-M achieves 76.0764 at 10K steps, with 29.77 min of cumulative training time and 3.1 GiB peak allocated memory. Under the same 10K budget, LOZO-M achieves 70.1734 F1. Even after 20K steps and 56.81 min of training, LOZO-M does not reach the target. Both methods have the same peak memory. This shows that MAPS improves the downstream performance of the low-rank ZO optimizer while preserving its low memory footprint. First-order methods exceed the F1 target much faster. Full-parameter Adam is first observed to exceed the target at step 25, with 6 s of training and 38.0 GiB peak memory. Adam-LoRA first exceeds it at step 200, with 24.98 s and 20.6 GiB. Thus, first-order methods are substantially faster when memory permits in this setting. MAPS-LOZO-M offers lower memory requirements, its peak memory is 91.9% lower than full-parameter FT and 84.9% lower than first-order LoRA.

    For the training loss, MAPS-LOZO-M meets the target at the 10K steps, taking 29.77 min. LOZO-M is first observed to meet it at step 16100, taking 45.78 min. The MAPS therefore requires approximately 35.0% less cumulative training time. The benefit also extends to dense ZO-Adam, although the gain is smaller. To meet the same training loss threshold, MAPS-ZO-Adam requires 9700 steps and 39.31 min, compared with 10700 steps and 41.49 min for ZO-Adam. This corresponds to 9.3% fewer training steps and 5.3% less training time. Both methods use 12.9 GiB peak memory.

These experiments clarify the practical scope of MAPS. We acknowledge that first-order methods reach the target faster when sufficient memory is available. When memory constraints favor zeroth-order fine-tuning, MAPS can improve the performance and training efficiency of existing ZO optimizers while preserving their low memory footprint. The efficiency gains depend on the target metric. The low memory requirements primarily come from zeroth-order training and its parameter representation. MAPS contributes an improved perturbation sampling strategy.

R1-W2 & R1-Q2

Thank you for highlighting the relationship to prior guided sampling methods. We clarify the differences between MAPS and ZO-AdaMU below, followed by experimental comparisons.

  1. ZO-AdaMU and MAPS use different historical states for different purposes.

    MAPS combines existing-state reuse, norm calibration, and selective guidance. It separates perturbation sampling from the base optimizer’s update rules. ZO-AdaMU jointly designs perturbation history, sampling, and adaptive updates. Using its notation, Eq. (4) constructs

    z˙t+1∼N(0,αt+1),z¨t+1∼N(mt,1−αt+1),\dot{\mathbf{z}}_{t+1} \sim \mathcal{N}(\mathbf{0}, \sqrt{\alpha_{t+1}}), \qquad \ddot{\mathbf{z}}_{t+1} \sim \mathcal{N} (\mathbf{m}_t, \sqrt{1-\alpha_{t+1}}),

    mt+1=β1z˙t+1+(1−β1)z¨t+1.\mathbf{m}_{t+1} = \beta_1\dot{\mathbf{z}}_{t+1} + (1-\beta_1)\ddot{\mathbf{z}}_{t+1}.

    Here, mt\mathbf{m}_t is its perturbation history state. ZO-AdaMU also constructs an adaptive scaling term from the squared samples. Its simulated annealing schedule controls αt\alpha_t, β1,t\beta_{1,t}, and β2,t\beta_{2,t}. ZO-AdaMU can thus be viewed as a specific improved version of zeroth-order Adam that couples momentum-guided perturbation sampling with adaptive parameter updates[1].

    MAPS instead asks whether an existing optimizer’s directional state can improve subsequent sampling while preserving its update rules. Its guidance state P\mathbf{P} is available before the current function queries. Examples include the first moment of ZO-Adam and the low-rank momentum of LOZO-M. MAPS does not introduce a separate perturbation history recurrence. For ZO-Adam, MAPS uses its first moment as P\mathbf{P} and constructs the dense perturbation S=z\mathbf{S}=\mathbf{z}. The first-moment, second-moment, and parameter-update rules remain unchanged. For LOZO-M, MAPS uses its low-rank momentum P=N\mathbf{P}=\mathbf{N} to guide the left factor S=U\mathbf{S}=\mathbf{U}. The perturbation remains UV⊤\mathbf{U}\mathbf{V}^{\top}. The refresh of V\mathbf{V}, momentum projection, and subsequent updates remain those of LOZO-M. MAPS provides a more generic sampling rule and is applicable to any ZO optimizer whose existing momentum provides a direction in its perturbation space.

  2. MAPS calibrates the momentum norm to decouple guidance strength from its raw magnitude.

    Direct mixing makes the effective guidance strength depend on the raw momentum magnitude. This magnitude can vary across optimizers, parameter blocks, and training stages. MAPS first matches its scale to Gaussian exploration. Our Eq. (5) defines

    P~=dPmax⁡∥P∥F,ϵ,S=1−λR+λP~,λ∈[0,1],\widetilde{\mathbf{P}} = \sqrt{d} \frac{\mathbf{P}}{\max\\{\lVert \mathbf{P}\rVert_F, \epsilon\\}}, \quad \mathbf{S} = \sqrt{1 - \lambda} \mathbf{R} + \sqrt{\lambda} \widetilde{\mathbf{P}}, \quad \lambda \in [0, 1],

    where R∼N(0,Id)\mathbf{R}\sim\mathcal{N}(\mathbf{0},\mathbf{I}_d) and dd is the dimension of the perturbation representation. And for valid momentum, E[∥S∥F2∣P]=d\mathbf{E}[\lVert \mathbf{S}\rVert_F^2\mid\mathbf{P}]=d. Thus, MAPS changes the directional distribution while preserving the expected squared norm. The coefficient λ\lambda controls the balance between random exploration and momentum guidance. The normalized state is used only for sampling.

    Selective momentum guidance through block-wise and temporal gating.

    ZO-AdaMU uses simulated annealing to adjust its sampling coefficients across training stages. MAPS explicitly controls which parameter blocks receive guidance and which iterations activate it, as described in Section 4.2. Block-wise gating applies momentum guidance to a randomly selected subset of parameter blocks. The remaining blocks retain the original random sampler. Temporal gating uses unguided sampling during warmup and randomly activates guidance afterward. Thus, random exploration is retained across both blocks and iterations throughout training. These mechanisms aim to reduce repeated reinforcement of inaccurate historical directions while exploiting useful momentum information. They modify only perturbation sampling and preserve the base optimizer’s update rules and two-query budget.

  1. Component ablations and comparison under a common training protocol.

    Table 5 evaluates individual sampling components while keeping the LOZO-M backbone and training settings fixed. The complete sampler outperforms the ablated variants. These results support both calibrating the relative scale of momentum and random perturbations, and retaining unguided exploration across blocks and iterations. They provide evidence that the gains depend on how momentum is incorporated into sampling, beyond simply reusing the optimizer state.

    We also compare the optimizers on WiC with OPT-1.3B, batch size 16, and 10K training steps. All methods share the same device, the data splits, evaluation protocol, and two training loss queries per step. We selected three random seeds for the comparison, and the results are shown in the table below.

    MethodRun 1Run 2Run 3Mean ± SD
    LOZO-M59.5655.8058.9358.10 ± 2.02
    MAPS-LOZO-M59.7257.3758.9358.67 ± 1.20
    ZO-AdaMU57.6857.9955.6457.11 ± 1.28

    MAPS-LOZO-M improves mean accuracy by 1.57 percentage points over ZO-AdaMU and 0.57 points over LOZO-M in this setting.

Overall, MAPS contributes a general sampling design. It calibrates existing momentum states and selectively uses them across parameter blocks and training iterations. It preserves the base optimizer’s update rules, whereas ZO-AdaMU jointly designs perturbation history and adaptive updates. Our experiments further support the advantages of MAPS in the evaluated setting.

R1-W3

Thank you for raising this concern. We would like to clarify the practical significance of MAPS from three aspects: experimental coverage, performance gains relative to established ZO methods, and computational overhead.

  1. Broad experimental evaluation.

    We evaluate MAPS across five model configurations from three model families: OPT-1.3B/13B/30B, Qwen2.5-1.5B, and Llama-3.2-1B. Our evaluation covers up to ten downstream tasks, including classification, multiple-choice, and question-answering tasks. We further instantiate MAPS with both low-rank and dense perturbation representations, covering LOZO-M, ZO-Adam, and ZO-Adam (LoRA). These experiments demonstrate that the improvements are not limited to a single model, task, or optimizer.

  2. Performance gains are meaningful relative to established ZO methods.

    The gains achieved by MAPS are comparable to or larger than those reported by established ZO methods. On OPT-13B, LOZO improves over MeZO-LoRA by an average of 1.28 percentage points, while LOZO-M further improves over LOZO by 0.72 percentage points across evaluated tasks[2]. Similarly, ZO-AdaMU improves over MeZO by 1.32 percentage points across evaluated tasks. Under our evaluation, MAPS-LOZO-M improves over LOZO-M by 1.50 percentage points across the tasks. Moreover, MAPS-ZO-Adam and MAPS-ZO-Adam (LoRA) improve over their respective base optimizers by 1.10 and 1.80 percentage points. These comparisons show that MAPS achieves gains within or above the range of improvements reported by established ZO methods, rather than marginal gains for ZO fine-tuning.

  3. Negligible computational and memory overhead.

    MAPS introduces minimal additional overhead by modifying only the perturbation sampling process. It reuses the momentum states already maintained by the base optimizer, without introducing additional optimizer states, gradient computations, or function evaluations. The original two-point estimation procedure and subsequent optimizer updates remain unchanged. Therefore, MAPS improves perturbation quality without increasing the function evaluation budget or requiring additional optimizer-state storage.

[1] Jiang et al. ZO-AdaMU Optimizer: Adapting Perturbation by the Momentum and Uncertainty in Zeroth-order Optimization. AAAI 2024.
[2] Chen et al. Enhancing Zeroth-Order Fine-Tuning for Language Models with Low-Rank Structures. ICLR 2025.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We sincerely thank all three reviewers for their thoughtful and constructive comments. Their feedback has helped us improve the clarity of our contributions, strengthen our experimental evidence, and better demonstrate the practical value of our work. We have carefully addressed all concerns and revised the manuscript accordingly, with the corresponding changes highlighted in blue.

A Generic and Plug-and-Play Framework.

We propose Momentum-Aware Perturbation Sampling (MAPS), a generic, plug-and-play framework that reuses the momentum states already maintained by existing ZO optimizers to guide subsequent perturbation sampling. Unlike methods that introduce dedicated perturbation history mechanisms or redesign the optimizer, MAPS modifies only the sampling process while preserving the base optimizer's update rules, optimizer states, and the function evaluation budget. It combines norm-calibrated momentum guidance with random exploration and selectively controls guidance across parameter blocks and training iterations.

Broad Applicability and Improved Performance.

We instantiate MAPS with LOZO-M and ZO-Adam, covering both low-rank and dense perturbation representations, as well as full-parameter and LoRA fine-tuning. Extensive experiments across five model configurations from three model families and up to ten downstream tasks demonstrate consistent performance improvements. Additional multi-seed experiments further support the effectiveness and consistency of MAPS.

Practical Efficiency.

We provide additional comparisons with first-order full-parameter fine-tuning and LoRA. We evaluate the cumulative time and memory required to reach common downstream performance and training loss targets. These results are presented in Section 5.2 (Figure 2) and Appendix C.2 (Table 8), providing a clearer assessment of the practical trade-offs between ZO and first-order fine-tuning.

Distinction from Prior Work.

We further clarify the differences from existing guided sampling methods. ZO-AdaMU is a dedicated ZO optimizer that jointly designs perturbation history, sampling, and adaptive updates. ConMeZO uses a cone sampler centered on an EMA of historical ZO gradient estimates, while Guided ES relies on external surrogate gradients to construct a guiding subspace. In contrast, MAPS is a generic, plug-and-play sampling framework that is readily applicable to different ZO optimizers with compatible momentum states. Further methodological distinctions and experimental comparisons are provided in our responses to R1 and R3.

We sincerely thank all three reviewers again for their feedback and suggestions. We believe these revisions strengthen the generality, effectiveness, and practical applicability of MAPS, and we look forward to the upcoming discussion phase.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.