Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911733231124480 |
|---|---|
| author | Suvorikova, Alexandra Pavlov, Igor Vasin, Artem Bychkov, Georgii Antsiferova, Anastasia Dvinskikh, Darina Gasnikov, Alexander |
| author_facet | Suvorikova, Alexandra Pavlov, Igor Vasin, Artem Bychkov, Georgii Antsiferova, Anastasia Dvinskikh, Darina Gasnikov, Alexander |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_31346 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity Suvorikova, Alexandra Pavlov, Igor Vasin, Artem Bychkov, Georgii Antsiferova, Anastasia Dvinskikh, Darina Gasnikov, Alexander Optimization and Control Machine Learning 90C56, 68Q25 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. |
| title | Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity |
| topic | Optimization and Control Machine Learning 90C56, 68Q25 |
| url | https://arxiv.org/abs/2605.31346 |