acceptodds
Under review as a conference paper at ICLR 2027

Zero-Order Optimization via Learnable Direction Sampling for LLM Fine-Tuning

Abstract

Zeroth-order (ZO) optimization estimates gradients through function evaluations along sampled perturbation directions. Standard isotropic sampling yields weak expected gradient alignment, limiting estimator quality and introducing dimension-dependent convergence rates. We propose a plug-and-play framework that learns the perturbation distribution to improve directional alignment. Our design follows from a descent bound that identifies expected gradient alignment as the objective for adapting the mean of a Gaussian sampling distribution. For an idealized directional algorithm with exact policy updates, we characterize the evolution of alignment and derive convergence guarantees with no explicit dimension dependence. Building on this formulation, we develop a practical finite-difference algorithm that updates the sampling policy using REINFORCE estimates and integrates with existing ZO optimizers. The resulting framework is particularly relevant to large language model (LLM) fine-tuning, where avoiding backpropagation reduces training memory requirements. Experiments demonstrate consistent improvements across models, ZO optimizers, and fine-tuning schemes under matched forward-evaluation budgets, supporting learned direction sampling as an effective mechanism for improving ZO fine-tuning. Our code is available at [https://anonymous.4open.science/r/zo_ldsd](https://anonymous.4open.science/r/zo_ldsd).

Primary area:
optimization
Keywords:
memory-efficient fine-tuning, forward-only optimization, adaptive perturbation sampling, zeroth-order optimization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_PdqpOpenReview ↗
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
  1. 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.

  2. 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
  1. 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 μt\mu_t of vt∼N(μt,ϵ2I)v_t \sim \mathcal{N}(\mu_t,\epsilon^2 I) while retaining an isotropic covariance. A large value of E[Ct]\mathbb{E}[C_t], where CtC_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. This distinction is particularly important in extremely high dimension, where the isotropic noise component has norm on the order of ϵd\epsilon\sqrt{d}. 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 K=5K=5 samples. For v−μ∼N(0,ϵ2I)v-\mu \sim \mathcal{N}(0,\epsilon^2 I), the score term (v−μ)/ϵ2(v-\mu)/\epsilon^2 satisfies E∥(v−μ)/ϵ2∥2=d/ϵ2\mathbb{E}\| (v-\mu)/\epsilon^2 \|^2 = d/\epsilon^2. 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 dd, but does not provide an analysis showing that K=O(1)K=O(1) remains reliable in the billion-parameter regime.

  2. The practical query cost is substantial. With the default K=5K=5, ZO-LDSD requires K+1=6K+1=6 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
  1. Could the authors provide a variance or concentration analysis for the actual sampled update direction under vt∼N(μt,ϵ2I)v_t \sim \mathcal{N}(\mu_t,\epsilon^2 I)? In particular, how does the variance of the ZO estimator depend on dd, ϵ\epsilon, and ∥μt∥\|\mu_t\|, beyond the expected squared alignment E[Ct]\mathbb{E}[C_t]?

  2. The REINFORCE score satisfies E∥(v−μ)/ϵ2∥2=d/ϵ2\mathbb{E}\|(v-\mu)/\epsilon^2\|^2=d/\epsilon^2. How does the variance of the resulting policy-gradient estimator scale with dd for fixed KK? Can the authors theoretically or empirically justify why K=5K=5 is sufficient when dd is on the order of billions of parameters?

  3. The dimension-independent result requires conditions such as ϵ=O(d−3/2M)\epsilon=O(d^{-3/2}M) and a constant-level initial alignment, whereas the LLM experiments use ϵ=1\epsilon=1. Could the authors report the empirical values of ∥μt∥/(ϵd)\|\mu_t\|/(\epsilon\sqrt{d}), sampled directional alignment, and E[Ct]\mathbb{E}[C_t] during LLM fine-tuning, and explain whether the theoretical regime is relevant to these experiments?

  4. Could the authors provide a convergence analysis for the actual Algorithm 2? Specifically, the theoretical algorithm optimizes E[Ct]\mathbb{E}[C_t] using exact directional information, while Algorithm 2 uses finite function differences, a REINFORCE estimator based on function values, and an argmin selection over KK candidates. What guarantees that this practical update improves the same alignment objective considered in Theorems 3.5--3.7?

  5. ZO-LDSD uses 6 forward evaluations per parameter update for the default K=5K=5, 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?

  6. 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

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\mathbb E[C^t]=1/d under isotropic Gaussian sampling.

Beyond the expected gradient alignment, for the directional estimator gxt=vt‾⟨vt‾,∇f(xt)⟩g_x^t=\overline{v^t}\langle\overline{v^t},\nabla f(x^t)\rangle, corresponding to the τ→0\tau\to0 ZO limit, the variance at fixed dd as ε/∥μt∥→0\varepsilon/\|\mu^t\|\to0 satisfies

E∥gxt−Egxt∥2∼∥∇f(xt)∥2ε2∥μt∥2[(d−1)cos⁡2βt+sin⁡2βt].\mathbb E\|g_x^t-\mathbb E g_x^t\|^2\sim\|\nabla f(x^t)\|^2\frac{\varepsilon^2}{\|\mu^t\|^2}\left[(d-1)\cos^2\beta^t+\sin^2\beta^t\right].

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:

E∥gxt−∇f(xt)∥2∥∇f(xt)∥2=1−E[Ct]=sin⁡2βt+ε2∥μt∥2[(d−1)cos⁡2βt−sin⁡2βt]+Od(ε4∥μt∥4).\boxed{\frac{\mathbb E\|g_x^t-\nabla f(x^t)\|^2}{\|\nabla f(x^t)\|^2}=1-\mathbb E[C^t]}=\sin^2\beta^t+\frac{\varepsilon^2}{\|\mu^t\|^2}\left[(d-1)\cos^2\beta^t-\sin^2\beta^t\right]+O_d\left(\frac{\varepsilon^4}{\|\mu^t\|^4}\right).

If also βt→0\beta^t\to0, 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.

Q3

The dimension-free rate of Lemma 3.7 describes the limit in which the sampling term (d−1)ε2/∥μt∥2(d-1)\varepsilon^2/\|\mu^t\|^2 of 1−E[Ct]1-\mathbb E[C^t] (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 ∥μt∥\|\mu^t\| during fine-tuning and compared ZO-LDSD with Gaussian sampling that uses the same K=5K=5 candidates, argmin selection and forward-pass budget, with the mean fixed at μ=0\mu=0. ZO-SGD, three seeds, ∥μT∥\|\mu^T\| at the end of training, averaged over seeds:

Model, taskddε\varepsilon∥μT∥/(εd)\|\mu^T\|/(\varepsilon\sqrt d)Gaussian, K=5K=5, argminAlgorithm 2
OPT-1.3B prompt tuning, SST-220,48014.3⋅10−34.3\cdot10^{-3}0.835 ±\pm 0.0460.851 ±\pm 0.045
OPT-1.3B prompt tuning, SST-220,4800.31.4⋅10−21.4\cdot10^{-2}0.822 ±\pm 0.0560.854 ±\pm 0.042
OPT-1.3B prompt tuning, Rotten Tomatoes20,4800.31.2⋅10−21.2\cdot10^{-2}0.850 ±\pm 0.0110.869 ±\pm 0.003
RoBERTa-Large LoRA r=2r=2, SST-22,048 per matrix0.11.1⋅10−21.1\cdot10^{-2}0.840 ±\pm 0.0330.885 ±\pm 0.015
RoBERTa-Large LoRA r=1r=1, SST-21,024 per matrix0.11.7⋅10−21.7\cdot10^{-2}0.856 ±\pm 0.0250.904 ±\pm 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 γx∼1/ε2\gamma_x\sim1/\varepsilon^2 to keep γxε2\gamma_x\varepsilon^2 fixed across ε\varepsilon.

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ε\varepsilonSampling termAlgorithm 2 - Gaussian (p.p.)
OPT-1.3B prompt tuning
OPT-1.3B prompt tuning, SST-215.41⋅1045.41\cdot10^4+1.6
OPT-1.3B prompt tuning, Rotten Tomatoes0.36.94⋅1036.94\cdot10^3+1.9
OPT-1.3B prompt tuning, SST-20.35.10⋅1035.10\cdot10^3+3.2
RoBERTa-Large LoRA
RoBERTa-Large LoRA r=2r=2, SST-20.18.26⋅1038.26\cdot10^3+4.5
RoBERTa-Large LoRA r=1r=1, SST-20.13.46⋅1033.46\cdot10^3+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).

MethodSamplingOPT-1.3B FTOPT-1.3B LoRARoBERTa-Large FTRoBERTa-Large LoRA
ZO-SGDGaussian, K=1K=1, more iterations0.9280.8540.8990.913
ZO-SGDGaussian, K=5K=5, same iterations0.9190.8500.8690.905
ZO-SGDAlgorithm 20.9350.9160.9090.928
ZO-AdaMMGaussian, K=1K=1, more iterations0.9250.9120.9090.812
ZO-AdaMMGaussian, K=5K=5, same iterations0.9170.9050.8990.801
ZO-AdaMMAlgorithm 20.9300.9290.9170.900
JAGUARGaussian, K=1K=1, more iterations0.9250.9210.9060.905
JAGUARGaussian, K=5K=5, same iterations0.9140.9110.8960.893
JAGUARAlgorithm 20.9300.9280.9220.927
ZoARGaussian, K=2K=2, N=15N=15, more iterations0.9300.9030.9200.913
LORENLow-rank curvature, 6 forwards, same iterations0.9350.8440.8690.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 0.869±0.0030.869\pm0.003, compared with 0.862±0.0240.862\pm0.024 for Gaussian sampling with K=1K=1 and more iterations and 0.850±0.0110.850\pm0.011 for Gaussian sampling with K=5K=5 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

  1. Low-Rank Curvature for Zeroth-Order Optimization in LLM Fine-Tuning, Seung et al., AAAI2026.
  2. Zeroth-Order Optimization is Secretly Single-Step Policy Optimization, Qiu et al., ICML2025 Workshop.
  3. On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization, Ma and Huang, NeurIPS2025.
  4. Zeroth-Order Optimization Finds Flat Minima, Zhang et al., NeurIPS2025.
  5. Seeing Stars: Exploiting Class Relationships for Sentiment Categorization with Respect to Rating Scales, Pang and Lee, ACL2005.
Reviewer_rVrxOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Learnable Direction Sampling Descent (LDSD) to address a fundamental limitation of conventional zeroth-order optimization (ZO): in high-dimensional spaces, randomly sampled search directions tend to exhibit poor alignment with the true gradient, leading to convergence rates that depend on the parameter dimension dd. The proposed method aims to improve the quality of search directions by learning the sampling distribution of random perturbations using information accumulated from previous function evaluations.

Specifically, the authors model the random perturbations using a Gaussian distribution N(μt,ε2I)\mathcal N(\mu_t,\varepsilon^2 I) and adapt the sampling directions by updating the mean parameter μt\mu_t online. On the theoretical side, the authors analyze the evolution of expected gradient alignment within an idealized Directional Gradient Descent (DGD) framework and establish a convergence rate without explicit dependence on the dimension dd, under certain initialization and parameter conditions. On the algorithmic side, the authors further combine finite-difference estimation, REINFORCE-based policy gradients, and candidate direction selection to develop the ZO-LDSD framework for large language model fine-tuning. Experimental results suggest that the proposed method can improve the performance of several existing zeroth-order optimizers on language model fine-tuning tasks.

Critical strengths

1. The proposed approach is novel and conceptually insightful.

Unlike conventional zeroth-order optimization methods, which typically sample random perturbations from a fixed isotropic distribution N(0,I)\mathcal N(0,I), this paper considers sampling from a learnable Gaussian distribution $ v_t\sim\mathcal N(\mu_t,\varepsilon^2 I), $ where the mean parameter μt\mu_t is dynamically updated using information accumulated during optimization. The goal is to improve the alignment between sampled search directions and the true gradient. This approach offers a valuable perspective on addressing the inefficiency of random direction sampling in high-dimensional zeroth-order optimization.

2. The theoretical analysis provides a mathematical foundation for learnable direction sampling.

The authors adopt expected squared gradient alignment as a central quantity in their theoretical analysis, establishing a connection between gradient alignment and the efficiency of objective function descent. They further investigate how idealized policy updates affect gradient alignment. In particular, Lemma 3.7 establishes a convergence rate without explicit dependence on the dimension dd, under specific initialization assumptions and technical conditions. Although this result relies on relatively restrictive assumptions, it nevertheless provides a meaningful theoretical perspective on how historical information can be leveraged to improve random search directions.

Critical weaknesses

The dimension-independent convergence guarantee relies on a restrictive initialization condition, and the end-to-end oracle complexity remains unclear. This is my primary concern about the paper.

Lemma 3.7 requires the initial sampling mean to satisfy the following alignment condition with the true gradient: cos⁡(β0)=⟨μ0,∇f(x0)⟩∣∣μ0∣∣⋅∣∣∇f(x0)∣∣≥14.\cos(\beta_0)=\frac{\langle\mu_0,\nabla f(x_0)\rangle}{||\mu_0||\cdot||\nabla f(x_0)||}\geq\frac14. However, under isotropic random initialization independent of the true gradient, the expected squared cosine similarity is only 1/d1/d. Consequently, in high-dimensional spaces, the probability that a randomly initialized direction satisfies the above constant-level positive alignment condition is typically very small.

Questions for authors

1. On the cost of obtaining a well-aligned initial direction.

Lemma 3.7 requires the initial direction to satisfy the alignment condition $\cos(\beta_0)\geq 1/4$. Could the authors further clarify how such an initial direction can be constructed using only zeroth-order function evaluations, without access to first-order gradients or any additional prior information about the gradient?

In particular, how does the number of function evaluations required to achieve constant-level gradient alignment scale with the dimension dd? When both the initialization cost and the function-query cost of subsequent optimization are taken into account, does LDSD still achieve dimension-independent end-to-end oracle complexity?

2. On the connection between the theoretical Algorithm 1 and the practical Algorithm 2.

Could the authors further explain why the REINFORCE-based policy update using one-sided perturbed losses in the practical Algorithm 2 is expected to improve the expected squared gradient alignment analyzed in Theorem 3.5?

Would it be possible to establish a corresponding gradient alignment guarantee for the finite-difference estimation, stochastic policy gradient updates, and candidate direction selection mechanisms employed in practice, or to provide a quantitative connection between the objectives underlying the two algorithms?

2 comments

Dear Reviewer rVrx,

We thank the reviewer for their valuable questions and the care devoted to evaluating our work. Their feedback prompted additional measurements and an extended analysis, which we present point by point below.

  • We propose computing a first-order gradient once to initialize μ0\mu^0, recomputing layer inputs and writing gradients directly into the preallocated μ\mu buffer. This makes backpropagation substantially slower but reduces peak memory. We measured memory and runtime on OPT-6.7B and Qwen3-8B with MultiRC, bf16, and one A100 80GB. ZO includes μ\mu storage, Init uses recomputation, and FO is standard SGD. BB and TT denote batch size and sequence length.

    Peak GPU memory (GB):

    ModelBBTTZOInitFO
    OPT-6.7B1651225.625.937.5
    OPT-6.7B8102425.625.937.5
    OPT-6.7B16102426.327.262.2
    Qwen3-8B1625631.730.649.2
    Qwen3-8B1651231.731.4OOM
    Qwen3-8B8102431.731.4OOM
    Qwen3-8B16102432.233.6OOM

    Wall-clock time (s) per step or initialization:

    ModelBBTTZOInitFO
    OPT-6.7B165121.239.531.48
    OPT-6.7B810241.3010.221.59
    OPT-6.7B1610242.3120.083.11
    Qwen3-8B162561.037.791.11
    Qwen3-8B165121.7315.38OOM
    Qwen3-8B810241.8016.14OOM
    Qwen3-8B1610243.2631.77OOM

    OOM denotes an out-of-memory failure at the 76 GB limit. After warm-up, initialization requires approximately the same peak GPU memory as a ZO step but takes about ten times as long. This makes repeated use impractical, while a single initialization consumes only a negligible fraction of the budget over thousands of training iterations. These results are now in Appendix B.2 (page 15, Tables 5-6). All changes relative to the original submission are highlighted in blue for the reviewers' convenience.

  • REINFORCE is an unbiased estimator of the policy gradient of its chosen reward, and the finite-difference ZO update converges to the directional update as τ→0\tau\to0. The revised manuscript adds Appendix E (pages 30-35), extending the alignment guarantees to finite differences and inexact policy updates. The section proceeds as follows:

    • Pages 30-31 quantify finite-difference bias and establish the descent bound.
    • Pages 31-33 derive one-step and trajectory alignment guarantees.
    • Sections E.1-E.2 (page 34) give convergence results for the two 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.

    The only additional mechanism outside this analysis is the greedy choice of vv. Its effect is isolated in Section 5.4 (page 8, Figure 3(d) on page 9), comparing learned sampling with averaging and argmin selection under the same forward-pass budget.

We thank the reviewer again for their careful assessment and engagement in the review process, which helped strengthen the paper. We believe these revisions address all of their concerns and hope they will further strengthen their positive assessment of our work.

I sincerely thank the authors for their detailed responses. I believe that most of my concerns have been addressed. I decide to maintain my original score.

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

This paper introduces LDSD (Learnable Direction Sampling Descent) for large language model (LLM) fine-tuning. LDSD is based on directional gradient descent, but instead of sampling directions from a zero-mean Gaussian distribution, it samples them from a Gaussian distribution with a learnable mean vector. To quantify how well the sampled directions align with the true gradient, the authors define the gradient alignment as the squared cosine of the angle between them. Algorithm 1 updates the mean vector by gradient ascent on the expected gradient alignment, while the model parameters are updated by directional gradient descent. For this algorithm, the authors show that the expected alignment increases to a constant level, and derive a convergence rate without explicit dependence on the dimension dd. However, Algorithm 1 requires the true gradient, which requires substantial memory in LLM fine-tuning. To address this issue, the authors propose a practical algorithm (Algorithm 2) based on zeroth-order (ZO) finite-difference estimates, REINFORCE, and greedy sample selection. They also provide experimental results on LLM fine-tuning to demonstrate the effectiveness of the proposed method.

Critical strengths

The paper proposes and theoretically analyzes an algorithm that improves directional alignment through adaptive sampling. It is interesting that the resulting convergence guarantee has no explicit dependence on the dimension dd. Furthermore, the paper introduces a zeroth-order framework for settings where gradients are unavailable and shows promising empirical results.

Critical weaknesses
  • I checked the proofs in some detail and found some gaps in the main theoretical results in Section 3.4 (see the questions below).
  • While the paper introduces a ZO framework (Algorithm 2), no corresponding theoretical analysis is provided. This is important because the main claim of the paper (i.e., removing the explicit dependence on the dimension dd) is only shown for Algorithm 1, so it is unclear whether this claim holds for the algorithm actually used in practice.
Questions for authors
  • In the proof of Theorem 3.5 (lines 929–933), the authors bound the angle between ∇f(xt)\nabla f(x^t) and ∇f(xt+1)\nabla f(x^{t+1}) by 2arcsin⁡(∥∇f(xt+1)−∇f(xt)∥/(2∥∇f(xt)∥))2\arcsin\big(\|\nabla f(x^{t+1})-\nabla f(x^t)\|/(2\|\nabla f(x^t)\|)\big). However, this bound does not seem to hold in general when the two gradients have different norms. Could the authors clarify how this bound is justified? The same bound is also used in the proof of Lemma 3.6 (line 1324).
  • In the proof of Lemma 3.6 (line 1308), the authors claim that ∇ψ(μt)\nabla\psi(\mu^t) is collinear with μt‾−∇f(xt)‾\overline{\mu^t}-\overline{\nabla f(x^t)}. However, these vectors do not seem to be collinear in general. Could the authors clarify this?
  • In Figure 3(d), the Gaussian baseline does not use the argmin selection, whereas the proposed method uses both the learnable direction and the argmin selection. This makes it unclear how much of the improvement comes from the learnable direction itself. It would be helpful to also compare with Gaussian sampling using the argmin selection under the same number of forward passes.
  • The link for the code in the abstract does not work (it says the repository is expired). The authors should fix this issue.
5 comments

Dear Reviewer 3Rdk,

We sincerely thank the reviewer for their careful reading and valuable feedback. Below, we address their questions in order.

  • We agree that the original angle bound does not hold for gradients with different norms. We have corrected the geometric argument in the revised manuscript (page 19, lines 987-996), using

    ∠(∇f(xt),∇f(xt+1))≤arcsin⁡(∥∇f(xt+1)−∇f(xt)∥∥∇f(xt)∥)≤arcsin⁡(Lγxt).\angle\big(\nabla f(x^t),\nabla f(x^{t+1})\big)\leq\arcsin\left(\frac{\|\nabla f(x^{t+1})-\nabla f(x^t)\|}{\|\nabla f(x^t)\|}\right)\leq\arcsin(L\gamma_x^t).

    For the reviewers' convenience, all changes in the revised manuscript are highlighted in blue.

  • We agree that the claimed collinearity is incorrect. Instead, ∇ψ(μt)\nabla\psi(\mu^t) lies in the tangent space to the unit sphere at μt‾\overline{\mu^t} and is collinear with the projection of ∇f(xt)‾−μt‾\overline{\nabla f(x^t)}-\overline{\mu^t} onto that space. As in the previous point, the geometric intuition is preserved, but this correction required a more substantial revision. We refer the reviewer to the corrected proof of Lemma 3.6 on pages 27-29, supported by Lemma D.3 on pages 25-27.

  • We have conducted the suggested comparison. Gaussian sampling with K=5K=5 candidates and argmin selection uses the same forward passes, step size and selection rule as ZO-LDSD and differs only in that the mean is fixed at μ=0\mu=0. The benefit of learning μ\mu is governed by the sampling term (d−1)ε2/∥μt∥2(d-1)\varepsilon^2/\|\mu^t\|^2 (see our response to Reviewer Pdqp, Q1), so we evaluate it with a moderate number of trainable parameters: prompt tuning of OPT-1.3B with 10 virtual tokens (d=20,480d=20{,}480) on SST-2, ZO-SGD, ε=1\varepsilon=1, γx=10−3\gamma_x=10^{-3}, γμ=10−1\gamma_\mu=10^{-1}, three seeds. All rows use the same total number of forward passes (120k). We report validation accuracy of the selected checkpoint:

    SamplingSeed 0Seed 1Seed 2Mean ±\pm std
    Gaussian, K=1K=1, more iterations0.7780.8040.8820.821 ±\pm 0.054
    Gaussian, K=5K=5, argmin, same iterations0.8360.8800.7880.835 ±\pm 0.046
    Algorithm 20.8720.8820.8000.851 ±\pm 0.045

    Algorithm 2 improves over argmin selection with Gaussian sampling on every seed (+0.036, +0.002, +0.012), so the gain is not explained by candidate selection alone. These results are included in Appendix B.1 (page 15, Table 4) of the revised manuscript.

  • The code link has been restored and is now working.

The first Weakness is addressed in the responses above. The revised manuscript also addresses the second issue raised in the Critical Weaknesses section. We have added Appendix E (pages 30-35), extending the theory to a finite-difference ZO oracle and inexact policy updates:

  • Pages 30-31 bound the finite-difference and policy errors.
  • Pages 31-33 establish alignment guarantees.
  • Sections E.1-E.2 (page 34) provide convergence guarantees for the two initialization regimes.
  • Section E.3, Discussion (page 35), explains the choice of finite-difference radius for a target accuracy, the resulting residual term, and the role of the policy-error bound, including a high-probability extension to unbounded noise.

We thank the reviewer again for their feedback, which helped improve the paper. We hope that these revisions address all of their concerns and allow them to increase the score.

Dear Reviewer 3Rdk,

We would like to gently follow up on our earlier rebuttal. We understand the considerable workload during the review process and sincerely appreciate the time you devote to evaluating submissions.

We would also be grateful if you could take a moment to look at the additional elements included in our response. Any feedback you might have on these points would be greatly appreciated.

I thank the authors for their responses, which have addressed some of my comments. However, Appendix E introduces substantial new proofs whose connection to Algorithm 2 is not sufficiently explained. In particular, it is unclear whether Algorithm 2 satisfies Assumption E.1, and the assumption itself is difficult to interpret, partly because notation such as F∇f(xt)‾(μt)F_{\overline{\nabla f(x_t)}}(\mu_t) is not clearly defined in the main text. Therefore, I will maintain my current score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.