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 的现有结果。此外，我们为选取具有相关成本的噪声级别的局面提供了新的结果。我们在合成和真实数据集上展示了该算法的有效性。