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.
Electrical & Computer Engineering, University of Washington, Seattle, WA · National Institute for Theory and Mathematics in Biology, Chicago, IL · Amazon, Inc.
Department of Mathematics, Hong Kong University of Science and Technology (HKUST) · HKUST-Shenzhen-Hong Kong Collaborative Innovation Research Institute