Research map / Probabilistic and scientific modeling / Variational and generative sampling
Effectiveness of Constant Stepsize in Markovian LSA and Statistical Inference
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.
Studies statistical inference with constant-stepsize Markovian linear stochastic approximation, proving a CLT for averaged iterates and combining batch-mean CIs with Richardson-Romberg extrapolation to reduce bias.
Problem
Constant-stepsize SA iterates have asymptotic bias under Markovian data and lack almost-sure convergence, so statistical inference with them has been overlooked; the paper asks whether constant stepsizes can be effective for CI construction.
Approach
Establish a CLT for Polyak-Ruppert averaged constant-stepsize Markovian LSA iterates, build batch-mean CIs, and apply Richardson-Romberg extrapolation across several constant stepsizes to reduce bias; also characterize stepsize selection and settings where bias vanishes.
Key results
- With RR extrapolation on Markovian LSA (10 states, d=5, length 10^5), 95% CI coverage reached a median of about 91% vs 0% for stepsize 0.2 and 88% for 0.02.
- At trajectory length 10^6, RR with constant stepsizes achieved 95.2% coverage with l2 error 1.0e-5 and CI width 0.00134, versus 93.4% coverage for bootstrapping with l2 error 2.0e-3 and CI width 0.00411.
- Constant stepsize iterates were robust to batch number, whereas diminishing stepsize (0.2/sqrt(k)) coverage dropped sharply as batch count grew (e.g., to 30.4% at 1000 batches).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add RR extrapolation to constant-stepsize LSA | Markovian LSA · Markovian LSA, 100 problems | coverage probability, 50th percentile: 90 -> 94 | Helped |
| Add RR extrapolation to constant-stepsize LSA | Markovian LSA · Markovian LSA, 100 problems | ℓ2 error (×10^-3), 50th percentile: 1.59 -> 1.32 | Helped |
| Use constant stepsize 0.02 instead of 0.2 | Markovian LSA · Markovian LSA, 100 problems | coverage probability, 50th percentile: 11 -> 90 | Helped |
| Use constant stepsize with RR instead of bootstrapping | Markovian LSA inference · Markovian LSA | coverage probability: 93.4% -> 95.2% | Helped |
| Use constant stepsize with RR instead of bootstrapping | Markovian LSA inference · Markovian LSA | CI width: 0.00411 -> 0.00134 | Helped |
| Use RR extrapolation instead of constant stepsize 0.02 | Markovian LSA · Markovian LSA, trajectory length 10^6 | coverage probability: 80.2 -> 95.2 | Helped |
| Use RR extrapolation instead of constant stepsize 0.02 | Nonlinear SA logistic regression · Logistic regression with Markovian data, trajectory length 10^6 | coverage probability: 8.0 -> 95.0 | Helped |
Surprising findings
- Increasing the number of RR stepsizes does not always reduce l2 error when stepsizes are closely spaced, because large extrapolation coefficients inflate variance.
- Constant stepsize 0.2 yields 0% coverage at long trajectories because its iterates converge to a biased limit.
Limitations
- The confidence interval construction is stated to be non-consistent and lacks full theoretical validation.
- RR coefficients from Vandermonde inversion can be ill-conditioned, increasing variance, especially for equidistant stepsizes with many stepsizes.
- Current procedure is not anytime or fully online because the variance estimator depends on a fixed batch structure.
Experimental setup
Datasets: synthetic Markov chain LSA problems (N=10 states, d=5) synthetic logistic regression with AR(1) Gaussian data
Benchmarks: synthetic Markovian LSA problems (d=5, 10 states) logistic regression with unbounded Markovian data
Metrics: l2 error of point estimate CI width coverage probability
Baselines: diminishing stepsize 0.2/sqrt(k) diminishing stepsize 0.02/sqrt(k) bootstrapping
Builds on: Polyak-Ruppert averaging batch-mean covariance estimation Richardson-Romberg extrapolation Markovian stochastic approximation bias analysis
Closest papers by meaning
- Statistical inference for Linear Stochastic Approximation with Markovian Noise (NeurIPS 2025 · similarity 0.89)
- The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize (NeurIPS 2024 · similarity 0.88)
- Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise (NeurIPS 2024 · similarity 0.86)
- The Polynomial Stein Discrepancy for Assessing Moment Convergence (ICML 2025 · similarity 0.85)
- Least squares variational inference (NeurIPS 2025 · similarity 0.84)
- AutoStep: Locally adaptive involutive MCMC (ICML 2025 · similarity 0.84)
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.