Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificates - IRT Saint Exupéry - Institut de Recherche Technologique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2021

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

Résumé

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 that algorithms must certify the accuracy of their recommendations. We characterize the optimal number of evaluations of any Lipschitz function $f$ to find and certify an approximate maximizer of $f$ at accuracy $\varepsilon$. Under a weak assumption on $\mathcal X$, this optimal sample complexity is shown to be nearly proportional to the integral $\int_{\mathcal X} \mathrm{d}\boldsymbol x/( \max(f) - f(\boldsymbol x) + \varepsilon )^d$. This result, which was only (and partially) known in dimension $d=1$, solves an open problem dating back to 1991. In terms of techniques, our upper bound relies on a slightly improved analysis of the DOO algorithm that we adapt to the certified setting and then link to the above integral. Our instance-dependent lower bound differs from traditional worst-case lower bounds in the Lipschitz setting and relies on a local worst-case analysis that could likely prove useful for other learning tasks.
Fichier principal
Vignette du fichier
main.pdf (356.48 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03129721 , version 1 (03-02-2021)
hal-03129721 , version 2 (09-03-2021)
hal-03129721 , version 3 (09-06-2021)
hal-03129721 , version 4 (21-03-2023)

Identifiants

Citer

François Bachoc, Tommaso R Cesari, Sébastien Gerchinovitz. Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificates. 2021. ⟨hal-03129721v3⟩
301 Consultations
270 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More