Stronger Coreset Bounds for Kernel Density Estimators via Chaining

Kernel density estimation is a fundamental nonparametric method for estimating probability densities, but its computational cost scales with the number of data points. Coresets provide a compact representation of the data while approximately preserving the resulting kernel density estimate. We give improved bounds on the coreset complexity of a broad class of kernels by combining a discrepancy-theoretic approach with a chaining argument. For uniformly bounded data, we give randomized polynomial-time algorithms that construct coresets of size $O\left(\frac{\sqrt{d}}{\epsilon }\sqrt{\log \log \frac{1}{\epsilon }}\right)$ for the Gaussian and Laplacian kernels, improving the best bounds obtainable using previous discrepancy-based techniques. For the Laplacian kernel in constant dimension, we additionally obtain coresets of size $O\left(\frac{1}{\epsilon }\sqrt{\log \log \frac{1}{\epsilon }}\right).$ We further establish bounds of $O\left(\frac{\sqrt{d}}{\epsilon }\sqrt{\log (2\max \{1,\alpha \})}\right)$ for the exponential, Hellinger, and Jensen-Shannon kernels, where $(1/\alpha )$ denotes the kernel bandwidth. Our results show how chaining techniques can sharpen discrepancy-based guarantees for kernel methods and also offer data-aware bounds for coreset complexity.