# DIGEST: Fast and Communication Efficient Decentralized Learning with Local Updates

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 52 references that are in the map.
- First posted on arXiv 14 Jul 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [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)
- [Don't Use Large Mini-Batches, Use Local SGD](https://mlsanity.com/paper/1808.07217/) (2018)
- [Federated Optimization:Distributed Optimization Beyond the Datacenter](https://mlsanity.com/paper/1511.03575/) (2015)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [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)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Unified Optimal Analysis of the (Stochastic) Gradient Method](https://mlsanity.com/paper/1907.04232/) (2019)
- [Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD](https://mlsanity.com/paper/1803.01113/) (2018)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [Decentralized Gradient Tracking with Local Steps](https://mlsanity.com/paper/2301.01313/) (2023)
- [Pipe-SGD: A Decentralized Pipelined SGD Framework for Distributed Deep Net Training](https://mlsanity.com/paper/1811.03619/) (2018)
- [Communication-efficient SGD: From Local SGD to One-Shot Averaging](https://mlsanity.com/paper/2106.04759/) (2021)
- [Private Weighted Random Walk Stochastic Gradient Descent](https://mlsanity.com/paper/2009.01790/) (2020)
- [Locally Asynchronous Stochastic Gradient Descent for Decentralised Deep Learning](https://mlsanity.com/paper/2203.13085/) (2022)

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

- [VulnLLMEval: A Framework for Evaluating Large Language Models in Software Vulnerability Detection and Patching](https://mlsanity.com/paper/2409.10756/) (2024)
- [DRACO: Decentralized Asynchronous Federated Learning over Row-Stochastic Wireless Networks](https://mlsanity.com/paper/2406.13533/) (2024)
- [Adaptive Aggregation Weights for Federated Segmentation of Pancreas MRI](https://mlsanity.com/paper/2410.22530/) (2024)
- [Differentiated Aggregation to Improve Generalization in Federated Learning](https://mlsanity.com/paper/2404.11754/) (2024)
- [A Comprehensive Survey on the Security of Smart Grid: Challenges, Mitigations, and Future Research Opportunities](https://mlsanity.com/paper/2407.07966/) (2024)
- [Self-Regulating Random Walks for Resilient Decentralized Learning on Graphs](https://mlsanity.com/paper/2407.11762/) (2024)
- [IPMN Risk Assessment under Federated Learning Paradigm](https://mlsanity.com/paper/2411.05697/) (2024)
- [On the Fast Adaptation of Delayed Clients in Decentralized Federated Learning: A Centroid-Aligned Distillation Approach](https://mlsanity.com/paper/2508.02993/) (2025)
- [A Tale of Two Learning Algorithms: Multiple Stream Random Walk and Asynchronous Gossip](https://mlsanity.com/paper/2504.09792/) (2025)
- [Federated Breast Cancer Detection Enhanced by Synthetic Ultrasound Image Augmentation](https://mlsanity.com/paper/2506.23334/) (2025)
- [Decentralized SGD with Controlled Disagreement Finds Flatter Minima](https://mlsanity.com/paper/2602.02899/) (2026)
- [Decentralized Learning via Random Walk with Jumps](https://mlsanity.com/paper/2604.12260/) (2026)

## Abstract (arXiv)

Two widely considered decentralized learning algorithms are Gossip and random walk-based learning. Gossip algorithms (both synchronous and asynchronous versions) suffer from high communication cost, while random-walk based learning experiences increased convergence time. In this paper, we design a fast and communication-efficient asynchronous decentralized learning mechanism DIGEST by taking advantage of both Gossip and random-walk ideas, and focusing on stochastic gradient descent (SGD). DIGEST is an asynchronous decentralized algorithm building on local-SGD algorithms, which are originally designed for communication efficient centralized learning. We design both single-stream and multi-stream DIGEST, where the communication overhead may increase when the number of streams increases, and there is a convergence and communication overhead trade-off which can be leveraged. We analyze the convergence of single- and multi-stream DIGEST, and prove that both algorithms approach to the optimal solution asymptotically for both iid and non-iid data distributions. We evaluate the performance of single- and multi-stream DIGEST for logistic regression and a deep neural network ResNet20. The simulation results confirm that multi-stream DIGEST has nice convergence properties; i.e., its convergence time is better than or comparable to the baselines in iid setting, and outperforms the baselines in non-iid setting.