Communication-efficient distributed SGD with Sketching

2019/03/12 by Nikita Ivkin, Daniel Rothchild, Ivkin, Nikita +9 · 9 citations
Computer Science · Mathematics · #Advanced Neural Network Applications #Distributed #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Parallel #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC) #cs.DC #cs.LG #math.OC #stat.ML

paper · pdf · doi:10.48550/arxiv.1903.04488

19 pages, 6 figures, published at NeurIPS 2019

openalex publication_date 2019/03/12 · arxiv created 2020/01/23 · arxiv updated 2020/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Large-scale distributed training of neural networks is often limited by network bandwidth, wherein the communication time overwhelms the local computation time. Motivated by the success of sketching methods in sub-linear/streaming algorithms, we introduce Sketched SGD, an algorithm for carrying out distributed SGD by communicating sketches instead of full gradients. We show that Sketched SGD has favorable convergence rates on several classes of functions. When considering all communication -- both of gradients and of updated model weights -- Sketched SGD reduces the amount of communication required compared to other gradient compression methods from O(d) or O(W) to O(log d), where d is the number of model parameters and W is the number of workers participating in training. We run experiments on a transformer model, an LSTM, and a residual network, demonstrating up to a 40x reduction in total communication cost with no loss in final model performance. We also show experimentally that Sketched SGD scales to at least 256 workers without increasing communication cost or degrading model performance.

Citations

• Finding frequent items in data streams
• Finding repeated elements
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Sparsified SGD with Memory
• On the Computational Inefficiency of Large Batch Sizes for Stochastic Gradient Descent
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• Learning Multiple Layers of Features from Tiny Images

Cited by

• FedMPDD: Communication-Efficient Federated Learning with Privacy Preservation Attributes via Projected Directional Derivative
• Heterogeneity-Oblivious Robust Federated Learning
• Federated Learning over Wireless Networks: A Band-limited Coordinated Descent Approach
• Tight analyses of first-order methods with error feedback
• Lego Sketch: A Scalable Memory-augmented Neural Network for Sketching Data Streams
• Sharp Gaussian approximations for Decentralized Federated Learning
• A Tight Theory of Error Feedback Algorithms in Distributed Optimization
• TrojanDam: Detection-Free Backdoor Defense in Federated Learning through Proactive Model Robustification utilizing OOD Data
• Trends and Advancements in Deep Neural Network Communication

Related

• A Distributed SGD Algorithm with Global Sketching for Deep Learning Training Acceleration
• Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedback
• O(1) Communication for Distributed SGD through Two-Level Gradient Averaging
• Sparse Communication for Training Deep Networks
• Efficient Communications in Training Large Scale Neural Networks