mlsanityData to 7 Oct 2026

Practical Efficient Global Optimization is No-regret

arXiv 2603.25311 ↗First posted 26 Mar 2026stat.ML cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

14 of 55 references.

References · 14

  1. 2018GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Accelerationcited by 603
  2. 2018Pyro: Deep Universal Probabilistic Programmingcited by 379
  3. 2017On Kernelized Multi-armed Banditscited by 348
  4. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
  5. 2019Exact Gaussian Processes on a Million Data Pointscited by 118
  6. 2022Recent Advances in Bayesian Optimizationcited by 74
  7. 2014Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameterscited by 30
  8. 2023SMT 2.0: A Surrogate Modeling Toolbox with a focus on Hierarchical and Mixed Variables Gaussian Processescited by 27
  9. 2014BayesOpt: A Bayesian Optimization Library for Nonlinear Optimization, Experimental Design and Banditscited by 18
  10. 2022Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimizationcited by 14
  11. 2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
  12. 2020Regret Bounds for Noise-Free Kernel-Based Banditscited by 11
2 more
  1. 2019Efficient Batch Black-box Optimization with Deterministic Regret Boundscited by 8
  2. 2022Adjusted Expected Improvement for Cumulative Regret Minimization in Noisy Bayesian Optimizationcited by 5

Built on by

Not cited yet.