Learning Mixtures of Gaussians in High Dimensions

Abstract

Efficiently learning mixture of Gaussians is a fundamental problem in statistics and learning theory. Given samples coming from a random one out of k Gaussian distributions in Rn, the learning problem asks to estimate the means and the covariance matrices of these Gaussians. This learning problem arises in many areas ranging from the natural sciences to the social sciences, and has also found many machine learning applications. Unfortunately, learning mixture of Gaussians is an information theoretically hard problem: in order to learn the parameters up to a reasonable accuracy, the number of samples required is exponential in the number of Gaussian components in the worst case. In this work, we show that provided we are in high enough dimensions, the class of Gaussian mixtures is learnable in its most general form under a smoothed analysis framework, where the parameters are randomly perturbed from an adversarial starting point. In particular, given samples from a mixture of Gaussians with randomly perturbed parameters, when n > Ω(k^2), we give an algorithm that learns the parameters with polynomial running time and using polynomial number of samples. The central algorithmic ideas consist of new ways to decompose the moment tensor of the Gaussian mixture by exploiting its structural properties. The symmetries of this tensor are derived from the combinatorial structure of higher order moments of Gaussian distributions (sometimes referred to as Isserlis' theorem or Wick's theorem). We also develop new tools for bounding smallest singular values of structured random matrices, which could be useful in other smoothed analysis settings.

References in corpus (7)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Polynomial Learning of Distribution Families
• Computational Limits for Matrix Completion
• The More, the Merrier: the Blessing of Dimensionality for Learning Large Gaussian Mixtures
• Learning Mixtures of Discrete Product Distributions using Spectral Decompositions
• Learning Gaussian Mixtures with Arbitrary Separation
• Random weighted projections, random quadratic forms and random eigenvectors

Cited by in corpus (11)

• An Analysis of the t-SNE Algorithm for Data Visualization
• Learning Mixtures of Linear Regressions with Nearly Optimal Complexity
• Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval
• When Does Non-Orthogonal Tensor Decomposition Have No Spurious Local Minima?
• Manifold Optimization for Gaussian Mixture Models
• Provable learning of Noisy-or Networks
• An Alternative to EM for Gaussian Mixture Models: Batch and Stochastic Riemannian Optimization
• Recovering Structured Probability Matrices
• Learning RUMs: Reducing Mixture to Single Component via PCA
• Landscape analysis of an improved power method for tensor decomposition
• Convergence Rates of Latent Topic Models Under Relaxed Identifiability Conditions