Optimal Coreset for Gaussian Kernel Density Estimation

Given a point set $P\subset {\mathbb{R}}^d$, the kernel density estimate of $P$ is defined as $${\bar{\mathcal{G}}}_P(x)=\frac{1}{\mid P\mid }\sum _{p\in P}{e}^{-{\parallel x-p\parallel }^2}$$ for any $x\in {\mathbb{R}}^d$. We study how to construct a small subset $Q$ of $P$ such that the kernel density estimate of $P$ is approximated by the kernel density estimate of $Q$. This subset $Q$ is called a coreset. The main technique in this work is constructing a $\pm 1$ coloring on the point set $P$ by discrepancy theory and we leverage Banaszczyk’s Theorem. When $d>1$ is a constant, our construction gives a coreset of size $O\left(\frac{1}{\epsilon }\right)$ as opposed to the best-known result of $O\left(\frac{1}{\epsilon }\sqrt{\log \frac{1}{\epsilon }}\right)$. It is the first result to give a breakthrough on the barrier of $\sqrt{\log }$ factor even when $d=2$.