  We study the construction of coresets for kernel density estimates. That is
we show how to approximate the kernel density estimate described by a large
point set with another kernel density estimate with a much smaller point set.
For characteristic kernels (including Gaussian and Laplace kernels), our
approximation preserves the $L_\infty$ error between kernel density estimates
within error $\epsilon$, with coreset size $2/\epsilon^2$, but no other aspects
of the data, including the dimension, the diameter of the point set, or the
bandwidth of the kernel common to other approximations. When the dimension is
unrestricted, we show this bound is tight for these kernels as well as a much
broader set.
  This work provides a careful analysis of the iterative Frank-Wolfe algorithm
adapted to this context, an algorithm called \emph{kernel herding}. This
analysis unites a broad line of work that spans statistics, machine learning,
and geometry.
  When the dimension $d$ is constant, we demonstrate much tighter bounds on the
size of the coreset specifically for Gaussian kernels, showing that it is
bounded by the size of the coreset for axis-aligned rectangles. Currently the
best known constructive bound is $O(\frac{1}{\epsilon} \log^d
\frac{1}{\epsilon})$, and non-constructively, this can be improved by
$\sqrt{\log \frac{1}{\epsilon}}$. This improves the best constant dimension
bounds polynomially for $d \geq 3$.
