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

Avik Kar, Siddharth Chandak, Rahul Singh, Eric Moulines, Shalabh Bhatnagar, Nicholas Bambos · 2026

Read High-Probability Bounds for SGD under the Polyak-Łojasiewicz Condition with Markovian Noise by Avik Kar, Siddharth Chandak, Rahul Singh, Eric Moulines, Shalabh Bhatnagar, Nicholas Bambos (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-14514.txt.

Description

Kar and co-authors bound SGD error under the Polyak-Lojasiewicz condition with Markovian noise. Gradient noise in real tasks often mixes Markov dependence with martingale parts. Noise size may also grow with the loss value. The team proves a uniform high-probability bound over all time steps. Expected suboptimality falls at a matching 1/k rate. Proof tools pair a Poisson equation with a staged probability argument. Three uses are shown: shared linear regression, private subsampling and online system identification.

Catalog record

CREATORAvik Kar, Siddharth Chandak, Rahul Singh, Eric Moulines, Shalabh Bhatnagar, Nicholas Bambos
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE105988
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.14514

Browse the full library · About the Tower of Babel