Communication-efficient distributed SGD with Sketching

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 $\mathcal{O}(d)$ or $\mathcal{O}(W)$ to $\mathcal{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.

19 pages, 6 figures, published at NeurIPS 2019

References in corpus (12)

• Federated Learning: Strategies for Improving Communication Efficiency
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Large Batch Training of Convolutional Networks
• Sparsified SGD with Memory
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• Measuring the Effects of Data Parallelism on Neural Network Training
• The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
• On the Computational Inefficiency of Large Batch Sizes for Stochastic Gradient Descent

Cited by in corpus (8)

• From Distributed Machine Learning to Federated Learning: A Survey
• DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs
• DRIVE: One-bit Distributed Mean Estimation
• DEFT: Exploiting Gradient Norm Difference between Model Layers for Scalable Gradient Sparsification
• Trends and Advancements in Deep Neural Network Communication
• Fast Machine Learning with Byzantine Workers and Servers
• Federated Learning over Wireless Networks: A Band-limited Coordinated Descent Approach
• Communication-Compressed Adaptive Gradient Method for Distributed Nonconvex Optimization