# Epidemic Learning: Boosting Decentralized Learning with Randomized Communication

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 60 references that are in the map.
- First posted on arXiv 3 Oct 2023.

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

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification](https://mlsanity.com/paper/1909.06335/) (2019)
- [LEAF: A Benchmark for Federated Settings](https://mlsanity.com/paper/1812.01097/) (2018)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [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)
- [The Non-IID Data Quagmire of Decentralized Machine Learning](https://mlsanity.com/paper/1910.00189/) (2019)
- [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)
- [Stochastic Gradient Push for Distributed Deep Learning](https://mlsanity.com/paper/1811.10792/) (2018)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015)
- [Distributed optimization over time-varying directed graphs](https://mlsanity.com/paper/1303.2289/) (2013)
- [MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling](https://mlsanity.com/paper/1905.09435/) (2019)
- [Optimal Complexity in Decentralized Training](https://mlsanity.com/paper/2006.08085/) (2020)
- [Exponential Graph is Provably Efficient for Decentralized Deep Training](https://mlsanity.com/paper/2110.13363/) (2021)
- [Consensus Control for Decentralized Deep Learning](https://mlsanity.com/paper/2102.04828/) (2021)
- [Optimal Algorithms for Non-Smooth Distributed Optimization in Networks](https://mlsanity.com/paper/1806.00291/) (2018)
- [Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs](https://mlsanity.com/paper/1406.2075/) (2014)
- [Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data](https://mlsanity.com/paper/2204.04452/) (2022)
- [Accelerating Gossip SGD with Periodic Global Averaging](https://mlsanity.com/paper/2105.09080/) (2021)
- [Decentralized federated learning of deep neural networks on non-iid data](https://mlsanity.com/paper/2107.08517/) (2021)
- [Communication-Efficient Topologies for Decentralized Learning with O(1) Consensus Rate](https://mlsanity.com/paper/2210.07881/) (2022)
- [Decentralized Learning Made Easy with DecentralizePy](https://mlsanity.com/paper/2304.08322/) (2023)
- [BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning](https://mlsanity.com/paper/2111.04287/) (2021)
- [Beyond spectral gap (extended): The role of the topology in decentralized learning](https://mlsanity.com/paper/2301.02151/) (2023)

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

- [Noiseless Privacy-Preserving Decentralized Learning](https://mlsanity.com/paper/2404.09536/) (2024)
- [Boosting Asynchronous Decentralized Learning with Model Fragmentation](https://mlsanity.com/paper/2410.12918/) (2024)
- [NoLoCo: No-all-reduce Low Communication Training Method for Large Models](https://mlsanity.com/paper/2506.10911/) (2025)
- [Low-Cost Privacy-Preserving Decentralized Learning](https://mlsanity.com/paper/2403.11795/) (2024)
- [Dynamic Topology Optimization for Non-IID Data in Decentralized Learning](https://mlsanity.com/paper/2602.03383/) (2026)
- [Energy-Aware Decentralized Learning with Intermittent Model Training](https://mlsanity.com/paper/2407.01283/) (2024)
- [Fair Decentralized Learning](https://mlsanity.com/paper/2410.02541/) (2024)
- [ROSS: RObust decentralized Stochastic learning based on Shapley values](https://mlsanity.com/paper/2411.00365/) (2024)
- [Exposing the Vulnerability of Decentralized Learning to Membership Inference Attacks Through the Lens of Graph Mixing](https://mlsanity.com/paper/2412.12837/) (2024)
- [Efficient AllReduce with Stragglers](https://mlsanity.com/paper/2505.23523/) (2025)
- [Mosaic Learning: A Framework for Decentralized Learning with Model Fragmentation](https://mlsanity.com/paper/2602.04352/) (2026)
- [Decentralized Federated Learning by Partial Message Exchange](https://mlsanity.com/paper/2603.01730/) (2026)
- [Your Neighbors Know: Leveraging Local Neighborhoods for Backdoor Detection in Decentralized Learning](https://mlsanity.com/paper/2605.19969/) (2026)
- [HEAL: Resilient and Self-* Hub-based Learning](https://mlsanity.com/paper/2605.27475/) (2026)
- [Accelerating MoE Model Inference with Expert Sharding](https://mlsanity.com/paper/2503.08467/) (2025)
- [Hubs and Spokes Learning: Efficient and Scalable Collaborative Machine Learning](https://mlsanity.com/paper/2504.20988/) (2025)
- [Go With The Flow: Churn-Tolerant Decentralized Training of Large Language Models](https://mlsanity.com/paper/2509.21221/) (2025)
- [Robust and Efficient Collaborative Learning](https://mlsanity.com/paper/2510.08311/) (2025)
- [PID-Guided Partial Alignment for Multimodal Decentralized Federated Learning](https://mlsanity.com/paper/2601.10012/) (2026)
- [DECA: Decentralizing Block-Wise Adam for Efficient LLM Full-Parameter Fine-Tuning on Non-IID Data](https://mlsanity.com/paper/2606.03209/) (2026)
- [Stream Learning: Partition-Fair Gossip Learning Without Tokens](https://mlsanity.com/paper/2608.06946/) (2026)

## Abstract (arXiv)

We present Epidemic Learning (EL), a simple yet powerful decentralized learning (DL) algorithm that leverages changing communication topologies to achieve faster model convergence compared to conventional DL approaches. At each round of EL, each node sends its model updates to a random sample of s other nodes (in a system of n nodes). We provide an extensive theoretical analysis of EL, demonstrating that its changing topology culminates in superior convergence properties compared to the state-of-the-art (static and dynamic) topologies. Considering smooth non-convex loss functions, the number of transient iterations for EL, i.e., the rounds required to achieve asymptotic linear speedup, is in O(n3/s2) which outperforms the best-known bound O(n3) by a factor of s2, indicating the benefit of randomized communication for DL. We empirically evaluate EL in a 96-node network and compare its performance with state-of-the-art DL approaches. Our results illustrate that EL converges up to  1.7× quicker than baseline DL algorithms and attains 2.2 % higher accuracy for the same communication volume.