Optimal Order Simple Regret for Gaussian Process Bandits

Abstract

Consider the sequential optimization of a continuous, possibly non-convex, and expensive to evaluate objective function $f$. The problem can be cast as a Gaussian Process (GP) bandit where $f$ lives in a reproducing kernel Hilbert space (RKHS). The state of the art analysis of several learning algorithms shows a significant gap between the lower and upper bounds on the simple regret performance. When $N$ is the number of exploration trials and ${\gamma }_N$ is the maximal information gain, we prove an $\tilde{\mathcal{O}}(\sqrt{{\gamma }_N/N})$ bound on the simple regret performance of a pure exploration algorithm that is significantly tighter than the existing bounds. We show that this bound is order optimal up to logarithmic factors for the cases where a lower bound on regret is known. To establish these results, we prove novel and sharp confidence intervals for GP models applicable to RKHS elements which may be of broader interest.

References in corpus (23)

• Practical Bayesian Optimization of Machine Learning Algorithms
• 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
• Neural Contextual Bandits with UCB-based Exploration
• Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters
• Neural Thompson Sampling
• Simple regret for infinitely many armed bandits
• Multi-Armed Bandits with Local Differential Privacy
• Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
• Differential Privacy for Multi-armed Bandits: What Is It and What Is Its Cost?
• Simple Regret Minimization for Contextual Bandits
• Locally Differentially Private (Contextual) Bandits Learning
• Bandit optimisation of functions in the Matérn kernel RKHS
• Bandits with heavy tail
• Corruption-Tolerant Gaussian Process Bandit Optimization
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization
• On Information Gain and Regret Bounds in Gaussian Process Bandits
• Tight Regret Bounds for Bayesian Optimization in One Dimension
• Ordinal Bayesian Optimisation
• On Thompson Sampling with Langevin Algorithms

Cited by in corpus (3)

• Interactive Visualization Recommendation with Hier-SUCB
• Gaussian Process Bandit Optimization with Few Batches
• Uniform Generalization Bounds for Overparameterized Neural Networks