Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise
<|reference_start|>Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise: We study stochastic approximation algorithms with Markovian noise and constant step-size $\alpha$. We develop a method based on infinitesimal generator comparisons to study the bias of the algorithm, which is the expected difference between $\theta_n$ -- the value at iteration $n$ -- and $\theta^*$ -- the unique equilibrium of the corresponding ODE. We show that, under some smoothness conditions, this bias is of order $O(\alpha)$. Furthermore, we show that the time-averaged bias is equal to $\alpha V + O(\alpha^2)$, where $V$ is a constant characterized by a Lyapunov equation, showing that $\esp{\bar{\theta}_n} \approx \theta^*+V\alpha + O(\alpha^2)$, where $\bar{\theta}_n=(1/n)\sum_{k=1}^n\theta_k$ is the Polyak-Ruppert average. We also show that $\bar{\theta}_n$ converges with high probability around $\theta^*+\alpha V$. We illustrate how to combine this with Richardson-Romberg extrapolation to derive an iterative scheme with a bias of order $O(\alpha^2)$.<|reference_end|>
@article{allmeier2024computing,
    title={Computing the Bias of Constant-step Stochastic Approximation with
  Markovian Noise},
    author={Sebastian Allmeier, Nicolas Gast},
    journal={arXiv preprint arXiv:2405.14285},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.14285},
    primaryClass={stat.ML cs.LG math.OC}
}