Sparse Spectrum Gaussian Process for Bayesian Optimization

We propose a novel sparse spectrum approximation of Gaussian process (GP) tailored for Bayesian optimization (BO). Whilst the current sparse spectrum methods provide desired approximations for regression problems, it is observed that this particular form of sparse approximations generates an overconfident GP, i.e., it produces less epistemic uncertainty than the original GP. Since the balance between the predictive mean and variance is the key determinant to the success of BO, the current methods are less suitable for BO. We derive a new regularized marginal likelihood for finding the optimal frequencies to fix this overconfidence issue, particularly for BO. The regularizer trades off the accuracy in the model fitting with targeted increase in the predictive variance of the resultant GP. Specifically, we use the entropy of the global maximum distribution (GMD) from the posterior GP as the regularizer that needs to be maximized. Since the GMD cannot be calculated analytically, we first propose a Thompson sampling based approach and then a more efficient sequential Monte Carlo based approach to estimate it. Later, we also show that the Expected Improvement acquisition function can be used as a proxy for it, thus making the process further efficient.