# Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Sampling

arXiv: https://arxiv.org/abs/2311.13548 · HTML: https://mlsanity.com/paper/2311.13548/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 106 references that are in the map.
- First posted on arXiv 22 Nov 2023.

## Builds on (most cited first, 30 of 33)

- [MMD GAN: Towards Deeper Understanding of Moment Matching Network](https://mlsanity.com/paper/1705.08584/) (2017)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm](https://mlsanity.com/paper/1702.07254/) (2017)
- [Generative Models and Model Criticism via Optimized Maximum Mean Discrepancy](https://mlsanity.com/paper/1611.04488/) (2016)
- [Kernel Thinning](https://mlsanity.com/paper/2105.05842/) (2021)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [Discrepancy, Coresets, and Sketches in Machine Learning](https://mlsanity.com/paper/1906.04845/) (2019)
- [Generalized Kernel Thinning](https://mlsanity.com/paper/2110.01593/) (2021)
- [Kernel quadrature with DPPs](https://mlsanity.com/paper/1906.07832/) (2019)
- [Probabilistic Integration: A Role in Statistical Computation?](https://mlsanity.com/paper/1512.00933/) (2015)
- [Finite sample properties of parametric MMD estimation: robustness to misspecification and dependence](https://mlsanity.com/paper/1912.05737/) (2019)
- [Positively Weighted Kernel Quadrature via Subsampling](https://mlsanity.com/paper/2107.09597/) (2021)
- [Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering](https://mlsanity.com/paper/1501.02056/) (2015)
- [Convergence Guarantees for Adaptive Bayesian Quadrature Methods](https://mlsanity.com/paper/1905.10271/) (2019)
- [Nystr"om Kernel Mean Embeddings](https://mlsanity.com/paper/2201.13055/) (2022)
- [Kernel interpolation with continuous volume sampling](https://mlsanity.com/paper/2002.09677/) (2020)
- [Frank-Wolfe Bayesian Quadrature: Probabilistic Integration with Theoretical Guarantees](https://mlsanity.com/paper/1506.02681/) (2015)
- [Distribution Compression in Near-linear Time](https://mlsanity.com/paper/2111.07941/) (2021)
- [Sampling-based Nystr"om Approximation and Kernel Quadrature](https://mlsanity.com/paper/2301.09517/) (2023)
- [Convergence Analysis of Deterministic Kernel-Based Quadrature Rules in Misspecified Settings](https://mlsanity.com/paper/1709.00147/) (2017)
- [The Sliding Frank-Wolfe Algorithm and its Application to Super-Resolution Microscopy](https://mlsanity.com/paper/1811.06416/) (2018)
- [A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe](https://mlsanity.com/paper/1702.06457/) (2017)
- [Differentially Private Database Release via Kernel Mean Embeddings](https://mlsanity.com/paper/1710.01641/) (2017)
- [Kernel Mean Estimation and Stein's Effect](https://mlsanity.com/paper/1306.0842/) (2013)
- [Compressive K-means](https://mlsanity.com/paper/1610.08738/) (2016)
- [Relating Leverage Scores and Density using Regularized Christoffel Functions](https://mlsanity.com/paper/1805.07943/) (2018)
- [Nystr"om landmark sampling and regularized Christoffel functions](https://mlsanity.com/paper/1905.12346/) (2019)
- [On the Sampling Problem for Kernel Quadrature](https://mlsanity.com/paper/1706.03369/) (2017)
- [ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions](https://mlsanity.com/paper/2106.12231/) (2021)
- [Mean Nystr"om Embeddings for Adaptive Compressive Learning](https://mlsanity.com/paper/2110.10996/) (2021)

## Built on by (most cited first, 10 of 10)

- [Weighted quantization using MMD: From mean field to mean shift via gradient flows](https://mlsanity.com/paper/2502.10600/) (2025)
- [A Dictionary of Closed-Form Kernel Mean Embeddings](https://mlsanity.com/paper/2504.18830/) (2025)
- [A Scalable Nystrom-Based Kernel Two-Sample Test with Permutations](https://mlsanity.com/paper/2502.13570/) (2025)
- [Stationary MMD Points](https://mlsanity.com/paper/2505.20754/) (2025)
- [Monte Carlo with kernel-based Gibbs measures: Guarantees for probabilistic herding](https://mlsanity.com/paper/2402.11736/) (2024)
- [Bayesian Quadrature](https://mlsanity.com/paper/2602.16218/) (2026)
- [Quenched large deviations for Monte Carlo integration with Coulomb gases](https://mlsanity.com/paper/2508.01392/) (2025)
- [Convex-Geometric Error Bounds for Positive-Weight Kernel Quadrature](https://mlsanity.com/paper/2605.05705/) (2026)
- [Amortized quadrature for posterior expectations in inverse problems](https://mlsanity.com/paper/2606.15871/) (2026)
- [Stochastic gradient descent with initial regularization](https://mlsanity.com/paper/2608.22953/) (2026)

## Abstract (arXiv)

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.