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

arXiv:2607.29245v1 Announce Type: cross Abstract: We study the expected improvement (EI) policy for minimizing a deterministic objective function f on a nonempty compact set mathcal X subsetmathbb R^d. We assume that f belongs to the RKHS mathcal H_k of a continuous positive-semidefinite kernel k on mathcal X. Function values are observed exactly, and EI is computed from a fixed zero-mean Gaussian-process model with covariance sigma^2k. 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,dot) 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^{-nu/d}) for isotropic Matern kernels of smoothness nu>0. For the isotropic squared-exponential kernel, simple regret is O(exp[-c_1min{N, N^{1/d}log(eN)}]) for some c_1>0. With exact EI maximization, it is O(exp[-c_2N^{1/d} log(eN)]) for some c_2>0. For every fixed Bgeq0, these bounds are uniform over the RKHS ball of radius B. If mathcal X has nonempty interior and B>0, then, among deterministic methods whose final recommendation may be any point of mathcal X, the exact EI policy is minimax-rate optimal over the RKHS ball of radius B for Matern kernels and minimax-rate optimal up to constants in the exponent for squared-exponential kernels.

Source: arXiv cs.LG | 2026-08-03