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

Abstract

We study expected improvement (EI) for minimizing a deterministic function $f$ in the RKHS ${\mathcal{H}}_k$ of a continuous positive-semidefinite kernel $k$ on a nonempty compact set $\mathcal{X}\subset {\mathbb{R}}^d$. Function values are observed exactly, and EI is computed from a fixed zero-mean Gaussian-process model with covariance ${\sigma }^{2}k$, $\sigma >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érn kernels of smoothness $\nu >0$ and $O(\exp [-c_1\min \{N,N^{1/d}\log (eN)\}])$ for the isotropic squared-exponential kernel, with $c_1>0$. For $d=1$, the sharper bound $O(\exp [-c_{2}N\log (eN)])$ holds for exact EI, with $c_2>0$. These bounds are uniform over each fixed RKHS ball. If $\mathcal{X}$ has nonempty interior and $B>0$, the exact EI policy is minimax-rate optimal over the RKHS ball of radius $B$ for Matérn kernels, even among randomized strategies whose final recommendation need not be a query point. For the squared-exponential kernel, it is minimax-rate optimal up to constants in the exponent among deterministic methods whose final recommendation may be any point of $\mathcal{X}$.

43 pages. Minor corrections and clarifications