Tight Regret Bounds for Bayesian Optimization in One Dimension

Abstract

We consider the problem of Bayesian optimization (BO) in one dimension, under a Gaussian process prior and Gaussian sampling noise. We provide a theoretical analysis showing that, under fairly mild technical assumptions on the kernel, the best possible cumulative regret up to time $T$ behaves as $\Omega (\sqrt{T})$ and $O(\sqrt{T\log T})$. This gives a tight characterization up to a $\sqrt{\log T}$ factor, and includes the first non-trivial lower bound for noisy BO. Our assumptions are satisfied, for example, by the squared exponential and Matérn-$\nu$ kernels, with the latter requiring $\nu >2$. Our results certify the near-optimality of existing bounds (Srinivas {\em et al.}, 2009) for the SE kernel, while proving them to be strictly suboptimal for the Matérn kernel with $\nu >2$.

ICML 2018 + supplementary material. This version also includes an 'Errata' section correcting two minor mistakes

References in corpus (7)

• Predictive Entropy Search for Efficient Global Optimization of Black-box Functions
• Bayesian Optimization with Exponential Convergence
• Bayesian Multi-Scale Optimistic Optimization
• Exponential Regret Bounds for Gaussian Process Bandits with Deterministic Observations
• Time-Varying Gaussian Process Bandit Optimization
• Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation
• Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization

Cited by in corpus (7)

• On Information Gain and Regret Bounds in Gaussian Process Bandits
• Combinatorial 3D Shape Generation via Sequential Assembly
• A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance
• Optimal Order Simple Regret for Gaussian Process Bandits
• Parameter Optimization using high-dimensional Bayesian Optimization
• Multiscale Gaussian Process Level Set Estimation
• LinEasyBO: Scalable Bayesian Optimization Approach for Analog Circuit Synthesis via One-Dimensional Subspaces