Decentralized Optimization in Networks with Arbitrary Delays
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916543961497600 |
|---|---|
| author | Ortega, Tomas Jafarkhani, Hamid |
| author_facet | Ortega, Tomas Jafarkhani, Hamid |
| contents | We consider the problem of decentralized optimization in networks with communication delays. To accommodate delays, we need decentralized optimization algorithms that work on directed graphs. Existing approaches require nodes to know their out-degree to achieve convergence. We propose a novel gossip-based algorithm that circumvents this requirement, allowing decentralized optimization in networks with communication delays. We prove that our algorithm converges on non-convex objectives, with the same main complexity order term as centralized Stochastic Gradient Descent (SGD), and show that the graph topology and the delays only affect the higher order terms. We provide numerical simulations that illustrate our theoretical results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_11344 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Decentralized Optimization in Networks with Arbitrary Delays Ortega, Tomas Jafarkhani, Hamid Optimization and Control Multiagent Systems Systems and Control Signal Processing 68W10, 68W15, 68W40, 90C06, 90C25, 90C35 G.1.6; F.2.1; E.4 We consider the problem of decentralized optimization in networks with communication delays. To accommodate delays, we need decentralized optimization algorithms that work on directed graphs. Existing approaches require nodes to know their out-degree to achieve convergence. We propose a novel gossip-based algorithm that circumvents this requirement, allowing decentralized optimization in networks with communication delays. We prove that our algorithm converges on non-convex objectives, with the same main complexity order term as centralized Stochastic Gradient Descent (SGD), and show that the graph topology and the delays only affect the higher order terms. We provide numerical simulations that illustrate our theoretical results. |
| title | Decentralized Optimization in Networks with Arbitrary Delays |
| topic | Optimization and Control Multiagent Systems Systems and Control Signal Processing 68W10, 68W15, 68W40, 90C06, 90C25, 90C35 G.1.6; F.2.1; E.4 |
| url | https://arxiv.org/abs/2401.11344 |