Coresets for Gaussian Mixture Models of Any Shape

Abstract

An $\epsilon$-coreset for a given set $D$ of $n$ points, is usually a small weighted set, such that querying the coreset \emph{provably} yields a $(1+\epsilon )$-factor approximation to the original (full) dataset, for a given family of queries. Using existing techniques, coresets can be maintained for streaming, dynamic (insertion/deletions), and distributed data in parallel, e.g. on a network, GPU or cloud. We suggest the first coresets that approximate the negative log-likelihood for $k$-Gaussians Mixture Models (GMM) of arbitrary shapes (ratio between eigenvalues of their covariance matrices). For example, for any input set $D$ whose coordinates are integers in $[-n^{100},n^{100}]$ and any fixed $k,d\ge 1$, the coreset size is $(\log n{)}^{O(1)}/{\epsilon }^2$, and can be computed in time near-linear in $n$, with high probability. The optimal GMM may then be approximated quickly by learning the small coreset. Previous results [NIPS'11, JMLR'18] suggested such small coresets for the case of semi-speherical unit Gaussians, i.e., where their corresponding eigenvalues are constants between $\frac{1}{2\pi }$ to $2\pi$. Our main technique is a reduction between coresets for $k$-GMMs and projective clustering problems. We implemented our algorithms, and provide open code, and experimental results. Since our coresets are generic, with no special dependency on GMMs, we hope that they will be useful for many other functions.

References in corpus (10)

• Searching for Exotic Particles in High-Energy Physics with Deep Learning
• Polynomial Learning of Distribution Families
• Learning mixtures of separated nonspherical Gaussians
• Near-optimal Coresets For Least-Squares Regression
• VC dimension of ellipsoids
• Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and more
• Coresets for Kinematic Data: From Theorems to Real-Time Systems
• Randomized Composable Coresets for Matching and Vertex Cover
• Aligning Points to Lines: Provable Approximations
• Secure Search on the Cloud via Coresets and Sketches

Cited by in corpus (4)

• Adversarial Robustness of Streaming Algorithms through Importance Sampling
• Coresets for Clustering with Missing Values
• Coresets for Regressions with Panel Data
• Coresets for Time Series Clustering