# Kernel Thinning

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

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 104 references that are in the map.
- First posted on arXiv 12 May 2021.

## Builds on (most cited first, 22 of 22)

- [Control functionals for Monte Carlo integration](https://mlsanity.com/paper/1410.2392/) (2014)
- [Automated Scalable Bayesian Inference via Hilbert Coresets](https://mlsanity.com/paper/1710.05053/) (2017)
- [Stein Points](https://mlsanity.com/paper/1803.10161/) (2018)
- [Support points](https://mlsanity.com/paper/1609.01811/) (2016)
- [Near-Optimal Coresets of Kernel Density Estimates](https://mlsanity.com/paper/1802.01751/) (2018)
- [Discrepancy, Coresets, and Sketches in Machine Learning](https://mlsanity.com/paper/1906.04845/) (2019)
- [Stein Point Markov Chain Monte Carlo](https://mlsanity.com/paper/1905.03673/) (2019)
- [Kernel quadrature with DPPs](https://mlsanity.com/paper/1906.07832/) (2019)
- [Optimal Thinning of MCMC Output](https://mlsanity.com/paper/2005.03952/) (2020)
- [Random Feature Stein Discrepancies](https://mlsanity.com/paper/1806.07788/) (2018)
- [Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering](https://mlsanity.com/paper/1501.02056/) (2015)
- [Monte Carlo with Determinantal Point Processes](https://mlsanity.com/paper/1605.00361/) (2016)
- [Discrepancy Minimization via a Self-Balancing Walk](https://mlsanity.com/paper/2006.14009/) (2020)
- [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)
- [Black-box Importance Sampling](https://mlsanity.com/paper/1610.05247/) (2016)
- [The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues](https://mlsanity.com/paper/1708.01079/) (2017)
- [A Bayes-Sard Cubature Method](https://mlsanity.com/paper/1804.03016/) (2018)
- [Statistically efficient thinning of a Markov chain sampler](https://mlsanity.com/paper/1510.07727/) (2015)
- [Improved Coresets for Kernel Density Estimates](https://mlsanity.com/paper/1710.04325/) (2017)
- [A Statistical Perspective on Coreset Density Estimation](https://mlsanity.com/paper/2011.04907/) (2020)
- [The power of online thinning in reducing discrepancy](https://mlsanity.com/paper/1608.02895/) (2016)

## Built on by (most cited first, 30 of 48)

- [MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting](https://mlsanity.com/paper/2306.08777/) (2023)
- [Generalized Kernel Thinning](https://mlsanity.com/paper/2110.01593/) (2021)
- [Positively Weighted Kernel Quadrature via Subsampling](https://mlsanity.com/paper/2107.09597/) (2021)
- [SonicMoE: Accelerating MoE with IO and Tile-aware Optimizations](https://mlsanity.com/paper/2512.14080/) (2025)
- [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)
- [Compress Then Test: Powerful Kernel Testing in Near-linear Time](https://mlsanity.com/paper/2301.05974/) (2023)
- [Counterfactual inference in sequential experiments](https://mlsanity.com/paper/2202.06891/) (2022)
- [Optimally-Weighted Estimators of the Maximum Mean Discrepancy for Likelihood-Free Inference](https://mlsanity.com/paper/2301.11674/) (2023)
- [Weighted quantization using MMD: From mean field to mean shift via gradient flows](https://mlsanity.com/paper/2502.10600/) (2025)
- [Kernel quadrature with randomly pivoted Cholesky](https://mlsanity.com/paper/2306.03955/) (2023)
- [Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Sampling](https://mlsanity.com/paper/2311.13548/) (2023)
- [A Dictionary of Closed-Form Kernel Mean Embeddings](https://mlsanity.com/paper/2504.18830/) (2025)
- [Online Kernel CUSUM for Change-Point Detection](https://mlsanity.com/paper/2211.15070/) (2022)
- [SOBER: Highly Parallel Bayesian Optimization and Bayesian Quadrature over Discrete and Mixed Spaces](https://mlsanity.com/paper/2301.11832/) (2023)
- [Coordinating Distributed Example Orders for Provably Accelerated Training](https://mlsanity.com/paper/2302.00845/) (2023)
- [Distributional Dataset Distillation with Subtask Decomposition](https://mlsanity.com/paper/2403.00999/) (2024)
- [Low-Rank Thinning](https://mlsanity.com/paper/2502.12063/) (2025)
- [Adaptive Batch Sizes for Active Learning A Probabilistic Numerics Approach](https://mlsanity.com/paper/2306.05843/) (2023)
- [A Unified View of Optimal Kernel Hypothesis Testing](https://mlsanity.com/paper/2503.07084/) (2025)
- [WildCat: Near-Linear Attention in Theory and Practice](https://mlsanity.com/paper/2602.10056/) (2026)
- [When can Regression-Adjusted Control Variates Help? Rare Events, Sobolev Embedding and Minimax Optimality](https://mlsanity.com/paper/2305.16527/) (2023)
- [Efficient and Accurate Explanation Estimation with Distribution Compression](https://mlsanity.com/paper/2406.18334/) (2024)
- [A Critical Look at Targeted Instruction Selection: Disentangling What Matters (and What Doesn't)](https://mlsanity.com/paper/2602.14696/) (2026)
- [Online, Informative MCMC Thinning with Kernelized Stein Discrepancy](https://mlsanity.com/paper/2201.07130/) (2022)
- [A Quadrature Approach for General-Purpose Batch Bayesian Optimization via Probabilistic Lifting](https://mlsanity.com/paper/2404.12219/) (2024)
- [Supervised Kernel Thinning](https://mlsanity.com/paper/2410.13749/) (2024)
- [Differentially Private Synthetic Data with Private Density Estimation](https://mlsanity.com/paper/2405.04554/) (2024)
- [Learning Counterfactual Distributions via Kernel Nearest Neighbors](https://mlsanity.com/paper/2410.13381/) (2024)
- [Stationary MMD Points](https://mlsanity.com/paper/2505.20754/) (2025)

## Abstract (arXiv)

We introduce kernel thinning, a new procedure for compressing a distribution mathbbP more effectively than i.i.d. sampling or standard thinning. Given a suitable reproducing kernel kstar and O(n2) time, kernel thinning compresses an n-point approximation to mathbbP into a √n-point approximation with comparable worst-case integration error across the associated reproducing kernel Hilbert space. The maximum discrepancy in integration error is Od(n-1/2√log n) in probability for compactly supported mathbbP and Od(n^-frac12 (log n)(d+1)/2√loglog n) for sub-exponential mathbbP on ℝd. In contrast, an equal-sized i.i.d. sample from mathbbP suffers Omega(n-1/4) integration error. Our sub-exponential guarantees resemble the classical quasi-Monte Carlo error rates for uniform mathbbP on [0,1]d but apply to general distributions on ℝd and a wide range of common kernels. Moreover, the same construction delivers near-optimal L^∞ coresets in O(n2) time. We use our results to derive explicit non-asymptotic maximum mean discrepancy bounds for Gaussian, Mat'ern, and B-spline kernels and present two vignettes illustrating the practical benefits of kernel thinning over i.i.d. sampling and standard Markov chain Monte Carlo thinning, in dimensions d=2 through 100.