Near-Optimal Coresets of Kernel Density Estimates

Jeff M. Phillips, Wai Ming Tai

TL;DR

This paper introduces a new, near-optimal method for creating "coresets" for kernel density estimates (KDEs). These coresets are significantly smaller subsets of data that can approximate the original KDE with high accuracy, offering a substantial improvement in efficiency for large datasets and a wider range of kernel functions, including those previously challenging to handle.

What Problem Does This Paper Address?

Kernel Density Estimation (KDE) is a fundamental technique in data analysis for estimating probability distributions from data points. However, computing a KDE for a large dataset can be computationally expensive, often requiring O(n) time for each query point, where 'n' is the number of data points. To address this, researchers have developed "coresets" – smaller subsets of the original data that can approximate the full KDE. The challenge has been to find coresets that are both small in size and provide accurate approximations across a broad spectrum of kernel functions, especially those commonly used in machine learning. Previous methods often relied on strong assumptions about the kernel (like being "characteristic" or having bounded VC-dimension for super-level sets), limiting their applicability. This paper aims to bridge this gap by providing a more general and efficient coreset construction for positive definite kernels.

Methods

The paper's core contribution lies in developing a new algorithm for constructing an $\epsilon$-KDE coreset of size $O(\sqrt{d \log(1/\epsilon)}/\epsilon)$, where $d$ is the data dimension and $\epsilon$ is the desired approximation error. This is achieved by reducing the KDE coreset problem to a kernel discrepancy problem. The authors leverage a technique based on assigning a coloring to the data points and recursively halving the set. A key innovation is the direct reduction of the kernel discrepancy problem to the 2-norm, bypassing more complex reductions. This approach relies on the positive definiteness of the kernel, which allows for a specific matrix decomposition.

For the lower bound, the authors construct a challenging dataset and kernel that demonstrate a near-matching lower bound of $\Omega(\sqrt{d}/\epsilon)$ for the coreset size. This construction requires kernels to be rotation- and shift-invariant, and "somewhere steep."

Datasets

The paper does not introduce new datasets for evaluation. Instead, it focuses on theoretical constructions and analyses for general point sets $P \subset \mathbb{R}^d$. The theoretical results are demonstrated to apply to various common kernel types, including Gaussian, Laplacian, Jensen-Shannon, Hellinger, and Sinc kernels, across different domains like $\mathbb{R}^d$ and $\Delta^d$.

Key Insights and Ideas

  • Positive Definiteness is Key: The paper highlights that the positive definiteness of a kernel is a crucial property that enables efficient coreset construction, allowing for a wider range of applicable kernels than previous methods.
  • Bridging the Gap for Sinc Kernels: The work provides the first non-trivial $\epsilon$-KDE coreset result for the Sinc kernel, which is positive definite but not characteristic and can be negative, overcoming a significant limitation of prior approaches.
  • Dimension Dependence Matters: The lower bound derived, $\Omega(\sqrt{d}/\epsilon)$, is the first to explicitly depend on the dimension $d$, and this dependence matches the upper bound, suggesting a tight characterization for many kernel types.
  • Discrepancy as a Unifying Tool: The paper effectively uses the concept of kernel discrepancy as a central tool to unify the analysis of coreset construction across different kernel types.
  • Efficiency Gains: The new upper bound offers a polynomial improvement in $1/\epsilon$ for certain dimensions compared to previous results, making KDE approximation more feasible for high-dimensional data.

Key Results

  • Upper Bound: An $\epsilon$-KDE coreset of size $O(\sqrt{d \log(1/\epsilon)}/\epsilon)$ can be constructed in polynomial time for positive definite kernels. This is a significant improvement for dimensions $d \in [3, 1/\epsilon^2)$.
  • Lower Bound: A near-matching lower bound of $\Omega(\sqrt{d}/\epsilon)$ is established for rotation- and shift-invariant, somewhere steep kernels.
  • Applicability: The results apply to a broad class of kernels, including Gaussian, Laplacian, Jensen-Shannon, Hellinger, and Sinc kernels.
  • Specific Kernel Corollaries:
    • For Gaussian and Laplacian kernels, the coreset size is $O(\sqrt{d/\epsilon} \sqrt{\log(1/\epsilon)})$, with a lower bound of $\Omega(\sqrt{d}/\epsilon)$.
  • For Jensen-Shannon and Hellinger kernels, the coreset size is $O(\sqrt{d/\epsilon} \sqrt{\log(1/\epsilon)})$.
  • For Sinc kernels (in $\mathbb{R}^d$ for $d \in \{1,2,3\}$), the coreset size is $O(\sqrt{d/\epsilon} \sqrt{\log(1/\epsilon)})$, with a lower bound of $\Omega(1/\epsilon)$.

Limitations and Future Work

  • Log Factor: While the upper bound is near-optimal, it includes a $\log(1/\epsilon)$ factor that is not present in the lower bound for certain cases (e.g., Gaussian kernels). The authors suggest that this factor might be removable, especially in well-behaved settings.
  • Generalization to Discrete Domains: The paper notes that while the core technique of decomposing the Gram matrix can extend to discrete domains (like graphs or trees), generating the finite Gram or discrepancy matrix efficiently for these objects remains an open challenge.
  • Lower Bound Conditions: The lower bound relies on specific kernel properties (rotation- and shift-invariance, somewhere steep) that might not hold for all kernels.
  • Future Work: The authors propose exploring whether the $\log(1/\epsilon)$ factor in the upper bound can be eliminated and investigating how to efficiently construct the necessary matrices for more complex, discrete data domains.

Summary updated

Abstract

We construct near-optimal coresets for kernel density estimate for points in R^d when the kernel is positive definite. Specifically we show a polynomial time construction for a coreset of size O(sqrt{d log (1/epsilon)}/epsilon), and we show a near-matching lower bound of size Omega(sqrt{d}/epsilon). The upper bound is a polynomial in 1/epsilon improvement when d in [3,1/epsilon^2) (for all kernels except the Gaussian kernel which had a previous upper bound of O((1/epsilon) log^d (1/epsilon))) and the lower bound is the first known lower bound to depend on d for this problem. Moreover, the upper bound restriction that the kernel is positive definite is significant in that it applies to a wide-variety of kernels, specifically those most important for machine learning. This includes kernels for information distances and the sinc kernel which can be negative.
BibTeX
@article{phillips2020near,
  author = {Jeff M. Phillips and Wai Ming Tai},
  title = {{Near-Optimal Coresets of Kernel Density Estimates}},
  journal = {Discret. Comput. Geom.},
  year = {2020},
  doi = {10.1007/s00454-019-00134-6},
}
Figure