Rethinking gradient sparsification as total error minimization

2021/08/02 by Atal Narayan Sahu, Sahu, Atal Narayan, Aritra Dutta +9 · 19 citations
Computer Science · Engineering · Mathematics · #Algorithm #Applied mathematics #Bottleneck #Computer science #Convergence (economics) #Convex optimization #Distributed #FOS: Computer and information sciences #FOS: Mathematics #Geometry #Machine Learning (cs.LG) #Mathematical optimization #Mathematics #Optimization and Control (math.OC) #Parallel #Privacy-Preserving Technologies in Data #Quadratic growth #Rate of convergence #Regular polygon #Sparse and Compressive Sensing Techniques #Speedup #Stochastic Gradient Optimization Techniques #Telecommunications #and Cluster Computing (cs.DC) #cs.DC #cs.LG #math.OC

paper · pdf · doi:10.48550/arxiv.2108.00951

published in arXiv (Cornell University) (Cornell University) · 33 pages, 31 figures

arxiv created 2021/08/02 · openalex publication_date 2021/08/02 · arxiv updated 2021/08/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

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.

Citations

• Long Short-Term Memory
• Sparsified SGD with Memory
• Error Feedback Fixes SignSGD and other Gradient Compression Schemes
• Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism
• Optimal Gradient Compression for Distributed and Federated Learning
• Learning Multiple Layers of Features from Tiny Images

Cited by

• Efficient Covariance Estimation for Sparsified Functional Data
• Covenant-72B: Pre-Training a 72B LLM with Trustless Peers Over-the-Internet
• FedSRD: Sparsify-Reconstruct-Decompose for Communication-Efficient Federated Large Language Models Fine-Tuning
• Privacy Enhancement in Over-the-Air Federated Learning via Adaptive Receive Scaling
• Communication-Efficient Federated Learning with Adaptive Number of Participants
• EP-GAT: Energy-based Parallel Graph Attention Neural Network for Stock Trend Classification
• EcoLoRA: Communication-Efficient Federated Fine-Tuning of Large Language Models
• γ-FedHT: Stepsize-Aware Hard-Threshold Gradient Compression in Federated Learning

Related

• The Convergence of Sparsified Gradient Methods
• An Efficient Statistical-based Gradient Compression Technique for Distributed Training Systems
• MiCRO: Near-Zero Cost Gradient Sparsification for Scaling and Accelerating Distributed DNN Training
• Downlink Compression Improves TopK Sparsification
• Preserving Near-Optimal Gradient Sparsification Cost for Scalable Distributed Deep Learning