Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation
This work addresses the problem of improving efficiency and flexibility in optimization and estimation tasks for researchers and practitioners in machine learning, though it is incremental as it builds on existing methods.
The authors introduced TruVaR, a unified algorithm for Bayesian optimization and level-set estimation that handles pointwise costs and heteroscedastic noise, achieving strong theoretical guarantees and demonstrating effectiveness on synthetic and real-world datasets.
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.