The Multi-Query Paradox in Zeroth-Order Optimization

Wei Lin, Qingyu Song, Hong Xu · 2025

Read The Multi-Query Paradox in Zeroth-Order Optimization by Wei Lin, Qingyu Song, Hong Xu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-15552.txt.

Introduction

Wei Lin, Qingyu Song, and Hong Xu study tuning when only function values can be probed. Some problems give no slope, so each step must guess the slope from a few probes. More probes per step sharpen the guess but eat the budget, leaving fewer steps. The team ask how to split a fixed probe budget best.

They compare two ways to merge probes. One is plain averaging, and the other is a new method built from a local stand in model. Their proofs give clear rates for both across many problem types. The verdict splits: with plain averaging, extra probes per step never pay off. With the new method, extra probes often do pay. The paper settles a basic budget choice.

Catalog record

CREATORWei Lin, Qingyu Song, Hong Xu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-15552

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

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 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. 1 Introduction Zeroth-order (ZO) optimization provides a powerful framework for problems where explicit gradient information is unavailable or prohibitively expensive to compute ( Conn, Scheinberg, and Vicente 2009 ) . Unlike first-order methods that rely on analytical gradients, ZO algorithms guide their search using only function value queries to approximate gradients. Typically, it is achieved by evaluating the objective function along one or more random directions and observing the change in function value ( Spall 2002 ; Mania, Guy, and Recht 2018 ) . This paradigm has recently gained significant attention due to its applicability to a wide array of challenging, high-dimensional problems, including fine-tuning of LLMs ( Malladi et al. 2023 ; Zhang et al. 2024 ) , policy optimization in reinforcement learning ( Sun et al. 2020 ) , and hyperparameter tuning ( Li et al. 2021 ) . The predominant approach in modern ZO optimization is the single-query method, where a gradient estimate is constructed using one random direction per optimization step ( Nesterov and Spokoiny 2017 ) . While foundational, these estimators are inherently noisy, with an estimation variance that often scales with the problem’s dimension ( Nesterov and Spokoiny 2017 ) . A natural extension to mitigate this issue is the multi-query approach, which employs a block of queries at each iteration to construct a more accurate gradient estimate ( Duchi et al. 2015 ) . However, this approach introduces a fundamental trade-off. Using multiple queries per iteration inverse proportionally reduces the total number of iteration steps that can be performed under a fixed budget of queries. A systematic investigation of the multi-query paradigm requires addressing two basic questions: (1) What is the most effective method for combining information from multiple query directions into a single, cohesive gradient estimate? (2) For a fixed total query budget, is it more efficient to perform many iterations with noisy, single-query estimates, or fewer iterations with higher-quality, multi-query estimates by consuming more queries per iteration? This work systematically addresses these questions. First, to resolve the aggregation problem, we propose a new multi-query estimator called Projection Alignment (ZO-Align), from the first principle of local surrogate minimization. While similar estimators have been proposed from the perspective of sparse gradient recovery ( Cai et al. 2022 ; Wang et al. 2018 ) , our optimization-centric derivation provides a more fundamental justification for the method, independent of any sparsity assumptions. For a comprehensive comparison, we also analyze the canonical strategy of simply averaging independent estimates (ZO-Avg) ( Duchi et al. 2015 ) . Our initial analysis of the estimators’ properties reveals that ZO-Align achieves a significantly lower mean squared error, motivating a deeper investigation into its performance within an optimization context. Second, to resolve the query allocation problem, we derive the convergence rates for algorithms using both ZO-Align and ZO-Avg, making the dependence on the number of queries used per iteration explicit. We then leverage these rates to formally pose and solve an optimization problem: for a fixed total query budget, find the best allocation of queries per iteration that minimizes the final optimization error. To ensure the generality and robustness of our conclusions, this entire theoretical framework is systematically applied across a wide spectrum of problem structures, including strongly convex, convex, non-convex, and stochastic settings. Our analysis reveals a stark dichotomy where the optimal allocation strategy is critically dependent on the chosen aggregation method. For ZO-Avg, we prove that it cannot effectively utilize information from multiple queries; any attempt to use more than one query per iteration is detrimental, and the optimal strategy is always the single-query approach. In direct contrast, the ZO-Align estimator is capable of efficiently harnessing multi-query information. For ZO-Align, we prove that performance improves with the number of queries, making the optimal strategy a full-subspace estimation where the number of queries matches the problem’s dimension. To complement our theoretical analysis, we conducted extensive experiments across a suite of optimization problems. The empirical results consistently validate our theoretical findings, demonstrating the practical implications of the query allocation dichotomy. Our work clarifies that the choice is not about finding an optimal intermediate query size, but rather a commitment to an aggregation method that dictates whether the optimal algorithm is a sequential single-query method or a full-subspace estimation. The primary contributions of this work are as follows: • We propose the ZO-Align estimator based on local surrogate minimization, providing a clear optimization-centric perspective that complements existing geometric interpretations. • We deliver the first comprehensive convergence analysis that directly compares ZO-Avg and ZO-Align across strongly convex, convex, non-convex, and stochastic settings, revealing a fundamental and consistent dichotomy in their performance. • We provide rigorous theoretical proofs that under a fixed query budget, the optimal query allocation for ZO-Avg is always single-query, whereas the optimal allocation for ZO-Align is to use the maximum possible number of queries, resolving the query allocation question for these two classes of estimators. • We empirically verify our theoretical findings, demonstrating that ZO-Align with a large query size significantly outperforms both ZO-Avg and single-query baselines across various optimization settings. 2 Related Work ZO gradient estimation. Zeroth-order optimization approximates gradients using finite-difference techniques, a concept explored through various random perturbation strategies. For instance, theoretical convergence has been demonstrated using Gaussian random noise perturbations ( Nesterov and Spokoiny 2017 ) , while other approaches have utilized uniform sampling ( Flaxman, Kalai, and McMahan 2004 ) and coordinate-wise perturbations ( Lian et al. 2016 ) . A distinct line of research focuses on problems where the gradient is assumed to be sparse, framing the estimation task as one of compressed sensing; here, techniques like LASSO ( Wang et al. 2018 ) or other forms of regularized regression ( Choromanski et al. 2020 ) enable the reconstruction

Read the complete text