# The More, the Merrier: the Blessing of Dimensionality for Learning Large Gaussian Mixtures

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2013.

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

- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models](https://mlsanity.com/paper/2303.04288/) (2023)
- [High-dimensional separability for one- and few-shot learning](https://mlsanity.com/paper/2106.15416/) (2021)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [Relative intrinsic dimensionality is intrinsic to learning](https://mlsanity.com/paper/2311.07579/) (2023)
- [A Fourier Approach to Mixture Learning](https://mlsanity.com/paper/2210.02415/) (2022)
- [Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples](https://mlsanity.com/paper/2309.03847/) (2023)
- [Robust Model Selection and Nearly-Proper Learning for GMMs](https://mlsanity.com/paper/2106.02774/) (2021)
- [On the Role of Channel Capacity in Learning Gaussian Mixture Models](https://mlsanity.com/paper/2202.07707/) (2022)
- [Generalized Identifiability Bounds for Mixture Models with Grouped Samples](https://mlsanity.com/paper/2207.11164/) (2022)
- [A Mathematical Framework for the Problem of Security for Cognition in Neurotechnology](https://mlsanity.com/paper/2403.07945/) (2024)
- [Diagonally-Weighted Generalized Method of Moments Estimation for Gaussian Mixture Modeling](https://mlsanity.com/paper/2507.20459/) (2025)
- [PMODE: Theoretically Grounded and Modular Mixture Modeling](https://mlsanity.com/paper/2508.21396/) (2025)
- [Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms](https://mlsanity.com/paper/2601.05157/) (2026)
- [Probabilistic Circuits for Irregular Multivariate Time Series Forecasting](https://mlsanity.com/paper/2604.27814/) (2026)
- [The Parametric Stability of Well-separated Spherical Gaussian Mixtures](https://mlsanity.com/paper/2302.00242/) (2023)
- [Understanding the geometry of deep learning with decision boundary volume](https://mlsanity.com/paper/2603.14768/) (2026)

## Abstract (arXiv)

In this paper we show that very large mixtures of Gaussians are efficiently learnable in high dimension. More precisely, we prove that a mixture with known identical covariance matrices whose number of components is a polynomial of any fixed degree in the dimension n is polynomially learnable as long as a certain non-degeneracy condition on the means is satisfied. It turns out that this condition is generic in the sense of smoothed complexity, as soon as the dimensionality of the space is high enough. Moreover, we prove that no such condition can possibly exist in low dimension and the problem of learning the parameters is generically hard. In contrast, much of the existing work on Gaussian Mixtures relies on low-dimensional projections and thus hits an artificial barrier. Our main result on mixture recovery relies on a new "Poissonization"-based technique, which transforms a mixture of Gaussians to a linear map of a product distribution. The problem of learning this map can be efficiently solved using some recent results on tensor decompositions and Independent Component Analysis (ICA), thus giving an algorithm for recovering the mixture. In addition, we combine our low-dimensional hardness results for Gaussian mixtures with Poissonization to show how to embed difficult instances of low-dimensional Gaussian mixtures into the ICA setting, thus establishing exponential information-theoretic lower bounds for underdetermined ICA in low dimension. To the best of our knowledge, this is the first such result in the literature. In addition to contributing to the problem of Gaussian mixture learning, we believe that this work is among the first steps toward better understanding the rare phenomenon of the "blessing of dimensionality" in the computational aspects of statistical inference.