Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization

Hung Tran-The, Sunil Gupta, Santu Rana, Svetha Venkatesh

Abstract

The expected improvement (EI) algorithm is one of the most popular strategies for optimization under uncertainty due to its simplicity and efficiency. Despite its popularity, the theoretical aspects of this algorithm have not been properly analyzed. In particular, whether in the noisy setting, the EI strategy with a standard incumbent converges is still an open question of the Gaussian process bandit optimization problem. We aim to answer this question by proposing a variant of EI with a standard incumbent defined via the GP predictive mean. We prove that our algorithm converges, and achieves a cumulative regret bound of $\mathcal O(\gamma_T\sqrt{T})$, where $\gamma_T$ is the maximum information gain between $T$ observations and the Gaussian process model. Based on this variant of EI, we further propose an algorithm called Improved GP-EI that converges faster than previous counterparts. In particular, our proposed variants of EI do not require the knowledge of the RKHS norm and the noise's sub-Gaussianity parameter as in previous works. Empirical validation in our paper demonstrates the effectiveness of our algorithms compared to several baselines.

Introduction

In Gaussian Process (GP) bandit optimization, the goal is to sequentially select points to maximize an unknown, expensive "black-box" function. The Expected Improvement (EI) acquisition function is a cornerstone of Bayesian Optimization, favored for its intuitive balance between exploration and exploitation. However, a significant theoretical gap has persisted: while EI is widely used in noisy environments, rigorous convergence proofs (regret bounds) for the standard, practical version of EI—which uses the best predictive mean as the incumbent—have been elusive.

Theoretical Framework and Regret Bounds

This work addresses this gap by analyzing a variant of GP-EI that utilizes a standard incumbent $\xi$, defined as the maximum of the GP predictive mean at previously sampled points. The primary challenge in proving regret bounds for EI in noisy settings is that the incumbent value does not necessarily improve monotonically.

The authors overcome this by leveraging the monotonicity of GP variance. As more points are sampled, the predictive variance decreases, allowing for a bound on the sum of improvements. This leads to a proven cumulative regret bound of $O(\gamma_T \sqrt{T})$, where $\gamma_T$ represents the maximum information gain.

Theoretical derivation of regret bounds for the proposed EI variants.

A key advantage of this approach is that the resulting algorithms are essentially parameter-free. Unlike UCB-based methods, they do not require prior knowledge of the RKHS norm or the noise's sub-Gaussianity parameter, making them significantly more robust for real-world deployment.

Improved-GP-EI: Scalability through Partitioning

Building on the theoretical foundation of GP-EI, the authors introduce Improved-GP-EI. This algorithm employs a partitioning strategy, dividing the search space into smaller hypercubes and fitting independent GPs on these regions.

This local approach offers two main benefits:

  1. Reduced Variance Growth: It prevents global variance from escalating too rapidly.
  2. Computational Efficiency: Instead of a single $O(T^3)$ matrix inversion, it performs multiple smaller inversions, drastically reducing the computational overhead as the number of iterations $T$ increases.

Empirical Validation

The algorithms were tested against benchmarks including synthetic functions (Hartmann, Shekel, Ackley), RKHS-sampled functions, and a real-world AutoML task (optimizing a 2-layer MLP on MNIST).

Performance comparison on the Hartmann3 (d=3) benchmark, showing log distance to optima over iterations.

In synthetic tests like Hartmann3, Improved-GP-EI consistently achieved lower regret than baselines like $\pi$-GP-UCB. Furthermore, it demonstrated a tangible speedup, averaging 1.21 minutes per iteration compared to 1.37 minutes for standard GP-EI on the Hartmann3 function. On the MNIST dataset, Improved-GP-EI reached higher prediction accuracy faster than all competing methods.

Conclusion and Future Work

This paper provides the first rigorous regret bounds for a practical version of the EI algorithm in noisy settings and introduces a scalable, high-performance variant. While the bounds are competitive, the authors note that for Matérn kernels, sublinear regret currently requires the smoothness parameter $\nu$ to be sufficiently large relative to the dimension $d$ (specifically $2\nu > d$). Future research will focus on extending these guarantees to higher-dimensional spaces and exploring parallelized versions of the partitioning strategy.

Summary updated

Abstract

The expected improvement (EI) algorithm is one of the most popular strategies for optimization under uncertainty due to its simplicity and efficiency. Despite its popularity, the theoretical aspects of this algorithm have not been properly analyzed. In particular, whether in the noisy setting, the EI strategy with a standard incumbent converges is still an open question of the Gaussian process bandit optimization problem. We aim to answer this question by proposing a variant of EI with a standard incumbent defined via the GP predictive mean. We prove that our algorithm converges, and achieves a cumulative regret bound of $\mathcal O(\gamma_T\sqrt{T})$, where $\gamma_T$ is the maximum information gain between $T$ observations and the Gaussian process model. Based on this variant of EI, we further propose an algorithm called Improved GP-EI that converges faster than previous counterparts. In particular, our proposed variants of EI do not require the knowledge of the RKHS norm and the noise's sub-Gaussianity parameter as in previous works. Empirical validation in our paper demonstrates the effectiveness of our algorithms compared to several baselines.
BibTeX
@inproceedings{tranthe2022regret,
  author = {Hung Tran-The and Sunil Gupta and Santu Rana and Svetha Venkatesh},
  title = {{Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=bP0dPCNlwR},
}
Figure