Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

The sample complexity of level set approximation

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02976018
Contributor : François Bachoc <>
Submitted on : Friday, October 23, 2020 - 10:54:19 AM
Last modification on : Wednesday, January 20, 2021 - 3:38:29 AM

Files

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02976018, version 1
  • ARXIV : 2010.13405

Citation

François Bachoc, Tommaso Cesari, Sébastien Gerchinovitz. The sample complexity of level set approximation. 2020. ⟨hal-02976018⟩

Share

Metrics

Record views

52

Files downloads

50