Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Sampling
This work addresses computational bottlenecks in kernel-based methods for statisticians and machine learning practitioners, offering incremental improvements in efficiency for tasks like distribution comparison and testing.
The paper tackles the problem of numerical integration in reproducing kernel Hilbert spaces using only pointwise evaluations, proposing a method that uses a small random subset of samples to achieve the optimal n^{-1/2} error rate while reducing computational cost. It demonstrates this with theoretical bounds and numerical experiments on real datasets, showing improved efficiency-accuracy tradeoffs compared to existing methods.
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.