Finite-Time High-Probability Bounds for Polyak–Ruppert Averaged Iterates of Linear Stochastic Approximation

Mathematics of Operations Research. 2025. Vol. 50. No. 2. P. 935–964.

Durmus A., Moulines E., Naumov A., Samsonov S.

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.

Keywords: цепи Маркова, Markov chains, linear stochastic approximation, стохастическая аппроксимация

Publication based on the results of: Development and theoretical analysis of new effective stochastic machine learning algorithms (2024)