# Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2016.

## Built on by (most cited first, 30 of 40)

- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Value-at-Risk Optimization with Gaussian Processes](https://mlsanity.com/paper/2105.06126/) (2021)
- [Nearly Optimal Algorithms for Level Set Estimation](https://mlsanity.com/paper/2111.01768/) (2021)
- [Risk-averse Heteroscedastic Bayesian Optimization](https://mlsanity.com/paper/2111.03637/) (2021)
- [SnAKe: Bayesian Optimization with Pathwise Exploration](https://mlsanity.com/paper/2202.00060/) (2022)
- [Lenient Regret and Good-Action Identification in Gaussian Process Bandits](https://mlsanity.com/paper/2102.05793/) (2021)
- [Entropy-based adaptive design for contour finding and estimating reliability](https://mlsanity.com/paper/2105.11357/) (2021)
- [Graph Neural Network Bandits](https://mlsanity.com/paper/2207.06456/) (2022)
- [Active Fine-Tuning of Multi-Task Policies](https://mlsanity.com/paper/2410.05026/) (2024)
- [Learning Regions of Interest for Bayesian Optimization with Adaptive Level-Set Estimation](https://mlsanity.com/paper/2307.13371/) (2023)
- [Movement Penalized Bayesian Optimization with Application to Wind Energy Systems](https://mlsanity.com/paper/2210.08087/) (2022)
- [Transition Constrained Bayesian Optimization via Markov Decision Processes](https://mlsanity.com/paper/2402.08406/) (2024)
- [Look-Ahead Acquisition Functions for Bernoulli Level Set Estimation](https://mlsanity.com/paper/2203.09751/) (2022)
- [Variational Search Distributions](https://mlsanity.com/paper/2409.06142/) (2024)
- [Accelerating Look-ahead in Bayesian Optimization: Multilevel Monte Carlo is All you Need](https://mlsanity.com/paper/2402.02111/) (2024)
- [Regret Analysis for Randomized Gaussian Process Upper Confidence Bound](https://mlsanity.com/paper/2409.00979/) (2024)
- [Sample-efficient Bayesian Optimisation Using Known Invariances](https://mlsanity.com/paper/2410.16972/) (2024)
- [Active Level Set Estimation for Continuous Search Space with Theoretical Guarantee](https://mlsanity.com/paper/2402.16237/) (2024)
- [Active Learning for Level Set Estimation Using Randomized Straddle Algorithms](https://mlsanity.com/paper/2408.03144/) (2024)
- [Distributionally Robust Active Learning for Gaussian Process Regression](https://mlsanity.com/paper/2502.16870/) (2025)
- [Relaxed Gaussian process interpolation: a goal-oriented approach to Bayesian optimization](https://mlsanity.com/paper/2206.03034/) (2022)
- [Provably Efficient Bayesian Optimization with Unknown Gaussian Process Hyperparameter Estimation](https://mlsanity.com/paper/2306.06844/) (2023)
- [Constrained Bayesian Optimization with Adaptive Active Learning of Unknown Constraints](https://mlsanity.com/paper/2310.08751/) (2023)
- [Practical Path-based Bayesian Optimization](https://mlsanity.com/paper/2312.00622/) (2023)
- [Active Few-Shot Fine-Tuning](https://mlsanity.com/paper/2402.15441/) (2024)
- [Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback](https://mlsanity.com/paper/2205.07217/) (2022)
- [Benefits of Monotonicity in Safe Exploration with Gaussian Processes](https://mlsanity.com/paper/2211.01561/) (2022)
- [Efficient Determination of Safety Requirements for Perception Systems](https://mlsanity.com/paper/2307.01371/) (2023)
- [Robust Transfer Learning for Active Level Set Estimation with Locally Adaptive Gaussian Process Prior](https://mlsanity.com/paper/2410.05660/) (2024)

## Abstract (arXiv)

We present a new algorithm, truncated variance reduction (TruVaR), that treats Bayesian optimization (BO) and level-set estimation (LSE) with Gaussian processes in a unified fashion. The algorithm greedily shrinks a sum of truncated variances within a set of potential maximizers (BO) or unclassified points (LSE), which is updated based on confidence bounds. TruVaR is effective in several important settings that are typically non-trivial to incorporate into myopic algorithms, including pointwise costs and heteroscedastic noise. We provide a general theoretical guarantee for TruVaR covering these aspects, and use it to recover and strengthen existing results on BO and LSE. Moreover, we provide a new result for a setting where one can select from a number of noise levels having associated costs. We demonstrate the effectiveness of the algorithm on both synthetic and real-world data sets.