Variance

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