The most useful estimator in an experiment is sometimes not the last estimate.

It is the average of the estimates after the experiment has stopped flailing.

That sentence sounds too plain to deserve a theory. Robbins and Monro made it precise in 1951 by asking a small, stubborn question:

how do you solve M(theta) = alpha
when M(theta) is only visible through noisy experiments?

No closed-form curve. No batch dataset. At each step you choose a point \(\theta_n\), observe a random response \(Y_n\) whose expectation is \(M(\theta_n)\), and move again.1

The classical update is:

\[\theta_{n+1} = \theta_n - a_n\left(Y_n-\alpha\right).\]

If the observed response is too often above the target, move down. If it is too often below the target, move up. The algorithm is a thermostat for an unknown regression curve.

The step sizes \(a_n\) have to obey a peculiar contract:

\[\sum_n a_n = \infty, \qquad \sum_n a_n^2 < \infty.\]

The first condition says the algorithm never fully loses the ability to correct a bad early guess. The second says the accumulated noise does not keep the iterate shaking forever.

That contract is the whole mood of stochastic approximation.

A Binary Experiment

The lab below hides a monotone response curve. The target response probability is 65%, and the true root is 0.350. At each iteration the algorithm chooses the current \(\theta\), receives one or more Bernoulli responses, and applies a Robbins-Monro update.

It also keeps a tail average of the iterates. This is the Polyak-Ruppert move: let the noisy path search, then average the part of the path that is plausibly near the root.23

With the default settings, across 80 deterministic replicas:

raw final RMSE        0.0445
tail-averaged RMSE   0.0417
final step size      0.00565

That is deliberately not a miraculous difference. The point is subtler. The last iterate is one noisy endpoint. The average is a low-pass report from the late path.

Deterministic browser experiment. The displayed curve is known to the lab for auditing, but the Robbins-Monro iterate only sees noisy Bernoulli responses at the current probe point.

Now try two small vandalism tests.

Set Exponent to 0.45. The square-sum condition fails. The raw endpoint keeps jittering; in the audited run the raw RMSE is 0.1095, while the tail average is 0.0416.

Set Exponent to 1.15. The total remaining movement becomes finite. The algorithm stops correcting too soon; the raw RMSE is about 1.08, and the average cannot save it.

The average is not a cure for a broken step schedule. It is a way to spend the noise left by a basically sane one.

The Root Is Not Observed

The original Robbins-Monro paper framed the problem as an unknown monotone regression function. The experimenter can prescribe levels, but only receives random responses. Their motivating example was quantile-like response / nonresponse data: choose a level, observe whether the random quantity fell below it, then move the next level.1

That matters because the algorithm is not merely “SGD with old notation.”

In a deterministic root finder, you might evaluate \(M(\theta)\) directly. In a batch estimator, you might collect a dataset and solve the estimating equation afterward. Robbins-Monro instead changes the future data collection point using the current noisy response.

The estimate is also an intervention.

Every point visited by the path is a small experimental design decision.

The Step Size Has Two Jobs

A step schedule \(a_n=c(n+n_0)^{-\gamma}\) has two visible jobs:

  1. reach the neighborhood of the root;
  2. keep late noise from dominating the report.

The famous condition

\[\sum_n a_n = \infty, \qquad \sum_n a_n^2 < \infty\]

turns into the rough exponent window:

1/2 < gamma <= 1

But that window is asymptotic. The lab’s gamma=1.00 can still be poor at finite time with the default gain and delay. It is technically in the window, but the path has not been given enough effective movement from the chosen start.

This is why step-size folklore is dangerous. The theorem says what must happen eventually under assumptions. A run still has a budget, an initial condition, a local slope, observation noise, and a finite patience.

Why Averaging Works

Polyak and Juditsky showed that averaging stochastic approximation trajectories can achieve the best possible asymptotic convergence rate in broad classical settings.3 Ruppert’s earlier technical report gave the same statistical intuition from a slowly convergent Robbins-Monro process.2

The informal picture is simple.

The raw iterate has two late components:

small bias from not being exactly at the root
fresh noise from the latest observations

Averaging many late iterates does not remove the systematic bias if the path is still far away. But once the path is wandering around the target, the independent parts of the noise begin to cancel.

That is why the average arrives late. Start averaging too early and you bake in the approach path. Start too late and you throw away useful variance reduction. Use a step size that dies too fast and both raw and averaged estimates inherit the same missed correction.

The lab’s Average starts control is a reminder that “average the iterates” is still a design choice.

SGD Is a Descendant, Not a Replacement

Modern stochastic gradient descent is one of the descendants of this idea. Bottou, Curtis, and Nocedal describe large-scale machine learning as a setting where stochastic gradient methods became central because exact deterministic optimization steps are often too expensive or too tied to one finite dataset.4

But the Robbins-Monro lens keeps one fact bright:

the stochastic step is an estimator before it is an optimizer

That framing changes the questions I would ask in a training run:

  1. What estimating equation is the update trying to solve?
  2. Is the step schedule still able to correct early bias?
  3. Is the late noise being reported as if it were signal?
  4. Would tail averaging, exponential moving averaging, or checkpoint averaging change the estimator being deployed?
  5. Are we judging the endpoint, the average, or the best validation checkpoint?

Those are not the same object.

A Receipt for Online Estimates

Before trusting an online stochastic estimate, I want a small receipt:

  • the exact step-size schedule, including warmup, delay, and decay;
  • the scale of the noisy observation used in the update;
  • a path plot, not only the endpoint;
  • a late-window average and the window used to compute it;
  • a repeated-run error distribution under a known simulator or replay;
  • a stress run where the step schedule fails.

The last item is important. A method that never shows how it fails is hard to recognize in production.

Robbins-Monro is beautiful because it is not overconfident. It says:

probe, move, shrink, average

The average is not more intelligent than the path.

It is just patient enough to ask the path what it kept seeing.

Paper Trail

  1. Herbert Robbins and Sutton Monro, “A Stochastic Approximation Method”, The Annals of Mathematical Statistics 22(3), 1951. A readable PDF mirror is available from Columbia. ↩ ↩2

  2. David Ruppert, “Efficient Estimations from a Slowly Convergent Robbins-Monro Process”, Cornell University Operations Research and Industrial Engineering Technical Report No. 781, 1988. ↩ ↩2

  3. Boris T. Polyak and Anatoli B. Juditsky, “Acceleration of Stochastic Approximation by Averaging”, SIAM Journal on Control and Optimization 30(4), 1992. ↩ ↩2

  4. Leon Bottou, Frank E. Curtis, and Jorge Nocedal, “Optimization Methods for Large-Scale Machine Learning”, SIAM Review 60(2), 2018. ↩