分析了固定先验期望改进策略在核函数空间中的收敛速度,证明其最优性。
Simple-regret rates and minimax optimality of fixed-prior expected improvement in Matérn and squared-exponential RKHSs
- 基于高斯过程与核空间理论,建立查询点创新范数的序列约束。
- 对各向同性马特恩核得 $O(N^{-ν/d})$ 简单后悔率,指数核为超指数衰减。
- 首次证明该策略在特定核空间中达到极小极大最优速率,适合优化理论研究者。
研究在紧凑集 $\mathcal X \subset \mathbb R^d$ 上最小化确定性目标函数 $f$ 时的期望改进(EI)策略。假设 $f$ 属于连续正定核 $k$ 的再生核希尔伯特空间(RKHS)$\mathcal H_k$,函数值可精确观测,且使用零均值高斯过程模型,协方差为 $σ^2k$。在初始设计后,策略选择一个期望改进至少为其最大值固定正分数的点。通过将候选点的归一化后验标准差与特征空间中的创新范数关联,并利用格拉姆行列式和科莫戈罗夫宽度估计子空间的序列分离半径,结合一步后悔不等式,得到有限预算下简单后悔的上界。经过 $N$ 次后续查询,对于各向同性马特恩核(光滑度 $ν>0$),简单后悔率为 $O(N^{-ν/d})$;对于各向同性平方指数核,为 $O(\exp[-c_1\min\{N, N^{1/d}\log(eN)\}])$,若精确最大化则为 $O(\exp[-c_2N^{1/d} \log(eN)])$,$c_1,c_2>0$。这些界对半径为 $B$ 的 RKHS 球内所有函数统一成立。当 $\mathcal X$ 内部非空且 $B>0$ 时,该策略在所有确定性方法中对马特恩核达到极小极大最优速率,对平方指数核在指数常数上最优。
原文摘要 · Abstract (English)
We study the expected improvement (EI) policy for minimizing a deterministic objective function $f$ on a nonempty compact set $\mathcal X \subset\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 $σ^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,\cdot)$ 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_1\min\{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 $B\geq0$, 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。