MLE-Free Gaussian Process Based Bayesian Optimization

Gaussian Process based Bayesian Optimization, also known as kernelized bandits, is the standard method for sequentially optimizing black-box and expensive to evaluate functions. Its sample efficiency is the reason behind its success. However, due to the need for fitting a Gaussian Process model at each iteration, its own computational cost cubically increases with the number of function evaluations, while instability possibly arises especially in the noise-free setting. Moreover, selecting the most suitable trade-off mechanism between exploration and exploitation is not trivial, and theoretical convergence proofs for well-known acquisition functions only hold under the (impractical) assumption of knowing in advance the specific Reproducing Kernel Hilbert Space which the objective function belongs to. We propose a novel method for fitting the Gaussian Process at a constant time, independently on the number of function evaluations, while also dealing with instability and exploitation-exploration trade-off. This leads to a novel Bayesian optimization framework in which modelling of the objective function and acquisition are simultaneously addressed by fitting the Gaussian Process. Empirical results on a preliminary set of well differentiated test problems show that the proposed algorithm provides a higher effectiveness and efficiency than the most well-known no regret algorithm (i.e., GP-LCB).