# Stronger Coreset Bounds for Kernel Density Estimators via Chaining

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 26 references that are in the map.
- First posted on arXiv 12 Oct 2023.

## Builds on (most cited first, 7 of 7)

- [Near-Optimal Coresets of Kernel Density Estimates](https://mlsanity.com/paper/1802.01751/) (2018)
- [Discrepancy, Coresets, and Sketches in Machine Learning](https://mlsanity.com/paper/1906.04845/) (2019)
- [Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering](https://mlsanity.com/paper/1501.02056/) (2015)
- [Confidence sets for persistence diagrams](https://mlsanity.com/paper/1303.7117/) (2013)
- [The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues](https://mlsanity.com/paper/1708.01079/) (2017)
- [Optimal Coreset for Gaussian Kernel Density Estimation](https://mlsanity.com/paper/2007.08031/) (2020)
- [Sparse Approximation of a Kernel Mean](https://mlsanity.com/paper/1503.00323/) (2015)

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

- [Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions](https://mlsanity.com/paper/2609.06327/) (2026)

## Abstract (arXiv)

We apply the discrepancy method and a chaining approach to give improved bounds on the coreset complexity of a wide class of kernel functions. Our results give randomized polynomial time algorithms to produce coresets of size Obig(frac√dvarepsilon√loglog frac1varepsilonbig) for the Gaussian and Laplacian kernels in the case that the data set is uniformly bounded, an improvement that was not possible with previous techniques. We also obtain coresets of size Obig(frac1varepsilon√loglog frac1varepsilonbig) for the Laplacian kernel for d constant. Finally, we give the best known bounds of Obig(frac√dvarepsilon√log(2max1,α)big) on the coreset complexity of the exponential, Hellinger, and JS Kernels, where 1/α is the bandwidth parameter of the kernel.