{"id":"arxiv/2605.31346","url":"https://arxiv.org/abs/2605.31346","tags":["math.OC","cs.LG"],"score":0,"title":"Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity","domain":"math.OC","source":"arxiv","authors":["Alexandra Suvorikova","Igor Pavlov","Artem Vasin","Georgii Bychkov","Anastasia Antsiferova","Darina Dvinskikh","Alexander Gasnikov"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-29","reactions":{}}