Stochastic Approximation

Series: Stochastic Approximation from First Principles · Part 1 of 22 Stochastic approximation studies a basic question: can an iterative update converge when every target observation contains noise? Robbins and Monro introduced the framework in 1951, and Dvoretzky gave a general convergence theorem in 1956. Its basic form is: $$ \text{New}=\text{Old}+\alpha(\text{Target}-\text{Old}). $$Imagine searching for a river at night. Let $w_k$ denote your actual position after step $k$. The riverbank has a fixed true location $w^*$, but you cannot see or use it directly. You can only listen to the water and form a location judgment, $\text{target}_k$. ...

Series: Stochastic Approximation from First Principles · Part 2 of 22 After writing the update $$ w_{k+1}=w_k+\alpha_k(\text{target}_k-w_k), $$we need a quantity that tells us whether the iteration is approaching the true target. In the forest analogy, the question is: Am I moving toward the river, or merely moving around the forest? Two Ways to Define Error The first option is the change between consecutive iterates: $$ w_{k+1}-w_k = \alpha_k(\text{target}_k-w_k) = \alpha_k(w^*+\eta_k-w_k). $$The second option is the displacement from the current position to the true target: ...

Series: Stochastic Approximation from First Principles · Part 3 of 22 To prove that a noisy update converges, we must constrain both the mechanism we control and the noise we do not. The original update is: $$ w_{k+1}=w_k+\alpha_k(w^*+\eta_k-w_k), $$and its error recursion is: $$ \Delta_{k+1}=(1-\alpha_k)\Delta_k+\alpha_k\eta_k. $$Assumptions on the Step Size The standard conditions are: $$ 0\le\alpha_k<1, $$$$ \sum_k\alpha_k=\infty, $$and: $$ \sum_k\alpha_k^2<\infty. $$Each controls a different failure mode: $0\le\alpha_k<1$ keeps each new position between the current position and the noisy target. $\sum_k\alpha_k=\infty$ prevents the process from losing the ability to correct its initial error. $\sum_k\alpha_k^2<\infty$ limits the cumulative strength with which noise enters the system. Assumptions on the Noise At the basic level, the disturbance sequence $\{\eta_k\}$ is assumed to satisfy: ...

Series: Stochastic Approximation from First Principles · Part 4 of 22 In the update $$ w_{k+1}=w_k+\alpha_k(\text{target}_k-w_k), $$what does $\alpha_k$ actually represent? Separate Direction from Distance Treat the update as a vector movement: $$ w_{k+1} =w_k+ \underbrace{\alpha_k\|\text{target}_k-w_k\|}_{\text{actual distance moved}} \cdot \underbrace{ \frac{\text{target}_k-w_k} {\|\text{target}_k-w_k\|} }_{\text{unit direction}}. $$The vector $\text{target}_k-w_k$ contains both a direction and a distance: $\|\text{target}_k-w_k\|$ is the distance suggested by the latest observation. $\alpha_k\|\text{target}_k-w_k\|$ is the distance the update actually moves. $\alpha_k$ is the fraction of the suggested movement that the update accepts. In the river analogy, you walk an $\alpha_k$ fraction of the estimated distance toward the location implied by the current sound. The step size is therefore both a movement ratio and a degree of trust in the latest estimate. ...

Series: Stochastic Approximation from First Principles · Part 5 of 22 Why should $\alpha_k$ lie between zero and one? The answer has two parts: geometry explains overshooting, and the error recursion explains noise amplification. Geometry Without Noise If $\eta_k=0$, then: $$ w_{k+1}=(1-\alpha_k)w_k+\alpha_k w^*. $$The result depends on the value of $\alpha_k$: Step size Position of $w_{k+1}$ Behavior $\alpha_k\in(0,1)$ Between $w_k$ and $w^*$ Moves steadily toward the target $\alpha_k=1$ Exactly at $w^*$ Reaches the target in one step $\alpha_k>1$ Beyond $w^*$ Overshoots and may oscillate In the river analogy, $\alpha_k>1$ means walking past the estimated river location. With no noise, that merely overshoots the river. With noise, it overshoots a location that may already be wrong. ...

Series: Stochastic Approximation from First Principles · Part 6 of 22 Step sizes above one can amplify noise and overshoot the target. But what about $\alpha=1$? Without noise, it reaches the target in one step. Under persistent noise, the same choice becomes a memoryless update. The Argument in One Chain The logic is: With no noise, $\alpha=1$ reaches $w^*$ immediately. With noise, it becomes $w_{k+1}=w^*+\eta_k$ and discards all history. With $\alpha<1$, the new position retains weight from the previous position as well as the new judgment. Both updates can be unbiased, but the history-preserving update can have lower variance. That advantage depends on assumptions about the noise: zero mean, finite variance, independence, and identical distribution in the simplified analysis. If $\alpha$ must remain one, convergence requires the noise itself to vanish. What Changes When Alpha Equals One The traveler executes $w_{k+1}=(1-\alpha)w_k+\alpha\text{target}_k$. After the analyst substitutes $\text{target}_k=w^*+\eta_k$, this becomes: ...

Series: Stochastic Approximation from First Principles · Part 7 of 22 The choice between $\alpha=1$ and $\alpha<1$ changes meaning as soon as the target contains noise. Without Noise Step size Update Meaning $\alpha=1$ $w_{k+1}=w^*$ The current observation is the exact target $0<\alpha<1$ $w_{k+1}=(1-\alpha)w_k+\alpha w^*$ Moves partway from the current position to the target If the target judgment is exact and the model allows direct movement, $\alpha=1$ is the fastest choice: a riverbank at 100 meters and a target of 100 meters produce immediate arrival. ...

Series: Stochastic Approximation from First Principles · Part 8 of 22 When $\alpha=1$, the update $$ w_{k+1}=w^*+\eta_k $$looks memoryless. That resemblance can be confused with the Markov property, but the two ideas are not equivalent. A Memoryless Update Fully Trusts the Current Observation At $\alpha_k=1$: $$ w_{k+1}=\text{target}_k=w^*+\eta_k. $$The update: ignores the previous state $w_k$; gives the previous position zero weight in the new position; depends only on the current noisy target. In the river analogy, you completely trust the latest sound and move directly to the location it suggests. The difficulty is that $\text{target}_k$ is not the river. It is an estimate contaminated by location error. ...

Series: Stochastic Approximation from First Principles · Part 9 of 22 Suppose the statistical properties of $\eta_k$ are known, while the behavior of $w_k$ is what we want to determine. We can use the former to compare two update mechanisms: $\alpha=1$ and $0<\alpha<1$. The goal is a traveler whose position is centered on the true riverbank $w^*$ and whose individual journeys do not fluctuate excessively. The Memoryless Update With $\alpha=1$: $$ w_{k+1}=w^*+\eta_k. $$Therefore: ...

Series: Stochastic Approximation from First Principles · Part 10 of 22 Preserving history helps only when the history contains enough signal to average out the noise. The usual noise assumptions explain when that hope is justified. In the river analogy, $\eta_k$ is not the wind or the echo itself. It is the location error produced after those physical disturbances affect your judgment: $$ \eta_k=\text{target}_k-w^*. $$The assumptions describe the errors in the inferred target. ...