# The sample complexity of level set approximation

arXiv: https://arxiv.org/abs/2010.13405 · HTML: https://mlsanity.com/paper/2010.13405/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Oct 2020.

## Built on by (most cited first, 6 of 6)

- [Rashomon Capacity: A Metric for Predictive Multiplicity in Classification](https://mlsanity.com/paper/2206.01295/) (2022)
- [Constrained Bayesian Optimization Under Partial Observations: Balanced Improvements and Provable Convergence](https://mlsanity.com/paper/2312.03212/) (2023)
- [Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation](https://mlsanity.com/paper/2506.03062/) (2025)
- [An Application of Online Learning to Spacecraft Memory Dump Optimization](https://mlsanity.com/paper/2202.06617/) (2022)
- [An (ε,δ)-accurate level set estimation with a stopping criterion](https://mlsanity.com/paper/2503.20272/) (2025)
- [Maximally Robust Satisficing Bayesian Optimization](https://mlsanity.com/paper/2607.13652/) (2026)

## Abstract (arXiv)

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"older functions, and we investigate how such rates improve when additional smoothness or other structural assumptions hold true.