Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting
By Niranjan Srinivas, Andreas Krause, Sham M. Kakade, Matthias W. Seeger. 2009
1,787 citations recorded by the source corpus.
Many applications require optimizing an unknown, noisy function that is expensive to evaluate. We formalize this task as a multiarmed bandit problem, where the payoff function is either sampled from a Gaussian process (GP) or has low norm in a reproducing kernel Hilbert space. We resolve the important open problem of deriving regret bounds for this setting, which imply novel convergence rates for GP optimization. We analyze an intuitive Gaussian process upper confidence bound (GP-UCB) algorithm, and bound its cumulative regret in terms of maximal in- formation gain, establishing a novel connection between GP optimization and experimental design. Moreover, by bounding the latter in terms of operator spectra, we obtain explicit sublinear regret bounds for many commonly used covariance functions. In some important cases, our bounds have surprisingly weak dependence on the dimensionality. In our experiments on real sensor data, GP-UCB compares favorably with other heuristical GP optimization approaches.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Science and Operations Research, Probabilistic & Bayesian Methods, Information Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Sergey Levine
- Yoshua Bengio
- Quoc V. Le
- Pieter Abbeel
- Frank Hutter
- Mohit Bansal
- Ruslan Salakhutdinov
- Percy Liang
In Computational Theory and Mathematics
- Frank Hutter
- Nando de Freitas
- Aaron Klein
- Stefan Falkner
- Ziyun Wang
- Barnab'as P'oczos
- Kirthevasan Kandasamy
- Peter I. Frazier
In Management Science and Operations Research
- Frank Hutter
- Aaron Klein
- Nando de Freitas
- Stefan Falkner
- Ziyun Wang
- Ameet Talwalkar
- Sergey Levine
- Benjamin Van Roy
In Probabilistic & Bayesian Methods
- Frank Hutter
- Aaron Klein
- Stefan Falkner
- Yoshua Bengio
- Barnab'as P'oczos
- Jeff Schneider
- Willie Neiswanger
- Sergey Levine
In Information Theory
- Nando de Freitas
- Francis R. Bach
- Daniel Russo
- Aaron Klein
- Benjamin Van Roy
- Adam D. Bull
- Kirthevasan Kandasamy
- Kevin Kaichuang Yang
Citations in the corpus
- BANANAS: Bayesian Optimization with Neural Architectures for Neural Architecture Search (2019, methodology): “We consider four common acquisition functions that can be computed using a function value estimate and uncertainty estimate for each input datapoint: Thompson sampling (TS) (Thompson 1933), upper confidence bound (UCB) (Srinivas et al. 2009), expected improvement (EI) (Močkus 1975), and probability”
- On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions (2015, methodology): “26) shows that the approximation and optimization problems have the same worst-case guarantees (with no influence of adaptivity); this optimization problem has also been studied in the bandit setting (Srinivas et al., 2012) and in the framework of “Bayesian optimization” (see, e.g. Bull, 2011). 4. Th”
- Google Vizier: A Service for Black-Box Optimization (2017, methodology): “In Figures 6 we look at result quality for four optimization algorithms currently implemented in the Vizier framework: a multiarmed bandit technique using a Gaussian process regressor [29], the SMAC algorithm [19], the Covariance Matrix Adaption Evolution Strategy (CMA-ES) [16], and a probabilistic ”
- A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning (2010, methodology): “We refer the interested reader to the original paper [Srinivas et al., 2010].”
- Learning to Optimize via Posterior Sampling (2013, methodology): “[35] have free parameters that must be chosen by the user.”
- A Tutorial on Thompson Sampling (2017, background): “, 2008; Rusmevichientong and Tsitsiklis, 2010), bandits with continuous action spaces and smooth reward functions (Kleinberg et al., 2008; Bubeck et al., 2011; Srinivas et al., 2012), and exploration in reinforcement learning (Jaksch et al.”
- Constrained Efficient Global Optimization of Expensive Black-box Functions (2022, methodology): “The column of maximum information gain shows the results of (Srinivas et al., 2012; Vakili et al., 2021).”
- The Parallel Knowledge Gradient Method for Batch Bayesian Optimization (2016, background): “…usuallyprovides a single point to evaluate next, with common acquisition functions for sequential Bayesianoptimization including probability of improvement (PI)[23], expected improvement (EI) [12], upperconfidence bound (UCB) [20], entropy search (ES) [10], and knowledge gradient (KG) [15].”
- Cooling Strategies for the Moment-Generating Function in Bayesian Global Optimization (2018, background): “, Expected Improvement (EI) [1], [2], Probability of Improvement (PI) [4], [12] and Lower Confidence Bound [13], [14], [15].”
- On the Equivalence between Quadrature Rules and Random Features (2015, methodology): “For noiseless problems, Novak (1988, page 26) shows that the approximation and optimization problems have the same worst-case guarantees (with no influence of adaptivity); this optimization problem has also been studied in the bandit setting (Srinivas et al., 2012) and in the framework of “Bayesian ”
- High-Dimensional Gaussian Process Bandits (2013, methodology): “ducible Kernel Hilbert Space (RKHS) is GP-UCB [12].”
- Gaussian Process Optimization with Mutual Information (2013, methodology): “We refer to (Srinivas et al., 2012) for the analysis of γT with other kernels widely used in practice.”
- Exponential Regret Bounds for Gaussian Process Bandits with Deterministic Observations (2012, methodology): “The analysis uses a branch and bound algorithm that is related to the UCB algorithm of (Srinivas et al., 2010).”
- Dex-Net 1.0: A cloud-based network of 3D objects for robust grasp planning using a Multi-Armed Bandit model with correlated rewards (2016, methodology): “1) for a binary quality metric such as force closure over a discrete set of candidate grasps Γ on an object O using a Bayesian Multi-Armed Bandit (MAB) model [26], [40] with correlated rewards [16] and priors computed from Dex-Net 1.”
- Machine learning to design integral membrane channelrhodopsins for efficient eukaryotic expression and plasma membrane localization (2017, methodology): “We used the localization regression model to predict ChR chimeras with optimal localization using the Lower Confidence Bound (LCB) algorithm, in which the predicted mean minus the predicted standard deviation (LB1) is maximized [37].”