Abstract
This paper studies the optimal rate of estimation in a finite Gaussian location mixture model in high dimensions without separation conditions. We assume that the number of components $k$ is bounded and that the centers lie in a ball of bounded radius, while allowing the dimension $d$ to be as large as the sample size $n$. Extending the one-dimensional result of Heinrich and Kahn (2015), we show that the minimax rate of estimating the mixing distribution in Wasserstein distance is $\Theta((d/n)^{1/4} + n^{-1/(4k-2)})$, achieved by an estimator computable in time $O(nd^2+n^{5/4})$. Furthermore, we show that the mixture density can be estimated at the optimal parametric rate $\Theta(\sqrt{d/n})$ in Hellinger distance and provide a computationally efficient algorithm to achieve this rate in the special case of $k=2$. Both the theoretical and methodological development rely on a careful application of the method of moments. Central to our results is the observation that the information geometry of finite Gaussian mixtures is characterized by the moment tensors of the mixing distribution, whose low-rank structure can be exploited to obtain a sharp local entropy bound.
Introduction
Gaussian Mixture Models (GMMs) are a cornerstone of unsupervised learning, used to model data coming from multiple sub-populations. While well-understood in low dimensions or under "separation conditions" (where clusters are far apart), their behavior in high dimensions without such assumptions has remained a significant challenge in statistical theory. This research establishes the fundamental statistical limits for estimating high-dimensional Gaussian location mixtures where the number of components is small but the dimension $d$ can be as large as the sample size $n$. The authors prove that the optimal estimation rate is governed by a combination of subspace estimation error and low-dimensional distribution estimation.
Methodology
The authors move away from the popular but often slow and locally-trapped Expectation-Maximization (EM) algorithm, opting instead for a framework based on the Method of Moments. Their approach involves several key steps:
- Dimension Reduction via PCA: Since there are only $k$ components, the centers of these clusters must lie within a $k$-dimensional subspace. The authors use Principal Component Analysis (PCA) to find this subspace, even without a "spectral gap," a common requirement in previous literature.
- Denoised Method of Moments (DMM): Once the data is projected into a low-dimensional space, they apply the DMM algorithm. This involves calculating empirical moments from the data and then "denoising" them by finding the closest valid moment vector in a mathematically defined moment space.
- Moment Tensors and Information Geometry: The authors characterize the information geometry of GMMs using moment tensors. They show that the Hellinger distance is essentially controlled by the Euclidean distance between their moment tensors.
- Le Cam-Birgé Construction: To prove the optimal rates for density estimation, they utilize a classic theoretical construction that builds an estimator from a series of pairwise tests between candidate distributions.
Key Insights
The "Rate Split"
The error in estimating the mixing distribution arises from two distinct sources: one part depends on the dimension ($d/n$), representing the difficulty of finding the correct subspace, and the other depends only on the number of components ($n^{-1/k}$), representing the difficulty of resolving overlapping clusters once the subspace is identified.
Robustness of PCA
A major insight is that PCA can effectively reduce dimensions for Wasserstein-distance estimation even when the components are not well-separated. This addresses a previous point of contention in the literature regarding the necessity of separation for effective dimensionality reduction.
Computational Advantages
While EM is the industry standard, the authors demonstrate that their moment-based approach is often faster and more accurate when clusters overlap significantly, as it avoids the local optima that frequently trap EM algorithms.
Main Results
- Optimal Rate for Mixing Distribution: The minimax rate for estimating the mixing distribution in Wasserstein distance is $\Theta((d/n)^{1/4} + n^{-1/(4k-2)})$. This result disproves a previous conjecture that the rate would be $(d/n)^{1/(4k-2)}$.
- Parametric Rate for Density: The mixture density can be estimated at the "parametric rate" of $\Theta(\sqrt{d/n})$ in Hellinger distance, the best possible rate for any smooth parametric model.
- Computational Efficiency: The proposed algorithm for mixing distribution estimation runs in $O(nd^2 + n^{5/4})$ time, making it practical for large-scale high-dimensional data.
Numerical Studies
The theoretical findings are supported by numerical studies using synthetic Gaussian mixtures. The authors generated data from 2-component and 3-component symmetric and asymmetric mixtures in 100 dimensions ($d=100$) with sample sizes ranging from 10,000 to 200,000. These simulations confirm that the DMM-based estimator outperforms the standard EM algorithm in scenarios with significant overlap.
Limitations and Future Work
While the authors prove a theoretical rate for density estimation for any $k$, a polynomial-time algorithm to achieve this rate is currently only available for $k=2$. Finding a polynomial-time algorithm for $k \ge 3$ remains an open challenge. Additionally, the current work assumes the number of components $k$ and the variance $\sigma^2$ are known. Future research could focus on developing fully adaptive models for unknown $k$ in high dimensions and extending the theory to handle cluster centers that are not confined to a bounded radius.
Summary updated