arXiv:2605.05705math.NAcs.LG2026-05

正权重核积分的误差可达到优于蒙特卡洛的收敛速度,关键在凸包几何结构。

Convex-Geometric Error Bounds for Positive-Weight Kernel Quadrature

  • 利用样本点生成的随机凸包,实现正权重重新加权。
  • 在固定维数下误差可达 O(d/N),优于等权平均。
  • 适用于需要稳定权重的高精度积分任务,如贝叶斯推断。

核积分可利用再生核希尔伯特空间(RKHS)的谱结构,在光滑被积函数上超越蒙特卡洛方法,但优化后的积分权重通常为符号混合,可能数值不稳定。本文研究当权重被约束为正时(即单纯形权重),谱加速是否仍可能。在目标函数固定的采样池设定下,已有大小为 N 的独立同分布候选点集,任务是重新加权以逼近核均值嵌入。我们发现,该正权重重加权问题并非由等权经验平均主导,而是受样本点生成的随机凸包控制。主要几何结果表明:在 d 维空间中,有界随机向量的均值可通过 N 个独立同分布样本的凸组合以高概率逼近,误差为 O(d/N),优于固定维度下的等权平均。通过增强的Mercer截断论证,将此 d 维凸包逼近推广至全 RKHS 最坏情况误差。所得正权重核积分误差界包含谱尾项和有限样本凸包项,在有利的谱衰减条件下可实现超越蒙特卡洛的速率,包括在指数谱衰减下接近 O(1/N) 的速率(含对数因子)。此外,我们提出一种构造性 Frank--Wolfe 算法,直接作用于池中原子,保持单纯形权重,并给出显式优化误差界。

原文摘要 · Abstract (English)

Kernel quadrature can exploit RKHS spectral structure and outperform Monte Carlo on smooth integrands, but optimized quadrature weights are generally signed and may be numerically unstable. We study whether spectral acceleration remains possible when the weights are constrained to be positive, i.e., simplex weights. In the exact-target fixed-pool setting, an evaluated i.i.d. candidate pool of size $N$ is already available and the task is to reweight it so as to approximate the kernel mean embedding. We show that this positive reweighting problem is governed not by the equal-weight empirical average, but by the random convex hull generated by the pool. Our main geometric result shows that the mean of a bounded $d$-dimensional random vector can be approximated by a convex combination of $N$ i.i.d. samples at accuracy $O(d/N)$ with high probability, sharper than equal-weight averaging in the fixed-dimensional regime. We transfer this $d$-dimensional convex-hull approximation to full RKHS worst-case error through an augmented Mercer-truncation argument. The resulting positive-weight KQ bounds consist of a spectral tail term and a finite-sample convex-hull term, yielding Monte-Carlo-beating rates in favorable spectral regimes, including near-$O(1/N)$ rates up to logarithmic factors under exponential spectral decay. We also provide a constructive Frank--Wolfe algorithm that operates directly on the pool atoms, maintains simplex weights, and admits an explicit optimization-error bound.

核积分正权重凸包误差界

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。