# Decentralized Optimization in Time-Varying Networks with Arbitrary Delays

arXiv: https://arxiv.org/abs/2405.19513 · HTML: https://mlsanity.com/paper/2405.19513/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 27 references that are in the map.
- First posted on arXiv 29 May 2024.

## Builds on (most cited first, 10 of 10)

- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Stochastic Gradient Push for Distributed Deep Learning](https://mlsanity.com/paper/1811.10792/) (2018)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [Advances in Asynchronous Parallel and Distributed Optimization](https://mlsanity.com/paper/2006.13838/) (2020)
- [Linear convergence in optimization over directed graphs with row-stochastic matrices](https://mlsanity.com/paper/1611.06160/) (2016)
- [Gossiped and Quantized Online Multi-Kernel Learning](https://mlsanity.com/paper/2301.09848/) (2023)
- [Decentralized Optimization in Networks with Arbitrary Delays](https://mlsanity.com/paper/2401.11344/) (2024)

## Built on by (most cited first, 1 of 1)

- [Chemical knowledge-informed framework for privacy-aware retrosynthesis learning](https://mlsanity.com/paper/2502.19119/) (2025)

## Abstract (arXiv)

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.