# Low-degree Lower bounds for clustering in moderate dimension

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 41 references that are in the map.
- First posted on arXiv 26 Feb 2026.

## Builds on (most cited first, 24 of 24)

- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent](https://mlsanity.com/paper/2009.06107/) (2020)
- [Optimality of Spectral Clustering in the Gaussian Mixture Model](https://mlsanity.com/paper/1911.00538/) (2019)
- [Computational Barriers to Estimation from Low-Degree Polynomials](https://mlsanity.com/paper/2008.02269/) (2020)
- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [On Learning Mixtures of Well-Separated Gaussians](https://mlsanity.com/paper/1710.11592/) (2017)
- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [The Hardness of Approximation of Euclidean k-means](https://mlsanity.com/paper/1502.03316/) (2015)
- [Partial recovery bounds for clustering with the relaxed Kmeans](https://mlsanity.com/paper/1807.07547/) (2018)
- [Polynomial-time Tensor Decompositions with Sum-of-Squares](https://mlsanity.com/paper/1610.01980/) (2016)
- [Optimal Spectral Recovery of a Planted Vector in a Subspace](https://mlsanity.com/paper/2105.15081/) (2021)
- [Optimal estimation of high-dimensional location Gaussian mixtures](https://mlsanity.com/paper/2002.05818/) (2020)
- [Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering](https://mlsanity.com/paper/1610.02918/) (2016)
- [Improved Convergence Guarantees for Learning Gaussian Mixture Models by EM and Gradient EM](https://mlsanity.com/paper/2101.00575/) (2021)
- [Low-degree lower bounds via almost orthonormal bases](https://mlsanity.com/paper/2509.09353/) (2025)
- [A Robust Spectral Algorithm for Overcomplete Tensor Decomposition](https://mlsanity.com/paper/2203.02790/) (2022)
- [Sharp Phase Transitions in Estimation with Low-Degree Polynomials](https://mlsanity.com/paper/2502.14407/) (2025)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Phase Transition for Stochastic Block Model with more than √n Communities (II)](https://mlsanity.com/paper/2511.21526/) (2025)
- [On the Role of Channel Capacity in Learning Gaussian Mixture Models](https://mlsanity.com/paper/2202.07707/) (2022)

## Abstract (arXiv)

We study the fundamental problem of clustering n points into K groups drawn from a mixture of isotropic Gaussians in ℝd. Specifically, we investigate the requisite minimal distance Delta between mean vectors to partially recover the underlying partition. While the minimax-optimal threshold for Delta is well-established, a significant gap exists between this information-theoretic limit and the performance of known polynomial-time procedures. Although this gap was recently characterized in the high-dimensional regime (n ≤ dK), it remains largely unexplored in the moderate-dimensional regime (n ≥ dK). In this manuscript, we address this regime by establishing a new low-degree polynomial lower bound for the moderate-dimensional case when d ≥ K. We show that while the difficulty of clustering for n ≤ dK is primarily driven by dimension reduction and spectral methods, the moderate-dimensional regime involves more delicate phenomena leading to a "non-parametric rate". We provide a novel non-spectral algorithm matching this rate, shedding new light on the computational limits of the clustering problem in moderate dimension.