Learning Gaussian mixture models (GMMs) using the Expectation-Maximization (EM) algorithm and its gradient-based variants is a fundamental problem in machine learning. It is known that randomly initialized (gradient) EM fails to learn multi-component GMMs in the exact-parameterized setting, where the number of components matches that of the ground-truth GMM. Recently, global convergence of gradient EM has been established in the over-parameterized setting, where more components are used, provided that the ground-truth components are well separated. In particular, the minimum separation between ground-truth components is required to scale as Ω(d), where d is the dimension. In this paper, we show that this dimensional dependence is unavoidable in high-dimensional settings. Specifically, we consider a hybrid EM algorithm that uses standard EM updates for the mixing weights and gradient EM updates for the component means. For any ε>0, we prove that when the dimension is sufficiently large, in the worst case a separation of order Ω(d0.5−ε) is insufficient to guarantee global convergence of population gradient EM in sub-exponential time under random initialization, even in the over-parameterized regime. Our result establishes an almost optimal worst-case lower bound on the ground-truth separation required for learning Gaussian mixtures via gradient EM in high dimensions.
Figures & tables
Figure 1: The gray parallelogram represents the ground-truth subspace P , and the blue points denote the ground-truth means μ1∗,μ2∗,μ3∗ . For each 1≤i≤m , we assumed μi as the initialized parameter in Si whose distance to P is minimal. The remaining parameters in Si are denoted by black points. At the end of Stage 1, the distance from μi to P is smaller than that of any other μj∈Si by at least dϵ .
Figure 2: Illustration of Stage 2 dynamics. Similar as in Figure 1 , the gray parallelogram represents the ground-truth subspace P , and the blue points denote the ground-truth means μ1∗,μ2∗,μ3∗ . During this stage, at first each μi moves towards μi∗ for 1≤i≤m , but at last μ1 becomes very close to P while others stay far from P .
Figure 3: Trajectories of the learned means μi for d=10,500 , generated by the released code with seed 0. Left: d=10 . Both ground-truth components are fit by some μi . Right: d=500 . Only one component converges toward the signal axis, while the remaining ones stay far away, demonstrating underfitting in this run. Gray crosses mark initialization, colored dots mark final means, and red stars mark true means. All three seeds are shown in Appendix D .
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Three-seed evaluation of the fixed-separation experiment in Section 5 . Columns show d=10,500 ; rows show seeds 0,1,2 . As in Figure 3 , gray crosses mark initialization, colored dots mark final means, and red stars mark true means. At d=10 , all three seeds approach both true components. At d=500 , all three seeds exhibit underfitting, with a single fitted component carrying essentially all final weight.
Figure 5: Mean trajectories at d=106 , using the same coordinates and style as Figure 3 . Rows show seeds 0,1,2 ; columns show the two separations. At the smaller separation one active mean lies between the true centers; at the larger separation two active means approach the distinct true centers.
Figure 6: Fitted-weight trajectories πi(t) at d=106 for all ten components and all 500 updates. At the smaller separation one component receives almost all final weight. At the larger separation two components have substantial final weights.
We study the problem of learning Gaussian mixture models under overparameterization. Prior work has shown that while overparameterization is essential for avoiding spurious local optima and enables global recovery of the ground-truth model using the gradient-EM (expectation-maximization) algorithm, it can dramatically slow down the local rate of convergence. Under certain assumptions on the mixture weights, we show that a standard divergence measure minimized by statistical learning procedures possesses a manifold of slow growth on which the well-known Polyak stepsize reduces the loss geometrically, and design a gradient-based method that converges to minimizers at a locally linear rate. Additionally, we show that our method converges to nearly optimal solutions -- up to a natural misspecification threshold -- for mixtures with arbitrary weights. At a high level, the method alternates between several "short" gradient descent steps that approach the manifold and "long" Polyak steps that contract the distance to minimizers. Our results suggest that slow convergence is not an intrinsic challenge of overparameterization, but can be overcome by exploiting the favorable structure of the loss landscape.
Electrical & Computer Engineering, University of Washington, Seattle, WA · National Institute for Theory and Mathematics in Biology, Chicago, IL · Amazon, Inc.
We study model-order selection and component-mean estimation for multidimensional Gaussian mixture models with a known common covariance matrix. Using empirical characteristic-function measurements, we construct Fourier covariance matrices whose population counterparts have rank equal to the number of mixture components. We establish a minimax lower bound showing that distinguishing a separated k-component mixture from the class of (k−1)-component mixtures requires Ω(Δ−(4k−4)) samples. We then develop an oracle spectral-thresholding estimator with a sufficient sample size of order Δ−(8k−8) for fixed k, together with a practical singular-value-ratio estimator. Given the model order, we estimate the component means by score-initialized gradient descent on a MUSIC-type projection objective. Under an explicit sample-size condition, a qualifying sample initialization lies in a certified attraction region with high probability, after which the iterates converge linearly. For fixed positive component separation, the resulting mean estimates achieve the parametric rate Op(n−1/2). Numerical experiments demonstrate competitive accuracy and lower computational cost than expectation-maximization across a range of multidimensional settings.
Xinyu Liu, Hai Zhang
Department of Mathematics, Hong Kong University of Science and Technology (HKUST) · HKUST-Shenzhen-Hong Kong Collaborative Innovation Research Institute
In this paper, we study the problem of learning one-dimensional Gaussian mixture models (GMMs) with a specific focus on estimating both the model order and the mixing distribution from independent and identically distributed (i.i.d.) samples. This paper establishes the optimal sampling complexity for model order estimation in one-dimensional Gaussian mixture models. We prove a fundamental lower bound on the number of samples required to correctly identify the number of components with high probability, showing that this limit depends critically on the separation between component means and the total number of components. We then propose a Fourier-based approach to estimate both the model order and the mixing distribution. Our algorithm utilizes Fourier measurements constructed from the samples, and our analysis demonstrates that its sample complexity matches the established lower bound, thereby confirming its optimality. Numerical experiments further show that our method outperforms conventional techniques in terms of efficiency and accuracy.
Xinyu Liu, Hai Zhang
Department of Mathematics Hong Kong University of Science and Technology Clear Water Bay, Hong Kong SAR, China