# An (ε,δ)-accurate level set estimation with a stopping criterion

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 51 references that are in the map.
- First posted on arXiv 26 Mar 2025.

## Builds on (most cited first, 24 of 24)

- [Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation](https://mlsanity.com/paper/1610.07379/) (2016)
- [A Method for Stopping Active Learning Based on Stabilizing Predictions and the Need for User-Adjustable Stopping](https://mlsanity.com/paper/1409.5165/) (2014)
- [Automatic Termination for Hyperparameter Optimization](https://mlsanity.com/paper/2104.08166/) (2021)
- [A supermartingale approach to Gaussian process based sequential design of experiments](https://mlsanity.com/paper/1608.01118/) (2016)
- [Stopping criterion for active learning based on deterministic generalization bounds](https://mlsanity.com/paper/2005.07402/) (2020)
- [Nearly Optimal Algorithms for Level Set Estimation](https://mlsanity.com/paper/2111.01768/) (2021)
- [Robust Super-Level Set Estimation using Gaussian Processes](https://mlsanity.com/paper/1811.09977/) (2018)
- [An Information-Theoretic Framework for Unifying Active Learning Problems](https://mlsanity.com/paper/2012.10695/) (2020)
- [Stopping Bayesian Optimization with Probabilistic Regret Bounds](https://mlsanity.com/paper/2402.16811/) (2024)
- [Adaptive Design of Experiments for Conservative Estimation of Excursion Sets](https://mlsanity.com/paper/1611.07256/) (2016)
- [Contour location via entropy reduction leveraging multiple information sources](https://mlsanity.com/paper/1805.07489/) (2018)
- [Evaluating Gaussian Process Metamodels and Sequential Designs for Noisy Level Set Estimation](https://mlsanity.com/paper/1807.06712/) (2018)
- [Multiscale Gaussian Process Level Set Estimation](https://mlsanity.com/paper/1902.09682/) (2019)
- [Bayesian Experimental Design for Finding Reliable Level Set under Input Uncertainty](https://mlsanity.com/paper/1910.12043/) (2019)
- [Active learning for distributionally robust level-set estimation](https://mlsanity.com/paper/2102.04000/) (2021)
- [Entropy-based adaptive design for contour finding and estimating reliability](https://mlsanity.com/paper/2105.11357/) (2021)
- [Stopping Active Learning based on Predicted Change of F Measure for Text Classification](https://mlsanity.com/paper/1901.09118/) (2019)
- [Active learning for level set estimation under input uncertainty and its extensions](https://mlsanity.com/paper/1909.06064/) (2019)
- [The sample complexity of level set approximation](https://mlsanity.com/paper/2010.13405/) (2020)
- [Look-Ahead Acquisition Functions for Bernoulli Level Set Estimation](https://mlsanity.com/paper/2203.09751/) (2022)
- [Quantifying uncertainties on excursion sets under a Gaussian random field prior](https://mlsanity.com/paper/1501.03659/) (2015)
- [Analysis of Stopping Active Learning based on Stabilizing Predictions](https://mlsanity.com/paper/1504.06329/) (2015)
- [Adaptive Defective Area Identification in Material Surface Using Active Transfer Learning-based Level Set Estimation](https://mlsanity.com/paper/2304.01404/) (2023)
- [Bayesian sequential design of computer experiments for quantile set inversion](https://mlsanity.com/paper/2211.01008/) (2022)

## Abstract (arXiv)

The level set estimation problem seeks to identify regions within a set of candidate points where an unknown and costly to evaluate function's value exceeds a specified threshold, providing an efficient alternative to exhaustive evaluations of function values. Traditional methods often use sequential optimization strategies to find ε-accurate solutions, which permit a margin around the threshold contour but frequently lack effective stopping criteria, leading to excessive exploration and inefficiencies. This paper introduces an acquisition strategy for level set estimation that incorporates a stopping criterion, ensuring the algorithm halts when further exploration is unlikely to yield improvements, thereby reducing unnecessary function evaluations. We theoretically prove that our method satisfies ε-accuracy with a confidence level of 1 - δ, addressing a key gap in existing approaches. Furthermore, we show that this also leads to guarantees on the lower bounds of performance metrics such as F-score. Numerical experiments demonstrate that the proposed acquisition function achieves comparable precision to existing methods while confirming that the stopping criterion effectively terminates the algorithm once adequate exploration is completed.