Error Recursion

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