论文标题
随着自适应批处理和重新验证，接近线性的时间高斯过程优化
Near-linear Time Gaussian Process Optimization with Adaptive Batching and Resparsification
论文作者
论文摘要
高斯流程（GP）是建模不确定性的最成功的框架之一。但是，GP优化（例如GP-UCB）遇到了主要的可扩展性问题。除非在批处理（例如，使用GP-BUCB）中选择候选物并并行评估，否则实验时间随评估的数量线性增长。此外，由于GP-BUCB之类的算法需要至少在尺寸和迭代中选择每个批次的算法，因此计算成本通常是过高的。在本文中，我们介绍了BBKB（批处理预算的内核土匪），这是第一个无需regret GP优化算法，该算法可在接近线性的时间内运行，并在批处理中选择候选人。这是通过对后差的新保证获得的，该方差使BBKB可以选择越来越大的批次，从而改善了GP-BUCB。此外，我们表明，相同的界限可用于自适应地延迟昂贵的更新，以使BBKB使用的稀疏GP近似值达到每步摊销成本的几乎恒定的成本。然后在几个实验中确认了这些发现，其中BBKB比最新方法快得多。
Gaussian processes (GP) are one of the most successful frameworks to model uncertainty. However, GP optimization (e.g., GP-UCB) suffers from major scalability issues. Experimental time grows linearly with the number of evaluations, unless candidates are selected in batches (e.g., using GP-BUCB) and evaluated in parallel. Furthermore, computational cost is often prohibitive since algorithms such as GP-BUCB require a time at least quadratic in the number of dimensions and iterations to select each batch. In this paper, we introduce BBKB (Batch Budgeted Kernel Bandits), the first no-regret GP optimization algorithm that provably runs in near-linear time and selects candidates in batches. This is obtained with a new guarantee for the tracking of the posterior variances that allows BBKB to choose increasingly larger batches, improving over GP-BUCB. Moreover, we show that the same bound can be used to adaptively delay costly updates to the sparse GP approximation used by BBKB, achieving a near-constant per-step amortized cost. These findings are then confirmed in several experiments, where BBKB is much faster than state-of-the-art methods.
