Paper detail

Convergence Rates and Decoupling in Linear Stochastic Approximation Algorithms

Almost sure convergence rates for linear algorithms $h_{k+1} = h_k +\frac{1}{k^χ} (b_k-A_kh_k)$ are studied, where $χ\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^{-γ})$ a.s. for the $γ\in[0,χ)$, positive definite $A$ and vector $b$ such that $\frac{1}{n^{χ-γ}}\sum\limits_{k=1}^n (A_{k}- A)\to 0$ and $\frac{1}{n^{χ-γ}}\sum\limits_{k=1}^n (b_k-b)\to 0$ a.s. When $χ-γ\in\left(\frac12,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.