A Proximal Gradient Method With Probabilistic Multi-Gossip Communications for Decentralized Composite Optimization
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909810957484032 |
|---|---|
| author | Guo, Luyao Wang, Luqing Shi, Xinli Cao, Jinde |
| author_facet | Guo, Luyao Wang, Luqing Shi, Xinli Cao, Jinde |
| contents | Decentralized optimization methods with local updates have recently gained attention for their provable ability to communication acceleration. In these methods, nodes perform several iterations of local computations between the communication rounds. Nevertheless, this capability is effective only when the network is sufficiently well-connected and the loss function is smooth. In this paper, we propose a communication-efficient method MG-Skip with probabilistic local updates and multi-gossip communications for decentralized composite (smooth + nonsmooth) optimization, whose stepsize is independent of the number of local updates and the network topology. For any undirected and connected networks, MG-Skip allows for the multi-gossip communications to be skipped in most iterations in the strongly convex setting, while its computation complexity is $\mathcal{O}\left(κ\log \frac{1}ε\right)$ and communication complexity is only $\mathcal{O}\left(\sqrt{\fracκ{(1-ρ)}} \log \frac{1}ε\right)$, where $κ$ is the condition number of the loss function, $ρ$ reflects the connectivity of the network topology, and $ε$ is the target accuracy. The theoretical results indicate that MG-Skip achieves provable communication acceleration, thereby validating the advantages of local updates in the nonsmooth setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_11861 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Proximal Gradient Method With Probabilistic Multi-Gossip Communications for Decentralized Composite Optimization Guo, Luyao Wang, Luqing Shi, Xinli Cao, Jinde Optimization and Control Machine Learning Decentralized optimization methods with local updates have recently gained attention for their provable ability to communication acceleration. In these methods, nodes perform several iterations of local computations between the communication rounds. Nevertheless, this capability is effective only when the network is sufficiently well-connected and the loss function is smooth. In this paper, we propose a communication-efficient method MG-Skip with probabilistic local updates and multi-gossip communications for decentralized composite (smooth + nonsmooth) optimization, whose stepsize is independent of the number of local updates and the network topology. For any undirected and connected networks, MG-Skip allows for the multi-gossip communications to be skipped in most iterations in the strongly convex setting, while its computation complexity is $\mathcal{O}\left(κ\log \frac{1}ε\right)$ and communication complexity is only $\mathcal{O}\left(\sqrt{\fracκ{(1-ρ)}} \log \frac{1}ε\right)$, where $κ$ is the condition number of the loss function, $ρ$ reflects the connectivity of the network topology, and $ε$ is the target accuracy. The theoretical results indicate that MG-Skip achieves provable communication acceleration, thereby validating the advantages of local updates in the nonsmooth setting. |
| title | A Proximal Gradient Method With Probabilistic Multi-Gossip Communications for Decentralized Composite Optimization |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2312.11861 |