Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation

Abstract

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 through (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, and derive \(p\)-moments inequality and high probability bounds for the iterates defined by LSA and its Polyak-Ruppert averaged version. More precisely, we establish bounds of order \((p \alpha t_{\operatorname{mix}})^{1/2}d^{1/p}\) on the \(p\)-th moment of the last iterate of LSA. In this formula \(\alpha\) is the step size of the procedure and \(t_{\operatorname{mix}}\) is the mixing time of the underlying chain (\(t_{\operatorname{mix}}=1\) in the i.i.d. setting). We then prove finite-time instance-dependent bounds on the Polyak-Ruppert averaged sequence of iterates. These results are sharp in the sense that the leading term we obtain matches the local asymptotic minimax limit, including tight dependence on the parameters \((d,t_{\operatorname{mix}})\) in the higher order terms.