- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes ZO-AdaNesterov, combining a zeroth-order estimator, delayed AdaGrad-style scalar adaptation, and Nesterov momentum. The paper develops finite-time convergence bounds, almost-sure convergence results, saddle-avoidance analysis, and experiments including full-parameter LLM fine-tuning.
Critical strengths
1.The theoretical analysis is technically substantial, especially the treatment of adaptive denominators, momentum, and stochastic zeroth-order estimation.
2.The finite-time convex and non-convex complexity results are clearly stated and improve the explicit dimension dependence over the main adaptive ZO baselines considered in the paper.
3.The experiments cover several qualitatively different settings, including tensor decomposition, LLM fine-tuning, image classification, and adversarial attacks.
Critical weaknesses
-
Although the summarized oracle complexity of R-AdaZO in Tab. 1 does not explicitly contain , its original analysis (Shu et al., 2025. Eqs (16), (22), and Theorem 5.9) explicitly incorporates noise-variance dependence into the convergence bound. The authors should clarify whether the negative “NoiAda” designation reflects a genuine limitation of R-AdaZO's oracle complexity or merely the omission of noise-dependent factors in its simplified asymptotic expression.
-
The proposed algorithm ZO-AdaNesterov is a natural extension of corresponding momentum method (Nadam) without using EMA. However, the absence of EMA may cause the learning rate to vanish prematurely and thus halting training.
-
The theory assumes independent pairs across directions, but the experimental protocol does not clarify whether each direction uses an independently sampled minibatch. If the directions share a minibatch within an optimizer step, the independence argument in Lemma D.13 does not directly apply, and the authors should account for the shared data-noise component, which is not reduced by averaging directions.
-
There is a substantial mismatch between the theoretical parameters required for convergence and the actual implementation in experiments: Theorems 3.1 and 3.3 require a horizon-dependent batch size that scales linearly with dimension and total iterations (yielding ). But in all empirical evaluations (Appendix K), the authors use fixed tiny direction samples, such as or . For a 1.88B model like Qwen3.5-2B, is orders of magnitude smaller than the theoretical batch size requirement . As a result, the provided theoretical bounds do not cover the algorithm evaluated in practice.
-
The adversarial attack experiments only compare generic zeroth-order optimizers, without considering established query-efficient black-box attacks such as AutoZOOM (AAAI2019), SimBA (ICML2019), or Square Attack (ECCV2020).
Questions for authors
-
Why did the authors not consider or compare a ZO-AdaHeavyball (Polyak Heavy-ball momentum + adaptive stepsize) variant? Is the theoretical analysis effective for HB momentum without the EMA strategy?
-
What is the specific advantage of Nesterov momentum? Why did the authors not compare with ZO-AdaNesterov with EMA?
-
The theoretical convergence analysis (e.g., Theorem 3.6) highlights the critical role of ϵ∈(0,1/2] in accelerating stepsize decay to guarantee almost sure convergence. However, Appendix K explicitly states that all experiments were implemented with ϵ=0. Does the algorithm still satisfy the theoretical guarantees when ϵ=0, and how does setting ϵ>0 affect empirical convergence speed and model performance?
4 comments
Part II
Weakness 5: Dedicated black-box attack baselines
We have added AutoZOOM, SimBA, and Square Attack using the same victim model, evaluation images, five-seed protocol, and 6,000-query cap. Table 11 reports:
| Method | Queries () ↓ | ASR (%) ↑ | ↓ |
|---|---|---|---|
| ZO-SGD | 2.805 ± 0.005 | 80.0 ± 1.6 | 1.199 ± 0.013 |
| ZO-AdaMM | 2.283 ± 0.030 | 86.4 ± 1.9 | 1.001 ± 0.007 |
| R-AdaZO | 2.181 ± 0.019 | 88.0 ± 2.5 | 1.093 ± 0.006 |
| ZO-AdaNesterov | 2.152 ± 0.052 | 90.0 ± 1.0 | 0.976 ± 0.006 |
| AutoZOOM | 0.194 ± 0.059 | 99.0 ± 1.0 | 2.833 ± 0.020 |
| SimBA | 0.955 ± 0.066 | 88.0 ± 1.2 | 1.161 ± 0.011 |
| Square Attack | 0.152 ± 0.031 | 99.8 ± 0.4 | 1.497 ± 0.001 |
The first four generic optimizers use the same C&W-style objective, estimator, smoothing radius, direction budget, and query accounting. The last three dedicated attacks retain their attack-specific search mechanisms and provide broader attack-level context.
AutoZOOM and Square Attack achieve higher reported ASR with fewer queries. ZO-AdaNesterov has the smallest reported mean distortion. Relative to SimBA, its ASR is 2.0 percentage points higher and its reported mean distortion is approximately 15.9% lower, but it uses approximately 2.25 times as many queries. We present this as a trade-off, not universal superiority.
Question 1: Heavy-ball comparison and applicability of the analysis
Tables 6–7 now compare ZO-AdaNesterov and ZO-AdaHB over on all five RoBERTa-large GLUE tasks. At , Nesterov has a higher reported mean on every task; the differences are 4.72 score points on QNLI and 4.05 on STS-B.
Across the 20 matched task–exponent pairs, Nesterov is higher in 18, tied in one, and lower in one. The exception is QNLI at : 68.60 versus 68.72. This predominance supports the Nesterov update in the tested settings. The summaries are endpoint comparisons, not a statistical-significance or convergence-speed claim. The current manuscript does not establish an HB counterpart of the convergence theorems. Those results are proved for the Nesterov recursion, which queries at the look-ahead point ; HB queries at . Extending the proofs requires a separate verification and is not claimed here.
Question 3: Guarantees and empirical effects of
The new results support as a practical default in the tested settings. For ZO-AdaNesterov (Table 6), outperforms all tested positive values on MRPC, QNLI, and STS-B. On the remaining two tasks, the best positive value improves the mean by only 0.05 points on SST-2 and 0.14 on RTE. In contrast, improves on by 2.55, 5.08, and 10.79 points on MRPC, QNLI, and STS-B, respectively. Thus, the occasional benefit of a positive exponent is small for our method, whereas the losses can be much larger.
Tables 7–8 show a consistent broader pattern: is best on all five tasks for HB and four of five for EMA. Across the three methods, it achieves the highest mean in 12 of 15 method–task settings and exceeds a tested positive exponent in 40 of 45 same-method, same-task comparisons. The EMA exception is SST-2, where is higher by 0.77 points. These endpoint results explain our practical choice of .
The theoretical role of positive is different from this empirical choice. Theorems 3.1 and 3.3 and Proposition 3.10 include under their stated assumptions and tuning. Positive is sufficient for the almost-sure gradient-norm guarantee in Theorem 3.6, not a recommendation that it improves finite-budget performance. Theorem 3.8 includes under its additional assumptions but establishes saddle avoidance.
We hope these revisions and clarifications address your concerns. We would welcome any further questions or discussion.
I maintain the original score.
Thanks for the detailed rebuttal and additional experiments. I appreciate the authors' efforts to address my concerns, particularly the new comparisons with EMA, HB momentum, and adversarial attack methods. My main remaining concern is about the adversarial attack experiments. The authors acknowledge this trade-off and highlight their method's lower L2 distortion, but they do not adequately quantify or validate whether it is favorable, nor do they convincingly explain why it is a meaningful practical advantage.
Therefore, I maintain the original score.
Thank you for clarifying your remaining concern. We would like to make the practical relevance of lower mean distortion more precise and quantify the trade-off supported by our existing results.
Reducing distortion is an established objective in black-box attack evaluation. AutoZOOM explicitly studies post-success distortion refinement, using additional queries to obtain smaller perturbations (Tu et al., AAAI 2019, Section 4.5 and Figure 3(a)). SimBA likewise analyzes the trade-off between query expenditure and perturbation norm and evaluates attacks jointly through success rate, query count, and distortion (Guo et al., ICML 2019, Sections 3–4). The practical relevance is particularly clear from the minimum-norm attack perspective: for a given correctly classified input, any successful perturbation provides an upper bound on its minimum adversarial distance, and a smaller valid perturbation tightens this bound. This is the robustness-evaluation objective discussed by Carlini and Wagner (2017) and Croce and Hein (ICML 2020, Section 2.1). Thus, the relevance of smaller distortion is that it can reveal classification failures within a smaller input neighborhood.
In our existing experiments, ZO-AdaNesterov has a reported mean distortion of , compared with , , and for AutoZOOM, SimBA, and Square Attack, respectively. Relative to SimBA, this corresponds to a reduction in mean distortion and a percentage-point increase in ASR, at approximately times the mean query count. AutoZOOM and Square Attack achieve higher ASR with substantially fewer queries. We therefore interpret these results as a quantified trade-off, rather than evidence of overall superiority over specialized attacks. In particular, the aggregate distortion values do not establish better success rates under an identical perturbation constraint or a tighter bound on an identical set of successful images.
We hope that the discussion above clarifies why reducing perturbation size is relevant to norm-based robustness evaluation and makes the associated costs in query count and attack success explicit. We would be grateful if you could reconsider your assessment in light of this more precise explanation of the practical objective and the quantified results.
References
[1] Tu et al. AutoZOOM: Autoencoder-Based Zeroth Order Optimization Method for Attacking Black-Box Neural Networks. AAAI 2019
[2] Guo et al. Weinberger. Simple Black-box Adversarial Attacks. ICML 2019
[3] Carlini and Wagner. Towards Evaluating the Robustness of Neural Networks. IEEE Symposium on Security and Privacy (SP), 2017
[4] Croce and Hein. Minimally Distorted Adversarial Examples with a Fast Adaptive Boundary Attack. ICML 2020
Part I
Thank you for the detailed comments. We have completed the requested EMA comparison and added it alongside the Nesterov/HB, exponent, and dedicated-attack experiments. All newly added or revised text in the manuscript is highlighted in blue.
Weakness 1: Meaning of “NoiAda” and R-AdaZO's noise dependence
Thank you for requesting this clarification. “NoiAda” was intended to mean a faster polynomial dependence on target accuracy when environmental noise is zero, not merely the presence of a variance parameter. The negative entry for R-AdaZO concerns this property of its published guarantee, rather than omitted noise factors in a simplified expression.
R-AdaZO is variance-aware: its equations (16), (22), and Theorem 5.9 retain function-value noise through
Σ2=Kμ28(σf2+C2)d.
However, setting σf=0 leaves the C2 contribution. This substitution does not yield a separate, faster noiseless accuracy exponent from their stated bound and tuning. In contrast, under our stated fractional-moment criteria, our query bounds specialize as
\xrightarrow{\sigma=0}O\left(\frac d\delta\right), \qquad O\left(\frac d{\delta^2}+\frac{d\sigma^2}{\delta^4}\right) \xrightarrow{\sigma=0}O\left(\frac d{\delta^2}\right).$$ We have made this definition explicit in Table 1 and added the detailed comparison in Appendix K.5. A negative entry means “not established by the cited bound,” not “impossible for the algorithm” or “no noise dependence.” We also distinguish their function-value variance from our gradient variance and retain the qualification about different error criteria. NoiAda does not mean that the parameter tuning is independent of the noise level. ## **Weakness 2 and Question 2: Nesterov momentum and EMA** The requested EMA comparison is now complete (**see Tables 6 and 8 in the revised manuscript**). ZO-AdaNesterov has a higher reported mean than ZO-AdaNesterov-EMA in **17 of 20** matched task–$\epsilon$ pairs. At $\epsilon=0$, it performs better on four of the five tasks: | Method ($\epsilon=0$) | SST-2 | MRPC | QNLI | RTE | STS-B | |---|---:|---:|---:|---:|---:| | ZO-AdaNesterov | **91.99 ± 0.44** | **77.36 ± 0.74** | **73.68 ± 4.63** | 61.74 ± 3.00 | **83.51 ± 4.25** | | ZO-AdaNesterov-EMA | 91.15 ± 0.55 | 77.26 ± 0.63 | 70.32 ± 4.95 | **64.70 ± 3.75** | 81.02 ± 5.67 | The largest gains at $\epsilon=0$ are on QNLI and STS-B: **3.36 and 2.49 score points**, respectively. Even taking each method's largest reported mean over the four exponents $\epsilon\in\{0,0.01,0.1,0.5\}$, ZO-AdaNesterov remains higher on four of the five tasks; EMA is higher on RTE (64.70 versus 61.88). All three matched-pair exceptions occur on RTE, at $\epsilon=0$, $0.01$, and $0.1$. At $\epsilon=0.5$, ZO-AdaNesterov has higher means on all five tasks. These results favor ZO-AdaNesterov across **most** tested tasks, while showing a task-specific benefit from EMA on RTE. ## **Weakness 3: Independence across directions** In **Tables 6–8** of the revised manuscript, the new experiments on Nesterov/HB/EMA and varying $\epsilon$ runs use a separately and independently sampled minibatch for each direction; the two evaluations within a finite difference use that direction's same minibatch. Their across-direction sampling therefore matches the independent-pair condition in Lemma D.13. We do not retrospectively relabel the original shared-minibatch runs. They remain separately identified in Table 2. For that protocol, Lemma K.1 conditions on the shared minibatch and retains the shared data-noise term that is not divided by $m$. The revised experimental section explicitly distinguishes the original and additional protocols. ## **Weakness 4: Large theoretical batches versus small experimental direction counts** Proposition 3.10 now permits any fixed $m\ge1$. Under independent pairs, $r=1/2-\epsilon>0$, $\mu_n=\mu_1/n$ with $\mu_1\le1/d$, and the stated finite-horizon tuning, $$\left(\mathbb E[\\|\nabla f(w_R)\\|^{2r}]\right)^{1/r} \le C\left[ \frac{1+d/m}{T} +\sqrt{\frac{d\sigma^2}{mT}} \right].$$ For $1\le m\le d$, this gives $O(d/\delta^2+d\sigma^2/\delta^4)$ queries for $\mathbb E[\\|\nabla f(w_R)\\|^{2r}]\le\delta^{2r}$. Thus, changing to independent minibatches resolves the sampling mismatch, while this separate small-$m$ result addresses the direction-count mismatch.