Low-degree Lower bounds for clustering in moderate dimension

Authors	Alexandra Carpentier & Nicolas Verzelen
Year	2026
Field	Machine Learning
arXiv	2602.23023
PDF	Download
Categories	cs.LG, stat.ML

Abstract

We study the fundamental problem of clustering $n$ points into $K$ groups drawn from a mixture of isotropic Gaussians in \mathbb{R}^d. Specifically, we investigate the requisite minimal distance $Δ$ between mean vectors to partially recover the underlying partition. While the minimax-optimal threshold for $Δ$ 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 \leq dK$), it remains largely unexplored in the moderate-dimensional regime ($n \geq dK$). In this manuscript, we address this regime by establishing a new low-degree polynomial lower bound for the moderate-dimensional case when $d \geq K$. We show that while the difficulty of clustering for $n \leq 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.

---

Engineering Breakdown

Plain English

This paper investigates the computational-statistical gap in clustering problems for Gaussian mixtures in moderate dimensions (when n ≥ dK). The authors establish that while the information-theoretic limit for clustering separation distance Δ is known, polynomial-time algorithms require substantially larger separation than this limit—a gap that wasn't well-characterized in this regime. They introduce low-degree polynomial lower bounds to formally quantify this gap, proving that any polynomial-time algorithm needs minimum separation distance significantly larger than the minimax-optimal threshold. This represents the first rigorous characterization of the clustering hardness in the moderate-dimensional setting where d ≥ K.

Core Technical Contribution

The core novelty is establishing tight low-degree polynomial lower bounds for clustering in the moderate-dimensional regime (n ≥ dK, d ≥ K), filling a gap between information-theoretic limits and computational feasibility. The authors use low-degree polynomial methods—a powerful technique from hardness of computation theory—to prove that no efficient polynomial algorithm can solve clustering below a certain separation threshold, even though information theory says it's possible. This provides a formal, provable barrier to what polynomial-time algorithms can achieve in this regime, connecting statistical optimality to computational intractability. The contribution is distinct from prior work because it addresses the under-explored moderate-dimensional case, whereas recent results focused on the high-dimensional regime (n ≤ dK).

How It Works

The paper frames clustering as a detection/recovery problem: given n points from K isotropic Gaussians in ℝ^d with mean separation Δ, recover the partition. The low-degree polynomial lower bound technique works by constructing a family of problem instances (spiked covariance models or planted partition problems) and proving that low-degree polynomials in the data cannot distinguish between the null distribution and the signal-present distribution. Specifically, the authors show that polynomial algorithms of degree o(√n) or similar bounds cannot achieve partial recovery when Δ is below their threshold, while information theory allows recovery at smaller Δ. The key insight is leveraging moment method properties and spectral properties of random matrices to establish that low-degree statistics fail to capture the planted structure, creating a fundamental computational-statistical tradeoff.

Production Impact

For production clustering systems, this paper's main message is cautionary: for certain moderate-dimensional Gaussian mixture scenarios, practitioners should expect polynomial-time algorithms (including spectral methods and EM) to require substantially larger cluster separation than theory guarantees is necessary. If your clustering task has clusters closer together than the low-degree bound, you face a hard choice: use exponential-time algorithms (impractical for large n), relax your recovery requirements, or add additional structure/assumptions. In practice, this means before deploying unsupervised clustering in moderate dimensions, validate whether your actual cluster separation exceeds the hardness threshold—if not, no polynomial algorithm will reliably work. For high-dimensional or extremely large-scale problems, this bound may be less restrictive, so problem geometry matters significantly.

Limitations and When Not to Use This

The paper assumes isotropic Gaussians with specific structure, which doesn't capture real-world data distributions like heavy tails, correlated features, or non-Gaussian shapes. The low-degree polynomial lower bounds are conditional on the low-degree hypercontractivity conjecture and similar assumptions, not unconditional barriers—so there remains possibility (however remote) of breakthrough algorithms. The results hold for partial recovery (recovering a constant fraction of labels), not perfect recovery, and the exact constants in the separation threshold Δ are not fully characterized. Finally, the paper doesn't provide constructive guidance on what to do when facing this hardness—practitioners still lack algorithmic recommendations for handling hard clustering instances beyond standard heuristics.

Research Context

This work extends the rapidly growing field of computational lower bounds using low-degree polynomials, spectral methods, and average-case hardness theory. Recent work (references would include Brennan, Bresler, Huang et al. and others studying planted partitions) established gaps in high dimensions; this paper closes the moderate-dimensional gap left open. It builds on the classical Balcan-Blum-Gupta framework for clustering hardness and connects to statistical query complexity theory. The research direction opened is characterizing fundamental limits across all dimensional regimes and understanding which geometric properties of the data (sparsity, manifold structure, etc.) help circumvent computational barriers.

---

:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::

---

Back to Research Lab → · Subscribe to AI Letters →