首次证明加噪声的高效全局优化算法无遗憾，理论更可靠。
Practical Efficient Global Optimization is No-regret
- 用带小扰动的高斯过程模型改进数值稳定性
- 证明该方法在常见核函数下累积后悔呈次线性增长
- 为实际应用中噪声参数选择提供理论依据
高效全局优化（EGO）是广泛使用的无噪声贝叶斯优化算法，结合高斯过程（GP）代理模型与期望改进（EI）采集函数。实际应用中，常在确定性GP的协方差矩阵中加入一个小的正标量（称为噪声或抖动），以提升数值稳定性，此即实用型EGO。尽管广泛应用且效果良好，至今尚未建立实用EGO的累积后悔上界。本文首次给出了实用EGO的累积后悔上界，证明其在常用核函数（如平方指数核和ν>1/2的Matérn核）下具有次线性累积后悔，因此属于无遗憾算法。此外，我们分析了噪声对后悔上界的影响，并讨论其对噪声参数选择的理论启示。数值实验验证了我们的理论发现。
原文摘要 · Abstract (English)
Efficient global optimization (EGO) is one of the most widely used noise-free Bayesian optimization algorithms.It comprises the Gaussian process (GP) surrogate model and expected improvement (EI) acquisition function. In practice, when EGO is applied, a scalar matrix of a small positive value (also called a nugget or jitter) is usually added to the covariance matrix of the deterministic GP to improve numerical stability. We refer to this EGO with a positive nugget as the practical EGO. Despite its wide adoption and empirical success, to date, cumulative regret bounds for practical EGO have yet to be established. In this paper, we present for the first time the cumulative regret upper bound of practical EGO. In particular, we show that practical EGO has sublinear cumulative regret bounds and thus is a no-regret algorithm for commonly used kernels including the squared exponential (SE) and Matérn kernels ($ν>\frac{1}{2}$). Moreover, we analyze the effect of the nugget on the regret bound and discuss the theoretical implication on its choice. Numerical experiments are conducted to support and validate our findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。