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 \[ \overline{\mathcal{G}}_P(x) =
\frac{1}{\left|P\right|}\sum_{p\in P}e^{-\left\lVert x-p \right\rVert^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}{\varepsilon}\right)$ as opposed to the best-known result of
$O\left(\frac{1}{\varepsilon}\sqrt{\log\frac{1}{\varepsilon}}\right)$. It is
the first result to give a breakthrough on the barrier of $\sqrt{\log}$ factor
even when $d=2$.
