Provably Efficient Bayesian Optimization with Unbiased Gaussian Process
  Hyperparameter Estimation
Huong Ha Vu Nguyen Hongyu Zhang Anton van den Hengel
Gaussian process (GP) based Bayesian optimization (BO) is a powerful method
for optimizing black-box functions efficiently. The practical performance and
theoretical guarantees associated with this approach depend on having the
correct GP hyperparameter values, which are usually unknown in advance and need
to be estimated from the observed data. However, in practice, these estimations
could be incorrect due to biased data sampling strategies commonly used in BO.
This can lead to degraded performance and break the sub-linear global
convergence guarantee of BO. To address this issue, we propose a new BO method
that can sub-linearly converge to the global optimum of the objective function
even when the true GP hyperparameters are unknown in advance and need to be
estimated from the observed data. Our method uses a multi-armed bandit
technique (EXP3) to add random data points to the BO process, and employs a
novel training loss function for the GP hyperparameter estimation process that
ensures unbiased estimation from the observed data. We further provide
theoretical analysis of our proposed method. Finally, we demonstrate
empirically that our method outperforms existing approaches on various
synthetic and real-world problems.