Kernel Thinning
  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}$ 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. With high probability,
the maximum discrepancy in integration error is
$\mathcal{O}_d(n^{-1/2}\sqrt{\log n})$ 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. 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$.
