Termination Condition(s) for Expectation Maximization

Question

What are good criteria for deciding when to terminate the expectation-maximization algorithm?

I know that the idea is that you should terminate when the change in the data log-likelihood is "small" or the change in the model parameters is "small" over one (or a few) iterations. But how do you determine "small"?

So far, my literature search has only provided papers that prove convergence under different conditions or provide specialized techniques to improve the rate of convergence. I've not seen good, practical, results on when to terminate the algorithm in practical use.

Answer 1

The two options mentioned in the answer by @YairDaon (likelihood difference and relative likelihood difference) are the most straightforward and robust options. However, I would caution against using the relative likelihood difference:
$l(\theta)$ is often not the full log-likelihood, but only a part of it with constant (and some other less important) terms omitted. Thus, the magnitude of $|\left[l(\theta_{n+1})-l(\theta_n)\right]/l(\theta_n)|$ would depend on what is omitted, and will be hard to interpret. Moreover, the absolute value of the likelihood is likely to be sensitive to the sample size (e.g., number of terms in $l(\theta)=\sum_{i=1}^N\log p(x_i|\theta)$), which means that the stopping criterion would produce results of different quality depending on the sample size.
On the other hand, the absolute difference $|\left[l(\theta_{n+1})-l(\theta_n)\right]|<\epsilon$ has very transparent interpretation of the probability changing by a factor of $\epsilon$. $\epsilon=0.001$ is indeed the value usually taken as the first try, as indicated in other answers.

Answer 2

You can use an absolute error criterion (e.g. difference between successive iterations $|\ell(\theta_{n+1}) - \ell(\theta_n)|< 10^{-4}$). You can also choose a relative error criterion, e.g. $\frac{|\ell(\theta_{n+1}) - \ell(\theta_n)|}{|\ell(\theta_n)|}< 10^{-4}$. This is somewhat more reasonable because you do not really know how large or small your log-likelihood is and normalizing makes your stopping condition independent of scale. Just make sure you do not set the desired tolerance too small or you will never achieve it.

Answer 3

Practically speaking, you set the change of likelihood, for instance, the 1e-3 defaulted in sklearn, or/and you set the max iteration as 100. And you try several different initializations, to try to prevent converging to local optimum points, and choose the best model.

If time and computation permit you can enlarge the iteration or/and make the likelihood change threshold smaller, like 1e-4 or the like.

Answer 4

TLDR: try a default threshold like $10^{-3}$ first. If that is slow, switch to a faster-than-linear algorithm that uses/approximates the Hessian.

It greatly depends. If your log likelihood has a low curvature, then you could be stuck waiting a long time for the objective function increments to fall below a fixed threshold like $10^{-3}$. This is because EM is only a first-order optimization method.

So, my advice would be to first run your EM algorithm using one of the default recommendations like $10^{-3}$. By the way, this default number should be with respect to the average objective (e.g., divide the ELBO sum by the sample size $N$). Ideally, it would terminate relatively quickly. However, if you get stuck in a long loop where each step is always increasing the objective function by only a small amount (but larger than your threshold), then you should look into an algorithm that has better convergence rate. For example, if you can compute the EM steps, you can probably calculate the gradient instead (eq. 8). With the gradient you can run a faster-than-linear algorithm like BFGS that is widely implemented. Personally, this trick has saved me countless hours.