| Autor: |
de Montbrun, Étienne, Gerchinovitz, Sébastien |
| Rok vydání: |
2023 |
| Předmět: |
|
| Zdroj: |
SIAM/ASA Journal on Uncertainty Quantification, 2024, 12 (4), pp.1135-1164 |
| Druh dokumentu: |
Working Paper |
| DOI: |
10.1137/23M1591086 |
| Popis: |
We consider the problem of multi-fidelity zeroth-order optimization, where one can evaluate a function $f$ at various approximation levels (of varying costs), and the goal is to optimize $f$ with the cheapest evaluations possible. In this paper, we study certified algorithms, which are additionally required to output a data-driven upper bound on the optimization error. We first formalize the problem in terms of a min-max game between an algorithm and an evaluation environment. We then propose a certified variant of the MFDOO algorithm and derive a bound on its cost complexity for any Lipschitz function $f$. We also prove an $f$-dependent lower bound showing that this algorithm has a near-optimal cost complexity. As a direct example, we close the paper by addressing the special case of noisy (stochastic) evaluations, which corresponds to $\eps$-best arm identification in Lipschitz bandits with continuously many arms. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
