# The Multi-Query Paradox in Zeroth-Order Optimization

arXiv: https://arxiv.org/abs/2509.15552 · HTML: https://mlsanity.com/paper/2509.15552/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 26 references that are in the map.
- First posted on arXiv 19 Sep 2025.

## Builds on (most cited first, 12 of 12)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Fine-Tuning Language Models with Just Forward Passes](https://mlsanity.com/paper/2305.17333/) (2023)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark](https://mlsanity.com/paper/2402.11592/) (2024)
- [Stochastic Zeroth-order Optimization in High Dimensions](https://mlsanity.com/paper/1710.10551/) (2017)
- [Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Sampling](https://mlsanity.com/paper/2003.13001/) (2020)
- [A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order](https://mlsanity.com/paper/1606.00498/) (2016)
- [Hessian-Aware Zeroth-Order Optimization for Black-Box Adversarial Attack](https://mlsanity.com/paper/1812.11377/) (2018)
- [Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization](https://mlsanity.com/paper/2405.16805/) (2024)
- [Zeroth-Order Supervised Policy Improvement](https://mlsanity.com/paper/2006.06600/) (2020)
- [Riemannian Accelerated Zeroth-order Algorithm: Improved Robustness and Lower Query Complexity](https://mlsanity.com/paper/2405.05713/) (2024)
- [Lazy Queries Can Reduce Variance in Zeroth-order Optimization](https://mlsanity.com/paper/2206.07126/) (2022)

## Built on by (most cited first, 4 of 4)

- [Powering Up Zeroth-Order Training via Subspace Gradient Orthogonalization](https://mlsanity.com/paper/2602.17155/) (2026)
- [Position: Zeroth-Order Optimization in Deep Learning Is Underexplored, Not Underpowered](https://mlsanity.com/paper/2605.15622/) (2026)
- [SubZero+: Memory-Efficient Adaptive Zeroth-Order LLM Fine-Tuning in Random Subspaces](https://mlsanity.com/paper/2608.15665/) (2026)
- [ZoAQ: Adaptive Zeroth-Order Querying via Query-Reuse Coupling](https://mlsanity.com/paper/2609.22115/) (2026)

## Abstract (arXiv)

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