Stochastic Approximation

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

Series: Stochastic Approximation from First Principles · Part 15 of 22 Dvoretzky’s convergence theorem abstracts the stochastic-approximation error recursion into: $$ \Delta_{k+1} = (1-\alpha_k)\Delta_k + \beta_k\eta_k. $$It states that if old error is contracted persistently, the noise is conditionally unbiased, and the accumulated noise strength is finite, then the error converges to zero almost surely. The Missing Result The earlier parts derived: $$ \Delta_{k+1} = (1-\alpha_k)\Delta_k + \alpha_k\eta_k, $$along with: $$ \sum_k\alpha_k=\infty, \qquad \sum_k\alpha_k^2<\infty, $$and basic noise assumptions such as: ...

Series: Stochastic Approximation from First Principles · Part 16 of 22 The entry point to Dvoretzky’s proof is not the signed error $\Delta_k$, but the squared error: $$ h_k=\Delta_k^2. $$This transforms an error that can change direction into a nonnegative energy. The proof first shows that this energy converges, then uses persistent contraction to rule out any positive limit. Why Square the Error Start from: $$ \Delta_{k+1} = (1-\alpha_k)\Delta_k + \beta_k\eta_k. $$Directly tracking $\Delta_k$ is difficult because it can be positive, negative, and repeatedly pushed across zero by noise. ...

Series: Stochastic Approximation from First Principles · Part 17 of 22 The energy proof controls entire sample paths. A more direct route expands $\Delta_k$ and studies: $$ \mathbb{E}[\Delta_k] \quad\text{and}\quad \operatorname{Var}(\Delta_k). $$If both approach zero, the distribution of $\Delta_k$ concentrates near zero. This route is intuitive, but it usually proves convergence in probability rather than the almost-sure convergence in Dvoretzky’s theorem. The Simplified Setting Begin with: $$ \Delta_{k+1} = (1-\alpha_k)\Delta_k + \beta_k\eta_k. $$For this route, treat $\alpha_k$ and $\beta_k$ as given coefficients and use ordinary assumptions such as zero-mean, bounded-variance, independent or uncorrelated disturbances. ...

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 19 of 22 The explicit error formula is: $$ \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. $$For this simplified calculation, treat $\alpha_i$ and $\beta_j$ as given coefficients and assume ordinary zero-mean noise. The full theorem replaces ordinary zero mean with conditional zero mean given the history. Take the Expectation If: $$ \mathbb{E}[\eta_j]=0, $$then: $$ \begin{aligned} \mathbb{E}[\Delta_k] &= \left[ \prod_{i=0}^{k-1}(1-\alpha_i) \right]\Delta_0\\ &\quad+ \sum_{j=0}^{k-1} \left[ \prod_{i=j+1}^{k-1}(1-\alpha_i) \right]\beta_j \underbrace{\mathbb{E}[\eta_j]}_{0}. \end{aligned} $$Therefore: ...

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