Provably Efficient Bayesian Optimization with Unknown Gaussian Process Hyperparameter Estimation
This addresses a critical bottleneck in Bayesian optimization for black-box function optimization, offering a provably efficient solution with theoretical guarantees, though it is incremental as it builds on existing BO and bandit techniques.
The paper tackles the problem of Bayesian optimization (BO) degrading due to incorrect Gaussian process hyperparameter estimation from biased data, proposing a method that uses EXP3 and a novel loss function to ensure consistent estimation and sub-linear convergence to the global optimum, with empirical results showing it outperforms existing approaches on synthetic and real-world problems.
Gaussian process (GP) based Bayesian optimization (BO) is a powerful method for optimizing black-box functions efficiently. The practical performance and theoretical guarantees of 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 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 objective function's global optimum 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 consistent estimation. 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.