Almost Sure Convergence

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 21 of 22 Suppose the expectation and variance calculations give: $$ \mathbb{E}[\Delta_k]\to0, \qquad \operatorname{Var}(\Delta_k)\to0. $$What kind of convergence follows? From the Second Moment to Probability By the variance identity: $$ \operatorname{Var}(\Delta_k) = \mathbb{E}[\Delta_k^2] - \left(\mathbb{E}[\Delta_k]\right)^2. $$Therefore: $$ \mathbb{E}[\Delta_k^2] = \operatorname{Var}(\Delta_k) + \left(\mathbb{E}[\Delta_k]\right)^2. $$Both terms approach zero, so: $$ \mathbb{E}[\Delta_k^2]\to0. $$For every $\varepsilon>0$, Chebyshev’s inequality gives: $$ \mathbb{P}(|\Delta_k|>\varepsilon) \le \frac{\mathbb{E}[\Delta_k^2]}{\varepsilon^2} \longrightarrow0. $$Hence: $$ \Delta_k\xrightarrow{p}0. $$This is convergence in probability. ...