acceptodds
Under review as a conference paper at ICLR 2027

Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity

Abstract

Zeroth-order (black-box) optimization is commonly applied when gradients are unavailable and objective evaluations rely on expensive simulations. In many such applications, the oracle fidelity is tunable: higher-accuracy queries reduce noise but incur higher computational costs. To capture this trade-off, we study an accuracy-aware wall-clock model where each query with fidelity has a cost , and we minimize the total time , subject to a target accuracy constraint. We show how the choice of oracle type, noise model, and optimization scheme induces explicit wall-clock-optimal choices for the algorithmic parameters. For instance, we demonstrate that accelerated methods can be wall-clock inferior to non-accelerated schemes. Furthermore, we characterize the conditions under which a constant fidelity strategy is optimal in the Big-O sense. Our framework provides a unified methodology to translate convergence guarantees into practical fidelity and batching recommendations. We apply this framework to several optimization schemes under various noise settings, including Tsybakov and adversarial noise.

Primary area:
optimization
Keywords:
zeroth-order optimization, oracle fidelity, wall-clock complexity

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_iP2TOpenReview ↗
Rating
1
Confidence
4(+2)
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies zeroth-order optimization with tunable function-evaluation accuracy and a fidelity-dependent cost model, $ c(\delta)=C\delta^{-\gamma}$. It develops fidelity-allocation rules and analyzes how evaluation accuracy, batching, smoothing, and acceleration affect computational cost. The theoretical results are illustrated through quadratic, regression, and classification experiments, together with a floating-point precision study intended to estimate the cost exponent.

Critical strengths
  1. The paper addresses a meaningful question: when more accurate function evaluations are more expensive, iteration complexity alone can give misleading guidance about computational efficiency.

  2. The allocation framework provides a useful way to organize the interaction between optimization error and evaluation cost. Comparing acceleration, batching, and fidelity within a common framework could be informative if the resulting guarantees are established correctly.

Critical weaknesses
  1. The batching argument requires a condition missing from the stated noise model. Definition 1 assumes bounded second moments and independence across repeated evaluations, but does not ensure that the noise contribution to the gradient estimator has zero conditional mean. Nevertheless, Appendix J, p.42, divides its uncentered second moment by BB. For conditionally i.i.d. noise contributions, E[∥nˉ∥2∣x]=1BE[∥n∥2∣x]+(1−1B)∥E[n∣x]∥2.\mathbb E[\|\bar n\|^2\mid x] = \frac{1}{B}\mathbb E[\|n\|^2\mid x] + \left(1-\frac{1}{B}\right)\|\mathbb E[n\mid x]\|^2. The omitted term need not vanish under Definition 1, which permits bounded, point-dependent deterministic perturbations. Consequently, Eq. (13) and Proposition 7 are not justified under the stated assumptions.

  2. The joint-optimization conclusion in Section 5.3 is contradicted by a feasible parameter choice within the paper’s own bound. Holding problem constants fixed, consider β=3\beta=3, γ=7/4\gamma=7/4, and N,B≍ε−1/2,h≍ε1/2,δ≍ε.N,B\asymp\varepsilon^{-1/2},\qquad h\asymp\varepsilon^{1/2},\qquad \delta\asymp\varepsilon. All terms in the large-batch error bound are O(ε)O(\varepsilon), while the cost is NBδ−γ≍ε−11/4NB\delta^{-\gamma}\asymp\varepsilon^{-11/4}. This improves upon both the reported accelerated rate ε−25/8\varepsilon^{-25/8} and the reported regularized rate ε−23/8\varepsilon^{-23/8}. The fixed-hh batching analysis therefore does not establish the claimed joint optimum or the resulting method-selection transition.

  3. The experiments do not adequately validate the practical recommendations. Appendix A.4 estimates γ\gamma from FP16 timing and its discrepancy from FP64 at a single fidelity level. This does not identify the exponent in Cδ−γC\delta^{-\gamma}, and the proposed estimate changes with the units used to measure time. Moreover, the GM/FGM fidelity searches are truncated at different theoretical sufficient thresholds, limiting their value as independent empirical comparisons. The modeled cost Nδ−γN\delta^{-\gamma} should also be distinguished more clearly from measured end-to-end runtime.

Questions for authors
  1. What assumption ensures E[nt∣xt]=0\mathbb E[n_t\mid x_t]=0 in Appendix J, and how would adding it change the scope of the claimed noise model?

  2. Is there an additional constraint excluding the parameter choice above? Otherwise, how should the joint complexity and the method-selection boundary in Section 5.3 be revised?

  3. Can the cost exponent be calibrated using measurements across multiple fidelity settings, and can the resulting recommendations be evaluated using actual runtime and a common fidelity search space?

8 comments

Thank you for the detailed verification. Your first two comments identify substantive problems in the stated assumptions and the joint optimization argument. We agree that these require corrections to the corresponding claims. We address each issue below.

Missing centering assumption in Appendix J.

We agree that Definition 1, as stated, does not imply E[nt∣xt]=0\mathbb{E}[n_t \mid x_t] = 0, and that point-dependent deterministic perturbations are a valid counterexample to the step in Appendix J. The omission is in the statement of Definition 1, not in Eq. (13): Eq. (13) is derived from Cor. 19 of Akhavan et al. (2024), which is proved under the assumption that (ξt,ξt′)(\xi_t, \xi_t') is independent of the randomization (ζt,rt)(\zeta_t, r_t) conditionally on xtx_t. We have added this condition to Definition 1. Under it, E[nt∣Ft]=d2ht E[ξt−ξt′∣Ft] E[K(rt)] E[ζt]=0,\mathbb{E}[n_t \mid \mathcal{F}_t] = \frac{d}{2h_t}\,\mathbb{E}[\xi_t - \xi_t' \mid \mathcal{F}_t]\,\mathbb{E}[K(r_t)]\,\mathbb{E}[\zeta_t] = 0, and the cross terms between batch copies vanish by the same factorization. Hence the term (1−1/B) ∥E[nt∣xt]∥2(1 - 1/B)\,\|\mathbb{E}[n_t \mid x_t]\|^2 is zero, and Eq. (13) and Proposition 7 hold as stated. Section 5.2 builds on Lobanov et al. (2024), who make the same assumption, so the correction covers that result as well. The added condition does not require E[ξt∣Ft]=0\mathbb{E}[\xi_t \mid \mathcal{F}_t] = 0: the noise may be biased, dependent across iterations, or non-random, as long as it does not depend on the randomization drawn at the current step (Akhavan et al. call this setting "almost adversarial"). What it excludes is an error that depends on the current random perturbation, in particular a deterministic function of the query point. Such errors are the subject of Definition 2 and Section 4, where the induced bias is not reduced by batching. The corrected definition thus makes explicit the division between the two noise models on which our conclusions rest. Our experiments on the γ=2\gamma = 2 batching threshold use fresh noise independent of the radius and the direction, and satisfy the corrected definition (see Section A5).

Updates in Section 5.3.

Your design is admissible, and we thank you for it. It exposes an unstated restriction and one incorrect claim in our text.

The accelerated rate in Section 5.3 was derived for batches B≤4κdB \le 4\kappa d (Appendix J.1, "in the small-batch regime"), but Section 5.3 did not state this restriction. In addition, Section 5.2 claimed that batches B>4κdB > 4\kappa d bring no leading-order gain for γ≤2\gamma \le 2. This holds for a fixed smoothing radius hh, but not when hh is optimized: the term NκdLh2/BN\kappa d L h^2/B restricts hh by h2≲εB/(NκdL)h^2 \lesssim \varepsilon B/(N\kappa d L), and this restriction weakens as BB grows. Your design uses B≍ε−1/2B \asymp \varepsilon^{-1/2}. No constraint excludes it: it coincides with the large-batch regime of Theorem 4.1 of Lobanov et al. (2024) (h≲ε1/(β−1)h \lesssim \varepsilon^{1/(\beta-1)}, Δ≲ε(3β+1)/(4(β−1))B1/2/d\Delta \lesssim \varepsilon^{(3\beta+1)/(4(\beta-1))} B^{1/2}/d) at this batch size.

New lemma in Appendix I proves the following. With M=max⁡{B,κ2d2/B}M=\max\{B,\kappa^2d^2/B\} and u=N/Mu=N/M, every admissible (N,B,δ,h)(N,B,\delta,h) satisfies NBδ−γ≳F(u)NB\delta^{-\gamma} \gtrsim F(u) for an explicit piecewise-power function FF, and every value F(u)F(u) is attained. This reduces the joint optimization to one variable and gives matching upper and lower bounds on the optimal cost under our error bound:

  1. B≤4κdB \le 4\kappa d: the design of Section 5.2 is jointly optimal over (N,B,δ,h)(N,B,\delta,h). In this regime the rates of Section 5.3 and the transition at γcrit(β)\gamma_{\mathrm{crit}}(\beta) hold as stated.
  2. No restriction on BB, β>7/3\beta>7/3, 1<γ<21<\gamma<2: the optimum is N∗≍RL/εN^\ast \asymp R\sqrt{L/\varepsilon}, h∗=H2≍(ε/(RκβLβ))1/(β−1)h^\ast = H_2 \asymp (\varepsilon/(R\kappa_\beta L_\beta))^{1/(\beta-1)}, B∗≍κd (H2/H1)2B^\ast \asymp \kappa d\,(H_2/H_1)^2, δ∗≍LH22/d\delta^\ast \asymp L H_2^2/\sqrt{d}, with T∗≍κd1+γ/2R2L2−γε−2H2−2(γ−1)T^\ast \asymp \kappa d^{1+\gamma/2}R^2L^{2-\gamma}\varepsilon^{-2}H_2^{-2(\gamma-1)}. For β=3\beta=3, γ=7/4\gamma=7/4 this is exactly the proposed design, with cost ε−11/4\varepsilon^{-11/4}. In all other cases with γ<2\gamma<2 the optimum is the design of Section 5.2.
  3. Batches up to Bˉ\bar B, 4κd≤Bˉ≤B∗4\kappa d \le \bar B \le B^\ast: the cost of case 1 is multiplied by (κd/Bˉ)γ−1(\kappa d/\bar B)^{\gamma-1}.

With batches B≍d,εd ε−bB \asymp_{d,\varepsilon} d\,\varepsilon^{-b}, 0≤b≤b∗(β)=3/2−2/(β−1)0 \le b \le b^\ast(\beta) = 3/2 - 2/(\beta-1), the boundary is γcrit(β,b)=(3−2b)(β−1)(3−2b)(β−1)−2.\gamma_{\mathrm{crit}}(\beta,b) = \frac{(3-2b)(\beta-1)}{(3-2b)(\beta-1)-2}. It equals our γcrit(β)\gamma_{\mathrm{crit}}(\beta) at b=0b=0 and reaches 22 at b=b∗(β)b=b^\ast(\beta). For β=3\beta=3 it is (3−2b)/(2−2b)(3-2b)/(2-2b): at γ=7/4\gamma=7/4 regularization is preferable for b<1/3b<1/3 and acceleration for b>1/3b>1/3. Your design has b=1/2b=1/2. Regularization can therefore be preferable only when the batch size is limited. With unrestricted batches, acceleration has the better ε\varepsilon-exponent for all γ<2\gamma<2 (by at least (2−γ)/(β−1)(2-\gamma)/(\beta-1) for β>7/3\beta>7/3). Section 5.3 and the Discussion now state the comparison in this form, and the batching statement of Section 5.2 is qualified ("at fixed hh").

Calibration of the cost model and independent runtime comparisons

We would like to clarify the primary intent behind Appendix A.4 and outline how we will improve its presentation. Our main goal in Appendix A.4 was to provide a concrete, illustrative example of applying our framework to an inexact function oracle. Specifically, we considered the scenario where the loss function values are evaluated using reduced-precision arithmetic. The reviewer is correct that the measurement units matter. In our theoretical model, such unit differences and system-specific overheads are intended to be absorbed by the constant C0C_0 in the cost function. Our intention was not to estimate γ\gamma from a single point (FP16 vs. FP64). Rather, in our framework, the exponent γ\gamma is meant to be estimated along the learning trajectory of the model. At its current stage, this appendix is presented strictly as an example of how the wall-clock-time model proposed in the main text could be instantiated, rather than a comprehensive empirical benchmark. In the revised manuscript, we will significantly improve the description of this approach. We will also consider how to develop such experiments further in the future to provide a more rigorous and fair empirical validation of the methods.

We would like to clarify that the differing truncation bounds for the δ\delta values were originally chosen based on the theoretical upper convergence bounds specific to each method (GM and FGM). However, we fully agree with the reviewer that, to conduct a rigorous and independent empirical comparison, both methods must be evaluated over the same interval of δ\delta values. Following your valuable suggestion, we conducted the proposed experiment (see Figure 4 in the new version of the manuscript).

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

This paper studies zeroth-order optimization with tunable evaluation accuracy, where an evaluation with error level δ\delta costs c(δ)=Cδ−γc(\delta)=C\delta^{-\gamma}. It derives optimal fidelity schedules for separable convergence bounds and studies their interaction with iteration budgets, batching, and smoothing. Applications cover adversarial and stochastic evaluation noise. The paper also develops an intermediate gradient method and compares accelerated and nonaccelerated schemes under the proposed cost model.

Critical strengths
  • Relevant computational trade-off. Accounting for evaluation accuracy and cost is useful when function values require simulations or approximate numerical procedures.
  • The theoretical results are interesting, particularly Theorem 1 and Proposition 5, help illustrate how gradient errors and the fidelity-cost exponent γ\gamma affect the resulting wall-clock complexity TcostT_{\text{cost}}.
  • Explicit error analysis. The separation between gradient estimation and optimization dynamics is useful. The time-varying error bound for IGM is also valuable, and its main proof appears internally consistent.
Critical weaknesses

Practical Motivation: Wall-Clock Optimization with Tunable Fidelity

  • I find the accuracy-aware wall-clock model, which explicitly accounts for the computational cost of oracle fidelity, interesting and potentially useful. However, the practical motivation is not sufficiently developed.
    • The introduction briefly mentions applications ("Tunable accuracy arises...") and prior studies ("Prior work has developed optimal schedules..."), but these discussions do not provide a clear picture of real-world applications or existing results in this research direction.
    • I would expect a more comprehensive discussion of practical examples and related work, particularly how the proposed framework differs from existing approaches (no related work at all).
  • The wall-clock optimization problem is well-formulated and makes sense to me. However, the assumptions underlying the model need stronger justification.
    • For example, Assumption 2 adopts a polynomial fidelity-cost model, c(δ)=Cδ−γc(\delta)=C\delta^{-\gamma}. Although the authors provide some intuition, I am not fully convinced of its practical generality. Real-world cost-fidelity relationships may be more complicated, potentially involving nonlinear transitions, minimum evaluation costs, or cutoff mechanisms. The paper acknowledges some of these limitations, but their implications for the proposed framework remain unclear.

Technical Contribution and Novelty

  • The paper does not clearly identify the main technical challenges or explain which aspects of the analysis require fundamentally new techniques beyond existing inexact-oracle optimization results.
  • While the proposed framework may be generalizable and useful, the technical novelty appears somewhat limited. A clearer discussion of the specific theoretical advances over prior work would help establish the significance of the contributions.

Presentation and Writing Issues

  • Introduction of γ\gamma. The role of γ\gamma is emphasized in the introduction and listed among the main contributions, but its meaning and significance are not sufficiently explained until Assumption 2. This makes the claimed contributions difficult to appreciate on a first reading.
  • Undefined abbreviations. Some abbreviations, such as FGM and ZO, are not defined at their first occurrence. Defining these terms earlier would improve readability.
Questions for authors
  • Could the authors provide more concrete real-world examples of tunable-fidelity zeroth-order optimization and discuss how their framework relates to existing studies on accuracy-aware computational costs? A clearer grounding in established applications and prior work is needed to justify the problem setting and its underlying assumptions, rather than developing the entire framework primarily from abstract modeling assumptions.
  • Could the authors clarify the main technical challenges and novel insights beyond the role of γ\gamma?
  • Given the potential generality of the proposed framework, could the authors discuss the conditions under which it can be extended to other optimization algorithms or oracle models?
2 comments

Thank you for the constructive assessment and for recognizing the value of the error analysis and the time-varying bound for the intermediate gradient method.

Concrete applications and relationship to existing work.

A direct application is bilevel learning for inverse problems. Evaluating an outer objective requires solving an inner reconstruction problem, and the stopping tolerance of that inner solver controls both evaluation accuracy and computational cost. Ehrhardt and Roberts (2021), Inexact Derivative-Free Optimization for Bilevel Learning, study precisely this setting, including learning regularization parameters. Another example is simulation-based parameter estimation or design, where each objective evaluation requires a numerical PDE solution. Mesh resolution and solver tolerances provide concrete fidelity controls. For example, under the assumptions that objective-evaluation error scales as hrh^r and computational work as h−qh^{-q}, eliminating the discretization scale hh gives \begin{equation*} c(\delta)\asymp \delta^{-q/r}. \end{equation*} This calculation explains one mechanism producing a polynomial cost law. The exponents depend on the discretization, regularity, and numerical solver.

Meaning, justification, and limitations of the polynomial cost model. \begin{equation*} c(\delta) = c_{\mathrm{ref}} \left(\frac{\delta}{\delta_{\mathrm{ref}}}\right)^{-\gamma}. \end{equation*} Here, δ\delta is the requested evaluation error level, and γ\gamma measures how expensive accuracy improvements are: halving the error increases evaluation cost by a factor 2γ2^\gamma. Assumption 2 describes a particular scaling regime. Its applicability should be assessed over the accuracy range used by the optimizer. Some evaluation procedures instead have logarithmic costs, substantial fixed overhead, discrete fidelity levels, or changes in scaling.

Technical challenges and contributions beyond introducing γ\gamma.

The sensitivity of accelerated methods to inexact oracles and the intermediate gradient method itself have substantial precedents in the work of Devolder, Glineur, and Nesterov. The additional analysis concerns the interaction of three components. First, function-value errors must be translated into gradient-estimation errors while retaining their dependence on smoothing and batching. For two-point estimators, decreasing the smoothing radius reduces approximation bias but amplifies evaluation noise, fidelity and smoothing therefore cannot be chosen independently. Second, the optimization analysis must retain the effect of errors at different iterations. The time-varying IGM bound provides the method-specific error-propagation information needed for fidelity allocation. Replacing the entire error sequence by its largest value would generally lose this information. Third, these error bounds must be combined with the full evaluation cost to compare choices of optimization dynamics, fidelity, smoothing, and batching. The distinction between stochastic variance, which independent averaging can reduce, and systematic bias, which persists under averaging, is essential to that comparison.

Conditions for extension to other methods and oracle models The allocation approach can be applied to another method when its analysis provides a suitable error certificate. For example, suppose effective oracle errors eke_k satisfy \begin{equation*} \mathcal R_N \le A_N+\sum_{k=0}^{N-1}w_{N,k}e_k, \qquad w_{N,k}>0, \end{equation*} and the cost of producing an oracle output with error eke_k is Ck(ek)C_k(e_k). For a fixed iteration budget, the allocation problem becomes \begin{equation*} \min_{{e_k}}\sum_{k=0}^{N-1}C_k(e_k) \quad\text{subject to}\quad \sum_{k=0}^{N-1}w_{N,k}e_k\le\varepsilon-A_N, \end{equation*} together with the feasible accuracy bounds.

For differentiable, decreasing, convex costs and a feasible problem, interior optimal allocations satisfy \begin{equation*} -\frac{C_k'(e_k)}{w_{N,k}}=\lambda, \end{equation*} with boundary conditions accounting for accuracy limits. Thus, polynomial costs give explicit formulas, while other admissible costs can be handled through numerical allocation.

Thank you for the rebuttal. I will keep my positive score. That said, I would still encourage the authors to provide a more comprehensive discussion of the motivation and related work, either in the main text or in the appendix.

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

This paper introduces a framework for ZO optimization with tunable oracle fidelity, which means that the estimation quality of gradient can be tuned with iteration NN and a oracle fidelity schedule {δk}\{\delta_k\}. It models the cost of queries as (1/precision)γ(1/\mathrm{precision})^\gamma, and takes the iteration steps, the batch size, the precision scheduler and the choice of algorithm into account to get the minimum wall-clock time. The conclusion is that when γ>1\gamma > 1, standard gradient descent (GD) is actually more cost-effective than Nesterov in the presence of adversarial noise, and when γ≥2\gamma \geq 2, increasing precision is less efficient than simply increasing the batch size under stochastic noise.


My evaluation became positive after rebuttal due to additional experiments and evidence to support the framework with appropriate ablations and bounds.

Critical strengths
  1. The framework is explicit and reusable. The Fidelity-separable bound in Definition 3 and the closed-form solution in Proposition 1 clearly show how to translate the bound of convergence into the optimal precision scheduling. Besides, the result in Equation 6 decouples the algorithm, the ZO estimator and the oracle, which is a systematic summary of relevant studies (Van Dessel & Glineur 2024; de Montbrun & Gerchinovitz 2024).

  2. The conclusion provides valuable insights. For example, the paper shows that Nesterov may perform worse than GD under the comparison of wall-clock time (for γ>1\gamma > 1) and that when γ≥2\gamma \geq 2, increasing precision is less efficient than simply increasing the batch size. Besides, the paper analyses the role of γ\gamma under different types of noise, providing meaningful guidance for the practical application of ZO methods.

Critical weaknesses
  1. The lack of main experiments. Though the paper provides some valuable insights and provides some experiment results in Appendix A, the main insight should be supported by more experimental results. For example, the paper indicates that when γ≥2\gamma \geq 2, increasing the batch size is better than increasing the precision, but does not provide relevant experiments. And the paper also lacks an experiment to show the advantage of the algorithm of IGM.

  2. The main conclusion, like the conclusion that when γ>1\gamma > 1, standard gradient descent (GD) is actually more cost-effective than Nesterov, is based on the comparison of upper bounds of FGM and GM and lacks a lower-bound guarantee. So, the conclusions stated in the paper may be too strong.

Questions for authors

The framework for tunable-fidelity ZO and the optimal scheduling scheme in the paper are like the framework and scheme proposed in Van Dessel and Glineur (2024). I would like to know what specific challenges arise when directly applying the framework from this related work to the analysis of ZO.

4 comments

We sincerely thank the reviewer for the detailed and constructive feedback. We are delighted that you found our framework explicit and reusable. We also highly appreciate your critical comments, which will help us significantly improve the manuscript. Below, we address each of your points in detail.

  1. Regarding the lack of experiments. We will try to conduct additional experiments, specifically in the revised version, we will expand the experimental section. In particular, we will add simulations across different regimes of γ\gamma to empirically demonstrate the result of Proposition 7. Furthermore, we will provide experiments demonstrating performance of IGM algorithm.

  2. Regarding the strength of the conclusions We agree that drawing definitive conclusions about the superiority of one method over another based solely on upper bounds can be misleading. We would like to clarify the scope of our claims and outline how we will address this in the revised manuscript. Our analysis does not aim to establish the fundamental, class-wide optimality of GD over Nesterov methods in the γ⩾1\gamma \geqslant 1 regime. Rather, our focus is strictly on a concrete, practical setup: we specifically analyze a gradient estimator based on a difference scheme combined with an intermediate gradient method. This specific combination is deliberately chosen because it guarantees a balance between the convergence rate and the accumulation of absolute error. In this sense, we propose one of the possible solutions to the stated problem for a zeroth-order oracle under adversarial noise. The comparison with FGM is intended to illustrate the practical trade-offs of this specific construction, rather than to make a universal claim. While a full lower-bound analysis is beyond the current scope of this paper, we will try to explicitly discuss the quality of our solution in the revised text.

  3. Regarding the application of the Van Dessel & Glineur (2024) framework to ZO. We agree that our framework builds upon the ideas of Van Dessel and Glineur (2024). The primary challenge in directly applying their framework to ZO optimization lies in the stochastic nature of the oracle noise. While Van Dessel and Glineur primarily assume a deterministic oracle, the gradient estimator in the ZO setting is inherently stochastic. This requires adapting their methodology to handle noise variance that is intricately coupled with the chosen precision δ\delta. The core challenge we address is how to effectively disentangle this deterministic error from the stochastic noise. Our proposed approach explicitly decouples the algorithm, the ZO estimator, and the oracle. This allows us to correctly adapt the fidelity-separable bound and apply the optimal scheduling scheme to the stochastic ZO setting.

Thank you for your reply. Response number 3 has addressed my concern adequately so that can be considered solved. However, given that the experimental results promised in the rebuttal are not yet complete, my major evaluations of this work still stand as is.

We have supplemented the paper with new experiments in Sections A2, A4, and A5, and we would be grateful if you could review these additions

Dear Authors:

I apologize for my previous oversight. I have checked your new experiments and results, and I consider my concerns adequately addressed. The goal of this paper is to establish a framework to minimize total cost under fixed accuracy by adjusting bs, query cost and other things, and I think the added experiments make this whole story self-sustained.

I will raise my score accordingly.

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

The paper addresses an underexplored, important question in 0th-order optimization, namely, the computation cost of evaluating the objective function at different accuracies rather than the previously studied number of function evaluations (under various error settings different from those in this paper).

The most interesting message is that an algorithm with better iteration complexity can be computationally inferior if it requires more accurate (thus more expensive) function evaluations -- while this is known to the community, it is very nice to see a formal analysis.

The authors use a common framework that involves fidelity allocation, gradient estimation, acceleration, and batching. I had high hopes for this paper, but as it is, its contributions are limited, as the techniques used are mainly syntheses of existing convergence arguments, and the experiments are relatively ideal.

Critical strengths
  • The topic and setup are important. Traditional ZO query complexity is practically misleading when, in actual applications, evaluations have adjustable precisions.

  • The setup and the convergence bounds present a unified perspective in the sense that they connect oracle noise, grad estimation, iteration dynamics, and total computational cost.

  • It shows that acceleration can counterintuitively reduce the number of iterations but increase the required accuracy of evaluations enough to make the total computation more expensive. It provides a basis to select algorithms not only considering just convergence rates but also their resilience to inexact oracles (though the experiments are still very limited).

  • The authors present an interpretable trade-off between improving individual evaluations and averaging more evaluations. Specifically, if oracle fidelity improvements are cheap, use more accurate evaluations; otherwise, use more inaccurate evaluations and average them (under their ideal stochastic noise model). They also show that adversarial and stochastic errors lead to different cost trade-offs.

Critical weaknesses
  • The choice of the phrase "wall-clock optimal" is too strong because the bound established is still the worst-case type. I understand that the setup considers computational cost that is more practical than the classic ones. That said, the convergence inequalities used do not necessarily reflect the "wall-clock." This distinction should be clarified. Even better, the authors could provide practical numerical evidence that the worst-case-driven algorithm-selection rules are commonly realized in practice.

  • Re. Proposition 7 and Appendix J: their stochastic batching analysis relies on an unbiasedness assumption. Inaccuracies in ZO oracles generally include both stochastic noise (unbiased) and non-stochastic errors (biased), and the latter often exists. Appendix J uses the argument that averaging BB realizations reduces the contribution of oracle noise by 1/B1/B -- if there are non-stochastic errors, this argument fails to hold. I don't know if there is an easy fix that won't affect the stochastic batching results.

  • I always keep an eye on novel analysis ideas and techniques. Van Dessel and Glineur (2024) already developed optimal inexactness schedules based on cost models and error-propagation weights. They included closed-form allocations for polynomial costs and made a case comparing with constant-fidelity strategies. In fact, Proposition 1 could be obtained from their allocation formula through a change of variables. The new contributions appear to be the specialization to noisy function-value oracles and the comparison of accelerated and non-accelerated iterations, the time-varying analysis for the intermediate gradient method, and the joint fidelity-batching analysis.

The paper could be stronger if it had provided convincing experiments. In its present form, I find the theoretical novelty and empirical evidence just shy of being sufficient for a top AI conference.

Questions for authors

I would appreciate if the authors could address my raised weaknesses.

2 comments

Thank you for recognizing the importance of accounting for fidelity-dependent evaluation costs and for identifying the aspects of the paper that require stronger justification. Your comments help us clarify the scope of the optimality claims, the assumptions behind batching.

Scope of the “wall-clock optimal” claim We agree that this phrase needs qualification. Our analysis bounds accumulated oracle cost under a prescribed fidelity-cost model. Optimizing such a bound establishes optimality for the corresponding allocation problem and convergence certificate. It does not establish minimax optimality in elapsed time or instance-wise superiority of one optimization method over another. In particular, comparing upper bounds for GD and accelerated methods does not prove a universal ordering of their actual runtimes. Also we add lower bound (Proposition 5) in the new version of the manuscript, so we would be grateful if you could review this addition.

Bias and the assumptions behind Proposition 7 and Appendix J. Thank you for raising this point. The batching step relies on a condition different from unbiasedness: the oracle error must not depend on the random direction and radius drawn at the current step. This is the noise assumption of Akhavan et al. (2024) and Lobanov et al. (2024), on which Section 5 builds; it was missing from our statement of Definition 1, and we have added it. Under this condition, the noise part of the estimator has zero conditional mean because E[ζt]=0\mathbb{E}[\zeta_t] = 0 and E[K(rt)]=0\mathbb{E}[K(r_t)] = 0, even when the oracle error itself is biased or non-random. Averaging BB copies therefore divides its contribution by BB, and the batching results are unchanged. We agree that systematic errors, such as discretization or rounding errors, usually depend on the query point. These errors fall under Definition 2. They induce a bias of order d κ δ/h\sqrt{d}\,\kappa\,\delta/h (Proposition 3) that batching does not reduce, and this is the mechanism behind the different roles of batching in Sections 4 and 5. When both types of error are present, batching reduces only the component satisfying Definition 1. We have added a sentence stating this after Remark 1.

Relationship to Van Dessel and Glineur (2024).

We agree that the generic allocation step should be credited more explicitly. Their Corollary 3.5 provides the polynomial-cost allocation rule, with accuracy proportional to (bk/ak)1/(r+1)(b_k/a_k)^{1/(r+1)}, and directly supports the connection highlighted by the reviewer. We will present the allocation step underlying Proposition 1 as a specialization of this framework and explain the corresponding change of variables. We will therefore focus the contribution statement on the additional analysis: deriving the function-value accuracy-gradient error-cost relationship for zeroth-order estimators. Combining it with the different error-propagation behavior of GD, accelerated methods, and the intermediate gradient method; and analyzing the joint choice of fidelity and batch size under different error models. The contribution we wish to emphasize is the resulting quantitative regimes for these choices.

Additional experimental evidence We have conducted an additional controlled experiment using the kernel two-point estimator from Definition 4 on the strongly convex Nesterov quadratic, with independent centered Gaussian function-value noise. We compare increasing the batch size at fixed oracle precision against improving precision with batch size one. Both strategies use the same stepsize and smoothing radius. Such experiment provided in Appendix A5, we would be grateful if you could review these additions.

We would like to thank you again for your valuable feedback on our paper. If our responses have successfully addressed your questions and concerns, we kindly ask you to consider updating your final score for the manuscript.

Comments on the paper

3 comments

We thank the reviewers for their valuable feedback. Below is a summary of the changes made in the revised version of the paper:

  1. Corrected the results in Propositions 4 and 6. We identified that a factor of dd was previously lost; this factor is necessary because the gradient estimate is computed at d+1d + 1 points.
  2. Added Proposition 5 to formally establish the lower bound.
  3. Added Figure 4, which provides a comparison between GM and FGM over identical ranges of δ\delta.
  4. Added Section A4, which presents additional convergence experiments for IGM.
  5. Added Section A5, demonstrating the over-batching boundary at γ=2\gamma = 2.
  6. Added a clarifying comment in Section A6 regarding the experiments used to estimate the wall-clock time model.
  7. Revised and corrected Section G.

Changes are marked in blue.

We thank the reviewers for their valuable feedback. Below is a summary of the second part of changes made in the revised version of the paper:

  1. Changes related to Definition 1 and Proposition 8 (formerly Proposition 7) are highlighted in olive.

  2. Changes related to the choice of the batching parameter are highlighted in magenta: Sections 5.2, 5.3, and Appendix I.

We thank the reviewers for their valuable feedback. Below is a summary of the third part of changes made in the revised version of the paper:

We added Section A6, which provides an experiment demonstrating a polynomial cost fit for an inexact function oracle based on numerical integration. Changes are marked in blue.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.