- 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
-
The paper addresses a meaningful question: when more accurate function evaluations are more expensive, iteration complexity alone can give misleading guidance about computational efficiency.
-
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
-
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 . For conditionally i.i.d. noise contributions, 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.
-
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 , , and All terms in the large-batch error bound are , while the cost is . This improves upon both the reported accelerated rate and the reported regularized rate . The fixed- batching analysis therefore does not establish the claimed joint optimum or the resulting method-selection transition.
-
The experiments do not adequately validate the practical recommendations. Appendix A.4 estimates from FP16 timing and its discrepancy from FP64 at a single fidelity level. This does not identify the exponent in , 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 should also be distinguished more clearly from measured end-to-end runtime.
Questions for authors
-
What assumption ensures in Appendix J, and how would adding it change the scope of the claimed noise model?
-
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?
-
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
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 (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 bring no leading-order gain for . This holds for a fixed smoothing radius , but not when is optimized: the term restricts by , and this restriction weakens as grows. Your design uses . No constraint excludes it: it coincides with the large-batch regime of Theorem 4.1 of Lobanov et al. (2024) (, ) at this batch size.
New lemma in Appendix I proves the following. With and , every admissible satisfies for an explicit piecewise-power function , and every value 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:
- : the design of Section 5.2 is jointly optimal over . In this regime the rates of Section 5.3 and the transition at hold as stated.
- No restriction on , , : the optimum is , , , , with . For , this is exactly the proposed design, with cost . In all other cases with the optimum is the design of Section 5.2.
- Batches up to , : the cost of case 1 is multiplied by .
With batches , , the boundary is It equals our at and reaches at . For it is : at regularization is preferable for and acceleration for . Your design has . Regularization can therefore be preferable only when the batch size is limited. With unrestricted batches, acceleration has the better -exponent for all (by at least for ). 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 ").
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 in the cost function. Our intention was not to estimate from a single point (FP16 vs. FP64). Rather, in our framework, the exponent 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 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 values. Following your valuable suggestion, we conducted the proposed experiment (see Figure 4 in the new version of the manuscript).
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, 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′) is independent of the randomization (ζt,rt) conditionally on xt. We have added this condition to Definition 1. Under it, E[nt∣Ft]=2htdE[ξt−ξt′∣Ft]E[K(rt)]E[ζt]=0, and the cross terms between batch copies vanish by the same factorization. Hence the term (1−1/B)∥E[nt∣xt]∥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: 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 batching threshold use fresh noise independent of the radius and the direction, and satisfy the corrected definition (see Section A5).