The Multi-Query Paradox in Zeroth-Order Optimization

Wei Lin, Qingyu Song, Hong Xu

Abstract

Zeroth-order (ZO) optimization provides a powerful framework for problems where explicit gradients are unavailable and must be approximated using only queries to function values. While the prevalent single-query approach is simple, it often suffers from high estimation variance, motivating a multi-query paradigm to improve accuracy. However, this creates a critical trade-off: under a fixed query budget, the number of queries per iteration and the total number of iterations are inversely proportional. This work systematically resolves the query allocation problem by analyzing two aggregation methods: simple averaging (ZO-Avg) and a new Projection Alignment method (ZO-Align) derived from local surrogate minimization. We uncover a stark dichotomy: for ZO-Avg, using more than one query per iteration is always query-inefficient, making the single-query approach optimal. Conversely, ZO-Align generally performs better with more queries per iteration, favoring a full-subspace estimation. These theoretical findings are validated through extensive experiments on both synthetic benchmarks and large language model (LLM) fine-tuning.

Introduction

Zeroth-order (ZO) optimization is an essential tool for "black-box" scenarios where gradients are inaccessible, such as fine-tuning large language models (LLMs), reinforcement learning, or hyperparameter tuning. In these settings, gradients are estimated by querying the objective function at random perturbations. A fundamental challenge arises in the Query Allocation Problem: given a fixed total budget of $B$ queries, should one perform many iterations with a single query (noisy but frequent updates) or fewer iterations with many queries (accurate but infrequent updates)?

Methodology: Aggregation Strategies

The efficiency of multi-querying depends critically on how individual query results are aggregated. This paper investigates two primary strategies:

  1. ZO-Avg (Simple Averaging): The standard approach where $q$ random directions are sampled, and their directional derivative estimates are averaged. While simple and parallelizable, it ignores the geometric correlations between the sampled directions.
  2. ZO-Align (Projection Alignment): A novel method derived from minimizing a local quadratic surrogate. It utilizes a Gram matrix to account for correlations between query directions, effectively projecting the true gradient onto the sampled subspace.

The Sharp Dichotomy

The core theoretical contribution of this work is the identification of a sharp dichotomy in query efficiency. For ZO-Avg, the marginal benefit of variance reduction from additional queries is always outweighed by the linear increase in query cost. Consequently, a single query per iteration ($q=1$) is theoretically optimal across strongly convex, convex, and non-convex landscapes.

In contrast, ZO-Align benefits from maximizing the number of queries per iteration. Because it accounts for the geometry of the sampled subspace, each additional query provides non-redundant information, making high-query iterations more efficient in terms of progress per query.

Convergence of ZO-Avg and ZO-Align under fixed query budgets. For ZO-Avg, q=1 is best; for ZO-Align, higher q is better.

Experimental Validation

The theoretical findings were validated through extensive experiments on both classical optimization benchmarks and high-dimensional LLM fine-tuning tasks.

Benchmark Results

On standard functions (e.g., strongly convex quadratics, Rosenbrock), the dichotomy is clearly visible. As shown in Figure 1, for a fixed query budget, ZO-Avg consistently performs best with $q=1$. Conversely, ZO-Align achieves its best performance when $q$ is maximized (e.g., $q=1000$ for a budget of 20,000).

LLM Fine-tuning

The researchers fine-tuned the Qwen3-0.6B model on classification tasks like SST-2 and CB. In these high-dimensional regimes ($d \gg q$), random directions are nearly orthogonal, causing the Gram matrix in ZO-Align to concentrate toward a scaled identity.

Loss curves for fine-tuning Qwen3-0.6B on SST-2. The single-query approach (q=1) remains most efficient for ZO-Avg in high dimensions.

As seen in Figure 2, the "single-query king" status of ZO-Avg holds even for LLMs. While ZO-Align's geometric advantage is less pronounced in extremely high dimensions due to concentration effects, the overall trend confirms that the choice of $q$ is inextricably linked to the aggregation method.

Conclusion

This research resolves the multi-query paradox by showing that the optimal query allocation is not an intermediate value but a binary choice determined by the aggregation method. For simple averaging, one should always use a single query. For projection-based alignment, one should use as many queries as computationally feasible. This clarification provides a principled guide for practitioners designing zeroth-order optimization pipelines.

Summary updated

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 value. The prevalent single-query approach is simple, but suffers from high estimation variance, motivating a multi-query paradigm to improves 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 resolves this query allocation problem. We analyze two aggregation methods: the de facto simple averaging (ZO-Avg), and a new Projection Alignment method (ZO-Align) 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, non-convex, and stochastic settings, we uncover a stark dichotomy: 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.
BibTeX
@misc{lin2025multi,
  author = {Wei Lin and Qingyu Song and Hong Xu},
  title = {{The Multi-Query Paradox in Zeroth-Order Optimization}},
  year = {2025},
  eprint = {2509.15552},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.15552},
}

Loading related content...

Figure