{"id":"arxiv/2605.20999","url":"https://arxiv.org/abs/2605.20999","tags":["math.PR","cs.LG","math.OC","stat.ML"],"score":0,"title":"Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise","domain":"math.PR","source":"arxiv","authors":["Shubhada Agrawal","Siva Theja Maguluri","Martin Zubeldia"],"reviews":0,"subject":"math.PR","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-20","reactions":{}}