# Decentralized Optimization On Time-Varying Directed Graphs Under Communication Constraints

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2020.

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

- [On the Convergence of Decentralized Federated Learning Under Imperfect Information Sharing](https://mlsanity.com/paper/2303.10695/) (2023)
- [Improved Convergence Analysis and SNR Control Strategies for Federated Learning in the Presence of Noise](https://mlsanity.com/paper/2307.07406/) (2023)
- [Fed-QSSL: A Framework for Personalized Federated Learning under Bitwidth and Data Heterogeneity](https://mlsanity.com/paper/2312.13380/) (2023)
- [FedNMUT -- Federated Noisy Model Update Tracking Convergence Analysis](https://mlsanity.com/paper/2403.13247/) (2024)
- [Communication-Efficient Zeroth-Order Distributed Online Optimization: Algorithm, Theory, and Applications](https://mlsanity.com/paper/2306.05655/) (2023)

## Abstract (arXiv)

We consider the problem of decentralized optimization where a collection of agents, each having access to a local cost function, communicate over a time-varying directed network and aim to minimize the sum of those functions. In practice, the amount of information that can be exchanged between the agents is limited due to communication constraints. We propose a communication-efficient algorithm for decentralized convex optimization that rely on sparsification of local updates exchanged between neighboring agents in the network. In directed networks, message sparsification alters column-stochasticity -- a property that plays an important role in establishing convergence of decentralized learning tasks. We propose a decentralized optimization scheme that relies on local modification of mixing matrices, and show that it achieves O(fraclnT√T) convergence rate in the considered settings. Experiments validate theoretical results and demonstrate efficacy of the proposed algorithm.