[edit]
Bayesian Optimistic Optimisation with Exponentially Decaying Regret
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:10390-10400, 2021.
Abstract
Bayesian optimisation (BO) is a well known algorithm for finding the global optimum of expensive, black-box functions. The current practical BO algorithms have regret bounds ranging from O(logN√N) to O(e−√N), where N is the number of evaluations. This paper explores the possibility of improving the regret bound in the noise-free setting by intertwining concepts from BO and optimistic optimisation methods 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 O(N−√N) under the assumption that the objective function is sampled from a Gaussian process with a Matérn kernel with smoothness parameter ν>4+D2, 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.