Certified Multi-Fidelity Zeroth-Order Optimization
Étienne de Montbrun Sébastien Gerchinovitz
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 \emph{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. We close the paper by addressing the special
case of noisy (stochastic) evaluations as a direct example.