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.

The sample complexity of level set approximation / F. Bachoc, T. Cesari, S. Gerchinovitz (PROCEEDINGS OF MACHINE LEARNING RESEARCH). - In: International Conference on Artificial Intelligence and Statistics / [a cura di] A. Banerjee, K. Fukumizu. - [s.l] : Banerjee, Arindam and Fukumizu, Kenji, 2021. - pp. 1-10 (( convegno International Conference on Artificial Intelligence and Statistics tenutosi a Virtual event nel 2021.

The sample complexity of level set approximation

T. Cesari
Secondo
;
2021

Abstract

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.
Settore INF/01 - Informatica
2021
https://proceedings.mlr.press/v130/bachoc21a.html
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
bachoc21a.pdf

accesso riservato

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 478.77 kB
Formato Adobe PDF
478.77 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/921476
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact