# Scale-Robust Timely Asynchronous Decentralized Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 26 references that are in the map.
- First posted on arXiv 30 Apr 2024.

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

- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [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)
- [Asynchronous Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1710.06952/) (2017)
- [Decentralized Deep Learning with Arbitrary Communication Compression](https://mlsanity.com/paper/1907.09356/) (2019)
- [How to scale distributed deep learning?](https://mlsanity.com/paper/1611.04581/) (2016)
- [The Age of Gossip in Networks](https://mlsanity.com/paper/2102.02893/) (2021)
- [Age of Information in Gossip Networks: A Friendly Introduction and Literature Survey](https://mlsanity.com/paper/2312.16163/) (2023)
- [Asynchronous Hierarchical Federated Learning](https://mlsanity.com/paper/2206.00054/) (2022)
- [Straggler-Resilient Decentralized Learning via Adaptive Asynchronous Updates](https://mlsanity.com/paper/2306.06559/) (2023)
- [ASUMAN: Age Sense Updating Multiple Access in Networks](https://mlsanity.com/paper/2207.07094/) (2022)
- [Timely Opportunistic Gossiping in Dense Networks](https://mlsanity.com/paper/2301.00798/) (2023)
- [Age-Aware Gossiping in Network Topologies](https://mlsanity.com/paper/2304.03249/) (2023)

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

- [Towards efficient compression and communication for prototype-based decentralized learning](https://mlsanity.com/paper/2411.09267/) (2024)

## Abstract (arXiv)

We consider an asynchronous decentralized learning system, which consists of a network of connected devices trying to learn a machine learning model without any centralized parameter server. The users in the network have their own local training data, which is used for learning across all the nodes in the network. The learning method consists of two processes, evolving simultaneously without any necessary synchronization. The first process is the model update, where the users update their local model via a fixed number of stochastic gradient descent steps. The second process is model mixing, where the users communicate with each other via randomized gossiping to exchange their models and average them to reach consensus. In this work, we investigate the staleness criteria for such a system, which is a sufficient condition for convergence of individual user models. We show that for network scaling, i.e., when the number of user devices n is very large, if the gossip capacity of individual users scales as Omega(log n), we can guarantee the convergence of user models in finite time. Furthermore, we show that the bounded staleness can only be guaranteed by any distributed opportunistic scheme by Omega(n) scaling.