Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise

• URL: http://arxiv.org/abs/2605.20999v1
• Date: Wed, 20 May 2026 10:38:08 GMT
• Title: Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise
• Abstract summary: We establish maximal concentration bounds for the iterates generated by approximation algorithms with general step sizes.<n>When the Martingale-difference noise is bounded, we show that the tail of the error can be sub-Gaussian.<n>We show that if the random operator is almost surely non-expansive, then the error tail is at most three times heavier than the noise tail.
• Score: 6.780086370528622
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We establish maximal concentration bounds for the iterates generated by stochastic approximation algorithms with general step sizes, where the noise has a finite-state Markovian component plus a Martingale-difference component. When the Martingale-difference noise is bounded, we show that the tail of the error can be sub-Gaussian, sub-Weibull, or something lighter than any Pareto but heavier than any Weibull, depending on the step size sequence and on whether the random operator is almost surely contractive, almost surely non-expansive, or expansive with positive probability. Our analysis relies on a novel Lyapunov function involving the moment-generating function of the solution to a Poisson equation, together with an auxiliary projected algorithm. We complement the upper bounds with worst-case examples showing that qualitatively sharper bounds are impossible. We further study the case of unbounded Martingale-difference noise when the average operator is contractive, and the step sizes are of order $1/k$. In this setting, we show that if the random operator is almost surely non-expansive, then the error tail is at most three times heavier than the noise tail, whereas if the random operator is expansive with positive probability, then the error may have substantially heavier tails. These results are obtained through a novel black-box truncation argument that reduces the unbounded-noise setting to the bounded-noise case.

Related papers

• Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approach [0.0]
  We establish mean-square and concentration bounds for Moreau approximation (SA) with arbitrary norm contractive mappings.<n>These settings arise in reinforcement learning, where operators are often contractive in the $ell_infty$ norm.<n>Our approach yields the first sub-Gaussian tailed maximal concentration bound for SA under multiplicative noise.
  arXiv  Detail & Related papers  (2026-07-20T06:27:22Z)
• Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization [12.903796669387809]
  We study high-probability regret bounds for online convex optimization (OCO) with strongly convex losses.<n>We establish three results that resolve open questions at the intersection of noise adaptivity, feedback structure, and constraint satisfaction.
  arXiv  Detail & Related papers  (2026-06-06T07:40:55Z)
• High-accuracy log-concave sampling with stochastic queries [70.90863485771405]
  We show that high-accuracy guarantees for log-concave sampling are achievable using iteration gradients with subexponential tails.<n>Our framework also provides similar high accuracy guarantees under zeroth order (value) queries.
  arXiv  Detail & Related papers  (2026-02-15T23:19:07Z)
• Finite-Sample Wasserstein Error Bounds and Concentration Inequalities for Nonlinear Stochastic Approximation [6.800624963330628]
  We derive non-asymptotic error bounds for nonlinear approximation algorithms in the Wasserstein-$p$ distance.<n>We show that the normalized last iterates converge to a Gaussian distribution in the $p$-Wasserstein distance at a rate of order $_n1/6$, where $_n$ is the step size.<n>These distributional guarantees imply high-probability concentration inequalities that improve upon those derived from moment bounds and Markovs inequality.
  arXiv  Detail & Related papers  (2026-02-02T18:41:06Z)
• Towards Sharp Minimax Risk Bounds for Operator Learning [8.781886844319231]
  We prove information-theoretic lower bounds together with matching or near-matching upper bounds for uniformly bounded Lipschitz operators.<n>A key implication is a curse of sample complexity which shows that the minimax risk for generic Lipschitz operators cannot decay at any algebraic rate in the sample size.
  arXiv  Detail & Related papers  (2025-12-19T17:07:43Z)
• 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)
• Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise [9.76321513479048]
  We establish maximal concentration bounds for the iterates generated by an approximation (SA) under a contractive operator. We consider two settings where the iterates are potentially unbounded: SA with bounded multiplicative noise and SA with sub-Gaussian additive noise.
  arXiv  Detail & Related papers  (2023-03-28T05:32: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)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  We consider a smooth and strongly convex objective function using a Newton method. We show that there exists a universal weighted averaging scheme that transitions to local convergence at an optimal stage.
  arXiv  Detail & Related papers  (2022-04-20T07:14:21Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. We establish non-asymptotic bounds for both the operator defect and the estimation error.
  arXiv  Detail & Related papers  (2022-01-21T02:46:57Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• 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.