mlsanityData to 7 Oct 2026

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

arXiv 2207.04475 ↗First posted 10 Jul 2022stat.ML cs.LG math.PRcited by 41

Not on the map. Why?

Abstract (arXiv)

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 barA θ = barb for which (barA, barb) can only be estimated by (asymptotically) unbiased observations (A(Zn),b(Zn))_n ∈ mathbbN. We consider here the case where Zn_n ∈ mathbbN is an i.i.d. 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_operatornamemix of the underlying chain and the norm of the noise variables. We emphasize that our result requires the SA step size to scale only with logarithm of the problem dimension d.

Key facts. Cited by 41 papers in the map (data through 7 Oct 2026). Builds on 10 of its 46 references that are in the map. First posted on arXiv 10 Jul 2022.

Builds on

10 of 46 references.

References · 10

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  2. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  3. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  4. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  5. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 65
  6. 2021Optimal and instance-dependent guarantees for Markovian linear stochastic approximationcited by 33
  7. 2019A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Boundcited by 31
  8. 2021Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsizecited by 26
  9. 2021On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learningcited by 22
  10. 2020Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximationcited by 19

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 9; 2024: 10; 2025: 12; 2026: 9.

41 papers.

Sort:

  1. 2022Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizescited by 28
  2. 2023Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noisecited by 26
  3. 2023Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stabilitycited by 20
  4. 2024Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learningcited by 19
  5. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolationcited by 17
  6. 2024Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learningcited by 17
  7. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  8. 2023Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noisecited by 14
  9. 2024Revisiting Step-Size Assumptions in Stochastic Approximationcited by 10
  10. 2023The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learningcited by 6
  11. 2024SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learningcited by 6
  12. 2024Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolationcited by 6
29 more
  1. 2025Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximationcited by 6
  2. 2023Rosenthal-type inequalities for linear statistics of Markov chainscited by 5
  3. 2023High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariancecited by 5
  4. 2023Effectiveness of Constant Stepsize in Markovian LSA and Statistical Inferencecited by 5
  5. 2024Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Waycited by 5
  6. 2025A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximationcited by 5
  7. 2025A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averagingcited by 4
  8. 2025Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to Q-Learningcited by 2
  9. 2025Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximationcited by 2
  10. 2026A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averagingcited by 2
  11. 2023Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regressioncited by 1
  12. 2024Is Thompson Sampling Susceptible to Algorithmic Collusion?cited by 1
  13. 2024A Finite-Sample Analysis of an Actor-Critic Algorithm for Mean-Variance Optimization in a Discounted MDPcited by 1
  14. 2025Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Samplingcited by 1
  15. 2025On the Rate of Gaussian Approximation for Linear Regression Problemscited by 1
  16. 2025Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspectivecited by 1
  17. 2025Parameter-Free Federated TD Learning with Markov Noise in Heterogeneous Environmentscited by 1
  18. 2025Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δcited by 1
  19. 2026Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Frameworkcited by 1
  20. 2024MCMC-driven learningcited by 0
  21. 2025Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximationcited by 0
  22. 2025A note on concentration inequalities for the overlapped batch mean variance estimators for Markov chainscited by 0
  23. 2026Stability and Sensitivity Analysis of Relative Temporal-Difference Learning: Extended Versioncited by 0
  24. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 0
  25. 2026On Gaussian approximation for entropy-regularized Q-learning with function approximationcited by 0
  26. 2026Mathematical methods of reinforcement learningcited by 0
  27. 2026Finite-Time Analysis of Discounted Exponential-Utility Reinforcement Learningcited by 0
  28. 2026Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noisecited by 0
  29. 2026Sharp Stationary Gaussian Approximation for Constant-Stepsize SGDcited by 0