Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysis

Siddharth Chandak, Anuj Kumar Yadav, Ayfer Özgür, Nicholas Bambos · 2026

Read Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysis by Siddharth Chandak, Anuj Kumar Yadav, Ayfer Özgür, Nicholas Bambos (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-19648.txt.

Introduction

Chandak and co-authors analyse stochastic approximation under heavy-tailed and long-range dependent noise. The method is a core iterative tool in reinforcement learning and optimization. Classic theory assumes tame noise with bounded variance. Finance and communications often break that assumption. The team seeks the root of a strongly monotone operator under the rougher noise. They prove the first finite-time moment bounds in both settings. Rates show how heavy tails and long memory slow convergence. Tests on gradient descent support the bounds.

Catalog record

CREATORSiddharth Chandak, Anuj Kumar Yadav, Ayfer Özgür, Nicholas Bambos
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66788
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.19648

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysis Siddharth Chandak, Anuj Kumar Yadav, Ayfer Özgür, Nicholas Bambos Abstract 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. I Introduction Stochastic Approximation (SA) is a class of iterative schemes to find the zeroes of an operator given its noisy realizations [ 31 ] . A wide range of practical algorithms across different fields can be modeled within the SA framework. These include optimization algorithms such as stochastic gradient descent (SGD) and mirror descent [ 7 ] , reinforcement learning algorithms such as Q-learning, policy gradient, and TD(0) [ 37 ] , as well as algorithms arising in communications and stochastic control [ 5 ] . Noise plays a central role in stochastic approximation, both in enabling many algorithms to be modeled within this framework and in shaping their behavior. The classical SA formulation assumes martingale difference noise with bounded moments [ 31 , 24 ] , which is well suited to statistical estimation and stochastic optimization problems arising from independent sampling or unbiased gradient estimates. More recently, reinforcement learning applications have motivated the study of Markovian noise models, as the learning dynamics are governed by Markov decision processes [ 4 , 5 ] . Reflecting this emphasis, much of the existing SA theory has been developed under these classical noise models. However, in many real-world applications, these noise models can be overly restrictive. A first limitation is the assumption of bounded second moments, which excludes noise with heavy tails and occasional large-magnitude fluctuations. To address this, it is natural to consider heavy-tailed noise models, in which the noise only admits finite p -th moments for some p<2 [ 26 ] . Such models capture settings where rare but extreme events play a significant role, as encountered in queueing systems [ 41 ] , and finance [ 12 ] . A second limitation is the assumption of weak or no temporal dependence, which fails to capture the persistent correlations observed in many time series. This motivates the study of SA under long-range dependent (LRD) noise processes, where correlations decay slowly over time and can substantially affect the dynamics of the iterates [ 29 ] . Such behavior arises naturally in applications including network traffic [ 25 ] , climate systems [ 32 ] , and economic time series [ 8 ] . Motivated by these applications and by the limitations of existing theory, we study stochastic approximation under heavy-tailed and long-range dependent noise models. I-A Our Contributions We establish the first finite-time convergence bounds for SA under both heavy-tailed and LRD noise models. Specifically, we study the problem of finding the root of a strongly monotone operator from noisy observations, and derive bounds on moments of the error \|x_{k}-x^{*}\| , where x^{*} is the unique zero of the operator. Under martingale difference and Markovian noise, the mean square error at iteration k decays as \mathcal{O}(k^{-1}) [ 10 ] . In contrast, under the noise models considered in this work, the convergence rates degrade as follows: • Heavy-tailed noise: When the noise admits only a finite p^{\text{th}} moment for some p\in(1,2) , we establish bounds on the p^{\text{th}} -moment of the error, showing a decay rate of \mathcal{O}(k^{-(p-1)}) . This setting includes, for example, centered Pareto distributions with tail index \alpha\in(1,2) and symmetric \alpha -stable noise, with p=\alpha in both cases. • LRD noise: When the autocovariance of the noise process decays as \mathcal{O}(h^{-\delta}) for \delta\in(0,1) , we obtain a mean square error bound of order \mathcal{O}(k^{-\delta}) . This setting covers, for instance, fractional Gaussian noise (fGn) with Hurst index H\in(1/2,1) where \delta=2-2H and FARIMA (0,c,0) processes where \delta=1-2c . These results admit a natural interpretation: heavier-tailed noise (smaller p ) induces larger fluctuations, while stronger temporal dependence (smaller \delta ) slows averaging, both leading to slower convergence. We apply our general framework to two important classes of algorithms: stochastic gradient descent (SGD) for strongly convex optimization and gradient play in strongly monotone games. As a consequence of our results in Theorems 2 and 3 , we obtain the first finite-time guarantees for SGD under LRD noise, and for gradient play under both heavy-tailed and LRD noise. We also provide numerical experiments illustrating the impact of heavy tails and temporal dependence on convergence. Our proof technique relies on introducing averaged noise and auxiliary iterates, transforming the iteration so that randomness appears only through an averaged term. This averaging regularizes the noise, yielding improved moment bounds even under heavy-tailed or long-range dependent (LRD) perturbations. We emphasize that analyzing this averaged noise sequence is just a proof technique and not a modification to the iteration. I-B Related Work Classical analyses of SA primarily focused on asymptotic convergence under martingale difference or Markovian noise (see [ 5 , 24 ] for textbook references). Motivated by applications in optimization and reinforcement learning, recent work has focused on finite-time guarantees. However, these non-asymptotic results are largely developed under the same classical noise assumptions (e.g., see [ 10 , 43 ] and references therein). To the best of our knowledge, the only existing work on general SA under heavy-tailed or LRD noise focuses on asymptotic convergence guarantees [ 1 ] . In particular, they show almost sure convergence for LRD noise, which we complement by providing mean square error bounds, and convergence in the p^{\text{th}} -moment for heavy-tailed noise, which we extend by establishing explicit finite-time bounds. Despite this limited literature for general stochastic approximation, stochastic gradient descent (SGD) under heavy-tailed noise has been widely studied. There is a substantial body of work that analyzes vanilla SGD under heavy-tailed gradient noise [ 35 , 30 , 15 , 38 , 44 ] . While our framework recovers the same rates in the strongly convex setting, these works exploit properties specific to gradients and therefore do not extend to the general strongly monotone operators considered in this work. Other works propose modifications to the algorithm such as norm-based clipping [ 18 , 39 ] , and gradient normalization [ 36 ] . I-C Outline and Notation This paper is structured as follows. Section II introduces the general SA framework. Section III presents the heavy-tailed and long-range dependent noise models and develops the corresponding bounds. Section IV provides a proof sketch of the main results. Section V presents SGD and gradient play as applications, together with numerical simulations. Section VI concludes with a discussion of future directions. Throughout this work, \|\cdot\| denotes the Euclidean norm, and \langle x_{1},x_{2}\rangle denotes

Read the complete text