# Active Learning for Level Set Estimation Using Randomized Straddle Algorithms

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 29 references that are in the map.
- First posted on arXiv 6 Aug 2024.

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

- [High Dimensional Bayesian Optimisation and Bandits via Additive Models](https://mlsanity.com/paper/1503.01673/) (2015)
- [Multi-fidelity Bayesian Optimisation with Continuous Approximations](https://mlsanity.com/paper/1703.06240/) (2017)
- [Distributionally Robust Bayesian Optimization](https://mlsanity.com/paper/2002.09038/) (2020)
- [High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groups](https://mlsanity.com/paper/1802.07028/) (2018)
- [Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration](https://mlsanity.com/paper/1304.5350/) (2013)
- [Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation](https://mlsanity.com/paper/1610.07379/) (2016)
- [Randomised Gaussian Process Upper Confidence Bound for Bayesian Optimisation](https://mlsanity.com/paper/2006.04296/) (2020)
- [Nearly Optimal Algorithms for Level Set Estimation](https://mlsanity.com/paper/2111.01768/) (2021)
- [Bayesian Optimization for Cascade-type Multi-stage Processes](https://mlsanity.com/paper/2111.08330/) (2021)
- [Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Bounds](https://mlsanity.com/paper/2302.01511/) (2023)
- [Robust Super-Level Set Estimation using Gaussian Processes](https://mlsanity.com/paper/1811.09977/) (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)
- [Delayed Feedback in Kernel Bandits](https://mlsanity.com/paper/2302.00392/) (2023)
- [Active learning for level set estimation under input uncertainty and its extensions](https://mlsanity.com/paper/1909.06064/) (2019)
- [Look-Ahead Acquisition Functions for Bernoulli Level Set Estimation](https://mlsanity.com/paper/2203.09751/) (2022)
- [Bounding Box-based Multi-objective Bayesian Optimization of Risk Measures under Input Uncertainty](https://mlsanity.com/paper/2301.11588/) (2023)
- [Adaptive Defective Area Identification in Material Surface Using Active Transfer Learning-based Level Set Estimation](https://mlsanity.com/paper/2304.01404/) (2023)

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

- [Regret Analysis for Randomized Gaussian Process Upper Confidence Bound](https://mlsanity.com/paper/2409.00979/) (2024)
- [Distributionally Robust Active Learning for Gaussian Process Regression](https://mlsanity.com/paper/2502.16870/) (2025)
- [JAREX: An Acquisition Function for Multi-Objective Algorithmic Process Characterization](https://mlsanity.com/paper/2609.24954/) (2026)

## Abstract (arXiv)

Level set estimation (LSE), the problem of identifying the set of input points where a function takes value above (or below) a given threshold, is important in practical applications. When the function is expensive-to-evaluate and black-box, the textitstraddle algorithm, which is a representative heuristic for LSE based on Gaussian process models, and its extensions having theoretical guarantees have been developed. However, many of existing methods include a confidence parameter β1/2t that must be specified by the user, and methods that choose β1/2t heuristically do not provide theoretical guarantees. In contrast, theoretically guaranteed values of β1/2t need to be increased depending on the number of iterations and candidate points, and are conservative and not good for practical performance. In this study, we propose a novel method, the textitrandomized straddle algorithm, in which βt in the straddle algorithm is replaced by a random sample from the chi-squared distribution with two degrees of freedom. The confidence parameter in the proposed method has the advantages of not needing adjustment, not depending on the number of iterations and candidate points, and not being conservative. Furthermore, we show that the proposed method has theoretical guarantees that depend on the sample complexity and the number of iterations. Finally, we confirm the usefulness of the proposed method through numerical experiments using synthetic and real data.