Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via
  Leverage Scores Sampling
Antoine Chatalic Nicolas Schreuder Ernesto De Vito Lorenzo Rosasco
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.