The Sample Complexities of Global Lipschitz Optimization - IRT Saint Exupéry - Institut de Recherche Technologique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2021

The Sample Complexities of Global Lipschitz Optimization

Résumé

We study the problem of black-box optimization of a Lipschitz function f defined on a compact subset X of R^d, both via algorithms that certify the accuracy of their recommendations and those that do not. We investigate their sample complexities, i.e., the number of samples needed to either reach or certify a given accuracy epsilon. We start by proving a tighter bound for the well-known DOO algorithm [Perevozchikov, 1990, Munos, 2011] that matches the best existing upper bounds for (more computationally challenging) non-certified algorithms. We then introduce and analyze a new certified version of DOO and prove a matching f-dependent lower bound (up to logarithmic terms) for all certified algorithms. Afterwards, we show that this optimal quantity is proportional to \int_X dx/(max(f) - f(x) + epsilon)^d, solving as a corollary a three-decade-old conjecture by Hansen et al. [1991]. Finally, we show how to control the sample complexity of state-of-the-art non-certified algorithms with an integral reminiscent of the Dudley-entropy integral.
Fichier principal
Vignette du fichier
main.pdf (404.73 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. The Sample Complexities of Global Lipschitz Optimization. 2021. ⟨hal-03129721v2⟩
301 Consultations
270 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More