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

2022/07/10 by Alain Durmus, Durmus, Alain, Éric Moulines +5 · 6 citations
Engineering · Mathematics · #60J20 #62L20 #Control Systems and Identification #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Statistical Methods and Inference #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2207.04475

openalex publication_date 2022/07/10 · openalex created_date 2022/07/13 · openalex updated_date 2026/07/28

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 ∈ ℕ}. We consider here the case where \Z_n\_{n ∈ ℕ} 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_mix 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.

Cited by

• Statistical Inference for Linear Functionals of Online Least-squares SGD when t \gtrsim d^1+δ
• Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation
• Parameter-Free Federated TD Learning with Markov Noise in Heterogeneous Environments
• Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspective
• On the Rate of Gaussian Approximation for Linear Regression Problems
• Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to Q-Learning

Related

• Linear Stochastic Approximation: Constant Step-Size and Iterate\n Averaging
• Statistical inference for Linear Stochastic Approximation with Markovian Noise
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
• Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation