Rethinking gradient sparsification as total error minimization

Abstract

Gradient compression is a widely-established remedy to tackle the communication bottleneck in distributed training of large deep neural networks (DNNs). Under the error-feedback framework, Top-$k$ sparsification, sometimes with $k$ as little as $0.1\%$ of the gradient size, enables training to the same model quality as the uncompressed case for a similar iteration count. From the optimization perspective, we find that Top-$k$ is the communication-optimal sparsifier given a per-iteration $k$ element budget. We argue that to further the benefits of gradient sparsification, especially for DNNs, a different perspective is necessary -- one that moves from per-iteration optimality to consider optimality for the entire training. We identify that the total error -- the sum of the compression errors for all iterations -- encapsulates sparsification throughout training. Then, we propose a communication complexity model that minimizes the total error under a communication budget for the entire training. We find that the hard-threshold sparsifier, a variant of the Top-$k$ sparsifier with $k$ determined by a constant hard-threshold, is the optimal sparsifier for this model. Motivated by this, we provide convex and non-convex convergence analyses for the hard-threshold sparsifier with error-feedback. Unlike with Top-$k$ sparsifier, we show that hard-threshold has the same asymptotic convergence and linear speedup property as SGD in the convex case and has no impact on the data-heterogeneity in the non-convex case. Our diverse experiments on various DNNs and a logistic regression model demonstrated that the hard-threshold sparsifier is more communication-efficient than Top-$k$.

arXiv comment33 pages, 31 figures

References in corpus (11)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism
• Sparsified SGD with Memory
• Error Feedback Fixes SignSGD and other Gradient Compression Schemes
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Understanding Top-k Sparsification in Distributed Deep Learning
• On Biased Compression for Distributed Learning
• Optimal Gradient Compression for Distributed and Federated Learning
• Accordion: Adaptive Gradient Communication via Critical Learning Regime Identification
• Compressed Communication for Distributed Training: Adaptive Methods and System

Cited by in corpus (2)

• DEFT: Exploiting Gradient Norm Difference between Model Layers for Scalable Gradient Sparsification
• Sparse Incremental Aggregation in Multi-Hop Federated Learning