  This paper provides a finite-time analysis of linear stochastic approximation
(LSA) algorithms with fixed step size, a core method in statistics and machine
learning. LSA is used to compute approximate solutions of a $d$-dimensional
linear system $\bar{\mathbf{A}} \theta = \bar{\mathbf{b}}$ for which
$(\bar{\mathbf{A}}, \bar{\mathbf{b}})$ can only be estimated by
(asymptotically) unbiased observations
$\{(\mathbf{A}(Z_n),\mathbf{b}(Z_n))\}_{n \in \mathbb{N}}$. We consider here
the case where $\{Z_n\}_{n \in \mathbb{N}}$ is an i.i.d. sequence or a
uniformly geometrically ergodic Markov chain. We derive $p$-th moment and
high-probability deviation bounds for the iterates defined by LSA and its
Polyak-Ruppert-averaged version. Our finite-time instance-dependent bounds for
the averaged LSA iterates are sharp in the sense that the leading term we
obtain coincides with the local asymptotic minimax limit. Moreover, the
remainder terms of our bounds admit a tight dependence on the mixing time
$t_{\operatorname{mix}}$ of the underlying chain and the norm of the noise
variables. We emphasize that our result requires the SA step size to scale only
with logarithm of the problem dimension $d$.
