# Faster Convergence with Less Communication: Broadcast-Based Subgraph Sampling for Decentralized Learning over Wireless Networks

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 51 references that are in the map.
- First posted on arXiv 24 Jan 2024.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [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)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [Communication Compression for Decentralized Training](https://mlsanity.com/paper/1803.06443/) (2018)
- [Distributed optimization over time-varying directed graphs](https://mlsanity.com/paper/1303.2289/) (2013)
- [A Faster Interior Point Method for Semidefinite Programming](https://mlsanity.com/paper/2009.10217/) (2020)
- [Federated Learning over Wireless Device-to-Device Networks: Algorithms and Convergence Analysis](https://mlsanity.com/paper/2101.12704/) (2021)
- [Optimal Algorithms for Non-Smooth Distributed Optimization in Networks](https://mlsanity.com/paper/1806.00291/) (2018)
- [Decentralized gradient methods: does topology matter?](https://mlsanity.com/paper/2002.12688/) (2020)
- [SQuARM-SGD: Communication-Efficient Momentum SGD for Decentralized Optimization](https://mlsanity.com/paper/2005.07041/) (2020)
- [A general framework for decentralized optimization with first-order methods](https://mlsanity.com/paper/2009.05837/) (2020)
- [Beyond spectral gap: The role of the topology in decentralized learning](https://mlsanity.com/paper/2206.03093/) (2022)
- [Moniqua: Modulo Quantized Communication in Decentralized SGD](https://mlsanity.com/paper/2002.11787/) (2020)
- [Decentralized and Model-Free Federated Learning: Consensus-Based Distillation in Function Space](https://mlsanity.com/paper/2104.00352/) (2021)
- [Convergence rates for distributed stochastic optimization over random networks](https://mlsanity.com/paper/1803.07836/) (2018)
- [Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima](https://mlsanity.com/paper/2003.02818/) (2020)
- [Communication-Efficient Design for Quantized Decentralized Federated Learning](https://mlsanity.com/paper/2303.08423/) (2023)
- [Distributed Consensus in Wireless Networks with Probabilistic Broadcast Scheduling](https://mlsanity.com/paper/2301.11714/) (2023)
- [Decentralized Learning over Wireless Networks: The Effect of Broadcast with Random Access](https://mlsanity.com/paper/2305.07368/) (2023)
- [Decentralized Learning over Wireless Networks with Broadcast-Based Subgraph Sampling](https://mlsanity.com/paper/2310.16106/) (2023)
- [Distributed Optimization via Gradient Descent with Event-Triggered Zooming over Quantized Communication](https://mlsanity.com/paper/2309.04588/) (2023)
- [Asynchronous Distributed Optimization with Delay-free Parameters](https://mlsanity.com/paper/2312.06508/) (2023)

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

- [Time-varying Mixing Matrix Design for Energy-efficient Decentralized Federated Learning](https://mlsanity.com/paper/2512.24069/) (2025)
- [Information Entropy-Based Scheduling for Communication-Efficient Decentralized Learning](https://mlsanity.com/paper/2507.17426/) (2025)

## Abstract (arXiv)

Consensus-based decentralized stochastic gradient descent (D-SGD) is a widely adopted algorithm for decentralized training of machine learning models across networked agents. A crucial part of D-SGD is the consensus-based model averaging, which heavily relies on information exchange and fusion among the nodes. Specifically, for consensus averaging over wireless networks, communication coordination is necessary to determine when and how a node can access the channel and transmit (or receive) information to (or from) its neighbors. In this work, we propose textttBASS, a broadcast-based subgraph sampling method designed to accelerate the convergence of D-SGD while considering the actual communication cost per iteration. textttBASS creates a set of mixing matrix candidates that represent sparser subgraphs of the base topology. In each consensus iteration, one mixing matrix is sampled, leading to a specific scheduling decision that activates multiple collision-free subsets of nodes. The sampling occurs in a probabilistic manner, and the elements of the mixing matrices, along with their sampling probabilities, are jointly optimized. Simulation results demonstrate that textttBASS enables faster convergence with fewer transmission slots compared to existing link-based scheduling methods. In conclusion, the inherent broadcasting nature of wireless channels offers intrinsic advantages in accelerating the convergence of decentralized optimization and learning.