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

2026/07/31 by Emmanuel Vazquez, Sébastien Petit
Mathematics · Computer Science · #stat.ML #cs.LG #cs.NA #math.NA #math.ST #stat.TH

paper · pdf

arxiv created 2026/07/31 · arxiv updated 2026/08/03

Abstract

We study the expected improvement (EI) policy for minimizing a deterministic objective function f on a nonempty compact set \mathcal X ⊂\mathbb 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 σ²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[-c₁min\N, N^1/dlog(eN)\]) for some c₁>0. With exact EI maximization, it is O(exp[-c₂N^1/d log(eN)]) for some c₂>0. For every fixed B≥0, 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 Matérn kernels and minimax-rate optimal up to constants in the exponent for squared-exponential kernels.

Citations

• Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits
• On the convergence rate of noisy Bayesian Optimization with Expected Improvement
• Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization
• Greedy Algorithms for Reduced Bases in Banach Spaces
• Pointwise consistency of the kriging predictor with known mean and covariance functions
• Convergence properties of the expected improvement algorithm
• The Approximation of One Matrix by Another of Lower Rank