Convergence

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

Series: Stochastic Approximation from First Principles · Part 20 of 22 The expectation can approach zero while the error remains widely dispersed. To determine whether noisy trajectories also concentrate, analyze: $$ \operatorname{Var}(\Delta_k). $$Isolate the Random Part Write the explicit recursion as: $$ \Delta_k=A_k+B_k, $$where: $$ A_k = \left[ \prod_{i=0}^{k-1}(1-\alpha_i) \right]\Delta_0 $$is deterministic, and: $$ B_k = \sum_{j=0}^{k-1}w_{j,k}\eta_j, $$with: $$ w_{j,k} = \left[ \prod_{i=j+1}^{k-1}(1-\alpha_i) \right]\beta_j. $$Because $A_k$ is deterministic: $$ \operatorname{Var}(\Delta_k)=\operatorname{Var}(B_k). $$If the noise terms are independent or at least uncorrelated: ...

Series: Stochastic Approximation from First Principles · Part 22 of 22 Dvoretzky’s recursion supports two natural proof routes: $$ \Delta_{k+1} = (1-\alpha_k)\Delta_k + \beta_k\eta_k. $$One expands $\Delta_k$ and studies its expectation and variance. The other studies the conditional drift of the energy $h_k=\Delta_k^2$. The routes are complementary. The first explains why the Robbins–Monro conditions are reasonable. The second gives the almost-sure convergence result. The Shared Mechanism Both routes rely on the same ideas: ...