Near-Optimal Coresets of Kernel Density Estimates

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.