Simple-regret rates and minimax optimality of fixed-prior expected improvement in Matérn and squared-exponential RKHSs Emmanuel Vazquez1 and Sébastien Petit2 1
arXiv:2607.29245v1 [stat.ML] 31 Jul 2026
Université Paris-Saclay, CNRS, CentraleSupélec, Laboratoire des Signaux et Systèmes, 91190 Gif-sur-Yvette, France, [email protected] 2 Laboratoire national de métrologie et d’essais (LNE), 1 rue Gaston Boissier, 75724 Paris Cedex 15, France, [email protected]
Abstract We study the expected improvement (EI) policy for minimizing a deterministic objective function f on a nonempty compact set X ⊂ Rd . We assume that f belongs to the RKHS Hk of a continuous positive-semidefinite kernel k on X . Function values are observed exactly, and EI is computed from a fixed zero-mean Gaussian-process model with covariance σ 2 k. After an initial design, the policy queries a point whose EI is at least a fixed positive fraction of its maximum. We identify the normalized posterior standard deviation at a candidate point x with the norm of the corresponding innovation in the canonical feature space, namely the component of k(x, ·) orthogonal to the span of the preceding evaluation representers. Sequential separation radii bound the ranked innovation norms along arbitrary query sequences. We estimate these radii using Gram determinants and Kolmogorov widths for subspaces of different dimensions, then combine the estimates with a one-step regret inequality to obtain finite-budget bounds for simple regret. After N post-initial queries, simple regret is O(N −ν/d ) for isotropic Matérn kernels of smoothness ν > 0. For the isotropic squared-exponential kernel, simple regret is O(exp[−c1 min{N, N 1/d log(eN )}]) for some c1 > 0. With exact EI maximization, it is O(exp[−c2 N 1/d log(eN )]) for some c2 > 0. For every fixed B ≥ 0, these bounds are uniform over the RKHS ball of radius B. The zero prior mean may be replaced by a known µ0 ∈ C(X ) when f − µ0 ∈ Hk . If X has nonempty interior and B > 0, then, among deterministic methods whose final recommendation may be any point of X , the exact EI policy is minimax-rate optimal over the RKHS ball of radius B for Matérn kernels and minimax-rate optimal up to constants in the exponent for squared-exponential kernels.
Keywords: Bayesian optimization; expected improvement; simple regret; minimax rates; reproducing-kernel Hilbert spaces; sequential separation radii; Kolmogorov widths.
1
Introduction
Let X ⊂ Rd , d ≥ 1, be nonempty and compact, and let k : X × X → R be continuous and positive semidefinite. Write Hk for the reproducing-kernel Hilbert space (RKHS) of k. We seek to minimize a deterministic function f ∈ Hk satisfying ∥f ∥Hk ≤ B, where B ≥ 0. Its queried values are observed exactly.
1
Starting from an initial design of n0 ≥ 1 query points x1 , . . . , xn0 , we use expected improvement (EI) as a sampling criterion to select xn0 +1 , xn0 +2 , . . .. To define EI, we use a fixed zero-mean Gaussian-process model Z with covariance σ 2 k, σ > 0. Given the past query points x1 , . . . , xn , n ≥ n0 , and their observed values f (x1 ), . . . , f (xn ), we condition the model on Z(xi ) = f (xi ), 1 ≤ i ≤ n. For each candidate point x ∈ X , the posterior distribution of Z(x) serves as a predictive distribution for f (x). The EI at x is the posterior expected amount by which Z(x) falls below the best observed value. The (exact) EI policy selects a point xn+1 at which EI is maximal. A weak-EI policy selects a point whose EI is at least a fixed fraction η ∈ (0, 1] of the maximum. We evaluate the objective function at xn+1 and condition the model on the enlarged data. We call the resulting sequential design (xn )n≥1 of query points a fixed-prior EI trajectory. Early probabilistic methods for sequential optimization appeared in the 1960s and 1970s (Matheron and Formery, 1962; Kushner, 1964; Močkus, 1975), and the notion of EI emerged during the same period (Močkus et al., 1978). Garnett (2023, Chapter 12) gives a historical account. Jones et al. (1998) popularized EI for computer experiments through the efficient global optimization algorithm. EI has since become a standard sampling criterion in what is now commonly called Bayesian optimization. With one evaluation remaining and the final estimate of the minimizer required to be one of the query points, querying an EI maximizer is a one-step Bayes-optimal strategy: it minimizes the posterior expectation of the best value observed after that evaluation (Vazquez and Bect, 2010a, Section 1). Over a longer horizon, repeating this one-step rule yields a myopic policy that is, however, widely used both in machine learning and in engineering design based on numerical simulations. Previous results and minimax comparisons. When EI is maximized exactly and k has the no-empty-ball property (Definition 2.2), the query sequence is dense in X for every f ∈ Hk , and the best observed value converges to the global minimum (Vazquez and Bect, 2010a, Theorem 6). (For an objective function sampled from the Gaussian-process prior, Vazquez and Bect (2010a, Theorem 7) also prove almost-sure density for the exact EI policy under the no-empty-ball property, but this probabilistic result lies outside the deterministic RKHS setting considered here.) Let T > n0 be the total number of evaluations and put N := T − n0 . Define the simple regret after T evaluations by rT := min f (xi ) − min f (x) . 1≤i≤T
x∈X
For exact EI strategies whose initial design is chosen independently of f , possibly at random, and with arbitrary selection among EI maximizers, Bull (2011, Theorem 2) proves worst-case expected simple-regret bounds when the covariance parameters are fixed and an unknown constant mean is integrated under a flat prior. If X has nonempty interior and the kernel is Matérn with smoothness ν, the upper bound is O(N −ν/d ) when 0 < ν < 1, √ O(N −1/d log N ) when ν = 1, and O(N −1/d ) when ν > 1. Thus its polynomial exponent saturates at 1/d for ν ≥ 1. For the squared-exponential kernel, the upper bound is O(N −1/d ). Bull (2011, Theorem 1) establishes the Matérn minimax rate N −ν/d . The randomized ε-greedy EI policy defined by Bull (2011, Definition 4) intersperses exact EI queries with uniformly random queries on X . Bull (2011, Theorem 5) proves that this policy attains the minimax rate, up to logarithmic factors, for every finite ν. The contrast between the saturation of the upper bound established by Bull for the exact EI policy and the rate attained by the randomized ε-greedy EI policy raises the natural question whether the 2
exact fixed-prior EI policy attains the rate N −ν/d for every ν > 0, without space-filling random queries. We prove in Theorem 7.3 that it does. Related work. With noisy observations and an objective function in an RKHS, TranThe et al. (2022, Theorems 1 and 2) obtain high-probability cumulative-regret bounds for two modified EI policies with iteration- or budget-dependent multipliers of the predictive standard deviation. When the objective function is sampled from a Gaussian process, Wang et al. (2025, Theorem 4.9) bound with high probability the difference between the best noisy observation and the global minimum for EI with Gaussian observation noise. For the noise-free Gaussian-process upper confidence bound (GP-UCB), Iwazaki (2025, Lemma 3 and Theorem 2) gives the simple-regret upper bounds O(N −ν/d (log N )ν/d ) for √ Matérn kernels with ν > 1/2 and O( N exp{−cN 1/(d+1) }) for the squared-exponential kernel, for some c > 0. The polynomial exponent in the Matérn bound agrees with the exponent in Theorem 6.3 in this work. Iwazaki (2025) proves these bounds using estimates of the maximum information gain for a Gaussian-process model with an auxiliary noise variance. Our proof draws on methods from greedy approximation and scattered-data approximation in RKHSs. Main results. For an isotropic Matérn kernel of smoothness ν > 0, we show in Theorem 6.3 that every fixed-prior EI trajectory generated by a weak-EI policy has simple regret rT = O N −ν/d . When B > 0 and X has nonempty interior, Theorem 7.3 establishes that the exact EI policy is minimax-rate optimal among deterministic methods whose final recommendation may be any point of X . For the isotropic squared-exponential kernel, Theorem 6.6 shows that, along every fixed-prior EI trajectory generated by a weak-EI policy, the simple regret satisfies, for some A′ , b′ > 0, rT ≤ A′ exp{−b′ min{N, N 1/d log(eN )}}, for all sufficiently large N . When B, X , k, σ, η, and the initial design are fixed, both kernel bounds hold uniformly over f ∈ Hk with ∥f ∥Hk ≤ B. When B > 0 and X has nonempty interior, Theorems 6.6 and 7.4 establish that the exact EI policy is minimax-rate optimal up to constants in the exponent among deterministic methods whose final recommendation may be any point of X . Regret bounds from approximation estimates. We call the component of k(xn+1 , ·) orthogonal to the span of the preceding evaluation representers k(x1 , ·), . . . , k(xn , ·) the selected-point innovation and denote its norm by vn+1 . Proposition 3.2 and regret monotonicity give, for some constants 0 ≤ q < 1 and C > 0, the one-step regret bound rn+1 ≤ min{rn , qrn + Cvn+1 },
n ≥ n0 .
(1.1)
The regret analysis combines (1.1) with approximation bounds for the selected-point innovation norms. The sequential separation radius of a kernel k on X , denoted by δm (k, X ) for m ≥ 1, is the supremum over ordered m-tuples of the smallest successive innovation norm. Let k0 be the normalized posterior covariance kernel after conditioning on the initial design. Let v[1] ≥ · · · ≥ v[N ]
3
be the decreasing rearrangement of vn0 +1 , . . . , vT . Lemma 4.2 gives v[m] ≤ δm (k0 , X ) ≤ δm (k, X ),
1 ≤ m ≤ N.
For each 1 ≤ L ≤ N , applying the affine branch qrn + Cvn+1 in (1.1) at the L evaluations with the smallest realized innovation norms and regret monotonicity at all remaining iterations gives the finite-budget estimate of Theorem 4.4, expressed in terms of the separation radii. To bound the separation radii, we use the Kolmogorov widths dm (k, X ), which measure how well the evaluation representers can be approximated uniformly by subspaces of Hk of dimension at most m. The connection between sequential separation radii and these widths draws on results from greedy approximation (Binev et al., 2011; DeVore et al., 2013; Wenzel et al., 2023). Given x1 , . . . , xm ∈ X , consider the kernel matrix (k(xi , xj ))1≤i,j≤m . Lemma 5.2 bounds its jth largest eigenvalue in terms of a Kolmogorov width at a rank chosen separately for each j. Standard power-function estimates from scattered data approximation, applied to regular grids, give dm (k, X ) = O(m−ν/d ) for Matérn kernels (Schaback and Wendland, 2002, Theorem 3.2) and dm (k, X ) = O(exp[−cm1/d log m]) for the squared-exponential kernel, for some c > 0 (Wendland, 2004, Theorem 11.22). Lemma 5.2 converts these width estimates into bounds on the separation radii. Scope and organization. Weak-EI policies attain the Matérn rate and the squaredexponential bound (6.10), are simple-regret consistent, and have dense query points when k has the no-empty-ball property. Exact EI maximization is needed for the minimax comparisons, while the analysis assumes exact observations and covariance parameters chosen independently of the data. Appendix G extends the upper regret bounds to a known continuous prior mean. Sections 2–5 establish the one-step regret bound and approximation bounds used in Section 6 to prove the rate theorems. Section 7 contains the minimax comparisons, and Section 8 discusses their scope.
2
Setting and preliminary results
2.1
Fixed-prior model and feature-space innovations
Let X ⊂ Rd , d ≥ 1, be nonempty and compact, and let k : X × X → R be continuous and positive semidefinite. Write Hk for its reproducing-kernel Hilbert space. We use Z ∼ GP(0, σ 2 k),
σ > 0,
(2.1)
as a fixed prior model. Let B ≥ 0 and assume that the deterministic objective function satisfies f ∈ Hk ,
∥f ∥Hk ≤ B.
(2.2)
x ∈ X.
(2.3)
Without loss of generality, we assume k(x, x) ≤ 1,
The initial design consists of n0 ≥ 1 query points and does not vary with the total evaluation budget. At every query point xi , we observe zi := f (xi ) exactly. Define, for j ≥ 1 and x = (x1 , . . . , xj ) ∈ X j , Vx := span{k(·, xi ), 1 ≤ i ≤ j}, 4
and set V∅ := {0}. Let Πx be the orthogonal projector onto Vx for every finite tuple x. The orthogonal projector onto Vx⊥ is Π⊥ x := I − Πx . Define, for x ∈ X , ιx (x) := Π⊥ x k(·, x),
Px (x) := ∥ιx (x)∥Hk = distHk k(·, x), Vx .
(2.4)
The vector ιx (x) is the feature-space innovation: the component of k(·, x) orthogonal to Vx . The function Px is the power function for x (Wendland, 2004). Its value Px (x) is the innovation norm at x. For the query history x = (x1 , . . . , xn ), with n ≥ n0 , we use the shorter notation Vn := Vx = span{k(·, xi ), 1 ≤ i ≤ n}, Πn := Πx ,
⊥ Π⊥ n := Πx = I − Πn .
The Gram matrix in Hk of the evaluation representers k(·, x1 ), . . . , k(·, xn ) is n Kn := ⟨k(·, xi ), k(·, xj )⟩Hk i,j=1 = [k(xi , xj )]ni,j=1 . We also write kn (x) := (k(x1 , x), . . . , k(xn , x))⊤ ,
zn := (z1 , . . . , zn )⊤ .
Define the evaluation map En : Hk −→ Rn ,
En f := (f (x1 ), . . . , f (xn ))⊤ .
Then Kn = En En∗ and hence Range(Kn ) = Range(En ). Thus zn = En f and kn (x) = En k(·, x) belong to Range(Kn ). Writing Kn† for the Moore–Penrose inverse of Kn , conditioning Z on Z(xi ) = zi , 1 ≤ i ≤ n, gives the posterior mean µn and normalized posterior standard deviation sn : µn (x) = kn (x)⊤ Kn† zn = (Πn f )(x), (2.5) 2 s2n (x) = k(x, x) − kn (x)⊤ Kn† kn (x) = ∥Π⊥ n k(·, x)∥Hk . The formulas in (2.5) remain valid for repeated evaluation sites and singular Gram matrices. By (2.4), sn (x) = P(x1 ,...,xn ) (x) = distHk k(·, x), Vn . (2.6) For x ∈ X , the deterministic interpolation error satisfies f (x) − µn (x) = f − Πn f, ι(x1 ,...,xn ) (x) H . k
The posterior predictive standard deviation is σsn (x). At the next query point, we write ιn+1 := ι(x1 ,...,xn ) (xn+1 ), vn+1 := ∥ιn+1 ∥Hk = P(x1 ,...,xn ) (xn+1 ) = sn (xn+1 ). The canonical isometry k(·, x) 7→ Z(x)/σ also gives vn+1 =
1 ∥Z(xn+1 ) − E [Z(xn+1 ) | Z(x1 ), . . . , Z(xn )]∥L2 . σ 5
(2.7)
2.2
Sequential separation radii
Define the sequential separation radius of k at rank m ≥ 1 by δm (k, X ) :=
sup
min P(x1 ,...,xj−1 ) (xj ).
x1 ,...,xm ∈X 1≤j≤m
(2.8)
Thus δm (k, X ) is the supremum, over all m-point sequences, of their smallest successive innovation norm. The sequence (δm (k, X ))m≥1 is nonincreasing. Indeed, the minimum for an (m+1)-point sequence is no larger than the minimum for its m-point prefix, and taking the supremum gives δm+1 (k, X ) ≤ δm (k, X ). In particular, p 0 ≤ δm (k, X ) ≤ δ1 (k, X ) = sup k(x, x). x∈X
By (2.3), δm (k, X ) ≤ 1. Rescaling the kernel by c2 gives δm (c2 k, X ) = c δm (k, X ),
c > 0.
Lemma 2.1 (Decay of the sequential separation radii). For the continuous kernel k on the compact set X , δm (k, X ) ↓ 0 (m → ∞). (2.9) Proof. The map x 7→ k(·, x) is continuous, so its image is compact in Hk . If all successive innovation norms of (x1 , . . . , xm ) ∈ X m exceed ε, then, for i < j, k(·, xj ) − k(·, xi ) H ≥ P(x1 ,...,xj−1 ) (xj ) > ε. k
Thus the m evaluation representers are pairwise ε-separated. The standard packing argument for compact metric spaces bounds their number in terms of ε. Hence δm (k, X ) ≤ ε for all sufficiently large m. Since ε > 0 is arbitrary and the separation radii are nonincreasing, (2.9) follows.
2.3
Restart after the initial design
After the initial design, let Ψ0 (x) := Π⊥ n0 k(·, x) be the projected canonical feature map. Define the residual kernel k0 by k0 (x, y) := ⟨Ψ0 (x), Ψ0 (y)⟩Hk .
(2.10)
For g ∈ Vn⊥0 and x ∈ X , ⟨g, Ψ0 (x)⟩Hk = ⟨g, k(·, x)⟩Hk = g(x). This identity shows that Ψ0 (X ) spans Vn⊥0 densely and that Vn⊥0 , with the norm inherited from Hk , is an RKHS with reproducing kernel k0 . By uniqueness, Hk0 = Vn⊥0 isometrically. In particular, k0 (·, x) = Ψ0 (x) as functions on X . After conditioning on the initial observations, Z has covariance function σ 2 k0 . The kernel k0 is continuous and positive semidefinite, with k0 (x, x) = s2n0 (x) ≤ 1. We use Pxk0 and δm (k0 , X ) for the innovation norm and sequential separation radius obtained from (2.4) and (2.8) with k0 in place of k. The superscript distinguishes this power function from Px , which is computed with k. The diagonal bound gives δm (k0 , X ) ≤ 1. For every n ≥ n0 , orthogonal decomposition relative to Vn0 gives sn (x) = distHk (Ψ0 (x), span{Ψ0 (xn0 +1 ), . . . , Ψ0 (xn )}) , 6
(2.11)
where the span is {0} when n = n0 . Thus sn is the power function for k0 based on the post-initial query points xn0 +1 , . . . , xn . ⊥ Since µn0 = Πn0 f , the initial residual f − µn0 = Π⊥ n0 f belongs to Hk0 = Vn0 , and ∥µn0 ∥Hk ≤ ∥f ∥Hk ≤ B. The residual RKHS radius after the initial interpolation is therefore B0 := B 2 − ∥µn0 ∥2Hk
1/2
.
(2.12)
The minimum-norm interpolation formula gives † ∥µn0 ∥2Hk = z⊤ n0 Kn0 zn0 ,
so B0 is computable even when Kn0 is singular. Since Vn0 ⊆ Vn , the projection norms satisfy ∥µn ∥Hk ≥ ∥µn0 ∥Hk . Hence, for every n ≥ n0 , ∥f − µn ∥2Hk = ∥f ∥2Hk − ∥µn ∥2Hk ≤ B02 .
2.4
(2.13)
Expected improvement and simple regret
Because k is continuous, x 7→ k(·, x) is continuous in Hk , hence every f ∈ Hk is continuous. Compactness therefore ensures that a minimizer x⋆ exists. Let f ⋆ := f (x⋆ ) = minx∈X f (x). Define the best observed value mn and the simple regret rn for n ≥ n0 by rn := mn − f ⋆ .
mn := min zi , 1≤i≤n
(2.14)
Since f ⋆ ≤ mn+1 ≤ mn , simple regret is nonincreasing: 0 ≤ rn+1 ≤ rn ,
n ≥ n0 .
(2.15)
Define, for n ≥ n0 , In : X −→ [0, ∞),
In (x) := (mn − f (x))+ ,
u+ := max{u, 0}.
(2.16)
This is the improvement that would be realized by querying the candidate point x. At a global minimizer, In equals the current simple regret. At the next selected point, it equals the decrease in simple regret: In (x⋆ ) = rn ,
In (xn+1 ) = (mn − zn+1 )+ = mn − mn+1 = rn − rn+1 .
(2.17)
Conditioning the Gaussian-process model (2.1) on the observed history Dn := ((xi , zi ))ni=1 gives the Gaussian predictive distribution Z(x) | Dn ∼ N µn (x), σ 2 s2n (x) . (2.18) Let En [·] := E[· | Dn ] denote posterior expectation. Following Jones et al. (1998, Equation (14)), the EI sampling criterion for minimization after n evaluations is EIn (x) := En (mn − Z(x))+ . (2.19) Let Φ and ϕ denote the standard normal distribution function and density, and put τ (z) := zΦ(z) + ϕ(z). Since τ ′ (z) = Φ(z) and τ ′′ (z) = ϕ(z) > 0, the function τ is increasing and strictly convex. Using (2.18), the closed form is σs (x) τ mn − µn (x) , s (x) > 0, n n σsn (x) EIn (x) = (2.20) (mn − µn (x))+ , sn (x) = 0. 7
Continuity of x 7→ k(·, x) implies that µn and sn are continuous. The expression in (2.20) is continuous in the pair (mn − µn (x), sn (x)), including at points where sn (x) = 0. Consequently, EIn is continuous on X , and compactness ensures that it attains its maximum. The selected point need not maximize EI exactly. We assume instead that there is an η ∈ (0, 1], independent of n, such that EIn (xn+1 ) ≥ η sup EIn (x),
n ≥ n0 .
(2.21)
x∈X
We call (2.21) the weak-EI condition.
2.5
Consistency and density
We call an EI trajectory consistent if rn → 0. Its query points are dense in X if {xn , n ≥ 1} = X . Simple-regret consistency does not imply that the query points are dense. The consistency and density results discussed in this subsection are recorded for completeness and insight. They are not used in the quantitative bounds that follow. The compactness proof in Appendix A adapts the argument of Vazquez and Bect (2010a, Lemma 12) to establish lim inf EIn (xn+1 ) = 0. n→∞
The lower EI bound in Lemma 3.1 at a minimizer, the selection condition (2.21), and monotonicity of simple regret then imply rn → 0. Corollary 4.7 in Subsection 4.4 gives a second proof by applying Lemma 2.1 to the continuous residual kernel k0 and then using Theorem 4.4. Definition 2.2 (No-empty-ball property). Following Vazquez and Bect (2010a, Definition 3), the kernel k has the no-empty-ball (NEB) property on X if, for every sequence (xi )i≥1 ⊂ X and every x ∈ X , P(x1 ,...,xn ) (x) −→ 0
⇐⇒
x ∈ {xi , i ≥ 1}.
(2.22)
Continuity of k implies P(x1 ,...,xn ) (x) → 0 whenever x ∈ {xi , i ≥ 1}. The NEB property also requires the converse. The Matérn kernels considered below have the NEB property on every compact X , whereas the squared-exponential kernel fails it when X has nonempty interior (Vazquez and Bect, 2010b). In dimension one, Yarotsky (2013, Theorem 1) proves this failure for stationary kernels whose spectral densities decay at least exponentially. When k has the NEB property, Vazquez and Bect (2010a, Theorem 6 and Remark 8) proved that every exact EI policy generates a dense sequence of query points in X for every f ∈ Hk . Theorem 2.3 extends this result to weak-EI policies. Theorem 2.3 (Density under the NEB property). If k has the NEB property, then every fixed-prior EI trajectory satisfying (2.21) is dense in X . Proof. See Appendix A.
8
3
EI comparison and one-step regret bound
3.1
Scalar EI comparison
The Cauchy–Schwarz inequality, the power-function identity (2.6), and the residual-norm bound (2.13) give, for every n ≥ n0 and x ∈ X , |f (x) − µn (x)| ≤ B0 sn (x).
(3.1)
Set a := B0 /σ. The scalar comparison below depends on B0 and σ only through this dimensionless ratio. Define, for n ≥ n0 and a candidate point x with sn (x) > 0, the standardized gaps mn − µn (x) mn − f (x) u := , t := . (3.2) σsn (x) σsn (x) By (3.1), |u − t| ≤ a. Moreover, In (x) = σsn (x) t+ and EIn (x) = σsn (x) τ (u).
(3.3)
We now seek affine bounds of the form κIn (x) ≤ EIn (x) ≤ In (x) + D σsn (x),
κ, D ≥ 0.
Using In (x) = σsn (x) t+ and (3.3), these bounds follow if κt+ ≤ τ (u) ≤ t+ + D
for every u, t ∈ R with |u − t| ≤ a.
(3.4)
For a > 0, we construct the coefficient κ in the lower bound κt+ ≤ τ (u) from the tangent to τ through (−a, 0). A tangent at abscissa z passes through (−a, 0) when τ (z) = (z + a)τ ′ (z), or equivalently ϕ(z) = aΦ(z). With h := ϕ/Φ, this equation becomes h(z) = a. The ratio h satisfies τ (z) > 0, h′ (z) = −h(z){z + h(z)} < 0, z + h(z) = Φ(z) and, as z increases from −∞ to +∞, h(z) decreases strictly from +∞ to 0. Lemma 3.1 (Upper and lower bounds for EI). Let za be the unique solution of h(z) = a when a > 0. Define, for a ≥ 0, ( 1, a = 0, κa := (3.5) Φ(za ), a > 0. For every n ≥ n0 and x ∈ X , max In (x) − B0 sn (x), κa In (x) ≤ EIn (x) ≤ In (x) + τ (a) σsn (x).
(3.6)
Proof. Fix n ≥ n0 and x ∈ X , and write s = sn (x). Suppose first that s > 0, and use the standardized gaps u, t from (3.2). For the upper bound, if t ≤ 0, then In (x) = 0 and u ≤ a, so EIn (x) ≤ τ (a) σs. If t > 0, then d {τ (t + a) − t} = Φ(t + a) − 1 ≤ 0. dt 9
Together with u ≤ t + a and monotonicity of τ , this gives EIn (x) ≤ σs τ (t + a) ≤ In (x) + τ (a) σs. When In (x) = 0, the two lower bounds follow from nonnegativity of EI. Suppose now that In (x) > 0, so t > 0. The identity τ (z) = z + τ (−z), the nonnegativity of τ , and the inequality u ≥ t − a give EIn (x) ≥ In (x) − B0 s. For the multiplicative lower bound, if a = 0, then u = t and τ (u) = τ (t) ≥ t. If a > 0, convexity of τ , whose derivative is Φ, and tangency at za give τ (t − a) ≥ τ (za ) + Φ(za )(t − a − za ) = Φ(za )t = κa t. Since u ≥ t − a and τ is nondecreasing, this proves EIn (x) ≥ κa In (x). If s = 0, (3.1) gives µn (x) = f (x), and the degenerate predictive distribution gives EIn (x) = In (x). This proves (3.6). The constants κa and τ (a) are optimal in (3.4). For a > 0, h(−a) − a =
τ (−a) > 0. Φ(−a)
Since h is decreasing and h(za ) = a, this gives za > −a. Hence a + za > 0. The pair (u, t) = (za , a + za ) satisfies |u − t| = a and attains equality in the multiplicative lower bound. When a = 0, the pairs (u, t) = (t, t) with t > 0 satisfy the constraint in (3.4) and τ (t) ϕ(t) = Φ(t) + −→ 1 t t
as t → ∞.
Thus the lower inequality in (3.4) cannot hold with κ > 1. The pair (u, t) = (a, 0) satisfies |u − t| = a and attains equality in the upper bound. Therefore κa is the largest value of κ, and τ (a) is the smallest value of D, for which (3.4) holds. The map a 7→ κa is nonincreasing, whereas a 7→ τ (a) is increasing. Moreover, as a → ∞, h(za ) = a implies za → −∞, and hence κa = Φ(za ) → 0. Bull (2011, Lemma 8) proves analogous bounds for an unknown constant mean integrated under a flat prior.
3.2
One-step regret bound
Proposition 3.2 (One-step regret bound). Define q := 1 − ηκa ∈ [0, 1),
C := στ (a) > 0.
(3.7)
For every n ≥ n0 , if the selected point xn+1 satisfies (2.21), then rn+1 ≤ qrn + Csn (xn+1 ).
(3.8)
Proof. The multiplicative lower bound in (3.6) at a global minimizer and the additive upper bound at the selected point, together with (2.17) and (2.21), give ηκa rn ≤ EIn (xn+1 ) ≤ rn − rn+1 + στ (a)sn (xn+1 ). Rearranging proves (3.8). 10
For n ≥ n0 with rn > 0, the one-step regret bound (3.8) gives strict regret decrease whenever Csn (xn+1 ) < (1 − q)rn . Otherwise, the right-hand side of (3.8) is at least rn , and (2.15) gives rn+1 ≤ rn . For T > n0 , the values vn+1 = sn (xn+1 ), n0 ≤ n < T , are the post-initial selected-point innovation norms. For 1 ≤ j ≤ T − n0 , Lemma 4.2 bounds their jth largest value by δj (k0 , X ). Remark 3.3 (Uniform constants). The initial values f (x1 ), . . . , f (xn0 ) enter the constants q and C through B0 in (2.12). Define qB := 1 − ηκB/σ ,
CB := στ (B/σ).
(3.9)
Since a = B0 /σ ≤ B/σ, the monotonicity of a 7→ κa and a 7→ τ (a) gives q ≤ qB < 1 and C ≤ CB . Since rn and sn (xn+1 ) are nonnegative, qrn + Csn (xn+1 ) ≤ qB rn + CB sn (xn+1 ). Thus (3.8) remains valid when q, C are replaced by qB , CB . The constants qB and CB depend only on B, σ, and η. (Appendix B uses both lower bounds in (3.6) to derive the refined one-step regret bound (B.1), which involves both sn (xn+1 ) and sn (x⋆ ) for a minimizer x⋆ .)
4
Ranked innovation norms and regret bounds
The separation radii of k bound those of k0 , which in turn bound the ranked selected-point innovation norms. The one-step regret bound (3.8) then yields finite-budget bounds and simple-regret consistency.
4.1
Separation radii after the initial design
By (2.11), the normalized posterior standard deviations at the post-initial selected points are successive innovation norms for k0 . Sections 5 and 6 give quantitative bounds for the separation radii of k. Lemma 4.1 (Residual-kernel separation radii). For every m ≥ 1, δm (k0 , X ) ≤ δm (k, X ).
(4.1)
Proof. Recall from (2.10) that k0 (x, y) = ⟨Ψ0 (x), Ψ0 (y)⟩Hk . Write, for an ordered tuple x = (x1 , . . . , xm ), x0 := ∅ and xj := (x1 , . . . , xj ) for 1 ≤ j ≤ m. Since k0 (·, x) = Ψ0 (x) and Hk0 carries the norm inherited from Hk , for 1 ≤ j ≤ m, 0 Pxkj−1 (xj ) = distHk (Ψ0 (xj ), span{Ψ0 (xi ), i < j}) .
Thus the distances defining δm (k0 , X ) may be computed in Hk . Since Ψ0 (x) = Π⊥ n0 k(·, x), span{Ψ0 (xi ), i < j} = Π⊥ n0 Vxj−1 . The projector Π⊥ n0 is a contraction, so ⊥ distHk Π⊥ k(·, x ), Π V ≤ distHk k(·, xj ), Vxj−1 . x j n0 n0 j−1 Taking the minimum over j and then the supremum over tuples proves (4.1). Thus bounds for δm (k, X ) also apply to δm (k0 , X ). The inequality can be strict because Π⊥ n0 may shorten these distances by removing components in Vn0 , the span generated by the initial design. 11
4.2
Ranked selected-point innovation norms
The following lemma bounds the jth largest normalized posterior standard deviation among the post-initial selected points. Lemma 4.2 (Bounds for the ranked selected-point innovation norms). Let T > n0 and write N := T − n0 . Set, for 1 ≤ i ≤ N , vei := vn0 +i = sn0 +i−1 (xn0 +i ).
(4.2)
Let v[1] ≥ · · · ≥ v[N ] be the nonincreasing rearrangement of ve1 , . . . , veN . Then v[j] ≤ δj (k0 , X ) ≤ δj (k, X ),
1 ≤ j ≤ N.
(4.3)
Proof idea. Fix j and list chronologically the indices of the j largest post-initial innovation norms. At each of these indices, the span generated by all earlier post-initial query points contains the span generated by the earlier points in this j-point subsequence. Each selected innovation norm is therefore at most the corresponding successive innovation norm of the subsequence. The smallest selected value is v[j] . Taking minima and using the definition of δj gives v[j] ≤ δj (k0 , X ). Lemma 4.1 gives the second inequality in (4.3). Appendix C.1 gives the complete proof. In particular, for 1 ≤ m ≤ N and ε ≥ 0, if δm (k0 , X ) ≤ ε, then at most m − 1 of the post-initial values vn0 +1 , . . . , vT can exceed ε.
4.3
Finite-budget bounds
Over a finite horizon, the positions of the smallest post-initial innovation norms are known only retrospectively. The following lemma expresses the recursion as a minimum over subsets of indices. Define, for q ∈ [0, 1), C > 0, and v ≥ 0, the map Fv : [0, ∞) → [0, ∞) by Fv (u) := min{u, qu + Cv}.
(4.4)
Lemma 4.3 (Recursion along a subsequence). Let N ≥ 1, and let u0 , . . . , uN and v1 , . . . , vN be nonnegative numbers such that ui ≤ ui−1 ,
ui ≤ qui−1 + Cvi ,
1 ≤ i ≤ N,
where q ∈ [0, 1) and C > 0. Given U0 ≥ u0 , define Ui := min{Ui−1 , qUi−1 + Cvi },
1 ≤ i ≤ N.
(4.5)
Then ui ≤ Ui for every i. Write each nonempty subset S ⊆ {1, . . . , N } as S = {i1 < · · · < i|S| }. Then |S| X |S| |S|−h UN = min q U0 + C q v ih , (4.6) S⊆{1,...,N }
h=1
where the expression in braces is interpreted as U0 when S = ∅. Proof idea. The map Fv is nondecreasing, so induction gives ui ≤ Ui . At each step, (4.5) takes either the first or the second branch of the minimum. The indices at which it takes the second branch form a subset S, and expanding those affine steps gives the expression in braces in (4.6). Induction on i gives the minimum over all subsets. Appendix C.2 gives the complete proof. 12
Theorem 4.4 (Finite-budget bound). Let (rn )n≥n0 be any nonnegative nonincreasing sequence satisfying, for fixed q ∈ [0, 1) and C > 0, rn+1 ≤ qrn + Cvn+1 ,
n ≥ n0 .
(4.7)
Let T > n0 , put N := T − n0 , and let v[1] ≥ · · · ≥ v[N ] be the decreasing rearrangement of the post-initial selected-point innovation norms vn0 +1 , . . . , vT . Let (δm (k0 , X ))m≥1 be the sequential separation radii of the residual kernel k0 on X . Set M := N − L + 1 for 1 ≤ L ≤ N . Then L−1 X L rT ≤ q rn0 + C q j v[M +j] j=0 L
≤ q rn0 + C
L−1 X
(4.8) j
q δM +j (k0 , X ).
j=0
Consequently, rT ≤ q L rn0 + C
1 − qL δM (k0 , X ). 1−q
(4.9)
Proof idea. Apply the subset formula in Lemma 4.3 to the chronological positions of the L smallest post-initial innovation norms. At every other position, use rn+1 ≤ rn instead of (4.7), so only these L innovation norms appear inP the iterated bound. The rearrangement j inequality bounds the weighted selected values by L−1 j=0 q v[M +j] . Lemma 4.2 then replaces each ranked innovation norm by δM +j (k0 , X ), giving (4.8). Monotonicity of the separation radii gives (4.9). Appendix C.3 gives the complete proof. Remark 4.5. When q = 0, taking L = 1 in (4.9) and using regret monotonicity gives rT ≤ min{rn0 , CδT −n0 (k0 , X )}. Application to fixed-prior EI. For fixed-prior EI, (2.15), Proposition 3.2, and (2.7) verify the hypotheses of Theorem 4.4. For every f ∈ Hk with ∥f ∥Hk ≤ B, Remark 3.3 shows that (3.8) remains valid with qB , CB . The theorem therefore applies with these constants to every fixed-prior EI trajectory satisfying (2.21). In (4.9), increasing L makes the contraction term q L rn0 nonincreasing, but decreases M = N − L + 1 and makes δM (k0 , X ) nondecreasing. Section 6 chooses L for polynomial and stretched-exponential decay of the separation radii.
4.4
Consistency from the finite-budget bound
Corollary 4.6 (Consistency from decay of the separation radii). Suppose that δm (k0 , X ) → 0. If (rn ) satisfies the hypotheses of Theorem 4.4, then rT −→ 0
(T → ∞).
Proof. Let T ≥ n0 + 2, put N := T − n0 , take L = ⌊N/2⌋, and set M := N − L + 1. As T → ∞, both L and M tend to infinity, and q L → 0 because 0 ≤ q < 1. The assumed decay of the separation radii and (4.9) give rT ≤ q L rn0 +
C δM (k0 , X ) −→ 0. 1−q
13
Corollary 4.7 (Consistency of EI). For every fixed-prior EI trajectory satisfying (2.21), rn −→ 0. Proof. By (2.15), Proposition 3.2, and (2.7), the simple-regret sequence and selectedpoint innovation norms satisfy the hypotheses of Theorem 4.4. The residual kernel k0 is continuous, so Lemma 2.1 gives δm (k0 , X ) → 0. Corollary 4.6 therefore gives rn → 0. For quantitative bounds, Lemma 4.1 shows that it suffices to bound δm (k, X ). Section 5 obtains such bounds from Gram determinants and Kolmogorov widths.
5
From Kolmogorov widths to sequential separation radii
5.1
From innovation norms to Gram determinants
The determinant and width bounds in this section do not use the Euclidean structure of X . We therefore let D be a nonempty set and k : D × D → R a positive-semidefinite kernel. We use the innovation and separation-radius notation of (2.4) and (2.8), with D in place of X . For an ordered tuple x = (x1 , . . . , xm ) ∈ Dm , the Gram matrix in Hk of the evaluation representers k(·, x1 ), . . . , k(·, xm ) is m Kx := ⟨k(·, xi ), k(·, xj )⟩Hk i,j=1 = [k(xi , xj )]m (5.1) i,j=1 . Applying Gram–Schmidt orthogonalization, without normalization, to the ordered evaluation representers produces their successive innovations. These vectors are orthogonal, and the Gram determinant is the product of their squared norms. The minimum of the innovation norms is therefore at most their geometric mean, det(Kx )1/(2m) . Li and Siegel (2024, Lemma 2.1) use the same identity to bound products of successive distances, and Santin et al. (2024) use it to bound kernel Gram determinants. Lemma 5.1 (Gram determinants and innovation norms). Let D be nonempty and let k : D × D → R be positive semidefinite. For every integer m ≥ 1, with Kx as in (5.1), δm (k, D) ≤ sup det(Kx )1/(2m) .
(5.2)
x∈Dm
Proof. Fix x = (x1 , . . . , xm ) ∈ Dm . At each j = 1, . . . , m, write ιj := ι(x1 ,...,xj−1 ) (xj ) for the innovation of k(·, xj ), that is, its component orthogonal to the span of the preceding evaluation representers. Since each ιj equals k(·, xj ) minus a linear combination of those representers, the transformation from k(·, x1 ), . . . , k(·, xm ) to (ι1 , . . . , ιm ) is unit triangular. The corresponding Gram matrices are congruent through a unittriangular matrix and hence have the same determinant, even when the representers are linearly dependent. The innovations ιj are mutually orthogonal, and ∥ιj ∥Hk = P(x1 ,...,xj−1 ) (xj ). Therefore m m Y Y 2 det Kx = ∥ιj ∥2Hk = P(x1 ,...,xj−1 ) (xj ) . (5.3) j=1
j=1
The minimum of nonnegative numbers is at most their geometric mean. Hence min P(x1 ,...,xj−1 ) (xj ) ≤ det(Kx )1/(2m) .
1≤j≤m
Taking the supremum over x ∈ Dm proves (5.2). 14
5.2
From Kolmogorov widths to Gram eigenvalues
When {k(·, x), x ∈ D} is compact in Hk , the packing argument gives the qualitative conclusion δm (k, D) → 0. We use Kolmogorov widths for quantitative bounds. The Kolmogorov widths (Kolmogorov, 1936) of the set of evaluation representers of k are dm (k, D) := inf sup distHk k(·, x), V , m = 0, 1, 2, . . . . (5.4) V ⊂Hk x∈D dim V ≤m
p In particular, d0 (k, D) = supx∈D k(x, x). For compact subsets of a Hilbert space, Binev et al. (2011, Section 2) formulate weak greedy approximation through a lower-triangular matrix. DeVore et al. (2013, Theorem 3.2) use this representation to give a product inequality for successive weak-greedy approximation errors in terms of Kolmogorov widths. Wenzel et al. (2023, Theorem 1) give a product inequality for the successive innovation norms along any sequential design. In the proof of Lemma 5.2, each ij < j is the approximation dimension used for the jth Gram eigenvalue. These dimensions may be chosen separately before the eigenvalue bounds are multiplied. Lemma 5.2 (Gram determinants and Kolmogorov widths). Let D be nonempty, let k : D × D → R be positive semidefinite, and suppose that supx∈D k(x, x) < ∞. For every integer m ≥ 1 and every choice of approximation dimensions i1 , . . . , im satisfying 0 ≤ ij < j, one has δm (k, D) ≤ sup det(Kx )1/(2m) ≤
x∈Dm Y m r j=1
1/m m di (k, D) . j − ij j
(5.5)
In particular, ij = ⌊j/2⌋ gives 1/(2m)
δm (k, D) ≤ sup det(Kx )
≤
√
2e
Y m
x∈Dm
1/m d⌊j/2⌋ (k, D) .
(5.6)
j=1
Proof. See Appendix D.2.
5.3
Polynomial and stretched-exponential width decay
Corollary 5.3 (Separation-radius decay from Kolmogorov widths). Suppose that k(x, x) ≤ 1 on D. 1. If, for some A, α > 0, dm (k, D) ≤ Am−α ,
m ≥ 1,
(5.7)
then there is Cw > 0, depending on A, α, such that δm (k, D) ≤ Cw m−α ,
m ≥ 1.
(5.8)
2. Let 0 < γ ≤ 1. If, for some A, b > 0, dm (k, D) ≤ A exp{−bmγ log(em)},
m ≥ 1,
(5.9)
then, for every 0 < b′ < b/(1 + γ), there is A′ > 0 such that δm (k, D) ≤ A′ exp{−b′ mγ log(em)}, Here A′ may depend on A, b, γ, b′ but not on m. 15
m ≥ 1.
(5.10)
Proof. See Appendix D.3. We choose the dimensions ij in the widths dij (k, D) differently in the two cases. For polynomial widths, ij = ⌊j/2⌋ keeps the geometric mean of the prefactors in (5.5) bounded independently of m and yields δm (k, D) = O(m−α ). For the stretched-exponential √ bound (5.10), choosing ij = j − 1 gives the prefactor m, and m−1
1 X γ mγ log m i log(ei) ∼ , m 1+γ
m → ∞.
i=1
√ The factor m and the o(mγ log m) remainder are absorbed by the positive difference b/(1 + γ) − b′ .
6
Rates for Matérn and squared-exponential kernels
6.1
From polynomial decay of the separation radii to regret
Proposition 6.1 (Regret from polynomial decay of the separation radii). Suppose that, for some A > 0, α > 0, β ≥ 0, and all sufficiently large m, δm (k0 , X ) ≤ Am−α {log(em)}β . Then, along every fixed-prior EI trajectory satisfying (2.21), rT = O N −α (log N )β , N = T − n0 −→ ∞.
(6.1)
(6.2)
For fixed f , the implied constant and the starting index may depend on A, α, β, rn0 , q, C and on the rank from which (6.1) holds. If f ranges over the ball {h ∈ Hk : ∥h∥Hk ≤ B}, the implied constant and the starting index can instead be chosen uniformly in f . This uniform choice may depend on B, σ, η, A, α, β, k, X , the initial design, and the rank from which (6.1) holds. Proof. See Appendix E.1. Proof idea. Apply Theorem 4.4 with L = 1 when q = 0. When 0 < q < 1, choose L = O(log N ) so that q L = O(N −α−1 ) and M = N − L + 1 ∼ N . Substitution in (4.9) gives (6.2).
6.2
Matérn kernels
Proposition 6.2 (Matérn separation-radius decay). Let kν be the restriction to a nonempty compact X ⊂ Rd of a stationary isotropic Matérn kernel on Rd with unit diagonal, fixed lengthscale, and smoothness ν > 0. Then δm (kν , X ) = O m−ν/d . (6.3) Proof. See Appendix E.2.
16
Proof idea. For a bounded open cube Q containing X , let kν,Q be the restriction to Q × Q of the Matérn kernel on Rd appearing in the proposition. Its spectral density is comparable at high frequencies to ∥ω∥−d−2ν . Schaback and Wendland (2002, Theorem 3.2) therefore give a power-function estimate of order hν , where h is the fill distance. For every m ≥ 1, one can choose a Cartesian grid in Q with at most m points and fill distance O(m−1/d ). Its kernel translates span a space of dimension at most m. Restricting this space from Q to X does not increase its approximation error and gives dm (kν , X ) ≤ dm (kν,Q , Q) = O(m−ν/d ).
(6.4)
Applying Corollary 5.3 to (6.4) gives the separation-radius bound (6.3). Only the auxiliary cube must satisfy the interior cone condition, so no boundary regularity of X is required. Combining (6.3) with Lemma 4.1 and Proposition 6.1 gives the following regret rate. Theorem 6.3 (Simple-regret rate for EI with a Matérn kernel). In the setting of Section 2, let k = kν be as in Proposition 6.2. Then, along every fixed-prior EI trajectory satisfying (2.21), rT = O N −ν/d , N = T − n0 −→ ∞. (6.5) For fixed B, X , k, σ, η, and initial design, neither the implied constant nor the starting index depends on the choice of f ∈ Hk with ∥f ∥Hk ≤ B. Proof. See Appendix E.3.
6.3
From stretched-exponential decay of the separation radii to regret
Proposition 6.4 (Regret from stretched-exponential decay of the separation radii). Suppose that, for some A, b > 0 and all sufficiently large m, δm (k0 , X ) ≤ A exp{−bm1/d log m}.
(6.6)
Let T > n0 , put N := T − n0 , and define ψd (N ) := min{N, N 1/d log(eN )}. Then there are constants A′ , b′ > 0 and an integer N0 ≥ 1 such that, for every fixed-prior EI trajectory satisfying (2.21), rT ≤ A′ exp{−b′ ψd (N )},
(6.7)
for every N ≥ N0 . We write an ≍ bn if there are constants 0 < c ≤ C < ∞ such that cbn ≤ an ≤ Cbn for all sufficiently large n. Here ψ1 (N ) = N , whereas, for d ≥ 2 and all sufficiently large N , ψd (N ) = N 1/d log(eN ) ≍ N 1/d log N . For fixed f , A′ , b′ and N0 may depend on A, b, d, rn0 , q, C and on the rank from which (6.6) holds. If f ranges over the ball {h ∈ Hk : ∥h∥Hk ≤ B}, the constants A′ , b′ and the starting index N0 can instead be chosen uniformly in f . This uniform choice may depend on B, σ, η, A, b, d, k, X , the fixed initial design, and the rank from which (6.6) holds. Proof. See Appendix E.4. Proof idea. Apply Theorem 4.4 with L = 1 when q = 0. When 0 < q < 1, take L = ⌊N/2⌋ for d = 1 and L = ⌈N 1/d log(eN )⌉ for d ≥ 2. Then q L rn0 and δN −L+1 (k0 , X ) are both O(exp[−cψd (N )]) for some c > 0. Equation (4.9) gives (6.7). 17
6.4
Squared-exponential kernels
Proposition 6.5 (Squared-exponential separation-radius decay). Let X ⊂ Rd be nonempty and compact, and fix ϱ > 0. Let k be the restriction to X × X of the unit-diagonal isotropic squared-exponential kernel on Rd defined by ∥x − y∥2 (x, y) 7−→ exp − . 2ϱ2 There are constants A, b > 0 such that, for all sufficiently large m, δm (k, X ) ≤ A exp −bm1/d log m .
(6.8)
When d = 1, the following sharper estimate holds, with log 0 = −∞: log δm (k, X ) 1 ≤− . m log m 2 m→∞
lim sup
(6.9)
Proof. See Appendix E.5. Proof idea. Enclose X in a cube Q. For a finite nonempty set Y ⊂ Q with small fill distance hY,Q , Wendland (2004, Theorem 11.22 and Equation (11.11)) gives a uniform power-function bound on Q of the form A0 exp{−b0 | log hY,Q |/hY,Q } for some A0 , b0 > 0. Taking Y to be a Cartesian grid with at most m points gives hY,Q = O(m−1/d ), and the span of its kernel translates has dimension at most m. The restriction h 7→ h|X from the RKHS of the squared-exponential kernel on Q to Hk is contractive and maps this span to a subspace of dimension at most m. The restricted subspace has worst-case approximation error over X no larger than the original subspace over Q. Hence the power-function estimate gives dm (k, X ) = O(exp[−c′ m1/d log m]). The compact set X need not have interior or a regular boundary. Corollary 5.3 then gives (6.8). In dimension one, Yarotsky (2013, Theorem 2) gives a conditional-variance bound, uniform over X , after conditioning on any set of distinct sites. Taking square roots and applying the resulting power-function bound to the final innovation norm of each tuple of distinct points gives (6.9). A tuple with a repeated point has a zero innovation. Theorem 6.6 (Simple-regret rates for EI with a squared-exponential kernel). In the setting of Section 2, let k be the squared-exponential kernel in Proposition 6.5. Let T > n0 and put N := T − n0 . 1. In every dimension d ≥ 1, for every fixed-prior EI trajectory satisfying the weak-EI condition (2.21), there are A′ , b′ > 0 such that rT ≤ A′ exp{−b′ min{N, N 1/d log(eN )}},
(6.10)
for all sufficiently large N . 2. When d = 1 and EI is maximized exactly, for every 0 < b′′ < 1/2 there is A′′ > 0 such that rT ≤ A′′ exp{−b′′ N log(eN )}, (6.11) for every N ≥ 1. For fixed B, X , k, σ, η, and the initial design, the constants and starting index in (6.10) do not depend on the choice of f ∈ Hk with ∥f ∥Hk ≤ B. When d = 1 and EI is maximized exactly, the same holds for A′′ when b′′ is fixed. 18
Proof idea. Combining (6.8) with Lemma 4.1 and Proposition 6.4 gives (6.10). In dimension one, interpolation makes EI zero at queried sites, whereas strict positive definiteness and (2.20) make it positive at unqueried sites. Hence the exact EI policy selects an unqueried site whenever one remains. Proposition E.5 then bounds supx∈X sT −1 (x). With η = 1, (B.1) gives rT ≤ (B0 + C) sup sT −1 (x), x∈X
which yields (6.11). Proof. See Appendix E.6. Remark 6.7 (Why the transfer bound loses a logarithmic factor in dimension one). Suppose d = 1 and 0 < q < 1, and choose 1 ≤ L ≤ N in the transfer bound. Write M := N −L+1 for the separation-radius index. The separation-radius term is bounded by A exp(−bM log M ) in (6.6), whereas the contraction term is q N −M +1 . The proof of Proposition 6.4 used L = ⌊N/2⌋ to establish the rate. Balancing the two terms more closely by choosing M ≍ N/ log(eN ) and L = N − M + 1 in (4.9) gives an upper bound O(e−cN ). Thus (4.9) loses the factor log(eN ) because q L decreases only geometrically in L. The refinement for exact maximization of EI in (6.11) combines the power-function bound for every set of distinct sites in dimension one with a bound for sn (x⋆ ).
7
Minimax comparison
The preceding upper bounds hold on every compact domain. The minimax comparisons below assume that X has nonempty interior.
7.1
Minimax classes
In the minimax notation below, N ≥ 1 denotes the total number of evaluations, including the initial design. Let AN be the class of deterministic algorithms X N = (X1 , . . . , XN ), where X1 ∈ X is chosen as part of the algorithm and, for 2 ≤ j ≤ N , Xj : (X × R)j−1 −→ X is Borel measurable. For an objective function f , the query points are defined recursively by X1 (f ) = X1 and j−1 Xj (f ) = Xj Xi (f ), f (Xi (f )) i=1 , 2 ≤ j ≤ N. The class A∞ consists of infinite deterministic sequential algorithms X = (Xn )n≥1 whose truncation (X1 , . . . , XN ) belongs to AN for every N ≥ 1. A deterministic method with N evaluations consists of X N ∈ AN and a Borel finalrecommendation rule bN : (X × R)N −→ X . X For an objective function f , write bN x bN (f ) := X
N Xj (f ), f (Xj (f )) j=1 .
The recommendation x bN (f ) need not be one of the query points.
19
Definition 7.1 (Deterministic minimax loss). For B > 0, the deterministic minimax loss is det sup f x bN (f ) − min f (x) . (7.1) RN (B; k, X ) := inf X N ∈AN ∥f ∥ ≤B Hk bN Borel X
x∈X
Let AeN be the class of sequential strategies X for which each query point is a measurable function of the preceding query-value history and of possible internal randomness that is independent of f . After N exact evaluations, the strategy returns a recommendation x bN ∈ X that is a measurable function of the complete history and of the same internal randomness. The recommendation need not be one of the query points. Write EX, f for expectation over that randomness when the objective function is f . The class Ae∞ consists of infinite randomized sequential strategies whose truncation after N evaluations belongs to AeN for every N ≥ 1. Definition 7.2 (Randomized minimax loss). For B > 0, the corresponding minimax expected loss is rand RN (B; k, X ) := inf sup EX, f f (b xN ) − min f (x) . (7.2) eN ∥f ∥H ≤B X∈A k
Worst-case regret of exact EI.
x∈X
Let X EI = (XnEI )n≥1
denote a measurable exact EI policy in A∞ with the fixed initial design, as provided by Proposition F.1. Define, for N ≥ n0 and B > 0, its worst-case regret by EI EI RN (B; k, X ) := sup min f Xj (f ) − min f (x) . (7.3) ∥f ∥Hk ≤B
1≤j≤N
x∈X
This is the worst-case loss of the deterministic method that follows the EI query rules and recommends the earliest query point at which the best observed value is attained.
7.2
Matérn kernels
Theorem 7.3 (Minimax optimality for Matérn kernels). Let X ⊂ Rd be compact with nonempty interior, let kν be the Matérn kernel in Proposition 6.2, and let B > 0. There are constants cM , CM > 0 such that, for all sufficiently large N , det EI −ν/d cM N −ν/d ≤ Rrand . N (B; kν , X ) ≤ RN (B; kν , X ) ≤ RN (B; kν , X ) ≤ CM N
(7.4)
Proof. The classical bump-function argument used in the proof of Bull (2011, Theorem 1) applies to kν and gives the lower bound for Rrand in (7.4). Every deterministic method in the N det definition of RN belongs to AeN by using no internal randomness. Hence Rrand N (B; kν , X ) ≤ det RN (B; kν , X ). Consider the method that uses the first N decision rules of X EI and recommends the earliest query point at which the best observed value is attained. This recommendation is a Borel function of the finite history, and its loss equals the regret in (7.3). ThereEI fore Rdet N (B; kν , X ) ≤ RN (B; kν , X ). Finally, the uniform bound in Theorem 6.3 gives EI (B; k , X ) = O((N − n )−ν/d ) = O(N −ν/d ), since n is fixed. RN ν 0 0
20
7.3
Squared-exponential kernels
Theorem 7.4 (Minimax optimality for the squared-exponential kernel). Let X ⊂ Rd be compact with nonempty interior, let k be as in Proposition 6.5, and let B > 0. There are positive constants c1 , c2 , C1 , C2 such that, for all sufficiently large N , EI 1/d c1 exp{−C1 N 1/d log(eN )} ≤ Rdet log(eN )}. N (B; k, X ) ≤ RN (B; k, X ) ≤ C2 exp{−c2 N (7.5) The constants c1 , C1 depend only on B, k, and X . The constants c2 , C2 may also depend on σ and the fixed initial design.
Proof idea. After restriction to a cube contained in int(X ) and rescaling to [0, 1]d , the metric-entropy estimate in Kühn (2011, Theorem 3), combined with Xu et al. (2024, Theorem 5.1), gives a lower bound on the number of evaluations required to make the simple regret computed from the best observed value smaller than a prescribed threshold. Appending the final recommendation of a deterministic method as the (N + 1)st query gives the lower bound for Rdet N in (7.5). For the upper bound, use the measurable exact EI policy and recommend the earliest query point at which the best observed value is attained. Theorem 6.6 gives the required bound, using (6.10) when d ≥ 2 and (6.11) when d = 1. Proof. See Subsection F.2 for the complete proof.
8
Discussion
Fixed-prior EI trajectories generated by weak-EI policies are simple-regret consistent for every continuous positive-semidefinite kernel on a nonempty compact domain (Corollary 4.7). For Matérn kernels, their rate is N −ν/d for every ν > 0. When B > 0 and X has nonempty interior, Theorem 7.3 shows that the exact EI policy is minimax-rate optimal among deterministic methods whose final recommendation may be any point of X . These results answer the question that motivated this article by providing a complete description of the simple-regret behavior of fixed-prior EI for Matérn kernels. Although the squared-exponential kernel does not have the NEB property and exact EI trajectories need not be dense (Yarotsky, 2013, Theorem 3), Theorems 6.6 and 7.4 also show that the exact EI policy is minimax-rate optimal up to constants in the exponent among deterministic methods. The main idea is to represent each query point xi by its evaluation representer k(xi , ·) and thereby reduce the upper-bound analysis of EI to geometric approximation in Hk . The comparison between sequential separation radii and Kolmogorov widths is inspired by work on greedy approximation (Binev et al., 2011; DeVore et al., 2013; Wenzel et al., 2023). In the proof of Lemma 5.2, a subspace dimension in the Kolmogorov-width bound is chosen separately for each eigenvalue of the Gram matrix of an ordered tuple of evaluation representers. Lemma 4.2 bounds the ranked selected-point innovation norms over each finite horizon by the separation radii of k0 , and hence by those of k. The finite-budget argument in Theorem 4.4 applies the affine branch of the one-step regret bound at the evaluations with the smallest innovation norms and uses regret monotonicity at all remaining iterations. For both kernels, the estimates of dm (k, X ) follow from standard power-function estimates in scattered data approximation.
21
The analysis assumes exact observations and covariance parameters fixed independently of the observations. Noise and covariance parameters selected from the data lie outside its scope.
A
Consistency and density
The compactness argument of Vazquez and Bect (2010a, Lemma 12) yields a subsequence used in both the consistency and density proofs. Lemma A.1 (Vanishing EI along a subsequence). In the setting of Section 2, let (xi )i≥1 ⊂ X be any infinite sequence of query points, with the corresponding values of f observed exactly. Then there exist indices nj → ∞ such that EInj (xnj +1 ) −→ 0.
(A.1)
Proof. By compactness, there are x̄ ∈ X and strictly increasing indices (φj ) such that xφj → x̄. After discarding finitely many terms and reindexing the subsequence, we may assume φ1 − 1 ≥ n0 and put nj := φj − 1. For j ≥ 2, xφj−1 has already been observed at time nj . Hence snj (xnj +1 ) ≤ k(·, xφj ) − k(·, xφj−1 ) H −→ 0, k Inj (xnj +1 ) ≤ f (xφj−1 ) − f (xφj ) + −→ 0. The first inequality holds because k(·, xφj−1 ) ∈ Vnj . The second uses mnj ≤ f (xφj−1 ). Both right-hand sides tend to zero because xφj → x̄, the map x 7→ k(·, x) is continuous, and f is continuous. The upper bound in (3.6) then gives (A.1). Consequence for consistency. For a fixed-prior EI trajectory satisfying (2.21), the lower bound in (3.6) at a minimizer x⋆ and (2.21) give ηκa rn ≤ EIn (xn+1 ). Along the subsequence from Lemma A.1, the right-hand side tends to zero. Since ηκa > 0, rnj → 0. The nonnegative sequence (rn ) is nonincreasing, so rn → 0. Density under the NEB property. Because sn (x) = P(x1 ,...,xn ) (x), the density proof applies the NEB property to the original kernel k. Proof of Theorem 2.3. Suppose that the query points are not dense. Then there is an x ∈ X \ {xi , i ≥ 1}. The NEB property gives sn (x) ̸→ 0. Since the spaces Vn are nested, the normalized posterior standard deviations sn (x) are nonincreasing in n. Hence 0 < inf sj (x) ≤ sn (x) ≤ 1, j≥n0
n ≥ n0 .
The RKHS error estimate (3.1) bounds µn (x) uniformly in n, and continuity of f on the compact set X bounds mn . Hence the pairs mn − µn (x), sn (x) lie in a compact subset of R × (0, 1]. With u = mn − µn (x) and s = sn (x), the positive-s branch of (2.20) is the function u (u, s) 7−→ σs τ . σs 22
This map is continuous and strictly positive, so it has a positive minimum on the compact subset containing these pairs. Consequently inf n≥n0 EIn (x) > 0. The selection condition (2.21) then implies that EIn (xn+1 ) is bounded away from zero, contradicting Lemma A.1.
B
Using the normalized posterior standard deviation at a minimizer
Lemma B.1 (Refined one-step regret bound). Let x⋆ be a minimizer of f . For every n ≥ n0 , if the selected point xn+1 satisfies (2.21), then rn+1 ≤ min {qrn , (1 − η)rn + ηB0 sn (x⋆ )} + Csn (xn+1 ).
(B.1)
Proof. Since In (x⋆ ) = rn , the two lower bounds in (3.6) give EIn (x⋆ ) ≥ max{rn − B0 sn (x⋆ ), κa rn }. At the selected point, In (xn+1 ) = rn − rn+1 . The upper bound in (3.6) and the selection condition (2.21) therefore give η max{rn − B0 sn (x⋆ ), κa rn } ≤ rn − rn+1 + Csn (xn+1 ). Rearranging gives rn+1 ≤ min {(1 − η)rn + ηB0 sn (x⋆ ), (1 − ηκa )rn } + Csn (xn+1 ). Since q = 1 − ηκa , this is (B.1). The proof of Theorem 4.4 uses only the qrn branch. Using the second branch in that argument would require additional control of sn (x⋆ ), whereas Lemma 4.2 bounds only the selected-point standard deviations. The proof for exact EI when d = 1 uses a uniform bound on the power function to bound sn (x⋆ ).
C
Ranked innovation norms and finite-budget bounds
C.1
Proof of the ranked innovation-norm bound
Proof of Lemma 4.2. Fix 1 ≤ j ≤ N , and let Ij ⊆ {1, . . . , N }, with |Ij | = j, contain indices of the j largest values among ve1 , . . . , veN , with ties resolved arbitrarily. Enumerate this set in chronological order as Ij = {i1 < · · · < ij }. The chronological enumeration need not arrange the values (e vih )jh=1 in decreasing order. Put yh := xn0 +ih for 1 ≤ h ≤ j. Then span{Ψ0 (xn0 +i ) : 1 ≤ i < ih } ⊇ span{Ψ0 (yℓ ), 1 ≤ ℓ < h},
(C.1)
where the span on the right is {0} when h = 1. Equations (4.2) and (2.11), together with (C.1), give veih = distHk (Ψ0 (yh ), span{Ψ0 (xn0 +i ) : 1 ≤ i < ih }) ≤ distHk (Ψ0 (yh ), span{Ψ0 (yℓ ), 1 ≤ ℓ < h}) , 23
1 ≤ h ≤ j.
(C.2)
Taking the minimum over h in (C.2) and then using the definition of δj , with k0 (·, y) = Ψ0 (y) and Hk0 carrying the norm inherited from Hk , gives v[j] = min veih 1≤h≤j
≤ min distHk (Ψ0 (yh ), span{Ψ0 (yℓ ), 1 ≤ ℓ < h}) 1≤h≤j
≤ δj (k0 , X ). Lemma 4.1 completes (4.3).
C.2
Proof of the recursion along a subsequence
Proof of Lemma 4.3. The base case is u0 ≤ U0 . Suppose that ui−1 ≤ Ui−1 . The two assumed inequalities at index i give ui ≤ min{ui−1 , qui−1 + Cvi } = Fvi (ui−1 ). Because q ≥ 0, the map Fvi is nondecreasing. Hence ui ≤ Fvi (ui−1 ) ≤ Fvi (Ui−1 ) = Ui , which proves ui ≤ Ui for every i. Let S ⊆ {1, . . . , N } and set s := |S|. When s ≥ 1, list its elements as S = {j1 < · · · < js }. Define s X s A(S) := q U0 + C q s−h vjh , h=1
where the sum is zero when S = ∅. Thus A(∅) = U0 . We prove by induction on i that Ui =
min
A(S).
S⊆{1,...,i}
For i = 0, the only subset is ∅, so the right-hand side is A(∅) = U0 . Suppose that the claim holds at index i − 1, and partition the subsets of {1, . . . , i} according to whether they contain i. For every S ′ ⊆ {1, . . . , i − 1}, the definition gives A(S ′ ∪ {i}) = qA(S ′ ) + Cvi . Since q ≥ 0, the induction hypothesis therefore yields min A(S) = min min A(S ′ ), S ′ ⊆{1,...,i−1}
S⊆{1,...,i}
min
S ′ ⊆{1,...,i−1}
′
A(S ∪ {i})
= min{Ui−1 , qUi−1 + Cvi } = Ui . Taking i = N proves (4.6).
C.3
Proof of the finite-budget bound
Proof of Theorem 4.4. As in Lemma 4.2, reindex the post-initial innovation norms from 1 to N by setting vei := vn0 +i = sn0 +i−1 (xn0 +i ), 1 ≤ i ≤ N, 24
and let v[1] ≥ · · · ≥ v[N ] be their decreasing rearrangement. Set ui := rn0 +i , so that uN = rT . The hypotheses of Theorem 4.4 give ui ≤ ui−1 ,
ui ≤ qui−1 + Ce vi ,
1 ≤ i ≤ N.
Define the auxiliary sequence (Ui )N i=0 by (4.5), starting from U0 := u0 = rn0 . The inequalities above verify the hypotheses of Lemma 4.3, which gives uN ≤ UN and the minimization formula (4.6) for UN . Choose the indices of the L smallest values among ve1 , . . . , veN , resolving ties arbitrarily. Write them as 1 ≤ i1 < · · · < iL ≤ N and set S⋆ := {i1 , . . . , iL }. The sequence (e vih )L h=1 is in chronological order and, since M = N − L + 1, has decreasing rearrangement (v[M ] , v[M +1] , . . . , v[N ] ). The minimization in (4.6) ranges over every subset S, including S⋆ . Hence UN is at most the value obtained with S = S⋆ . Since |S⋆ | = L, this gives rT = uN ≤ UN ≤ q L rn0 + C
L X
q L−h veih .
h=1
Pairing the larger selected values with the larger weights maximizes the sum, so the largest selected value receives weight 1, the next largest weight q, and so on. Applying Lemma 4.2 to each v[M +j] then gives L X h=1
q
L−h
veih ≤
L−1 X
j
q v[M +j] ≤
j=0
L−1 X
q j δM +j (k0 , X ).
j=0
This proves (4.8). Since the separation radii are nonincreasing, L−1 X
j
q δM +j (k0 , X ) ≤ δM (k0 , X )
j=0
L−1 X
qj =
j=0
1 − qL δM (k0 , X ), 1−q
which proves (4.9).
D
Kolmogorov widths, Gram determinants, and separation radii
D.1
Operator form of the Eckart–Young theorem
Lemma D.1 (Eckart–Young identity). Let H be a real Hilbert space, let m ≥ 1 be an integer, and let S : Rm → H be linear. Denote the eigenvalues of S ∗ S, counted with multiplicity, by λ1 ≥ · · · ≥ λm ≥ 0. For a linear map A : Rm → H, its Hilbert–Schmidt norm is m X ∥A∥2HS := ∥Aeℓ ∥2H , ℓ=1 m m where (eℓ )ℓ=1 is the standard basis of R . For every integer 0 ≤ i ≤ m,
inf m
∥S − A∥2HS =
A:R →H linear rank(A)≤i
X
λℓ .
(D.1)
ℓ>i
The infimum is attained by truncating a singular-value decomposition of S after i terms. 25
Proof. If S = 0, the conclusion is immediate. Assume henceforth that S = ̸ 0. Let S := ran S, which is finite-dimensional and therefore closed, and let ΠS be its orthogonal projector. For every linear operator A : Rm → H, orthogonality of S and S ⊥ gives ∥S − A∥2HS = ∥S − ΠS A∥2HS + ∥(I − ΠS )A∥2HS .
(D.2)
Moreover, rank(ΠS A) ≤ rank(A). Hence the infimum in (D.1) is unchanged if it is restricted to operators whose range lies in S. If B ∈ Rp×m , with p ≤ m, let λ1 (B ⊤ B) ≥ · · · ≥ λm (B ⊤ B) ≥ 0 be the eigenvalues of ⊤ B B. With ∥·∥F denoting the Frobenius norm, the matrix Eckart–Young theorem (Eckart and Young, 1936) gives X e 2 = min ∥B − B∥ λℓ (B ⊤ B), 0 ≤ i ≤ m. (D.3) F e p×m B∈R e rank(B)≤i
ℓ>i
If B = U ΣV ⊤ is a singular-value decomposition, a minimizer is U Σi V ⊤ , where Σi retains the min{i, p} largest singular values and replaces the others by zero. Put p := dim S ≤ m, and choose orthonormal bases of Rm and S. In these bases, operators from Rm to S are represented by p × m matrices, and the Hilbert–Schmidt norm agrees with the Frobenius norm. If B is the matrix representing S, then B ⊤ B represents S ∗ S and has eigenvalues λ1 , . . . , λm . Applying (D.3) to B gives (D.1) and shows that the truncated singular-value decomposition attains the infimum.
D.2
Determinant bound from Kolmogorov widths
Proof of Lemma 5.2. Fix x = (x1 , . . . , xm ) ∈ Dm , and let Sx : Rm → Hk be the synthesis operator m X Sx c := cℓ k(·, xℓ ). ℓ=1
Write λ1 (x) ≥ · · · ≥ λm (x) ≥ 0 for the eigenvalues of Kx = Sx∗ Sx . Given an integer 0 ≤ i < m and ε > 0, choose, by (5.4), a subspace V ⊂ Hk with dim V ≤ i whose uniform approximation error is less than di (k, D) + ε, and let ΠV be the orthogonal projector onto V . Since ΠV Sx has rank at most i, Lemma D.1 gives X ℓ>i
λℓ (x) ≤ ∥Sx − ΠV Sx ∥2HS =
m X
distHk k(·, xℓ ), V
2
≤ m{di (k, D) + ε}2 .
(D.4)
ℓ=1
Letting ε ↓ 0 and using the nonincreasing order of the eigenvalues gives, for all integers 0 ≤ i < j ≤ m, j X (j − i)λj (x) ≤ λℓ (x) ≤ mdi (k, D)2 . (D.5) ℓ=i+1
Moreover, the determinant is the product of these eigenvalues, so Y 1/(2m) m det(Kx )1/(2m) = λj (x) . j=1
Substitute i = ij into the preceding eigenvalue bound and take square roots for each j. Multiplying the resulting inequalities over j = 1, . . . , m and taking the mth root gives Y 1/m m r m 1/(2m) det(Kx ) ≤ di (k, D) . j − ij j j=1
26
Taking the supremum over x ∈ Dm and using (5.2) proves (5.5). Taking ij = ⌊j/2⌋ gives r 2m 1/2 λj (x) ≤ d (k, D). j ⌊j/2⌋ Multiplying these inequalities and using m! ≥ (m/e)m proves (5.6). The inequalities remain valid when an eigenvalue or a width is zero. In particular, Kx need not be invertible.
D.3
From width decay to separation-radius decay
Proof of Corollary 5.3. Substitute (5.7) into (5.6) for m ≥ 2. Since d0 (k, D) ≤ 1 and ⌊j/2⌋ ≥ j/3 for j ≥ 2, we obtain √ δm (k, D) ≤ 2e A(m−1)/m 3α (m!)−α/m ≤ Cw m−α . (D.6) The bound m! ≥ (m/e)m allows Cw to be chosen independently of m. The case m = 1 follows from δ1 (k, D) = d0 (k, D) ≤ 1, after increasing Cw if necessary. To prove (5.10), set ij = j − 1 in (5.5). Then (m−1 )1/m Y √ δm (k, D) ≤ m di (k, D) . (D.7) i=0
If δm (k, D) = 0, the inequality in (5.10) holds at that m. Otherwise, the product in (D.7) is positive, so di (k, D) > 0 for every 0 ≤ i < m and logarithms may be taken. Since d0 (k, D) ≤ 1, (5.9) gives m−1
log δm (k, D) ≤
1 m−1 b X γ log m + log A − i log(ei). 2 m m
(D.8)
i=1
Moreover, an integral comparison gives m−1 X
iγ log(ei) =
i=1
and hence
m−1
1 X γ i log(ei) = m i=1
m1+γ log m + O(m1+γ ), 1+γ
1 +O 1+γ
1 log m
mγ log m.
Let 0 < b′ < b/(1 + γ), and choose eb with b′ < eb < b/(1 + γ).
(D.9)
(D.10)
Substituting (D.10) into
(D.8) gives, for all sufficiently large m such that δm (k, D) > 0, log δm (k, D) ≤ −eb mγ log m. For all sufficiently large m, eb log m ≥ b′ log(em). Hence δm (k, D) ≤ exp{−b′ mγ log(em)} for those m. Since δm (k, D) ≤ δ1 (k, D) = d0 (k, D) ≤ 1, increasing A′ if necessary extends (5.10) to the finitely many smaller values of m.
E
Separation-radius decay and regret rates
This appendix proves Propositions 6.1 and 6.4 and the Matérn and squared-exponential separation-radius estimates used in Section 6. The bounds valid in every dimension use Cartesian-grid approximations. The sharper one-dimensional squared-exponential argument instead combines the conditional-variance estimate proved by Yarotsky (2013, Theorem 2) with (B.1). 27
E.1
Regret from polynomial decay of the separation radii
Proof of Proposition 6.1. By (2.15), (2.7), and the one-step regret bound (3.8), the simpleregret sequence and the selected-point innovation norms satisfy the hypotheses of Theorem 4.4. If q = 0, take L = 1, so M = N . Theorem 4.4 then gives rT ≤ CδN (k0 , X ), and the result follows from (6.1). Suppose 0 < q < 1. With N = T − n0 , choose α+1 L := log(eN ) , M := N − L + 1. − log q For all sufficiently large N , this choice satisfies 1 ≤ L ≤ N . Moreover, L = O(log N ), M = N − O(log N ), and q L ≤ (eN )−α−1 . Theorem 4.4 and (6.1) give rT ≤ q L rn0 +
CA M −α {log(eM )}β . 1−q
The bound q L ≤ (eN )−α−1 gives q L rn0 = O(N −α−1 ). Since M = N −L+1 = N −O(log N ), we have M ∼ N , and therefore M −α {log(eM )}β = O N −α (log N )β . Combining these estimates, rT = O N −α (log N )β , which proves (6.2). For every objective function f satisfying (2.2), Remark 3.3 and (2.7) give rn+1 ≤ qB rn + CB vn+1 , where 0 ≤ qB < 1 and CB > 0 are independent of f . Moreover, the reproducing property, (2.3), and (2.2) give rn0 ≤ 2B. The residual kernel k0 depends only on the kernel and the initial sites. Thus (6.1), including its starting rank, is independent of f . If qB = 0, the preceding argument applies with L = 1. If 0 < qB < 1, use α+1 L= log(eN ) . − log qB Together with rn0 ≤ 2B, these choices give (6.2) with an implied constant and a starting index that do not depend on the choice of f ∈ Hk with ∥f ∥Hk ≤ B.
E.2
Matérn separation-radius decay
Lemma E.1 (Matérn power functions and widths). Let kν be a stationary isotropic Matérn kernel on Rd , normalized to have unit diagonal, with fixed lengthscale and smoothness ν > 0. Let Q ⊂ Rd be a bounded open cube and set kν,Q := kν |Q×Q . If Y ⊂ Q is finite and nonempty, define its fill distance and power function by hY,Q := sup min∥x − y∥, x∈Q y∈Y
PYQ (x) := distHkν,Q (kν,Q (·, x), span{kν,Q (·, y), y ∈ Y}) . (E.1)
There are constants CQ , h0 > 0 such that, for every finite nonempty Y ⊂ Q, sup PYQ (x) ≤ CQ hνY,Q
whenever hY,Q ≤ h0 .
(E.2)
x∈Q
Consequently, for every nonempty compact X ⊂ Rd , there is AX < ∞ such that dm (kν , X ) ≤ AX m−ν/d ,
m ≥ 1.
(E.3)
The constant AX depends only on the kernel parameters and on the cube chosen to contain X . No regularity of ∂X is required. 28
Proof. Write kν (x, y) = Φν (x − y). There are constants c0 , c1 > 0, depending only on the kernel parameters, such that the Matérn spectral density is b ν (ω) = c0 c1 + ∥ω∥2 −(ν+d/2) . Φ (E.4) The spectral density is everywhere positive, so Φν is strictly positive definite (Wendland, 2004, Corollary 6.9). As ∥ω∥ → ∞, b ν (ω) ≍ ∥ω∥−d−2ν . Φ
(E.5)
To bound PYQ , we apply the power-function estimate proved by Schaback and Wendland b (2002, Theorem 3.2). The theorem assumes Φ(ω) ≍ ∥ω∥−d−s∞ , and comparison with (E.5) gives s∞ = 2ν. We use the theorem with m = 0, where m denotes the order of conditional positive definiteness. For m = 0, no polynomial moment conditions are imposed, and the condition reduces to strict positive definiteness, established above for Φν . A bounded open cube satisfies the required interior cone condition. The power function in the theorem equals the RKHS residual norm in (E.1). Hence the theorem gives s /2
∞ PYQ (x) ≤ CQ hY,Q = CQ hνY,Q
for every x ∈ Q once hY,Q ≤ h0 , proving (E.2). Now fix a nonempty compact X ⊂ Rd and choose a bounded open cube Q of side length aQ > 0 containing X . For each integer n ≥ 1, partition Q into nd congruent cubes and let Yn be their centers. Then √ aQ d d . (E.6) |Yn | = n , hYn ,Q ≤ 2n ′ := Y d 1/d /2, the Given m ≥ 1, put nm := ⌊m1/d ⌋ and Ym nm . Since nm ≤ m and nm ≥ m space ′ VmQ := span{kν,Q (·, y), y ∈ Ym } √ −1/d ′ ,Q ≤ aQ has dimension at most m, while hYm dm . Hence, for all sufficiently ′ large m, (E.2), applied with Y = Ym , gives √ sup distHkν,Q kν,Q (·, x), VmQ ≤ CQ (aQ d)ν m−ν/d . (E.7) x∈Q
Let kν,X := kν |X ×X , and let RQ,X : Hkν,Q −→ Hkν,X ,
RQ,X g := g|X .
By the restriction theorem (Aronszajn, 1950, Section 5), ∥RQ,X g∥Hkν,X ≤ ∥g∥Hkν,Q ,
g ∈ Hkν,Q .
Moreover, RQ,X kν,Q (·, x) = kν,X (·, x) for x ∈ X . The space Wm := RQ,X VmQ has dimension ′ need not belong to X . Their restricted kernel translates at most m. The grid points in Ym belong to Hkν,X and span Wm , which is admissible in (5.4). The interior cone condition is imposed on the auxiliary cube Q, while X may have empty interior or an irregular boundary. For every x ∈ X , distHkν,X kν,X (·, x), Wm = inf RQ,X kν,Q (·, x) − v H Q v∈Vm
29
kν,X
≤ inf ∥kν,Q (·, x) − v∥Hk Q v∈Vm
ν,Q
= distHkν,Q kν,Q (·, x), VmQ . Taking the supremum over x ∈ X and using (E.7) proves (E.3) for all sufficiently large m. Since kν (x, x) = 1, one has dm (kν , X ) ≤ d0 (kν , X ) = 1. Increasing AX if necessary gives (E.3) for the finitely many smaller ranks. Proof of Proposition 6.2. Lemma E.1 gives (E.3). Since kν (x, x) = 1, the polynomial case of Corollary 5.3, with α = ν/d, then yields (6.3).
E.3
Simple-regret rate for EI with a Matérn kernel
Proof of Theorem 6.3. By Lemma 4.1, δm (k0 , X ) ≤ δm (kν , X ), so δm (k0 , X ) = O(m−ν/d ). Proposition 6.1, with α = ν/d, β = 0, and qB , CB , then gives (6.5). The constants qB , CB depend on B, σ, η. The implied constant and the rank from which (6.3) holds depend only on the fixed kernel and domain. Since rn0 ≤ 2B, the implied constant and starting index in (6.5) do not depend on the choice of f ∈ Hk with ∥f ∥Hk ≤ B.
E.4
Regret from stretched-exponential decay of the separation radii
Lemma E.2 (Choice of L for stretched-exponential decay). Assume (6.6) and fix q ∈ [0, 1). Recall from Proposition 6.4 that ψd (N ) = min{N, N 1/d log(eN )}.
(E.8)
e eb > 0 and an integer N1 ≥ 1 such that, for every integer N ≥ N1 , There are constants A, the choices q = 0, 1, L = ⌊N/2⌋, M := N − L + 1, (E.9) 0 < q < 1, d = 1, 1/d ⌈N log(eN )⌉, 0 < q < 1, d ≥ 2, satisfy 1 ≤ L ≤ N and e exp{−ebψd (N )}. q L + δM (k0 , X ) ≤ A
(E.10)
The constants and N1 depend only on A, b, d, q and the rank from which (6.6) holds. Proof. If q = 0, (E.9) gives L = 1 and M = N . Thus q L = 0, and the left-hand side of (E.10) is δN (k0 , X ). When d = 1, (E.8) gives ψ1 (N ) = N , and, for all sufficiently large N , δN (k0 , X ) ≤ A exp{−bN log N } ≤ A exp{−bN } = A exp{−bψ1 (N )}. When d ≥ 2, for all sufficiently large N , (E.8) gives ψd (N ) = N 1/d log(eN ), and log N ≥ 1 2 log(eN ). Hence δN (k0 , X ) ≤ A exp{−bN 1/d log N } ≤ A exp{− 2b ψd (N )}. This proves (E.10) when q = 0.
30
Suppose 0 < q < 1. When d = 1, (E.9) gives L = ⌊N/2⌋ and M = N − L + 1. For all sufficiently large N , L≥
N , 3
M≥
N , 2
log M ≥
1 log(eN ), 2
and hence q L ≤ e−| log q|N/3 ,
δM (k0 , X ) ≤ A exp{− 4b N log(eN )}.
Since ψ1 (N ) = N and log(eN ) ≥ 1, setting c1 := min{| log q|/3, b/4} > 0 gives q L + δM (k0 , X ) ≤ (1 + A) exp{−c1 ψ1 (N )}. When d ≥ 2, (E.9) gives L = ⌈N 1/d log(eN )⌉ and M = N − L + 1. For all sufficiently large N , this choice satisfies 1 ≤ L ≤ N . Moreover, M ≥ N/2 and log M ≥ 21 log(eN ). Therefore q L ≤ exp{−| log q|N 1/d log(eN )},
M 1/d log M ≥ 2−1−1/d N 1/d log(eN ).
By (6.6) and the identity ψd (N ) = N 1/d log(eN ), setting c2 := min{| log q|, b 2−1−1/d } > 0 gives q L + δM (k0 , X ) ≤ (1 + A) exp{−c2 ψd (N )}. These estimates prove (E.10). Proof of Proposition 6.4. By (2.15), (2.7), and the one-step regret bound (3.8), the simpleregret sequence and selected-point innovation norms satisfy the hypotheses of Theorem 4.4. For the values of L and M in (E.9), (4.9) gives C rT ≤ rn0 q L + δM (k0 , X ) 1−q C e exp{−ebψd (N )}. ≤ rn0 + A 1−q This proves (6.7). Remark 3.3 gives q ≤ qB < 1 and C ≤ CB for every f ∈ Hk with ∥f ∥Hk ≤ B. Since rn ≥ 0 and sn (xn+1 ) ≥ 0, the one-step regret bound remains valid with qB , CB in place of q, C. Moreover, (2.3) and (2.2) give rn0 ≤ 2B. For the fixed initial design, (6.6), including its starting rank, is independent of f . Applying Lemma E.2 with q = qB and (4.9) with qB , CB gives constants and a starting index independent of f .
E.5
Squared-exponential separation-radius decay
Lemma E.3 (Power-function bound for the squared-exponential kernel on a cube). Let Q ⊂ Rd be a closed cube of positive side length, fix ϱ > 0, and let ∥x − y∥2 kQ (x, y) := exp − , x, y ∈ Q. 2ϱ2
31
Define, for every finite nonempty Y ⊂ Q, hY,Q := sup min∥x − y∥, x∈Q y∈Y
VYQ := span{kQ (·, y), y ∈ Y}.
There are constants c0 > 0 and h0 ∈ (0, 1), depending only on d, ϱ, Q, such that | log hY,Q | Q , sup distHkQ kQ (·, x), VY ≤ exp −c0 hY,Q x∈Q
(E.11)
(E.12)
whenever hY,Q ≤ h0 . Proof. The spectral density of the squared-exponential kernel on Rd is positive everywhere, so its restriction kQ is strictly positive definite (Wendland, 2004, Corollary 6.9). Hence, for every u ∈ HkQ , there is a unique IY u ∈ VYQ that agrees with u on Y. To apply Wendland (2004, Theorem 11.22) to the squared-exponential kernel, take the auxiliary function 2 g(t) := e−t/(2ϱ ) (t ≥ 0), because kQ (x, y) = g(∥x − y∥2 ). For every integer j ≥ 0, 2
|g (j) (t)| = (2ϱ2 )−j e−t/(2ϱ ) ≤ (2ϱ2 )−j
(t ≥ 0).
Thus the derivative hypothesis in Theorem 11.22 is satisfied. The theorem and Equation (11.11) give constants c0 > 0 and h0 ∈ (0, 1), depending only on d, ϱ, Q, for which every u ∈ HkQ satisfies | log hY,Q | ∥u∥HkQ , (E.13) sup |u(x) − IY u(x)| ≤ exp −c0 hY,Q x∈Q whenever hY,Q ≤ h0 . For x ∈ Q, the power-function identity gives distHkQ kQ (·, x), VYQ = sup |u(x) − IY u(x)|.
(E.14)
∥u∥Hk ≤1 Q
Taking the supremum over x ∈ Q in (E.14) and applying (E.13) proves (E.12). Lemma E.4 (Squared-exponential Kolmogorov widths). Let X ⊂ Rd be nonempty and compact, and fix ϱ > 0. Let k : X × X → R be the restriction of the squared-exponential kernel ∥x − y∥2 (x, y) 7−→ exp − . 2ϱ2 There are constants Aw , bw > 0 such that dm (k, X ) ≤ Aw exp{−bw m1/d log(em)},
m ≥ 1.
(E.15)
The constants depend only on d, ϱ, and the cube chosen to contain X . Proof. Choose a closed cube Q ⊂ Rd of side length aQ > 0 containing X , and define ∥x − y∥2 kQ (x, y) := exp − , x, y ∈ Q. 2ϱ2 Let c0 > 0 and h0 ∈ (0, 1) be the constants given by Lemma E.3 for this cube. Given m ≥ 1, write nm := ⌊m1/d ⌋ and denote by Ym the centers of the ndm congruent subcubes obtained by partitioning Q. Define VYQm := span{kQ (·, y), y ∈ Ym }. 32
Then |Ym | = ndm ≤ m, nm ≥ m1/d /2, and the fill distance of Ym in Q satisfies √ aQ d . hYm ,Q ≤ 2nm The map h 7→ | log h|/h is decreasing on (0, 1). Hence the bounds on nm and hYm ,Q imply that there is b1 > 0, depending only on d, ϱ, Q, such that hYm ,Q ≤ h0 ,
c0
| log hYm ,Q | ≥ b1 m1/d log(em), hYm ,Q
(E.16)
for all sufficiently large m. Since dim VYQm ≤ m, applying Lemma E.3 with Y = Ym and using (E.16) gives dm (kQ , Q) ≤ sup distHkQ kQ (·, x), VYQm ≤ exp{−b1 m1/d log(em)}. (E.17) x∈Q
As in the proof of Lemma E.1, restriction from Q to X is contractive and does not increase subspace dimensions. Therefore, dm (k, X ) ≤ dm (kQ , Q). Thus (E.15) holds with bw = b1 for all sufficiently large m. Since k(x, x) = 1, one has dm (k, X ) ≤ d0 (k, X ) = 1. Increasing Aw if necessary gives (E.15) for the finitely many smaller ranks. Proposition E.5 (Power-function bound for the squared-exponential kernel at distinct sites in dimension one). Let X ⊂ R be nonempty and compact, and fix ϱ > 0. Let k : X × X → R be given by (x − y)2 k(x, y) = exp − . 2ϱ2 For every 0 < b < 1/2, there is a constant Ab ≥ 1, depending only on b, ϱ, and X , such that, for every integer K ≥ 1 and every collection of pairwise distinct sites x1 , . . . , xK ∈ X , sup P(x1 ,...,xK ) (x) ≤ Ab exp{−bK log(eK)}.
(E.18)
x∈X
Moreover, with log 0 = −∞, log δm (k, X ) 1 ≤− . m log m 2 m→∞
lim sup
Proof. Choose cX ∈ R and aX > 0 such that X ⊂ [cX − aX , cX + aX ], and set x e :=
x − cX , aX
x ei :=
xi − c X , aX
γ :=
ϱ2 . 2a2X
(E.19)
All the rescaled points lie in [−1, 1]. With the Fourier convention of Yarotsky (2013), Equation (16) with a = γ and spectral exponent 2 gives the spectral density gbγ (t) := exp(−γt2 ). Its inverse Fourier transform is 2 r Z π h gγ (h) = exp(−γt2 )eith dt = exp − , γ 4γ R 33
h ∈ R.
Since 4γa2X = 2ϱ2 , the rescaling in (E.19) gives r x − cX y − cX γ − . gγ k(x, y) = π aX aX g
Given a finite tuple y of real numbers, write Py γ for the power function associated with the kernel (s, t) 7→ gγ (s − t). Its square is the conditional variance of a centered Gaussian process with this covariance function after conditioning at the sites in y. Conditional variances scale linearly with the covariance function. Thus r 2 2 γ g P(x1 ,...,xK ) (x) = x) . (E.20) P(exγ1 ,...,exK ) (e π For all sufficiently large K and all distinct points x e, x e1 , . . . , x eK , Yarotsky (2013, Theorem 2 and Equation (14)), applied to gbγ (t) = exp(−γt2 ), gives 2 g P(exγ1 ,...,exK ) (e x) ≤ exp{Fγ (K) + 2K}
K Y
|e x−x ei |2 ,
(E.21)
i=1
where 2K + 1 Fγ (K) := 2
log
2K + 1 2γ
− 2 log K − 1
= −K log K + Oγ (K).
(E.22)
Here Oγ (K) denotes a quantity whose absolute value is bounded by Cγ K, where Cγ may depend on γ but not on K. Since |e x−x ei | ≤ 2, using (E.22) in (E.20) and (E.21) gives r 2 γ P(x1 ,...,xK ) (x) ≤ exp{Fγ (K) + 2K + K log 4} = exp{−K log K + Oγ (K)}. (E.23) π If x is one of the sites xi , then the power function is zero. The bound (E.23) therefore holds for every x ∈ X . Taking square roots shows that, for every 0p < b < 1/2, (E.18) holds with Ab = 1 for all sufficiently large K. Since P(x1 ,...,xK ) (x) ≤ k(x, x) = 1, choosing Ab ≥ 1 large enough also covers the finitely many smaller values of K. Now let (x1 , . . . , xm ) ∈ X m . If the tuple contains a repeated point, the innovation norm at the first repetition is zero. If the points are distinct and m ≥ 2, the minimum of the successive innovation norms is at most the final one, and (E.18) gives min P(x1 ,...,xj−1 ) (xj ) ≤ Ab exp{−b(m − 1) log(e(m − 1))}.
1≤j≤m
(E.24)
Taking the supremum over ordered tuples and including the repeated-point case gives, for m ≥ 2, δm (k, X ) ≤ Ab exp{−b(m − 1) log(e(m − 1))}. Dividing logarithms by m log m and then letting b ↑ 1/2 proves the second assertion. Proof of Proposition 6.5. Lemma E.4 gives (E.15). Since k(x, x) = 1, the stretchedexponential case of Corollary 5.3, with exponent 1/d, shows that, for every 0 < bδ < bw /(1 + 1/d), there is Aδ > 0 such that δm (k, X ) ≤ Aδ exp{−bδ m1/d log(em)},
m ≥ 1.
Here Aδ depends only on d, ϱ, the cube chosen to contain X , and the chosen bδ . Choosing any admissible bδ proves (6.8). When d = 1, the second assertion of Proposition E.5 gives (6.9). 34
E.6
Simple-regret rates for EI with a squared-exponential kernel
Proof for weak-EI policies. By Lemma 4.1, δm (k0 , X ) ≤ δm (k, X ). Thus (6.6) holds for k0 , with constants and a threshold rank independent of f . Proposition 6.4 then gives (6.10). The same constants and starting index apply to every f ∈ Hk with ∥f ∥Hk ≤ B. Proof for exact EI when d = 1. The Euclidean spectral density of the squared-exponential kernel is positive everywhere, so the kernel is strictly positive definite (Wendland, 2004, Corollary 6.9). At a previously queried site y, interpolation gives sn (y) = 0 and µn (y) = f (y), so EIn (y) = 0. At an unqueried site x, strict positive definiteness gives sn (x) > 0, and (2.20) gives EIn (x) > 0. The exact EI policy therefore selects an unqueried site whenever one exists. If every point of X has been queried by time T − 1, then rT = 0, so (6.11) holds. Otherwise, every post-initial point selected before xT is new. Let D0 := {x1 , . . . , xn0 } , ST −1 := {x1 , . . . , xT −1 }. Since the N − 1 post-initial points selected before xT are new, JN := |ST −1 | = D0 + N − 1 ≥ N. Repeated sites do not change the span of the evaluation representers, so sT −1 is the power function associated with the JN distinct sites in ST −1 . At time T − 1, equation (B.1) with η = 1, together with B0 ≤ B and C ≤ CB from Remark 3.3, gives rT ≤ min {qrT −1 , B0 sT −1 (x⋆ )} + CsT −1 (xT ) ≤ B0 sT −1 (x⋆ ) + CsT −1 (xT ) ≤ (B + CB ) sup sT −1 (x). x∈X
Proposition E.5 therefore gives, for every 0 < b′′ < 1/2, rT ≤ (B + CB )Ab′′ exp{−b′′ JN log(eJN )}. Since JN ≥ N , (6.11) follows with A′′ = (B + CB )Ab′′ .
F
Measurable policies and minimax bounds
F.1
Measurable exact EI policies
Proposition F.1 (Measurable exact EI policies). There is a measurable exact EI policy X = (Xn )n≥1 whose first n0 decisions are the fixed initial design and such that, for every f ∈ Hk , EIn Xn+1 (f ) = max EIn (x), n ≥ n0 . x∈X
Proof. For each n ≥ n0 , we construct an extension of EI to the whole history space that is Borel measurable in the history and continuous in the candidate point. A measurable selection of EI maximizers is a Borel decision rule that assigns an EI-maximizing candidate point to every history. The measurable-selection theorem then gives such rules. Together with the fixed initial decisions, they define the required policy. 35
Measurability of the posterior quantities. Let Hn := (X × R)n for each n ≥ n0 . Both Hn and X are complete separable metric spaces. A decision rule after n evaluations is a Borel map from Hn to X , even though some histories in Hn cannot occur when the objective function belongs to Hk and its values are observed exactly. We therefore extend the posterior formulas to all of Hn × X . Given h = ((x1 , z1 ), . . . , (xn , zn )) ∈ Hn , put zn := (z1 , . . . , zn )⊤ . The Gram matrix Kn = [k(xi , xj )]ni,j=1 and the best observed value mn = min1≤i≤n zi are continuous functions of the history in Hn . The map (h, x) 7→ kn (x) := (k(xi , x))ni=1 is continuous on Hn × X . For a real matrix A of fixed size, −1 ⊤ A† = lim A⊤ A + γI A . γ↓0
For each γ > 0, the map A 7→ (A⊤ A + γI)−1 A⊤ is continuous. Hence the Moore–Penrose inverse is Borel measurable as a pointwise limit of continuous matrix maps. We use the formulas involving Kn† in (2.5) to define µn and sn on Hn ×X . For each fixed x, µn (x) and sn (x) are Borel measurable functions of the history, and for each fixed history they are continuous in x. Thus these formulas define Borel extensions of the posterior mean and normalized posterior standard deviation. They agree with the posterior quantities when the history consists of exact observations of an objective function f ∈ Hk . Measurability of EI. At each history h ∈ Hn , use (2.20), with mn , µn , and sn given by the extensions above, to define x 7→ EIn (x). This agrees with posterior EI on histories arising from exact observations. The continuity stated after (2.20) makes EIn Borel measurable in the history for each fixed x and continuous in x for each fixed history. By the Carathéodory measurability theorem, separability of X then makes (h, x) 7→ EIn (x) jointly Borel measurable on Hn × X . Measurable selection of EI maximizers. Compactness of X ensures that EIn attains its maximum for every history. Applying Brown and Purves (1973, Corollary 1) to − EIn gives a Borel map from Hn to X whose value at each history maximizes EIn . Construction of the policy. Together with the fixed initial decisions, these maps define the required policy X.
F.2
Deterministic minimax bounds for the squared-exponential kernel
Covering numbers of a squared-exponential RKHS on the unit cube. Given a kernel k on Rd and a nonempty set D ⊂ Rd , write Hk,D for the RKHS of k|D×D . For a Hilbert space H and B ≥ 0, write BB (H) := {h ∈ H : ∥h∥H ≤ B}. When D is compact, write C(D) for the space of real-valued continuous functions on D, equipped with the sup norm. For d ≥ 1 and ϱ > 0, let kϱ be the squared-exponential kernel on Rd written in the form ∥u − v∥2 kϱ (u, v) := exp − , u, v ∈ Rd . 2ϱ2 Then Kühn (2011, Theorem 3) proves that the metric entropy (the logarithm of the sup-norm covering number) of B1 (Hkϱ ,[0,1]d ) at radius ε is of order {log(1/ε)}d+1 {log log(1/ε)}d as ε ↓ 0. We use only the lower estimate. The next lemma transfers that lower bound to the radius-B ball of Hkϱ ,X . 36
Lemma F.2 (Metric entropy of the squared-exponential RKHS ball). Let X ⊂ Rd be compact with nonempty interior, and fix ϱ, B > 0. Let N (BB (Hkϱ ,X ), ε, ∥·∥∞ ) be the supnorm covering number of this ball on X , and set Lε := log(B/ε). There are constants c > 0 and ε0 ∈ (0, B/(4e)) such that, for 0 < ε ≤ ε0 , log N (BB (Hkϱ ,X ), 4ε, ∥·∥∞ ) ≥ c
Ld+1 ε . (log Lε )d
(F.1)
Proof. Choose a closed cube Q = bQ + aQ [0, 1]d ⊂ int(X ),
aQ > 0.
Write ∥·∥∞,Q for the sup norm on Q. The RKHS extension and restriction theorems (Wendland, 2004, Theorems 10.46– 10.47) show that restriction from X to Q maps BB (Hkϱ ,X ) onto BB (Hkϱ ,Q ). Restricting a sup-norm cover on X therefore gives a cover on Q, so N (BB (Hkϱ ,Q ), ε, ∥·∥∞,Q ) ≤ N (BB (Hkϱ ,X ), ε, ∥·∥∞ ).
(F.2)
By homogeneity, N (BB (Hkϱ ,Q ), 4ε, ∥·∥∞,Q ) = N (B1 (Hkϱ ,Q ), 4ε/B, ∥·∥∞,Q ).
(F.3)
The similarity ϑQ (x) :=
x − bQ aQ
maps Q onto [0, 1]d . Put ϱ′ := ϱ/aQ . Then −1 kϱ ϑ−1 Q (u), ϑQ (v)
∥u − v∥2 = exp − = kϱ′ (u, v). 2(ϱ′ )2
The metric entropy estimate in Kühn (2011, Theorem 3) therefore applies to Hkϱ′ ,[0,1]d . Composition with ϑ−1 Q is an isometric isomorphism from Hkϱ ,Q onto Hkϱ′ ,[0,1]d and preserves the sup norm. It also maps C(Q) isometrically onto C([0, 1]d ), so arbitrary centers of covers ′ are transported by composition with ϑ−1 Q . Taking ε := 4ε/B, the covering number on the right-hand side of (F.3) is therefore the covering number at radius ε′ of B1 (Hkϱ′ ,[0,1]d ). Since log(1/ε′ ) = Lε − log 4, Kühn (2011, Theorem 3) bounds the logarithm of this covering d number below by a positive constant multiple of Ld+1 ε /(log Lε ) for all sufficiently small ε. Choose ε0 ∈ (0, B/(4e)) so that this bound holds whenever 0 < ε ≤ ε0 . Combining this estimate with (F.2)–(F.3) proves (F.1).
From metric entropy to a lower bound on the number of evaluations. Let H be an RKHS on Rd whose reproducing kernel is continuous on Rd × Rd and bounded above by one on X × X , where X is nonempty and compact. Fix B > 0, and write BB (H)|X := {f |X : f ∈ BB (H)}. Xu et al. (2024, Theorem 5.1) give constants c0 , ε1 > 0 such that, for every T ≥ 1 and 0 < ε ≤ ε1 , any algorithm X ∈ A∞ satisfying sup min g Xj (g) − min g(x) ≤ ε g∈BB (H)|X
1≤j≤T
x∈X
37
must satisfy T ≥ c0
log N (BB (H)|X , 4ε, ∥·∥∞ ) . log(B/ε)
(F.4)
Here c0 can be chosen independently of H, B, and X , whereas the threshold ε1 may depend on them. Lemma F.3 (Squared-exponential evaluation lower bound). Under the assumptions and notation of Lemma F.2, there are constants c′ , c′′ > 0 and ε∗ ∈ (0, ε0 ] such that, for every T ≥ 1 and 0 < ε ≤ ε∗ , any X T ∈ AT whose best observed value has worst-case simple regret at most ε over BB (Hkϱ ,X ) satisfies T ≥c
′ log N (BB (Hkϱ ,X ), 4ε, ∥·∥∞ )
Lε
′′
≥c
Lε log Lε
d .
Proof. The RKHS restriction theorem gives e e e BB (Hkϱ ,X ) = f |X : f ∈ Hkϱ ,Rd , ∥f ∥Hk ,Rd ≤ B = BB (Hkϱ ,Rd )|X . ϱ
(F.5)
(F.6)
Extend X T to an element of A∞ by querying a fixed point at every subsequent step. This leaves the first T query points and the best value observed among them unchanged. The kernel kϱ is continuous and bounded above by one on X × X . Hence both (F.4) and Lemma F.2 apply when 0 < ε ≤ ε∗ , where ε∗ := min{ε0 , ε1 }. Taking c′ := c0 and c′′ := c′ c proves both inequalities in (F.5). Proof of Theorem 7.4. Lower bound. Let ϱ be the lengthscale of k. Then Hk = Hkϱ ,X , so the ball in Lemma F.2 is the ball used in Theorem 7.4. Let c′′ be as in Lemma F.3, and let ε∗ be its threshold. Choose C1 > 0 such that ′′
c
C1 3
d >2
and set εN := B exp{−C1 N 1/d log(eN )}. Then LεN = C1 N 1/d log(eN ),
log LεN ≤ 3 log(eN )
for all sufficiently large N . Fix a deterministic method with query rules X N = (X1 , . . . , XN ) and Borel recommenbN . Append X bN as the (N + 1)st query. The resulting algorithm X ′ dation X N +1 ∈ AN +1 is given by ′ b Xj′ := Xj (1 ≤ j ≤ N ), XN +1 := XN . For every f ∈ BB (Hkϱ ,X ), min
1≤j≤N +1
bN (f ) − min f (x). f Xj′ (f ) − min f (x) ≤ f x x∈X
x∈X
38
(F.7)
Since εN → 0, one has εN ≤ ε∗ for all sufficiently large N . If the method had worst-case loss at most εN , Lemma F.3, applied with T = N + 1, would give ′′
N +1≥c
LεN log LεN
d
′′
≥c
C1 3
d N > 2N
for all sufficiently large N . This contradicts N + 1 ≤ 2N . Thus every deterministic method has worst-case loss greater than εN . Taking the infimum over the methods gives 1/d Rdet log(eN )}, N (B; k, X ) ≥ B exp{−C1 N
which is the lower bound in (7.5) with c1 = B. Upper bound. Consider the method that uses the first N decision rules of X EI and recommends the earliest query point at which the best observed value is attained. Its EI (B; k, X ), so worst-case loss is RN EI Rdet N (B; k, X ) ≤ RN (B; k, X ).
Theorem 6.6, applied with post-initial budget N − n0 , gives EI RN (B; k, X ) ≤ C2 exp{−c2 N 1/d log(eN )}
for some C2 , c2 > 0, using (6.10) when d ≥ 2 and (6.11) when d = 1. Since n0 does not depend on N , it changes only the constants. This proves the upper bound in (7.5).
G
Known continuous prior means
Setting and posterior formulas. Let µ0 ∈ C(X ) be a known prior mean, and consider the fixed prior GP(µ0 , σ 2 k). Let f0 := f − µ0 and assume f0 ∈ Hk ,
∥f0 ∥Hk ≤ B.
The finite-budget bounds in Theorem 4.4 and the upper bounds in Theorems 6.3 and 6.6 hold along every EI trajectory based on this prior and satisfying (2.21). The sharper one-dimensional squared-exponential rate requires exact maximization of EI. For n ≥ n0 , let ⊤ f0,n := zn − µ0 (x1 ), . . . , µ0 (xn ) = En f0 . Then
µn (x) = µ0 (x) + kn (x)⊤ Kn† f0,n = µ0 (x) + (Πn f0 )(x),
x ∈ X,
f − µn = (I − Πn )f0 . The Moore–Penrose expression remains valid with repeated sites because f0,n ∈ Range(Kn ). For a given sequence of query points, µ0 affects the posterior mean but not the posterior covariance or sn , although it may change the points selected by EI. The definitions of mn and EIn remain unchanged. Continuity of k and µ0 implies the continuity of f, µn , sn , and EIn . Compactness of X then gives a minimizer of f and a maximizer of EIn .
39
EI comparison and finite-budget bounds. After the initial design, fb0,n0 := Πn0 f0 is the minimum-norm interpolant of the centered initial data. Since ∥fb0,n0 ∥Hk ≤ ∥f0 ∥Hk ≤ B, define 1/2 (f ) B 0 := B 2 − ∥fb0,n ∥2 . 0
0
Hk
(f )
Since Vn0 ⊆ Vn , orthogonal projection and the definition of B0 0 give, for n ≥ n0 , (f )
∥(I − Πn )f0 ∥Hk ≤ ∥(I − Πn0 )f0 ∥Hk ≤ B0 0 . The reproducing property, the orthogonality of (I − Πn )f0 to Vn , and the Cauchy–Schwarz inequality then give (f )
|f (x) − µn (x)| = [(I − Πn )f0 ](x) ≤ B0 0 sn (x),
x ∈ X.
(G.1)
With the constant η ∈ (0, 1] from (2.21), define (f )
B 0 a := 0 , σ
q := 1 − ηκa ∈ [0, 1),
C := στ (a) > 0,
where τ (z) = zΦ(z) + ϕ(z) and κa is defined by (3.5). The proof of Lemma 3.1, with (G.1) in place of (3.1), gives, for every n ≥ n0 and x ∈ X , (f ) max In (x) − B0 0 sn (x), κa In (x) ≤ EIn (x) ≤ In (x) + Csn (x).
(G.2)
Consider an EI trajectory satisfying (2.21), and let x⋆ be a global minimizer. Since (f ) In (x⋆ ) = rn and In (xn+1 ) = rn − rn+1 , the proof of Lemma B.1, with B0 0 in place of B0 , gives n o (f ) rn+1 ≤ min qrn , (1 − η)rn + ηB0 0 sn (x⋆ ) + Csn (xn+1 ). (G.3) In particular, rn+1 ≤ qrn + Csn (xn+1 ).
(G.4)
By (2.7), sn (xn+1 ) = vn+1 , so Theorem 4.4 gives the finite-budget bounds. Since k0 is continuous, Lemma 2.1 and Corollary 4.6 also give rn → 0. Kernel-specific rates. Lemma 4.1 transfers the separation-radius estimates in Section 6 to k0 , yielding the Matérn and squared-exponential rates under (2.21). For the fixed prior mean µ0 , these rates hold uniformly over µ0 + {h ∈ Hk , ∥h∥Hk ≤ B}. (f )
Indeed, B0 0 ≤ B, so Remark 3.3 gives q ≤ qB < 1 and C ≤ CB . The diagonal normalization (2.3) gives ∥f0 ∥∞ ≤ B, and hence rn0 ≤ 2B + sup µ0 (x) − inf µ0 (x). x∈X
x∈X
40
Exact one-dimensional squared-exponential rate. When d = 1, k is squaredexponential, and EI is maximized exactly, the rate in (6.11) also holds for a known continuous prior mean. Interpolation gives EIn (x) = 0 at queried sites, whereas strict positive definiteness makes the predictive distribution nondegenerate and EIn (x) > 0 at unqueried sites. Thus exact EI selects a new site whenever one remains. For T > n0 , let N := T − n0 . If every point of X has been queried by time T − 1, then rT = 0. Otherwise, the first T − 1 queries contain at least N distinct sites. With η = 1, (f ) (f ) the branch (1 − η)rT −1 + ηB0 0 sT −1 (x⋆ ) in (G.3), together with the bounds B0 0 ≤ B and C ≤ CB , gives rT ≤ BsT −1 (x⋆ ) + CB sT −1 (xT ) ≤ (B + CB ) sup sT −1 (x). x∈X
Removing repetitions leaves sT −1 unchanged. The power function based on any N of the distinct sites is an upper bound for sT −1 . Proposition E.5 therefore gives, for every 0 < b′′ < 1/2, rT ≤ (B + CB )Ab′′ exp{−b′′ N log(eN )}, which proves (6.11) uniformly on the translated ball.
References N. Aronszajn. Theory of reproducing kernels. Transactions of the American Mathematical Society, 68(3):337–404, 1950. doi:10.1090/S0002-9947-1950-0051437-7. P. Binev, A. Cohen, W. Dahmen, R. DeVore, G. Petrova, and P. Wojtaszczyk. Convergence rates for greedy algorithms in reduced basis methods. SIAM Journal on Mathematical Analysis, 43(3):1457–1472, 2011. doi:10.1137/100795772. L. D. Brown and R. Purves. Measurable selections of extrema. The Annals of Statistics, 1 (5):902–912, 1973. doi:10.1214/aos/1176342510. A. D. Bull. Convergence rates of efficient global optimization algorithms. Journal of Machine Learning Research, 12(88):2879–2904, 2011. URL https://www.jmlr.org/papers/v12/bull11a.html. R. DeVore, G. Petrova, and P. Wojtaszczyk. Greedy algorithms for reduced bases in Banach spaces. Constructive Approximation, 37(3):455–466, 2013. doi:10.1007/s00365-013-9186-2. C. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):211–218, 1936. doi:10.1007/BF02288367. R. Garnett. Bayesian Optimization. Cambridge University Press, Cambridge, 2023. ISBN 978-1-108-42578-0. doi:10.1017/9781108348973. S. Iwazaki. Gaussian process upper confidence bound achieves nearly-optimal regret in noise-free Gaussian process bandits. In Advances in Neural Information Processing Systems, volume 38, pages 65863–65886. Curran Associates, Inc., 2025. URL https://proceedings.neurips.cc/paper_files/paper/2025/file/ 5f1eee2509599faeeb3570a887016a64-Paper-Conference.pdf.
41
D. R. Jones, M. Schonlau, and W. J. Welch. Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13(4):455–492, 1998. doi:10.1023/A:1008306431147. A. N. Kolmogorov. Über die beste Annäherung von Funktionen einer gegebenen Funktionenklasse. Annals of Mathematics, 37(1):107–110, 1936. doi:10.2307/1968691. T. Kühn. Covering numbers of Gaussian reproducing kernel Hilbert spaces. Journal of Complexity, 27(5):489–499, 2011. doi:10.1016/j.jco.2011.01.005. H. J. Kushner. A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise. Journal of Basic Engineering, 86(1):97–106, 1964. doi:10.1115/1.3653121. Y. Li and J. W. Siegel. Entropy-based convergence rates of greedy algorithms. Mathematical Models and Methods in Applied Sciences, 34(5):779–802, 2024. doi:10.1142/S0218202524500143. G. Matheron and P. Formery. Recherche d’optimum dans la reconnaissance et la mise en exploitation des gisements miniers. Note géostatistique 41, Bureau de recherches géologiques et minières, Nov. 1962. J. Močkus. On Bayesian methods for seeking the extremum. In G. I. Marchuk, editor, Optimization Techniques: IFIP Technical Conference, Novosibirsk, July 1–7, 1974, volume 27 of Lecture Notes in Computer Science, pages 400–404. Springer, Berlin, Heidelberg, 1975. doi:10.1007/3-540-07165-2_55. J. Močkus, V. Tiesis, and A. Žilinskas. The application of Bayesian methods for seeking the extremum. In L. C. W. Dixon and G. P. Szegő, editors, Towards Global Optimisation, volume 2, pages 117–129. North-Holland, Amsterdam, 1978. G. Santin, T. Wenzel, and B. Haasdonk. On the optimality of target-data-dependent kernel greedy interpolation in Sobolev reproducing kernel Hilbert spaces. SIAM Journal on Numerical Analysis, 62(5):2249–2275, 2024. doi:10.1137/23M1587956. R. Schaback and H. Wendland. Inverse and saturation theorems for radial basis function interpolation. Mathematics of Computation, 71(238):669–681, 2002. doi:10.1090/S0025-5718-01-01383-7. H. Tran-The, S. Gupta, S. Rana, and S. Venkatesh. Regret bounds for expected improvement algorithms in Gaussian process bandit optimization. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 8715–8737. PMLR, 2022. URL https://proceedings.mlr.press/v151/tran-the22a.html. E. Vazquez and J. Bect. Convergence properties of the expected improvement algorithm with fixed mean and covariance functions. Journal of Statistical Planning and Inference, 140(11):3088–3095, 2010a. doi:10.1016/j.jspi.2010.04.018. E. Vazquez and J. Bect. Pointwise consistency of the kriging predictor with known mean and covariance functions. In A. Giovagnoli, A. C. Atkinson, B. Torsney, and C. May, editors, mODa 9 – Advances in Model-Oriented Design and Analysis, Contributions to Statistics, pages 221–228. Physica-Verlag HD, Heidelberg, 2010b. doi:10.1007/978-3-7908-2410-0_29. 42
J. Wang, H. Wang, N.-Y. Chiang, and C. G. Petra. On the convergence rate of noisy Bayesian optimization with expected improvement. arXiv:2501.09262v2, 2025. URL https://arxiv.org/abs/2501.09262v2. H. Wendland. Scattered Data Approximation, volume 17 of Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge, 2004. doi:10.1017/CBO9780511617539. T. Wenzel, G. Santin, and B. Haasdonk. Analysis of target data-dependent greedy kernel algorithms: convergence rates for f -, f · P -, and f /P -greedy. Constructive Approximation, 57(1):45–74, 2023. doi:10.1007/s00365-022-09592-3. W. Xu, Y. Jiang, E. T. Maddalena, and C. N. Jones. Lower bounds on the noiseless worst-case complexity of efficient global optimization. Journal of Optimization Theory and Applications, 201(2):583–608, 2024. doi:10.1007/s10957-024-02399-1. D. Yarotsky. Examples of inconsistency in optimization by expected improvement. Journal of Global Optimization, 56(4):1773–1790, 2013. doi:10.1007/s10898-012-9936-x.
43