Exponential Regret Bounds for Gaussian Process Bandits with Deterministic Observations

Abstract

This paper analyzes the problem of Gaussian process (GP) bandits with deterministic observations. The analysis uses a branch and bound algorithm that is related to the UCB algorithm of (Srinivas et al, 2010). For GPs with Gaussian observation noise, with variance strictly greater than zero, Srinivas et al proved that the regret vanishes at the approximate rate of $O(1/\sqrt{t})$, where t is the number of observations. To complement their result, we attack the deterministic case and attain a much faster exponential convergence rate. Under some regularity assumptions, we show that the regret decreases asymptotically according to $O(e^{-\frac{\tau t}{(\ln t{)}^{d/4}}})$ with high probability. Here, d is the dimension of the search space and tau is a constant that depends on the behaviour of the objective function near its global maximum.

Appears in Proceedings of the 29th International Conference on Machine Learning (ICML 2012). arXiv admin note: substantial text overlap with arXiv:1203.2177

References in corpus (3)

• A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning
• Fast learning rates for plug-in classifiers
• Portfolio Allocation for Bayesian Optimization

Cited by in corpus (31)

• Scalable Bayesian Optimization Using Deep Neural Networks
• High Dimensional Bayesian Optimisation and Bandits via Additive Models
• Multi-fidelity Bayesian Optimisation with Continuous Approximations
• Bayesian Optimization with Exponential Convergence
• Bayesian Multi-Scale Optimistic Optimization
• Gaussian Process Optimization with Mutual Information
• Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem
• Differentially Private Bayesian Optimization
• Bayesian Optimization in a Billion Dimensions via Random Embeddings
• Bayesian optimization of hyper-parameters in reservoir computing
• Copeland Dueling Bandits
• Exploiting correlation and budget constraints in Bayesian multi-armed bandit optimization
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization
• Kernel Trajectory Maps for Multi-Modal Probabilistic Motion Prediction
• Tight Regret Bounds for Bayesian Optimization in One Dimension
• A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance
• Budgeted Batch Bayesian Optimization With Unknown Batch Sizes
• Stochastic Process Bandits: Upper Confidence Bounds Algorithms via Generic Chaining
• A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption
• Derivative-Free & Order-Robust Optimisation
• Sequential design of experiments for estimating percentiles of black-box functions
• Stochastic Lipschitz Q-Learning
• Regret Bounds for Gaussian-Process Optimization in Large Domains
• Funneled Bayesian Optimization for Design, Tuning and Control of Autonomous Systems
• On Hyper-parameter Tuning for Stochastic Optimization Algorithms
• Context-Specific Validation of Data-Driven Models
• Optimization for Gaussian Processes via Chaining
• Constrained, Global Optimization of Functions with Lipschitz Continuous Gradients
• One-parameter family of acquisition functions for efficient global optimization
• Scalable Bayesian Optimization with Sparse Gaussian Process Models
• Contraction methods for continuous optimization