Limits of clustering many groups in low-dimensional data revealed

Low-degree polynomials lower bounds for clustering in small dimension

Machine Learning

Summary

Clustering means grouping data points that are similar to each other. This paper studies how hard it is to cluster when there are many groups but only a few features describing each data point. The authors show that even with powerful polynomial-based methods, a very large sample size is needed to correctly identify the groups if the groups are not far apart. They also connect their results from simple data types to more complex Gaussian data. Their work gives theoretical evidence about when clustering becomes computationally difficult in such scenarios.

What this means in practice

  • For machine learning engineers: Understand fundamental limits on clustering many groups from limited low-dimensional data, guiding dataset size requirements for algorithms.
  • For data scientists in signal processing: Inform feasibility of separating signal groups in scenarios with many sources but few measured features, avoiding unrealistic expectations of clustering accuracy.

A theory result. No direct application yet.

Authors

Alexandra Carpentier, Nicolas Verzelen

Abstract

We study the computational limits of clustering $n$ observations drawn from a mixture of $K$ isotropic distributions in $\mathbb R^d$, in the regime where the number $K$ of groups is much larger than the dimension $d$. In this regime, tensor-based procedures recover the partition with a polylogarithmic separation between the centers, but they require a sample size that is a large and non-explicit polynomial of $dK$, whereas the existing low-degree lower bounds only show that $n$ must be larger than $dK^2$. We introduce a mixture of $2K$ product Bernoulli distributions on $\{0,1\}^d$, with $K=(d+1)^m$, whose centers are built from a dual BCH code. This construction ensures that the moment tensors of the observations coincide with those of the uniform distribution on $\{-1,1\}^d$ up to the order $2m+1$. For any fixed $m$, we establish a low-degree polynomial lower bound showing that clustering is hard as long as the separation $Δ$ satisfies $Δ^2\ll(K^2d^{3/2}/n)^{1/(2m+2)}\wedge\sqrt d$, up to polylogarithmic factors. In particular, with a polylogarithmic separation, low-degree polynomials require $n\gtrsim K^2d^{3/2}$ observations, up to polylogarithmic factors. Through a Gaussianization argument, this hardness carries over, in the sense of reductions, to isotropic Gaussian mixtures. Our proof relies on a family of polynomials of the observations, indexed by bipartite graphs, which is almost orthonormal. The moments of these polynomials are governed by the number of solutions of polynomial systems over the finite field $\mathbb F\_{d+1}$ that are induced by the BCH code, and the crux of our analysis is to connect the combinatorial structure of the bipartite graphs with the structure of the solution sets of these systems.