在超球域上证明了高斯过程贝叶斯优化的更紧下界，揭示算法极限。
Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere
- 基于平方指数核，在超球输入域推导出算法无关的最坏情况累积后悔下界。
- 累积后悔下界为 Ω(√(T (ln T)^d (ln ln T)^(-d)))，简单后悔需 Ω(ε⁻²(ln 1/ε)^d (ln ln 1/ε)^(-d)) 步。
- 结果表明现有最优算法仅差常数对数因子，适合关注理论边界的研究者。
我们研究了在频率论设定下，高斯过程（GP）贝叶斯优化问题的算法无关、最坏情况下的下界，其中奖励函数固定且在已知再生核希尔伯特空间（RKHS）中具有有界范数。特别关注最广泛使用的平方指数（SE）核。该问题的一个未解难题是上下界在维度相关对数因子上的差距。本文在超球输入域下部分解决了这一问题。我们证明，任何算法的累积后悔至少为 Ω(√(T (ln T)^d (ln ln T)^(-d)))，其中 T 为总步数，d 为超球域的维度。对于简单后悔，任何算法需 Ω(ε⁻²(ln 1/ε)^d (ln ln 1/ε)^(-d)) 步才能找到 ε-最优点。同时，我们给出了 SE 核最大信息增益的改进上界：O((ln T)^{d+1}(ln ln T)^{-d})。结果表明，在超球域下，现有最优算法的性能仅差维度无关的对数因子，具有理论最优性。
原文摘要 · Abstract (English)
We study an algorithm-independent, worst-case lower bound for the Gaussian process (GP) bandit problem in the frequentist setting, where the reward function is fixed and has a bounded norm in the known reproducing kernel Hilbert space (RKHS). Specifically, we focus on the squared exponential (SE) kernel, one of the most widely used kernel functions in GP bandits. One of the remaining open questions for this problem is the gap in the \emph{dimension-dependent} logarithmic factors between upper and lower bounds. This paper partially resolves this open question under a hyperspherical input domain. We show that any algorithm suffers $Ω(\sqrt{T (\ln T)^{d} (\ln \ln T)^{-d}})$ cumulative regret, where $T$ and $d$ represent the total number of steps and the dimension of the hyperspherical domain, respectively. Regarding the simple regret, we show that any algorithm requires $Ω(ε^{-2}(\ln \frac{1}ε)^d (\ln \ln \frac{1}ε)^{-d})$ time steps to find an $ε$-optimal point. We also provide the improved $O((\ln T)^{d+1}(\ln \ln T)^{-d})$ upper bound on the maximum information gain for the SE kernel. Our results guarantee the optimality of the existing best algorithm up to \emph{dimension-independent} logarithmic factors under a hyperspherical input domain.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。