# High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence

arXiv: https://arxiv.org/abs/2606.26316 · HTML: https://mlsanity.com/paper/2606.26316/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 41 of its 62 references that are in the map.
- First posted on arXiv 24 Jun 2026.

## Builds on (most cited first, 30 of 41)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails](https://mlsanity.com/paper/2106.14343/) (2021)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance](https://mlsanity.com/paper/2302.00999/) (2023)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)
- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [From Gradient Clipping to Normalization for Heavy Tailed SGD](https://mlsanity.com/paper/2410.13849/) (2024)
- [Stochastic Gradient Descent under Markovian Sampling Schemes](https://mlsanity.com/paper/2302.14428/) (2023)
- [Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance](https://mlsanity.com/paper/2102.10346/) (2021)
- [Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization](https://mlsanity.com/paper/1804.06568/) (2018)
- [High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noise](https://mlsanity.com/paper/2006.05610/) (2020)
- [A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance](https://mlsanity.com/paper/2002.05273/) (2020)
- [Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes](https://mlsanity.com/paper/2309.01922/) (2023)
- [The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise](https://mlsanity.com/paper/2401.07844/) (2024)
- [High Probability Convergence of Clipped-SGD Under Heavy-tailed Noise](https://mlsanity.com/paper/2302.05437/) (2023)
- [Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems](https://mlsanity.com/paper/2311.04161/) (2023)
- [High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2106.05958/) (2021)
- [Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomness](https://mlsanity.com/paper/2003.10973/) (2020)
- [A principled framework for the design and analysis of token algorithms](https://mlsanity.com/paper/2205.15015/) (2022)
- [Streaming Linear System Identification with Reverse Experience Replay](https://mlsanity.com/paper/2103.05896/) (2021)
- [Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications](https://mlsanity.com/paper/2312.02828/) (2023)

## Abstract (arXiv)

We study first-order methods for smooth objectives satisfying the Polyak-Lojasiewicz (PL) condition when gradient samples are generated by an exogenous Markov chain. In the light-tailed setting, prior uniform-in-time high-probability bounds for ordinary Stochastic Gradient Descent (SGD) under a standard growth envelope scale as widetildeO(tmix2/k), leaving a gap with the widetildeO(tmix/k) expectation bounds. We close this gap using a lag-blocking argument to establish a uniform high-probability guarantee with a leading stochastic term of widetildeO(tmix/(k+K0)) under geometric mixing. We prove this linear dependence on the mixing time is optimal via a matching Omega(σ2 tmix/k) lower bound on a quadratic objective driven by a persistent two-state chain. We then extend this framework to heavy-tailed Markovian gradients satisfying a stationary finite-p-moment condition, p ∈ (1,2]. We design an all-samples clipped block method that uses every Markov transition while mitigating Markovian bias. Under a transition budget T, this algorithm achieves a high-probability stochastic error of widetildeO(σp2(tmix/T)2(p-1)/p). We establish a matching lower bound by reducing PL optimization to heavy-tailed mean estimation for a sticky Markov chain. Ultimately, this work tightly characterizes the optimal polynomial dependence on mixing time for light-tailed PL-SGD, and the optimal heavy-tail exponent and effective-sample-size dependence in the robust regime.