Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation
Ilija Bogunovic, Jonathan Scarlett, Andreas Krause, Volkan Cevher
Abstract
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.
BibTeX
@inproceedings{NIPS2016_ce78d1da,
author = {Bogunovic, Ilija and Scarlett, Jonathan and Krause, Andreas and Cevher, Volkan},
booktitle = {Advances in Neural Information Processing Systems},
editor = {D. Lee and M. Sugiyama and U. Luxburg and I. Guyon and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation},
url = {https://proceedings.neurips.cc/paper_files/paper/2016/file/ce78d1da254c0843eb23951ae077ff5f-Paper.pdf},
volume = {29},
year = {2016}
}