# Multiscale Gaussian Process Level Set Estimation

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

## Key facts

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

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

- [Nearly Optimal Algorithms for Level Set Estimation](https://mlsanity.com/paper/2111.01768/) (2021)
- [Lenient Regret and Good-Action Identification in Gaussian Process Bandits](https://mlsanity.com/paper/2102.05793/) (2021)
- [Part-X: A Family of Stochastic Algorithms for Search-Based Test Generation with Probabilistic Guarantees](https://mlsanity.com/paper/2110.10729/) (2021)
- [Adaptive Defective Area Identification in Material Surface Using Active Transfer Learning-based Level Set Estimation](https://mlsanity.com/paper/2304.01404/) (2023)
- [Active Learning for Level Set Estimation Using Randomized Straddle Algorithms](https://mlsanity.com/paper/2408.03144/) (2024)
- [Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spaces](https://mlsanity.com/paper/2603.08287/) (2026)
- [Robust Transfer Learning for Active Level Set Estimation with Locally Adaptive Gaussian Process Prior](https://mlsanity.com/paper/2410.05660/) (2024)
- [Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation](https://mlsanity.com/paper/2506.03062/) (2025)
- [High-dimensional Level Set Estimation with Trust Regions and Double Acquisition Functions](https://mlsanity.com/paper/2602.12391/) (2026)
- [An (ε,δ)-accurate level set estimation with a stopping criterion](https://mlsanity.com/paper/2503.20272/) (2025)

## Abstract (arXiv)

In this paper, the problem of estimating the level set of a black-box function from noisy and expensive evaluation queries is considered. A new algorithm for this problem in the Bayesian framework with a Gaussian Process (GP) prior is proposed. The proposed algorithm employs a hierarchical sequence of partitions to explore different regions of the search space at varying levels of detail depending upon their proximity to the level set boundary. It is shown that this approach results in the algorithm having a low complexity implementation whose computational cost is significantly smaller than the existing algorithms for higher dimensional search space X. Furthermore, high probability bounds on a measure of discrepancy between the estimated level set and the true level set for the the proposed algorithm are obtained, which are shown to be strictly better than the existing guarantees for a large class of GPs. In the process, a tighter characterization of the information gain of the proposed algorithm is obtained which takes into account the structured nature of the evaluation points. This approach improves upon the existing technique of bounding the information gain with maximum information gain.