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)?

  • $\begingroup$ I think this paper is relevant to your question. $\endgroup$ – Digio Sep 16 '17 at 20:25

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.

  • $\begingroup$ It took a year but I am glad to find the answer :D $\endgroup$ – user3086871 Sep 25 '18 at 4:12
  • $\begingroup$ @user3086871, yeah I only saw the question a couple days ago. Sometimes discoverability is challenging. $\endgroup$ – Lucas Roberts Sep 25 '18 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.