# A Distributed Synchronous SGD Algorithm with Global Top-k Sparsification for Low Bandwidth Networks

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jan 2019.

## Built on by (most cited first, 30 of 37)

- [1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed](https://mlsanity.com/paper/2102.02888/) (2021)
- [FEDZIP: A Compression Framework for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2102.01593/) (2021)
- [Time-Correlated Sparsification for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2101.08837/) (2021)
- [On the Utility of Gradient Compression in Distributed Training Systems](https://mlsanity.com/paper/2103.00543/) (2021)
- [1-bit LAMB: Communication Efficient Large-Scale Large-Batch Training with LAMB's Convergence Speed](https://mlsanity.com/paper/2104.06069/) (2021)
- [Near-Optimal Sparse Allreduce for Distributed Deep Learning](https://mlsanity.com/paper/2201.07598/) (2022)
- [ScaleCom: Scalable Sparsified Gradient Compression for Communication-Efficient Distributed Training](https://mlsanity.com/paper/2104.11125/) (2021)
- [A Survey of What to Share in Federated Learning: Perspectives on Model Utility, Privacy Leakage, and Communication Efficiency](https://mlsanity.com/paper/2307.10655/) (2023)
- [FusionAI: Decentralized Training and Deploying LLMs with Massive Consumer-Level GPUs](https://mlsanity.com/paper/2309.01172/) (2023)
- [Neural Distributed Source Coding](https://mlsanity.com/paper/2106.02797/) (2021)
- [Federated Learning over Wireless Networks: A Band-limited Coordinated Descent Approach](https://mlsanity.com/paper/2102.07972/) (2021)
- [Communication-Efficient Large-Scale Distributed Deep Learning: A Comprehensive Survey](https://mlsanity.com/paper/2404.06114/) (2024)
- [Towards Efficient Synchronous Federated Training: A Survey on System Optimization Strategies](https://mlsanity.com/paper/2109.03999/) (2021)
- [Evaluation and Optimization of Gradient Compression for Distributed Deep Learning](https://mlsanity.com/paper/2306.08881/) (2023)
- [Accelerating Distributed ML Training via Selective Synchronization](https://mlsanity.com/paper/2307.07950/) (2023)
- [Layered Randomized Quantization for Communication-Efficient and Privacy-Preserving Distributed Learning](https://mlsanity.com/paper/2312.07060/) (2023)
- [Beyond Throughput and Compression Ratios: Towards High End-to-end Utility of Gradient Compression](https://mlsanity.com/paper/2407.01378/) (2024)
- [Distributed Online Learning for Joint Regret with Communication Constraints](https://mlsanity.com/paper/2102.07521/) (2021)
- [FedSkel: Efficient Federated Learning on Heterogeneous Systems with Skeleton Gradients Update](https://mlsanity.com/paper/2108.09081/) (2021)
- [Collaborative Learning over Wireless Networks: An Introductory Overview](https://mlsanity.com/paper/2112.05559/) (2021)
- [Killing Two Birds with One Stone: Quantization Achieves Privacy in Distributed Learning](https://mlsanity.com/paper/2304.13545/) (2023)
- [Accelerating Distributed Deep Learning using Lossless Homomorphic Compression](https://mlsanity.com/paper/2402.07529/) (2024)
- [Bandwidth-Aware and Overlap-Weighted Compression for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2408.14736/) (2024)
- [FedCode: Communication-Efficient Federated Learning via Transferring Codebooks](https://mlsanity.com/paper/2311.09270/) (2023)
- [Exploring Scaling Laws for Local SGD in Large Language Model Training](https://mlsanity.com/paper/2409.13198/) (2024)
- [Peering Beyond the Gradient Veil with Distributed Auto Differentiation](https://mlsanity.com/paper/2102.09631/) (2021)
- [AET-SGD: Asynchronous Event-triggered Stochastic Gradient Descent](https://mlsanity.com/paper/2112.13935/) (2021)
- [Empirical Analysis on Top-k Gradient Sparsification for Distributed Deep Learning in a Supercomputing Environment](https://mlsanity.com/paper/2209.08497/) (2022)
- [CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexity](https://mlsanity.com/paper/2309.13307/) (2023)
- [Inclusive Data Representation in Federated Learning: A Novel Approach Integrating Textual and Visual Prompt](https://mlsanity.com/paper/2310.04455/) (2023)

## Abstract (arXiv)

Distributed synchronous stochastic gradient descent (S-SGD) has been widely used in training large-scale deep neural networks (DNNs), but it typically requires very high communication bandwidth between computational workers (e.g., GPUs) to exchange gradients iteratively. Recently, Top-k sparsification techniques have been proposed to reduce the volume of data to be exchanged among workers. Top-k sparsification can zero-out a significant portion of gradients without impacting the model convergence. However, the sparse gradients should be transferred with their irregular indices, which makes the sparse gradients aggregation difficult. Current methods that use AllGather to accumulate the sparse gradients have a communication complexity of O(kP), where P is the number of workers, which is inefficient on low bandwidth networks with a large number of workers. We observe that not all top-k gradients from P workers are needed for the model update, and therefore we propose a novel global Top-k (gTop-k) sparsification mechanism to address the problem. Specifically, we choose global top-k largest absolute values of gradients from P workers, instead of accumulating all local top-k gradients to update the model in each iteration. The gradient aggregation method based on gTop-k sparsification reduces the communication complexity from O(kP) to O(klog P). Through extensive experiments on different DNNs, we verify that gTop-k S-SGD has nearly consistent convergence performance with S-SGD, and it has only slight degradations on generalization performance. In terms of scaling efficiency, we evaluate gTop-k on a cluster with 32 GPU machines which are interconnected with 1 Gbps Ethernet. The experimental results show that our method achieves 2.7-12× higher scaling efficiency than S-SGD and 1.1-1.7× improvement than the existing Top-k S-SGD.