The sample complexity of level set approximation
This work addresses a fundamental problem in function approximation and optimization, with potential applications in fields like machine learning and scientific computing, though it appears incremental as it builds on existing methods for sample complexity analysis.
The paper tackles the problem of approximating the level set of an unknown function by sequentially querying its values, introducing algorithms that achieve rate-optimal sample complexity guarantees for Hölder functions, with improvements under additional smoothness or structural assumptions.
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.