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

  1. Sergey Levine
  2. Yoshua Bengio
  3. Quoc V. Le
  4. Pieter Abbeel
  5. Frank Hutter
  6. Mohit Bansal
  7. Ruslan Salakhutdinov
  8. Percy Liang

In Computational Theory and Mathematics

  1. Frank Hutter
  2. Nando de Freitas
  3. Aaron Klein
  4. Stefan Falkner
  5. Ziyun Wang
  6. Barnab'as P'oczos
  7. Kirthevasan Kandasamy
  8. Peter I. Frazier

In Management Science and Operations Research

  1. Frank Hutter
  2. Aaron Klein
  3. Nando de Freitas
  4. Stefan Falkner
  5. Ziyun Wang
  6. Ameet Talwalkar
  7. Sergey Levine
  8. Benjamin Van Roy

In Probabilistic & Bayesian Methods

  1. Frank Hutter
  2. Aaron Klein
  3. Stefan Falkner
  4. Yoshua Bengio
  5. Barnab'as P'oczos
  6. Jeff Schneider
  7. Willie Neiswanger
  8. Sergey Levine

In Information Theory

  1. Nando de Freitas
  2. Francis R. Bach
  3. Daniel Russo
  4. Aaron Klein
  5. Benjamin Van Roy
  6. Adam D. Bull
  7. Kirthevasan Kandasamy
  8. Kevin Kaichuang Yang

Citations in the corpus