# Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domains by Adaptive Discretization

arXiv: https://arxiv.org/abs/2106.08598 · HTML: https://mlsanity.com/paper/2106.08598/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 39 references that are in the map.
- First posted on arXiv 16 Jun 2021.

## Builds on (most cited first, 14 of 14)

- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Scalable Variational Gaussian Process Classification](https://mlsanity.com/paper/1411.2005/) (2014)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Kernel methods through the roof: handling billions of points efficiently](https://mlsanity.com/paper/2006.10350/) (2020)
- [FALKON: An Optimal Large Scale Kernel Method](https://mlsanity.com/paper/1705.10958/) (2017)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Rates of Convergence for Sparse Variational Gaussian Process Regression](https://mlsanity.com/paper/1903.03571/) (2019)
- [Improving the Expected Improvement Algorithm](https://mlsanity.com/paper/1705.10033/) (2017)
- [Gaussian Process bandits with adaptive discretization](https://mlsanity.com/paper/1712.01447/) (2017)
- [Bayesian Optimization with Exponential Convergence](https://mlsanity.com/paper/1604.01348/) (2016)
- [Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processes](https://mlsanity.com/paper/2106.01121/) (2021)
- [Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHS](https://mlsanity.com/paper/2005.04832/) (2020)
- [Near-linear Time Gaussian Process Optimization with Adaptive Batching and Resparsification](https://mlsanity.com/paper/2002.09954/) (2020)
- [Bayesian Multi-Scale Optimistic Optimization](https://mlsanity.com/paper/1402.7005/) (2014)

## Built on by (most cited first, 7 of 7)

- [Stochastic Zeroth order Descent with Structured Directions](https://mlsanity.com/paper/2206.05124/) (2022)
- [Global Optimization with Parametric Function Approximation](https://mlsanity.com/paper/2211.09100/) (2022)
- [Generalized Kernelized Bandits: A Novel Self-Normalized Bernstein-Like Dimension-Free Inequality and Regret Bounds](https://mlsanity.com/paper/2508.01681/) (2025)
- [Optimistic Optimization of Gaussian Process Samples](https://mlsanity.com/paper/2209.00895/) (2022)
- [Iterative regularization in classification via hinge loss diagonal descent](https://mlsanity.com/paper/2212.12675/) (2022)
- [Bayesian Optimization by Kernel Regression and Density-based Exploration](https://mlsanity.com/paper/2502.06178/) (2025)
- [A Structured Tour of Optimization with Finite Differences](https://mlsanity.com/paper/2505.19720/) (2025)

## Abstract (arXiv)

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(T4), 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(T2 deff2), where deff 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.