The sample complexity of level set approximation - IRT Saint Exupéry - Institut de Recherche Technologique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2020

The sample complexity of level set approximation

Résumé

We study the problem of approximating the level set of an unknown function by sequentially querying its values. We introduce a family of algorithms called Bisect and Approximate through which we reduce the level set approximation problem to a local function approximation problem. We then show how this approach leads to rate-optimal sample complexity guarantees for Hölder functions, and we investigate how such rates improve when additional smoothness or other structural assumptions hold true.
Fichier principal
Vignette du fichier
main.pdf (427.28 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02976018 , version 1 (23-10-2020)
hal-02976018 , version 2 (11-02-2021)

Identifiants

Citer

François Bachoc, Tommaso R Cesari, Sébastien Gerchinovitz. The sample complexity of level set approximation. 2020. ⟨hal-02976018v1⟩
236 Consultations
230 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More