An All-Reduce Compatible Top-K Compressor for Communication-Efficient Distributed Learning

2025/10/30 by Chen, Chuyan, Ma, Chenyang, Li, Zhangxin +3
#Distributed #FOS: Computer and information sciences #Machine Learning (cs.LG) #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.2510.26709

Abstract

Communication remains a central bottleneck in large-scale distributed machine learning, and gradient sparsification has emerged as a promising strategy to alleviate this challenge. However, existing gradient compressors face notable limitations: Rand-K discards structural information and performs poorly in practice, while Top-K preserves informative entries but loses the contraction property and requires costly All-Gather operations. In this paper, we propose ARC-Top-K, an All-Reduce-Compatible Top-K compressor that aligns sparsity patterns across nodes using a lightweight sketch of the gradient, enabling index-free All-Reduce while preserving globally significant information. ARC-Top-K is provably contractive and, when combined with momentum error feedback (EF21M), achieves linear speedup and sharper convergence rates than the original EF21M under standard assumptions. Empirically, ARC-Top-K matches the accuracy of Top-K while reducing wall-clock training time by up to 60.7%, offering an efficient and scalable solution that combines the robustness of Rand-K with the strong performance of Top-K.

Citations

• Greedy Low-Rank Gradient Compression for Distributed Learning with Convergence Guarantees
• Subspace Optimization for Large Language Models with Convergence Guarantees
• GaLore: Memory-Efficient LLM Training by Gradient Low-Rank Projection
• Evaluation and Optimization of Gradient Compression for Distributed Deep Learning
• Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?
• Momentum Provably Improves Error Feedback!
• LLaMA: Open and Efficient Foundation Language Models
• Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression
• Training Compute-Optimal Large Language Models
• EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization
• Language Models are Few-Shot Learners
• Advances and Open Problems in Federated Learning
• Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer
• RoBERTa: A Robustly Optimized BERT Pretraining Approach
• Natural Compression for Distributed Deep Learning
• Edge Intelligence: Paving the Last Mile of Artificial Intelligence with Edge Computing
• Edge Intelligence: Paving the Last Mile of Artificial Intelligence With Edge Computing
• Error Feedback Fixes SignSGD and other Gradient Compression Schemes
• Federated Optimization in Heterogeneous Networks
• Sparsified SGD with Memory
• ATOMO: Communication-efficient Learning via Atomic Sparsification
• Gradient Sparsification for Communication-Efficient Distributed Optimization
• Federated Learning: Strategies for Improving Communication Efficiency
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Deep Residual Learning for Image Recognition
• The Emergence of Edge Computing

Related

• An Efficient Statistical-based Gradient Compression Technique for Distributed Training Systems
• Downlink Compression Improves TopK Sparsification
• Efficient Distributed Training through Gradient Compression with Sparsification and Quantization Techniques
• Near-Optimal Sparse Allreduce for Distributed Deep Learning
• Adaptive Compression for Communication-Efficient Distributed Training