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:
- 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.
- 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.
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.
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