mlsanityData to 7 Oct 2026

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

arXiv 2606.26316 ↗First posted 24 Jun 2026cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

41 of 62 references.

References · 41

  1. 2016Deep Learning with Differential Privacycited by 2,682
  2. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  3. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  4. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 231
  5. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  6. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 211
  7. 2019SGD: General Analysis and Improved Ratescited by 206
  8. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  9. 2020Better Theory for SGD in the Nonconvex Worldcited by 156
  10. 2019Mean estimation and regression under heavy-tailed distributions--a surveycited by 133
  11. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
  12. 2018On Markov Chain Gradient Descentcited by 63
29 more
  1. 2023High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variancecited by 60
  2. 2020Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noisecited by 52
  3. 2023(Amplified) Banded Matrix Factorization: A unified approach to private trainingcited by 49
  4. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 48
  5. 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 37
  6. 2021Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variancecited by 34
  7. 2020High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noisecited by 31
  8. 2018Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimizationcited by 30
  9. 2020A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performancecited by 26
  10. 2024The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noisecited by 23
  11. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 22
  12. 2023Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problemscited by 21
  13. 2023High Probability Convergence of Clipped-SGD Under Heavy-tailed Noisecited by 19
  14. 2020Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomnesscited by 18
  15. 2021High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noisecited by 18
  16. 2021Streaming Linear System Identification with Reverse Experience Replaycited by 17
  17. 2022A principled framework for the design and analysis of token algorithmscited by 17
  18. 2023Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applicationscited by 15
  19. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  20. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approachcited by 14
  21. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPscited by 11
  22. 2024Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noisecited by 10
  23. 2023Provably Robust Temporal Difference Learning for Heavy-Tailed Rewardscited by 9
  24. 2025Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noisecited by 9
  25. 2026Privacy Amplification for BandMF via b-Min-Sep Subsamplingcited by 6
  26. 2025Adversarially-Robust TD Learning with Markovian Data: Finite-Time Rates and Fundamental Limitscited by 5
  27. 2026Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noisecited by 4
  28. 2026High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noisecited by 2
  29. 2026Persistent-Transient Policy Evaluation for Markov Chains via Minimal Peripheral Quotientscited by 1

Built on by

Not cited yet.