What is the difference between EM and Gradient Ascent?

Question

What is the difference between the algorithms EM (Expectation Maximization) and Gradient Ascent (or descent)? Is there any condition under which they are equivalent?

Answer 1

From:

Xu L and Jordan MI (1996). On Convergence Properties of the EM Algorithm for Gaussian Mixtures. Neural Computation 2: 129-151.

Abstract:

We show that the EM step in parameter space is obtained from the gradient via a projection matrix P, and we provide an explicit expression for the matrix.

Page 2

In particular we show that the EM step can be obtained by pre-multiplying the gradient by a positive denite matrix. We provide an explicit expression for the matrix ...

Page 3

That is, the EM algorithm can be viewed as a variable metric gradient ascent algorithm ...

This is, the paper provides explicit transformations of the EM algorithm into gradient-ascent, Newton, quasi-Newton.

From wikipedia

There are other methods for finding maximum likelihood estimates, such as gradient descent, conjugate gradient or variations of the Gauss–Newton method. Unlike EM, such methods typically require the evaluation of first and/or second derivatives of the likelihood function.

Answer 2

No, they are not equivalent. In particular, EM convergence is much slower.

If you are interested in an optimization point-of-view on EM, in this paper you will see that EM algorithm is a special case of wider class of algorithms (proximal point algorithms).

Answer 3

I wanted to follow up (even though this is some years later) on the OP's second question:

Is there any condition under which they are equivalent?

In fact there is a condition under which they're equivalent.

The first order EM algorithm is gradient descent on the marginal likelihood function.

To parse the implications of this statement you need the precise definitions and the derivation, which is pretty straightforward so I'll sketch it here:

The statement above is literally, $\nabla_\theta Q_n(\theta | \theta^t)|_{\theta =\theta^t} = \nabla_{\theta}l(\theta).$ Define, $$ Q_n(\theta | \theta^t) = \frac{1}{n}\sum_{i=1}^n \left\{\int_z k_{\theta^t}(z|y_i)\log f_\theta(y_i, z)dz \right\}. $$ Here $z$ is the unobserved or "latent" variable, $k_{\theta^t}(z|y_i)$ its conditional distribution, $y_i$ are observed data, and $\theta^t$ is the parameter value at iteration $t$, $\theta$ is the parameter you are optimizing for in the EM algorithm. Further $$ l(\theta) = \frac{1}{n}\sum_{i=1}^n\log\left(\int_z f_\theta(y_i, z)dz\right) $$

Now consider,

$$ \nabla_\theta Q_n(\theta | \theta^t) = \frac{1}{n}\sum_{i=1}^n \left\{\int_z k_{\theta^t}(z|y_i)\nabla_\theta \log f_\theta(y_i, z)dz \right\}. $$ The right-hand side of the equation is: $$ \frac{1}{n}\sum_{i=1}^n \left\{\int_z k_{\theta^t}(z|y_i)\nabla_\theta \log f_\theta(y_i, z)dz \right\} = \frac{1}{n}\sum_{i=1}^n \left\{\int_z k_{\theta^t}(z|y_i)\frac{\nabla_\theta f_\theta(y_i, z)dz }{f_\theta(y_i, z)}\right\}. $$ Next write out the definition of the conditional distribution, $$ \frac{1}{n}\sum_{i=1}^n \left\{\int_z k_{\theta^t}(z|y_i)\frac{\nabla_\theta f_\theta(y_i, z)dz }{f_\theta(y_i, z)}\right\}= \frac{1}{n}\sum_{i=1}^n \left\{\int_z \frac{f_\theta(y_i, z)}{f_\theta(y_i)}\frac{\nabla_\theta f_\theta(y_i, z)dz }{f_\theta(y_i, z)}\right\}. $$ Now you cancel the $f_\theta(y_i, z)$ terms $$ \frac{1}{n}\sum_{i=1}^n \left\{\int_z \frac{\nabla_\theta f_\theta(y_i, z)dz }{f_\theta(y_i)}\right\}. $$ Now switch the order of the integral and derivative to obtain $$ \frac{1}{n}\sum_{i=1}^n \left\{ \frac{\nabla_\theta f_\theta(y_i) }{f_\theta(y_i)}\right\} = \frac{1}{n}\sum_{i=1}^n \left\{\nabla_\theta \log f_\theta(y_i)\right\}, $$ and it is easy to see that this is the same as

$$ \nabla_\theta l(\theta), $$

which shows the claim:

The first order EM algorithm is gradient descent on the marginal likelihood function.

Of course this makes the usual assumptions about interchange of derivative and integral, so if those assumptions are not valid, then the claim will not be valid. Those types of cases occur most frequently when a parameter is on the boundary of the support of the distribution and the derivative w.r.t. the parameter becomes a Dirac delta function which does not allow interchange of derivative and integral.

The claim is made at the bottom of page 82 of the following paper:

Statistical guarantees for the EM algorithm: From population to sample-based analysis Sivaraman Balakrishnan, Martin J. Wainwright, Bin Yu Ann. Statist. 45(1): 77-120 (February 2017). DOI: 10.1214/16-AOS1435.