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 (27)
- Adam: A Method for Stochastic Optimization
- Practical Bayesian Optimization of Machine Learning Algorithms
- Thompson Sampling for Contextual Bandits with Linear Payoffs
- Scalable Bayesian Optimization Using Deep Neural Networks
- Gaussian Processes for Big Data
- Predictive Entropy Search for Efficient Global Optimization of Black-box Functions
- Batch Bayesian Optimization via Local Penalization
- Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences
- Scalable Global Optimization via Local Bayesian Optimization
- The Parallel Knowledge Gradient Method for Batch Bayesian Optimization
- Replication or exploration? Sequential design for stochastic simulation experiments
- Batched Large-scale Bayesian Optimization in High-dimensional Spaces
- Random Feature Expansions for Deep Gaussian Processes
- Variational Fourier features for Gaussian processes
- Bayesian Optimization of Combinatorial Structures
- Constrained Bayesian Optimization for Automatic Chemical Design
- Revisiting Bayesian Optimization in the light of the COCO benchmark
- A Flexible Framework for Multi-Objective Bayesian Optimization using Random Scalarizations
- Practical Hilbert space approximate Bayesian Gaussian processes for probabilistic programming
- Matérn Gaussian processes on Riemannian manifolds
- Gaussian Process Molecule Property Prediction with FlowMO
- 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
- Sparse Spectrum Gaussian Process for Bayesian Optimization