# Communication-efficient Decentralized Local SGD over Undirected Networks

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2020.

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

- [On the Convergence of Decentralized Federated Learning Under Imperfect Information Sharing](https://mlsanity.com/paper/2303.10695/) (2023)
- [Faster Convergence of Local SGD for Over-Parameterized Models](https://mlsanity.com/paper/2201.12719/) (2022)
- [The Role of Local Steps in Local SGD](https://mlsanity.com/paper/2203.06798/) (2022)
- [FedLALR: Client-Specific Adaptive Learning Rates Achieve Linear Speedup for Non-IID Data](https://mlsanity.com/paper/2309.09719/) (2023)
- [FedNMUT -- Federated Noisy Model Update Tracking Convergence Analysis](https://mlsanity.com/paper/2403.13247/) (2024)
- [Sharp Gaussian approximations for Decentralized Federated Learning](https://mlsanity.com/paper/2505.08125/) (2025)
- [A Stochastic Approximation Approach for Efficient Decentralized Optimization on Random Networks](https://mlsanity.com/paper/2410.18774/) (2024)
- [Adaptive Sampling and Clipping for Private Worst-Case Group Optimization](https://mlsanity.com/paper/2602.10820/) (2026)

## Abstract (arXiv)

We consider the distributed learning problem where a network of n agents seeks to minimize a global function F. Agents have access to F through noisy gradients, and they can locally communicate with their neighbors a network. We study the Decentralized Local SDG method, where agents perform a number of local gradient steps and occasionally exchange information with their neighbors. Previous algorithmic analysis efforts have focused on the specific network topology (star topology) where a leader node aggregates all agents' information. We generalize that setting to an arbitrary network by analyzing the trade-off between the number of communication rounds and the computational effort of each agent. We bound the expected optimality gap in terms of the number of iterates T, the number of workers n, and the spectral gap of the underlying network. Our main results show that by using only R=Omega(n) communication rounds, one can achieve an error that scales as O(1/nT), where the number of communication rounds is independent of T and only depends on the number of agents. Finally, we provide numerical evidence of our theoretical results through experiments on real and synthetic data.