Cutoff for Exact Recovery of Gaussian Mixture Models

Xiaohui Chen, Yun Yang

TL;DR

This paper pinpoints the precise separation threshold between cluster centers in Gaussian Mixture Models (GMMs) required for guaranteed recovery of cluster labels. Crucially, they demonstrate that a Semidefinite Programming (SDP) relaxation of K-means achieves this information-theoretic optimal threshold, even without assuming symmetric cluster centers.

What Problem Does This Paper Address?

Clustering is a fundamental task in data analysis, aiming to group similar data points. Gaussian Mixture Models (GMMs) are a popular probabilistic framework for clustering, assuming data is generated from a mixture of Gaussian distributions. A key challenge in GMMs is "exact recovery": can we perfectly identify which cluster each data point belongs to, given the observed data? This problem is particularly difficult when cluster centers are close to each other, making it hard to distinguish them.

Existing work has established bounds on how close cluster centers can be for recovery to be possible, but often these bounds are not sharp (i.e., they are not the tightest possible) or rely on strong assumptions like symmetric cluster centers. Furthermore, while algorithms like K-means are widely used, their theoretical guarantees for exact recovery are often limited, especially in high-dimensional settings. This paper aims to close this gap by precisely characterizing the information-theoretic limit for exact recovery in GMMs and showing that a practical, computationally tractable method (SDP relaxation of K-means) can achieve this limit.

Methods

The core of this paper lies in two main contributions:

  1. Information-Theoretic Cutoff: The authors derive the precise "cutoff" value for the separation between cluster centers. This cutoff is defined in terms of the squared Euclidean distance between cluster means ($\Delta^2$) relative to the noise variance ($\sigma^2$) and other model parameters (dimension $p$, number of clusters $K$, and sample size $n$). They establish both an upper bound (what's achievable) and a lower bound (what's fundamentally necessary) for exact recovery, showing they meet at a specific threshold.
  2. SDP Relaxation for K-means: They demonstrate that a specific Semidefinite Programming (SDP) relaxation of the K-means objective function can achieve this information-theoretic cutoff. The SDP formulation involves finding a positive semidefinite matrix that satisfies certain constraints, effectively relaxing the discrete nature of the original K-means problem. The key novelty here is showing that this SDP relaxation achieves exact recovery at the sharp threshold, without requiring the cluster centers to be symmetrically arranged (e.g., $\mu$ and $-\mu$). This is a significant improvement over prior work that often relied on such symmetry assumptions.

The proofs involve sophisticated techniques from high-dimensional probability, convex optimization, and information theory, including dual certificate arguments and concentration inequalities.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of a generative model (Gaussian Mixture Models) rather than empirical evaluation on real-world datasets.

Key Insights and Ideas

  • Sharp Information-Theoretic Threshold: The paper provides a definitive answer to the question of how close cluster centers can be before perfect recovery becomes impossible. This is a fundamental limit for any clustering algorithm.
  • SDP Relaxation Achieves Optimality: A major finding is that a specific SDP relaxation of K-means is not just "good" but information-theoretically optimal. It achieves the sharpest possible recovery threshold, matching the theoretical limit.
  • No Symmetry Assumption Needed: The SDP relaxation works even when cluster centers are not symmetrically positioned. This is a crucial practical advantage, as real-world data rarely adheres to such strict symmetry.
  • Bridging Theory and Practice: The work connects abstract information-theoretic limits with concrete algorithmic performance, showing that a computationally feasible method can attain the best possible outcome.

Key Results

  • Information-Theoretic Cutoff: The paper establishes that for $K$ clusters with equal sizes, exact recovery is possible with high probability if the squared separation between cluster centers, $\Delta^2$, is above a threshold proportional to $\sigma^2 \left(1 + \frac{K p \log n}{n}\right)$. Specifically, the cutoff is given by $\Delta^2 \gtrsim \sigma^2 \left(1 + \frac{K p \log n}{n}\right)$.
  • SDP Performance: The proposed SDP relaxation achieves exact recovery with high probability if $\Delta^2$ is above a threshold very close to the information-theoretic cutoff, specifically $\Delta^2 \gtrsim \sigma^2 \left(1 + \frac{K p \log n}{n}\right)$.
  • Lower Bound: If $\Delta^2$ is below a threshold proportional to $\sigma^2 \left(1 - \frac{K p \log n}{n}\right)$, the probability of exact recovery vanishes for any estimator.
  • Minimax Optimality: For the case of equal cluster sizes, the SDP relaxation is shown to be minimax-optimal, meaning it achieves the best possible performance in the worst-case scenario.

Limitations and Future Work

  • Equal Cluster Sizes: The main theoretical results are derived under the assumption of equal cluster sizes. The paper acknowledges that the behavior for unbalanced cluster sizes remains an open question.
  • General Noise Covariance: The analysis primarily focuses on spherical Gaussian noise (i.e., identity covariance matrix scaled by $\sigma^2$). Extending the results to general, non-spherical covariance matrices is suggested as future work.
  • Unknown K: While the paper mentions adapting the SDP for an unknown number of clusters $K$, the sharp threshold analysis is primarily for a known $K$.
  • Computational Hardness for Large K: The paper conjectures that for large $K$ (specifically $K \gg \log n$), there might be a computational hardness regime where no polynomial-time algorithm can achieve the information-theoretic threshold for exact recovery, even though spectral methods and SDPs might achieve partial recovery. This is an open question.

Summary updated

Abstract

We determine the information-theoretic cutoff value on separation of cluster centers for exact recovery of cluster labels in a K-component Gaussian mixture model with equal cluster sizes. Moreover, we show that a semidefinite programming (SDP) relaxation of the K-means clustering method achieves such sharp threshold for exact recovery without assuming the symmetry of cluster centers.
BibTeX
@article{chen2021cutoff,
  author = {Xiaohui Chen and Yun Yang},
  title = {{Cutoff for Exact Recovery of Gaussian Mixture Models}},
  journal = {IEEE Trans. Information Theory},
  year = {2021},
  url = {https://openreview.net/forum?id=1PJs4bIZ06},
}
Figure