Kernel Thinning
share
We introduce kernel thinning, a new procedure for compressing a distribution ℙ more effectively than i.i.d. sampling or standard thinning. Given a suitable reproducing kernel 𝐤 and 𝒪(n^2) time, kernel thinning compresses an n-point approximation to ℙ into a √(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 𝒪_d(n^-1/2√(log n)) for compactly supported ℙ and 𝒪_d(n^-1/2√((log n)^d+1loglog n)) for sub-exponential ℙ on ℝ^d. In contrast, an equal-sized i.i.d. sample from ℙ suffers Ω(n^-1/4) integration error. Our sub-exponential guarantees resemble the classical quasi-Monte Carlo error rates for uniform ℙ on [0,1]^d but apply to general distributions on ℝ^d and a wide range of common kernels. We use our results to derive explicit non-asymptotic maximum mean discrepancy bounds for Gaussian, Matérn, 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.
READ FULL TEXT