Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization

Jonathan Scarlett, Ilija Bogunovic, Volkan CevherOpenReview 2021 · OpenReview

TL;DR

This paper establishes fundamental limits on how efficiently we can optimize a noisy black-box function using Gaussian Processes (GPs). The authors derive algorithm-independent lower bounds for both instantaneous and cumulative regret, showing that for common GP kernels, these bounds closely match existing upper bounds, suggesting that current algorithms are near-optimal.

What Problem Does This Paper Address?

Optimizing black-box functions, especially when evaluations are noisy and expensive, is a critical problem in many fields like robotics and hyperparameter tuning. Gaussian Processes (GPs) are a popular tool for this, offering a probabilistic model of the unknown function. However, most existing work focuses on upper bounds on regret (how well algorithms perform). This paper tackles the crucial question of lower bounds: what is the absolute best performance any algorithm can achieve, regardless of its specific design? Specifically, they investigate the non-Bayesian setting where the function is assumed to have a bounded norm in a Reproducing Kernel Hilbert Space (RKHS), and the observations are corrupted by additive Gaussian noise. The authors aim to understand how much information can be extracted from noisy samples and what are the inherent limitations imposed by the function's smoothness (defined by the GP kernel) and the noise level.

Methods

The core of the paper's methodology lies in constructing a specific class of "needle-in-a-haystack" functions. These functions are designed to be maximally difficult for any optimization algorithm to distinguish, forcing it to make many queries to pinpoint the optimum. By analyzing the regret incurred on this challenging function class, the authors derive lower bounds.

Key techniques include:

  • RKHS Norm Bounds: Leveraging properties of RKHS norms to bound the complexity of the constructed functions.
  • Fourier Transforms: Using Fourier analysis to characterize the kernels and the constructed functions, particularly for the squared exponential and Matérn kernels.
  • Information Theory: Implicitly using concepts related to information gain and divergence to bound the distinguishability of functions.
  • Finite Ensemble Construction: Creating a finite set of functions where each function's optimum is well-separated, making it hard for an algorithm to identify the true optimum without significant exploration.
  • Regret Analysis: Deriving bounds for both simple (instantaneous) regret and cumulative regret, considering the impact of noise.

Datasets

Not discussed in the paper. The paper focuses on theoretical lower bounds and uses synthetic function classes for analysis rather than real-world datasets.

Key Insights and Ideas

  • Fundamental Limits Exist: The paper demonstrates that there are inherent limitations to how quickly we can find the optimum of a noisy black-box function, even with powerful tools like GPs.
  • Near-Optimality of Current Methods: For the widely-used squared exponential kernel, the derived lower bounds closely match existing upper bounds. This suggests that algorithms like GP-UCB are already performing close to the theoretical best possible.
  • Matérn Kernel Gap: The gap between lower and upper bounds is more significant for the Matérn kernel. This indicates that current algorithms might be suboptimal for this class of functions, or that the existing upper bounds are loose.
  • Noise Impact: The analysis explicitly incorporates noisy observations, showing how noise fundamentally affects the achievable regret bounds.
  • Kernel Dictates Difficulty: The smoothness properties of the kernel (e.g., the Matérn parameter $\nu$) directly influence the difficulty of the optimization problem and the resulting regret bounds.

Key Results

The paper provides algorithm-independent lower bounds on regret for noisy Gaussian Process bandit optimization.

  • Squared Exponential Kernel:
    • Simple Regret: Requires $T = \Omega\left(\frac{1}{\epsilon^2} (\log \frac{1}{\epsilon})^{d/2}\right)$ evaluations to achieve an average simple regret of $\epsilon$.
  • Cumulative Regret: The average cumulative regret is $\Omega\left(\sqrt{T (\log T)^d}\right)$. These bounds are shown to closely match existing upper bounds.

  • Matérn Kernel:

    • Simple Regret: Bounds are of the form $\Omega\left( (\frac{1}{\epsilon})^{2+d/\nu}\right)$.
  • Cumulative Regret: Bounds are of the form $\Omega\left( T^{\frac{\nu + d}{2\nu + d}}\right)$. For the Matérn kernel, the gaps between these lower bounds and existing upper bounds are more pronounced.

Limitations and Future Work

  • Non-Bayesian Setting: The results are derived for the non-Bayesian setting. The authors note that the "needle-in-a-haystack" functions are unlikely to be observed in the Bayesian setting, suggesting that milder scaling laws might be achievable there.
  • Matérn Kernel Gap: The significant gap for the Matérn kernel suggests that further research is needed to either improve existing algorithms or refine the lower bounds for this kernel.
  • Conjecture on $\gamma_T$: The paper conjectures that existing upper bounds for the Matérn kernel might be loose and could be improved by closing the gap related to the term $\gamma_T$.
  • Bayesian Setting: The authors explicitly suggest exploring lower bounds for the Bayesian setting as a future research direction.
  • Unknown Kernels: While the paper's lower bounds hold regardless of kernel knowledge, future work could investigate lower bounds for scenarios where the kernel itself is unknown.

Summary updated

Abstract

In this paper, we consider the problem of sequentially optimizing a black-box function $f$ based on noisy samples and bandit feedback. We assume that $f$ is smooth in the sense of having a bounded norm in some reproducing kernel Hilbert space (RKHS), a commonly-considered non-Bayesian form of Gaussian process optimization. We provide algorithm-independent lower bounds on the instantaneous regret, measuring the suboptimality of a single point reported after $T$ rounds, and on the cumulative regret, measuring the sum of regrets over all the chosen points. For the isotropic squared-exponential kernel in $d$ dimensions, we find that an average instantaneous regret of $\epsilon$ requires $T = \Omega\big(\frac{1}{\epsilon^2} (\log\frac{1}{\epsilon})^{d/2}\big)$, and the average cumulative regret is at least $\Omega\big( \sqrt{T(\log T)^d} \big)$, thus matching existing upper bounds up to the replacement of $d/2$ by $d+O(1)$ in both cases. For the Mat\'ern-$\nu$ kernel, we give analogous bounds of the form $\Omega\big( (\frac{1}{\epsilon})^{2+d/\nu}\big)$ and $\Omega\big( T^{\frac{\nu + d}{2\nu + d}} \big)$, and discuss the resulting gaps to the existing upper bounds.
BibTeX
@misc{scarlett2021lower,
  author = {Jonathan Scarlett and Ilija Bogunovic and Volkan Cevher},
  title = {{Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization}},
  year = {2021},
  url = {https://openreview.net/forum?id=VKxsWpsBbIl},
  howpublished = {OpenReview},
}
Figure