High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise

Avik Kar; Siddharth Chandak; Rahul Singh; Eric Moulines; Shalabh Bhatnagar; Nicholas Bambos

cs.LGMar 15, 2026

High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise

Authors: Avik Kar, Siddharth Chandak, Rahul Singh, Eric Moulines, Shalabh Bhatnagar, Nicholas Bambos

Organizations: Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India. · Department of Electrical Engineering, Stanford University, Stanford, CA, USA. · CMAP, CNRS, École polytechnique, Institut Polytechnique ´de Paris, Palaiseau, France.

Abstract

We present the first uniform-in-time high-probability bound for SGD under the PL condition, where the gradient noise contains both Markovian and martingale difference components. This significantly broadens the scope of finite-time guarantees, as the PL condition arises in many machine learning and deep learning models while Markovian noise naturally arises in decentralized optimization and online system identification problems. We further allow the magnitude of noise to grow with the function value, enabling the analysis of many practical sampling strategies. In addition to the high-probability guarantee, we establish a matching $1/k$ decay rate for the expected suboptimality. Our proof technique relies on the Poisson equation to handle the Markovian noise and a probabilistic induction argument to address the lack of almost-sure bounds on the objective. Finally, we demonstrate the applicability of our framework by analyzing three practical optimization problems: token-based decentralized linear regression, supervised learning with subsampling for privacy amplification, and online system identification.

Explore similar work

High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence
Jun 24, 2026Dhruv Sarkar, Aprameyo Chakrabartty, Vaneet AggarwalStochastic Optimization Optimization Convergence Analysis
Indian Institute of Technology Kharagpur · Mohamed bin Zayed University of Artificial Intelligence · Purdue University
High-Probability Guarantees for SGD under $β$ -Heavy-Tailed Gradient Noise
Sep 26, 2026Qijun Tong, Masahiro Ikeda, Ryota KawasumiStochastic Gradient Descent Stochastic Optimization Convergence
The University of Electro-Communications · The University of Osaka · Gunma University
Unveiling High-Probability Generalization in Decentralized SGD
May 11, 2026Jiahuan Wang, Ping Luo, Ziqing Wen +2Algorithmic Stability Decentralized Learning
College of Computer Science and Technology National University of Defense Technology Changsha, Hunan 410073, China

Jun 24, 2026J/K move · Enter open · S save

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

Dhruv Sarkar, Aprameyo Chakrabartty, Vaneet Aggarwal

Indian Institute of Technology Kharagpur · Mohamed bin Zayed University of Artificial Intelligence · Purdue University

Stochastic Optimization Optimization Convergence Analysis Heavy-Tailed Noise Stochastic Optimization Convergence Heavy-Tailed Distributions Heavy-Tailed Stochastic Optimization+1

Open paper AskPDF arXiv

We study first-order methods for smooth objectives satisfying the Polyak-Łojasiewicz (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

\widetilde{O}(t_{mix}^2/k)

, leaving a gap with the

\widetilde{O}(t_{mix}/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

\widetilde{O}(t_{mix}/(k+K_0))

under geometric mixing. We prove this linear dependence on the mixing time is optimal via a matching

Ω(σ^2 t_{mix}/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 \in (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

\widetilde{O}(σ_p^2(t_{mix}/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.

Abstract

Explore similar work

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

High-Probability Guarantees for SGD under βββ-Heavy-Tailed Gradient Noise

Unveiling High-Probability Generalization in Decentralized SGD

High-Probability Guarantees for SGD under $β$ -Heavy-Tailed Gradient Noise