# Learning Mixtures of Gaussians in High Dimensions

arXiv: https://arxiv.org/abs/1503.00424 · HTML: https://mlsanity.com/paper/1503.00424/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2015.

## Built on by (most cited first, 29 of 29)

- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [Towards Demystifying Representation Learning with Non-contrastive Self-supervision](https://mlsanity.com/paper/2110.04947/) (2021)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Adversarial Combinatorial Bandits with General Non-linear Reward Functions](https://mlsanity.com/paper/2101.01301/) (2021)
- [Clustering a Mixture of Gaussians with Unknown Covariance](https://mlsanity.com/paper/2110.01602/) (2021)
- [Learning GMMs with Nearly Optimal Robustness Guarantees](https://mlsanity.com/paper/2104.09665/) (2021)
- [Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy](https://mlsanity.com/paper/2302.07426/) (2023)
- [Clustered Federated Learning via Generalized Total Variation Minimization](https://mlsanity.com/paper/2105.12769/) (2021)
- [Landscape analysis of an improved power method for tensor decomposition](https://mlsanity.com/paper/2110.15821/) (2021)
- [Tensor Moments of Gaussian Mixture Models: Theory and Applications](https://mlsanity.com/paper/2202.06930/) (2022)
- [A Robust Spectral Algorithm for Overcomplete Tensor Decomposition](https://mlsanity.com/paper/2203.02790/) (2022)
- [Optimal Estimation and Computational Limit of Low-rank Gaussian Mixtures](https://mlsanity.com/paper/2201.09040/) (2022)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures](https://mlsanity.com/paper/2112.05445/) (2021)
- [A general technique for approximating high-dimensional empirical kernel matrices](https://mlsanity.com/paper/2511.03892/) (2025)
- [Robust Model Selection and Nearly-Proper Learning for GMMs](https://mlsanity.com/paper/2106.02774/) (2021)
- [Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models](https://mlsanity.com/paper/2211.03827/) (2022)
- [Algorithms from Invariants: Smoothed Analysis of Orbit Recovery over SO(3)](https://mlsanity.com/paper/2106.02680/) (2021)
- [On the Role of Channel Capacity in Learning Gaussian Mixture Models](https://mlsanity.com/paper/2202.07707/) (2022)
- [Big Learning Expectation Maximization](https://mlsanity.com/paper/2312.11926/) (2023)
- [Learning High-dimensional Gaussians from Censored Data](https://mlsanity.com/paper/2504.19446/) (2025)
- [A Nested Matrix-Tensor Model for Noisy Multi-view Clustering](https://mlsanity.com/paper/2305.19992/) (2023)
- [Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning](https://mlsanity.com/paper/2311.07284/) (2023)
- [Factor Adjusted Spectral Clustering for Mixture Models](https://mlsanity.com/paper/2408.12564/) (2024)
- [Diagonally-Weighted Generalized Method of Moments Estimation for Gaussian Mixture Modeling](https://mlsanity.com/paper/2507.20459/) (2025)
- [Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms](https://mlsanity.com/paper/2601.05157/) (2026)
- [Learning Mixtures of Unknown Causal Interventions](https://mlsanity.com/paper/2411.00213/) (2024)
- [Mixtures Closest to a Given Measure: A Semidefinite Programming Approach](https://mlsanity.com/paper/2509.22879/) (2025)
- [Mode Collapse of Mean-Field Variational Inference](https://mlsanity.com/paper/2510.17063/) (2025)

## Abstract (arXiv)

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 > Omega(k2), 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.