Optimal Coreset for Gaussian Kernel Density Estimation

Given a point set Psubset ℝd, the kernel density estimate of P is defined as [ overlineGP(x) = frac1left|Pright|sump∈ Pe-leftlVert x-p rightrVert2 ] 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 Oleft(frac1varepsilonright) as opposed to the best-known result of Oleft(frac1varepsilon√logfrac1varepsilonright). It is the first result to give a breakthrough on the barrier of √log factor even when d=2.