Learning mixtures of separated nonspherical Gaussians

Abstract

Mixtures of Gaussian (or normal) distributions arise in a variety of application areas. Many heuristics have been proposed for the task of finding the component Gaussians given samples from the mixture, such as the EM algorithm, a local-search heuristic from Dempster, Laird and Rubin [J. Roy. Statist. Soc. Ser. B 39 (1977) 1-38]. These do not provably run in polynomial time. We present the first algorithm that provably learns the component Gaussians in time that is polynomial in the dimension. The Gaussians may have arbitrary shape, but they must satisfy a ``separation condition'' which places a lower bound on the distance between the centers of any two component Gaussians. The mathematical results at the heart of our proof are ``distance concentration'' results--proved using isoperimetric inequalities--which establish bounds on the probability distribution of the distance between a pair of points generated according to the mixture. We also formalize the more general problem of max-likelihood fit of a Gaussian mixture to unstructured data.

Published at http://dx.doi.org/10.1214/105051604000000512 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• A Two-round Variant of EM for Gaussian Mixtures

Cited by in corpus (26)

• Causal Effect Inference with Deep Latent-Variable Models
• An Analysis of the t-SNE Algorithm for Data Visualization
• Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences
• Analyzing Tensor Power Method Dynamics in Overcomplete Regime
• Learning Mixtures of Gaussians using the k-means Algorithm
• On Bayes Risk Lower Bounds
• Statistical Convergence of the EM Algorithm on Gaussian Mixture Models
• IAN: Iterated Adaptive Neighborhoods for manifold learning and dimensionality estimation
• Theoretical Analysis of the $k$-Means Algorithm - A Survey
• Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders
• Coresets for Gaussian Mixture Models of Any Shape
• Mixture Models, Robustness, and Sum of Squares Proofs
• Convex Relaxations of Bregman Divergence Clustering
• Adversarially Robust Low Dimensional Representations
• Near-optimal Sample Complexity Bounds for Robust Learning of Gaussians Mixtures via Compression Schemes
• List-Decodable Mean Estimation in Nearly-PCA Time
• On the Behavior of the Expectation-Maximization Algorithm for Mixture Models
• Clustering with Tangles: Algorithmic Framework and Theoretical Guarantees
• Learning Arbitrary Statistical Mixtures of Discrete Distributions
• Learning Mixtures of Arbitrary Distributions over Large Discrete Domains
• An Online Algorithm for Learning Selectivity to Mixture Means
• Autoencoders Learn Generative Linear Models
• Dimension reduction for data of unknown cluster structure
• Optimal estimation of high-dimensional location Gaussian mixtures
• Algorithms for finding $k$ in $k$-means
• A Fourier analytique approach to Gaussian mixture learning