# Kernel Thinning

Source: [Kernel Thinning](<https://www.sota2.com/research/paper/68fa5bcf1e209131ce9cbabb>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T17:17:33.138Z

Authors: Raaz Dwivedi, Lester Mackey

Published: 2021-05-12T17:56:42.000Z

## Abstract

We introduce kernel thinning, a new procedure for compressing a distribution $\\mathbb{P}$ more effectively than i.i.d. sampling or standard thinning. Given a suitable reproducing kernel $\\mathbf{k}\_{\\star}$ and $O(n^2)$ time, kernel thinning compresses an $n$-point approximation to $\\mathbb{P}$ into a $\\sqrt{n}$-point approximation with comparable worst-case integration error across the associated reproducing kernel Hilbert space. The maximum discrepancy in integration error is $O\_d(n^{-1/2}\\sqrt{\\log n})$ in probability for compactly supported $\\mathbb{P}$ and $O\_d(n^{-\\frac{1}{2}} (\\log n)^{(d+1)/2}\\sqrt{\\log\\log n})$ for sub-exponential $\\mathbb{P}$ on $\\mathbb{R}^d$. In contrast, an equal-sized i.i.d. sample from $\\mathbb{P}$ suffers $\\Omega(n^{-1/4})$ integration error. Our sub-exponential guarantees resemble the classical quasi-Monte Carlo error rates for uniform $\\mathbb{P}$ on $\[0,1\]^d$ but apply to general distributions on $\\mathbb{R}^d$ and a wide range of common kernels. Moreover, the same construction delivers near-optimal $L^\\infty$ coresets in $O(n^2)$ 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$.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Dataset Summarization on GMM-100](<https://www.sota2.com/research/sota/dataset-summarization-on-gmm-100.md>): Dataset Summarization; GMM-100; MMDw: 0.0992.

- [Dataset Summarization on Joker](<https://www.sota2.com/research/sota/dataset-summarization-on-joker.md>): Dataset Summarization; Joker; MMDw: 0.149.

- [Dataset Summarization on GMM-2](<https://www.sota2.com/research/sota/dataset-summarization-on-gmm-2.md>): Dataset Summarization; GMM-2; MMDw: 0.167.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2105.05842>)

[PDF](<https://arxiv.org/pdf/2105.05842.pdf>)
