2026-08-10T21:42:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8779 2024-03-06T10:42:38Z ddc:004 open_access

Near-Optimal Coresets of Kernel Density Estimates Phillips, Jeff M. Tai, Wai Ming Coresets Kernel Density Estimate Discrepancy We construct near-optimal coresets for kernel density estimate for points in R^d when the kernel is positive definite. Specifically we show a polynomial time construction for a coreset of size O(sqrt{d log (1/epsilon)}/epsilon), and we show a near-matching lower bound of size Omega(sqrt{d}/epsilon). The upper bound is a polynomial in 1/epsilon improvement when d in [3,1/epsilon^2) (for all kernels except the Gaussian kernel which had a previous upper bound of O((1/epsilon) log^d (1/epsilon))) 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jeff M. Phillips and Wai Ming Tai 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.66 urn:nbn:de:0030-drops-87797 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.66 eng https://creativecommons.org/licenses/by/3.0/legalcode