Gaussian Approximation for Two-Timescale Linear Stochastic Approximation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917134919008256 |
|---|---|
| author | Butyrin, Bogdan Rubtsov, Artemy Naumov, Alexey Ulyanov, Vladimir Samsonov, Sergey |
| author_facet | Butyrin, Bogdan Rubtsov, Artemy Naumov, Alexey Ulyanov, Vladimir Samsonov, Sergey |
| contents | In this paper, we establish non-asymptotic bounds for accuracy of normal approximation for linear two-timescale stochastic approximation (TTSA) algorithms driven by martingale difference or Markov noise. Focusing on both the last iterate and Polyak-Ruppert averaging regimes, we derive bounds for normal approximation in terms of the convex distance between probability distributions. Our analysis reveals a non-trivial interaction between the fast and slow timescales: the normal approximation rate for the last iterate improves as the timescale separation increases, while it decreases in the Polyak-Ruppert averaged setting. We also provide the high-order moment bounds for the error of linear TTSA algorithm, which may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_07928 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Gaussian Approximation for Two-Timescale Linear Stochastic Approximation Butyrin, Bogdan Rubtsov, Artemy Naumov, Alexey Ulyanov, Vladimir Samsonov, Sergey Machine Learning Optimization and Control Probability Statistics Theory 60F05, 62L20 In this paper, we establish non-asymptotic bounds for accuracy of normal approximation for linear two-timescale stochastic approximation (TTSA) algorithms driven by martingale difference or Markov noise. Focusing on both the last iterate and Polyak-Ruppert averaging regimes, we derive bounds for normal approximation in terms of the convex distance between probability distributions. Our analysis reveals a non-trivial interaction between the fast and slow timescales: the normal approximation rate for the last iterate improves as the timescale separation increases, while it decreases in the Polyak-Ruppert averaged setting. We also provide the high-order moment bounds for the error of linear TTSA algorithm, which may be of independent interest. |
| title | Gaussian Approximation for Two-Timescale Linear Stochastic Approximation |
| topic | Machine Learning Optimization and Control Probability Statistics Theory 60F05, 62L20 |
| url | https://arxiv.org/abs/2508.07928 |