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
| CREATOR | Avik Kar, Siddharth Chandak, Rahul Singh, Eric Moulines, Shalabh Bhatnagar, Nicholas Bambos |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 105988 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.14514