# Improved Coresets for Kernel Density Estimates

arXiv: https://arxiv.org/abs/1710.04325 · HTML: https://mlsanity.com/paper/1710.04325/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Oct 2017.

## Built on by (most cited first, 8 of 8)

- [Kernel Thinning](https://mlsanity.com/paper/2105.05842/) (2021)
- [New Coresets for Projective Clustering and Applications](https://mlsanity.com/paper/2203.04370/) (2022)
- [Faster Kernel Matrix Algebra via Density Estimation](https://mlsanity.com/paper/2102.08341/) (2021)
- [No Dimensional Sampling Coresets for Classification](https://mlsanity.com/paper/2402.05280/) (2024)
- [Supervised Kernel Thinning](https://mlsanity.com/paper/2410.13749/) (2024)
- [Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation](https://mlsanity.com/paper/2212.00642/) (2022)
- [Density Sketches for Sampling and Estimation](https://mlsanity.com/paper/2102.12301/) (2021)
- [Scalable Learning of Multivariate Distributions via Coresets](https://mlsanity.com/paper/2603.19792/) (2026)

## Abstract (arXiv)

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 2/ε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 O(frac1ε logd frac1ε), and non-constructively, this can be improved by √log frac1ε. This improves the best constant dimension bounds polynomially for d ≥ 3.