aiqbench analysis
This paper advances Bayesian optimization theory by deriving tight convergence rates for Gaussian Process Thompson Sampling and introducing GP-CTS to eliminate intrinsic logarithmic penalties in regret bounds. By achieving minimax-optimal rates, the work provides a more efficient theoretical framework for optimizing expensive black-box functions within limited evaluation budgets. The research is strictly theoretical, focusing on statistical learning guarantees rather than hardware implementation or specific product deployment.
Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization
arXiv:2610.19925v1 Announce Type: cross 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\'ern 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\'ern-$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.
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.
Machine Learning (stat.ML); Machine Learning (cs.LG)
arXiv:2610.19925 [stat.ML]
(or arXiv:2610.19925v1 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2610.19925 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 271 words
Related coverage
A brief history of quantum vs classical computational advantage
Quantum Journal · Sep 1, 2026
The art and science of hyperparameter optimization on Amazon Nova Forge
AWS · Jun 2, 2026
Fully sequential Gaussian process regression for preference learning
arXiv · Oct 15, 2026
Residual Minimization Achieves Second-Order Convergence for Schrödinger Equations
Quantum Zeitgeist · Aug 19, 2026