Near-optimal coresets of kernel density estimates

DOI10.1007/S00454-019-00134-6MaRDI QIDQ2189735zbMATH OpenOpenAlexWikidataFDO

Authors Jeff M. Phillips, Wai Ming Tai

Publication date 16 June 2020

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.01751, https://drops.dagstuhl.de/opus/volltexte/2018/8779/

zbMATH Keywords

coresetdiscrepancy theorykernel density estimate

Mathematics Subject Classification ID

Nonparametric estimation (62G05) Density estimation (62G07) Asymptotic properties of nonparametric inference (62G20) Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Abstract: We construct near-optimal coresets for kernel density estimates for points in $mathbb{R}^d$ when the kernel is positive definite. Specifically we show a polynomial time construction for a coreset of size $O(sqrtd/varepsiloncdotsqrtlog1/varepsilon)$, and we show a near-matching lower bound of size $Omega(minsqrtd/varepsilon,1/varepsilo{n}^2)$. When $dgeq1/varepsilo{n}^2$, it is known that the size of coreset can be $O(1/varepsilo{n}^2)$. The upper bound is a polynomial-in-$(1/varepsilon)$ improvement when $din[3,1/varepsilo{n}^2)$ 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.

Recommendations

• Near-optimal coresets of kernel density estimates
• Improved coresets for kernel density estimates
• scientific article; zbMATH DE number 7164768
• Coresets for polytope distance
• Coresets for Discrete Integration and Clustering

Cites work

• -samples for kernels
• A kernel two-sample test
• Clustering to minimize the maximum intercluster distance
• Comparing distributions and shapes using the kernel distance
• Confidence sets for persistence diagrams
• Convergence Rates for Conditional Gradient Sequences Generated by Implicit Step Length Rules
• Coresets for polytope distance
• Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
• Factorization norms and hereditary discrepancy
• Generalized density clustering
• Geometric discrepancy. An illustrated guide
• Geometric inference on kernel density estimates
• Hilbert space embeddings and metrics on probability measures
• scientific article; zbMATH DE number 991833 (Why is no real title available?)
• scientific article; zbMATH DE number 3870398 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 1380581 (Why is no real title available?)
• scientific article; zbMATH DE number 4001209 (Why is no real title available?)
• scientific article; zbMATH DE number 837911 (Why is no real title available?)
• Improved bounds on the sample complexity of learning
• Improved coresets for kernel density estimates
• Integral Probability Metrics and Their Generating Classes of Functions
• Kernel Mean Embedding of Distributions: A Review and Beyond
• Kernel methods in machine learning
• Local outlier detection reconsidered: a generalized view on locality with applications to spatial, video, and network outlier detection
• Metric spaces and completely monontone functions
• New analysis and results for the Frank-Wolfe method
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• On the estimation of the gradient lines of a density and the consistency of the mean-shift algorithm
• On the Nyström method for approximating a gram matrix for improved kernel-based learning
• Sparse Approximation of a Kernel Mean
• The Gram-Schmidt walk: a cure for the Banaszczyk blues
• Theory of Reproducing Kernels
• Topological consistency via kernel estimation

Cited in

(10)

• Improved coresets for kernel density estimates
• Near-optimal coresets of kernel density estimates
• Coresets for polytope distance
• -samples for kernels
• Optimal coreset for Gaussian kernel density estimation
• Emerging directions in Bayesian computation
• Coresets for kernel clustering
• Finer-grained hardness of kernel density estimation
• Dimension-independent kernel -covers
• Compressed empirical measures (in finite dimensions)

This page was built for publication: Near-optimal coresets of kernel density estimates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2189735)