Settling the Polynomial Learnability of Mixtures of Gaussians

By Ankur Moitra, Gregory Valiant. IEEE Annual Symposium on Foundations of Computer Science, 2010

355 citations recorded by the source corpus.

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 running time and data requirements polynomial in the dimension and the inverse of the desired accuracy, with provably minimal assumptions on the Gaussians. As a simple consequence of our learning algorithm, we we give the first polynomial time algorithm for proper density estimation for mixtures of k Gaussians that needs no assumptions on the mixture. It was open whether proper density estimation was even statistically possible (with no assumptions) given only polynomially many samples, let alone whether it could be computationally efficient. The building blocks of our algorithm are based on the work (Kalai \emph{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 the previous work is showing that one can efficiently learn univariate mixtures of two Gaussians. In contrast, because pathological scenarios can arise when considering projections of mixtures of more than two Gaussians, the bulk of the work in this paper concerns how to leverage a weaker algorithm for learning univariate mixtures (of many Gaussians) to learn in high dimensions. Our algorithm employs hierarchical clustering and rescaling, together with methods for backtracking and recovering from the 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.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/e3b7d9921955b698ca37cc8e1108d8b45cc9c6e0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

A Method of Moments for Mixture Models and Hidden Markov Models (2012, methodology): “Like the moment methods of Moitra and Valiant (2010) and Belkin and Sinha (2010), our algorithm does not require a separation condition; but unlike those previous methods, the algorithm has computational and sample complexity polynomial in k .”
Robust Estimators in High Dimensions without the Computational Intractability (2016, background): “…learning several fundamental classes of high-dimensional distributions: (1) a single Gaussian, (2) a product distribution on the hypercube, (3) mixtures of two product distributions (under a natural balancedness condition), and (4) mixtures of k Gaussians with identical spherical covariances.”
List-decodable robust mean estimation and learning mixtures of spherical gaussians (2017, methodology): “The related problems of density estimation and proper learning for GMMs have also been extensively studied [1, 20, 28, 38, 39, 46].”
Outlier-robust moment-estimation via sum-of-squares (2017, background): “…is that for many parameter estimation problems the best known algorithms in terms of provable guarantees are based on the method of moments , which means that they don’t require direct access to a sample from the distribution but instead only to its low-degree moments (e.g. [Pea94, KMV10, MV10]).”
Better Agnostic Clustering Via Relaxed Tensor Norms (2017, background): “( If the cluster means are in general position, other lines of work yields results for Gaussians [ KMV10, MV10, BS10, HK13, BCV14, GVX14, BCMV14, ABG + 14, GHK15] or for distributions satisfying independence assumptions [HKZ09, AGH + 13].”
Agnostic Estimation of Mean and Covariance (2016, background): “For example, for a mixture of k Gaussians in R n , it is known that the sample and time complexity are bounded by n O ( k ) in general [KMV10, MV10, BS10] and by poly( n, k ) under natural separation assumptions [Das99, SK01, VW04, DS07, CR08, BV08, HK13].”
When can Wasserstein GANs minimize Wasserstein Distance? (2020, methodology): “Method of Moments has been used in many other machine learning problems such as mixture of Gaussian distribution [35, 27], topic models [1], hidden Markov models [2], dictionary learning [5], mixture of linear regression [20] and so on, and has been used to design practical GANs [19] as well.”
Scalable Training of Mixture Models via Coresets (2011, background): “Recently, [18] and [19] provide algorithms with polynomial running time (except exponential dependence on k) and sample complexity for arbitrary GMMs.”
Training Gaussian Mixture Models at Scale via Coresets (2017, background): “Moitra and Valiant (2010) and Belkin and Sinha (2010) prove that arbitrary GMMs with ﬁxed number of components can be learned in polynomial time and sample complexity (but exponential dependence on k ).”
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures (2016, methodology): “In the past few decades, a long line of work within TCS [57], [21], [4], [72], [11], [53], [65], [6], [24], [25], [14], [23], [15], [16], [1], [27], [22], [33], [32] has focused on designing efficient estimators in a variety of settings.”
Tensor decompositions for learning latent variable models (2012, background): “This was employed for parameter estimation of discrete Markov models [Cha96] using pair-wise and triple-wise probability tables, and later for other latent variable models such as hidden Markov models (HMMs), latent trees, Gaussian mixture models, and topic models such as latent Dirichlet allocation”
Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees (2018, neutral): “constant number of Gaussian distributions [48].”
Learning mixtures of spherical gaussians: moment methods and spectral decompositions (2012, background): “Recent work from [22] demonstrates an information-theoretic barrier to estimation for general Gaussian mixture models.”
A Spectral Algorithm for Latent Dirichlet Allocation (2012, background): “Both SVDs are performed on matrices of size k × k, where k is the number of latent factors, making the algorithm scalable (typically the dimension of the observed space d≫ k).”