Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysis
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918399046582272 |
|---|---|
| author | Chandak, Siddharth Yadav, Anuj Ozgur, Ayfer Bambos, Nicholas |
| author_facet | Chandak, Siddharth Yadav, Anuj Ozgur, Ayfer Bambos, Nicholas |
| contents | Stochastic approximation (SA) is a fundamental iterative framework with broad applications in reinforcement learning and optimization. Classical analyses typically rely on martingale difference or Markov noise with bounded second moments, but many practical settings, including finance and communications, frequently encounter heavy-tailed and long-range dependent (LRD) noise. In this work, we study SA for finding the root of a strongly monotone operator under these non-classical noise models. We establish the first finite-time moment bounds in both settings, providing explicit convergence rates that quantify the impact of heavy tails and temporal dependence. Our analysis employs a noise-averaging argument that regularizes the impact of noise without modifying the iteration. Finally, we apply our general framework to stochastic gradient descent (SGD) and gradient play, and corroborate our finite-time analysis through numerical experiments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_19648 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysis Chandak, Siddharth Yadav, Anuj Ozgur, Ayfer Bambos, Nicholas Machine Learning Systems and Control Optimization and Control Stochastic approximation (SA) is a fundamental iterative framework with broad applications in reinforcement learning and optimization. Classical analyses typically rely on martingale difference or Markov noise with bounded second moments, but many practical settings, including finance and communications, frequently encounter heavy-tailed and long-range dependent (LRD) noise. In this work, we study SA for finding the root of a strongly monotone operator under these non-classical noise models. We establish the first finite-time moment bounds in both settings, providing explicit convergence rates that quantify the impact of heavy tails and temporal dependence. Our analysis employs a noise-averaging argument that regularizes the impact of noise without modifying the iteration. Finally, we apply our general framework to stochastic gradient descent (SGD) and gradient play, and corroborate our finite-time analysis through numerical experiments. |
| title | Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysis |
| topic | Machine Learning Systems and Control Optimization and Control |
| url | https://arxiv.org/abs/2603.19648 |