Certified Multi-Fidelity Zeroth-Order Optimization - IRT Saint Exupéry - Institut de Recherche Technologique
Journal Articles SIAM/ASA Journal on Uncertainty Quantification Year : 2024

Certified Multi-Fidelity Zeroth-Order Optimization

Abstract

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.
Fichier principal
Vignette du fichier
main.pdf (471.82 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-04174484 , version 1 (01-08-2023)
hal-04174484 , version 2 (09-10-2024)

Licence

Identifiers

Cite

Étienne de Montbrun, Sébastien Gerchinovitz. Certified Multi-Fidelity Zeroth-Order Optimization. SIAM/ASA Journal on Uncertainty Quantification, 2024, 12 (4), pp.1135-1164. ⟨10.1137/23M1591086⟩. ⟨hal-04174484v2⟩
117 View
50 Download

Altmetric

Share

More