In this work we consider the problem of numerical integration, i.e.,
approximating integrals with respect to a target probability measure using only
pointwise evaluations of the integrand. We focus on the setting in which the
target distribution is only accessible through a set of $n$ i.i.d.
observations, and the integrand belongs to a reproducing kernel Hilbert space.
We propose an efficient procedure which exploits a small i.i.d. random subset
of $m<n$ samples drawn either uniformly or using approximate leverage scores
from the initial observations. Our main result is an upper bound on the
approximation error of this procedure for both sampling strategies. It yields
sufficient conditions on the subsample size to recover the standard (optimal)
$n^{-1/2}$ rate while reducing drastically the number of functions evaluations,
and thus the overall computational cost. Moreover, we obtain rates with respect
to the number $m$ of evaluations of the integrand which adapt to its
smoothness, and match known optimal rates for instance for Sobolev spaces. We
illustrate our theoretical findings with numerical experiments on real
datasets, which highlight the attractive efficiency-accuracy tradeoff of our
method compared to existing randomized and greedy quadrature methods. We note
that, the problem of numerical integration in RKHS amounts to designing a
discrete approximation of the kernel mean embedding of the target distribution.
As a consequence, direct applications of our results also include the efficient
computation of maximum mean discrepancies between distributions and the design
of efficient kernel-based tests.

在本研究中，我们考虑了数值积分的问题，即仅使用对被积函数进行逐点评估的方法，用目标概率测度来近似积分。我们提出了一种有效的程序，利用所给的包含有 n 个独立同分布的观测样本和总体分布密切相关的再现核希尔伯特空间中的积分函数。我们的主要结果是，对于两种不同的抽样策略，我们的程序的近似误差有一个上界。这个上界给出了对子样本大小的充分条件，以恢复标准的（最佳的）n^{-1/2} 速率，同时大大减少了函数评估的数量，从而减少整体的计算成本。此外，我们获得了关于积分函数评估数量 m 的速率，这些速率能够适应其平滑性，并且在 Sobolev 空间等情况下与已知的最佳速率相匹配。我们通过对真实数据集的数值实验来说明我们的理论发现，这些实验突出了我们的方法在效率 - 精度权衡方面与现有的随机和贪婪积分方法相比的优势。值得注意的是，RKHS 中的数值积分问题归结为设计目标分布的离散近似核平均嵌入。因此，我们的结果还包括了计算分布间最大均值差异和设计有效的基于核的检验的高效方法。