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

We study expected improvement (EI) for minimizing a deterministic function f in the RKHS mathcal Hk of a continuous positive-semidefinite kernel k on a nonempty compact set mathcal Xsubsetmathbb Rd. Function values are observed exactly, and EI is computed from a fixed zero-mean Gaussian-process model with covariance σ2k, σ>0. A weak-EI policy queries a point whose EI is at least a fixed positive fraction of its maximum. We introduce a notion of sequential separation radius relating ranked selected-point innovation norms to Kolmogorov widths, drawing on greedy approximation. Standard power-function estimates from scattered-data approximation and a finite-budget regret argument yield the rates. After N post-initial queries, every weak-EI policy has simple regret O(N-nu/d) for isotropic Mat'ern kernels of smoothness nu>0 and O(exp[-c1minN,N1/dlog(eN)]) for the isotropic squared-exponential kernel, with c1>0. For d=1, the sharper bound O(exp[-c2Nlog(eN)]) holds for exact EI, with c2>0. These bounds are uniform over each fixed RKHS ball. If mathcal X has nonempty interior and B>0, the exact EI policy is minimax-rate optimal over the RKHS ball of radius B for Mat'ern kernels, even among randomized strategies whose final recommendation need not be a query point. For the squared-exponential kernel, it is minimax-rate optimal up to constants in the exponent among deterministic methods whose final recommendation may be any point of mathcal X.