Skip to Main content Skip to Navigation
Directions of work or proceedings

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 :
Directions of work or proceedings
Complete list of metadata
Contributor : François Bachoc <>
Submitted on : Thursday, February 11, 2021 - 12:33:48 PM
Last modification on : Wednesday, June 9, 2021 - 10:00:35 AM


Files produced by the author(s)


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


François Bachoc, Tommaso Cesari, Sébastien Gerchinovitz. The sample complexity of level set approximation. 2021, Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS 2021). ⟨hal-02976018v2⟩



Record views


Files downloads