Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize

This paper provides a non-asymptotic analysis of linear stochastic approximation (LSA) algorithms with fixed stepsize. Our analysis is based on new results regarding moments and high probability bounds for products of matrices which are shown to be tight. We derive high probability bounds on the performance of LSA under weaker conditions on the sequence \{({\bf A}_n, {\bf b}_n): n \in \mathbb{N} *\} than previous works. However, in contrast, we establish polynomial concentration bounds with order depending on the stepsize. We show that our conclusions cannot be improved without additional assumptions on the sequence of random matrices \{{\bf A}_n: n \in \mathbb{N} *\}, and in particular that no Gaussian or exponential high probability bounds can hold.