Practical Efficient Global Optimization is No-regret

Jingyi Wang; Haowei Wang; Nai-Yuan Chiang; Juliane Mueller; Tucker Hartland; Cosmin G. Petra

stat.MLMar 26, 2026

Practical Efficient Global Optimization is No-regret

Authors: Jingyi Wang, Haowei Wang, Nai-Yuan Chiang, Juliane Mueller, Tucker Hartland, Cosmin G. Petra

Organizations: Lawrence Livermore National Laboratory, CA, USA · National University of Singapore, Singapore · National Laboratory of the Rockies, CO, USA

Abstract

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érn kernels ( $ν>\frac{1}{2}$ ). 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.

Figures & tables

Figure 1: Illustrative example of EI contour of the Branin function with 50 samples. From left to right: contour plots for $\epsilon=10^{-2}$ , $\epsilon=10^{-6}$ , $\epsilon=10^{-10}$ , and no nugget. The maximum EI 50 value from left to right: $2.53\times 10^{-2}$ , $1.90\times 10^{-4}$ , $4.72\times 10^{-5}$ , and $4.72\times 10^{-5}$ .

Figure 2: Cumulative regret upper bound with nugget $\epsilon$ at different $T$ and selected constants for SE kernel. The case “other” means neither the conditions for case $1$ nor those for case $2$ are satisfied.

d	kernel	$\epsilon$	t=1	t=50	t=100	t=200
2	SE	$10^{-10}$	0.596	0.091	0.058	0.040
2	SE	$10^{-6}$	0.596	0.141	0.101	0.076
2	SE	$10^{-4}$	0.596	0.153	0.120	0.097
2	Matérn	$10^{-10}$	0.393	0.061	0.031	0.016
2	Matérn	$10^{-6}$	0.393	0.055	0.028	0.015
2	Matérn	$10^{-4}$	0.393	0.054	0.028	0.016

Table 1: The average accumulative regret for different iteration over 20 macro-replications.

Panel of Figure 3 — Figure 3: Median average cumulative regret bound for practical EGO with $\epsilon$ values $10^{-2}$ , $10^{-4}$ , and $10^{-6}$ for five examples. From top to bottom: Rosenbrock, Six-hump camel, Hartmann6, Branin, Michalewicz functions.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Cumulative regret upper bound with nugget $\epsilon$ at different $T$ and selected constants for Matérn kernel ( $\nu=\frac{1}{2}$ ). The case “other” means neither the conditions for case $1$ nor those for case $2$ are satisfied.

Figure 5: Illustrative example of EI contour of the Branin function with 50 random samples. From left to right: contour plots for $\epsilon=10^{-2}$ , $\epsilon=10^{-6}$ , $\epsilon=10^{-10}$ , and no nugget. The maximum EI 50 value from left to right: $0.40515$ , $0.40085$ , $0.40085$ , and $0.40085$ . The maximum level of the colorbar corresponds to the maximum of EI 50 of each plot.

Panel of Figure 6 — Figure 6: 25th and 75th percentile average cumulative regret for practical EGO with nugget values $10^{-2}$ , $10^{-4}$ , and $10^{-6}$ for five examples.

Bayesian Optimization

Bayesian optimization uses probabilistic models and sequential experiments to find strong solutions when evaluating a black-box objective is costly.

See all 240 papers

Exploration strategies for Gaussian process bandit optimization with inference regret guarantees
Oct 12, 2026Hwanwoo Kim, Jungwoo Hong, Kyungjae LeeGaussian Process Bandits Bayesian Optimization
Department of Mathematical Sciences, University of Texas at Dallas · Department of Statistics, Korea University
Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration
Aug 19, 2026Matthias Mandl, Hanne KekkonenGaussian Process Bandits Bayesian Optimization
Delft Institute of Applied Mathematics Delft University of Technology Mekelweg 4, 2628 CD, Delft
Regret-Based $(ε,δ)$ -optimal Stopping Criteria for Bayesian Optimization
May 21, 2026Haowei Wang, Jingyi Wang, Qiyu WeiBayesian Optimization Optimal Stopping
The University of Manchester, UK

Oct 12, 2026J/K move · Enter open · S save

Exploration strategies for Gaussian process bandit optimization with inference regret guarantees

Hwanwoo Kim, Jungwoo Hong, Kyungjae Lee

Department of Mathematical Sciences, University of Texas at Dallas · Department of Statistics, Korea University

Gaussian Process Bandits Bayesian Optimization Regret Minimization Exploration-Exploitation Tradeoff Multi-Armed Bandits

Open paper AskPDF arXiv

Existing cumulative regret guarantees for Bayesian optimization (BO) do not necessarily characterize the quality of the algorithm's final output. This gap is critical under noisy evaluations, where the goal is to return a single high-quality recommendation. To address it, we introduce efficient exploration strategies that can be incorporated into any BO procedure by occasionally replacing the acquisition query with an exploration query. To validate this approach, we bound the Gaussian process posterior standard deviation over the search space via the fill distance of the queries, which measures the largest region left unexplored. We then use this result to derive upper bounds on the inference regret, i.e., the gap between the global optimum and the function value at the algorithm's returned point. Empirically, these exploration strategies improve the final recommendations of existing BO algorithms on synthetic benchmarks, hyperparameter optimization, and a control task.

Abstract

Bayesian Optimization

Explore similar work

Exploration strategies for Gaussian process bandit optimization with inference regret guarantees

Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration

Regret-Based (ε,δ)(ε,δ)(ε,δ)-optimal Stopping Criteria for Bayesian Optimization

Regret-Based $(ε,δ)$ -optimal Stopping Criteria for Bayesian Optimization