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

1. Problem Formulation

The paper addresses the Stochastic Approximation (SA) problem, which seeks to find the root $x^*$ of an operator $F: \mathbb{R}^d \to \mathbb{R}^d$ given noisy observations. The standard iterative update is:
$$x_{k+1} = x_k - \beta_k (F(x_k) + \eta_k)$$
where $\beta_k$ is the stepsize and $\eta_k$ is the noise sequence.

Key Constraints & Assumptions:

• Operator: $F(\cdot)$ is assumed to be $\mu$-strongly monotone and $L$-Lipschitz continuous. This ensures a unique root $x^*$ and covers applications like Strongly Convex Optimization (where $F = \nabla g$) and Gradient Play in Strongly Monotone Games.
• Stepsize: A decaying stepsize of the form $\beta_k = \frac{\beta}{k + K_0}$ is used.
• The Gap: Classical SA theory assumes martingale difference noise with bounded second moments (light-tailed), yielding a convergence rate of $O(1/k)$ for the mean squared error (MSE). However, many real-world systems (finance, queueing, network traffic) exhibit:
  1. Heavy-tailed noise: Infinite variance (second moment) but finite $p$-th moments for $p < 2$.
  2. Long-Range Dependent (LRD) noise: Persistent temporal correlations where autocovariance decays slowly (non-summable).

The paper aims to establish finite-time convergence bounds for SA under these non-classical noise models, where traditional analysis fails.

---

2. Methodology

The core innovation of the paper is a noise-averaging proof technique that avoids modifying the algorithm itself. Instead of analyzing the raw iteration directly, the authors introduce auxiliary constructs to "regularize" the noise.

Key Technical Steps:

1. Fixed-Point Reformulation: The root-finding problem is transformed into finding a fixed point of a contractive mapping $G(x) = x - \zeta F(x)$, where $\zeta = \mu/L^2$.
2. Auxiliary Iterates and Averaged Noise:
   • The authors define an averaged noise sequence $U_k$ recursively: $U_{k+1} = (1-\tilde{\beta}_k)U_k + \tilde{\beta}_k \tilde{\eta}_k$, with $U_0=0$.
   • They define a modified iterate $z_k = x_k - U_k$.
   • This transformation rewrites the original dynamics such that the randomness enters the recursion for $z_k$ only through the term $\Delta_k = G(x_k) - G(z_k)$, which is bounded by $\|U_k\|$.
3. Regularization Effect:
   • Even if the original noise $\eta_k$ has infinite variance (heavy-tailed) or strong correlations (LRD), the averaged noise $U_k$ exhibits significantly better moment properties due to the smoothing effect of the averaging process.
   • The analysis then bounds the error $\|x_k - x^*\|$ by decomposing it into the error of the auxiliary sequence $\|z_k - x^*\|$ and the averaged noise $\|U_k\|$.

Why Traditional Analysis Fails:

• Heavy-tailed: Standard proofs rely on bounding $E[\|\eta_k\|^2]$, which is infinite.
• LRD: Standard proofs rely on the cross-term $E[\langle x_k - x^*, \eta_k \rangle]$ vanishing (martingale property). In LRD, this term is non-zero due to temporal correlation.
• Solution: The averaging technique decouples the noise from the state in a way that allows bounding the moments of $U_k$ even when the raw noise moments are unbounded or correlated.

---

3. Key Contributions and Results

The paper provides the first finite-time moment bounds for SA under both heavy-tailed and LRD noise models.

A. Heavy-Tailed Noise

• Assumption: Noise has finite $p$-th moment ($1 < p < 2$) but infinite second moment (e.g., Pareto, $\alpha$-stable distributions).
• Result: The $p$-th moment of the error decays as:
  $$E[\|x_k - x^*\|^p] \leq \frac{C}{(k + K_0)^{p-1}}$$
• Implication: The convergence rate is $O(k^{-(p-1)})$. As the tail becomes heavier (smaller $p$), the rate slows down. By Jensen's inequality, the first moment decays as $O(k^{-(p-1)/p})$.

B. Long-Range Dependent (LRD) Noise

• Assumption: Noise is a zero-mean stationary process with autocovariance decaying as $|\gamma(h)| \leq \sigma^2 (1+h)^{-\delta}$ for $\delta \in (0, 1)$. Examples include Fractional Gaussian Noise (fGn) and FARIMA processes.
• Result: The Mean Squared Error (MSE) decays as:
  $$E[\|x_k - x^*\|^2] \leq \frac{C}{(k + K_0)^\delta}$$
• Implication: The convergence rate is $O(k^{-\delta})$. Stronger temporal dependence (smaller $\delta$) leads to slower convergence because past noise terms influence the iterates for longer.

C. Applications

The framework is applied to two specific domains:

1. Stochastic Gradient Descent (SGD): For strongly convex optimization. The paper derives the first finite-time guarantees for SGD under LRD noise.
2. Gradient Play: For finding Nash Equilibria in strongly monotone games. The paper provides guarantees for gradient play under both heavy-tailed and LRD noise.

---

4. Numerical Validation

The authors conducted simulations to corroborate theoretical findings:

• SGD with Heavy Tails: Using Pareto noise with varying tail indices $\alpha$. Results showed that smaller $\alpha$ (heavier tails) resulted in slower convergence and larger error spikes in single runs, with the average error aligning closer to the upper quantiles of the distribution.
• SGD with LRD: Using Fractional Gaussian Noise with varying Hurst parameters $H$. Results confirmed that higher $H$ (stronger persistence) led to slower convergence rates, matching the theoretical $O(k^{-\delta})$ scaling.
• Gradient Play: Simulations in a wireless power control game with $\alpha$-stable and FARIMA noise confirmed that the theoretical degradation rates hold in multi-agent settings.

---

5. Significance and Impact

• Bridging Theory and Practice: Classical SA theory is often too restrictive for real-world data (finance, network traffic) which frequently exhibits heavy tails and long memory. This work extends the theoretical foundation to these practical regimes.
• No Algorithmic Modification: Unlike other approaches that require algorithmic changes (e.g., gradient clipping or normalization) to handle heavy tails, this analysis proves convergence guarantees for the standard, unmodified SA iteration.
• Quantitative Insights: The results provide explicit convergence rates that quantify exactly how the "heaviness" of the tail ($p$) or the "strength" of the dependence ($\delta$) degrades performance.
• General Framework: The noise-averaging technique is a novel proof tool that could be extended to other non-classical noise settings or non-expansive operators in future work.

In summary, this paper rigorously demonstrates that while heavy-tailed and long-range dependent noise degrade the convergence speed of stochastic approximation, the standard algorithm remains stable and convergent, with rates explicitly determined by the statistical properties of the noise.