- 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 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
-
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., rather than parameter-wise optimizer state.
-
The theoretical motivation is well aligned with the algorithm. The paper derives the variance-minimizing sampling distribution 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
-
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.
-
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 ; the improvement comes from replacing the uniform-sampling second-moment coefficient by the smaller dynamic-oracle quantity . I believe this is more precisely described as an improved leading convergence coefficient rather than a different asymptotic convergence order.
Questions for authors
-
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?
-
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?
-
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 , entropy/effective sample size of , the fraction of unique examples per minibatch, or cumulative sampling frequencies?
-
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.
-
The convergence results for uniform and adaptive sampling both have an 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?
-
Could the authors clarify how the horizon-dependent schedules for and in Theorem 2 relate to the fixed and used in all main experiments?
4 comments
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 is a sample's directional update and is sampled with probability , inverse-probability weighting (IPW) gives 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 group | SAZO (5K) | MeZO (10K) | Reduction |
|---|---|---|---|
| Corrupted | 525.64 | 625.00 | 15.90% |
| Clean | 259.47 | 625.00 | 58.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 and are and , smaller than the learning rate's , 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 and 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.
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.
Thank You for Your Constructive Comments and Feedback
We sincerely thank your constructive comments and recognition of our responses!
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 (Theorem 2; Table 1), where UT and DT 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):
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=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.