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 Bayesian Optimization, the goal is to find the maximum of an expensive "black-box" function. The Expected Improvement (EI) algorithm is a staple in the practitioner's toolkit because it intuitively balances exploration and exploitation. However, a persistent gap exists between its practical success and theoretical justification. Most existing proofs for EI assume a noiseless environment or rely on computationally expensive incumbents. In real-world noisy settings, the standard incumbent—the best predictive mean at previously sampled points—is notoriously difficult to analyze because it lacks monotonicity. Previous theoretical attempts to address this required prior knowledge of the function's Reproducing Kernel Hilbert Space (RKHS) norm and noise parameters, which are typically unknown.

Proposed Methodology

This work introduces two primary algorithmic contributions designed to bridge the theory-practice gap.

GP-EI with a Standard Incumbent

The authors define the incumbent $\xi$ as the maximum of the GP predictive mean at points already sampled. They prove that this version achieves a cumulative regret bound of $O(\gamma_T \sqrt{T})$, where $\gamma_T$ represents the maximum information gain. This result is significant as it provides convergence guarantees for a version of EI that practitioners actually use.

Improved GP-EI

To accelerate convergence, the authors introduce Improved GP-EI, which utilizes a partitioning strategy. The search space is divided into a "cover" of hypercubes. The algorithm fits independent GPs on each hypercube and selects the next point by maximizing EI independently across these elements. As data accumulates, hypercubes are split into smaller ones.

Convergence of function values for different GP-EI variants.

A key advantage of Improved GP-EI is its use of a time-varying scale parameter ($\omega_T$) that grows poly-logarithmically. This allows the algorithm to operate without prior knowledge of the function's RKHS norm ($B$) or the noise parameter ($R$), making it more robust and parameter-free compared to Upper Confidence Bound (UCB) strategies.

Empirical Evaluation

The algorithms were rigorously tested across synthetic benchmarks, RKHS-generated functions, and real-world hyperparameter optimization tasks.

Synthetic Benchmarks

The performance was evaluated on standard stress tests including Hartmann3 (3D), Shekel (4D), Hartmann6 (6D), and Ackley (10D). As shown in the results, Improved GP-EI consistently reaches the optima faster and more accurately than baselines like $\pi$-GP-UCB.

Performance comparison across synthetic benchmarks (Hartmann, Shekel, Ackley) measuring log distance to optima.

Real-World Application: MNIST Hyperparameter Tuning

The authors applied Improved GP-EI to optimize the learning rate and regularization parameters of a 2-layer Multi-Layer Perceptron (MLP) on the MNIST dataset. Improved GP-EI reached higher test accuracy faster than $\pi$-GP-UCB, demonstrating its practical utility in machine learning pipelines.

Key Insights

  • Handling Non-Monotonicity: The theoretical breakthrough involved using the monotonicity of variance functions to handle the non-monotonic nature of the standard incumbent in noisy settings.
  • Scalability through Partitioning: By breaking the search space into hypercubes, Improved GP-EI avoids the $O(T^3)$ computational bottleneck of standard GPs, performing matrix inversions on smaller subsets of data.
  • Robustness: EI-based strategies demonstrated greater robustness to kernel choice and "hidden" parameters than UCB-based methods, which often require careful manual tuning.

Conclusion

This paper provides the first theoretical convergence guarantees for EI in noisy GP bandit optimization using a standard incumbent. The proposed Improved GP-EI variant not only offers faster convergence but also operates without the need for prior knowledge of function smoothness or noise levels. While future work may explore different acquisition functions within the partitioning framework or refine bounds for specific kernels, this work marks a significant step forward in the theoretical understanding of Bayesian Optimization.

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