On the Linear Speedup of the Push-Pull Method for Decentralized Optimization over Digraphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911170788589568 |
|---|---|
| author | Liang, Liyuan Luo, Gan Yuan, Kun |
| author_facet | Liang, Liyuan Luo, Gan Yuan, Kun |
| contents | The linear speedup property is essential for demonstrating the advantage of distributed algorithms over their single-node counterparts. In this paper, we study the stochastic Push-Pull method, a widely adopted decentralized optimization algorithm over directed graphs (digraphs). Unlike methods that rely solely on row-stochastic or column-stochastic mixing matrices, Push-Pull avoids nonlinear correction and has shown superior empirical performance across a variety of settings. However, its theoretical analysis remains challenging, and the linear speedup property has not been generally establishe--revealing a significant gap between empirical success and limited theoretical understanding. To bridge this gap, we propose a novel analysis framework and prove that Push-Pull achieves linear speedup over arbitrary strongly connected digraphs. Our results provide the comprehensive theoretical understanding for stochastic Push-Pull, aligning its theory with empirical performance. Code: https://github.com/pkumelon/PushPull. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_18075 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Linear Speedup of the Push-Pull Method for Decentralized Optimization over Digraphs Liang, Liyuan Luo, Gan Yuan, Kun Optimization and Control The linear speedup property is essential for demonstrating the advantage of distributed algorithms over their single-node counterparts. In this paper, we study the stochastic Push-Pull method, a widely adopted decentralized optimization algorithm over directed graphs (digraphs). Unlike methods that rely solely on row-stochastic or column-stochastic mixing matrices, Push-Pull avoids nonlinear correction and has shown superior empirical performance across a variety of settings. However, its theoretical analysis remains challenging, and the linear speedup property has not been generally establishe--revealing a significant gap between empirical success and limited theoretical understanding. To bridge this gap, we propose a novel analysis framework and prove that Push-Pull achieves linear speedup over arbitrary strongly connected digraphs. Our results provide the comprehensive theoretical understanding for stochastic Push-Pull, aligning its theory with empirical performance. Code: https://github.com/pkumelon/PushPull. |
| title | On the Linear Speedup of the Push-Pull Method for Decentralized Optimization over Digraphs |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2506.18075 |