A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance

Abstract

We consider sequential optimization of an unknown function in a reproducing kernel Hilbert space. We propose a Gaussian process-based algorithm and establish its order-optimal regret performance (up to a poly-logarithmic factor). This is the first GP-based algorithm with an order-optimal regret guarantee. The proposed algorithm is rooted in the methodology of domain shrinking realized through a sequence of tree-based region pruning and refining to concentrate queries in increasingly smaller high-performing regions of the function domain. The search for high-performing regions is localized and guided by an iterative estimation of the optimal function value to ensure both learning efficiency and computational efficiency. Compared with the prevailing GP-UCB family of algorithms, the proposed algorithm reduces computational complexity by a factor of $O(T^{2d-1})$ (where $T$ is the time horizon and $d$ the dimension of the function domain).

Accepted to NeurIPS 2021

References in corpus (25)

• Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design
• Gaussian Processes for Big Data
• Max-value Entropy Search for Efficient Bayesian Optimization
• Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences
• Finite-Time Analysis of Kernelised Contextual Bandits
• Bayesian Optimization with Exponential Convergence
• Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization
• Bayesian Multi-Scale Optimistic Optimization
• Hybrid Batch Bayesian Optimization
• Adversarially Robust Optimization with Gaussian Processes
• Exponential Regret Bounds for Gaussian Process Bandits with Deterministic Observations
• Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters
• Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search
• Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
• Correlated random features for fast semi-supervised learning
• Bandit optimisation of functions in the Matérn kernel RKHS
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization
• Efficient Linear Bandits through Matrix Sketching
• On Information Gain and Regret Bounds in Gaussian Process Bandits
• Tight Regret Bounds for Bayesian Optimization in One Dimension
• High-Dimensional Experimental Design and Kernel Bandits
• Ordinal Bayesian Optimisation
• Stochastic Process Bandits: Upper Confidence Bounds Algorithms via Generic Chaining
• Scalable Thompson Sampling using Sparse Gaussian Process Models
• Stochastic Coordinate Minimization with Progressive Precision for Stochastic Convex Optimization

Cited by in corpus (1)

• Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures