Answers are grounded in this paper and cite their sources.
We study expected improvement (EI) for minimizing a deterministic function f in the RKHS Hₖ of a continuous positive-semidefinite kernel k on a nonempty compact set X⊂ Rᵈ. Function values are observed exactly, and EI is computed from a fixed zero-mean Gaussian-process model with covariance σ²k, $σ>0$. A weak-EI policy queries a point whose EI is at least a fixed positive fraction of its maximum. We introduce a notion of sequential separation radius relating ranked selected-point innovation norms to Kolmogorov widths, drawing on greedy approximation. Standard power-function estimates from scattered-data approximation and a finite-budget regret argument yield the rates. After N post-initial queries, every weak-EI policy has simple regret O(N-ν/d) for isotropic Matérn kernels of smoothness $ν>0$ and O(exp[-c₁min,N1/dlog(eN)\]) for the isotropic squared-exponential kernel, with c₁>0. For $d=1$, the sharper bound O(exp[-c₂Nlog(eN)]) holds for exact EI, with c₂>0. These bounds are uniform over each fixed RKHS ball. If X has nonempty interior and $B>0$, the exact EI policy is minimax-rate optimal over the RKHS ball of radius B for Matérn kernels, even among randomized strategies whose final recommendation need not be a query point. For the squared-exponential kernel, it is minimax-rate optimal up to constants in the exponent among deterministic methods whose final recommendation may be any point of X.
No takes yet. Share an insight, caveat, or question.
Vázquez et al. (2026) studied this question.