# Near-Optimal Coresets of Kernel Density Estimates

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Feb 2018.

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

- [Kernel Thinning](https://mlsanity.com/paper/2105.05842/) (2021)
- [Generalized Kernel Thinning](https://mlsanity.com/paper/2110.01593/) (2021)
- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Distribution Compression in Near-linear Time](https://mlsanity.com/paper/2111.07941/) (2021)
- [Learnware: Small Models Do Big](https://mlsanity.com/paper/2210.03647/) (2022)
- [Streaming Attention Approximation via Discrepancy Theory](https://mlsanity.com/paper/2502.07861/) (2025)
- [Fast Private Kernel Density Estimation via Locality Sensitive Quantization](https://mlsanity.com/paper/2307.01877/) (2023)
- [Efficiently Computing Similarities to Private Datasets](https://mlsanity.com/paper/2403.08917/) (2024)
- [Faster Kernel Matrix Algebra via Density Estimation](https://mlsanity.com/paper/2102.08341/) (2021)
- [DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2107.02736/) (2021)
- [Low-Rank Thinning](https://mlsanity.com/paper/2502.12063/) (2025)
- [Dynamic Maintenance of Kernel Density Estimation Data Structure: From Practice to Theory](https://mlsanity.com/paper/2208.03915/) (2022)
- [Introduction to Coresets: Approximated Mean](https://mlsanity.com/paper/2111.03046/) (2021)
- [Deep Active Learning in the Presence of Label Noise: A Survey](https://mlsanity.com/paper/2302.11075/) (2023)
- [No Dimensional Sampling Coresets for Classification](https://mlsanity.com/paper/2402.05280/) (2024)
- [Nearly Optimal Attention Coresets](https://mlsanity.com/paper/2605.05602/) (2026)
- [Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation](https://mlsanity.com/paper/2212.00642/) (2022)
- [Dimensionality Reduction for General KDE Mode Finding](https://mlsanity.com/paper/2305.18755/) (2023)
- [Compressed Empirical Measures (in finite dimensions)](https://mlsanity.com/paper/2204.08847/) (2022)
- [Differentially Private Synthetic Data Using KD-Trees](https://mlsanity.com/paper/2306.13211/) (2023)
- [Stronger Coreset Bounds for Kernel Density Estimators via Chaining](https://mlsanity.com/paper/2310.08548/) (2023)
- [New Bounds for Kernel Sums via Fast Spherical Embeddings](https://mlsanity.com/paper/2605.01263/) (2026)
- [Density Sketches for Sampling and Estimation](https://mlsanity.com/paper/2102.12301/) (2021)
- [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)
- [Scalable Learning of Multivariate Distributions via Coresets](https://mlsanity.com/paper/2603.19792/) (2026)
- [TabKDE: Simple and Scalable Tabular Data Generation with Kernel Density Estimates](https://mlsanity.com/paper/2605.17642/) (2026)
- [Amortized quadrature for posterior expectations in inverse problems](https://mlsanity.com/paper/2606.15871/) (2026)
- [Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions](https://mlsanity.com/paper/2609.06327/) (2026)

## Abstract (arXiv)

We construct near-optimal coresets for kernel density estimates for points in ℝd when the kernel is positive definite. Specifically we show a polynomial time construction for a coreset of size O(√d/varepsilon· √log 1/varepsilon ), and we show a near-matching lower bound of size Omega(min√d/varepsilon, 1/varepsilon2). When d≥ 1/varepsilon2, it is known that the size of coreset can be O(1/varepsilon2). The upper bound is a polynomial-in-(1/varepsilon) improvement when d ∈ [3,1/varepsilon2) 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.