The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian Mixtures

This paper studies the problem of estimating the means ±θ*∈ℝd of a symmetric two-component Gaussian mixture δ*· N(θ*,I)+(1-δ*)· N(-θ*,I) where the weights δ* and 1-δ* are unequal. Assuming that δ* is known, we show that the population version of the EM algorithm globally converges if the initial estimate has non-negative inner product with the mean of the larger weight component. This can be achieved by the trivial initialization θ0=0. For the empirical iteration based on n samples, we show that when initialized at θ0=0, the EM algorithm adaptively achieves the minimax error rate tildeOBig(minBigfrac1(1-2δ*)√fracdn,frac1|θ*|√fracdn,left(fracdnright)1/4BigBig) in no more than OBig(frac1|θ*|(1-2δ*)Big) iterations (with high probability). We also consider the EM iteration for estimating the weight δ*, assuming a fixed mean θ (which is possibly mismatched to θ*). For the empirical iteration of n samples, we show that the minimax error rate tildeOBig(frac1|θ*|√fracdnBig) is achieved in no more than OBig(frac1|θ*|2Big) iterations. These results robustify and complement recent results of Wu and Zhou obtained for the equal weights case δ*=1/2.