Convergence Rates and Decoupling in Linear Stochastic Approximation Algorithms

Abstract

Almost sure convergence rates for linear algorithms $h_{k+1}=h_k+\frac{1}{k^{\chi }}(b_k-A_k{h}_k)$ are studied, where $\chi \in (0,1)$, $\{A_k{\}}_{k=1}^{\infty }$ are symmetric, positive semidefinite random matrices and $\{b_k{\}}_{k=1}^{\infty }$ are random vectors. It is shown that $|h_n-A^{-1}b|=o(n^{-\gamma })$ a.s. for the $\gamma \in [0,\chi )$, positive definite $A$ and vector $b$ such that $\frac{1}{n^{\chi -\gamma }}\sum _{k=1}^n(A_k-A)\to 0$ and $\frac{1}{n^{\chi -\gamma }}\sum _{k=1}^n(b_k-b)\to 0$ a.s. When $\chi -\gamma \in \left(\frac{1}{2},1\right)$, these assumptions are implied by the Marcinkiewicz strong law of large numbers, which allows the $\{A_k\}$ and $\{b_k\}$ to have heavy-tails, long-range dependence or both. Finally, corroborating experimental outcomes and decreasing-gain design considerations are provided.

27 pages