Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise

Code

• github.com/ngast/paper_bias_stochastic_approximation2024
  OfficialIn papernone★ 0

Abstract

We study stochastic approximation algorithms with Markovian noise and constant step-size . We develop a method based on infinitesimal generator comparisons to study the bias of the algorithm, which is the expected difference between _n -- the value at iteration n -- and ^* -- the unique equilibrium of the corresponding ODE. We show that, under some smoothness conditions, this bias is of order O(). Furthermore, we show that the time-averaged bias is equal to V + O(^2), where V is a constant characterized by a Lyapunov equation, showing that E[_n] ^*+V + O(^2), where _n=(1/n)_k=1^n_k is the Polyak-Ruppert average. We also show that _n converges with high probability around ^*+ V. We illustrate how to combine this with Richardson-Romberg extrapolation to derive an iterative scheme with a bias of order O(^2).

Reproductions