arXiv：cs.LG· Haowei Wang, Yilin Zheng·· 10 小时前
高斯过程 Thompson Sampling 的高效全局优化收敛速率研究
Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization
AI 导读
针对高斯过程 Thompson Sampling（GP-TS），研究在无噪声观测与 RKHS 固定目标函数假设下，对光滑参数为 ν 的 Matérn 核在 d 维空间中给出最坏期望简单遗憾上界 O(N^{-ν/d}√log N)，并在一维 Matérn-5/2 核下证明匹配下界 Ω(N^{-5/2}√log N)，表明对数惩罚为该设定下标准 GP-TS 固有。
正文
Abstract:Efficient global optimization aims to identify a global optimum of an expensive black-box function within a limited evaluation budget $N$. We investigate the convergence rates of Gaussian process Thompson sampling (GP-TS) under noiseless observations, assuming a fixed objective function in a reproducing kernel Hilbert space (RKHS). For Matérn kernels with smoothness parameter $\nu$ in dimension $d$, we establish a worst-case expected simple-regret upper bound of $O(N^{-\nu/d}\sqrt{\log N})$ for both discrete GP-TS on sufficiently fine grids and its continuous counterpart. For the continuous implementation, we develop a nested-grid argument to control posterior sample paths over the entire domain. We further establish matching lower bounds of $\Omega(N^{-5/2}\sqrt{\log N})$ for both implementations under a fixed one-dimensional Matérn-$5/2$ kernel, demonstrating that the logarithmic penalty is intrinsic to standard GP-TS in this setting. Motivated by this limitation, we propose Gaussian Process Capped Thompson Sampling (GP-CTS), which caps posterior sample paths using a valid RKHS norm upper bound while preserving optimism. This modification successfully eliminates the logarithmic penalty and achieves the minimax-optimal rate $\Theta(N^{-\nu/d})$ for both discrete and continuous implementations.
| Subjects: | Machine Learning (stat.ML); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.19925 [stat.ML] |
| (or arXiv:2610.19925v1 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2610.19925 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Yilin Zheng [view email]
[v1]
Wed, 14 Oct 2026 10:15:09 UTC (56 KB)
来源：arXiv：cs.LG · arxiv.org