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

arXiv: https://arxiv.org/abs/2607.29245 · HTML: https://mlsanity.com/paper/2607.29245/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 26 references that are in the map.
- First posted on arXiv 31 Jul 2026.

## Builds on (most cited first, 3 of 3)

- [Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2203.07875/) (2022)
- [Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits](https://mlsanity.com/paper/2502.19006/) (2025)
- [On the convergence rate of noisy Bayesian Optimization with Expected Improvement](https://mlsanity.com/paper/2501.09262/) (2025)

## Built on by (most cited first, 1 of 1)

- [Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization](https://mlsanity.com/paper/2610.19925/) (2026)

## Abstract (arXiv)

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.