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

Alain Durmus (), Eric Moulines (), Alexey Naumov () and Sergey Samsonov ()
Additional contact information
Alain Durmus: Department of Applied Mathematics, Ecole Polytechnique, 91128 Palaiseau, France
Eric Moulines: Department of Applied Mathematics, Ecole Polytechnique, 91128 Palaiseau, France
Alexey Naumov: HSE University and Steklov Mathematical Institute of Russian Academy of Sciences, Moscow 101000, Russian Federation
Sergey Samsonov: HSE University and Institute for Information Transmission Problems, Moscow 101000, Russian Federation

Mathematics of Operations Research, 2025, vol. 50, issue 2, 935-964

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 A ¯ θ = b ¯ for which ( A ¯ , b ¯ ) can only be estimated by (asymptotically) unbiased observations { ( A ( Z n ) , b ( Z n ) ) } n ∈ N . We consider here the case where { Z n } n ∈ N is an a sequence of independent and identically distributed random variables 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 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 .

Keywords: Primary: 62L20; 60J20; linear stochastic approximation; Polyak–Ruppert averaging; stability of random matrix product (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.0179 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:50:y:2025:i:2:p:935-964

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().