Principled Design of Expected Improvement for Continuous Simulation Optimization

1 Introduction

• A finite-budget high-probability simple-regret certificate jointly selects the incumbent, replication order, and sampled-design recommendation under unknown heteroscedastic noise.The paper also derives a finite-sample SK confidence bound that supports the analysis; its variance-underestimation correction yields joint coverage over the design space and simulation iterations.Source: §1 · pp. 3–4
• Within general posterior-quantile rule families, the certificate selects a lower-quantile incumbent, an upper-quantile terminal recommendation, and replication order Θ(log T) under mild conditions on common kernels.The lower incumbent keeps potentially optimal regions in contention; the upper terminal quantile accounts for remaining uncertainty among sampled designs.Source: §1 · p. 3
• For SE kernels, simple regret is ˜O(T^-1/2), matching the polynomial dependence in the minimax lower bound; for Matérn kernels, it is ˜O(T^-(2ν-d)/(2ν+d)).Both rates match existing confidence-based bounds under known homoscedastic noise up to logarithmic factors; estimating unknown variances adds at most an additional logarithmic factor.Source: §1 · p. 3

2.1 EI in simulation optimization

• Prior EI simulation methods use differing incumbent, replication, and recommendation rules, while finite-budget theory jointly selecting them under unknown heteroscedastic noise is missing.Existing analyses include asymptotic results, and prior work notes that an inappropriate recommendation rule can offset search gains.Source: §2.1 · p. 4

2.2 Noisy EI theory in GP bandits

• Noisy GP-bandit EI theory typically assumes a specified noise model and studies regret over sampled rounds, whereas simulation optimization must learn noise by replication and return one design.Existing bandit approaches may offer Bayesian regret rather than a high-probability simple-regret guarantee for the returned design.Source: §2.2 · p. 5

3.1 Stochastic Kriging and Expected Improvement

• Stochastic kriging models a latent response with a GP, while EI chooses the next design by expected improvement over an incumbent using predicted performance and uncertainty.Simulation observations combine the latent response with input-dependent normal noise; SK separates response-surface uncertainty from intrinsic simulation noise.Source: §3.1 · pp. 5–6

3.2 Information Gain

• Information gain measures the mutual information between noisy sample-mean observations and latent responses, and its sequential decomposition connects it to cumulative posterior variance.This identity lets regret analysis control cumulative posterior uncertainty at selected points.Source: §3.2 · p. 6

3.3 Reproducing Kernel Hilbert Spaces

• The RKHS norm measures latent-function complexity relative to the kernel, and the analysis assumes the objective lies in a bounded RKHS.The kernel is continuous and normalized, with its diagonal bounded below; SE and Matérn kernels provide the regularity conditions used for regret guarantees.Source: §3.3 · p. 6

4.1 A Generic EI Procedure

• The generic EI procedure uses a common batch size bT at selected designs and returns a sampled design after budget T, while allowing any admissible replication size.The framework requires at least two designs with at least two replications each; replication counts need only share the same asymptotic order for the order-wise guarantees.Source: §4.1 · p. 7

4.1.1 Global linear-quantile incumbents

• The incumbent is the minimum over the full domain of a linear posterior-quantile rule, with cn > 0, cn = 0, and cn < 0 representing lower-quantile, mean, and upper-quantile choices.Full-domain optimization avoids an additional sampled-set approximation term in the analysis.Source: §4.1.1 · p. 7

4.1.2 Final recommendation

• The terminal recommendation is selected from sampled designs using a linear posterior quantile, with dT left unspecified for selection by the later regret certificate.The procedure recommends an evaluated point and accounts for residual uncertainty.Source: §4.1.2 · p. 8

4.2 Confidence Bound for SK Prediction

• When bT = Θ(log T), the variance-estimation correction factors κT and hT remain O(1), whereas superlogarithmic replication can make them approach one but leaves fewer designs to explore.The noise variances need only be uniformly bounded; their bounds are not assumed known to the algorithm.Source: §4.2 · pp. 8–9
• With probability at least 1 −δ, the SK predictor is simultaneously within Λnσn(x) of f(x) over all x ∈ X and iterations n = 0, …, NT.The confidence analysis accounts for estimated heteroscedastic variances; κT corrects for underestimation, while hT controls overestimation.Source: §4.2 · pp. 9–10

5.1 Regret certificate for a sampled point

• The EI-selected point’s regret certificate accounts for an incumbent that may exceed the unknown optimum, transferring its uncertainty term to the selected point through a coefficient depending on the incumbent and confidence bound.The transfer enables subsequent control using posterior variances at sampled points.Source: §5.1 · pp. 10–11

5.2 From sampled points to final simple regret

• A well-certified sampled point is compared with the terminal recommendation by bounding its posterior uncertainty and using the recommendation’s sampled-point quantile rule.The certificate combines this comparison with the bound for EI-selected points.Source: §5.2 · pp. 11–12
• With probability at least 1 −δ, Theorem 5.6 bounds the final recommendation’s simple regret by a sum of a search-process term and two terms for transfer to the terminal recommendation.The incumbent sequence controls the search term, the terminal coefficient controls the transfer terms, and replication size affects all three.Source: §5.2 · p. 12

6.1 Choice of the terminal coefficient

• The terminal coefficient d_T = Λ_NT minimizes the uniform certificate and returns the sampled design with the smallest posterior upper-confidence value.Source: §6.1 · p. 12

6.2 Choice of the incumbent coefficient

• The minimizing incumbent sequence uses c_n = Λ_n, selecting the best lower posterior quantile during search.The lemma establishes that this choice minimizes every term in the bound defining D_T(c).Source: §6.2 · p. 12

6.3 Kernel-Dependent Choice of the Replication Size

• The kernel-specific replication choice minimizes a tractable upper bound; its mild information-gain conditions hold for several common kernel classes.These include finite-rank and exponentially decaying-eigenvalue kernels, and sufficiently fast polynomial eigenvalue decay, including Matérn kernels with ν > d/2.Source: §6.3 · p. 14
• Logarithmic-order replication balances variance learning against spatial exploration: smaller replication produces a large correction, while larger replication sacrifices exploration without improving the bound’s leading order.This conclusion is stated alongside the design choices of an optimistic incumbent and a conservative final recommendation.Source: §6.3 · p. 14

6.4 Kernel-specific rates and comparison with lower bounds

• Under the SE kernel, the resulting bound is minimax optimal in its polynomial dependence on the raw simulation budget, up to logarithmic factors.Learning unknown local variances changes the SE bound by a logarithmic factor, not its polynomial dependence; similar results are reported for Matérn kernels.Source: §6.4 · pp. 14–15

7.1.1 Controlled setting.

• The RKHS experiments use objectives constructed in the assumed RKHS with known kernel hyperparameters, while the comparison also tests four synthetic functions with learned hyperparameters.The synthetic functions span low-dimensional multimodal, densely multimodal, and higher-dimensional landscapes, with 100 macro-replications per test.Source: §7 · p. 15, §7.1.1 · p. 15, §7.2 · p. 17

7.1.2 Empirical evidence of the regret bound

• On the four-dimensional Matérn-5/2 objective, mean GAP falls from 2.5861 at T = e8 to 0.1017 at T = e10, remaining below the normalized theoretical reference curve.Across all four RKHS settings, mean simple regret decreases over the displayed budgets and stays below the corresponding reference curves.Source: §7.1.2 · pp. 15–16, Figure 1 · p. 16

7.1.3 Ablation of the design choices

• The calibrated lower-confidence incumbent has the smallest average GAP, while the calibrated logarithmic replication schedule outperforms the tested O(1), O(log log T), and O(T^1/2) alternatives.Other incumbent rules converge more slowly as budgets grow; smaller replication counts give noisier local estimates, whereas O(T^1/2) can leave too few adaptive decisions.Source: §7.1.3 · pp. 16–17, Figure 2 · p. 17
• The proposed final rule and posterior-mean recommendation are nearly indistinguishable in the reported test, and both outperform the lower-quantile criterion.The paper reports an additional larger-noise experiment where penalizing residual uncertainty more clearly improves recommendation reliability.Source: §7.1.3 · pp. 16–17
• Across the fully crossed 36 configurations, the proposed combination consistently ranks among the top two on the RKHS objectives.This complements one-factor-at-a-time tests by checking the three design choices jointly.Source: §7.1.3 · p. 17

7.2 Comparison with Existing Algorithms

• At T = e10, CertEI attains the smallest average GAP on all six problems, with its advantage most pronounced on Camelback and rescaled Branin.It improves most consistently as budgets increase, though it is not always best at smaller budgets and Hills remains difficult for all methods.Source: §7.2 · pp. 17–18, Figure 3 · p. 18

8 Summary

• The regret-bound-guided design uses a lower-quantile incumbent, Θ(log T) replications, and a conservative upper-quantile recommendation over sampled designs.The bound relies on a finite-sample confidence inequality for the SK predictor when noise variances are estimated from replications.Source: §8 · p. 18
• For SE kernels, simple regret is eO(T^-1/2), matching the polynomial dependence in the minimax lower bound; for Matérn kernels, the rate matches its known-homoscedastic confidence-bound counterpart up to logarithmic factors.Source: §8 · p. 18

B Proof of Lemma 4.3

• For fixed replication number b ≥ 2, the proof gives hT = Θ(log T), while bT = Θ(log T) yields hT = Θ(1) and bT/log T → ∞ gives hT → 1.These regimes describe how the proof’s variance-related factor hT changes with the replication schedule.Source: B Proof of Lemma 4.3 · p. 20

• The proof bounds the probability of the complement of VT by δ/2, then combines variance and confidence events whose total failure probability is at most δ.On VT, the auxiliary estimator equals the clipped plug-in SK predictor for n = 1,…,NT.Source: C Proof of Theorem 4.4 · p. 21
• The analysis reveals each batch’s sample variance before its sample mean; under Gaussian sampling, the two are independent conditional on the enlarged history.This filtration makes the conditional sample-mean error Gaussian with variance d_q^2.Source: C Proof of Theorem 4.4 · p. 21
• The RKHS confidence inequality yields a bound holding simultaneously for all n ≥ 1 and all x in X with probability at least 1 − δ/2.The proof applies it to the enlarged filtration and the auxiliary predictor.Source: C Proof of Theorem 4.4 · p. 21

D Proof of Lemma 5.1

• An EI maximizer has predictive standard deviation at least that of the quantile-minimizing design.The proof obtains this from global quantile minimality and EI optimality.Source: D Proof of Lemma 5.1 · p. 22

E Proof of Lemma 5.2

• The quantile adjustment qc(r) is uniquely defined and satisfies qc(r) ≥ c for r ≥ 1.This follows from the continuity and strict increase of τ and the defining equation for qc(r).Source: E Proof of Lemma 5.2 · p. 22

F Proof of Lemma 5.3

• On the confidence event, f(x) − f⋆ is bounded by {Λn + qc(ρ)}σn(x) plus the positive-part incumbent error (ξ − f⋆)+.The proof’s coefficient A(Λn, c) is minimal under the two scalar conditions u ≤ −c and |u − t| ≤ λ.Source: F Proof of Lemma 5.3 · pp. 22–23

G Proof of Lemma 5.4

• The normalized posterior-variance quantity n(x) is at most 1 because the kernel diagonal is bounded by 1 and conditioning cannot increase posterior variance.Source: G Proof of Lemma 5.4 · p. 23

H Proof of Lemma 5.5

• The realized clipped plug-in SK predictor’s replication count is bounded by 2γ_SK_NT log(1 + b_T/W_T).The proof compares log determinants using the lower bound on the observation-noise matrix.Source: H Proof of Lemma 5.5 · p. 24

I Proof of Theorem 5.6

• The recommendation’s posterior standard deviation is bounded by ω_T at sampled locations, and the selected incumbent has standard deviation at most η_T.The proof uses posterior-variance monotonicity as observations are added.Source: I Proof of Theorem 5.6 · pp. 24–25
• The regret bound is at most {D_T(c) + 2Λ_NT}η_T under the stated inequalities.The preceding bound is D_T(c)η_T + 2Λ_NTζ_T; the proof concludes that the stated conclusions hold on G_T.Source: I Proof of Theorem 5.6 · p. 25

J Proof of Corollary 6.2

• Setting c_n = Λ_n and d_T = Λ_NT makes A(Λ_n, c_n) = 0, and substitution into Theorem 5.6 yields the claimed bound.The proof notes that Λ_n and ℓ_n are nondecreasing.Source: J Proof of Corollary 6.2 · p. 25

K Proof of Lemma 6.1

• The function A(λ, c) is at least (λ − c)+, and the resulting function q̄_n is nondecreasing and 1-Lipschitz.The proof establishes the lower bound on A and then uses it with monotonicity to obtain the Lipschitz property.Source: K Proof of Lemma 6.1 · pp. 25–26

L Proofs for the Replication-Number Analysis

• The replication-number analysis uses the calibrated Theorem 5.6 bound with d_T = Λ_NT, yielding the same replication objective as Corollary 6.2.Source: L Proofs for the Replication-Number… · p. 26

L.1 Proof of the Finite-Batch Information-Gain Bound

• For a normalized kernel, the covariance matrix on any finite point collection has trace at most the collection size, so the derived bound is independent of the chosen points and batch size.Source: §L.1 · p. 26

L.2 Proof of the General-Kernel Replication Theorem

• Neither sublogarithmic nor superlogarithmic replication can minimize the bound; the analysis evaluates a logarithmic replication candidate.At b_0 = ⌈c log T⌉, the proof gives h_T(b_0) = O(1), W_T(b_0) = Θ(1), and log(1 + b_0/W_T(b_0)) = Θ(log log T).Source: §L.2 · pp. 27–28

M.1 Finite-rank kernels

• For fixed-rank kernels, the proof verifies the conditions used in Theorem 6.5, including that g_T = Θ(log T) when v_0 is fixed.The section’s stated role is to verify the theorem’s three conditions for commonly used kernel classes.Source: M Kernel Classes Satisfying the… · p. 28, §M.1 · p. 29
• The finite-rank class includes linear kernels and fixed-degree polynomial kernels on bounded finite-dimensional domains.Source: §M.1 · p. 29

M.2 Kernels with exponential eigenvalue decay

• Under the stated regularity conditions, kernels with exponential eigenvalue decay satisfy all three conditions of Theorem 6.5; the SE kernel is an example.Source: §M.2 · p. 29

M.3 Kernels with polynomial eigenvalue decay

• Kernels with polynomial eigenvalue decay satisfy all three conditions of Theorem 6.5 when β_p > 2; for Matérn kernels, this requires ν > d/2.Source: §M.3 · pp. 29–30

N Derivation of the Rate after Choosing the Replication Number and Kernels

• Under Theorem 6.5’s conditions, the replication size is chosen as b_T = Θ(log T).Source: N Derivation of the Rate after… · p. 30

O.1 Objective Functions and Experimental Settings

• The fixed RKHS objectives use SE and Matérn-5/2 kernels in dimensions two and four, with shared basis points and weights between kernels within each dimension.The four-dimensional experiments use 40 initial Latin-hypercube points; the replication-order ablation instead uses 20 to keep O(T^1/2) feasible at the smallest budget.Source: §O.1 · p. 31

O.2 Additional EI-incumbent ablation

• In all three additional incumbent-ablation settings, the CertEI incumbent has the smallest average GAP at every reported budget; the upper-quantile incumbent is generally worst as budgets increase.Source: §O.2 · p. 31

O.3 Additional Replication-order ablation

• O(log T) achieves the lowest average GAP across both two-dimensional objectives at all three budgets, while its advantage varies by kernel and larger replication can become competitive at higher budgets.Source: §O.3 · p. 31

O.4 Additional Final-recommendation ablation

• Across the additional instances, the calibrated upper-quantile and posterior-mean recommendation rules perform comparably, while the optimistic lower-quantile rule has larger average GAP.Source: §O.4 · p. 32

O.4.1 A diagnostic terminal-selection test

• In the high-noise diagnostic, the conservative recommendation has substantially smaller GAP than posterior-mean selection, while the optimistic rule performs worst.Source: §O.4.1 · p. 33

O.5 Joint Ablation of the Three Design Choices

• The recommended three-choice configuration ranks among the top two of 36 in every tested setting; joint ablations favor O(log T) replication and the proposed lower-quantile incumbent.Source: §O.5 · pp. 34, 36, Figure 8 · p. 35, Figure 9 · p. 35

O.6 Settings for the Synthetic Test Functions

• The synthetic test functions use Matérn-5/2 kernels and noise that is largest near the global optimum.Source: §O.6 · p. 36