Improved Coresets for Kernel Density Estimates

Jeff M. Phillips, Wai Ming Tai

This paper, presented by researchers from the University of Utah, provides a theoretical breakthrough in how we compress large datasets for Kernel Density Estimation (KDE). By refining the analysis of iterative algorithms and leveraging tools from discrepancy theory, the authors establish new, tighter bounds on the size of "coresets"—small subsets of data that can stand in for the massive original set with minimal loss in accuracy.

TL;DR

The authors prove that for common kernels like Gaussian and Laplace, you can approximate a massive dataset with a tiny "coreset" of size $2/\epsilon^2$ to achieve an $L_\infty$ error of $\epsilon$, regardless of the data's dimensionality or spread. For Gaussian kernels in fixed dimensions, they further improve this bound to near-linear in $1/\epsilon$, significantly outperforming previous polynomial bounds.

What Problem Does This Paper Address?

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 has a major scaling problem: to calculate the density at a single point, you must sum the contributions of all $n$ points in your dataset. If you have millions of points, this becomes computationally prohibitive.

A coreset is a small subset $Q$ of the original points $P$ such that the KDE calculated using only $Q$ is very close to the KDE calculated using the full set $P$. The challenge is determining exactly how small $Q$ can be while guaranteeing a maximum error ($\epsilon$). Previous research often produced bounds that depended on the "bandwidth" (smoothing parameter) of the kernel or the physical diameter of the point set—factors that can make coresets impractically large in real-world scenarios.

Methods

The paper approaches the problem through two primary lenses:

  1. Frank-Wolfe Analysis (Kernel Herding): The authors analyze a greedy iterative algorithm known as "kernel herding." In each step, the algorithm picks 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 show that the problem of finding a kernel coreset can be mapped to the "axis-aligned rectangle discrepancy" problem. Essentially, if you can find a way to color points $+1$ and $-1$ such that every axis-aligned box is "balanced," you have also found a good coreset for a Gaussian KDE.
  3. Mathematical Lower Bounds: To test the limits of their theories, the authors construct a worst-case high-dimensional point set (using a scaled canonical basis) to prove that certain error bounds cannot be improved further.

Datasets

As a theoretical contribution, this paper does not use empirical datasets (like MNIST or ImageNet). Instead, it uses mathematical constructions to prove its theorems. Specifically, it defines a point set $P$ in $\mathbb{R}^n$ where points are placed along the axes to demonstrate the $\Omega(1/\epsilon^2)$ lower bound for high-dimensional data.

Key Insights and Ideas

  • Dimension Independence: One of the most striking findings is that for "characteristic kernels" (like Gaussian and Laplace), 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.
  • The Gaussian-Rectangle Connection: The authors realized that because the Gaussian kernel is "multiplicatively separable" (it can be broken down into a product of 1D functions), it shares deep mathematical properties with axis-aligned rectangles. This allowed them to apply decades of research from combinatorial geometry to the KDE problem.
  • Tightness of Bounds: The paper settles a long-standing question by proving that the $1/\epsilon^2$ bound is "tight" for high dimensions. This means that without making assumptions about the data's structure, we cannot expect to find smaller general-purpose coresets.

Key Results

  • General Bound: For any characteristic kernel, a coreset of size $2/\epsilon^2$ is sufficient to ensure the $L_\infty$ error is less than $\epsilon$.
  • 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.

Limitations and Future Work

  • Kernel Specificity: The significant improvement in low dimensions ($O(\frac{1}{\epsilon} \log^d \frac{1}{\epsilon})$) relies heavily on the separability of the Gaussian kernel. It is currently unclear if similar improvements can be made for non-separable kernels like the Laplace kernel in low dimensions.
  • The "Poly-log" Gap: While the new bounds are much tighter, there is still a small gap between the best constructive upper bound and the non-constructive lower bound (a difference of $\sqrt{\log(1/\epsilon)}$).
  • Algorithmic Complexity: While the bounds are constructive, the algorithms derived from discrepancy theory can be complex to implement compared to the simpler Frank-Wolfe approach. Future work could focus on more practical, efficient implementations of these discrepancy-based coresets.

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∞ error between kernel density estimates within error ε, with coreset size 4/ε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 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 , and non-constructively, this can be improved by . This improves the best constant dimension bounds polynomially for d ≥ 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},
}

Loading related content...

Figure