High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915864775753728 |
|---|---|
| author | Kar, Avik Chandak, Siddharth Singh, Rahul Moulines, Eric Bhatnagar, Shalabh Bambos, Nicholas |
| author_facet | Kar, Avik Chandak, Siddharth Singh, Rahul Moulines, Eric Bhatnagar, Shalabh Bambos, Nicholas |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_14514 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise Kar, Avik Chandak, Siddharth Singh, Rahul Moulines, Eric Bhatnagar, Shalabh Bambos, Nicholas Machine Learning Systems and Control Optimization and Control 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. |
| title | High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise |
| topic | Machine Learning Systems and Control Optimization and Control |
| url | https://arxiv.org/abs/2603.14514 |