# Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Oct 2016.

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

- [Gaussian Universality of Perceptrons with Random Labels](https://mlsanity.com/paper/2205.13303/) (2022)
- [Optimal Inference in Contextual Stochastic Block Models](https://mlsanity.com/paper/2306.07948/) (2023)
- [Cascade of phase transitions in the training of Energy-based models](https://mlsanity.com/paper/2405.14689/) (2024)
- [Fundamental limits for rank-one matrix estimation with groupwise heteroskedasticity](https://mlsanity.com/paper/2106.11950/) (2021)
- [Bias in Motion: Theoretical Insights into the Dynamics of Bias in SGD Training](https://mlsanity.com/paper/2405.18296/) (2024)
- [Active clustering with bandit feedback](https://mlsanity.com/paper/2406.11485/) (2024)
- [Asymptotic Bayes risk of semi-supervised multitask learning on Gaussian mixture](https://mlsanity.com/paper/2303.02048/) (2023)
- [Inferring Hidden Structures in Random Graphs](https://mlsanity.com/paper/2110.01901/) (2021)
- [Planted Bipartite Graph Detection](https://mlsanity.com/paper/2302.03658/) (2023)
- [Subspace clustering in high-dimensions: Phase transitions & Statistical-to-Computational gap](https://mlsanity.com/paper/2205.13527/) (2022)
- [Analysis of High-dimensional Gaussian Labeled-unlabeled Mixture Model via Message-passing Algorithm](https://mlsanity.com/paper/2411.19553/) (2024)
- [Statistical-computational gap in multiple Gaussian graph alignment](https://mlsanity.com/paper/2512.00610/) (2025)
- [Low-degree Lower bounds for clustering in moderate dimension](https://mlsanity.com/paper/2602.23023/) (2026)

## Abstract (arXiv)

We consider the problem of Gaussian mixture clustering in the high-dimensional limit where the data consists of m points in n dimensions, n,m rightarrow ∞ and α = m/n stays finite. Using exact but non-rigorous methods from statistical physics, we determine the critical value of α and the distance between the clusters at which it becomes information-theoretically possible to reconstruct the membership into clusters better than chance. We also determine the accuracy achievable by the Bayes-optimal estimation algorithm. In particular, we find that when the number of clusters is sufficiently large, r > 4 + 2 √α, there is a gap between the threshold for information-theoretically optimal performance and the threshold at which known algorithms succeed.