  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 $\mathcal{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 $\mathcal{O}_d(n^{-1/2}\sqrt{\log n})$ in probability
for compactly supported $\mathbb{P}$ and $\mathcal{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 $\mathcal 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$.
