Decentralized Optimization in Time-Varying Networks with Arbitrary Delays
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914962179358720 |
|---|---|
| author | Ortega, Tomas Jafarkhani, Hamid |
| author_facet | Ortega, Tomas Jafarkhani, Hamid |
| contents | We consider a decentralized optimization problem for networks affected by communication delays. Examples of such networks include collaborative machine learning, sensor networks, and multi-agent systems. To mimic communication delays, we add virtual non-computing nodes to the network, resulting in directed graphs. This motivates investigating decentralized optimization solutions on directed graphs. Existing solutions assume nodes know their out-degrees, resulting in limited applicability. To overcome this limitation, we introduce a novel gossip-based algorithm, called DT-GO, that does not need to know the out-degrees. The algorithm is applicable in general directed networks, for example networks with delays or limited acknowledgment capabilities. We derive convergence rates for both convex and non-convex objectives, showing that our algorithm achieves the same complexity order as centralized Stochastic Gradient Descent. In other words, the effects of the graph topology and delays are confined to higher-order terms. Additionally, we extend our analysis to accommodate time-varying network topologies. Numerical simulations are provided to support our theoretical findings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_19513 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Decentralized Optimization in Time-Varying Networks with Arbitrary Delays Ortega, Tomas Jafarkhani, Hamid Machine Learning Distributed, Parallel, and Cluster Computing Systems and Control Optimization and Control 68W10, 68W15, 68W40, 90C06, 90C35, 90C25 G.1.6; F.2.1; E.4 We consider a decentralized optimization problem for networks affected by communication delays. Examples of such networks include collaborative machine learning, sensor networks, and multi-agent systems. To mimic communication delays, we add virtual non-computing nodes to the network, resulting in directed graphs. This motivates investigating decentralized optimization solutions on directed graphs. Existing solutions assume nodes know their out-degrees, resulting in limited applicability. To overcome this limitation, we introduce a novel gossip-based algorithm, called DT-GO, that does not need to know the out-degrees. The algorithm is applicable in general directed networks, for example networks with delays or limited acknowledgment capabilities. We derive convergence rates for both convex and non-convex objectives, showing that our algorithm achieves the same complexity order as centralized Stochastic Gradient Descent. In other words, the effects of the graph topology and delays are confined to higher-order terms. Additionally, we extend our analysis to accommodate time-varying network topologies. Numerical simulations are provided to support our theoretical findings. |
| title | Decentralized Optimization in Time-Varying Networks with Arbitrary Delays |
| topic | Machine Learning Distributed, Parallel, and Cluster Computing Systems and Control Optimization and Control 68W10, 68W15, 68W40, 90C06, 90C35, 90C25 G.1.6; F.2.1; E.4 |
| url | https://arxiv.org/abs/2405.19513 |