Rate of convergence of EM algorithm? What can be said in general about the rate of convergence of EM algorithm? 
For example, if I let the parameters to be $\theta$, starting point to be $\theta^0$, and the optimal solution is $\theta^*$, so that $||\theta^t-\theta^*||<\alpha||\theta^0-\theta^*||$, what can be said about $\alpha$ in general?
Also, how can we prove that it is slower than the other methods (Like Newton-Rapson, Expected Conjugate Gradient)?
 A: In the general case you need to verify that your problem setup satisfies certain properties for the EM algorithm to converge to a stationary point that is a local maximum. Further requirements are needed for global maximum. Assuming these criteria are met you can then quantify the rate of the convergence toward the global optimum. 
In the general case (and assuming you have global optimum) the most you can usually say is that the EM algorithm is a first order algorithm. 
First order algorithms are algorithms such that: 
$$|\theta^{k+1} - \theta^*| \leq \gamma |\theta^{k}-\theta^*|.$$
If $\gamma=1$ then convergence is linear and if $1<\gamma<2$ then the algorithm is said to have super-linear convergence and if $\gamma=2$ is quadratic convergence. The convergence rate really depends on the specifics of the problem. Many examples and an a pedagogic introduction to convergence rates of the EM algorithm are given in the book by McLachlin and Krishnan if you want more details.
Xu and Jordan provide an in-depth study for the mixture of Gaussians case. 
