Scalable Thompson Sampling using Sparse Gaussian Process Models
arXiv:2006.05356
Abstract
Thompson Sampling (TS) from Gaussian Process (GP) models is a powerful tool for the optimization of black-box functions. Although TS enjoys strong theoretical guarantees and convincing empirical performance, it incurs a large computational overhead that scales polynomially with the optimization budget. Recently, scalable TS methods based on sparse GP models have been proposed to increase the scope of TS, enabling its application to problems that are sufficiently multi-modal, noisy or combinatorial to require more than a few hundred evaluations to be solved. However, the approximation error introduced by sparse GPs invalidates all existing regret bounds. In this work, we perform a theoretical and empirical analysis of scalable TS. We provide theoretical guarantees and show that the drastic reduction in computational complexity of scalable TS can be enjoyed without loss in the regret performance over the standard TS. These conceptual claims are validated for practical implementations of scalable TS on synthetic benchmarks and as part of a real-world high-throughput molecular design task.
References in corpus (14)
- Practical Bayesian Optimization of Machine Learning Algorithms
- Scalable Bayesian Optimization Using Deep Neural Networks
- Predictive Entropy Search for Efficient Global Optimization of Black-box Functions
- Scalable Global Optimization via Local Bayesian Optimization
- Random Feature Expansions for Deep Gaussian Processes
- Revisiting Bayesian Optimization in the light of the COCO benchmark
- Practical Hilbert space approximate Bayesian Gaussian processes for probabilistic programming
- Gaussian Process Molecule Property Prediction with FlowMO
- Matérn Gaussian processes on Riemannian manifolds
- BOSS: Bayesian Optimization over String Spaces
- Sparse Gaussian Processes with Spherical Harmonic Features
- GIBBON: General-purpose Information-Based Bayesian OptimisatioN
- GPflux: A Library for Deep Gaussian Processes
- Thompson Sampling for Contextual Bandit Problems with Auxiliary Safety Constraints