Online EM algorithm was proposed by Olivier Cappé in Link to paper. They assume that complete data likelihood $f(x ; \theta)$ belongs to exponential family i.e.

$f(x;\theta) = h(x) \exp \left\lbrace -\psi(\theta) + \langle \phi(\theta), S(x) \rangle \right\rbrace$

The observations $Y$ sampled from unknown distribution $\pi$ are deterministic function of latent variables. The parameter $\theta$ is computed iteratively using stochastic approximation approach to update sufficient statistic $S(x)$

$\hat{s}_{n+1} = \hat{s}_n + \gamma_{n+1} \left( h(\hat{s}_n) + \xi_{n+1} \right) $


$ h(s) = \mathbb{E}_\pi \left[\overline{s}\left(Y;\overline{\theta}(s)\right)\right] - s \\ \xi_{n+1} = \overline{s}\left(Y;\overline{\theta}(\hat{s}_n)\right) - \mathbb{E}\left[ \overline{s}\left(Y;\overline{\theta}(\hat{s}_n)\right) | \mathcal{F}_n \right] \\ \overline{s}\left(Y; \theta\right) = \mathbb{E}_{\theta}\left[S(x)|Y=y \right] \\ \overline{\theta}(s) = \underset{\theta}{argmax}\left( -\psi(\theta) + \langle \phi(\theta), s \rangle \right) $

$\gamma_i$ is non increasing step size and $\mathcal{F_n}$ is the $\sigma-$field of $\{\hat{s}_0, Y_{1:n}\}$

They provide the following theorems for proving convergence:

enter image description here

In the propositions they show that KL diverenge of the computed and real distribution is a Lyapunov function of h(s). In theorem 5 they show the convergence of estimated parameter to the true parameter. Here is the proof of theorem 5. Proof of theorem 5

I do not understand how they derive the highlighted inequality. They say they are using Chebyshev's inequality associated to the Doob's martingale inequality but it is not clear to me. Can someone please help me understand this?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.