On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration

Abstract

We undertake a precise study of the asymptotic and non-asymptotic properties of stochastic approximation procedures with Polyak-Ruppert averaging for solving a linear system $\bar{A}\theta =\bar{b}$. When the matrix $\bar{A}$ is Hurwitz, we prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity. The CLT characterizes the exact asymptotic covariance matrix, which is the sum of the classical Polyak-Ruppert covariance and a correction term that scales with the step size. Under assumptions on the tail of the noise distribution, we prove a non-asymptotic concentration inequality whose main term matches the covariance in CLT in any direction, up to universal constants. When the matrix $\bar{A}$ is not Hurwitz but only has non-negative real parts in its eigenvalues, we prove that the averaged LSA procedure actually achieves an $O(1/T)$ rate in mean-squared error. Our results provide a more refined understanding of linear stochastic approximation in both the asymptotic and non-asymptotic settings. We also show various applications of the main results, including the study of momentum-based stochastic gradient methods as well as temporal difference algorithms in reinforcement learning.

References in corpus (14)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Parallelizing Stochastic Gradient Descent for Least Squares Regression: mini-batching, averaging, and model misspecification
• Accelerating Stochastic Gradient Descent For Least Squares Regression
• Variance-reduced $Q$-learning is minimax optimal
• Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains
• Statistical Inference for Model Parameters in Stochastic Gradient Descent
• HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation
• Non-asymptotic Analysis of Biased Stochastic Approximation Scheme
• Stochastic approximation with cone-contractive operators: Sharp ${\ell }_{\infty }$-bounds for $Q$-learning
• Statistical Inference for the Population Landscape via Moment Adjusted Stochastic Gradients
• Statistical inference using SGD
• Instance-dependent ${\ell }_{\infty }$-bounds for policy evaluation in tabular reinforcement learning

Cited by in corpus (6)

• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques
• Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scaling
• Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis
• Online Covariance Matrix Estimation in Stochastic Gradient Descent
• Statistical Estimation and Inference via Local SGD in Federated Learning