The sample complexity of level set approximation

2020/10/26 by Bachoc, François, Cesari, Tommaso, Gerchinovitz, Sébastien · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2010.13405

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.

Cited by

• Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation

Related

• Nearly Optimal Algorithms for Level Set Estimation
• A Survey on Approximation in Parameterized Complexity: Hardness and\n Algorithms
• Adaptive approximation of monotone functions
• An Adaptive Sampling Algorithm for Level-set Approximation
• Levelable Sets and the Algebraic Structure of Parameterizations