Improved Coresets for Kernel Density Estimates

Jeff M. Phillips, Wai Ming Tai

Kernel Density Estimation (KDE) is a fundamental tool in statistics and machine learning, used to estimate the probability density function of a random variable. However, KDE faces a significant scaling challenge: calculating the density at a single point requires summing the contributions of all $n$ points in a dataset. For massive datasets with millions or billions of entries, this becomes computationally prohibitive.

To solve this, researchers use coresets—small subsets of the original data that can approximate the full dataset's density with a guaranteed maximum error $\epsilon$. This paper, presented by researchers from the University of Utah, provides a theoretical breakthrough by establishing new, tighter bounds on coreset sizes for common kernels like Gaussian and Laplace.

The Challenge of KDE Scaling

The goal of coreset construction is to find a subset $Q$ of the original point set $P$ such that the $L_\infty$ error between the KDE of $P$ and the KDE of $Q$ is at most $\epsilon$. Historically, the size of $Q$ often depended on the "bandwidth" (smoothing parameter) of the kernel or the physical diameter of the point set. In real-world scenarios where data is high-dimensional or widely spread, these dependencies can make coresets impractically large.

Theoretical Methods

The authors approach the problem through three primary theoretical lenses:

  1. Frank-Wolfe Analysis (Kernel Herding): The researchers analyze a greedy iterative algorithm known as "kernel herding." In each step, the algorithm selects the point from the original set that most reduces the approximation error in a Reproducing Kernel Hilbert Space (RKHS). While previous proofs for this method were complex or required weighted subsets, this paper provides a simplified, first-principles proof for unweighted coresets.
  2. Discrepancy Theory: For Gaussian kernels, the authors introduce a novel reduction. They demonstrate that the problem of finding a kernel coreset can be mapped to the "axis-aligned rectangle discrepancy" problem. By showing that the Gaussian kernel is "multiplicatively separable" (it can be broken down into a product of 1D functions), they apply decades of research from combinatorial geometry to achieve superior bounds.
  3. Mathematical Lower Bounds: To test the limits of their theories, the authors construct worst-case high-dimensional point sets to prove that certain error bounds are fundamentally optimal and cannot be improved further.

Key Results and Comparison

The paper's most significant contribution is the establishment of dimension-independent bounds for characteristic kernels and near-linear bounds for Gaussian kernels in low dimensions.

Comparison of coreset sizes, runtimes, and restrictions between previous work and the new results presented in this paper.

As shown in the table above, the "New Result" entries significantly improve upon previous work:

  • General Bound: For any characteristic kernel (like Gaussian or Laplace), a coreset of size $2/\epsilon^2$ is sufficient to ensure the $L_\infty$ error is less than $\epsilon$, regardless of dimensionality or data spread.
  • Low-Dimension Gaussian Bound: In a fixed dimension $d$, the authors improved the coreset size for Gaussian kernels to $O(\frac{1}{\epsilon} \log^d \frac{1}{\epsilon})$. For $d \geq 3$, this is a polynomial improvement over the best previously known constructive bounds.
  • Lower Bound: They proved a lower bound of $\Omega(1/\epsilon^2)$ for "somewhere-steep" kernels in high dimensions, showing that their general bound is optimal in that context.

Key Insights

  • Dimension Independence: One of the most striking findings is that for characteristic kernels, the general coreset size of $2/\epsilon^2$ is completely independent of the number of dimensions ($d$), the diameter of the data, or the kernel bandwidth. This suggests that KDE is a robust tool even for high-dimensional data.
  • The Gaussian-Rectangle Connection: The realization that Gaussian kernels share deep mathematical properties with axis-aligned rectangles allowed the authors to apply advanced tools from combinatorial geometry to the KDE problem, bypassing previous limitations.
  • Tightness of Bounds: By proving the $1/\epsilon^2$ lower bound, the paper settles a long-standing question, confirming that without making assumptions about the data's structure, we cannot expect to find smaller general-purpose coresets in high dimensions.

Limitations and Future Work

While the new bounds are much tighter, a small "poly-log" gap remains between the best constructive upper bound and the non-constructive lower bound. Furthermore, the significant improvements in low dimensions rely heavily on the separability of the Gaussian kernel; it remains unclear if similar improvements can be achieved for non-separable kernels like the Laplace kernel. Future work may also focus on making the discrepancy-based algorithms more practical and efficient for large-scale implementations.

Summary updated

Abstract

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$.
BibTeX
@inproceedings{phillips2018improved,
  author = {Jeff M. Phillips and Wai Ming Tai},
  title = {{Improved Coresets for Kernel Density Estimates}},
  booktitle = {SODA},
  year = {2018},
  doi = {10.1137/1.9781611975031.173},
}
Figure