Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916453191516160 |
|---|---|
| author | Allmeier, Sebastian Gast, Nicolas |
| author_facet | Allmeier, Sebastian Gast, Nicolas |
| contents | 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 $\mathbb{E}[\barθ_n] \approx θ^*+Vα+ O(α^2)$, where $\barθ_n=(1/n)\sum_{k=1}^nθ_k$ is the Polyak-Ruppert average. We also show that $\barθ_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)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_14285 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise Allmeier, Sebastian Gast, Nicolas Machine Learning Optimization and Control 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 $\mathbb{E}[\barθ_n] \approx θ^*+Vα+ O(α^2)$, where $\barθ_n=(1/n)\sum_{k=1}^nθ_k$ is the Polyak-Ruppert average. We also show that $\barθ_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)$. |
| title | Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2405.14285 |