2026-07-21T23:51:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16071 2024-03-06T10:56:53Z ddc:004 open_access

Optimal Coreset for Gaussian Kernel Density Estimation Tai, Wai Ming Discrepancy Theory Kernel Density Estimation Coreset Given a point set P ⊂ ℝ^d, the kernel density estimate of P is defined as 𝒢-_P(x) = 1/|P| ∑_{p ∈ P}e^{-∥x-p∥²} 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Wai Ming Tai 2022 Is Part Of LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2022.63 urn:nbn:de:0030-drops-160719 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.63 eng https://creativecommons.org/licenses/by/4.0/legalcode