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 ℋk of a continuous positive-semidefinite kernel k on a nonempty compact set 𝒳⊂ℝd. 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−ν/d) for isotropic Matérn kernels of smoothness ν>0 and O(exp[−c1min{N,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 𝒳 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 𝒳.
Related
- Expected Minimax Regret Rates for Adaptive LQG Control on Fixed Parameter Sets
- Expected Utility Regret Rule: Minimax and Bayes Optimal Portfolio Choice
- Minimax estimation of the expected conditional covariance under bounds on the covariate density
- Robust Local Fréchet Regression: Nonasymptotic Theory and Minimax Optimality
- Minimax-Optimality of Posterior Sampling for Reinforcement Learning
BibTeX
@misc{vazquez2026simpleregret,
title = {{Simple-regret rates and minimax optimality of fixed-prior expected improvement in Matérn and squared-exponential RKHSs}},
author = {Emmanuel Vazquez and Sébastien Petit},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.29245},
eprint = {2607.29245},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.29245},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Simple-regret rates and minimax optimality of fixed-prior expected improvement in Matérn and squared-exponential RKHSs
AU - Emmanuel Vazquez
AU - Sébastien Petit
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2607.29245
UR - https://arxiv.org/abs/2607.29245
AB - We study expected improvement (EI) for minimizing a deterministic function f in the RKHS ℋ_k of a continuous positive-semidefinite kernel k on a nonempty compact set 𝒳⊂ℝ^d. 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^−ν/d) for isotropic Matérn kernels of smoothness ν>0 and O(exp[−c_1min{N,N^1/dlog(eN)}]) for the isotropic squared-exponential kernel, with c_1>0. For d=1, the sharper bound O(exp[−c_2Nlog(eN)]) holds for exact EI, with c_2>0. These bounds are uniform over each fixed RKHS ball. If 𝒳 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 𝒳.
ER -