Noise

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 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 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. ...

Series: Stochastic Approximation from First Principles · Part 11 of 22 If $\alpha=1$, the traveler moves directly to the latest inferred location: $$ w_{k+1}=\text{target}_k. $$The analyst can then substitute $\text{target}_k=w^*+\eta_k$: $$ w_{k+1}=w^*+\eta_k. $$For $w_k$ to converge to $w^*$, the disturbance itself must converge to zero: $$ \eta_k\to0. $$For mean-square convergence, this requires: $$ \mathbb{E}[\eta_k^2]\to0. $$If the errors are mean zero, this reduces to $\operatorname{Var}(\eta_k)\to0$. By contrast, a history-preserving mechanism can work with persistent noise whose variance remains finite: ...

Series: Stochastic Approximation from First Principles · Part 18 of 22 The recursion: $$ \Delta_{k+1} = (1-\alpha_k)\Delta_k + \beta_k\eta_k $$can be expanded into two sources of error: $$ \Delta_k = \left[ \prod_{i=0}^{k-1}(1-\alpha_i) \right]\Delta_0 + \sum_{j=0}^{k-1} \left[ \prod_{i=j+1}^{k-1}(1-\alpha_i) \right]\beta_j\eta_j. $$The first term carries the initial error. The second carries the entire history of disturbances. Expand the First Steps At the first update: $$ \Delta_1=(1-\alpha_0)\Delta_0+\beta_0\eta_0. $$At the second: $$ \begin{aligned} \Delta_2 &=(1-\alpha_1)\Delta_1+\beta_1\eta_1\\ &=(1-\alpha_1) \left[(1-\alpha_0)\Delta_0+\beta_0\eta_0\right] +\beta_1\eta_1\\ &=(1-\alpha_1)(1-\alpha_0)\Delta_0\\ &\quad+(1-\alpha_1)\beta_0\eta_0 +\beta_1\eta_1. \end{aligned} $$Continuing this substitution yields the general formula above. ...