Gaussian Process Optimization with Adaptive Sketching: Scalable and No Regret

Abstract

Gaussian processes (GP) are a well studied Bayesian approach for the optimization of black-box functions. Despite their effectiveness in simple problems, GP-based algorithms hardly scale to high-dimensional functions, as their per-iteration time and space cost is at least quadratic in the number of dimensions $d$ and iterations $t$. Given a set of $A$ alternatives to choose from, the overall runtime $O(t^{3}A)$ is prohibitive. In this paper we introduce BKB (budgeted kernelized bandit), a new approximate GP algorithm for optimization under bandit feedback that achieves near-optimal regret (and hence near-optimal convergence rate) with near-constant per-iteration complexity and remarkably no assumption on the input space or covariance of the GP. We combine a kernelized linear bandit algorithm (GP-UCB) with randomized matrix sketching based on leverage score sampling, and we prove that randomly sampling inducing points based on their posterior variance gives an accurate low-rank approximation of the GP, preserving variance estimates and confidence intervals. As a consequence, BKB does not suffer from variance starvation, an important problem faced by many previous sparse GP approximations. Moreover, we show that our procedure selects at most $\tilde{O}(d_{eff})$ points, where $d_{eff}$ is the effective dimension of the explored space, which is typically much smaller than both $d$ and $t$. This greatly reduces the dimensionality of the problem, thus leading to a $O(TA{d}_{eff}^2)$ runtime and $O(A{d}_{eff})$ space complexity.

arXiv commentAccepted at COLT 2019. Corrected typos and improved comparison with existing methods

References in corpus (10)

• Practical Bayesian Optimization of Machine Learning Algorithms
• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Finite-Time Analysis of Kernelised Contextual Bandits
• Batched Large-scale Bayesian Optimization in High-dimensional Spaces
• When Gaussian Process Meets Big Data: A Review of Scalable GPs
• Fast Randomized Kernel Methods With Statistical Guarantees
• Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
• Second-Order Kernel Online Convex Optimization with Adaptive Sketching
• Statistical and Computational Trade-Offs in Kernel K-Means
• Efficient Linear Bandits through Matrix Sketching