研究黑箱优化中精度与计算成本的权衡，给出实际运行时间最优的策略。
Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity
- 构建了考虑查询精度和代价的实时优化模型
- 发现加速算法未必比普通方法更快
- 给出在什么条件下固定精度最省时
零阶（黑箱）优化适用于梯度不可得、目标评估依赖高成本仿真的情形。许多场景中，查询精度可调：高精度降低噪声但增加计算开销。为此，本文提出一种精度感知的实时模型，每个精度为δ的查询代价为c(δ)，目标是最小化总时间T_total = ∑_{k=1}^N c(δ_k)，同时满足目标精度约束。我们揭示了优化算法、噪声模型与查询策略如何共同决定最优参数选择。例如，加速方法在某些情况下反而比非加速方案耗时更长。此外，我们刻画了常数精度策略在渐进意义下最优的条件。该框架统一了收敛性保证到实际查询精度与批处理建议的映射。
原文摘要 · Abstract (English)
Zeroth-order (black-box) optimization is applied when gradients are unavailable and objective evaluations rely on expensive simulations. In many such applications, the oracle fidelity is tunable: higher-accuracy queries reduce noise but incur higher computational costs. To capture this trade-off, we study an accuracy-aware wall-clock model where each query with fidelity $δ$ has a cost $c(δ)$, and we minimize the total time $T_{\mathrm{total}} = \sum_{k=1}^{N} c(δ_k)$, subject to a target accuracy constraint. We show how the choice of oracle type, noise model, and optimization scheme induces explicit wall-clock-optimal choices for the algorithmic parameters. For instance, we demonstrate that accelerated methods can be wall-clock inferior to non-accelerated schemes. Furthermore, we characterize the conditions under which a constant fidelity strategy is optimal in the Big-O sense. Our framework provides a unified methodology to translate convergence guarantees into practical fidelity and batching recommendations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。