Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificates

François Bachoc, Tommaso R Cesari, Sébastien Gerchinovitz

We study the problem of zeroth-order (black-box) optimization of a Lipschitz function $f$ defined on a compact subset $\mathcal{X}$ of ${\mathbb{R}}^d$, with the additional constraint…