A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance
A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance
复制标题
DOI：
--
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Sudeep Salgia;Sattar Vakili;Qing Zhao
中科院分区：
文献类型：
--
作者：
Sudeep Salgia;Sattar Vakili;Qing Zhao
考虑再生核Hilbert空间中未知函数的序列优化问题。我们提出了一个高斯过程为基础的算法，并建立其顺序最优的遗憾性能（到一个多对数因子）。这是第一个基于GP的算法，具有顺序最优后悔保证。该算法是植根于域收缩的方法，通过一系列的基于树的区域修剪和细化集中查询越来越小的高性能区域的功能域实现。通过对最优函数值的迭代估计来局部化和引导对高性能区域的搜索，以确保学习效率和计算效率。与目前流行的GP-UCB算法族相比，该算法的计算复杂度降低了$O（T^{2d-1}）$（其中$T$是时域，$d$是函数域的维数）.
We consider sequential optimization of an unknown function in a reproducing kernel Hilbert space. We propose a Gaussian process-based algorithm and establish its order-optimal regret performance (up to a poly-logarithmic factor). This is the first GP-based algorithm with an order-optimal regret guarantee. The proposed algorithm is rooted in the methodology of domain shrinking realized through a sequence of tree-based region pruning and refining to concentrate queries in increasingly smaller high-performing regions of the function domain. The search for high-performing regions is localized and guided by an iterative estimation of the optimal function value to ensure both learning efficiency and computational efficiency. Compared with the prevailing GP-UCB family of algorithms, the proposed algorithm reduces computational complexity by a factor of $O(T^{2d-1})$ (where $T$ is the time horizon and $d$ the dimension of the function domain).