Robbins-Monro

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