Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize

2021/06/02 by Alain Durmus, Éric Moulines, Durmus, Alain +9 · 5 citations
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Probability (math.PR) #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2106.01257

openalex publication_date 2021/06/02 · openalex created_date 2021/06/22 · openalex updated_date 2026/07/28

Abstract

This paper provides a non-asymptotic analysis of linear stochastic approximation (LSA) algorithms with fixed stepsize. This family of methods arises in many machine learning tasks and is used to obtain approximate solutions of a linear system Aθ= b for which A and b can only be accessed through random estimates \(\bf A_n, \bf b_n): n ∈ ℕ^*\. Our analysis is based on new results regarding moments and high probability bounds for products of matrices which are shown to be tight. We derive high probability bounds on the performance of LSA under weaker conditions on the sequence \(\bf A_n, \bf b_n): n ∈ ℕ^*\ than previous works. However, in contrast, we establish polynomial concentration bounds with order depending on the stepsize. We show that our conclusions cannot be improved without additional assumptions on the sequence of random matrices \\bf A_n: n ∈ ℕ^*\, and in particular that no Gaussian or exponential high probability bounds can hold. Finally, we pay a particular attention to establishing bounds with sharp order with respect to the number of iterations and the stepsize and whose leading terms contain the covariance matrices appearing in the central limit theorems.

Citations

• Stochastic Approximation: A Dynamical Systems Viewpoint

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
• Statistical Guarantees for High-Dimensional Stochastic Gradient Descent
• Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning
• On the Rate of Gaussian Approximation for Linear Regression Problems

Related

• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
• Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation
• Statistical inference for Linear Stochastic Approximation with Markovian Noise
• Linear Stochastic Approximation: Constant Step-Size and Iterate\n Averaging
• Convergence Rates and Decoupling in Linear Stochastic Approximation Algorithms