mlsanityData to 14 Oct 2026

Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation

arXiv 2510.12375 ↗First posted 14 Oct 2025stat.ML cs.LG math.OCcited by 4

Not on the map. Why?

Abstract (arXiv)

In this paper, we refine the Berry-Esseen bounds for the multivariate normal approximation of Polyak-Ruppert averaged iterates arising from the linear stochastic approximation (LSA) algorithm with decreasing step size. We consider the normal approximation by the Gaussian distribution with covariance matrix predicted by the Polyak-Juditsky central limit theorem and establish the rate up to order n-1/3 in convex distance, where n is the number of samples used in the algorithm. We also prove a non-asymptotic validity of the multiplier bootstrap procedure for approximating the distribution of the rescaled error of the averaged LSA estimator. We establish approximation rates of order up to 1/√n for the latter distribution, which significantly improves upon the previous results obtained by Samsonov et al. (2024).

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 20 of its 54 references that are in the map. First posted on arXiv 14 Oct 2025.

Builds on

20 of 54 references.

References · 20

  1. 2015An Introduction to Matrix Concentration Inequalitiescited by 397
  2. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  3. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  4. 2016Statistical Inference for Model Parameters in Stochastic Gradient Descentcited by 71
  5. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 68
  6. 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
  7. 2020Online Covariance Matrix Estimation in Stochastic Gradient Descentcited by 37
  8. 2021Optimal and instance-dependent guarantees for Markovian linear stochastic approximationcited by 33
  9. 2019Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLTcited by 30
  10. 2021Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsizecited by 27
  11. 2021Online Bootstrap Inference For Policy Evaluation in Reinforcement Learningcited by 26
  12. 2021On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learningcited by 23
8 more
  1. 2024Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learningcited by 19
  2. 2024Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learningcited by 17
  3. 2024Statistical Inference for Policy Evaluation with Temporal Difference Learningcited by 15
  4. 2025Statistical inference for Linear Stochastic Approximation with Markovian Noisecited by 13
  5. 2025Uncertainty quantification for Markov chain induced martingales with application to temporal difference learningcited by 11
  6. 2025Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descentcited by 10
  7. 2023Statistical Inference with Stochastic Gradient Methods under φ-mixing Datacited by 7
  8. 2024Asymptotics of Stochastic Gradient Descent with Dropout Regularization in Linear Modelscited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Gaussian Approximation for Asynchronous Q-learningcited by 1
  2. 2026When Does Dynamic Preconditioning Preserve the Polyak-Ruppert CLT? A Stabilization Thresholdcited by 1
  3. 2026Statistical Inference on Gradient Flowscited by 1
  4. 2026Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximationcited by 0