- 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
-
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.
-
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.
-
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.
-
Minor corrections:
- Section 6.3: “As shown on Figure 5” → “As shown in Figure 5.”
- Theorem D.3: should be 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
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 . For constant , the factor in the per-update guarantee is offset by the 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 with , , and . With fresh independent Gaussian subspaces and step size , Align's expected loss contracts by a factor per update. One two-direction update and two singleton updates both use two directions, but their expected loss factors satisfy . 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.
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 setting, let g=∇f(x) and consider 1≤q≤d independent standard Gaussian directions. Avg has mean g, while Align has mean (q/d)g. Multiplying Align by d/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.