pipette
ESEspañol

Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization

Haowei Wang, Yilin Zheng

Preprint

In the authors' words

Efficient global optimization aims to identify a global optimum of an expensive black-box function within a limited evaluation budget . 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\'ern kernels with smoothness parameter in dimension , we establish a worst-case expected simple-regret upper bound of 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 for both implementations under a fixed one-dimensional Mat\'ern- 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 for both discrete and continuous implementations.

Main resultLimitation the authors admit

Appeared: Thursday, October 15. arXiv. Preprint, not yet peer-reviewed.