- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper proposes LDSD, a framework that adapts the mean of a Gaussian perturbation distribution in zeroth-order optimization. The method interprets the sampling mean as a policy and seeks to improve expected gradient alignment through policy updates. The paper first analyzes an idealized directional-gradient setting and derives convergence results based on expected alignment, then develops ZO-LDSD, a practical finite-difference version using REINFORCE and multiple sampled candidate directions. Experiments integrate the proposed sampling strategy with ZO-SGD, ZO-AdaMM, and JAGUAR for language-model fine-tuning.
Critical strengths
-
The paper studies an important issue in high-dimensional ZO optimization: isotropic random directions tend to have poor alignment with the true gradient, which can substantially degrade optimization efficiency for large models. Learning the perturbation distribution rather than modifying a particular ZO optimizer is an interesting modular perspective. The proposed mechanism can be integrated with different base optimizers, and the experiments show consistent improvements over their corresponding Gaussian-sampling variants.
-
The paper provides a nontrivial theoretical analysis of expected gradient alignment for an idealized directional-gradient setting. The connection between direction sampling and policy optimization is conceptually interesting. The authors make an effort to control the computational budget in the experiments. In particular, the main comparisons match the total number of forward evaluations, and additional wall-clock experiments are provided.
Critical weaknesses
-
The central theoretical quantity is expected gradient alignment, but the randomness and variance of the actual sampled directions are not sufficiently characterized. The method only learns the mean of while retaining an isotropic covariance. A large value of , where is the squared directional alignment, does not by itself establish that individual sampled directions concentrate around a useful direction or that the practical ZO estimator has low variance. This distinction is particularly important in extremely high dimension, where the isotropic noise component has norm on the order of . I did not find a variance, concentration, or high-probability analysis for the practical sampled ZO estimator under the learned distribution. This issue also appears in the policy update itself. The practical method estimates the policy gradient using REINFORCE with only samples. For , the score term satisfies . Therefore, without further structure, the stochasticity of the policy-gradient estimator can itself grow strongly with dimension. The paper explicitly acknowledges that the accuracy of this Monte Carlo estimate may depend on , but does not provide an analysis showing that remains reliable in the billion-parameter regime.
-
The practical query cost is substantial. With the default , ZO-LDSD requires forward evaluations for each parameter update, compared with 2 evaluations for a standard two-point ZO update. The authors correctly compensate for this in the main experiments by matching the total oracle-call budget, so I do not view the comparison itself as unfair. However, the proposed mechanism still trades approximately three times more queries per optimization step for improved direction selection. This is important for applications where query latency or the number of sequential model evaluations is the main bottleneck. More importantly, the paper discusses recent methods such as ZoAR, which specifically performs policy-inspired variance reduction and query reuse, and LOREN, which also learns anisotropic perturbation distributions, but does not compare against them experimentally. The empirical evaluation is relatively narrow for a paper making broad claims about LLM fine-tuning. The main evaluation uses only SST-2 and COPA, with most ablations, memory measurements, and wall-clock experiments conducted on SST-2. Although several model sizes are considered, the larger-scale experiments use only LoRA. This makes it difficult to assess whether the gains generalize across the diverse reasoning, classification, and generation tasks commonly considered in recent ZO LLM fine-tuning work. In addition, the reported tables do not appear to provide variance across random seeds, which is particularly relevant for a method whose main mechanism is stochastic direction sampling.
Questions for authors
-
Could the authors provide a variance or concentration analysis for the actual sampled update direction under ? In particular, how does the variance of the ZO estimator depend on , , and , beyond the expected squared alignment ?
-
The REINFORCE score satisfies . How does the variance of the resulting policy-gradient estimator scale with for fixed ? Can the authors theoretically or empirically justify why is sufficient when is on the order of billions of parameters?
-
The dimension-independent result requires conditions such as and a constant-level initial alignment, whereas the LLM experiments use . Could the authors report the empirical values of , sampled directional alignment, and during LLM fine-tuning, and explain whether the theoretical regime is relevant to these experiments?
-
Could the authors provide a convergence analysis for the actual Algorithm 2? Specifically, the theoretical algorithm optimizes using exact directional information, while Algorithm 2 uses finite function differences, a REINFORCE estimator based on function values, and an argmin selection over candidates. What guarantees that this practical update improves the same alignment objective considered in Theorems 3.5--3.7?
-
ZO-LDSD uses 6 forward evaluations per parameter update for the default , compared with 2 for standard two-point ZO. Could the authors provide a more detailed query-efficiency comparison with recent methods specifically designed for adaptive sampling or query reuse, particularly ZoAR and LOREN, under the same total oracle-call and wall-clock budgets?
-
Could the authors extend the experiments beyond SST-2 and COPA and report results over multiple random seeds with standard deviations? A broader evaluation would be important for establishing that the learned sampling mechanism generalizes beyond the current small set of downstream tasks.
5 comments
Q3
The dimension-free rate of Lemma 3.7 describes the limit in which the sampling term of (see Q1) is negligible. The decomposition in Q1 predicts how the benefit of the learned mean changes between isotropic sampling and this limit. We therefore measured during fine-tuning and compared ZO-LDSD with Gaussian sampling that uses the same candidates, argmin selection and forward-pass budget, with the mean fixed at . ZO-SGD, three seeds, at the end of training, averaged over seeds:
| Model, task | Gaussian, , argmin | Algorithm 2 | |||
|---|---|---|---|---|---|
| OPT-1.3B prompt tuning, SST-2 | 20,480 | 1 | 0.835 0.046 | 0.851 0.045 | |
| OPT-1.3B prompt tuning, SST-2 | 20,480 | 0.3 | 0.822 0.056 | 0.854 0.042 | |
| OPT-1.3B prompt tuning, Rotten Tomatoes | 20,480 | 0.3 | 0.850 0.011 | 0.869 0.003 | |
| RoBERTa-Large LoRA , SST-2 | 2,048 per matrix | 0.1 | 0.840 0.033 | 0.885 0.015 | |
| RoBERTa-Large LoRA , SST-2 | 1,024 per matrix | 0.1 | 0.856 0.025 | 0.904 0.007 |
For OPT-1.3B we report validation accuracy of the selected checkpoint, as in our response to Reviewer 3Rdk (third point), and for RoBERTa-Large test accuracy. We scale to keep fixed across .
For direct comparison, the table below reports the sampling term and accuracy gain, grouped by fine-tuning method as in Table 9 (page 36) of the revised manuscript.
| Model, task | Sampling term | Algorithm 2 - Gaussian (p.p.) | |
|---|---|---|---|
| OPT-1.3B prompt tuning | |||
| OPT-1.3B prompt tuning, SST-2 | 1 | +1.6 | |
| OPT-1.3B prompt tuning, Rotten Tomatoes | 0.3 | +1.9 | |
| OPT-1.3B prompt tuning, SST-2 | 0.3 | +3.2 | |
| RoBERTa-Large LoRA | |||
| RoBERTa-Large LoRA , SST-2 | 0.1 | +4.5 | |
| RoBERTa-Large LoRA , SST-2 | 0.1 | +4.8 |
As shown in the second table, within each model and task, the advantage of the learned mean over isotropic sampling with the same selection grows as the sampling term decreases, as the decomposition in Q1 predicts. The fine-tuning experiments therefore lie in the intermediate regime between isotropic sampling and the limit of Lemma 3.7, which is reached on the problem of Section 3.6 where the exact gradient is available (Figure 2, page 6), and the observed trend points towards that limit. These measurements and the hyperparameters of each run are reported in Appendix F (pages 35-36) of the revised manuscript.
Q4
The revised manuscript extends the theory to finite-difference ZO updates and inexact stochastic policy updates in Appendix E (pages 30-35). The proofs explicitly track the resulting errors:
- Lemmas E.1-E.2 (pages 30-31) bound finite-difference bias and establish descent.
- Theorem E.1 and Lemma E.3 (pages 31-33) control alignment over one step and along the trajectory.
- Lemmas E.4-E.5 (page 34) derive convergence guarantees for both initialization regimes.
- Section E.3, Discussion (page 35), explains the target-accuracy dependence, the finite-difference residual, and the policy-noise assumptions, including a high-probability extension to unbounded noise.
For the reviewer's convenience, all additions in the revised manuscript are highlighted in blue. Greedy direction selection is evaluated separately in the existing ablation in Section 5.4 (page 8, Figure 3(d) on page 9). Under the same forward-pass budget, it compares learned sampling with averaging and with argmin selection, separating the contribution of selection from that of learning the direction.
Q5
Following the reviewer's suggestion, we added comparisons with LOREN [1] and ZoAR [2]. The results are included in Table 1 of the revised manuscript (page 8) and reproduced below for convenience (the new results are shown in the last two rows).
| Method | Sampling | OPT-1.3B FT | OPT-1.3B LoRA | RoBERTa-Large FT | RoBERTa-Large LoRA |
|---|---|---|---|---|---|
| ZO-SGD | Gaussian, , more iterations | 0.928 | 0.854 | 0.899 | 0.913 |
| ZO-SGD | Gaussian, , same iterations | 0.919 | 0.850 | 0.869 | 0.905 |
| ZO-SGD | Algorithm 2 | 0.935 | 0.916 | 0.909 | 0.928 |
| ZO-AdaMM | Gaussian, , more iterations | 0.925 | 0.912 | 0.909 | 0.812 |
| ZO-AdaMM | Gaussian, , same iterations | 0.917 | 0.905 | 0.899 | 0.801 |
| ZO-AdaMM | Algorithm 2 | 0.930 | 0.929 | 0.917 | 0.900 |
| JAGUAR | Gaussian, , more iterations | 0.925 | 0.921 | 0.906 | 0.905 |
| JAGUAR | Gaussian, , same iterations | 0.914 | 0.911 | 0.896 | 0.893 |
| JAGUAR | Algorithm 2 | 0.930 | 0.928 | 0.922 | 0.927 |
| ZoAR | Gaussian, , , more iterations | 0.930 | 0.903 | 0.920 | 0.913 |
| LOREN | Low-rank curvature, 6 forwards, same iterations | 0.935 | 0.844 | 0.869 | 0.920 |
The best results obtained with our sampling strategy match or exceed both ZoAR and LOREN in all four configurations.
As the reviewer notes, comparisons use a fixed total query budget. We emphasize that even in query-constrained settings, query efficiency is determined by the quality reached within that total budget. Therefore, six evaluations per step are beneficial when they yield higher quality for the same total number of calls. Additionally, LOREN uses multiple evaluations per iteration and reports optimal performance with the same six-call budget.
Q6
We agree that evaluation on broader tasks would be beneficial. However, within a resource-constrained research environment, our evaluation follows established practice in literature. The LLM experiments of Ma and Huang [3] use OPT-1.3B on SST-2, a strict subset of our model-task coverage. Zhang et al. [4] study RoBERTa-Large on SST-2, SST-5, and TREC. Both appeared at NeurIPS 2025. Our evaluation complements these settings with multiple model scales, a joint study of full fine-tuning and LoRA, and several underlying ZO optimizers. We additionally evaluated Rotten Tomatoes [5] with prompt tuning of OPT-1.3B (Appendix F, Table 10, three seeds, validation accuracy of the selected checkpoint): Algorithm 2 reaches , compared with for Gaussian sampling with and more iterations and for Gaussian sampling with and argmin selection.
We sincerely thank the reviewer for their thoughtful questions, which prompted substantial additional work and significantly strengthened both the theoretical analysis and the experimental evidence. We believe our responses address all of their concerns and hope that these improvements will support a higher evaluation of our work.
References
- Low-Rank Curvature for Zeroth-Order Optimization in LLM Fine-Tuning, Seung et al., AAAI2026.
- Zeroth-Order Optimization is Secretly Single-Step Policy Optimization, Qiu et al., ICML2025 Workshop.
- On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization, Ma and Huang, NeurIPS2025.
- Zeroth-Order Optimization Finds Flat Minima, Zhang et al., NeurIPS2025.
- Seeing Stars: Exploiting Class Relationships for Sentiment Categorization with Respect to Rating Scales, Pang and Lee, ACL2005.
Dear Reviewer Pdqp,
We sincerely thank the reviewer for the time devoted to the review and their attention to our work. Below, we address their questions point by point.
Q1
Alignment is central because it directly controls descent in Lemma 3.3. Moreover, Corollary 3.4 explicitly recovers the dimension factor from E[Ct]=1/d under isotropic Gaussian sampling.
Beyond the expected gradient alignment, for the directional estimator gxt=vt⟨vt,∇f(xt)⟩, corresponding to the τ→0 ZO limit, the variance at fixed d as ε/∥μt∥→0 satisfies
E∥gxt−Egxt∥2∼∥∇f(xt)∥2∥μt∥2ε2[(d−1)cos2βt+sin2βt].
All expectations here are conditional on the current iterate and policy. Since the estimator is biased, low variance alone does not ensure agreement with the true gradient. Its relative mean squared error is more informative and, by the projection structure, equals the alignment deficit exactly:
∥∇f(xt)∥2E∥gxt−∇f(xt)∥2=1−E[Ct]=sin2βt+∥μt∥2ε2[(d−1)cos2βt−sin2βt]+Od(∥μt∥4ε4).
If also βt→0, this gives the shared decomposition
=\frac{\mathbb E\lVert g_x^t-\nabla f(x^t)\rVert^2} {\lVert\nabla f(x^t)\rVert^2} \sim \underset{\text{angular error}}{\underbrace{(\beta^t)^2}} + \underset{\text{sampling error}}{\underbrace{(d-1)\frac{\varepsilon^2}{\lVert\mu^t\rVert^2}}}.$$ Thus, high alignment and accurate gradient estimation require the same two properties: a small angle between $\mu^t$ and the gradient, and strong sampling concentration controlled by $\varepsilon/\|\mu^t\|$. This is fully consistent with the discussion of distribution parameterization on page 4, lines 173-188, where the mean controls both the preferred direction (through mean direction) and sampling concentration (through mean norm). We therefore respectfully disagree with the following statement in the Weaknesses: "A large value of $\mathbb E[C^t]$, where $C^t$ is the squared directional alignment, does not by itself establish that individual sampled directions concentrate around a useful direction or that the practical ZO estimator has low variance." The analysis above links high alignment directly to low relative mean squared error. **Q2** The paper includes an ablation of the number of sampled directions $K$ in Section 5.4 (page 8, Figure 3(a) on page 9). Using ZO-SGD on SST-2 with RoBERTa-Large and LoRA, we vary $K$ from 1 to 6. Accuracy improves up to $K=5$ and then slightly declines at $K=6$. Thus, the ablation identifies an empirical optimum at $K=5$ (6 forward passes), supporting the default used in our experiments. Interestingly, LOREN [1], also highlighted by the reviewer and using multiple queries per step, reports optimal performance with the same six forward evaluations per iteration.