Improved Convergence Guarantees for Learning Gaussian Mixture Models by EM and Gradient EM

We consider the problem of estimating the parameters a Gaussian Mixture Model\nwith K components of known weights, all with an identity covariance matrix. We\nmake two contributions. First, at the population level, we present a sharper\nanalysis of the local convergence of EM and gradient EM, compared to previous\nworks. Assuming a separation of $\\Omega(\\sqrt{\\log K})$, we prove convergence\nof both methods to the global optima from an initialization region larger than\nthose of previous works. Specifically, the initial guess of each component can\nbe as far as (almost) half its distance to the nearest Gaussian. This is\nessentially the largest possible contraction region. Our second contribution\nare improved sample size requirements for accurate estimation by EM and\ngradient EM. In previous works, the required number of samples had a quadratic\ndependence on the maximal separation between the K components, and the\nresulting error estimate increased linearly with this maximal separation. In\nthis manuscript we show that both quantities depend only logarithmically on the\nmaximal separation.\n