acceptodds
Under review as a conference paper at ICLR 2027

Adaptive Stepsizes Meet Momentum: An Improved Zeroth-Order Method

Abstract

Training deep networks relies heavily on adaptive step sizes and momentum mechanisms. Yet, in gradient-free regimes, their theoretical foundations are still underdeveloped. Since many problems permit only zeroth-order oracle access, classical gradient-based analyses cannot be applied. To address this, we propose ZO-AdaNesterov, a stochastic zeroth-order Nesterov momentum method equipped with adaptive step sizes, and develop a rigorous convergence analysis. We derive oracle complexity bounds for both convex and nonconvex objectives, which are strictly sharper than those of existing zeroth-order adaptive momentum methods. Besides, we provide the *first* last-iterate saddle-avoidance result for zeroth-order adaptive methods: with probability one, ZO-AdaNesterov does not converge to strict saddle points. Numerical experiments further confirm the efficiency of our method.

Primary area:
optimization
Keywords:
Zeroth-order method, Adaptive stepsizes, Momentum

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_SVADOpenReview ↗
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
  1. Although the summarized oracle complexity of R-AdaZO in Tab. 1 does not explicitly contain �0��0�, 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.

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

  3. The theory assumes independent (ui,ξi)(u_i, \xi_i) 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.

  4. 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 m=⌈dmax⁡{1,2σ2T}⌉m = \lceil d \max\{1, 2\sigma^2 T\} \rceil that scales linearly with dimension dd and total iterations TT (yielding m=O(d/δ2)m = O(d / \delta^2)). But in all empirical evaluations (Appendix K), the authors use fixed tiny direction samples, such as m=10m = 10 or m=50m = 50. For a 1.88B model like Qwen3.5-2B, m=50m = 50 is orders of magnitude smaller than the theoretical batch size requirement m=O(d⋅T)m = O(d \cdot T). As a result, the provided theoretical bounds do not cover the algorithm evaluated in practice.

  5. 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
  1. 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?

  2. What is the specific advantage of Nesterov momentum? Why did the authors not compare with ZO-AdaNesterov with EMA?

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

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=8(σf2+C2)dKμ2.\Sigma^2=\frac{8(\sigma_f^2+C^2)d}{K\mu^2}.

However, setting σf=0\sigma_f=0 leaves the C2C^2 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.

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:

MethodQueries (×103\times10^3) ↓ASR (%) ↑ℓ2\ell_2 ↓
ZO-SGD2.805 ± 0.00580.0 ± 1.61.199 ± 0.013
ZO-AdaMM2.283 ± 0.03086.4 ± 1.91.001 ± 0.007
R-AdaZO2.181 ± 0.01988.0 ± 2.51.093 ± 0.006
ZO-AdaNesterov2.152 ± 0.05290.0 ± 1.00.976 ± 0.006
AutoZOOM0.194 ± 0.05999.0 ± 1.02.833 ± 0.020
SimBA0.955 ± 0.06688.0 ± 1.21.161 ± 0.011
Square Attack0.152 ± 0.03199.8 ± 0.41.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 ϵ∈{0,0.01,0.1,0.5}\epsilon\in\{0,0.01,0.1,0.5\} on all five RoBERTa-large GLUE tasks. At ϵ=0\epsilon=0, 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 ϵ=0.5\epsilon=0.5: 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 xn=wn+θvnx_n=w_n+\theta v_n; HB queries at wnw_n. Extending the proofs requires a separate verification and is not claimed here.

Question 3: Guarantees and empirical effects of ϵ\epsilon

The new results support ϵ=0\epsilon=0 as a practical default in the tested settings. For ZO-AdaNesterov (Table 6), ϵ=0\epsilon=0 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, ϵ=0\epsilon=0 improves on ϵ=0.5\epsilon=0.5 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: ϵ=0\epsilon=0 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 ϵ=0.01\epsilon=0.01 is higher by 0.77 points. These endpoint results explain our practical choice of ϵ=0\epsilon=0.

The theoretical role of positive ϵ\epsilon is different from this empirical choice. Theorems 3.1 and 3.3 and Proposition 3.10 include ϵ=0\epsilon=0 under their stated assumptions and tuning. Positive ϵ\epsilon 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 ϵ=0\epsilon=0 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.

Reviewer_SVADOpenReview ↗

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 ℓ2\ell_2 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 0.9760.976, compared with 2.8332.833, 1.1611.161, and 1.4971.497 for AutoZOOM, SimBA, and Square Attack, respectively. Relative to SimBA, this corresponds to a 15.9%15.9\% reduction in mean distortion and a 2.02.0 percentage-point increase in ASR, at approximately 2.252.25 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

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

This paper studies zeroth-order optimization (ZO), where the gradient is unvailable and only the function evaluations are accesible. This paper proposes ZO-AdaNesterov, which combines adaptive stepsize methods and Nesterov-type momentum in ZO, and establishes a convergence guarantee which has a better dimension dependence compared to the existing ZO methods with adaptive stepsizes such as ZO-AdaMM and R-AdaZO. Moreover, the established bounds has an explicit bound on the noise variance, unlike ZO-AdaMM and R-AdaZO. Almost sure convergence and saddle avoidance of the last-iterate of ZO-AdaNesterov is also provided. Finally, the proposed method has been shown to be competitive with existing ZO methods with adaptive stepsize and momentum.

Critical strengths
  • This paper establishes a convergence analysis of the proposed method, ZO-AdaNesterov. It shows that ZO-AdaNesterov has a better dimension dependence compared to the existing ZO with adaptive stepsize methods such as ZO-AdaMM, R-AdaZO, both under convex and non-convex settings. Moreover, the provided convergence bound is noise-adaptive, i.e., the bound shows an explicit dependence on the noise variance σ2\sigma^2. In addition, the paper demonstrates useful properties such as saddle-point avoidance of the last iterate of ZO-AdaNesterov.
  • The performance of the proposed method is also shown under various settings.
Critical weaknesses
  • On the exponents of the convergence bound (12−ϵ\frac{1}{2} - \epsilon for convex and 1−2ϵ1-2\epsilon for non-convex), while they are consistent with prior work [1], the paper lacks a clear and sufficient explanation. This type of bound is clearly different from the standard convergence bounds such as E[f(xT)−f⋆]\mathbb{E}[f(x_{T}) - f^\star] for convex settings or min⁡tE∥∇f(xt)∥2\min_{t}\mathbb{E}\lVert\nabla f(x_{t})\rVert^2 for non-convex settings. To compare them with the results using those standard criteria, it needs to be justified by Markov's inequality, as in [1], to convert the original bounds into high-probability guarantees. Additionally, in these cases, it would be preferable to note the dependence on the failure probability (of the high-probability guarantees).
  • In Table 1, the complexity of ZO-AdaMM in convex settings assumes a constrained setting, so it would be more appropriate to note this.
  • The dependence of K1K_{1} on ϵ\epsilon is difficult to track.

Minor Issues

  • Line 81: Nesterov-tyoe → Nesterov-type

[1] Li, Xiaoyu, and Francesco Orabona. "On the convergence of stochastic gradient descent with adaptive stepsizes." The 22nd international conference on artificial intelligence and statistics. PMLR, 2019.

Questions for authors
  • Does the almost sure convergence and saddle avoidance necessarily require Assumption 3 (Lipschitzness of FF)?
3 comments

Thank you for these suggestions. The revision clarifies the convergence criteria, confidence dependence, and assumptions.

All newly added or revised text in the manuscript is highlighted in blue.

Weakness 1: Fractional moments and high-probability guarantees

We agree that our fractional-moment results are not standard expected-gap or expected squared-gradient guarantees. Their powers arise from the Hölder step with p=1/2+ϵp=1/2+\epsilon and r=1/2−ϵr=1/2-\epsilon.

Appendix K.3 now gives the Markov conversion explicitly. For each failure probability ρ∈(0,1)\rho\in(0,1), Theorems 3.1 and 3.3 imply, respectively,

f(\bar w_T)-f^\ast> \frac{K_1}{T\rho^{1/r}} \right)\le\rho, \qquad \mathbb P\left( \\|\nabla f(w_R)\\|^2> \frac{K_2}{T\rho^{1/r}} \right)\le\rho.$$ These are separate probability statements; they do not imply the corresponding expectation bounds. With $\bar K_i=1+K_i$, the original independent-pair batch rule gives sufficient query bounds $$N_C= O\left( \frac{d\bar K_1}{\delta\rho^{1/r}} + \frac{d\sigma^2\bar K_1^2}{\delta^2\rho^{2/r}} \right),$$ $$N_N= O\left( \frac{d\bar K_2}{\delta^2\rho^{1/r}} + \frac{d\sigma^2\bar K_2^2}{\delta^4\rho^{2/r}} \right)$$ for objective gap at most $\delta$ or gradient norm at most $\delta$, respectively. Corollary K.3 makes the polynomial confidence factors and integer-rounding convention explicit. Table 1 now distinguishes error criteria rather than presenting a like-for-like dominance comparison. ## **Weakness 2: Constrained convex setting of ZO-AdaMM** We have labeled ZO-AdaMM's convex result as constrained and identified its expected average-regret criterion on a bounded set. The revised comparison no longer suggests that it shares our unconstrained setting and fractional-moment criterion. ## **Weakness 3: Dependence of $K_1$ on $\epsilon$** Equation (90) in Appendix K.3 now expands this dependence: $$K_1=\max\left\\{\frac{W_1(h)}a[2\mathcal L_b(Q_1(h))]^{p/r},\left(\frac{W_1(h)}a\right)^{1/r}[2\mathcal J(4M)]^{p/r^2}\right\\}, \qquad h=a/b^{1/2+\epsilon},$$ where $$\mathcal L_b(Q)= r^{-r}\left[(b+N_\star)^r+(4c_vQ)^r\right], \qquad \mathcal J(4M)=r^{-r}(16M)^r.$$ Thus, $\epsilon$ enters through $p,r$ and through $h,Q_1(h),W_1(h)$. We fix $\epsilon<1/2$ and do not claim uniform constants as $\epsilon\uparrow1/2$ or as an energy-absorption margin vanishes. ## **Question: Is Assumption 3 necessary?** Assumption 3 is a sufficient condition for our proofs, not a condition proved necessary. It yields $\|g_n\|\le dL$. Appendix I uses this pathwise bound to control squared-update energy and total stepsizes; Appendix J uses it for bounded noise increments and the adaptive-clock estimates needed for saddle avoidance. A variance bound alone does not justify those steps, so Assumption 3 cannot simply be deleted from the present proofs. Remark 3.9 and Appendix K.4 now explain its role without claiming intrinsic necessity. ## **Minor issue** “Nesterov-tyoe” has been corrected to “Nesterov-type.” We hope these revisions and clarifications address your concerns. We would welcome any further questions or discussion.

Thank you for your detailed response and clarifications. I will keep my original score unchanged.

Thank you for your positive assessment. We sincerely appreciate the time and effort you have devoted to this discussion.

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

This paper proposes ZO-AdaNesterov, which combines a zeroth-order gradient estimator, Nesterov momentum, and an adaptive scalar stepsize based on previously observed estimates. The analysis has two parts: finite-time complexity bounds for convex and nonconvex objectives, and asymptotic results showing vanishing gradients and avoidance of strict saddle manifolds under additional assumptions. The authors emphasize improved dimension dependence and the ability to handle unbounded stochastic oracles in the complexity analysis. Experiments cover tensor decomposition, language-model fine-tuning, and additional tasks. The most substantial contribution appears to be the treatment of adaptive, biased stochastic dynamics rather than the update rule itself.

Critical strengths
  1. The paper develops finite-time convergence and almost-sure saddle-avoidance results for the same adaptive momentum method, with the different assumptions stated explicitly.
  2. Five-seed experiments and comparable tuning budgets give the empirical comparisons a reasonable foundation.
Critical weaknesses
  1. The finite-time bounds require m=⌈dmax⁡{1,2σ2T}⌉m=\lceil d\max\{1,2\sigma^2T\}\rceil samples per iteration. This is far above the small direction counts used in the large-model experiments, so those bounds do not explain the method’s practical operating regime.
  2. The convex guarantee controls a fractional moment of the objective gap. This does not imply the usual expected-gap guarantee, so the headline complexity comparison needs qualification, the earlier ZO-AdaMM convex analysis controls expected average regret (ZO-AdaMM, Section 5).
Questions for authors

What finite-time guarantees remain available with the small number of directions used in your experiments, given that Theorems 3.1 and 3.3 require m=⌈dmax⁡{1,2σ2T}⌉m=\lceil d\max\{1,2\sigma^2T\}\rceil?

1 comment

Thank you for identifying these limitations. The revision distinguishes the error criteria and adds finite-time results for small direction counts. All newly added or revised text in the manuscript is highlighted in blue.

Weakness 1 and Question 1: Finite-time guarantees with small direction counts

Thank you for this question. We agree that the batch-size condition in the original Theorems 3.1 and 3.3 does not directly cover small direction counts. To address this limitation, in the revised manuscript, Proposition 3.10 and Appendix K.2 now establish finite-time guarantees for any fixed m≥1m\ge1, including m=1m=1, without changing the algorithm's update rule.

Under the original oracle assumptions, with μn=μ1/n\mu_n=\mu_1/n, 0<μ1≤1/d0<\mu_1\le1/d, r=1/2−ϵ>0r=1/2-\epsilon>0, and suitable horizon-dependent choices of a,ba,b, the bounds are

\le C_C\left[ \frac{1+d/m}{T} +\sqrt{\frac{d\sigma^2}{mT}} \right]$$ for convex objectives, and $$\left(\mathbb E[\\|\nabla f(w_R)\\|^{2r}]\right)^{1/r} \le C_N\left[ \frac{1+d/m}{T} +\sqrt{\frac{d\sigma^2}{mT}} \right]$$ for lower-bounded smooth objectives, where $R$ is independent and uniform on $\{1,\ldots,T\}$. The constants are independent of $d,m,T,\sigma$. For $1\le m\le d$, substituting the total query count $N=2mT$ gives $$O\left(\frac dN+\sqrt{\frac{d\sigma^2}{N}}\right)$$ for both displayed error criteria. Consequently, **Corollary K.2** retains the query-complexity orders $$N_C=O\left(\frac d\delta+\frac{d\sigma^2}{\delta^2}\right), \qquad N_N=O\left(\frac d{\delta^2}+\frac{d\sigma^2}{\delta^4}\right),$$ for achieving $\mathbb E[(f(\bar w_T)-f^\ast)^r]\le\delta^r$ and $\mathbb E[\\|\nabla f(w_R)\\|^{2r}]\le\delta^{2r}$, respectively. Thus, small batches can preserve the total query-complexity order. ## **Weakness 2: Fractional moments versus expected objective gaps** We agree that a bound on $\mathbb E[(f(\bar w_T)-f^\ast)^r]$ for $r<1$ does not imply a standard expected-gap bound. Table 1 and the accompanying discussion now distinguish our fractional-moment criterion from ZO-AdaMM's expected average-regret guarantee on a bounded constraint set. We no longer claim a criterion-independent improvement in expected objective-gap complexity. Appendix K.3 explicitly gives the Markov-based high-probability consequences and their failure-probability dependence. We hope these revisions and clarifications address your concerns. We would welcome any further questions or discussion.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.