Robbins-Monro Gain Sequences in SAEM

Why SAEM Needs a Gain Sequence

In SAEM, the complete-data sufficient statistic is not usually replaced by its exact conditional expectation at each iteration. Instead, the algorithm uses a simulated latent-effect draw to form a noisy statistic and updates a running estimate. The gain determines how strongly that new simulated information changes the running estimate. It must control simulation noise, but it must also leave enough weight on future draws for the estimate to keep adapting as the parameter estimate changes.

This tutorial concerns the standard summability requirements on that gain sequence, not a particular schedule for implementing them. The key tension is that gains that remain large allow simulation fluctuations to persist, whereas gains whose total sum is finite can eventually make the algorithm insensitive to new information.

Definition: Let $\gamma_k$ be the gain at SAEM iteration $k$, with $0 < \gamma_k \leq 1$. The classical Robbins–Monro conditions are $$ \sum_{k=1}^{\infty}\gamma_k=\infty \qquad\text{and}\qquad \sum_{k=1}^{\infty}\gamma_k^2<\infty. $$ The first condition is called nonsummability of the gains; the second is square summability. Together they require gains to diminish enough to control accumulated random variation, but not so quickly that the total opportunity for adaptation is finite.

How the Conditions Enter SAEM

Write $s(y,u)$ for the complete-data sufficient statistic computed from observed data $y$ and latent random effects $u$. At iteration $k$, let $U_k$ denote a latent-effect draw generated conditional on the observations and the current parameter estimate. A stochastic-approximation update of the statistic has the form

S_k=S_{k-1}+\gamma_k\{s(y,U_k)-S_{k-1}\}.

Thus the new value is a weighted move from the current statistic estimate $S_{k-1}$ toward the simulated statistic $s(y,U_k)$. In the SAEM procedure, the M-step uses the current $S_k$ to update the parameter estimate. This formula makes the gain's two roles visible: a large gain quickly follows a new draw, while a small gain smooths the draw's effect.

If the latent draw were an independent draw from a fixed conditional distribution and the target statistic were a fixed value $S^\ast$, then the average simulated statistic would be centered at $S^\ast$. In an actual SAEM run, the conditional distribution depends on the current parameter estimate, and draws may come from a Markov chain. The target therefore moves as the algorithm proceeds, and simulation errors may be dependent. The summability conditions are not, by themselves, a guarantee of convergence. They are gain requirements used alongside regularity conditions on the model, the stochastic errors, the latent-effect simulation, and the parameter updates.

Why One Sum Diverges and the Other Converges

The update can be rewritten as $S_k=(1-\gamma_k)S_{k-1}+\gamma_k s(y,U_k)$. If the simulated statistic were replaced by a fixed target $S^\ast$, the error $D_k=S_k-S^\ast$ would obey $D_k=(1-\gamma_k)D_{k-1}$. Repeated substitution gives

D_k=D_0\prod_{j=1}^{k}(1-\gamma_j).

For gains between zero and one, $1-\gamma_j\leq \exp(-\gamma_j)$. Consequently,

\left|\prod_{j=1}^{k}(1-\gamma_j)\right| \leq \exp\left(-\sum_{j=1}^{k}\gamma_j\right).

If the sum of gains diverges, the bound tends to zero. In this fixed-target calculation, the initial error is progressively forgotten. If instead $\sum_k\gamma_k$ is finite, that argument no longer ensures that the initial error disappears: only a finite total amount of gain is available. This explains why nonsummability supports continued adaptation.

The square-sum condition addresses random fluctuations. For a simple illustration, suppose the target is fixed and the observed statistic is $S^\ast+\varepsilon_k$, where the errors are independent, have mean zero, and have variance $\tau^2<\infty$. The error recursion is

D_k=(1-\gamma_k)D_{k-1}+\gamma_k\varepsilon_k.

The new random contribution has variance $\gamma_k^2\tau^2$. If the sum of squared gains is finite, the total variance contributed by these weighted independent errors is bounded by $\tau^2\sum_k\gamma_k^2$. This is the basic reason square summability controls accumulated noise. It is an illustration, not a proof for every SAEM setting: Markov-chain draws can be dependent, and their conditional distribution changes with the iterate.

Important qualification: The Robbins–Monro conditions are standard sufficient gain conditions within stochastic-approximation convergence arguments, not a stand-alone convergence theorem. Such arguments also require suitable control of simulation error and parameter iterates, as well as regularity of the statistic and update. In SAEM, convergence is generally to a stationary point under appropriate assumptions; the gain conditions do not guarantee finding a global maximum.

Worked Examples: Checking Gains and Understanding Their Effects

Worked Example: A Power-Law Gain That Meets Both Conditions

Consider $\gamma_k=(k+1)^{-0.7}$ for $k\geq1$. The gains are positive and at most one. To check nonsummability, compare $\sum_{k=1}^{\infty}(k+1)^{-0.7}$ with a p-series. Its exponent is $0.7<1$, so the series diverges. For square summability,

\sum_{k=1}^{\infty}\gamma_k^2 =\sum_{k=1}^{\infty}(k+1)^{-1.4}<\infty,

because the p-series exponent $1.4$ is greater than one. This sequence meets both standard summability conditions. That conclusion classifies its asymptotic sums; it does not establish that every other SAEM convergence assumption is met.

Worked Example: Updating a Sufficient Statistic

Suppose a hypothetical SAEM run has $S_{k-1}=10$, and the next simulated complete-data statistic is $s(y,U_k)=14$. If the gain is $\gamma_k=0.25$, the update is

$$ S_k=10+0.25(14-10)=10+1=11. $$

The estimate moves one quarter of the four-unit gap toward the simulated value. At the next iteration, suppose $S_k=11$, the simulated statistic is $6$, and the gain is $0.20$. Then

S_{k+1}=11+0.20(6-11)=11-1=10.

The second draw moves the running statistic down by one unit. These calculations show the local effect of the gain. The summability conditions concern the entire sequence of gains, not whether a single update moves up or down.

Worked Example: A Gain Sequence That Decays Too Quickly

Consider $\gamma_k=2^{-k}$, for $k\geq1$. Its total gain is

\sum_{k=1}^{\infty}2^{-k}=1,

so it fails $\sum_k\gamma_k=\infty$. Its squared gains do sum to a finite value, since $\sum_{k=1}^{\infty}4^{-k}=1/3$, but satisfying only the square-sum condition is not enough. The finite total gain means that, in the fixed-target error calculation, the product $\prod_{j=1}^{k}(1-\gamma_j)$ does not have to tend to zero. For example, this product is bounded below by $1-\sum_{j=1}^{k}\gamma_j$ when the factors lie in $[0,1]$, and here its limiting value is positive. Thus this sequence can leave a lasting influence from the starting statistic and can give later draws very little influence.

Worked Example: Gains That Fail to Diminish Noise Sufficiently

Suppose $\gamma_k=k^{-1/2}$. The gains tend to zero, but their squares are $\gamma_k^2=1/k$. Therefore

\sum_{k=1}^{\infty}\gamma_k^2 =\sum_{k=1}^{\infty}\frac{1}{k} =\infty.

This sequence fails square summability, even though each individual gain becomes smaller. In the independent-error illustration, the cumulative variance contribution is proportional to $\sum_k\gamma_k^2$, which is not finite for this sequence. The example distinguishes “the gains tend to zero” from the stronger requirement that their squares have a finite sum.

Comparing the Main Gain Behaviours

Gain behaviour	Summability implication	Potential consequence
Positive gains with divergent sum and finite square sum	Meets both Robbins–Monro conditions	Allows continued adaptation while controlling accumulated noise, subject to other assumptions
Gains with finite total sum	Fails $\sum_k\gamma_k=\infty$	May leave too little total adaptation to remove initial error or follow a changing target
Gains whose squares have divergent sum	Fails $\sum_k\gamma_k^2<\infty$	Does not provide the standard square-summable control of simulation noise
Constant positive gain	Both sums diverge	Continues to react to new draws, but generally retains persistent fluctuations rather than meeting the diminishing-gain conditions

A constant gain is a common practical alternative when ongoing responsiveness is valued, but it is not a Robbins–Monro diminishing sequence. In the simple independent-error setting, a constant gain $\gamma$ produces an autoregressive error recursion with coefficient $1-\gamma$. Its stationary variance is $\gamma\tau^2/(2-\gamma)$, for $0<\gamma<1$, rather than zero. This calculation explains why constant-gain updates can continue to fluctuate. It does not say that a constant gain is always inappropriate; it highlights the difference between that approach and the classical diminishing-gain conditions.

Assumptions, Diagnostics, and Limitations

The gain conditions are meaningful only in a setting where the rest of the stochastic-approximation argument is plausible. Among the relevant requirements are that the conditional statistic has a well-defined target, the simulation errors are controlled in an appropriate sense, and the iterates remain in a region where the model and M-step behave regularly. With latent-effect Markov chains, dependence and inadequate exploration can undermine the intended simulation behaviour. A mathematically valid gain sequence cannot repair a chain that fails to represent the required conditional distribution.

In practice, check the sequence itself separately from the simulation and parameter behaviour. For a proposed deterministic sequence, verify positivity, any imposed upper bound, divergence of the gain sum, and convergence of the squared-gain sum. Do not infer the two infinite-series properties from a short list of initial gains. During fitting, interpret persistent statistic or parameter fluctuations in light of both the gains and the latent-effect simulation; a noisy trace alone does not identify which component is responsible.

The two conditions also do not prescribe how quickly gains should decrease at each stage, how many latent-effect draws to use, or how to choose a transition between phases of an algorithm. Those are separate implementation questions. Nor do summability conditions ensure that the objective has a unique optimum, that the M-step is solved accurately, or that the estimate has good finite-sample properties.

Common Mistake

Common mistake: “The gain tends to zero, so simulation noise must vanish and the SAEM statistic will converge.” Tending to zero alone is insufficient: $k^{-1/2}$ tends to zero but its squared gains have a divergent sum. Conversely, a sequence can have a finite sum of squared gains yet have a finite total gain, as $2^{-k}$ does. Check both conditions, then consider the simulation and stability assumptions; neither step alone proves convergence.

Key takeaway: Robbins–Monro gains satisfy $\sum_k\gamma_k=\infty$ and $\sum_k\gamma_k^2<\infty$. The divergent total gain preserves the capacity to adapt, while the finite squared-gain total limits accumulated random variation under suitable noise assumptions. These are necessary elements of a convergence argument, not a substitute for its other assumptions.

Check Your Understanding

Answer each question, then compare with the solutions below.

For $\gamma_k=1/k$, do the gains satisfy both Robbins–Monro summability conditions? Explain using series tests.
For $\gamma_k=1/(k+1)^{1.2}$, which condition fails?
If $S_{k-1}=8$, $s(y,U_k)=12$, and $\gamma_k=0.10$, calculate $S_k$.
Why is it incorrect to conclude that $\gamma_k=k^{-1/2}$ meets the standard conditions just because $\gamma_k\to0$?
Name one important reason the two gain conditions alone cannot guarantee SAEM convergence.

Solutions. (1) The harmonic series $\sum_k1/k$ diverges, while $\sum_k1/k^2$ converges, so both conditions hold. (2) The gain sum has p-series exponent $1.2>1$ and is finite, so the nonsummability condition fails; its squared sum also converges. (3) $S_k=8+0.10(12-8)=8+0.4=8.4$. (4) Its squared sequence is $1/k$, whose sum diverges, so square summability fails. (5) For example, a latent-effect Markov chain may not adequately represent the required conditional distribution, or the parameter iterates may not remain stable; additional regularity and noise-control assumptions are needed.