Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise

Shubhada Agrawal, Siva Theja Maguluri, Martin Zubeldia

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 co…