Id: arxiv/2611.25163 Url: https://arxiv.org/abs/2611.25163 Tags: math.ST, cs.CC, stat.ML Score: 0 Title: The low-degree sample complexity of clustering Gaussian mixtures with more groups than dimensions Domain: math.ST Source: arxiv Authors: Alexandra Carpentier, Nicolas Verzelen Reviews: 0 Subject: math.ST Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-11-18 Page: https://delphi.science/r/arxiv/2611.25163 We study the computational limits of clustering $n$ observations drawn from a mixture of $K$ isotropic Gaussian distributions in $\mathbb R^d$, when the number $K$ of groups is much larger than the dimension $d$. In this regime, distance-based and spectral procedures require a squared separation $Δ^2$ of order $\sqrt d$. In contrast, tensor-based procedures cluster at a polylogarithmic separation but need a sample size that is a large polynomial of $dK$, and the low-degree lower bounds known for random centers only show that $n$ must exceed $dK^2$. Focusing on normally distributed centers,…