Technical

Series: Stochastic Approximation from First Principles · Part 20 of 22 The expectation can approach zero while the error remains widely dispersed. To determine whether noisy trajectories also concentrate, analyze: $$ \operatorname{Var}(\Delta_k). $$Isolate the Random Part Write the explicit recursion as: $$ \Delta_k=A_k+B_k, $$where: $$ A_k = \left[ \prod_{i=0}^{k-1}(1-\alpha_i) \right]\Delta_0 $$is deterministic, and: $$ B_k = \sum_{j=0}^{k-1}w_{j,k}\eta_j, $$with: $$ w_{j,k} = \left[ \prod_{i=j+1}^{k-1}(1-\alpha_i) \right]\beta_j. $$Because $A_k$ is deterministic: $$ \operatorname{Var}(\Delta_k)=\operatorname{Var}(B_k). $$If the noise terms are independent or at least uncorrelated: ...

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

Series: Stochastic Approximation from First Principles · Part 22 of 22 Dvoretzky’s recursion supports two natural proof routes: $$ \Delta_{k+1} = (1-\alpha_k)\Delta_k + \beta_k\eta_k. $$One expands $\Delta_k$ and studies its expectation and variance. The other studies the conditional drift of the energy $h_k=\Delta_k^2$. The routes are complementary. The first explains why the Robbins–Monro conditions are reasonable. The second gives the almost-sure convergence result. The Shared Mechanism Both routes rely on the same ideas: ...