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

• URL: http://arxiv.org/abs/2603.19648v1
• Date: Fri, 20 Mar 2026 05:17:32 GMT
• Title: Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysis
• Abstract summary: We study approximation (SA) for finding the root of a strongly monotone operator under non-classical noise models.<n>Our analysis employs a noise-averaging argument that regularizes the impact of noise without modifying the iteration.
• Score: 5.319609927556882
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Stability and Generalization of Nonconvex Optimization with Heavy-Tailed Noise [24.27538723361077]
  We develop a general framework for establishing bounds under heavy-tailed noise.<n>We provide the stability and generalization analysis for several popular algorithms under heavy-tailed noise.
  arXiv  Detail & Related papers  (2026-01-27T15:50:57Z)
• Algorithmic Stability of Stochastic Gradient Descent with Momentum under Heavy-Tailed Noise [20.922456964393213]
  We establish generalization bounds for SGD with momentum (SGDm) under heavy-tailed noise.<n>For quadratic loss functions, we show that SGDm admits a worse generalization bound in the presence of momentum and heavy tails.<n>We develop a uniform-in-time discretization error bound, which to our knowledge, is the first result of its kind for SDEs with degenerate noise.
  arXiv  Detail & Related papers  (2025-02-02T19:25:48Z)
• Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise [20.474661995490365]
  This work investigates approximations with merely nonexpansive operators.<n>In particular, we study nonexpansive approximations with Markovian noise.<n>As an application, we prove, for the first time, that the classical average reward temporal difference learning converges to a sample path dependent fixed point.
  arXiv  Detail & Related papers  (2024-09-29T04:16:24Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  We study the non-asymptotic performance of approximation schemes with delayed updates under Markovian sampling. Our theoretical findings shed light on the finite-time effects of delays for a broad class of algorithms.
  arXiv  Detail & Related papers  (2024-02-19T03:08:02Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  We consider clipped optimization problems with heavy-tailed noise with structured density. We show that it is possible to get faster rates of convergence than $mathcalO(K-(alpha - 1)/alpha)$, when the gradients have finite moments of order. We prove that the resulting estimates have negligible bias and controllable variance.
  arXiv  Detail & Related papers  (2023-11-07T17:39:17Z)
• Correlated Noise in Epoch-Based Stochastic Gradient Descent: Implications for Weight Variances [0.0]
  gradient descent (SGD) has become a cornerstone of neural network optimization. We investigate the effects of epoch-based noise correlations on the stationary distribution of discrete-time SGD with momentum.
  arXiv  Detail & Related papers  (2023-06-08T15:45:57Z)
• Doubly Stochastic Models: Learning with Unbiased Label Noises and Inference Stability [85.1044381834036]
  We investigate the implicit regularization effects of label noises under mini-batch sampling settings of gradient descent. We find such implicit regularizer would favor some convergence points that could stabilize model outputs against perturbation of parameters. Our work doesn't assume SGD as an Ornstein-Uhlenbeck like process and achieve a more general result with convergence of approximation proved.
  arXiv  Detail & Related papers  (2023-04-01T14:09:07Z)
• Tradeoffs between convergence rate and noise amplification for momentum-based accelerated optimization algorithms [8.669461942767098]
  We study momentum-based first-order optimization algorithms in which the iterations are subject to an additive white noise. For strongly convex quadratic problems, we use the steady-state variance of the error in the optimization variable to quantify noise amplification. We introduce two parameterized families of algorithms that strike a balance between noise amplification and settling time.
  arXiv  Detail & Related papers  (2022-09-24T04:26:30Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  We prove the first high-probability results with logarithmic dependence on the confidence level for methods for solving monotone and structured non-monotone VIPs. Our results match the best-known ones in the light-tails case and are novel for structured non-monotone problems. In addition, we numerically validate that the gradient noise of many practical formulations is heavy-tailed and show that clipping improves the performance of SEG/SGDA.
  arXiv  Detail & Related papers  (2022-06-02T15:21:55Z)
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD [73.55632827932101]
  We optimize the information-theoretical generalization bound by manipulating the noise structure in SGLD. We prove that with constraint to guarantee low empirical risk, the optimal noise covariance is the square root of the expected gradient covariance.
  arXiv  Detail & Related papers  (2021-10-26T15:02:27Z)
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance [76.54300276636982]
  Noise in gradient descent provides a crucial implicit regularization effect for training over parameterized models. We show that parameter-dependent noise -- induced by mini-batches or label perturbation -- is far more effective than Gaussian noise. Our analysis reveals that parameter-dependent noise introduces a bias towards local minima with smaller noise variance, whereas spherical Gaussian noise does not.
  arXiv  Detail & Related papers  (2020-06-15T18:31:02Z)
• Stochastic Approximation with Markov Noise: Analysis and applications in reinforcement learning [0.0]
  We present for the first time an convergence analysis of two time-scale approximation driven by "controlled" Markov noise. We analyze the behavior of our framework by relating it to limiting differential inclusions in both time scales. We obtain the first informative error bounds on function approximation for the policy evaluation algorithm.
  arXiv  Detail & Related papers  (2020-04-08T03:59:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.