Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domains by Adaptive Discretization
This addresses the computational bottleneck in Bayesian optimization for researchers and practitioners, offering a scalable solution with theoretical guarantees, though it is an incremental improvement over existing adaptive discretization methods.
The paper tackles the problem of Gaussian process optimization on continuous domains, which often suffers from high computational complexity, by introducing Ada-BKB, a no-regret algorithm that reduces runtime from O(T^4) to O(T^2 d_eff^2) and demonstrates good performance in experiments on synthetic functions and hyper-parameter optimization.
Gaussian process optimization is a successful class of algorithms(e.g. GP-UCB) to optimize a black-box function through sequential evaluations. However, for functions with continuous domains, Gaussian process optimization has to rely on either a fixed discretization of the space, or the solution of a non-convex optimization subproblem at each evaluation. The first approach can negatively affect performance, while the second approach requires a heavy computational burden. A third option, only recently theoretically studied, is to adaptively discretize the function domain. Even though this approach avoids the extra non-convex optimization costs, the overall computational complexity is still prohibitive. An algorithm such as GP-UCB has a runtime of $O(T^4)$, where $T$ is the number of iterations. In this paper, we introduce Ada-BKB (Adaptive Budgeted Kernelized Bandit), a no-regret Gaussian process optimization algorithm for functions on continuous domains, that provably runs in $O(T^2 d_\text{eff}^2)$, where $d_\text{eff}$ is the effective dimension of the explored space, and which is typically much smaller than $T$. We corroborate our theoretical findings with experiments on synthetic non-convex functions and on the real-world problem of hyper-parameter optimization, confirming the good practical performances of the proposed approach.