{"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","summary":"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,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-18","reactions":{}}