mlsanityData to 7 Oct 2026

Low-degree Lower bounds for clustering in moderate dimension

arXiv 2602.23023 ↗First posted 26 Feb 2026math.ST cs.LG math.PRcited by 0

Not on the map. Why?

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.

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

Builds on

24 of 41 references.

References · 24

  1. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  2. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 82
  3. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  4. 2017The power of sum-of-squares for detecting hidden structurescited by 54
  5. 2016Statistical and Computational Guarantees of Lloyd's Algorithm and its Variantscited by 52
  6. 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
  7. 2019Optimality of Spectral Clustering in the Gaussian Mixture Modelcited by 42
  8. 2020Computational Barriers to Estimation from Low-Degree Polynomialscited by 38
  9. 2022The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statisticscited by 31
  10. 2017On Learning Mixtures of Well-Separated Gaussianscited by 30
  11. 2021Clustering Mixtures with Almost Optimal Separation in Polynomial Timecited by 28
  12. 2015The Hardness of Approximation of Euclidean k-meanscited by 25
12 more
  1. 2018Partial recovery bounds for clustering with the relaxed Kmeanscited by 25
  2. 2016Polynomial-time Tensor Decompositions with Sum-of-Squarescited by 22
  3. 2021Optimal Spectral Recovery of a Planted Vector in a Subspacecited by 21
  4. 2020Optimal estimation of high-dimensional location Gaussian mixturescited by 16
  5. 2016Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clusteringcited by 13
  6. 2021Improved Convergence Guarantees for Learning Gaussian Mixture Models by EM and Gradient EMcited by 11
  7. 2022A Robust Spectral Algorithm for Overcomplete Tensor Decompositioncited by 7
  8. 2025Sharp Phase Transitions in Estimation with Low-Degree Polynomialscited by 7
  9. 2023Computational Lower Bounds for Graphon Estimation via Low-degree Polynomialscited by 6
  10. 2025Low-degree lower bounds via almost orthonormal basescited by 5
  11. 2025Phase Transition for Stochastic Block Model with more than √n Communities (II)cited by 3
  12. 2022On the Role of Channel Capacity in Learning Gaussian Mixture Modelscited by 2

Built on by

Not cited yet.