The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian Mixtures
This provides theoretical guarantees for EM algorithm performance in unbalanced mixture models, extending prior work on equal weights, which is incremental but important for statistical learning applications.
This paper tackles the problem of estimating the means of an unbalanced symmetric Gaussian mixture using the EM algorithm, showing that it globally converges and achieves minimax error rates with specific iteration bounds, such as $ ilde{O}\Big(\min\Big\{ rac{1}{(1-2\delta_{*})}\sqrt{ rac{d}{n}}, rac{1}{\| heta_{*}\|}\sqrt{ rac{d}{n}},\left( rac{d}{n} ight)^{1/4}\Big\}\Big)$ for mean estimation.
This paper studies the problem of estimating the means $\pmθ_{*}\in\mathbb{R}^{d}$ of a symmetric two-component Gaussian mixture $δ_{*}\cdot N(θ_{*},I)+(1-δ_{*})\cdot 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 $\tilde{O}\Big(\min\Big\{\frac{1}{(1-2δ_{*})}\sqrt{\frac{d}{n}},\frac{1}{\|θ_{*}\|}\sqrt{\frac{d}{n}},\left(\frac{d}{n}\right)^{1/4}\Big\}\Big)$ in no more than $O\Big(\frac{1}{\|θ_{*}\|(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 $\tilde{O}\Big(\frac{1}{\|θ_{*}\|}\sqrt{\frac{d}{n}}\Big)$ is achieved in no more than $O\Big(\frac{1}{\|θ_{*}\|^{2}}\Big)$ iterations. These results robustify and complement recent results of Wu and Zhou obtained for the equal weights case $δ_{*}=1/2$.