Stochastic approximation

Remarks

Example: let $Z_1, Z_2, \dots$ be independent with common mean $m$, and take $h(\theta) = m - \theta$, $Y_{n+1} = Z_{n+1} - \theta_n$ and $a_n = 1/(n+1)$, with $\theta_0 = 0$. Then $E[Y_{n+1} \mid \mathcal{F}_n] = m - \theta_n$, and by induction $\theta_n = (Z_1 + \cdots + Z_n)/n$, the sample mean, which tends to the zero $m$ of $h$.

Non-example: the deterministic Newton iteration $\theta_{n+1} = \theta_n - h(\theta_n)/h'(\theta_n)$ is not a stochastic approximation algorithm, since it needs exact values of $h$ and $h'$ rather than noisy observations, so clause 3 fails.

The usual conditions on the step sizes are $\sum_n a_n = \infty$ and $\sum_n a_n^2 < \infty$. The first condition lets the iterates travel any distance, and the second makes the accumulated noise $\sum_n a_n (Y_{n+1} - h(\theta_n))$ converge. Writing the noise as a martingale difference sequence, the iterates follow, in the long run, the ordinary differential equation $\dot\theta = h(\theta)$.