Series: Stochastic Approximation from First Principles · Part 12 of 22

The Robbins–Monro conditions specify how a stochastic-approximation step-size sequence should decay:

$$ \sum_k\alpha_k=\infty, \qquad \sum_k\alpha_k^2<\infty. $$

The first condition keeps the total corrective force large enough to remove old error. The second makes later steps small enough to control the accumulated effect of noise.

One Coefficient Controls Two Forces

The error recursion is:

$$ \Delta_{k+1} = (1-\alpha_k)\Delta_k + \alpha_k\eta_k. $$

Its two terms pull in different directions:

  • $(1-\alpha_k)\Delta_k$ contracts the old error.
  • $\alpha_k\eta_k$ injects a new disturbance.

The step size is therefore more than a generic learning rate. It controls both:

  1. whether the iteration keeps correcting what is already wrong;
  2. how much new noise enters at each step.

In the river analogy, a larger $\alpha_k$ corrects your old route more aggressively, but it also lets the latest echo change your position more aggressively.

The First Condition Keeps Learning Alive

$$ \sum_k\alpha_k=\infty $$

prevents the total step size from becoming finite. If $\alpha_k$ decays too fast, the process can stop making meaningful corrections before reaching the target.

This is the requirement to keep walking.

The Second Condition Limits Noise Energy

$$ \sum_k\alpha_k^2<\infty $$

controls the disturbance because the variance of $\alpha_k\eta_k$ scales with $\alpha_k^2$.

This is the requirement to keep later observations from repeatedly moving the estimate by large amounts.

Why the Conditions Are Not Contradictory

The first condition says that $\alpha_k$ cannot decay too fast:

The total amount of correction must remain infinite.

The second says that it must decay fast enough:

The squared strength of the injected noise must have a finite total.

A standard example is:

$$ \alpha_k=\frac{1}{k}, $$

because:

$$ \sum_k\frac{1}{k}=\infty, \qquad \sum_k\frac{1}{k^2}<\infty. $$

Three Schedules, Three Outcomes

The two conditions distinguish schedules that can look similarly small at a glance:

  • $\alpha_k=1/(k+1)$: the total correction remains infinite while the squared step sizes are summable. This is the canonical balance.
  • $\alpha_k=1/(k+1)^2$: the total correction is finite, so the traveler can stop making meaningful progress before reaching the river.
  • $\alpha_k=1/\sqrt{k+1}$: the total correction is infinite, but the squared step sizes behave like the harmonic series. Repeated sound errors continue to inject too much cumulative noise.

It is therefore not enough that $\alpha_k\to0$. The rate of decay determines whether the route preserves enough correction while suppressing enough noise.

The step size must decay slowly enough to sustain learning and quickly enough to suppress noise.

In the forest, you must always retain the ability to adjust your route, but later in the journey you cannot allow one sound to trigger a large move. Otherwise you either stop in the forest or keep wandering with every echo.

The two conditions create the mechanism boundary: the willingness to learn must not vanish, while the weight assigned to noise must.