首次证明期望改进算法在噪声环境下无遗憾，给出最优候选选择方案。
Bayesian Optimization with Expected Improvement: No Regret and the Choice of Incumbent
- 分析三种常用候选值的期望改进算法，理论推导其累积后悔上界。
- 证明在平方指数与马特恩核下，使用后验均值或采样后验均值作为候选时无遗憾。
- 实验验证理论结果，为实际应用中候选值选择提供依据。
期望改进（EI）是贝叶斯优化中最广泛使用的获取函数之一。尽管其在实际应用中表现优异，但关于其累积后悔上界的理论分析仍属开放问题。本文研究经典的噪声高斯过程期望改进（GP-EI）算法，在目标函数为高斯过程样本的贝叶斯设定下，考虑三种常用的候选值：后验均值最佳候选（BPMI）、采样后验均值最佳候选（BSPMI）和观测值最佳候选（BOI）。首次给出了使用BPMI和BSPMI时的累积后悔上界，并证明在平方指数（SE）和马特恩（Matérn）核下，这两种情形的GP-EI均为无遗憾算法。此外，首次证明使用BOI时，对于SE和马特恩核，要么获得次线性累积后悔上界，要么具有快速收敛的噪声简单后悔上界。这些结果为噪声环境下应用GP-EI时的候选值选择提供了理论指导。通过数值实验验证了理论结论。
原文摘要 · Abstract (English)
Expected improvement (EI) is one of the most widely used acquisition functions in Bayesian optimization (BO). Despite its proven empirical success in applications, the cumulative regret upper bound of EI remains an open question. In this paper, we analyze the classic noisy Gaussian process expected improvement (GP-EI) algorithm. We consider the Bayesian setting, where the objective is a sample from a GP. Three commonly used incumbents, namely the best posterior mean incumbent (BPMI), the best sampled posterior mean incumbent (BSPMI), and the best observation incumbent (BOI) are considered as the choices of the current best value in GP-EI. We present for the first time the cumulative regret upper bounds of GP-EI with BPMI and BSPMI. Importantly, we show that in both cases, GP-EI is a no-regret algorithm for both squared exponential (SE) and Matérn kernels. Further, we present for the first time that GP-EI with BOI either achieves a sublinear cumulative regret upper bound or has a fast converging noisy simple regret bound for SE and Matérn kernels. Our results provide theoretical guidance to the choice of incumbent when practitioners apply GP-EI in the noisy setting. Numerical experiments are conducted to validate our findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。