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.

本文提出了一个新算法TruVaR，它统一处理了基于高斯过程的贝叶斯优化（BO）和水平集估计（LSE）。该算法通过对一组潜在优化点（BO）或未分类点（LSE）的截断方差的求和进行贪婪收缩，并根据置信度边界进行更新。TruVaR在几个重要的设置中表现出了有效性，这些设置通常难以纳入近视算法中，包括单点成本和异方差噪声。我们提供了TruVaR的一般理论保证，其中涵盖了这些方面，并用其恢复和加强了有关BO和LSE的现有结果。此外，我们为选取具有相关成本的噪声级别的局面提供了新的结果。我们在合成和真实数据集上展示了该算法的有效性。

截断方差缩减：贝叶斯优化和水平集估计的统一方法