Near-Optimal Coresets of Kernel Density Estimates

2018/02/06 by Phillips, Jeff M., Tai, Wai Ming · 3 citations
#Computational Geometry (cs.CG) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1802.01751

Abstract

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)/ε⋅ √(log 1/ε) ), and we show a near-matching lower bound of size Ω(min\√(d)/ε, 1/ε²\). When d≥ 1/ε², it is known that the size of coreset can be O(1/ε²). The upper bound is a polynomial-in-(1/ε) improvement when d ∈ [3,1/ε²) 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.

Cited by

• The Expiration Streaming Model: Diameter, k-Center, Counting, Sampling, and Friends
• Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
• An Improved Bound for the Beck-Fiala Conjecture

Related

• Improved Coresets for Kernel Density Estimates
• Optimal Coreset for Gaussian Kernel Density Estimation
• Stronger Coreset Bounds for Kernel Density Estimators via Chaining
• A Statistical Perspective on Coreset Density Estimation
• Hashing-Based-Estimators for Kernel Density in High Dimensions