Towards Clustering High-dimensional Gaussian Mixture Clouds in Linear Running Time

Dan Kushnir, Shirin Jalali, Iraj SanieeAISTATS 2019 · OpenReview

Abstract

Clustering mixtures of Gaussian distributions is a fundamental and challenging problem. State-of-the-art theoretical work on learning Gaussian mixture models has mostly focused on estimating the mixture parameters, which often incurs significant computational and sample complexity costs. This paper introduces ClusterGMM, a highly efficient algorithm that leverages random 1D projections to achieve linear running time in both the number of samples ($n$) and the ambient dimension ($p$). By proving that a suitable clustering direction can be found in sub-logarithmic time relative to the dimension, the authors provide a method where sample complexity is entirely independent of $p$.

Introduction: The Curse of Dimensionality

Clustering data from Gaussian mixtures is a cornerstone of machine learning, but traditional approaches often hit a "curse of dimensionality" wall. Popular methods like Expectation-Maximization (EM) and k-means frequently lack convergence guarantees and become prohibitively slow as the dimension and number of samples grow. Furthermore, accurately learning the parameters (such as the covariance matrix) of a Gaussian in $p$ dimensions typically requires at least $O(p^2)$ samples. In modern "big data" scenarios with high dimensions but relatively few samples, traditional parameter learning becomes impossible. This paper addresses whether we can cluster high-dimensional "clouds" of data without the overhead of learning the full high-dimensional model.

The ClusterGMM Approach

The researchers propose ClusterGMM, which utilizes a "dual approach" based on dimensionality reduction. Instead of tackling the $p$-dimensional space directly, the algorithm repeatedly projects the high-dimensional data onto random 1D lines. In this 1D space, mixture parameters are estimated using the Method of Moments (MoM) or a simple 1D EM. This process is extremely fast ($O(n)$) and requires very few samples.

The core innovation lies in the "Separation Search." The authors prove that if two Gaussian clusters are "c-separated" in the high-dimensional space, a "good" 1D projection—one that preserves enough separation to allow for low-error clustering—can be found very quickly. The process repeats until a projection yields a separation meeting a user-defined error threshold or a theoretical "projection budget" is exhausted.

Comparison of algorithmic complexity and separation requirements across various GMM clustering methods.

Key Insights: Clustering vs. Learning

A central insight of this work is that clustering does not require full parameter learning. One does not need the full covariance matrix to determine cluster membership; a single "good" 1D view is often sufficient.

The "Sub-Logarithmic Surprise" is another major contribution. While one might expect finding a good 1D direction in a massive $p$-dimensional space to be difficult, the authors prove that for sufficiently separated Gaussians, the expected number of random projections needed grows slower than $\ln p$. This makes the search incredibly efficient and leads to a total expected complexity of $o(\ln p)O(np)$.

Empirical Validation

The paper validates these theoretical bounds using synthetic datasets, including spherical Gaussians in $R^{100}$ and non-spherical Gaussians in $R^{1000}$. The results demonstrate that the algorithm's performance is robust even when the data lies on a lower-dimensional manifold (i.e., the covariance matrix is not full rank).

Number of projections required to find a 'good' clustering direction versus the separability of the Gaussian components.

Experimental results on 100D and 1000D data closely match the predicted theoretical bounds for the number of projections required to reach specific error rates. Notably, the sample complexity $O(\frac{1}{\epsilon^2} \log \frac{1}{\delta})$ lacks a $p$ term, confirming that the number of samples required does not increase with the addition of more features.

Conclusion

This paper provides a powerful theoretical justification for using simple random projections as a primary tool for big-data clustering. By moving away from the heavy computational cost of full-dimensional GMM estimation, ClusterGMM offers a scalable solution for high-dimensional datasets where clusters are sufficiently separated. Future work may extend these efficient bounds more broadly beyond the two-cluster case and explore scenarios with heavier cluster overlap.

Summary updated

Abstract

Clustering mixtures of Gaussian distributions is a fundamental and challenging problem. State-of-the-art theoretical work on learning Gaussian mixture models has mostly focused on estimating the mi...
BibTeX
@inproceedings{kushnir2019towards,
  author = {Dan Kushnir and Shirin Jalali and Iraj Saniee},
  title = {{Towards Clustering High-dimensional Gaussian Mixture Clouds in Linear Running Time}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=WA8QsD0mJW8},
}
Figure