Missing Information and EM Convergence Speed

Why Latent Uncertainty Affects EM Speed

EM can make reliable progress in likelihood while moving only a small distance in parameter space on each iteration. This is especially noticeable in mixture models: when an observation could plausibly belong to several components, its latent allocation is uncertain. The information lost by not observing those allocations has a precise relationship to EM’s local convergence rate.

The central idea is comparative. If the complete data were available, the log-likelihood would usually have more curvature, and its information would be larger. EM’s iterations account for the difference between that complete-data information and the information available from the observations alone. The resulting local rate is matrix-valued; its largest eigenvalue in magnitude determines the slowest local direction.

Complete, Observed, and Missing Information

Definition: Let $Y$ denote observed data and $Z$ latent data, with joint density or mass function $p_\theta(y,z)$ and marginal observed-data function $p_\theta(y)=\int p_\theta(y,z)\,dz$, where the integral includes a sum for discrete latent variables. The complete-data score is $S_c(\theta)=\nabla_\theta\log p_\theta(Y,Z)$, and the observed-data score is $S_o(\theta)=\nabla_\theta\log p_\theta(Y)$. At a parameter value where the scores have mean zero, the complete-data and observed-data Fisher information matrices are $I_{\mathrm{com}}(\theta)=E_\theta[S_cS_c^\mathsf{T}]$ and $I_{\mathrm{obs}}(\theta)=E_\theta[S_oS_o^\mathsf{T}]$. The missing information is $I_{\mathrm{mis}}(\theta)=E_\theta[\operatorname{Var}_\theta(S_c\mid Y)]$.

These definitions concern repeated sampling under the model. For a fixed observed data set, conditional variances such as $\operatorname{Var}(S_c\mid Y=y)$ also appear in the local EM rate calculation; those are sample-specific matrices, not expectations over repeated data sets.

The Missing-Information Decomposition

Assume the parameter is an interior point of an open parameter space, the support does not depend on $\theta$, and differentiation can be interchanged with the marginalization over $Z$. Assume the scores have finite second moments and mean zero. These regularity conditions allow the score of the marginal model to be obtained by conditioning the complete-data score.

Theorem (missing-information decomposition): Under these conditions, $$ I_{\mathrm{com}}(\theta)=I_{\mathrm{obs}}(\theta)+I_{\mathrm{mis}}(\theta). $$ In particular, $I_{\mathrm{mis}}$ is positive semidefinite, so observed information cannot exceed complete-data information in any direction.

Proof. Differentiating the marginal density gives $$ \nabla_\theta p_\theta(y) =\int p_\theta(y,z)\nabla_\theta\log p_\theta(y,z)\,dz. $$ Dividing by $p_\theta(y)$ shows that $S_o(\theta)=E_\theta[S_c(\theta)\mid Y]$. The law of total covariance then gives $$ \operatorname{Var}_\theta(S_c) =E_\theta[\operatorname{Var}_\theta(S_c\mid Y)] +\operatorname{Var}_\theta(E_\theta[S_c\mid Y]). $$ Since both scores have mean zero, their covariance matrices are their Fisher information matrices. Substituting $E[S_c\mid Y]=S_o$ proves the decomposition. A conditional covariance matrix is positive semidefinite, and so is its expectation; this proves the final claim. $\square$

Worked Example: Reading an Information Fraction

Suppose a one-parameter model has complete-data information $I_{\mathrm{com}}=10$ and missing information $I_{\mathrm{mis}}=8$, in the same parameterization and at the same parameter value. Find the observed information and the fraction of complete-data information that is missing.

By the decomposition, $I_{\mathrm{obs}}=I_{\mathrm{com}}-I_{\mathrm{mis}}=10-8=2$. The missing fraction is $I_{\mathrm{mis}}/I_{\mathrm{com}}=8/10=0.8$; the observed fraction is $2/10=0.2$. This calculation alone is not a convergence-rate proof: it compares Fisher information under repeated sampling. The local EM rate requires curvature matrices for the observed data set being fitted, as derived next.

Local EM Convergence as a Missing-Information Fraction

For fixed observed data $y$, write the EM auxiliary function as $$ Q(\theta\mid\phi)=E_\phi[\log p_\theta(y,Z)\mid Y=y]. $$ An EM map $M$ sends the current parameter $\phi$ to a maximizer of $Q(\theta\mid\phi)$ over $\theta$. Consider an interior fixed point $\theta_*$, so $M(\theta_*)=\theta_*$. Assume the conditional distribution of $Z$ and the complete-data log density are twice continuously differentiable in the relevant neighborhood; differentiation can be interchanged with conditional integration; the M-step selects a unique differentiable local maximizer; and the matrix $$ A=-\nabla_\theta^2 Q(\theta_*\mid\theta_*) $$ is nonsingular. Define the conditional missing-information matrix $$ C=\operatorname{Var}_{\theta_*}\{S_c(\theta_*)\mid Y=y\}. $$

Theorem (local EM rate): Under these conditions, the derivative of the EM map at the fixed point is $$ DM(\theta_*)=A^{-1}C. $$ If $\theta_*$ is a strict local maximum of the observed log-likelihood and its negative Hessian is positive definite, the eigenvalues of this rate matrix lie in $[0,1)$. The spectral radius $\rho(DM(\theta_*))$ is the local linear convergence factor.

Proof. Let $g(\theta,\phi)=\nabla_\theta Q(\theta\mid\phi)$. The M-step condition is $g(M(\phi),\phi)=0$. At the fixed point, the derivative with respect to the first argument is $\partial g/\partial\theta=-A$. For a conditional expectation of a fixed function $h(Z)$, differentiating with respect to $\phi$ gives $$ \nabla_\phi E_\phi[h(Z)\mid y] =\operatorname{Cov}_\phi\{h(Z),S_c(\phi)\mid y\}. $$ Indeed, the derivative of the conditional log density of $Z$ given $y$ is $S_c(\phi)-E_\phi[S_c(\phi)\mid y]$; differentiating the expectation and centering this derivative yields the stated covariance. Apply this identity to $h(Z)=S_c(\theta_*)$, holding $\theta_*$ fixed while differentiating $\phi$. It follows that $\partial g/\partial\phi=C$ at $(\theta_*,\theta_*)$. Differentiating $g(M(\phi),\phi)=0$ at $\phi=\theta_*$ therefore gives $$ -A\,DM(\theta_*)+C=0, \qquad DM(\theta_*)=A^{-1}C. $$ Moreover, $g(\theta,\theta)=\nabla_\theta\log p_\theta(y)$, by the conditional score identity. Differentiating this equality along the diagonal at $\theta_*$ shows that the observed negative Hessian is $B=A-C$. If $B$ is positive definite, then $C$ is positive semidefinite and $A=B+C$ is positive definite. The matrix $A^{-1}C$ is similar to the symmetric matrix $A^{-1/2}CA^{-1/2}$, so its eigenvalues are nonnegative. For any nonzero vector $v$, $$ v^\mathsf{T}A^{-1/2}CA^{-1/2}v < v^\mathsf{T}v, $$ because $A^{-1/2}BA^{-1/2}$ is positive definite and $A=B+C$. Thus all eigenvalues are less than one. A differentiable iteration with this derivative contracts sufficiently close to the fixed point at a linear rate governed by its largest eigenvalue in magnitude. $\square$

This is a local statement, not a guarantee about the whole path from an arbitrary initialization. It describes behavior once the iterates are near a regular fixed point. If the observed curvature becomes singular or the M-step is not differentiable, the stated rate formula need not apply.

Worked Example: A Two-Direction Local Rate

Suppose the complete-data conditional curvature and missing-information matrices at a fixed point are $$ A=\begin{pmatrix}4&0\\0&2\end{pmatrix}, \qquad C=\begin{pmatrix}2&0.4\\0.4&1\end{pmatrix}. $$ Find the local EM rate matrix and its slowest linear rate.

First, $A^{-1}=\begin{pmatrix}1/4&0\\0&1/2\end{pmatrix}$, so $$ DM(\theta_*)=A^{-1}C =\begin{pmatrix}0.5&0.1\\0.2&0.5\end{pmatrix}. $$ Its characteristic equation is $$ (0.5-\lambda)^2-(0.1)(0.2)=0, $$ giving $\lambda=0.5\pm\sqrt{0.02}$, or approximately $0.6414$ and $0.3586$. Thus the spectral radius is approximately $0.6414$. Locally, the slowest direction contracts by about 0.6414 per iteration; the rate is not obtained by taking a separate scalar ratio from each diagonal entry because the information and update couple the two coordinates.

As a check, the observed negative Hessian is $B=A-C=\begin{pmatrix}2&-0.4\\-0.4&1\end{pmatrix}$. Its leading principal minor is $2>0$, and its determinant is $2-0.16=1.84>0$, so it is positive definite. The example is consistent with a strict local maximum and eigenvalues below one.

Uncertain Mixture Memberships and Slow Updates

In a finite mixture, let $Z_i$ indicate the component generating observation $Y_i$. Posterior responsibilities are conditional probabilities for these indicators. When responsibilities are close to zero or one, the allocations are nearly known; when they are closer to intermediate values, the conditional allocation variance is larger. Since the missing-information matrix contains conditional score variance, uncertain allocations can leave a larger fraction of information missing and make the local EM rate closer to one.

Worked Example: Comparing Two Mixture Fits

Consider a two-component mixture with mixing weight $\pi$ for component 1. The two components generate a binary observation $a$ or $b$. In an overlapping model, let $P(a\mid Z=1)=0.9$ and $P(a\mid Z=2)=0.1$. Observe one $a$ and one $b$, and evaluate the EM map at $\pi=0.5$.

For the observation $a$, Bayes’ rule gives $$ \tau_a(\pi)=P(Z=1\mid a) =\frac{0.9\pi}{0.9\pi+0.1(1-\pi)}, \qquad \tau_a(0.5)=0.9. $$ For $b$, the component probabilities are reversed, so $\tau_b(0.5)=0.1$. The mixing-weight M-step averages the responsibilities. Hence $T(0.5)=(0.9+0.1)/2=0.5$, confirming that this is a fixed point for these data.

More generally, differentiating the posterior responsibility gives $$ \tau_i'(\pi)=\frac{\tau_i(\pi)\{1-\tau_i(\pi)\}}{\pi(1-\pi)}. $$ Therefore $T'(\pi)=\{\tau_a'(\pi)+\tau_b'(\pi)\}/2$, and at the fixed point $$ T'(0.5)=\frac{0.9(0.1)+0.1(0.9)}{2(0.25)}=0.36. $$ Now keep the same balanced pair of observations but use a clearer model with $P(a\mid Z=1)=0.99$ and $P(a\mid Z=2)=0.01$. The responsibilities at $\pi=0.5$ are $0.99$ and $0.01$; their average is again $0.5$, and the local derivative is $$ T'(0.5)=\frac{0.99(0.01)+0.01(0.99)}{2(0.25)}=0.0396. $$ Thus the ambiguous fit contracts much more slowly near its fixed point: its local factor is $0.36$, compared with $0.0396$ for the clearer fit. The calculation illustrates the information mechanism, not a universal rule that responsibility entropy alone determines the rate in every parameter direction.

Interpretation and a Common Pitfall

The rate matrix explains why a likelihood can appear to plateau while EM continues to make small parameter updates. When a direction has a large missing-information fraction, the corresponding eigenvalue of $A^{-1}C$ can be close to one. Many iterations may then be needed to reduce error in that direction. This helps interpret convergence diagnostics, but it does not replace them: slow local contraction and poor initialization are different problems.

Pitfall: treating uncertainty as a convergence-rate calculation. It is tempting to say that fractional responsibilities automatically imply a particular number of iterations. The correction is to examine the conditional score covariance and the full local rate matrix. Responsibilities indicate latent uncertainty, but the effect depends on how that uncertainty enters each parameter direction.
Pitfall: using the rate formula far from a fixed point. The derivative $DM(\theta_*)$ describes local behavior near a regular fixed point. It does not predict the entire path from a distant starting value.
Pitfall: confusing Fisher information with fixed-sample curvature. The decomposition of expected Fisher information is a repeated-sampling statement. A rate calculation at a fitted data set uses local conditional curvature and conditional score variance for that data set.

Key takeaway: EM’s local rate is controlled by missing information relative to complete-data curvature. Greater latent-allocation uncertainty can increase the rate eigenvalues, so convergence becomes slower; the relevant comparison is matrix-valued and local.

Check Your Understanding

Use the definitions and results above to answer these questions.

State the missing-information decomposition and explain why its missing-information term is positive semidefinite.
What does an eigenvalue of the local EM rate matrix close to one imply about nearby iterations?
In the two-component mixing-weight example, why is $\pi=0.5$ a fixed point when the two responsibilities are $0.9$ and $0.1$?
Why is posterior responsibility uncertainty alone insufficient to specify the complete local convergence rate?
What additional condition makes the eigenvalues of the local rate matrix strictly less than one in the theorem?