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

• 成果类型: Article
• 署名作者: Durmus, Alain; Moulines, Eric; Naumov, Alexey; Samsonov, Sergey
• 署名单位: Institut Polytechnique de Paris; Ecole Polytechnique; HSE University (National Research University Higher School of Economics); Russian Academy of Sciences; Steklov Mathematical Institute of the Russian Academy of Sciences; Kharkevich Institute for Information Transmission Problems of the RAS
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.0179
• 发表日期: 2025

摘要

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 (A) over bar theta = (b) over bar for which ((A) over bar, (b) over bar) can only be estimated by (asymptotically) unbiased observations {(A(Z(n)),b(Z(n)))}(n is an element of N). We consider here the case where {Z(n)}(n is an element of N) 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 t(mix) 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.