# Minimax Theory for High-dimensional Gaussian Mixtures with Sparse Mean Separation

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2013.

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

- [Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression](https://mlsanity.com/paper/2303.02118/) (2023)
- [Can semi-supervised learning use all the data effectively? A lower bound perspective](https://mlsanity.com/paper/2311.18557/) (2023)
- [Semi-Supervised Sparse Gaussian Classification: Provable Benefits of Unlabeled Data](https://mlsanity.com/paper/2409.03335/) (2024)
- [Learning With Multi-Group Guarantees For Clusterable Subpopulations](https://mlsanity.com/paper/2410.14588/) (2024)
- [Support Recovery in Mixture Models with Sparse Parameters](https://mlsanity.com/paper/2202.11940/) (2022)
- [Optimal Discriminant Analysis in High-Dimensional Latent Factor Models](https://mlsanity.com/paper/2210.12862/) (2022)
- [Sharp-SSL: Selective high-dimensional axis-aligned random projections for semi-supervised learning](https://mlsanity.com/paper/2304.09154/) (2023)
- [Enhanced anomaly detection in well log data through the application of ensemble GANs](https://mlsanity.com/paper/2411.19875/) (2024)
- [Subspace clustering in high-dimensions: Phase transitions & Statistical-to-Computational gap](https://mlsanity.com/paper/2205.13527/) (2022)
- [Mixture-Models: a one-stop Python Library for Model-based Clustering using various Mixture Models](https://mlsanity.com/paper/2402.10229/) (2024)
- [False membership rate control in mixture models](https://mlsanity.com/paper/2203.02597/) (2022)

## Abstract (arXiv)

While several papers have investigated computationally and statistically efficient methods for learning Gaussian mixtures, precise minimax bounds for their statistical performance as well as fundamental limits in high-dimensional settings are not well-understood. In this paper, we provide precise information theoretic bounds on the clustering accuracy and sample complexity of learning a mixture of two isotropic Gaussians in high dimensions under small mean separation. If there is a sparse subset of relevant dimensions that determine the mean separation, then the sample complexity only depends on the number of relevant dimensions and mean separation, and can be achieved by a simple computationally efficient procedure. Our results provide the first step of a theoretical basis for recent methods that combine feature selection and clustering.