Principled Design of Expected Improvement for Continuous Simulation Optimization

Songhao Wang; Jianglin Xia; Haowei Wang; Szu Hui Ng

stat.MLOct 13, 2026

Principled Design of Expected Improvement for Continuous Simulation Optimization

Authors: Songhao Wang, Jianglin Xia, Haowei Wang, Szu Hui Ng

Organizations: College of Business, Southern University of Science and Technology, Shenzhen, CHINA · Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore, SINGAPORE

Abstract

Expected improvement based on stochastic kriging (SK) surrogate is widely used in continuous simulation optimization, but unknown heteroscedastic noise makes three basic design choices consequential: the incumbent to define improvement, replication allocation, and final recommendation. Existing methods typically either assume the noise levels are known or choose these components separately through heuristic rules or empirical calibration. We instead derive a high-probability upper bound on the simple regret and systematically choose the three components within general rule classes to tighten this bound. We first establish a finite-sample confidence bound for the SK predictor as a foundation for the three design choices. Within general posterior-quantile rule classes, tightening the regret certificate selects a lower-quantile incumbent and an upper-quantile recommendation among sampled designs. The opposing quantiles reflect the different roles of exploratory experiments and the final implemented decision. Under mild conditions satisfied by common kernels, minimizing a tractable kernel-specific bound yields a logarithmic replication order. Based on these design choices, the resulting simple regret matches the existing results under known homoscedastic noise up to logarithmic factors. To our knowledge, this is the first simple-regret guarantee of this form for a continuous-domain EI-type simulation optimization method that learns unknown heteroscedastic variances through replications.

Figures & tables

Panel of Figure 1 — Figure 1: Average simple regret of CertEI on the RKHS objectives.

Panel of Figure 2 — Figure 2: Controlled ablations on the four-dimensional Matérn- $5/2$ objective.

Panel of Figure 3 — Figure 3: Average GAP of the four algorithms

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Kernel	$x^{\star}_{1}$	$x^{\star}_{2}$	$f^{\star}$	$f_{\max}$	$R_{f}$	$B_{f}$
Matérn- $5/2$	0.058755	0.952746	-2.945546	3.072480	6.018026	6.931367
Squared exponential	0.609984	0.537395	-3.081055	3.369256	6.450311	6.935835

Appendix

Table 1: Properties of the two-dimensional RKHS objectives

Kernel	$x^{\star}$	$f^{\star}$	$f_{\max}$	$R_{f}$	$B_{f}$
Matérn- $5/2$	$(0.680540,0.617090,0.067218,0.626605)$	-5.390637	3.219524	8.610161	11.255655
Squared exponential	$(0.678059,0.621087,0.066322,0.619068)$	-6.000295	3.217247	9.217542	11.318412

Appendix

Table 2: Properties of the fixed four-dimensional RKHS objectives.

Panel of Figure 4 — Figure 4: Additional EI-incumbent ablations

Panel of Figure 5 — Figure 5: Average GAP under the four replication orders for the additional objective functions

Panel of Figure 6 — Figure 6: Average GAP under the three final-recommendation rules

Component	Kernel centers	Weight per center
Safe basin	$c_{\mathrm{s}}$ and the eight axis offsets $c_{\mathrm{s}}\pm 0.11e_{i}$ , $i=1,\ldots,4$	$-0.06986611$
Global basin	$(0.72,0.72,0.72,0.72)$	$-0.97812556$
Decoy basins	$(0.76,0.24,0.76,0.24)$ , $(0.24,0.76,0.24,0.76)$ , $(0.78,0.78,0.22,0.22)$ , and $(0.22,0.22,0.78,0.78)$	$-0.41919667$

Appendix

Table 3: Kernel centers and normalized coefficients of the diagnostic objective.

Figure 7: GAP distributions at three representative budgets

Figure 8: Joint ablation on the two-dimensional Matérn- $5/2$ objective

Figure 9: Joint ablation on the two-dimensional SE objective

Figure 10: Joint ablation on the four-dimensional Matérn- $5/2$ objective

Problem	$d$	$(a,b)$	$\rho$	Candidates
Six-hump Camelback	2	$(4,-1.75)$	8	2,048
Rescaled Branin	2	$(4,-3)$	6	2,048
Hills	2	$(8,-1.5)$	8	2,048
Hartmann-6	6	$(7.2,-3.5)$	8	10,000

Appendix

Table 4: Settings for the analytical test functions. The nominal replication size is

\rho\log T

Stochastic Optimization

Stochastic optimization studies how to find good decisions or model parameters when objectives, data, or feedback are random or noisy.

See all 209 papers

Jul 31, 2026

Simple-regret rates and minimax optimality of fixed-prior expected improvement in Matérn and squared-exponential RKHSs

We study expected improvement (EI) for minimizing a deterministic function

f

in the RKHS

\mathcal H_k

of a continuous positive-semidefinite kernel

k

on a nonempty compact set

\mathcal X\subset\mathbb R^d

. Function values are observed exactly, and EI is computed from a fixed zero-mean Gaussian-process model with covariance

σ^2k

σ>0

. A weak-EI policy queries a point whose EI is at least a fixed positive fraction of its maximum. We introduce a notion of sequential separation radius relating ranked selected-point innovation norms to Kolmogorov widths, drawing on greedy approximation. Standard power-function estimates from scattered-data approximation and a finite-budget regret argument yield the rates. After

N

post-initial queries, every weak-EI policy has simple regret

O(N^{-ν/d})

for isotropic Matérn kernels of smoothness

ν>0

and

O(\exp[-c_1\min\{N,N^{1/d}\log(eN)\}])

for the isotropic squared-exponential kernel, with

c_1>0

. For

d=1

, the sharper bound

O(\exp[-c_2N\log(eN)])

holds for exact EI, with

c_2>0

. These bounds are uniform over each fixed RKHS ball. If

\mathcal X

has nonempty interior and

B>0

, the exact EI policy is minimax-rate optimal over the RKHS ball of radius

B

for Matérn kernels, even among randomized strategies whose final recommendation need not be a query point. For the squared-exponential kernel, it is minimax-rate optimal up to constants in the exponent among deterministic methods whose final recommendation may be any point of

\mathcal X

Emmanuel Vazquez, Sébastien Petit

Université Paris-Saclay, CNRS, CentraleSupélec, Laboratoire des Signaux et Systèmes, 91190 Gif-sur-Yvette, France · Laboratoire national de métrologie et d’essais (LNE), 1 rue Gaston Boissier, 75724 Paris Cedex 15, France

Bayesian Optimization Gaussian Processes Regret Minimization Kernel Methods

Ask PDF

Jun 6, 2024

Simulating, Fast and Slow: Learning Policies for Black-Box Optimization

Simulators are vital in science and engineering, as they faithfully model the influence of design parameters on real-world observations. Optimizing design parameters to minimize a desired objective function is notoriously challenging since simulators are often non-differentiable black boxes. Moreover, each simulation incurs significant compute time, thus doing such optimizations naively may be prohibitively expensive. Furthermore, in experiment design settings, practitioners are typically required to solve the same optimization problem for various input distributions before proceeding to real-world experiments. Starting these related optimizations from scratch each time can be inefficient if the forward simulation model is expensive to evaluate. To address these challenges, this paper introduces a novel method for solving black-box optimization problems on various input distributions by learning a policy that guides the training of a differentiable surrogate. The surrogate's gradients are then used to optimize the simulation parameters with SGD. After training the policy, the cost for downstream optimization of problems involving black-box simulators is amortized, and we require up to

10\times

fewer expensive simulator calls compared to baselines such as previous local surrogate-based approaches, numerical optimization, and Bayesian optimization.

Tim Bakker, Fabio Valerio Massoli, Thomas Hehn +2

University of Amsterdam § · Qualcomm AI Research‡

Black-Box Optimization Learning to Optimize Surrogate-Assisted Optimization

Ask PDF

Mar 26, 2026

Practical Efficient Global Optimization is No-regret

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.

Jingyi Wang, Haowei Wang, Nai-Yuan Chiang +3

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

Bayesian Optimization Global Optimization Regret Minimization

Ask PDF

Abstract

Stochastic Optimization

Explore similar work

Simple-regret rates and minimax optimality of fixed-prior expected improvement in Matérn and squared-exponential RKHSs

Simulating, Fast and Slow: Learning Policies for Black-Box Optimization

Practical Efficient Global Optimization is No-regret