Bayesian Optimistic Optimisation with Exponentially Decaying Regret
This work addresses the challenge of efficient global optimization for practitioners in fields like machine learning, offering a novel algorithm with improved theoretical guarantees, though it is incremental as it builds on existing Bayesian and optimistic optimization methods.
The paper tackled the problem of improving regret bounds in Bayesian optimization for expensive black-box functions, proposing the BOO algorithm which achieved an exponential regret bound of O(N^{-sqrt(N)}) under specific assumptions and outperformed baselines in experiments on synthetic functions and hyperparameter tuning tasks.
Bayesian optimisation (BO) is a well-known efficient algorithm for finding the global optimum of expensive, black-box functions. The current practical BO algorithms have regret bounds ranging from $\mathcal{O}(\frac{logN}{\sqrt{N}})$ to $\mathcal O(e^{-\sqrt{N}})$, where $N$ is the number of evaluations. This paper explores the possibility of improving the regret bound in the noiseless setting by intertwining concepts from BO and tree-based optimistic optimisation which are based on partitioning the search space. We propose the BOO algorithm, a first practical approach which can achieve an exponential regret bound with order $\mathcal O(N^{-\sqrt{N}})$ under the assumption that the objective function is sampled from a Gaussian process with a Matérn kernel with smoothness parameter $ν> 4 +\frac{D}{2}$, where $D$ is the number of dimensions. We perform experiments on optimisation of various synthetic functions and machine learning hyperparameter tuning tasks and show that our algorithm outperforms baselines.