acceptodds
Under review as a conference paper at ICLR 2027

The Multi-Query Paradox in Zeroth-Order Optimization

Abstract

Zeroth-order (ZO) optimization provides a powerful framework for problems where explicit gradients are unavailable and have to be approximated using only queries to function values. The prevalent single-query approach is simple, but suffers from high estimation variance, motivating a multi-query paradigm to improve estimation accuracy. This, however, creates a critical trade-off: under a fixed budget of queries (i.e. cost), queries per iteration and the total number of optimization iterations are inversely proportional to one another. How to best allocate this budget is a fundamental, under-explored question. This work systematically studies this query allocation problem. We analyze two aggregation methods: the de facto simple averaging (ZO-Avg), and a projection-based rule (ZO-Align), which we derive from local surrogate minimization. By deriving convergence rates for both methods that make the dependence on the number of queries explicit across strongly convex, convex, and non-convex settings, we uncover aggregation-dependent allocation behaviors: For ZO-Avg, we prove that using more than one query per iteration is always query-inefficient, rendering the single-query approach optimal. On the contrary, ZO-Align generally performs better with more queries per iteration, resulting in a full-subspace estimation as the optimal approach. Thus, our work clarifies that the multi-query problem boils down to a choice not about an intermediate query size, but between two classic algorithms, a choice dictated entirely by the aggregation method used. These theoretical findings are also consistently validated by extensive experiments.

Primary area:
optimization
Keywords:
Zeroth Order Optimization

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_6NBTOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to allocate a fixed query budget across iterations in zeroth-order optimization. It compares simple averaging (ZO-Avg) with projection-based aggregation (ZO-Align) and derives convergence guarantees under strongly convex, convex, and non-convex settings, with a stochastic extension. The bounds favor single-direction updates for ZO-Avg, whereas ZO-Align favors full-subspace queries in the strongly convex setting and yields allocation-insensitive guarantees in the general convex and non-convex settings. Experiments on classical optimization problems, LQR control, and language model fine-tuning support the analysis.

Critical strengths

The paper offers an interesting perspective on zeroth-order optimization by studying query allocation under a fixed total budget. The projection-based aggregation method is also appealing, with a clear geometric interpretation and a natural derivation from local surrogate minimization.

Critical weaknesses

The comparison with prior work and the discussion of the theoretical results are relatively limited. More explicit comparisons with existing convergence guarantees and deeper discussion of the findings would help clarify the paper’s contributions and practical implications.

Questions for authors
  1. Could the authors clarify whether the limited benefit of additional queries in ZO-Avg stems from not accounting for the geometry of the sampled directions? Since ZO-Avg and ZO-Align also differ in bias and scaling, discussing these factors would strengthen this interpretation.

  2. Please provide explicit convergence-rate comparisons with related work under comparable assumptions and query budgets. Additional remarks would help clarify the strengths and implications of the proposed bounds.

  3. In the broader convex and non-convex settings, the ZO-Align bounds depend only on the total query budget. Please discuss what this implies about the trade-off between per-iteration sampling and the number of updates, and whether allocation insensitivity reflects an intrinsic property or a limitation of the bounds.

  4. Minor corrections:

    • Section 6.3: “As shown on Figure 5” → “As shown in Figure 5.”
    • Theorem D.3: xTx_T should be xˉT\bar{x}_T when referring to the weighted average.
    • Theorem D.4: “initialization error dominate” → “the initialization-error term dominates.”
    • Please use consistent terminology for “Simple Averaging” and “Naive Averaging.”
3 comments
AuthorsOpenReview ↗

Response to Reviewer 6NBT (1/2)

Thank you for recognizing the value of studying query allocation under a fixed budget. Below we respond point by point.

Sampling geometry, bias, and scaling (W1, Q1)

Thank you for this question. The effect of sampling geometry persists after matching bias and scaling, as can be seen directly from the estimators in Section 3. In the μ→0\mu\to0 setting, let g=∇f(x)g=\nabla f(x) and consider 1≤q≤d1\le q\le d independent standard Gaussian directions. Avg has mean gg, while Align has mean (q/d)g(q/d)g. Multiplying Align by d/qd/q makes both estimators unbiased, with MSEs

=\frac{d+1}{q}\|g\|^2, \qquad \mathbb E\left\|\frac dq\widehat g_{\mathrm{Align}}-g\right\|^2 =\frac{d-q}{q}\|g\|^2.$$ This difference reflects the random lengths and correlations of Gaussian directions. Align's Gram correction makes its idealized estimate depend only on the sampled subspace, while Avg retains dependence on the lengths and correlations of its basis vectors. At $q=1$, only length variation is involved. The normalization above can be paired with multiplying Align's step size by $q/d$, leaving its actual update unchanged. For orthonormal directions, the geometric difference disappears: $\widehat g_{\mathrm{Avg}}=\widehat g_{\mathrm{Align}}/q$, and matching step sizes gives identical updates. Thus the comparison depends on the specified sampling geometry as well as aggregation. The limited benefit of increasing $q$ for Gaussian Avg additionally involves the fixed-budget trade-off analyzed in Section 4: using more directions per estimate leaves fewer updates. With the prescribed step sizes, the coefficients of $\|g\|^2$ in the guaranteed one-step decrease are $q/[2L(q+d+1)]$ for Avg and $q/(2Ld)$ for Align. These coefficients are unchanged by rescaling an estimator and inversely rescaling its step. Dividing by the directional cost $q$, Avg's coefficient decreases with $q$, whereas Align's is constant. This connects the geometric distinction to Avg's single query preference in the convex/nonconvex bounds; the strongly convex bounds further retain contraction products, yielding the different allocation preferences established in the paper. **Query allocation and its relationship to existing guarantees (W1, Q2)** Thank you for asking for a clearer comparison. We do not claim a better convergence rate for a fixed choice of $q$. Our contribution is to make query allocation an explicit optimization variable in the convergence analysis, and to formulate and solve the resulting fixed-budget allocation problems. The cited subspace guarantees [1], [2] analyze convergence for a prescribed number of directions per update. Our analysis treats the direction counts across iterations, together with the number of updates, as decisions to be optimized under a common total budget. For a direct rate comparison, consider $L$-smooth objectives with attained minima, independent random subspaces, and exact directional derivatives. After matching normalization and step size to Align's update at $\eta=1/L$, and writing $K=Tq$, our fixed-$q$ Align analysis recovers the strongly convex contraction factor $(1-\gamma q/(dL))^{K/q}$ [1], where $\gamma$ denotes strong convexity. Its convex expected objective-error bound has the same $O(dLR_0^2/K)$ dependence as [2], and its nonconvex minimum expected squared gradient norm has the same $O(dL\Delta_0/K)$ dependence as [1]. Here $R_0$ is the initial distance to a minimizer and $\Delta_0$ the initial objective gap. These comparisons establish the connection to existing convergence theory. The allocation contribution is to express each aggregation's convergence bound as a function $\mathcal R_A(q_0,\ldots,q_{T-1})$ of the entire schedule, then minimize it over $T$ and $q_t\in\{1,\ldots,d\}$ subject to the directional budget $\sum_tq_t\le K$. Solving these problems under the prescribed step sizes shows that ZO-Avg's bounds are minimized by single-direction updates, while the strongly convex Align bound is minimized by full-dimensional updates with a possible remainder. Thus, the analysis determines how the accuracy gained from additional directions should be balanced against the number of affordable updates, and how that decision changes with the aggregation rule and objective class.
AuthorsOpenReview ↗

Response to Reviewer 6NBT (2/2)

Meaning of allocation-independent bounds (W1, Q3)

Allocation insensitivity is a property of these guarantees. It does not establish equal actual performance. In the convex/nonconvex Align analyses, the accumulated progress is weighted by ∑tqt/d=K/d\sum_tq_t/d=K/d. For constant qq, the factor qq in the per-update guarantee is offset by the T=K/qT=K/q available updates. The resulting bounds retain the total directional budget but do not distinguish the trajectories produced by different allocations. A simple exact example makes this distinction concrete. Consider f(x)=L∥x∥2/2f(x)=L\|x\|^2/2 with L>0L>0, d≥2d\ge2, and x0≠0x_0\ne0. With fresh independent Gaussian subspaces and step size η=1/L\eta=1/L, Align's expected loss contracts by a factor 1−q/d1-q/d per update. One two-direction update and two singleton updates both use two directions, but their expected loss factors satisfy 1−2d<(1−1d)21-\frac2d < \left(1-\frac1d\right)^2. The two-direction allocation therefore gives strictly smaller expected error despite the identical general convex guarantee.

More broadly, local strong convexity is a recurring structure in nonconvex optimization, with rigorous results for one-hidden-layer neural-network recovery [3], and LQR [4]. This gives the strongly convex allocation analysis practical relevance to optimization phases within locally strongly convex regions, even when the overall objective is nonconvex. Our LQR experiments likewise show larger direction blocks benefiting Align, consistent with the broader point that allocation can matter beyond globally strongly convex problems.

Minor corrections (Q4)

Thank you for these corrections. We have corrected them in the revision.

References

[1] Kozak, David, et al. "A stochastic subspace approach to gradient-free optimization in high dimensions." Computational Optimization and Applications 79.2 (2021): 339-368.

[2] Kozak, David, et al. "Zeroth-order optimization with orthogonal random directions: D. Kozak et al." Mathematical Programming 199.1 (2023): 1179-1219.

[3] Zhong, Kai, et al. "Recovery guarantees for one-hidden-layer neural networks." International conference on machine learning . PMLR, 2017.

[4] Bu, Jingjing, et al. "LQR through the lens of first order methods: Discrete-time case." arXiv preprint arXiv:1907.08921 (2019).

Thank you for your response. Since you have addressed my concerns, I will keep my score unchanged.

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

This paper studies how to allocate a fixed query budget in zeroth-order optimization. It compares averaging independent Gaussian directional estimates (ZO-Avg) with a projection-based estimator (ZO-Align), and derives query-dependent convergence bounds under strongly convex, convex, non-convex, and stochastic convex assumptions. Optimizing these bounds favors single-direction updates for ZO-Avg, while ZO-Align favors full-subspace updates in the strongly convex setting and has allocation-independent bounds in the deterministic convex and non-convex settings. Experiments cover synthetic objectives, LQR control, and Qwen3-0.6B fine-tuning, with additional finite-smoothing ablations.

Critical strengths
  1. The fixed-budget perspective is useful. Comparing methods by total queries rather than iterations directly addresses whether improved estimation accuracy compensates for fewer optimization updates. Making the query-block dependence explicit across several objective classes provides a coherent framework for examining this trade-off.
  2. The paper examines important limits of its conclusions. The high-dimensional analysis explains why ZO-Align approaches a rescaled ZO-Avg update when the query block is small relative to dimension. Appendix B also shows that finite smoothing can change the preferred allocation, providing useful context for interpreting the idealized theory.
Critical weaknesses
  1. The central optimality claims exceed what the analysis establishes. The results optimize particular convergence upper bounds using step sizes chosen to maximize a smoothness-based descent guarantee. A smaller upper bound does not, by itself, establish smaller actual optimization error or an optimal allocation among all admissible step-size schedules. Moreover, Theorems 4.5 and 4.7 are allocation-independent for ZO-Align, rather than establishing that full-subspace estimation is preferable. The stochastic result is additionally restricted to an initialization-dominated approximation. These distinctions matter because resolving the allocation question is the paper’s main contribution. The query-cost convention also needs clarification. The analysis imposes a budget on the number of directions, whereas the one-sided estimator generally requires an additional evaluation of the current objective per iteration. Unless this value is already available without cost, a block of q directions costs q+1 function evaluations. This overhead disproportionately affects single-direction updates and is consequential to the fixed-budget comparison.
  2. The contribution relative to existing random-subspace and orthogonal-direction methods is insufficiently established. In the idealized regime, writing U=QR gives ZO-Align as QQᵀ∇f, which is a random-subspace projected-gradient update. The discussion mainly connects this estimator to sparse gradient recovery, but does not adequately position it against the more directly related stochastic subspace literature. A comparison with orthogonal-direction aggregation would also help distinguish the effects of aggregation from those of direction norms and correlations. Without this positioning, it is difficult to assess how much of the proposed dichotomy represents a new principle rather than a comparison between two established estimator geometries.
Questions for authors

1.Clarification of optimality: Are the allocation claims intended to concern only the displayed upper bounds under the prescribed step sizes? Is there a tightness argument or direct error comparison supporting the stronger statements about actual query efficiency? 2.Clarification of query accounting: Do the reported budgets include evaluations of f(x_t), or only perturbed evaluations? If baseline evaluations are excluded, how are they obtained without additional cost, and does the allocation ordering persist when all function evaluations are counted? 3.Clarification of novelty: What theoretical conclusions are new relative to stochastic subspace descent and zeroth-order optimization with orthogonal random directions? How does the claimed dependence on aggregation change when the queried directions are orthonormal?

2 comments
AuthorsOpenReview ↗

Response to Reviewer ZViV (1/2)

We thank the reviewer for the valuable comments. Below we respond point by point.

Scope of optimality and actual performance (W1, Q1)

Our main allocation theorems optimize the displayed convergence guarantees under prescribed step sizes. They favor q=1q=1 for Gaussian ZO-Avg, and full blocks with a possible remainder for strongly convex ZO-Align. As you note, Theorems 4.5 and 4.7 give allocation-independent Align bounds in the general convex and nonconvex settings. The stochastic Align conclusion concerns the initialization-dominated term under the stated shared-sample and variance assumptions. These regimes and step policies are part of the guarantees; they do not establish optimality over arbitrary step-size schedules.

A direct comparison of actual errors is available on f(x)=L∥x∥2/2f(x)=L\|x\|^2/2, with x0≠0x_0\ne0, where symmetric differences are exact. For the isotropic quadratic, consider fresh independent Gaussian blocks of a fixed size q≤dq \le d dividing the directional budget KK, with step sizes ηAvg=q/[L(q+d+1)]\eta_{\mathrm{Avg}}=q/[L(q+d+1)] and ηAlign=1/L\eta_{\mathrm{Align}}=1/L. Using Gaussian fourth-moment identities and E[PU]=(q/d)I\mathbb E[P_U]=(q/d)I, we obtain exact expressions for the expected final-to-initial loss ratio R(q)=E[f(xK/q)]/f(x0)R(q)=\mathbb E[f(x_{K/q})]/f(x_0): RAvg(q)=((d+1)/(d+1+q))K/qR_{\mathrm{Avg}}(q)=((d+1)/(d+1+q))^{K/q} for ZO-Avg, and RAlign(q)=(1−q/d)K/qR_{\mathrm{Align}}(q)=(1-q/d)^{K/q} for ZO-Align.

The Avg expression increases with qq, so singleton updates minimize the expected error. Full-dimensional Align reaches the minimum after one update whenever K≥dK\ge d. These are exact expected errors on this quadratic class, providing a direct allocation comparison beyond upper-bound optimization.

We also examine independently tuned steps on six constructed quadratics: geometric spectra from 1 to κ\kappa, random initialization with f(x0)=1f(x_0)=1, symmetric differences with μ=10−6\mu=10^{-6}, and a budget of B=8dB=8d function evaluations for constructing updates. Each block receives 12 step candidates on five tuning seeds; joint search considers 11–23 block sizes. In all six cases, it selects q=1q=1 for ZO-Avg and q=dq=d for ZO-Align. The table reports final objectives as mean ± sample SD over 20 disjoint evaluation seeds, with selected qq determined using tuning data only. This supports the allocation preferences after step tuning in these task and budget settings.

(d,κ)(d,\kappa)Avg, tuned q=1q=1Avg, tuned q=dq=dAlign, tuned q=1q=1Align, tuned q=dq=dZO-Avg selected qZO-Align selected q
(20, 2)0.0209 ± 0.01410.0666 ± 0.02970.0135 ± 0.0086(1.91±1.01)×10−5(1.91\pm1.01)\times10^{-5}120
(20, 3)0.0261 ± 0.01590.0743 ± 0.03120.0147 ± 0.0088(5.16±2.74)×10−4(5.16\pm2.74)\times10^{-4}120
(50, 2)0.0216 ± 0.00650.0629 ± 0.01400.0174 ± 0.0065(1.95±0.62)×10−5(1.95\pm0.62)\times10^{-5}150
(50, 3)0.0289 ± 0.00920.0738 ± 0.01450.0203 ± 0.0080(5.04±1.65)×10−4(5.04\pm1.65)\times10^{-4}150
(100, 2)0.0210 ± 0.00550.0777 ± 0.01100.0200 ± 0.0047(1.91±0.44)×10−5(1.91\pm0.44)\times10^{-5}1100
(100, 3)0.0249 ± 0.00500.0843 ± 0.00960.0221 ± 0.0056(4.91±1.19)×10−4(4.91\pm1.19)\times10^{-4}1100

Directional-query accounting (W1, Q2)

Thank you for pointing out the inconsistency in our estimator description and query accounting. Our experiments used symmetric two-sided finite differences, but we incorrectly wrote the estimator as one-sided in Section 3.1. The directional measurement used in the experiments is vt,i=f(xt+μut,i)−f(xt−μut,i)2μv_{t,i}=\frac{f(x_t+\mu u_{t,i})-f(x_t-\mu u_{t,i})}{2\mu}.

Our main MSE and convergence analysis assumes μ→0\mu\to0, where both one-sided and two-sided differences recover the same directional derivative u⊤∇f(x)u^\top\nabla f(x). Correcting the estimator description therefore leaves these idealized theoretical results unchanged.

Regarding accounting, qq denotes the number of sampled directions per update, KK the total directional budget, and BB the corresponding function-evaluation budget. The two-sided estimator queries only f(xt+μu)f(x_t+\mu u) and f(xt−μu)f(x_t-\mu u). It requires no additional evaluation of f(xt)f(x_t). Each two-sided directional estimate requires two evaluations, so B=2KB=2K. This factor is the same for every direction and block size. The constraints ∑t2qt≤B\sum_t2q_t\le B and ∑tqt≤K\sum_tq_t\le K describe exactly the same feasible allocations. The conversion therefore preserves the allocation conclusions under this budget model. We have corrected this inconsistency in the revised submission.

AuthorsOpenReview ↗

Response to Reviewer ZViV (2/2)

Contribution and orthonormal directions (W2, Q3)

Our contribution concerns query allocation within established ZO update rules. We agree with your identification of idealized ZO-Align as a random-subspace update. We explicitly connect it to stochastic subspace methods [1] and orthogonal-direction methods [2], and acknowledge the Gaussian covariance analysis and isotropic singleton precedent in [3]. Building on these ingredients, our comparative allocation analysis characterizes how the aggregation rule changes the trade-off between directional accuracy and the number of affordable updates across objective classes. It identifies when singleton or full-dimensional updates optimize the stated guarantees and when those guarantees leave allocation unresolved.

For orthonormal queried directions and the same directional measurements, the two estimates differ only by normalization: g^Avg=g^Align/q\widehat g_{\mathrm{Avg}}=\widehat g_{\mathrm{Align}}/q. Choosing ηAvg=qηAlign\eta_{\mathrm{Avg}}=q\eta_{\mathrm{Align}} gives identical updates, including finite differences along those same directions. Thus, after matching the steps, the two aggregations have the same allocation behavior.

Gaussian directions have random lengths and correlations, so the Gram correction generally changes the update beyond a scalar rescaling; at q=1q=1, only random length contributes. Orthonormal sampling removes both effects. The Gaussian Avg/Align distinction therefore depends on the specified sampling geometry as well as aggregation. The allocation question remains within the common orthonormal update rule: how should the fixed budget be divided between directions and updates? This connects the analysis to existing subspace methods while making its scope explicit.

References

[1] Kozak, David, et al. "A stochastic subspace approach to gradient-free optimization in high dimensions." Computational Optimization and Applications 79.2 (2021): 339-368.

[2] Kozak, David, et al. "Zeroth-order optimization with orthogonal random directions: D. Kozak et al." Mathematical Programming 199.1 (2023): 1179-1219.

[3] Bordelon, Blake, and Cengiz Pehlevan. "Learning curves for SGD on structured features." arXiv preprint arXiv:2106.02713 (2021).

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

The paper studies how to allocate a fixed query budget between the number of directions per update and the number of updates in zeroth-order optimization. It compares averaging independent Gaussian directional estimates (ZO-Avg) with projecting the gradient onto their span (ZO-Align). In the idealized zero-smoothing limit, it derives convergence bounds with explicit dependence on the direction count for strongly convex, convex, and non-convex objectives, together with a stochastic convex extension. The ZO-Avg bounds favor single-direction updates. For ZO-Align, the strongly convex bound favors full-dimensional updates, whereas the deterministic convex and non-convex bounds are allocation-independent. Experiments cover synthetic objectives, LQR, and language-model fine-tuning, including finite-smoothing ablations and a diagonal approximation to ZO-Align in high dimensions.

Critical strengths
  1. The paper studies a practically relevant question: how to balance the quality of each update against the number of updates affordable under a fixed query budget. Its unified comparison of averaging and projection-based estimators makes this trade-off explicit and offers a useful perspective on the design of zeroth-order methods.

  2. The work connects its theoretical analysis to controlled optimization problems, LQR, and language-model fine-tuning. The observation that the two aggregation approaches become nearly equivalent in high dimensions is useful for understanding when additional geometric processing is unlikely to help. The finite-smoothing and stochastic analyses also help delimit the applicability of the proposed conclusions.

Critical weaknesses
  1. The substantive contribution beyond existing work is not yet sufficiently established. Projection-based zeroth-order updates and important convergence results are already available in the stochastic subspace and orthogonal-direction literature, including Kozak et al. (2021, 2023). The paper's remaining contribution is primarily its unified allocation analysis, but the main claims present a broader resolution than this analysis supports. In particular, allocation preferences obtained by optimizing selected convergence bounds do not establish universally optimal choices for actual optimization performance. This limits both the demonstrated novelty and the strength of the central conclusion.

  2. The practical recommendations are not yet supported by a sufficiently clear and cost-consistent comparison. The paper studies a fixed function-evaluation budget, but its directional-query accounting is not clearly reconciled with the evaluations required by the implemented estimators. This distinction can affect the reported allocation ranking. The experiments illustrate behavior on several tasks, but they do not yet establish how much useful guidance the allocation principle adds beyond established methods under a consistent cost model and comparable tuning. The limited difference between the methods in high-dimensional fine-tuning further makes it important to identify where the proposed analysis changes practical decisions.

Questions for authors
  1. What is the main new insight beyond the existing stochastic subspace and orthogonal-direction literature, particularly Kozak et al. (2021, 2023)? Please explain which conclusions or design decisions become possible through the proposed allocation analysis that were not already supported by these earlier results.

  2. How broadly should the claimed allocation dichotomy be interpreted? Please distinguish recommendations supported by the theoretical guarantees from claims about actual optimization performance, and identify the problem regimes in which the preference for single-direction or full-subspace updates is justified. This would clarify whether the paper establishes a general allocation principle or useful guidance for particular settings.

  3. Do the reported allocation rankings remain when all function evaluations are counted consistently and the compared configurations receive comparable step-size tuning? Please distinguish comparisons using prescribed theoretical step sizes from comparisons of tuned performance, and use representative existing results to assess whether the central recommendation is robust to these choices.

  4. How does the proposed allocation perspective compare with established random-subspace and orthogonal-direction methods under the same budget? A focused comparison on an existing representative task, or a clear equivalence argument where appropriate, would help isolate what is gained from the allocation analysis beyond the underlying estimator or direction-sampling scheme.

  5. In which of the studied settings does the proposed allocation guidance offer a meaningful benefit over a well-tuned standard choice, and how large is that benefit once aggregation overhead is considered? The high-dimensional near-equivalence is itself informative; please explain what practical recommendation follows from it and where the framework has the strongest potential to improve query efficiency. A synthesis of the existing theory and results would help assess this value without requiring a new large-scale benchmark suite.

4 comments
AuthorsOpenReview ↗

Reponse to Reviewer nxpM (1/2)

We thank the reviewer for the valuable comments. Below we respond point by point.

Contribution (Q1, Q2, W1)

Our main insight is that the value of spending more directions on each update depends on the aggregation rule and the optimization budget. Improving a directional estimate does not by itself determine whether it is worth taking fewer updates. At the prescribed steps, our fixed-budget bounds favor single-direction Gaussian averaging, whereas the strongly convex projection bound favors full-dimensional updates. We study this allocation decision using established update rules, building on the projection methods and convergence analysis of [1,2], and the Gaussian covariance recurrence and isotropic singleton precedent of [3]. We make these connections explicit here.

Practical performance with tuned step size (Q2, Q3)

Our recommendations depend on the aggregation rule and problem regime. For idealized directional estimates at the prescribed steps, the fixed-budget bounds favor q=1q=1 for ZO-Avg. For ZO- Align, the strongly convex bound favors full-dimensional updates; the convex and nonconvex bounds are allocation-independent. These preferences also occur in exact expected errors. Consider f(x)=L∥x∥2/2f(x)=L\|x\|^2/2, with x0≠0x_0\ne0, where symmetric differences are exact. For the isotropic quadratic, consider fresh independent Gaussian blocks of a fixed size q≤dq \le d dividing the directional budget KK, with step sizes ηAvg=q/[L(q+d+1)]\eta_{\mathrm{Avg}}=q/[L(q+d+1)] and ηAlign=1/L\eta_{\mathrm{Align}}=1/L. Using Gaussian fourth-moment identities and E[PU]=(q/d)I\mathbb E[P_U]=(q/d)I, we obtain exact expressions for the expected final-to-initial loss ratio R(q)=E[f(xK/q)]/f(x0)R(q)=\mathbb E[f(x_{K/q})]/f(x_0): RAvg(q)=((d+1)/(d+1+q))K/qR_{\mathrm{Avg}}(q)=((d+1)/(d+1+q))^{K/q} for ZO-Avg, and RAlign(q)=(1−q/d)K/qR_{\mathrm{Align}}(q)=(1-q/d)^{K/q} for ZO-Align.

The Avg expression increases with qq, so q=1q=1 minimizes the expected error. ZO-Align reaches the minimum after one update whenever K≥dK\ge d. This establishes the contrast directly on this quadratic class. We also test independently tuned steps on six constructed well-conditioned quadratics below: geometric spectra from 1 to κ\kappa, random initialization with f(x0)=1f(x_0)=1, symmetric differences with μ=10−6\mu=10^{-6}, and budget 8d8d. Each block receives 12 step candidates on five tuning seeds. Joint search over 11–23 block sizes selects q=1q=1 for ZO-Avg and q=dq=d for ZO-Align in all six cases. The table reports final objectives, mean ± sample SD over 20 disjoint evaluation seeds.

(d,κ)(d,\kappa)Avg, tuned q=1q=1Avg, tuned q=dq=dAlign, tuned q=1q=1Align, tuned q=dq=dZO-Avg selected qZO-Align selected q
(20, 2)0.0209 ± 0.01410.0666 ± 0.02970.0135 ± 0.0086(1.91±1.01)×10−5(1.91\pm1.01)\times10^{-5}120
(20, 3)0.0261 ± 0.01590.0743 ± 0.03120.0147 ± 0.0088(5.16±2.74)×10−4(5.16\pm2.74)\times10^{-4}120
(50, 2)0.0216 ± 0.00650.0629 ± 0.01400.0174 ± 0.0065(1.95±0.62)×10−5(1.95\pm0.62)\times10^{-5}150
(50, 3)0.0289 ± 0.00920.0738 ± 0.01450.0203 ± 0.0080(5.04±1.65)×10−4(5.04\pm1.65)\times10^{-4}150
(100, 2)0.0210 ± 0.00550.0777 ± 0.01100.0200 ± 0.0047(1.91±0.44)×10−5(1.91\pm0.44)\times10^{-5}1100
(100, 3)0.0249 ± 0.00500.0843 ± 0.00960.0221 ± 0.0056(4.91±1.19)×10−4(4.91\pm1.19)\times10^{-4}1100

In low-dimensional problems where full blocks are affordable, our guarantees support full-dimensional updates. For very high-dimensional problems with feasible blocks q≪dq\ll d, single-direction averaging is a theoretically motivated default when function evaluations are the limiting resource. Here, Gram concentration additionally explains why geometric processing adds little to an update after scale compensation. The single query recommendation comes from ZO-Avg's allocation analysis. The high-dimensional approximation concerns aggregation at the same qq.

AuthorsOpenReview ↗

Response to reviewer nxpM (2/2)

Directional-query accounting (W2, Q3)

Thank you for pointing out the inconsistency in our estimator description and query accounting. Our experiments used symmetric two-sided finite differences, but we incorrectly wrote the estimator as one-sided in Section 3.1. The directional measurement used in the experiments is vt,i=f(xt+μut,i)−f(xt−μut,i)2μv_{t,i}=\frac{f(x_t+\mu u_{t,i})-f(x_t-\mu u_{t,i})}{2\mu}.

Our main MSE and convergence analysis assumes μ→0\mu\to0, where both one-sided and two-sided differences recover the same directional derivative u⊤∇f(x)u^\top\nabla f(x). Correcting the estimator description therefore leaves these idealized theoretical results unchanged.

Regarding accounting, qq denotes the number of sampled directions per update, KK the total directional budget, and BB the corresponding function-evaluation budget. The two-sided estimator queries only f(xt+μu)f(x_t+\mu u) and f(xt−μu)f(x_t-\mu u). It requires no additional evaluation of f(xt)f(x_t). Each two-sided directional estimate requires two evaluations, so B=2KB=2K. This factor is the same for every direction and block size. The constraints ∑t2qt≤B\sum_t2q_t\le B and ∑tqt≤K\sum_tq_t\le K describe exactly the same feasible allocations. The conversion therefore preserves the allocation conclusions under this budget model. We have corrected this inconsistency in the revised submission.

Query allocation within existing ZO methods (Q4)

Our study examines how an existing ZO method should divide a fixed function-evaluation budget between directions per update and the number of updates. Random-subspace and orthogonal-direction methods also face this allocation decision. The relevant comparison therefore varies qq within a fixed update family, with matched direction-sampling assumptions, evaluation accounting, and step-size policies. Our experiments follow this approach by comparing different allocations within each method.

The allocation analysis shows why an intermediate block size need not provide the best trade-off. Under the prescribed steps, the Gaussian ZO-Avg bounds favor singleton updates, while the strongly convex projection bound favors full-dimensional updates. The exact quadratic calculation and controlled tuning results above provide corresponding actual-performance evidence in the stated settings. These findings guide the choice of qq within established update rules and clarify when spending more directions on each update is worthwhile.

Practical guidance and reduced tuning burden (Q5)

The practical value of our allocation analysis is to reduce the need to tune the number of sampled directions. In the six controlled quadratic cases reported above, joint tuning of qq and the step size selects q=1q=1 for ZO-Avg and q=dq=d for ZO-Align, matching the allocations suggested by the analysis. In these settings, fixing the suggested qq and tuning only the step size recovers the same selected configurations with 12 rather than 132–276 candidate configurations per method and task. This provides a concrete reduction in hyperparameter search while retaining the performance of joint tuning in these experiments.

For high-dimensional problems, we recommend single-direction Gaussian averaging as a theoretically motivated default, with tuning focused on the step size. When feasible blocks satisfy q≪dq\ll d, Gram concentration shows that averaging and projection updates become close after scalar step compensation. This supports using simple averaging to avoid additional Gram-matrix processing when its effect on individual updates is limited.

References

[1] Kozak, David, et al. "A stochastic subspace approach to gradient-free optimization in high dimensions." Computational Optimization and Applications 79.2 (2021): 339-368.

[2] Kozak, David, et al. "Zeroth-order optimization with orthogonal random directions: D. Kozak et al." Mathematical Programming 199.1 (2023): 1179-1219.

[3] Bordelon, Blake, and Cengiz Pehlevan. "Learning curves for SGD on structured features." arXiv preprint arXiv:2106.02713 (2021).

Thank you for the response. The clarification about two-sided differences addresses my main concern about query accounting, and the additional step-size tuning experiments strengthen the comparison.

Two concerns raised in my original review remain:

  1. The revised paper does not clearly distinguish its new allocation conclusions from the implications of existing random-subspace and orthogonal-direction methods and their direction-count-dependent convergence guarantees.

  2. The analysis for general objectives optimizes convergence bounds at prescribed step sizes. The exact quadratic results support a special case, but do not justify the broader optimality claims retained in the revised abstract and conclusion.

I therefore maintain my rating of 2.

Thank you for your follow-up and for acknowledging the clarification on query accounting and the additional step-size tuning experiments. We have further revised the manuscript to clarify the relationship to prior work and the scope of our allocation conclusions.

  1. Clarifying the relationship to prior work.

We have revised the Introduction, Section 2, and Section 3.3 to clarify the relationship to existing work. The Introduction now explicitly credits established projection-based updates. Section 2 acknowledges that stochastic subspace and orthogonal-direction methods already provide direction-count-dependent convergence guarantees and discuss evaluation cost, and identifies our focus as optimizing the resulting guarantees over direction-count sequences under a common budget. Section 3.3 further states that, in the directional-derivative limit, ZO-Align coincides with stochastic subspace descent after step-size normalization. These changes distinguish the established update rules and convergence guarantees from the allocation analysis built upon them.

  1. Scope of optimality and the choice of step sizes.

We have revised the abstract and conclusion to explicitly describe our analysis as optimizing fixed-budget convergence bounds in the directional-derivative limit, using step sizes that maximize the standard smoothness-based one-step descent guarantee.

We first optimize the step size and then study query allocation. Proposition 4.1 identifies the step sizes that maximize the standard smoothness-based one-step descent guarantee. Other step sizes yield a weaker guarantee, making these analytically optimal choices a natural basis for our allocation analysis. In practice, learning rates are also tuned, typically through grid search, to obtain the best performance for a given configuration. Our theoretical analysis follows this optimization rationale by optimizing the step-size-dependent guarantee before examining how the query budget should be allocated.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.