Tight Regret Bounds for Bayesian Optimization in One Dimension
This work addresses the theoretical understanding of regret bounds in Bayesian optimization, which is incremental as it refines existing results for specific kernels.
The paper tackles the problem of Bayesian optimization in one dimension with Gaussian process priors and noise, providing theoretical analysis that shows the best possible cumulative regret up to time T is between Ω(√T) and O(√T log T), establishing tight bounds up to a √log T factor and including the first non-trivial lower bound for noisy BO.
We consider the problem of Bayesian optimization (BO) in one dimension, under a Gaussian process prior and Gaussian sampling noise. We provide a theoretical analysis showing that, under fairly mild technical assumptions on the kernel, the best possible cumulative regret up to time $T$ behaves as $Ω(\sqrt{T})$ and $O(\sqrt{T\log T})$. This gives a tight characterization up to a $\sqrt{\log T}$ factor, and includes the first non-trivial lower bound for noisy BO. Our assumptions are satisfied, for example, by the squared exponential and Matérn-$ν$ kernels, with the latter requiring $ν> 2$. Our results certify the near-optimality of existing bounds (Srinivas {\em et al.}, 2009) for the SE kernel, while proving them to be strictly suboptimal for the Matérn kernel with $ν> 2$.