Stochastic Approximation from First Principles

Stochastic approximation asks a simple question: if every observation is noisy, can repeated correction still reach the true target?

This series follows that question one knowledge card at a time. It begins with a hidden target and a noisy observation, derives the error recursion, studies how the step size balances correction against noise, and ends with the Robbins–Monro conditions and two routes to Dvoretzky’s convergence result.

The running example is a traveler trying to reach a river hidden in a forest. The traveler’s actual position is $w_k$. At step $k$, sound produces a noisy judgment $\text{target}_k$ of where the river lies, and the traveler walks a fraction $\alpha_k$ of the vector toward that judged location:

$$ w_{k+1}=w_k+\alpha_k(\text{target}_k-w_k). $$

The true riverbank $w^*$ is fixed but unknown to the traveler. It belongs to the analyst’s view of the journey and appears only when we decompose the judgment as $\text{target}_k=w^*+\eta_k$.

A traveler repeatedly follows noisy river-location judgments and converges toward the riverbank.

Part 1

Where Stochastic Approximation Begins: Learning from a Noisy Target

Stochastic approximation begins when the true target is hidden and each update can use only a noisy estimate of it.

Part 2

Model Error as Distance to the True Target

Why convergence should track distance to the true target rather than the size of the latest update.

Part 3

What a Noisy Iteration Needs in Order to Converge

A compact map of the step-size and noise assumptions behind stochastic-approximation convergence.

Part 4

What the Step Size Really Means

The step size is simultaneously a movement ratio, a trust coefficient, and a weight on new information.

Part 5

Why the Step Size Must Stay Below One under Noise

Step sizes between zero and one are the only range that combines monotone error contraction with attenuation of new noise.

Part 6

Why Alpha Cannot Equal One Under Persistent Noise

With alpha equal to one, every update discards history and inherits the full error of the latest noisy target.

Part 7

The Same Step Size Behaves Differently with and without Noise

Alpha equal to one is optimal for an exact target but accepts the full disturbance when the target is noisy.

Part 8

A Memoryless Update Is Not the Same as Markov Sufficiency

An update can erase the previous iterate without becoming Markov; Markov sufficiency is a property of the chosen state.

Part 9

Expectation and Variance Explain Why History Stabilizes an Update

A direct derivation compares memoryless and history-preserving updates under zero-mean finite-variance noise.

Part 10

What the Noise Assumptions Actually Buy Us

Zero mean, finite variance, independence, and identical distribution each support a different part of noise averaging.

Part 11

Alpha Equal to One Requires the Noise to Vanish

If every update fully replaces the current position, convergence requires the river-location judgment error itself to disappear.

Part 12

The Robbins–Monro Conditions Balance Learning and Noise

The step sizes must remain large enough to keep correcting error and become small enough to suppress accumulated noise.

Part 13

Why the Step Sizes Must Sum to Infinity

A finite total step size can make an iteration stop moving before its error has disappeared.

Part 14

Why the Squared Step Sizes Must Be Summable

For a changing step-size sequence, square summability bounds the total variance injected by noisy observations.

Part 15

Dvoretzky's Theorem Turns Noisy Contraction into Pathwise Convergence

Dvoretzky generalizes the stochastic-approximation error recursion and gives conditions for almost-sure convergence.

Part 16

Square the Error to Turn Convergence into Energy Dissipation

The Dvoretzky proof tracks squared error, shows that its positive drift is summable, and rules out a positive limiting energy.

Part 17

A Second Proof Route Starts from Expectation and Variance

Expanding the recursion explains how initial error and historical noise decay, but usually yields convergence in probability rather than almost-sure convergence.

Part 18

Expand the Error into Initial Bias and Historical Noise

The explicit error formula separates the residual initial condition from the weighted sum of all past disturbances.

Part 19

How the Initial Error Disappears in Expectation

Zero-mean noise removes the disturbance terms from the expectation, leaving a product that vanishes when the step sizes sum to infinity.

Part 20

How Historical Noise Is Attenuated

Each disturbance is controlled twice: by its entry coefficient and by every contraction that follows it.

Part 21

Why Mean-Square Analysis Stops at Convergence in Probability

Vanishing expectation and variance control each time slice, but they do not directly control the shape of an infinite sample path.

Part 22

Two Proof Routes Explain Different Levels of Convergence

Expectation and variance explain distributional concentration; the energy and martingale route proves almost-sure convergence.