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