Iterative Methods

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 4 of 22 In the update $$ w_{k+1}=w_k+\alpha_k(\text{target}_k-w_k), $$what does $\alpha_k$ actually represent? Separate Direction from Distance Treat the update as a vector movement: $$ w_{k+1} =w_k+ \underbrace{\alpha_k\|\text{target}_k-w_k\|}_{\text{actual distance moved}} \cdot \underbrace{ \frac{\text{target}_k-w_k} {\|\text{target}_k-w_k\|} }_{\text{unit direction}}. $$The vector $\text{target}_k-w_k$ contains both a direction and a distance: $\|\text{target}_k-w_k\|$ is the distance suggested by the latest observation. $\alpha_k\|\text{target}_k-w_k\|$ is the distance the update actually moves. $\alpha_k$ is the fraction of the suggested movement that the update accepts. In the river analogy, you walk an $\alpha_k$ fraction of the estimated distance toward the location implied by the current sound. The step size is therefore both a movement ratio and a degree of trust in the latest estimate. ...

Series: Stochastic Approximation from First Principles · Part 7 of 22 The choice between $\alpha=1$ and $\alpha<1$ changes meaning as soon as the target contains noise. Without Noise Step size Update Meaning $\alpha=1$ $w_{k+1}=w^*$ The current observation is the exact target $0<\alpha<1$ $w_{k+1}=(1-\alpha)w_k+\alpha w^*$ Moves partway from the current position to the target If the target judgment is exact and the model allows direct movement, $\alpha=1$ is the fastest choice: a riverbank at 100 meters and a target of 100 meters produce immediate arrival. ...