2020/07/15 by Tai, Wai Ming
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.2007.08031
Given a point set P⊂ ℝd, the kernel density estimate of P is defined as GP(x) = (1)/(|P|)∑p∈ Pe-‖ x-p ‖2 for any x∈ℝd. We study how to construct a small subset Q of P such that the kernel density estimate of P is approximated by the kernel density estimate of Q. This subset Q is called a coreset. The main technique in this work is constructing a ± 1 coloring on the point set P by discrepancy theory and we leverage Banaszczyk's Theorem. When d>1 is a constant, our construction gives a coreset of size O((1)/(ε)) as opposed to the best-known result of O((1)/(ε)√(log(1)/(ε))). It is the first result to give a breakthrough on the barrier of √(log) factor even when d=2.