{"id":"arxiv/2603.14514","url":"https://arxiv.org/abs/2603.14514","tags":["cs.LG","eess.SY","math.OC","stat.ML"],"score":0,"title":"High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise","domain":"cs.LG","source":"arxiv","authors":["Avik Kar","Siddharth Chandak","Rahul Singh","Eric Moulines","Shalabh Bhatnagar","Nicholas Bambos"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-15","reactions":{}}