Gaussian Process Optimization with Adaptive Sketching: Scalable and No Regret
[edit]
Proceedings of the ThirtySecond Conference on Learning Theory, PMLR 99:533557, 2019.
Abstract
Gaussian processes (GP) are a stochastic processes, used as Bayesian approach for the optimization of blackbox functions. Despite their effectiveness in simple problems, GPbased algorithms hardly scale to highdimensional functions, as their periteration time and space cost is at least \emph{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 (\textit{budgeted kernelized bandit}), a new approximate GP algorithm for optimization under bandit feedback that achieves nearoptimal regret (and hence nearoptimal convergence rate) with nearconstant periteration complexity and remarkably no assumption on the input space or covariance of the GP. We combine a kernelized linear bandit algorithm (GPUCB) leverage score sampling as a randomized matrix sketching and prove that selecting inducing points based on their posterior variance gives an accurate lowrank approximation of the GP, preserving variance estimates and confidence intervals. As a consequence, BKB does not suffer from \emph{variance starvation}, an important problem faced by many previous sparse GP approximations. Moreover, we show that our procedure selects at most $\widetilde{O}(d_{eff})$ points, where $d_{eff}$ is the \emph{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(T A d_{eff}^2)$ runtime and $O(A d_{eff})$ space complexity.
Related Material


