Step Size

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

Series: Stochastic Approximation from First Principles · Part 13 of 22 Why does stochastic approximation require: $$ \sum_k\alpha_k=\infty? $$In the river analogy, the condition asks: If I become less willing to trust each new sound, could I stop moving before I reach the river? The Iteration Must Retain Enough Movement The actual length of step $k$ is: $$ \alpha_k\|\text{target}_k-w_k\|. $$The total distance moved is: $$ \sum_k \alpha_k\|\text{target}_k-w_k\|. $$We control $\alpha_k$, but we do not directly control the remaining true error. The desired result is: ...

Series: Stochastic Approximation from First Principles · Part 14 of 22 Why does stochastic approximation also require: $$ \sum_k\alpha_k^2<\infty? $$The constant-step calculation gives an intuitive variance comparison, but a real stochastic-approximation schedule changes with $k$. We need a form that works for an entire sequence. Expand a Variable-Step Update Start with: $$ w_{k+1} = (1-\alpha_k)w_k + \alpha_k(w^*+\eta_k). $$The first two updates are: $$ w_1=(1-\alpha_0)w_0+\alpha_0(w^*+\eta_0), $$$$ \begin{aligned} w_2 &=(1-\alpha_1)w_1+\alpha_1(w^*+\eta_1)\\ &=(1-\alpha_1)(1-\alpha_0)w_0\\ &\quad+(1-\alpha_1)\alpha_0(w^*+\eta_0) +\alpha_1(w^*+\eta_1). \end{aligned} $$In general: ...