Bayesian Optimistic Optimisation with Exponentially Decaying Regret

2021/05/10 by Tran-The, Hung, Gupta, Sunil, Rana, Santu +1 · 1 citation
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2105.04332

Abstract

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 O((logN)/(√(N))) to \mathcal O(e^-√(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^-√(N)) under the assumption that the objective function is sampled from a Gaussian process with a Matérn kernel with smoothness parameter ν> 4 +(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.

Cited by

• BioBO: Biology-informed Bayesian Optimization for Perturbation Design

Related

• Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal
• Tight Regret Bounds for Bayesian Optimization in One Dimension
• Sub-linear Regret Bounds for Bayesian Optimisation in Unknown Search Spaces
• On the Suboptimality of GP-UCB under Polynomial Effective Optimism
• Direct Regret Optimization in Bayesian Optimization