arXiv:2509.15552cs.LG2025-09被引 3

揭示零阶优化中多查询的悖论,证明不同方法下最优查询策略截然不同。

The Multi-Query Paradox in Zeroth-Order Optimization

  • 提出投影对齐新方法,优于传统平均法
  • 发现多查询在某些方法下反而更高效
  • 理论与实验验证:方法决定最优查询数

零阶优化在无法获取显式梯度时,通过函数值查询进行近似。主流单查询方法虽简单但方差高,促使采用多查询以提升精度。然而,在固定查询预算下,每轮查询数与迭代次数成反比,如何分配预算成为核心问题。本文系统分析两种聚合方法:通用的简单平均(ZO-Avg)和新提出的投影对齐(ZO-Align),推导其在强凸、凸、非凸及随机设置下的收敛速率,明确依赖于查询数量。结果揭示显著差异:对于ZO-Avg,每轮超过一个查询始终效率低下,单查询最优;而对于ZO-Align,更多查询每轮通常更优,最优策略为全子空间估计。因此,多查询问题本质是方法选择问题,由聚合方式决定。理论结果经大量实验一致验证。

原文摘要 · Abstract (English)

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.

零阶优化查询效率收敛分析

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。