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