Almost sure convergence rates for linear algorithms $h_{ k+1} = h_k +\frac{ 1}{ k^\chi} (b_k-A_kh_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\limits_{ k=1}^n (A_{ k}- A)\to 0$ and $\frac{ 1}{ n^{ \chi-\gamma}}\sum\limits_{ k=1}^n (b_k-b)\to 0$ a.s. When $\chi-\gamma\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.
Categories: math.ST stat.TH