Proving that the Variational EM algorithm converges

Question

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?

Answer 1

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:

\begin{align} \log p(x|\theta')-\log p(x|\theta^{*}) &=ELBO_{\phi^{*}}^{\theta'}+KL(\phi^{*},\theta')-ELBO_{\phi^{*}}^{\theta^{*}}-KL(\phi^{*},\theta^{*}) \\ &\leq ELBO_{\phi^{*}}^{\theta^{*}}+KL(\phi^{*},\theta')-ELBO_{\phi^{*}}^{\theta^{*}}-KL(\phi^{*},\theta^{*})\\ &=KL(\phi^{*},\theta')-KL(\phi^{*},\theta^{*})\\ &=\int q(z|x,\phi^{*})\log\frac{p(z|x,\theta^{*})}{p(z|x,\theta')} \end{align}