Dvoretzky

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 16 of 22 The entry point to Dvoretzky’s proof is not the signed error $\Delta_k$, but the squared error: $$ h_k=\Delta_k^2. $$This transforms an error that can change direction into a nonnegative energy. The proof first shows that this energy converges, then uses persistent contraction to rule out any positive limit. Why Square the Error Start from: $$ \Delta_{k+1} = (1-\alpha_k)\Delta_k + \beta_k\eta_k. $$Directly tracking $\Delta_k$ is difficult because it can be positive, negative, and repeatedly pushed across zero by noise. ...

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