改进了高斯过程上置信界算法的后悔值理论边界。
Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization
- 通过分析输入序列的集中性，精细化了信息增益的计算方法。
- 在Matérn核下实现约√T的累积后悔，平方指数核下为√(T ln²T)。
- 对贝叶斯优化中的经典算法提供了更紧致的理论保障，适合理论研究者。
本文研究贝叶斯优化问题（也称高斯过程老虎机问题），即学习者在从已知高斯过程（GP）中采样的函数上最小化累积后悔。针对具有特定光滑度的Matérn核，我们证明了高斯过程上置信界（GP-UCB）算法以高概率实现$ ilde{O}( ext{√}T)$的累积后悔。此外，在平方指数核下，我们的分析得到$O( ext{√}(T ext{ln}^2 T))$的后悔界。这些结果填补了现有GP-UCB后悔上界与Scarlett（2018）给出的最佳已知界限之间的差距。证明的关键思想是捕捉由GP-UCB生成的输入序列的集中行为，从而实现对高斯过程信息增益的更精细分析。
原文摘要 · Abstract (English)
This paper addresses the Bayesian optimization problem (also referred to as the Bayesian setting of the Gaussian process bandit), where the learner seeks to minimize the regret under a function drawn from a known Gaussian process (GP). Under a Matérn kernel with a certain degree of smoothness, we show that the Gaussian process upper confidence bound (GP-UCB) algorithm achieves $\tilde{O}(\sqrt{T})$ cumulative regret with high probability. Furthermore, our analysis yields $O(\sqrt{T \ln^2 T})$ regret under a squared exponential kernel. These results fill the gap between the existing regret upper bound for GP-UCB and the best-known bound provided by Scarlett (2018). The key idea in our proof is to capture the concentration behavior of the input sequence realized by GP-UCB, enabling a more refined analysis of the GP's information gain.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。