# Optimal Coreset for Gaussian Kernel Density Estimation

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jul 2020.

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

- [No Dimensional Sampling Coresets for Classification](https://mlsanity.com/paper/2402.05280/) (2024)
- [Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation](https://mlsanity.com/paper/2212.00642/) (2022)
- [Stronger Coreset Bounds for Kernel Density Estimators via Chaining](https://mlsanity.com/paper/2310.08548/) (2023)
- [Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical](https://mlsanity.com/paper/2209.01147/) (2022)
- [Dimension-Independent Kernel ε-Covers](https://mlsanity.com/paper/2306.16516/) (2023)
- [Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions](https://mlsanity.com/paper/2609.06327/) (2026)

## Abstract (arXiv)

Given a point set Psubset ℝd, the kernel density estimate of P is defined as [ overlineGP(x) = frac1left|Pright|sump∈ Pe-leftlVert x-p rightrVert2 ] for any x∈ℝd. We study how to construct a small subset Q of P such that the kernel density estimate of P is approximated by the kernel density estimate of Q. This subset Q is called a coreset. The main technique in this work is constructing a ± 1 coloring on the point set P by discrepancy theory and we leverage Banaszczyk's Theorem. When d>1 is a constant, our construction gives a coreset of size Oleft(frac1varepsilonright) as opposed to the best-known result of Oleft(frac1varepsilon√logfrac1varepsilonright). It is the first result to give a breakthrough on the barrier of √log factor even when d=2.