Benefits of Expectation Maximization for Mixture Models

Question

What are the benefits of using expectation maximization for mixture models vs. direct maximization of the marginal likelihoods?

Analytic maximization step
In case of Gaussian mixtures the benefit is obvious: the maximization step can be done analytically, which allows to replace complex optimization by a simple iterative algorithms.

This answer makes this point more generally:

Expectation maximization is a technique to solve statistical problems that consist of an "easy" maximization (if some latent variables were known), and an "easy" expectation calculation on the log-likelihood (if the parameters were known). However, the "how" and "why" the expectation and maximization steps require ingenuity, and are model-specific. So while it's possible that some models from deep learning could be posed in fashion that might leverage EM, EM is not a generic optimization technique, not even to classical statistical models.

Numerical maximization step
This advantage is however less evident in cases where the maximization step has to be done numerically. This answer argues that EM is still advantageous in the sense that it eases the use of optimization algorithms and easier to interpret:

One benefit of EM is that it naturally produces valid parameters for the mixture distribution on every iteration. In contrast, standard optimization algorithms would need constraints to be imposed. For example, say you're fitting a Gaussian mixture model. A standard nonlinear programming approach would require constraining covariance matrices to be positive semidefinite, and constraining mixture component weights to be nonnegative and sum to one.

Another aspect of numerical maximization step is that it is not guaranteed to find the absolute maximum of the llikelihood. Therefore one may have to rerun the algorithm multiple times with different starting parameters. Moreover, it is not certain that monotonuous increase of the likelihood is guaranteed in this case (see my related question).

I am looking therefore for the discussion of the advantages of EM technique in comparison to direct maximization of the marginal likelihood (the comparison with Markov Chain Monte Carlo is perhaps more obvious).

Related questions:
Why should one use EM vs. say, Gradient Descent with MLE?
What is the difference between EM and Gradient Ascent?

Update
@Xi'an point out in their comment that the likelihood for a mixture model is highly multimodal (I also encountered a similar point in these notes). However this raises a few questions:

• Is multimodality of mixture likelihood an empirical observation or a mathematical fact?
• This problem is not exactly bypassed by EM: in order to find teh global minimum, the algorithm has to be launched several times, just as we would have done with direct gradient descent minimization.

Answer 1

I understand that you are asking why EM is preferred over Gradient (G-) based methods for generic mixture models. Nevertheless, given the amount of recent literature on the specific topic of Gaussian Mixture Models (GMMs), I will summarize a few advantages of each method, focussed on GMMs. I believe some of the points are applicable to generic mixture models as well.

Advantages of EM

1. EM does not require hyper-parameters like learning rate, etc. which needs to be tuned [1,2].
2. EM is quasi-linear in convergence, it takes far too lesser iterations compared to a first order method [1,2]. Further, the authors of this paper [4] compare the runtime where it is noted that EM is faster by a factor of at least 10x
3. The likelihood is guaranteed to increase monotonically with each iteration ; this is not the case with G-based methods as choosing the wrong learning rate or momentum can deteriorate the likelihood between iterations.
4. EM is invariant to reparametrization [1]; this is not the case with the usual G-based methods, with the exception of a few methods like Newton's method.

Advantages of G-based methods

1. One needs to manually derive the updates of the E and M steps in the EM. For simpler models such as GMM, this can be done but it quickly becomes complicated for complex models; there is no need to derive such updates in the case of G-based methods, as they rely on Automatic Differentiation and reparametrizations. There is a library called Mixture-Models available in Python which does this effortlessly, not just for GMMs, but also for many sophisticated mixture models [3].

2. For High-Dimensional data in GMMs, it is shown that G-based methods give better performance compared to EM [3]. This is a big deal because traditionally researchers have focussed on constraining GMMs to fit them on HD data. It is shown that no such modelling constraints are required and one can directly fit GMMs using G-based methods and achieve superior performance.

3. This is more of a subtle, yet important point. Starting from a given initialisation, in EM, one is guaranteed to follow a certain trajectory in the likelihood landscape. With G-based methods, a bit of exploration is possible by varying the learning rate and momentum. Given the highly non-convex likelihood landscape, this exploration would help to achieve better optimum for the same initialisation.

References:

[1] Homeomorphic-Invariance of EM: Non-Asymptotic Convergence in KL Divergence for Exponential Families via Mirror Descent

[2] On Convergence Properties of the EM Algorithm for Gaussian Mixtures

[3] Mixture-Models: a one-stop Python Library for Model-based Clustering using various Mixture Models

[4] Avoiding inferior clusterings with misspecified GMMs