Minimax Gaussian Classification & Clustering

Tianyang Li, Xinyang Yi, Constantine Caramanis, Pradeep RavikumarAISTATS 2017 · OpenReview

Abstract

This paper establishes the fundamental statistical limits—minimax bounds—for classification and clustering within the framework of two-component isotropic Gaussian mixture models. By defining clustering error in a discriminative fashion, we bridge the gap between supervised and unsupervised learning. Our analysis identifies a critical sample size threshold below which no algorithm outperforms random guessing. We demonstrate that both Fisher’s Linear Discriminant (for classification) and a PCA-based rule (for clustering) achieve a fast minimax rate of $\Theta(1/n)$. Furthermore, we extend these results to high-dimensional sparse settings where the number of features $p$ exceeds the sample size $n$, provided the mean separation is sparse.

Introduction

In statistical learning theory, the minimax rate represents the best possible performance any algorithm can achieve for a specific problem, regardless of its computational complexity. While Gaussian models are foundational to the field, several gaps have persisted in our understanding of their minimax limits. Specifically, previous literature often suggested classification error rates of $O(1/\sqrt{n})$. This research investigates whether a faster rate of $\Theta(1/n)$ is achievable even when classes overlap (non-zero Bayes error) and seeks to unify the treatment of clustering and classification.

Theoretical Framework

We consider data drawn from an Isotropic Gaussian Mixture Model: $$X \sim \pi_1 \mathcal{N}(\mu_1, \sigma^2 I) + \pi_0 \mathcal{N}(\mu_0, \sigma^2 I)$$ where $\rho = ||\mu_1 - \mu_0||$ represents the separation between the means.

A key contribution of this work is the discriminative definition of clustering error. By treating clustering as "classification with a hidden permutation" of labels, we can directly compare the performance of unsupervised methods against supervised benchmarks. This unified metric allows for a rigorous quantification of the "information price" paid when labels are unavailable.

Minimax Rates and the "Fast Rate" Phenomenon

Our analysis proves that the excess risk—the gap between an algorithm's error and the ideal Bayes error—can decrease at a rate of $\Theta(1/n)$. This is significantly faster than the $1/\sqrt{n}$ rate typically associated with non-parametric statistics.

  • Classification: We show that Fisher’s Linear Discriminant (FLD) is minimax optimal, achieving this fast rate in general settings.
  • Clustering: We demonstrate that a clustering rule constructed using Principal Component Analysis (PCA) to identify the direction of maximum variance also achieves the $\Theta(1/n)$ rate (up to logarithmic factors).

The Impossibility Zone

A central finding of this research is the existence of a "phase transition" in learning. If the sample size $n$ is too small relative to the dimension $p$ and the separation $\rho$, specifically if: $$n \cdot \max\{\rho^2, \rho^4\}/p \to 0$$ then any algorithm, no matter how sophisticated, will perform no better than a random coin flip (error $\approx 1/2$). This defines a fundamental "Impossibility Zone" where the signal-to-noise ratio is too low for recovery.

Furthermore, we quantify the inherent difficulty of clustering compared to classification. The lower bounds for clustering error depend on the mean separation as $1/\rho^3$, whereas classification error depends on $1/\rho$. This mathematical distinction formally characterizes why unsupervised tasks require more distinct data separation to reach the same accuracy as supervised tasks.

High-Dimensional Sparsity

In modern data science, we frequently encounter settings where the number of features $p$ is much larger than the number of samples $n$. We address this by analyzing the sparse setting, where the difference between Gaussian means is concentrated in only $s$ features ($s \ll p$).

In this regime, we utilize $\ell_1$-regularized optimization for classification and a thresholding-PCA approach for clustering. We prove that learning remains possible if $n$ scales with $s \log p$ rather than the full dimension $p$. Specifically, the sparse classification rate becomes $\Theta(s \log p / n)$, demonstrating that sparsity can effectively bypass the curse of dimensionality.

Conclusion

This work provides a comprehensive map of the statistical limits of Gaussian classification and clustering. By establishing fast minimax rates and identifying the critical thresholds for sample size and separation, we provide a theoretical foundation for evaluating existing algorithms and developing new ones. Future work will focus on relaxing the isotropic assumption to accommodate general covariance structures and investigating the potential statistical-computational gaps in sparse clustering where optimal solutions may be computationally intractable.

Summary updated

Abstract

We present minimax bounds for classification and clustering error in the setting where covariates are drawn from a mixture of two isotropic Gaussian distributions. Here, we define clustering error in a discriminative fashion, demonstrating fundamental connections between classification (supervised) and clustering (unsupervised). For both classification and clustering, our lower bounds show that without enough samples, the best any classifier or clustering rule can do is close to random guessing. For classification, as part of our upper bound analysis, we show that Fisher's linear discriminant achieves a fast minimax rate $\Theta(1/n)$ with enough samples $n$. For clustering, as part of our upper bound analysis, we show that a clustering rule constructed using principal component analysis achieves the minimax rate with enough samples. We also provide lower and upper bounds for the high-dimensional sparse setting where the dimensionality of the covariates $p$ is potentially larger than the number of samples $n$, but where the difference between the Gaussian means is sparse.
BibTeX
@inproceedings{li2017minimax,
  author = {Tianyang Li and Xinyang Yi and Constantine Caramanis and Pradeep Ravikumar},
  title = {{Minimax Gaussian Classification \& Clustering}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
  url = {https://openreview.net/forum?id=1TBN5xhiqV},
}
Figure