Near-Optimal Coresets of Kernel Density Estimates
This work addresses efficient data summarization for kernel methods in machine learning, offering significant theoretical advances with practical implications for large-scale data analysis.
The paper tackles the problem of constructing coresets for kernel density estimates in high-dimensional spaces, achieving a near-optimal coreset size of O(√d/ε·√log 1/ε) with a matching lower bound of Ω(min{√d/ε, 1/ε²}), providing polynomial improvements for dimensions between 3 and 1/ε².
We construct near-optimal coresets for kernel density estimates for points in $\mathbb{R}^d$ when the kernel is positive definite. Specifically we show a polynomial time construction for a coreset of size $O(\sqrt{d}/\varepsilon\cdot \sqrt{\log 1/\varepsilon} )$, and we show a near-matching lower bound of size $Ω(\min\{\sqrt{d}/\varepsilon, 1/\varepsilon^2\})$. When $d\geq 1/\varepsilon^2$, it is known that the size of coreset can be $O(1/\varepsilon^2)$. The upper bound is a polynomial-in-$(1/\varepsilon)$ improvement when $d \in [3,1/\varepsilon^2)$ 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.