,\alpha| \theta^{(t)},\alpha^\prime=0)$. The~third panel
of Figure~\ref{fig:comp} plots this function using a heat map, where
brighter colors represent higher values and darker colors represent
lower values. The~solid line superimposed on the plot is the optimal
value of $\theta$ as a function of $\alpha$ and is given by
\begin{equation}
{\sum_{i=1}^n X_i + m(1-\alpha) \theta^{(t)}\over n + m(1-\alpha)^2}.
\end{equation}
For example, with $\alpha=0$ the curve gives $\theta^{(t+1)}_{\mathrm{EM}}$.
The dashed line gives the optimal value of $\theta$ as a function of
$\alpha$ under CDA-EM. This curve corresponds to the modes of the
dashed curves in the second panel. The~solid and dashed curves in the
third panel differ because CDA-EM and PXEM differ in how they treat
$\alpha^\prime$ in $Q(\theta,\alpha| \theta^{(t)},\alpha^\prime)$.
PXEM fixes $\alpha^\prime$ at the identity value under the
transformation from $Y$ to $Z$ (i.e., PXEM fixes $\alpha^\prime=0$),
whereas CDA-EM does not update $\alpha$ in the iteration and sets
$\alpha^\prime=\alpha$ throughout. The~function
$Q(\theta,\alpha|\theta^{(t)},\alpha^\prime=0)$ plotted in panel 3 increases
along the solid curve as $\alpha$ goes to $-\infty$ and the solid curve
asymptotes to $\theta=0$, the maximum likelihood estimate. Thus, both
CDA-EM run with $\alpha=1$ and PXEM converge to the maximum likelihood
estimate in one iteration.

One might be tempted to think that PXEM is superior to CDA-EM because
it optimizes $Q(\theta,\alpha| \theta^{(t)},\break \alpha^\prime=0)$ over
both $\theta$ and $\alpha$ at each iteration, whereas CDA-EM
optimizes $Q(\theta,\alpha| \theta^{(t)},\alpha^\prime=\alpha)$
over only $\theta$ under a constraint that fixes $\alpha$ at a
prespecified value. That is, one might expect PXEM to increase $\ell$
more because it increases $Q$ more. This reasoning, however, not only
blurs the difference in how the two algorithms treat $\alpha^\prime$,
but also oversimplifies the rates of convergence of EM-type algorithms.
An algorithm that increases $Q$ more at every iteration does not
necessary converge faster. This can be seen clearly in the first panel
of Figure~\ref{fig:comp}. The~optimal update is $\theta^\star$, but
$\theta^\star$ is far from the maximizer of $Q$. Our goal is not to
increase $Q$ more, but to make $Q$ a better approximation of the log
likelihood. As another example, the EM algorithm by definition
increases $Q$ by at least as much in its \mbox{M-step} as ECM can in a
sequence of CM-steps. Nonetheless, \citet{meng94b} shows that ECM
can converge faster than EM. In the present example, CDA-EM sets
$\alpha=1$ and updates $\theta$ to $\theta^{(t+1)}=0$ which is a saddle
point of $Q(\theta,\alpha| \theta^{(t)},\alpha^\prime=0)$. Even
though $Q(\theta,\alpha| \theta^{(t)},\alpha^\prime=0)$ evaluated
at the CDA-EM update is less than when it is evaluated at the PXEM
update, both updates have $\theta^{(t+1)}=0$ and thus give the same value
of the observed data log likelihood. The~rate of convergence is more
directly determined by (\ref{eq:emrate}) than by the relative increase
in $Q$. It is this rate that CDA-EM aims to optimize and that PXEM
improves by eliminating the conditioning on $\alpha$; see Section~\ref
{sec:eda:joint}.

\begin{figure}[b]

\includegraphics{309f08.eps}

\caption{The~partially blocked Gibbs sampler. The~inner loop is
iterated $N$ times.}
\label{fig:partblockgibbs}
\end{figure}

\subsection{Nesting}
\label{sec:eda:nest}

\begin{figure

\includegraphics{309f09.eps}

\caption{The~MCEM algorithm.
The~inner loop is iterated several times. [In the maximization
step we compute $\theta$ to maximize the conditional expectation of
$\log p(\theta|Y^{\mathrm{aug}}_1, Y^{\mathrm{aug}}_2)$, with the
expectation computed in
the Monte Carlo expectation step. Here we use the
superscript ``a'' as an abbreviation for ``aug'' or ``augmented.'']} \label{fig:mcem}
\end{figure}

Nested EM and DA-type algorithms involve iteratively using a data
augmentation method to accomplish one of the steps of a larger
algorithm also involving data augmentation. Figures~\ref
{fig:partblockgibbs}--\ref{fig:nem} illustrate three different ways
this might be done. To motivate the nesting strategy, we begin with the
partially-blocked Gibbs sampler illustrated in Figure~\ref{fig:partblockgibbs}
(\citet{vand00nem}). Although we consider a
sampler composed using three full conditional distributions, the ideas
apply immediately to samplers with arbitrarily many conditional
distributions. In particular, suppose we wish to sample from
$p(\theta|Y^{\mathrm{obs}})$, where $\theta =(\theta _1,\theta _2,\theta_3)$
by using a Gibbs sampler which samples from each of
$p(\theta _1|\theta _2,\theta_3,Y^{\mathrm{obs}})$,
$p(\theta_2|\theta _1,\theta _3,Y^{\mathrm{obs}})$, and
$p(\theta _3|\theta_1,\theta _2, Y^{\mathrm{obs}})$ in
turn. If sampling from
$p(\theta _1|\theta _2,\theta _3,\break Y^{\mathrm{obs}})$ is expensive
relative to sampling from the other two conditional distributions, it
may be beneficial to sample once from
$p(\theta _1|\theta _2,\theta_3,Y^{\mathrm{obs}})$
and then to sample from $p(\theta _2|\theta _1,\theta _3,Y^{\mathrm{obs}})$
and $p(\theta_3|\theta _1,\theta _2,Y^{\mathrm{obs}})$ $N$ times each in turn. If
$N$ is large, the
internal Gibbs sampler delivers an approximate draw from the joint
distribution $p(\theta _2,\theta _3 | \theta _1)$. If this
approximation is
good, we are essentially running a blocked Gibbs sampler with
conditional distributions
$p(\theta _1|\theta _2,\break\theta_3,Y^{\mathrm{obs}})$ and
$p(\theta_2,\theta _3|\theta _1,Y^{\mathrm{obs}})$. The~partially blocked
Gibbs sampler is
useful when the advantage of blocking outweighs the cost of sampling
from $p(\theta _2,\theta _3|\theta _1,\break Y^{\mathrm{obs}})$ via a
nested Gibbs sampler. This
strategy may be helpful when $\theta _2$ and $\theta _3$ exhibit significant
correlation given $\theta _1$ and/or
$p(\theta _1|\theta _2,\theta_3, Y^{\mathrm{obs}})$ is
particularly difficult to sample (e.g., \citeauthor{vandconnkashsiem01},
\citeyear{vandconnkashsiem01}). Notice there is a subtle tradeoff
here. If $\theta_2$ and $\theta_3$ are (nearly) conditionally
independent given $\theta_1$, then there is no need to run the inner
iteration. If, on the other hand, they are highly correlated, then the
inner iteration may need to be run many times in order to deliver a
good draw. The~key to success with this strategy is repeating the
expensive draw of $p(\theta_1 | \theta_2, \theta_3)$ as seldom as possible.

\begin{figure

\includegraphics{309f10.eps}

