Research map / Optimization / Nonconvex and smooth optimization
The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize
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.
Analyzes constant-stepsize nonlinear stochastic approximation with Markovian data, proving weak convergence of the joint chain (x_k, theta_k), a bias expansion with a multiplicative Markov-nonlinearity compound term, moment bounds, and a CLT.
Problem
Constant-stepsize stochastic approximation where both the update rule is nonlinear and the data form a Markov chain; prior work treated only one of these structures at a time, leaving weak convergence and the asymptotic bias unresolved.
Approach
Uses smoothness and recurrence of the nonlinear SA update with a fine-grained coupling analysis of the correlation between theta_k and Markov data x_k, establishing weak convergence of the joint process and a bias expansion whose compound term (nonlinearity times Markovian noise) is new.
Key results
- Establishes weak convergence of the joint process (x_k, theta_k) with geometric rate (1-alpha mu)^{k/2} under projection and alpha tau L^2 constraint.
- Bias characterization E[theta_inf]-theta* = alpha(b_m+b_n+b_c)+O((alpha tau)^{3/2}), with b_c a new multiplicative Markov-nonlinearity compound term.
- RR extrapolation reduces squared error bias to O((alpha tau)^3) from order alpha^2 in tail-averaged iterates.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| apply Polyak-Ruppert tail averaging | constant-stepsize nonlinear Markovian SA · tail-averaged iterates | variance: \mathcal{O}\Big(\frac{\tau_\alpha}{k-k_0}\Big) | Helped |
| apply Polyak-Ruppert tail averaging | constant-stepsize nonlinear Markovian SA · tail-averaged iterates | asymptotic bias: \alpha^2 \|b\|^2 | No clear effect |
| apply Richardson-Romberg extrapolation using stepsizes α and 2α | constant-stepsize nonlinear Markovian SA · RR-extrapolated iterates | squared bias: \mathcal{O}\Big((\alpha\tau_\alpha)^{3}\Big) | Helped |
Surprising findings
- The compound term b_c, arising from interaction of Markovian noise and nonlinearity, is absent from prior nonlinear i.i.d. and linear Markovian SA analyses.
- Polyak-Ruppert averaging reduces variance but cannot remove the order-alpha bias.
Limitations
- Requires a projection step or a noise minorization assumption for the weak convergence result.
- Relies on uniform ergodicity of the Markov chain.
- Dimension dependence of results is not refined.
Experimental setup
Metrics: asymptotic bias mean squared error Wasserstein-2 distance
Builds on: linear stochastic approximation with Markovian noise nonlinear SGD with i.i.d. data Richardson-Romberg extrapolation Polyak-Ruppert averaging
Closest papers by meaning
- Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise (NeurIPS 2024 · similarity 0.90)
- How Accurately Can a Gaussian Approximate Stochastic Approximation Iterates? (NeurIPS 2026 · similarity 0.88)
- Effectiveness of Constant Stepsize in Markovian LSA and Statistical Inference (AAAI 2024 · similarity 0.88)
- Statistical inference for Linear Stochastic Approximation with Markovian Noise (NeurIPS 2025 · similarity 0.87)
- Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift (NeurIPS 2026 · similarity 0.87)
- Convergence Rate in a Nonlinear Two-Time-Scale Stochastic Approximation with State (Time)-Dependence (AAAI 2025 · 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.