acceptodds
Under review as a conference paper at ICLR 2027

ZoAQ: Adaptive Zeroth-Order Querying via Query-Reuse Coupling

Abstract

Zeroth-order optimization (ZOO) estimates updates from function evaluations, making perturbation queries a primary cost. Fixed budgets spend the same number of queries at every step, while adaptive controllers may offset their savings by using additional oracle calls to test estimator reliability. We introduce ZoAQ, an adaptive ZOO method built around query reuse. Rather than discarding past evaluations after each step, ZoAQ makes them useful for both the next update and the decision to query further. This enables adaptive query allocation without extra validation queries. Our analysis characterizes when this agreement identifies an update that supports descent and guides the controller to a sufficient query budget. On synthetic objectives, ZoAQ reduces queries by 43–48% relative to fixed baselines using 1.2M queries. In black-box attacks, it reaches 100% success with 320 and 625 average queries on MNIST and CIFAR-10, respectively. Across four OPT fine-tuning settings, ZoAQ saves 43–46% forward evaluations relative to fixed K = 4, with accuracy changes within tasks ranging from −0.018 to +0.010.

Primary area:
optimization
Keywords:
zeroth-order optimization, adaptive query allocation, query reuse, black-box optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_NWdeOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

ZoAQ adaptively allocates zeroth-order queries by reusing historical evaluations and testing the cosine similarity between a candidate gradient estimate and historical momentum. The paper analyzes estimation error, momentum tracking, and conditional descent, with experiments on synthetic optimization, black-box attacks, and language-model fine-tuning.

Critical strengths
  1. The controller is straightforward to implement. Its acceptance test requires no additional function evaluations, and newly acquired samples contribute to the current estimate.

  2. The analysis explicitly considers the trade-off between estimation error and staleness under historical reuse. Experiments cover several application settings.

Critical weaknesses
  1. The claimed advantage regarding validation-query overhead is poorly supported.Bollapragada & Wild (2023, §2.1) and Bollapragada et al. (2024, §2.3) already allow variance estimation using a subset of the current samples. These baselines do not inherently incur "validation-only" query costs. Furthermore, Appendix F.3 treats the base-point evaluation in one-sided differences strictly as statistical overhead, even though it actively contributes to gradient estimation and Appendix G.1 assigns the same K+1K+1 cost across all compared methods.

  2. The momentum-tracking assumption is restrictive and empirically unverified.Theorems 5.3 and E.3 require:∥m~t−1−ht∥≤κˉ∥ht∥,κˉ<1/2.\Vert{}\widetilde m_{t-1} - h_t\Vert{} \le \bar\kappa \Vert{}h_t\Vert{}, \qquad \bar\kappa < 1/\sqrt{2}. In fact, consider F(x)=x2/2F(x)=x^2/2 along the noiseless gradient-descent trajectory xt+1=0.95xtx_{t+1}=0.95x_t, with true gradient ht=xth_t=x_t. An EMA mt=0.9mt−1+0.1htm_t=0.9m_{t-1}+0.1h_t, initialized at zero, satisfies mt−1/ht→2m_{t-1}/h_t\to2, so its relative tracking error approaches 11. Bias correction does not change this limit. Thus, the required tracking condition need not hold even along such a simple deterministic trajectory.

  3. Theoretical guarantees do not cover the actual implementation. Algorithm 1 accepts a candidate at Kmax⁡K_{\max} even when the test fails. Theorems 5.3 and E.3 instead require a sufficiently large cap, thereby excluding this fallback. Corollary D.4 accounts for query costs but does not control the frequency or cumulative optimization effect of failed-test updates.

Questions for authors
  1. Which queries in the cited adaptive sampling methods are used exclusively for validation? How is the overhead attribution in F.3 consistent with the common accounting in G.1?

  2. Can the authors report momentum’s relative error against the true gradient and the fraction of iterations satisfying the tracking condition on synthetic objectives?

  3. How frequently does the algorithm hit Kmax⁡K_{\max} and update on a failed test? Can the convergence theory be extended to account for these fallback steps and the actual R-AdaZO update?

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

ZoAQ adaptively selects the number of fresh zeroth-order directions by combining stored direction-response records with newly acquired records and testing the resulting estimate against an EMA of accepted estimates. A failed cosine-consistency test adds queries to the same candidate; acceptance updates the optimizer and resets the next step to the minimum budget. The analysis bounds acquisition noise and staleness, propagates errors through the EMA, and derives conditional first-passage and normalized-descent guarantees. Experiments cover synthetic objectives, MNIST/CIFAR-10 attacks, and OPT LoRA fine-tuning, reporting reduced oracle calls with task-dependent quality trade-offs.

Critical strengths
  1. The controller makes productive use of acquired evaluations. Nested candidates preserve all queries acquired during expansion, and stored seeds/responses let history improve the estimate without another function evaluation. The acquisition-noise versus staleness decomposition and the pathwise EMA argument explicitly address overlapping histories rather than assuming accepted estimates are independent.

  2. Several controls go beyond a single fixed-budget comparison. Table 11 compares fixed-budget history reuse at K = 1 and K = 2 on attacks, while the appendices examine history size, threshold initialization, reset behavior, and a changing objective. The LLM tables report both accuracy and loss and acknowledge the OPT-13B SST-2 degradation, making the efficiency–quality trade-off visible.

Critical weaknesses
  1. The theoretical certificate is not established for the operating regime used in experiments. Theorems 5.2–5.3 require a sufficiently accurate EMA, a feasible threshold band, and a sufficient budget below the cap. The experiments use an unprojected threshold initialized at 1.0 (Tables 10 and 12), whereas Appendix C.3 explains why projection is needed to preserve the band. Appendix E also excludes the experimental coordinatewise preconditioner from the normalized-descent result. These limitations are disclosed, but the reported cosine traces do not measure true gradient alignment or demonstrate that the assumptions hold. Thus the main reliability interpretation remains conditional rather than validated for the implemented optimizer.

  2. The LLM evaluation does not isolate adaptive allocation from simply using fewer directions or fixed-budget reuse. Tables 12–13 compare primarily against fixed K = 4, while the main ZoAQ runs average only 2.17–2.28 directions. Fixed K = 1/2 and matched fixed-budget history-reuse controls are provided for other regimes but not for these fine-tuning experiments. For OPT-13B SST-2, accuracy falls from 0.938 to 0.920. Without a matched cost–quality frontier, the reported 43–46% FE reduction alone does not establish the value of the controller at model scale.

Questions for authors
  1. On synthetic objectives with accessible gradients, how often do the EMA tracking bound, feasible threshold band, positive true-gradient alignment, and cap-sufficiency condition hold? Please separate ordinary passes from forced acceptance at Kmax and compare projected versus implemented threshold updates.

  2. At comparable total forward-evaluation budgets, how does ZoAQ compare with fixed K = 1/2 and fixed-budget history reuse on the four OPT/task settings? Please use the same backbone, data, and checkpoint-selection protocol.

  3. Please reconcile the StatZO implementation description: Appendix F discusses a sample-variance condition and center-query overhead, whereas G.3 specifies a relative-norm test against the EMA. Which rule is executed in each regime, and which calls are included in its reported query totals?

Reviewer_4JhROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how to allocate queries per step in zeroth-order optimization. ZoAQ builds a candidate gradient from fresh directions plus recently stored query responses. It accepts the candidate when its cosine with an EMA of past accepted estimates exceeds an adaptive threshold, and otherwise adds more directions, so no validation-only queries are needed. The analysis covers the concentration–staleness trade-off of reuse, the soundness and completeness of the gate, and a bound on the accepted budget. Experiments on synthetic functions, black-box attacks, and LLM fine-tuning report substantial query savings over fixed-budget baselines.

Critical strengths

A practical, lightweight mechanism. Every query serves both the update and the acceptance test, and expansion is nested. Each step restarts from the minimum budget, so adaptivity comes at no extra oracle cost.

Broad evaluation. The experiments span three quite different regimes. They include ablations on the trigger metric, reset policy, threshold, history window, and an objective switch.

A useful view of reuse. The paper makes the concentration–staleness trade-off explicit. ZoAQ also outperforms a reuse-only baseline, which suggests the gains are not from reuse alone.

Critical weaknesses

The consistency signal may be largely self-referential. Each candidate shares many of its records with the EMA it is compared against, so a high cosine may reflect shared data rather than an accurate estimate. The gate also seems to bias updates toward past directions. It is therefore unclear whether the savings come from reliability-based allocation.

The theory seems disconnected from the experiments. Its assumptions appear to require far more directions than the method uses. The analyzed update and threshold also differ from those used in practice. In addition, the threshold plots suggest frequent fallbacks to the maximum budget, which the main theorem rules out.

The motivation may be overstated. It seems that classical norm and inner-product tests can be computed from the same samples, without validation-only queries. The inner-product test also shares the gate’s goal, but the paper does not discuss it.

The empirical evidence has gaps. LLM savings are compared only against a larger fixed budget, without a cost-matched baseline. Some reported numbers also appear internally inconsistent, for example the accept rates versus the average budgets.

Questions for authors

Given that the candidate and the EMA share many records, I wonder how much of the consistency score comes from this overlap. A score computed from fresh directions only, or a random-acceptance control with the same budget, might help clarify this.

Could the analysis be extended to the low-budget regime the method targets, where the number of directions is much smaller than the dimension? If not, it may be helpful to check on the synthetic tasks, where the true gradient is available, whether the tracking condition holds and how often the controller falls back to the maximum budget.

It would be interesting to see how ZoAQ compares with classical norm or inner-product tests computed on the same retained and fresh records, as this may better isolate the benefit of the proposed gate.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.