为高斯过程贝叶斯优化中的汤普森采样提供更全面的后悔界分析
On Regret Bounds of Thompson Sampling for Bayesian Optimization
- 从概率和期望两方面给出汤普森采样的后悔上界
- 揭示其在失败概率δ下存在多项式依赖关系
- 适用于关注算法稳定性和理论性能的研究者
本文研究了在目标函数为高斯过程样本路径假设下的高斯过程汤普森采样（GP-TS）方法。相较于已有高概率与期望后悔界结果的GP-UCB，对GP-TS的分析多局限于期望后悔。本文填补空白，给出多个后悔界：(i) GP-TS的后悔下界，表明其在概率δ下存在关于1/δ的多项式依赖；(ii) 累积后悔二阶矩的上界，直接导出关于δ的改进后悔上界；(iii) 期望宽松后悔上界；(iv) 时间跨度T上的改进累积后悔上界。过程中还提出了若干有用引理，包括放松近期分析中获得改进上界的必要条件。
原文摘要 · Abstract (English)
We study a widely used Bayesian optimization method, Gaussian process Thompson sampling (GP-TS), under the assumption that the objective function is a sample path from a GP. Compared with the GP upper confidence bound (GP-UCB) with established high-probability and expected regret bounds, most analyses of GP-TS have been limited to expected regret. Moreover, whether the recent analyses of GP-UCB for the lenient regret and the improved cumulative regret upper bound can be applied to GP-TS remains unclear. To fill these gaps, this paper shows several regret bounds: (i) a regret lower bound for GP-TS, which implies that GP-TS suffers from a polynomial dependence on $1/δ$ with probability $δ$, (ii) an upper bound of the second moment of cumulative regret, which directly suggests an improved regret upper bound on $δ$, (iii) expected lenient regret upper bounds, and (iv) an improved cumulative regret upper bound on the time horizon $T$. Along the way, we provide several useful lemmas, including a relaxation of the necessary condition from recent analysis to obtain improved regret upper bounds on $T$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。