Research map / Optimization / Nonconvex and smooth optimization
Statistical inference for Linear Stochastic Approximation with Markovian Noise
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives non-asymptotic Berry–Esseen bounds (O(n^{-1/4}) in Kolmogorov distance) for Polyak–Ruppert averaged linear stochastic approximation with Markovian noise, and a non-asymptotic bound (O(n^{-1/10})) for a multiplier subsample block bootstrap confidence procedure, applied to TD learning.
Problem
Quantifying the rate of Gaussian approximation and bootstrap-based confidence interval validity for Polyak–Ruppert averaged LSA iterates driven by Markovian (non-i.i.d.) noise, where prior results lacked Kolmogorov-distance rates.
Approach
Combines a Poisson-equation martingale decomposition for Markov chain linear statistics with a Berry–Esseen bound for martingales to get O(n^{-1/4}) Kolmogorov rates, then shows the overlapping-batch-means style multiplier block bootstrap for LSA is non-asymptotically valid by reducing iterate block variance to noise block variance.
Key results
- Berry-Esseen bound of order O(n^{-1/4}) (up to logs) in Kolmogorov distance for projected PR-averaged LSA iterates under Markovian noise.
- Multiplier subsample bootstrap coverage approximation rate O(n^{-1/10}) (up to logs) with block size n^{4/5} and step size exponent 3/5.
- Recovers O(n^{-1/8}) rate (up to logs) for overlapping batch means estimation of the asymptotic variance.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply the proposed Berry–Esseen analysis to Polyak–Ruppert averaged LSA under Markovian noise | Linear stochastic approximation · Linear stochastic approximation with Markovian noise | Kolmogorov distance: \mathcal{O}(n^{-1/4}) vs. \mathcal{O}(n^{-1/12}) | Helped |
| Use the multiplier subsample bootstrap for Markovian-noise LSA | Linear stochastic approximation · Linear stochastic approximation with Markovian noise | Bootstrap coverage approximation error: \mathcal{O}(n^{-1/10}) | Helped |
| Use the overlapping batch means estimator for asymptotic variance | Linear stochastic approximation · Linear stochastic approximation with Markovian noise | Asymptotic variance estimation error: \mathcal{O}(n^{-1/8}) | Helped |
| Apply the proposed normal-approximation analysis to TD learning | TD learning · TD learning with Markovian noise | Kolmogorov distance: \mathcal{O}(n^{-1/4}) | Helped |
Limitations
- Analysis restricted to one-dimensional projections; multivariate version left open.
- Requires knowing n in advance to set k0; step-size choice trades off CLT rate against bootstrap/variance rate.
- Bootstrap uses non-subsampled blocks and the Gaussian comparison relies on limiting variance, leaving open whether the alternative sigma_n approximation works for dependent data.
Experimental setup
Metrics: Kolmogorov distance coverage approximation rate
Baselines: TD learning Berry-Esseen bound (log n / n^{1/4} convex distance) Wasserstein LSA rate (sqrt(log n)/n^{1/6}) multiplier bootstrap for i.i.d. SA (O(n^{-1/2}) coverage)
Builds on: Polyak-Ruppert averaging multiplier subsample bootstrap overlapping batch means TD learning
Closest papers by meaning
- Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning (NeurIPS 2024 · similarity 0.90)
- Effectiveness of Constant Stepsize in Markovian LSA and Statistical Inference (AAAI 2024 · similarity 0.89)
- A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging (NeurIPS 2025 · similarity 0.88)
- How Accurately Can a Gaussian Approximate Stochastic Approximation Iterates? (NeurIPS 2026 · similarity 0.88)
- The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize (NeurIPS 2024 · similarity 0.87)
- Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.