Kernel Thinning

Raaz Dwivedi; Lester Mackey

Kernel Thinning

Raaz Dwivedi, Lester Mackey

Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1753-1753, 2021.

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}$ 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^{-\frac{1}{2}}\sqrt{\log n})$ for compactly supported

$\mathbb{P}$ and

$\mathcal{O}_d(n^{-\frac{1}{2}} \sqrt{(\log n)^{d+1}\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^{-\frac14})$ 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é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.

Cite this Paper

BibTeX


@InProceedings{pmlr-v134-dwivedi21a,
  title = 	 {Kernel Thinning},
  author =       {Dwivedi, Raaz and Mackey, Lester},
  booktitle = 	 {Proceedings of Thirty Fourth Conference on Learning Theory},
  pages = 	 {1753--1753},
  year = 	 {2021},
  editor = 	 {Belkin, Mikhail and Kpotufe, Samory},
  volume = 	 {134},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {15--19 Aug},
  publisher =    {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v134/dwivedi21a/dwivedi21a.pdf},
  url = 	 {https://proceedings.mlr.press/v134/dwivedi21a.html},
  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}$ 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^{-\frac{1}{2}}\sqrt{\log n})$ for compactly supported $\mathbb{P}$ and $\mathcal{O}_d(n^{-\frac{1}{2}} \sqrt{(\log n)^{d+1}\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^{-\frac14})$ 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é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.}
}

Endnote

%0 Conference Paper
%T Kernel Thinning
%A Raaz Dwivedi
%A Lester Mackey
%B Proceedings of Thirty Fourth Conference on Learning Theory
%C Proceedings of Machine Learning Research
%D 2021
%E Mikhail Belkin
%E Samory Kpotufe	
%F pmlr-v134-dwivedi21a
%I PMLR
%P 1753--1753
%U https://proceedings.mlr.press/v134/dwivedi21a.html
%V 134
%X 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^{-\frac{1}{2}}\sqrt{\log n})$ for compactly supported $\mathbb{P}$ and $\mathcal{O}_d(n^{-\frac{1}{2}} \sqrt{(\log n)^{d+1}\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^{-\frac14})$ 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é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.

APA


Dwivedi, R. & Mackey, L.. (2021). Kernel Thinning. Proceedings of Thirty Fourth Conference on Learning Theory, in Proceedings of Machine Learning Research 134:1753-1753 Available from https://proceedings.mlr.press/v134/dwivedi21a.html.

Related Material

Download PDF