Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation

Basic Information

• Paper ID: 2510.12375
• Title: Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation
• Authors: Bogdan Butyrin, Eric Moulines, Alexey Naumov, Sergey Samsonov, Qi-Man Shao, Zhuo-Song Zhang
• Classification: stat.ML cs.LG math.OC math.PR math.ST stat.TH
• Publication Date: October 15, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.12375

Abstract

This paper improves the Berry-Esseen bounds for multivariate Gaussian approximation of Polyak-Ruppert averaged iterates in linear stochastic approximation (LSA) algorithms. The study establishes a convergence rate of order $n^{-1/3}$ in the convex distance sense for Gaussian approximation with the covariance matrix predicted by the Polyak-Juditsky central limit theorem, where $n$ denotes the number of samples used by the algorithm. Additionally, the paper proves the non-asymptotic validity of the multiplier bootstrap procedure for approximating the rescaled error distribution of the averaged LSA estimator, achieving an approximation rate of order $1/\sqrt{n}$, which significantly improves upon previous results by Samsonov et al. (2024).

Research Background and Motivation

Problem Background

Linear stochastic approximation (LSA) is a fundamental method in statistics and machine learning for approximating the unique solution to the linear system $\bar{A}\theta^* = \bar{b}$, where $\bar{A} \in \mathbb{R}^{d \times d}$ is a non-singular matrix. The algorithm performs iterative updates based on an observed sequence $\{(A(Z_k), b(Z_k))\}_{k \in \mathbb{N}}$.

Core Challenges

1. Distribution Approximation Accuracy: Existing Gaussian approximation results exhibit slow convergence rates, limiting the precision of confidence interval construction in practical applications
2. Covariance Matrix Estimation: The asymptotic covariance matrix $\Sigma_\infty$ is unknown in practice, requiring effective estimation and approximation methods
3. Bootstrap Validity: Traditional bootstrap methods face theoretical and practical challenges in online learning algorithms

Research Motivation

• Improve convergence rate analysis of the central limit theorem in LSA algorithms
• Develop more precise bootstrap confidence interval construction methods
• Provide theoretical support for applications such as temporal difference (TD) learning in reinforcement learning

Core Contributions

1. Improved Moment Bounds: Establishes higher-order moment bounds for $\sqrt{n}(\bar{\theta}_n - \theta^*)$, obtaining for $p \geq 2$: $E^{1/p}[\|\bar{\theta}_n - \theta^*\|^p] \lesssim \frac{\sqrt{p}\sqrt{\text{Tr}\Sigma_\infty}}{\sqrt{n}} + \frac{p^{3/2}}{n^{5/6}}$
2. Improved Berry-Esseen Bounds: Establishes a Gaussian approximation rate of order $n^{-1/3}$ in the convex distance sense, improving upon the previous $n^{-1/4}$ result
3. Non-asymptotic Analysis of Multiplier Bootstrap: Proves the validity of the bootstrap procedure with an approximation rate of $n^{-1/2}$, significantly superior to existing results
4. Technical Innovation: By choosing an appropriate covariance matrix $\Sigma_n$ rather than $\Sigma_\infty$ for approximation, avoids direct Gaussian comparison steps

Methodology Details

Problem Formulation

Consider the LSA iteration: $\theta_k = \theta_{k-1} - \alpha_k(A(Z_k)\theta_{k-1} - b(Z_k)), \quad k \geq 1$$\bar{\theta}_n = n^{-1}\sum_{k=0}^{n-1}\theta_k, \quad n \geq 1$

The objective is to analyze the distribution approximation properties of $\sqrt{n}(\bar{\theta}_n - \theta^*)$.

Core Technical Framework

1. Error Decomposition Technique

Decompose the LSA error into transient and fluctuation terms: $\theta_k - \theta^* = \tilde{\theta}_k^{(tr)} + \tilde{\theta}_k^{(fl)}$ where:

• $\tilde{\theta}_k^{(tr)} = \Gamma_{1:k}(\theta_0 - \theta^*)$ (transient term)
• $\tilde{\theta}_k^{(fl)} = -\sum_{\ell=1}^k \alpha_\ell \Gamma_{\ell+1:k}\varepsilon_\ell$ (fluctuation term)

2. Perturbation Expansion Method

Further decompose the fluctuation term: $\tilde{\theta}_k^{(fl)} = J_k^{(0)} + H_k^{(0)}$ where $J_k^{(0)}$ is the linear dominant term and $H_k^{(0)}$ is the higher-order remainder.

3. Randomized Concentration Inequalities

Apply the Shao-Zhang framework, expressing the statistic as: $\sqrt{n}\Sigma_n^{-1/2}(\bar{\theta}_n - \theta^*) = W + D$ where $W$ is a linear statistic and $D$ is a nonlinear remainder.

Step Size Selection Strategy

Employ polynomial decay step sizes: $\alpha_k = \frac{c_0}{(k + k_0)^\gamma}, \quad \gamma \in (1/2, 1)$

Key finding: The optimal convergence rate is achieved at $\gamma = 2/3$.

Experimental Setup

Theoretical Verification Framework

The paper is primarily theoretical, with results verified through:

1. Assumptions:
   • A1: Independent and identically distributed observations
   • A2: Hurwitz matrix condition and bounded noise
   • A3: Step size conditions
   • A4-A5: Sample size and technical conditions
2. Application Scenarios: Temporal difference (TD) learning algorithm as an important special case

Evaluation Metrics

• Convex Distance: $\rho_{Conv}(\mu, \nu) = \sup_{B \in Conv(\mathbb{R}^d)}|\mu(B) - \nu(B)|$
• Convergence Rate: Approximation accuracy expressed as powers of $n$

Experimental Results

Main Theoretical Results

Theorem 1: Moment Bounds

Under appropriate assumptions, for $p \geq 2$: $E^{1/p}[\|\bar{\theta}_n - \theta^*\|^p] \leq \frac{C_{1,1}\sqrt{p}\sqrt{\text{Tr}\Sigma_n}}{\sqrt{n}} + \Delta^{(fl)}(n,p,\gamma) + \frac{C_{1,5}\|\theta_0 - \theta^*\|}{n}$

Theorem 2: Gaussian Approximation

$\rho_{Conv}(\sqrt{n}(\bar{\theta}_n - \theta^*), \Sigma_n^{1/2}\eta) \leq \frac{C_{2,1}}{\sqrt{n}} + \frac{C_{2,2}}{n^{\gamma/2}} + C_{2,3}\phi_n + \frac{C_{2,4}\|\theta_0 - \theta^*\|}{n}$

Theorem 3: Asymptotic Approximation

$\rho_{Conv}(\sqrt{n}(\bar{\theta}_n - \theta^*), \Sigma_\infty^{1/2}\eta) \leq \frac{C_{2,1}}{\sqrt{n}} + \frac{C_{2,2}}{n^{\gamma/2}} + C_{2,3}\phi_n + \frac{C_{2,4}\|\theta_0 - \theta^*\|}{n} + \frac{C_3}{n^{1-\gamma}}$

Theorem 4: Bootstrap Approximation

With probability $1-1/n$: $\sup_{B \in Conv(\mathbb{R}^d)}|P^b(\sqrt{n}(\bar{\theta}_n^b - \bar{\theta}_n) \in B) - P(\sqrt{n}(\bar{\theta}_n - \theta^*) \in B)| \leq \frac{C_4\|\theta_0 - \theta^*\| + \Delta_{4,1}}{\sqrt{n}} + \frac{\Delta_{4,2}}{n^{\gamma/2}} + \Delta_{4,3}\phi_n + \frac{\Delta_{4,4}}{n}$

Convergence Rate Comparison

Related Work

LSA Theory Development

• Asymptotic Theory: Polyak & Juditsky (1992) established foundational asymptotic normality
• Non-asymptotic Analysis: Durmus et al. (2021, 2025) and others provided finite-sample bounds
• Gaussian Approximation: Anastasiou et al. (2019) employed Stein's method

Bootstrap Methods

• Classical Bootstrap: Efron's (1992) pioneering work
• Multiplier Bootstrap: Fang et al. (2018) for online bootstrap in SGD
• Theoretical Analysis: Chernozhukov et al. (2013, 2017) high-dimensional theory

Technical Tools

• Random Matrix Products: Concentration inequalities by Huang et al. (2021)
• Nonlinear Statistics: Randomized concentration method by Shao & Zhang (2022)

Conclusions and Discussion

Main Conclusions

1. Optimal Convergence Rate: Achieves a Berry-Esseen bound of order $n^{-1/3}$ in the convex distance sense, which is optimal under the LSA setting
2. Bootstrap Improvement: Bootstrap approximation rate reaches $n^{-1/2}$, significantly superior to the existing $n^{-1/4}$ result
3. Technical Breakthrough: By choosing $\Sigma_n$ rather than $\Sigma_\infty$ as the approximating covariance, overcomes technical obstacles

Limitations

1. Independence Assumption: Considers only i.i.d. noise; Markov noise case left for future work
2. Step Size Constraints: Requires specific polynomial decay step size forms
3. Dimension Dependence: Constants contain dimension-dependent terms, potentially large in high dimensions

Future Directions

1. Markov Extension: Generalize results to Markov noise settings
2. Matching Lower Bounds: Establish matching lower bounds in the interval $\gamma \in (1/2, 2/3)$
3. Practical Applications: Verify theoretical predictions in concrete reinforcement learning and optimization problems

In-Depth Evaluation

Strengths

1. Theoretical Depth: Provides the most precise convergence rate analysis in the LSA field with high technical difficulty
2. Methodological Innovation: Cleverly selects approximating covariance matrix, overcoming limitations of existing methods
3. Optimal Results: Multiple results achieve or approach theoretically optimal bounds
4. Proof Techniques: Combines multiple advanced probabilistic tools with clear technical roadmap

Weaknesses

1. Experimental Verification: As a purely theoretical paper, lacks numerical experiments to verify theoretical predictions
2. Practical Applicability: Complex constant dependencies; actual performance in applications requires further investigation
3. Scope of Applicability: Strong assumption conditions; limited applicability to real-world problems

Impact

1. Academic Value: Provides important progress in stochastic approximation theory, expected to be widely cited
2. Application Prospects: Provides theoretical foundation for reinforcement learning, online optimization, and related fields
3. Methodological Contribution: Technical methods may inspire research on other nonlinear statistical problems

Applicable Scenarios

• Policy evaluation in reinforcement learning (TD learning)
• Online convex optimization algorithm analysis
• Statistical inference problems requiring precise confidence intervals
• Theoretical analysis in large-scale machine learning

References

1. Polyak, B. T., & Juditsky, A. B. (1992). Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization.
2. Shao, Q. M., & Zhang, Z. S. (2022). Berry–Esseen bounds for multivariate nonlinear statistics with applications to M-estimators and stochastic gradient descent algorithms. Bernoulli.
3. Fang, Y., Xu, J., & Yang, L. (2018). Online bootstrap confidence intervals for the stochastic gradient descent estimator. Journal of Machine Learning Research.
4. Durmus, A., Moulines, E., Naumov, A., & Samsonov, S. (2025). Finite-time high-probability bounds for Polyak–Ruppert averaged iterates of linear stochastic approximation. Mathematics of Operations Research.