Understanding Top-k Sparsification in Distributed Deep Learning

Abstract

Distributed stochastic gradient descent (SGD) algorithms are widely deployed in training large-scale deep learning models, while the communication overhead among workers becomes the new system bottleneck. Recently proposed gradient sparsification techniques, especially Top-$k$ sparsification with error compensation (TopK-SGD), can significantly reduce the communication traffic without an obvious impact on the model accuracy. Some theoretical studies have been carried out to analyze the convergence property of TopK-SGD. However, existing studies do not dive into the details of Top-$k$ operator in gradient sparsification and use relaxed bounds (e.g., exact bound of Random-$k$) for analysis; hence the derived results cannot well describe the real convergence performance of TopK-SGD. To this end, we first study the gradient distributions of TopK-SGD during the training process through extensive experiments. We then theoretically derive a tighter bound for the Top-$k$ operator. Finally, we exploit the property of gradient distribution to propose an approximate top-$k$ selection algorithm, which is computing-efficient for GPUs, to improve the scaling efficiency of TopK-SGD by significantly reducing the computing overhead. Codes are available at: \url{https://github.com/hclhkbu/GaussianK-SGD}.

14 pages

References in corpus (10)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Horovod: fast and easy distributed deep learning in TensorFlow
• Highly Scalable Deep Learning Training System with Mixed-Precision: Training ImageNet in Four Minutes
• Sparsified SGD with Memory
• Error Feedback Fixes SignSGD and other Gradient Compression Schemes
• DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
• AdaComp : Adaptive Residual Gradient Compression for Data-Parallel Distributed Training
• Optimizing Network Performance for Distributed DNN Training on GPU Clusters: ImageNet/AlexNet Training in 1.5 Minutes
• RedSync : Reducing Synchronization Traffic for Distributed Deep Learning

Cited by in corpus (22)

• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• FetchSGD: Communication-Efficient Federated Learning with Sketching
• Near-Optimal Sparse Allreduce for Distributed Deep Learning
• An Efficient Statistical-based Gradient Compression Technique for Distributed Training Systems
• Towards Scalable Distributed Training of Deep Learning on Public Cloud Clusters
• Rethinking gradient sparsification as total error minimization
• On the Utility of Gradient Compression in Distributed Training Systems
• Bayesian Federated Learning over Wireless Networks
• Federated Learning for Energy Constrained IoT devices: A systematic mapping study
• Accordion: Adaptive Gradient Communication via Critical Learning Regime Identification
• Layer-wise Adaptive Gradient Sparsification for Distributed Deep Learning with Convergence Guarantees
• A Carbon Tracking Model for Federated Learning: Impact of Quantization and Sparsification
• AC/DC: Alternating Compressed/DeCompressed Training of Deep Neural Networks
• Communication-Efficient Decentralized Learning with Sparsification and Adaptive Peer Selection
• GOBO: Quantizing Attention-Based NLP Models for Low Latency and Energy Efficient Inference
• Channel-driven Decentralized Bayesian Federated Learning for Trustworthy Decision Making in D2D Networks
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent
• GraVAC: Adaptive Compression for Communication-Efficient Distributed DL Training
• Compressing gradients by exploiting temporal correlation in momentum-SGD
• An Empirical Study on Compressed Decentralized Stochastic Gradient Algorithms with Overparameterized Models
• Rate distortion comparison of a few gradient quantizers
• Speeding-Up Back-Propagation in DNN: Approximate Outer Product with Memory