A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging
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_ | 1866918036852703232 |
|---|---|
| author | Khodadadian, Sajad Zubeldia, Martin |
| author_facet | Khodadadian, Sajad Zubeldia, Martin |
| contents | Polyak-Ruppert averaging is a widely used technique to achieve the optimal asymptotic variance of stochastic approximation (SA) algorithms, yet its high-probability performance guarantees remain underexplored in general settings. In this paper, we present a general framework for establishing non-asymptotic concentration bounds for the error of averaged SA iterates. Our approach assumes access to individual concentration bounds for the unaveraged iterates and yields a sharp bound on the averaged iterates. We also construct an example, showing the tightness of our result up to constant multiplicative factors. As direct applications, we derive tight concentration bounds for contractive SA algorithms and for algorithms such as temporal difference learning and Q-learning with averaging, obtaining new bounds in settings where traditional analysis is challenging. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_21796 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging Khodadadian, Sajad Zubeldia, Martin Machine Learning Probability Polyak-Ruppert averaging is a widely used technique to achieve the optimal asymptotic variance of stochastic approximation (SA) algorithms, yet its high-probability performance guarantees remain underexplored in general settings. In this paper, we present a general framework for establishing non-asymptotic concentration bounds for the error of averaged SA iterates. Our approach assumes access to individual concentration bounds for the unaveraged iterates and yields a sharp bound on the averaged iterates. We also construct an example, showing the tightness of our result up to constant multiplicative factors. As direct applications, we derive tight concentration bounds for contractive SA algorithms and for algorithms such as temporal difference learning and Q-learning with averaging, obtaining new bounds in settings where traditional analysis is challenging. |
| title | A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging |
| topic | Machine Learning Probability |
| url | https://arxiv.org/abs/2505.21796 |