acceptodds
Under review as a conference paper at ICLR 2027

Sample-Adaptive Zeroth-Order Post-Training

Abstract

Zeroth-order (ZO) optimization offers a memory-efficient alternative to backpropagation for fine-tuning large language models. However, existing ZO methods typically sample training examples uniformly, overlooking their evolving importance and leaving avoidable estimation variance. To address this limitation, we propose Sample-Adaptive Zeroth-Order Optimization (SAZO), which learns sample importance online and adaptively allocates queries to accelerate convergence. SAZO extracts gradient-norm information from existing directional differences to estimate sample importance without access to true gradients. Furthermore, to track evolving importance from sparse minibatch feedback, SAZO maintains per-example exponential moving averages that aggregate observations across updates. The method requires no additional model evaluations and only additional scalar state compared with MeZO. We prove that SAZO asymptotically matches the leading convergence term of the *minimum-variance* sampling oracle, and achieves a strictly faster convergence rate than standard methods. Extensive experiments across four model families demonstrate improved average downstream performance and up to faster convergence to the same training loss in terms of query count.

Primary area:
optimization
Keywords:
Zeroth-Order Optimization,Large Language Model Post-Training,Adaptive Importance Sampling

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_CPdyOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes Sample-Adaptive Zeroth-Order Optimization (SAZO), which adapts the sampling distribution over training examples rather than the perturbation distribution over model parameters. SAZO estimates per-example gradient norms from the directional differences already computed by ZO optimization, maintains their temporal estimates using per-example exponential moving averages, and performs importance sampling with inverse-probability weighting. The method requires no additional model evaluations and only O(N)O(N) additional scalar state. The authors provide convergence analysis showing that the leading optimization term approaches that of a variance-minimizing dynamic sampling oracle, and experiments across several language-model families demonstrate improved downstream performance and substantially faster loss reduction than MeZO and HiZOO.

Critical strengths
  1. The sample-adaptive perspective is novel and interesting in the context of memory-efficient ZO fine-tuning. Most existing ZO methods adapt the parameter update, perturbation geometry, or preconditioning, whereas SAZO instead exploits heterogeneity across training examples. This provides a complementary direction for improving ZO efficiency. The method is practically lightweight. SAZO reuses the directional differences already required by the ZO update to estimate sample importance and therefore introduces no additional model evaluations. Its additional memory requirement is only one scalar score per training example, i.e., O(N)O(N) rather than O(d)O(d) parameter-wise optimizer state.

  2. The theoretical motivation is well aligned with the algorithm. The paper derives the variance-minimizing sampling distribution pi,t∗∝∥∇fi(xt)∥p_{i,t}^{*}\propto\|\nabla f_i(x_t)\| and then constructs a practical ZO estimator of this unavailable quantity. The convergence analysis connects the learned sampling distribution to the dynamic oracle through a sampling-regret bound. The experimental evaluation is reasonably broad. The authors evaluate masked and generative language models ranging from RoBERTa-large to Llama3-8B, across classification, multiple-choice, and question-answering tasks. The reported gains are consistent across model families, and the convergence experiments use a common forward-pass budget.

Critical weaknesses
  1. The comparison with parameter-space adaptive and momentum-based ZO methods is limited. The paper motivates SAZO partly by contrasting sample-space adaptation with existing approaches such as ZO-AdaMM and R-AdaZO, which use historical moment information in parameter space. However, the main experimental comparisons are largely restricted to MeZO and HiZOO. This makes it difficult to determine whether adaptive sample selection provides advantages beyond what can already be obtained through momentum or adaptive-moment ZO optimization.

  2. The statistical consequences of repeatedly sampling high-importance examples deserve further investigation. The paper does account for sampling with replacement: duplicate examples within a minibatch are evaluated once while retaining their multiplicities, and Appendix D analyzes the resulting estimator. Therefore, I do not view duplicate sampling as a correctness issue. However, importance sampling can still cause the training distribution to become highly concentrated on a small subset of examples. Although the uniform exploration term guarantees that every example retains nonzero probability, the paper does not characterize the resulting sampling concentration or effective sample diversity. In particular, examples with persistently large gradient norms may be sampled much more frequently than others. It would be useful to understand whether such examples correspond to informative hard samples or potentially noisy/outlier examples, and whether oversampling them can affect generalization. Some of the convergence claims appear stronger than what the theoretical result directly establishes. The paper states that SAZO achieves a "strictly faster convergence rate" than standard methods. However, the leading terms for uniform sampling and optimal adaptive sampling both scale as O(T−1/2)O(T^{-1/2}); the improvement comes from replacing the uniform-sampling second-moment coefficient UTU_T by the smaller dynamic-oracle quantity DTD_T. I believe this is more precisely described as an improved leading convergence coefficient rather than a different asymptotic convergence order.

Questions for authors
  1. Could the authors provide comparisons with momentum- or adaptive-moment-based ZO methods such as ZO-AdaMM and R-AdaZO? Since SAZO operates in sample space while these methods operate in parameter space, can SAZO be combined with them, and if so, are the gains complementary?

  2. More generally, what is the conceptual advantage of adaptive sample selection over momentum-based variance reduction? Under what type of noise or sample heterogeneity should one expect SAZO to provide larger gains than momentum-based ZO optimization?

  3. Although Appendix D handles repeated draws correctly at the estimator level, how concentrated does the learned sampling distribution become in practice? Could the authors report statistics such as the maximum pi,tp_{i,t}, entropy/effective sample size of ptp_t, the fraction of unique examples per minibatch, or cumulative sampling frequencies?

  4. Could repeatedly sampling examples with large estimated gradient norms lead to over-emphasis on noisy, mislabeled, or outlier examples? It would be useful to evaluate SAZO under controlled label noise or to analyze whether the most frequently sampled examples are consistently informative rather than anomalous.

  5. The convergence results for uniform and adaptive sampling both have an O(T−1/2)O(T^{-1/2}) leading order. Would it be more precise to describe SAZO as improving the leading variance-dependent coefficient rather than achieving a strictly faster asymptotic convergence rate?

  6. Could the authors clarify how the horizon-dependent schedules for ϵ\epsilon and β\beta in Theorem 2 relate to the fixed ϵ=0.1\epsilon=0.1 and β=0.05\beta=0.05 used in all main experiments?

4 comments
AuthorsOpenReview ↗

Response to Question 1, 2, 3

Thank you for your constructive questions and for recognizing the value of adapting in sample space. We have revised the manuscript and added further experiments and analyses in response to your suggestions. Changes in the revised manuscript are highlighted in blue. The section, figure, table, and theorem references below refer to the revised manuscript.

W1 & Q1 & Q2: Comparison and combination with momentum

Compared to standalone momentum-based methods, SAZO boasts two conceptual advantages below. (1) SAZO adds only O(N) scalar storage, whereas momentum-based methods require additional storage at least on the order of the model parameter size. (2) SAZO only needs to track O(N) scalars, which are easy to learn; in contrast, momentum-based methods need to characterize O(d)-dimensional vectors, which is intrinsically difficult.

But how does learning O(N) scalars provide considerable gains? The answer is that heterogeneity is central to the benefit of SAZO. On a common parameter trajectory, SAZO improves the leading convergence term over uniform sampling by a factor of UT/DT≥1\sqrt{\mathcal U_T/\mathcal D_T}\ge1 (Theorem 2; Table 1), where UT\mathcal U_T and DT\mathcal D_T are the horizon-averaged estimator second moments under uniform and optimal sampling. Their difference is proportional to the average across-sample variance of gradient norms, and vanishes when all sample gradient norms are equal. Thus stronger relative gradient-norm heterogeneity creates a greater advantage for sample adaptation (Section 3.3).

We conducted experiments showing that SAZO converges faster than momentum-based methods (Appendix E.8, Figure 10). Moreover, SAZO has lower peak memory usage compared to the examined momentum-based algorithms (ZO-AdaMM [1] with 2.63× peak GPU memory and R-AdaZO [2] with 2.02× peak GPU memory).

However, SAZO can be combined with momentum-based methods to achieve even better performance. We passed SAZO's importance-corrected estimate into each optimizer's existing moment updates, and both converge faster than standalone SAZO. We also provide a detailed theoretical convergence analysis of a natural momentum extension of SAZO, which is called SAZO-m (Appendix A.7).

Peak GPU memory and mean population loss at 10K updates (Appendix E.8, Figure 10 and Table 9):

MethodMeZOZO-AdaMMR-AdaZOSAZOSAZO-mZO-AdaMM+SAZOR-AdaZO+SAZO
Peak memory (GiB)2.807.375.662.804.187.375.66
Population loss0.0880.0840.0800.0320.0300.0240.014

W2 & Q3: Sampling concentration and diversity

We have added the report of the effective sample size, maximum sampling probability, and distinct examples per minibatch during a particular training progress of SAZO(Appendix E.11, Table 11). To name a few, the maximum single-example probability over the reported trajectories is 3.0%. For N=1024N=1024, uniform sampling has ESS 1024, while SAZO's ESS ranges from 172 to 833 across the reported conditions. There are 54.5–61.7 distinct examples in a minibatch of size 64 on average.

References

[1] Chen et al. (2019). ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization.

[2] Shu et al. (2025). Refining Adaptive Zeroth-Order Optimization at Ease.

AuthorsOpenReview ↗

Response to Question 4, 5, 6

W2 & Q4: Oversampling noisy or anomalous examples?

SAZO does not oversample noisy, mislabeled, or outlier examples for the two reasons below. (1) Unequal sampling probabilities do not change the equal weights in the original finite-sum objective. If hih_i is a sample's directional update and II is sampled with probability pip_i, inverse-probability weighting (IPW) gives EI[hINpI]=1N∑ihi.\mathbb E_I\left[\frac{h_I}{Np_I}\right]=\frac1N\sum_i h_i. Thus all examples retain equal objective weights in expectation (Section 3.1). (2) Greater relative sampling frequency also need not mean greater cumulative compute. Instead, SAZO saves queries on both normal and anomalous samples. Indeed, directionally sensitive examples, including corrupted ones, require more frequent revisits relative to easy samples; nevertheless, SAZO uses the information it has already collected to reduce sampling of easier, more predictable examples more aggressively; The comparison below is about how many draws each method needs to reach the same held-out quality when 20% of the sample labels are flipped.

Mean cumulative draws per example (Appendix E.11, Table 13):

Example groupSAZO (5K)MeZO (10K)Reduction
Corrupted525.64625.0015.90%
Clean259.47625.0058.48%

We also evaluated SAZO under other controlled condition where training data were corrupted (Table 5; Appendix E.11). SAZO achieves higher mean clean-test accuracy than MeZO under every reported corruption condition, including 5%, 10%, and 20% label flips, spelling noise, contradictory examples, and synthetic outliers. For your reference, its gains under label flips are 1.8, 1.7, and 4.2 percentage points, respectively. These results demonstrate robustness of SAZO across under training-data corruption.

W2 & Q5: Convergence order versus leading coefficient

You are correct that the improvement is in the leading variance-dependent coefficient, not a different asymptotic order. We have replaced the “strictly faster convergence rate” wording in the abstract and introduction with an improved convergence coefficient.

Q6: Why use fixed hyperparameters in the experiments?

What follows is the explanation. (1) Theorem 2 states that the exponents characterizing the dependence of β and ε on the horizon are smaller than that for η, and hence they are less sensitive. Its horizon exponents for β\beta and ε\varepsilon are 3/103/10 and 1/101/10, smaller than the learning rate's 1/21/2, indicating weaker dependence on the budget. (2) Our ablations show stable performance across broad ranges of the hyperparameter parameters (Section 4.4; Appendix E.4). We therefore used β=0.05\beta=0.05 and ε=0.1\varepsilon=0.1 as defaults and grid-searched only the learning rate in the main performance comparisons. (3) Keeping the sampler settings fixed also avoids giving SAZO an unfair advantage through additional tuning freedom. Choosing the hyperparameters of SAZO is not tricky.

Thank you again for your valuable suggestions. We welcome any further questions and would be very happy to discuss them with you.

Reviewer_CPdyOpenReview ↗

Response to Submission25547

Thank you for your detailed response. Your clarifications have addressed most of my concerns. After carefully considering your rebuttal, I have decided to maintain my original rating.

AuthorsOpenReview ↗

Thank You for Your Constructive Comments and Feedback

We sincerely thank your constructive comments and recognition of our responses!

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

This paper proposes improving zeroth-order optimization by adaptively sampling training examples based on their estimated gradient magnitudes. It provides convergence analyses and evaluates the proposed method on models including RoBERTa-large, OPT-1.3B, Phi-2, and Llama3-8B.

Critical strengths
  1. It applies importance sampling to ZO fine-tuning, which is novel and simple. The method obtains gradient-norm estimation without gradients.
  2. It provides analyses of sampling regret and compares with a dynamic oracle.
Critical weaknesses
  1. The paper compares with MeZO and HiZOO, which is a small set of baselines. How about reweighting samples with losses as an additional baseline? People have applied this idea to first-order methods, e.g., Tilted Empirical Risk Minimization. It would be more convincing if the paper could show that directional difference gradient-norm estimation outperforms simply using training losses.

  2. Some ablations would further support the paper's claims. For example, studying whether dynamically tracking sample importance is necessary; studying whether the proposed ZO importance estimator actually recovers useful sample rankings.

Questions for authors

It seems that the asymptotic guarantee differs from the implemented optimizer: the vanishing-regret guarantee requires decaying exploration, EMA, and learning-rate hyperparameters, but the experimental algorithm uses fixed values. Can the authors explain how one should select hyperparameters in practice?

5 comments
AuthorsOpenReview ↗

Response to Weakness 1

Thank you for your valuable questions. We have revised the manuscript and added further experiments and analyses in response to your suggestions. Changes in the revised manuscript are highlighted in blue. The section, figure, table, and theorem references below refer to the revised manuscript.

W1: Comparison with loss-based weighting

One conceptual distinction between existing loss-based weighting methods in first-order optimization and SAZO is that the former modify the original optimization objective at the sample level while the latter keeps all examples equally weighted and the target unchanged. To be more specific, the estimated "importance" of a sample with respect to SAZO can be considered as the sample's potential contribution to the variance of the gradient estimator. Moreover, Inverse-Probability Weighting (IPW) multiplies each queried contribution by 1/(Npi)1/(Np_i), exactly cancelling its sampling probability pip_i in expectation (Section 3.1). Thus SAZO reduces variance without changing the original objective. In contrast, loss-based methods such as TERM [1], OHEM [2], and self-paced learning [3] alter the proportion of samples in the finite-sum target in order to obtain improved robustness.

Another crucial distinction is that, in first-order optimization, loss-based weighting methods mainly answer the question “Which examples should receive greater emphasis during learning?” However, SAZO answers a different question: “Given a limited budget of zeroth-order queries, which examples should be evaluated to obtain the most informative estimate of the original objective’s gradient?” These two questions are not equivalent. SAZO adaptively learns the sensitivity of different samples, allocating more frequent queries to sensitive samples and sparser queries to others, thereby improving overall query efficiency. This is intended to overcome the noise challenges in the zeroth-order setting and reduce query costs, rather than to adjust the relative weight of different samples in the optimization objective. The results below support lower ZO query costs even with 20% mislabeled examples (Appendix E.11, Table 13).

Example groupSAZO draws/exampleMeZO draws/exampleReduction
Corrupted52662515.9%
Clean25962558.5%

We therefore compared ZO adaptations of these loss-based methods with MeZO and SAZO on SST-2 (Appendix E.9; Figure 11). Their loss trajectories resemble MeZO, whereas SAZO converges faster. For instance, TERM improves accuracy over MeZO (93.2% vs. 92.7%), but remains below SAZO (94.1%).

Mean test accuracy and 10K-step population CE from Figure 11:

MethodTest accuracy (%)Population loss (CE)
MeZO92.70.09
TERM93.20.11
OHEM92.30.13
SPL91.60.10
SAZO94.10.03

To conclude, in zeroth-order scenarios where optimization under substantial noise is the primary bottleneck, SAZO outperforms loss-based weighting algorithms.

References

[1] Li et al. (2021). Tilted Empirical Risk Minimization.

[2] Shrivastava, Gupta, and Girshick (2016). Training Region-Based Object Detectors with Online Hard Example Mining.

[3] Kumar, Packer, and Koller (2010). Self-Paced Learning for Latent Variable Models.

AuthorsOpenReview ↗

Response to Weakness 2

W2.1: Necessity of dynamic tracking

Here is why tracking is necessary. (1) Sample importance changes during optimization. We evaluated exact gradient-norm importance at initialization and after 20K updates on SST-2 and TREC; the rank correlations are only 0.52 and 0.12, respectively (Appendix E.5; Figure 8). Initially important examples may become easy and less important once learned, whereas persistently difficult examples can remain important (Appendix E.6; Figure 9). A distribution fixed at one checkpoint cannot follow these changes, while SAZO updates its allocation dynamically.

(2) There is a tension between observation noise and information staleness. Random ZO directions make importance observations noisy, so even scoring examples at a static checkpoint requires repeated observations for reliability. Freezing the model during this process forgoes optimization progress, whereas updating it makes earlier scores stale. Instead, SAZO's EMA balances averaging against staleness by reusing each optimization difference, without additional model evaluations (Section 3.2; Algorithm 1; Theorem 1).

(3) Dynamically tracking sample importance brings the gradient-estimator variance closer to its minimum, thereby accelerating optimization. We compared SAZO with uniform sampling and a sampler fixed to the exact initial gradient-norm oracle on SST-2 (Appendix E.5). It turns out that SAZO achieves lower relative cumulative sampling regret and faster loss reduction (Figure 1(b,c)). Here, sampling regret measures excess estimator variance relative to the current variance-minimizing allocation, directly connecting better tracking to variance reduction.

W2.2: What sample ordering is learned?

The sample ordering SAZO learns to track is interpretable: examples that become easy lose priority, whereas persistently difficult or newly misclassified examples gain priority. Appendix E.6 and Figure 9 illustrate this on SST-2; the same inputs and labels acquire different importance as the model learns. Moreover, these ordering changes cannot be explained solely by fixed input features such as wording, sequence length, or class labels: those remain unchanged while predictions and gradient contributions evolve (Appendix E.6).

Example (Figure 9)Initial5K updates20K updates
A: “a great cast”Correct; 0.065Correct; 0.021Correct; 0.018
B: “over-dramatic at times”Wrong; 3.113Correct; 0.781Correct; 0.230
C: “smug grin”Wrong; 2.863Wrong; 6.485Wrong; 11.170
D: “amateurish ... a minor treat”Correct; 0.805Wrong; 6.200Wrong; 10.930

Each cell above reports prediction correctness and normalized oracle importance N∥∇fi(xt)∥/∑j∥∇fj(xt)∥N\|\nabla f_i(x_t)\|/\sum_j\|\nabla f_j(x_t)\| (1 corresponds to uniform allocation) with respect to a particular sample. As the table shows, A stays correctly predicted and receives little priority; B becomes correctly predicted and loses priority, while persistently incorrect C gains priority. Thus dynamic ranking can identify newly emerging difficulties during training, rather than just remembering which examples were initially hard (Appendix E.6; Figure 9). SAZO’s lower tracking regret in Figure 1(b) supports the value of following this evolving ordering.

AuthorsOpenReview ↗

Response to the Question

Q1: Horizon dependence and practical selection

The horizon TT is the planned total budget, not the current step tt. Thus the hyperparameters depending on it are fixed within a run, and chosen for the budget. To be more specific, Theorem 2 selects constants for the budget TT, as is standard in stochastic optimization [4, 5, 6, 7]. For example, η∝T−1/2\eta\propto T^{-1/2} maps a 10K-run learning rate of 3×10−63\times10^{-6} to 1.5×10−61.5\times10^{-6} for a separate 40K run; each remains fixed within its run. In contrast, the smaller exponents for β\beta and ε\varepsilon (3/103/10 and 1/101/10, versus 1/21/2 for η\eta), together with our ablations (Section 4.4; Appendix E.4), support weaker sensitivity, motivating scanning only η\eta in the main experiments. Fixing the sampler settings also avoids giving SAZO extra tuning freedom and an unfair advantage over the baselines.

Furthermore, our ablation experiments show that SAZO is robust to its hyperparameters. The tables report training loss of SAZO on RoBERTa-large/SST-2 (Section 4.4; Appendix E.4, Figures 5–6). Except for extreme divergence cases, SAZO’s performance remains close across a 100-fold range of the hyperparameter.

Varying ε\varepsilon with β=0.05\beta=0.05 fixed (15K updates):

ε\varepsilon0.050.10.51
Loss0.0560.0500.0630.086*

Varying β\beta with ε=0.1\varepsilon=0.1 fixed (15K updates):

β\beta0.0050.050.51
Loss0.0510.0500.051Diverged

*The ε=1\varepsilon=1 run diverges later (Appendix E.4, Figure 6).

Practical guidance is as follows. (1) Choose β\beta according to the epoch budget. A sufficient budget favors a smaller β\beta, whereas a tight budget calls for faster adaptation with a larger β\beta. (2) Use ε=0.1\varepsilon=0.1 as a practical default for LLM training. ε\varepsilon controls the balance between adaptation to sample heterogeneity and uniform exploration, which is standard in EXP3 [8]. An exploration rate of 0.1 is commonly used in practice, and we follow this practice.

References

[4] Shalev-Shwartz and Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms.

[5] Bubeck (2015). Convex Optimization: Algorithms and Complexity.

[6] Nemirovski et al. (2009). Robust Stochastic Approximation Approach to Stochastic Programming.

[7] Ghadimi and Lan (2013). Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming.

[8] Auer et al. (2002). The Nonstochastic Multiarmed Bandit Problem.

Thank you again for your valuable suggestions. We welcome any further questions and would be very happy to discuss them with you.

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

This paper proposes SAZO, a sample-adaptive zeroth-order optimization method for llm fine-tuning. SAZO estimates the per-sample importance by tracking exponential moving averages of directional differences. The method requires negelectable sample size O(N) scalar storage. The paper provides sampling-regret and convegence analyses. They evaluate SAZO across four models families, reporting improved downstream performance and up to 6 times fewer forward passes to reach MeZO's endpoint training loss.

Critical strengths
  1. Users with limited training memory need ways to improve learning without storing full gradients or adding model evaluations. SAZO provides an inexpensive way to allocate training effort across examples. Its gains under both full-parameter and parameter-efficient tuning support its usefulness within the tested setting.

  2. The diagnostics show that sample importance changes during training and that online tracking can improve allocation. The downstream gains across four model families suggest that the benefit extends beyond one model or dataset.

Critical weaknesses
  1. The paper’s scope is broader than its evaluation supports. The paper presents SAZO as a method for LLM post-training, but its experiments mainly cover classification, natural language inference, and question answering. More advanced reasoning benchmarks like mathematical problem-solving, code generation, instruction following are lack. The results support SAZO’s usefulness for the evaluated tasks, but its broader post-training value remains unclear.

  2. The reported 6 times speedup concerns reaching MeZO’s final training loss. It does not establish how quickly SAZO reaches a given held-out quality. The separate measurements of memory and per-update time also leave the overall tradeoff unresolved. A comparison with memory-efficient first-order methods, such as LoRA, and a competitive ZO baseline under the same GPU-memory limit would clarify when SAZO is preferable.

Questions for authors
  1. How robust is the method to imperfect training data? Noisy or contradictory examples may produce large directional derivatives and receive more evaluations. Importance weighting preserves the training objective, but does spending more compute on these examples still help?

  2. With sampled responses or noisy rewards, the magnitude of a finite difference may reflect evaluation noise as well as gradient magnitude. Under what conditions would the importance score remain reliable?

4 comments
AuthorsOpenReview ↗

Response to Weakness 1 & 2

Thank you for your constructive questions about SAZO's broader applicability and practical efficiency. We have revised the manuscript and added further experiments and analyses in response to your suggestions. Changes in the revised manuscript are highlighted in blue. The section, figure, table, and theorem references below refer to the revised manuscript.

W1: More advanced post-training tasks

We have added experiments on mathematical reasoning, code generation, and instruction following (Appendix E.10, Table 10). We compared MeZO and SAZO under the same update budget within each task and also reported the initial model's zero-shot performance. We searched constant learning rates for both methods over {1,3}×10−6\lbrace 1, 3 \rbrace \times 10^{-6}. It turns out that SAZO improves over baseline on all three tasks, supporting its application to a broader range of more difficult post-training tasks.

Task and modelMetricZero-shotMeZOSAZO
Mathematics: Qwen2.5-Math-1.5BGSM8K numerical-answer accuracy49.22%57.81%64.65%
Coding: Qwen2.5-1.5B-InstructHumanEval greedy pass@154.27%53.66%57.93%
Instruction following: Llama3-8BTwo-turn IFBench Loose pass rate31.15%31.15%32.23%

W2: Time to held-out quality under memory constraints

We have added a direct time-to-held-out-quality comparison with FO-LoRA [1] and a memory-saving FO-LoRA implementation (Appendix E.7, Table 8).

The key to this comparison is that LoRA constrains the rank of parameter updates, but does not reduce the dimensionality of the surrounding activations required for backpropagation. However, activations can become the dominant memory cost in large-batch LLM training. Therefore, using LoRA alone does not necessarily bring first-order memory usage close to ZO. To approach ZO's memory footprint, the first-order method must also use checkpointing and recomputation, which saves activation memory but substantially increases computation time. SAZO avoids storing backpropagation activations and instead accelerates optimization within the memory-limited setting. Thus SAZO outperforms first-order methods under restricted memory.

MethodSteps to ≥90%Relative timeRelative peak memory
FO-LoRA250.02×4×
FO-LoRA (checkpointing)251.74×≈1×
SAZO-LoRA11501.00×1×
MeZO-LoRA29502.52×1×

References

[1] Hu et al. (2021). LoRA: Low-Rank Adaptation of Large Language Models.

AuthorsOpenReview ↗

Response to Question 1 & 2

Q1: Does spending more queries on anomalous samples help?

SAZO indeed samples training data with more significant importance score more frequently. So it is reasonable to question and investigate whether SAZO wastes compute on anomalous samples. The answer is quite counter-intuitive. It turns out that SAZO saves queries on both normal and anomalous samples. Greater relative sampling frequency need not mean greater cumulative compute. On the one hand, directionally sensitive examples, including corrupted ones, are harder to predict and therefore require more frequent revisits relative to easy examples. On the other hand, SAZO uses the information it has already collected to reduce sampling of easier, more predictable examples more aggressively.

The comparison below measures the draws needed to reach the same held-out quality under 20% label flips. SAZO saves draws on both groups, with larger savings on clean examples.

Mean cumulative draws per example (Appendix E.11, Table 13):

Example groupSAZO (5K)MeZO (10K)Reduction
Corrupted52662515.9%
Clean25962558.5%

We also evaluated SAZO under other controlled forms of training-data corruption (Table 5; Appendix E.11). Experiments reveal that SAZO achieves higher mean clean-test accuracy than MeZO under every reported corruption condition, including 5%, 10%, and 20% label flips, spelling noise, contradictory examples, and synthetic outliers. For your reference, its gains under label flips are 1.8, 1.7, and 4.2 percentage points, respectively. These results demonstrate SAZO's robustness under training-data corruptions.

Q2: When are importance scores reliable with noisy function values?

We have added a theoretical analysis of noisy function values in Appendix A.8. For centered evaluation noise independent of the Gaussian perturbation direction, under bounded standardized fourth moments, allocation proportional to the expected absolute noisy directional difference achieves an estimator second moment within a constant factor of the minimum (Corollary 1). In particular, under Gaussian noise, this ratio is at most 1+1/[4d(d+2)]1+1/[4d(d+2)], even with unknown, sample-dependent noise variances (Corollary 2). Thus the importance score remains near-optimal under these assumptions.

We have also added a function-value noise experiment (Table 5; Appendix E.11), injecting independent Gaussian noise with standard deviation 0.02 into both methods' queried function values while keeping texts and labels unchanged. The induced directional-noise standard deviation is 55.04% of the initial median absolute noise-free directional difference. Under the stated condition, SAZO achieves 91.3% clean-test accuracy versus MeZO's 90.0%, validating the effectiveness of the theory.

Thank you again for your valuable suggestions. We welcome any further questions and would be very happy to discuss them with you.

Reviewer_2mttOpenReview ↗

Thank you for the additional experiments and detailed responses

Thank you for the detailed responses and additional experiments. The new reasoning, coding, and instruction-following results address my concern about evaluation benchmarks. The time-to-held-out-quality comparison also provides clearer evidence of practical efficiency, while the corruption experiments and noise analysis help address my robustness questions. Overall, the rebuttal strengthens the paper, and I maintain my weak acceptance recommendation.

AuthorsOpenReview ↗

Thank You for Your Constructive Comments and Feedback

We sincerely thank your constructive comments and recognition of our responses!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.