Certified Multi-Fidelity Zeroth-Order Optimization
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913541090443264 |
|---|---|
| author | de Montbrun, Étienne Gerchinovitz, Sébastien |
| author_facet | de Montbrun, Étienne Gerchinovitz, Sébastien |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_00978 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Certified Multi-Fidelity Zeroth-Order Optimization de Montbrun, Étienne Gerchinovitz, Sébastien Machine Learning Optimization and Control Statistics Theory 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. |
| title | Certified Multi-Fidelity Zeroth-Order Optimization |
| topic | Machine Learning Optimization and Control Statistics Theory |
| url | https://arxiv.org/abs/2308.00978 |