Settling the Polynomial Learnability of Mixtures of Gaussians

Abstract

Given data drawn from a mixture of multivariate Gaussians, a basic problem is to accurately estimate the mixture parameters. We give an algorithm for this problem that has a running time, and data requirement polynomial in the dimension and the inverse of the desired accuracy, with provably minimal assumptions on the Gaussians. As simple consequences of our learning algorithm, we can perform near-optimal clustering of the sample points and density estimation for mixtures of k Gaussians, efficiently. The building blocks of our algorithm are based on the work Kalai et al. [STOC 2010] that gives an efficient algorithm for learning mixtures of two Gaussians by considering a series of projections down to one dimension, and applying the method of moments to each univariate projection. A major technical hurdle in Kalai et al. is showing that one can efficiently learn univariate mixtures of two Gaussians. In contrast, because pathological scenarios can arise when considering univariate projections of mixtures of more than two Gaussians, the bulk of the work in this paper concerns how to leverage an algorithm for learning univariate mixtures (of many Gaussians) to yield an efficient algorithm for learning in high dimensions. Our algorithm employs hierarchical clustering and rescaling, together with delicate methods for backtracking and recovering from failures that can occur in our univariate algorithm. Finally, while the running time and data requirements of our algorithm depend exponentially on the number of Gaussians in the mixture, we prove that such a dependence is necessary.

arXiv comment43 pages, 2 figures

References in corpus (2)

• A Two-round Variant of EM for Gaussian Mixtures
• Learning Gaussian Mixtures with Arbitrary Separation

Cited by in corpus (31)

• A Spectral Algorithm for Latent Dirichlet Allocation
• A Method of Moments for Mixture Models and Hidden Markov Models
• The More, the Merrier: the Blessing of Dimensionality for Learning Large Gaussian Mixtures
• Analyzing Tensor Power Method Dynamics in Overcomplete Regime
• Training Gaussian Mixture Models at Scale via Coresets
• Learning mixtures of spherical Gaussians: moment methods and spectral decompositions
• A Latent Source Model for Online Collaborative Filtering
• On learning parametric-output HMMs
• Statistical Convergence of the EM Algorithm on Gaussian Mixture Models
• Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables
• Learning Mixtures of Linear Regressions with Nearly Optimal Complexity
• Learning Binary Latent Variable Models: A Tensor Eigenpair Approach
• Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval
• Theoretical Analysis of the $k$-Means Algorithm - A Survey
• Learning High-Dimensional Mixtures of Graphical Models
• Spectral Approaches to Nearest Neighbor Search
• An Alternative to EM for Gaussian Mixture Models: Batch and Stochastic Riemannian Optimization
• Fourier PCA and Robust Tensor Decomposition
• Provable Sparse Tensor Decomposition
• On the Behavior of the Expectation-Maximization Algorithm for Mixture Models
• Sparse Solutions to Nonnegative Linear Systems and Applications
• Learning Mixtures of Arbitrary Distributions over Large Discrete Domains
• Matching while Learning
• On Convergence of Epanechnikov Mean Shift
• Generalized Topic Modeling
• Learning Arbitrary Statistical Mixtures of Discrete Distributions
• Some techniques in density estimation
• Dimension reduction for data of unknown cluster structure
• Learning Mixtures of Permutations: Groups of Pairwise Comparisons and Combinatorial Method of Moments
• Diversity in Spectral Learning for Natural Language Parsing
• Geometric Methods for Robust Data Analysis in High Dimension