# Practical Efficient Global Optimization is No-regret

arXiv: https://arxiv.org/abs/2603.25311 · HTML: https://mlsanity.com/paper/2603.25311/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 55 references that are in the map.
- First posted on arXiv 26 Mar 2026.

## Builds on (most cited first, 14 of 14)

- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Pyro: Deep Universal Probabilistic Programming](https://mlsanity.com/paper/1810.09538/) (2018)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Exact Gaussian Processes on a Million Data Points](https://mlsanity.com/paper/1903.08114/) (2019)
- [Recent Advances in Bayesian Optimization](https://mlsanity.com/paper/2206.03301/) (2022)
- [Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters](https://mlsanity.com/paper/1406.7758/) (2014)
- [SMT 2.0: A Surrogate Modeling Toolbox with a focus on Hierarchical and Mixed Variables Gaussian Processes](https://mlsanity.com/paper/2305.13998/) (2023)
- [BayesOpt: A Bayesian Optimization Library for Nonlinear Optimization, Experimental Design and Bandits](https://mlsanity.com/paper/1405.7430/) (2014)
- [Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2203.07875/) (2022)
- [Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization](https://mlsanity.com/paper/2506.01393/) (2025)
- [Regret Bounds for Noise-Free Kernel-Based Bandits](https://mlsanity.com/paper/2002.05096/) (2020)
- [Efficient Batch Black-box Optimization with Deterministic Regret Bounds](https://mlsanity.com/paper/1905.10041/) (2019)
- [Adjusted Expected Improvement for Cumulative Regret Minimization in Noisy Bayesian Optimization](https://mlsanity.com/paper/2205.04901/) (2022)

## Abstract (arXiv)

Efficient global optimization (EGO) is one of the most widely used noise-free Bayesian optimization algorithms.It comprises the Gaussian process (GP) surrogate model and expected improvement (EI) acquisition function. In practice, when EGO is applied, a scalar matrix of a small positive value (also called a nugget or jitter) is usually added to the covariance matrix of the deterministic GP to improve numerical stability. We refer to this EGO with a positive nugget as the practical EGO. Despite its wide adoption and empirical success, to date, cumulative regret bounds for practical EGO have yet to be established. In this paper, we present for the first time the cumulative regret upper bound of practical EGO. In particular, we show that practical EGO has sublinear cumulative regret bounds and thus is a no-regret algorithm for commonly used kernels including the squared exponential (SE) and Mat'ern kernels (nu>frac12). Moreover, we analyze the effect of the nugget on the regret bound and discuss the theoretical implication on its choice. Numerical experiments are conducted to support and validate our findings.