Key points are not available for this paper at this time.
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 Formula: see text for which Formula: see text can only be estimated by (asymptotically) unbiased observations Formula: see text. We consider here the case where Formula: see text is an a sequence of independent and identically distributed random variables sequence or a uniformly geometrically ergodic Markov chain. We derive pth 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 Formula: see text of the underlying chain and the norm of the noise variables. We emphasize that our result requires the LSA step size to scale only with logarithm of the problem dimension d. Funding: The work of A. Durmus and E. Moulines was partly supported by Grant ANR-19-CHIA-0002. This project received funding from the European Research Council ERC-SyG OCEAN Grant 101071601. The research of A. Naumov and S. Samsonov was prepared within the framework of the HSE University Basic Research Program.
Durmus et al. (Tue,) studied this question.