# Proving that the Variational EM algorithm converges

We know that

\begin{align} \log p(x) &=\mathbb{E}_{z\sim q(z|x)}\left[\log p(x)\right] \\ &=\mathbb{E}_{z\sim q(z|x)}\left[\log\left(p(x)\frac{p(z|x)q(z|x)}{p(z|x)q(z|x)}\right)\right] \\ &=\mathbb{E}_{z\sim q(z|x)}\left[\log\frac{p(x,z)}{q(z|x)}+\log\frac{q(z|x)}{p(z|x)}\right] \\ &=\mathbb{E}_{z\sim q(z|x)}\left[\log\frac{p(x,z)}{q(z|x)}\right]+KL(q(z|x)\|p(z|x)) \end{align}

Let's assume that $p$ and $q$ are parametric and don't share any parameters.

It's easy to show that the EM algorithm never decreases $\log p(x)$, but I don't think that's enough to conclude that if the M-step makes no improvement then we found a local maximum of $\log p(x)$.

I can prove that we found a local maximum by using the gradient, but what if $p$ and $q$ are not differentiable?

• Just to check if my understanding is correct: after the E-step, $\log p(x)$ is equal to the ELBO, but only in one point, so we can't conclude right away that if we can't optimize the ELBO than we can't optimize log p(x) either. I'm assuming we can get the KL to 0, for simplicity. Commented Nov 2, 2017 at 17:16

The EM algorithm maximizes the ELBO wrt $\phi$ and $\theta$: $$\DeclareMathOperator*{\argmax}{arg\,max} (\phi^{*},\theta^{*})=\argmax_{\phi,\theta}ELBO_{\phi}^{\theta}$$
Let $\theta'=\argmax_{\theta}\log p(x|\theta)$. We have: