Sparsified SGD with Memory
2018/09/20 by Sebastian U. Stich, Stich, Sebastian U., Jean-Baptiste Cordonnier +3 · 124 citations
Computer Science · Engineering · Mathematics · #68W15 #68W40 #90C06 #90C25 #Data Structures and Algorithms (cs.DS) #Distributed #Distributed Sensor Networks and Detection Algorithms #E.4 #F.2.1 #FOS: Computer and information sciences #G.1.6 #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Parallel #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #acm:68W15 #acm:68W40 #acm:90C06 #acm:90C25 #and Cluster Computing (cs.DC) #cs.DC #cs.DS #cs.LG #msc:68W15 #msc:68W40 #msc:90C06 #msc:90C25 #stat.ML
paper · pdf · doi:10.48550/arxiv.1809.07599
to appear at NIPS 2018
openalex publication_date 2018/09/20 · arxiv created 2018/11/28 · arxiv updated 2018/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Abstract
Huge scale machine learning problems are nowadays tackled by distributed optimization algorithms, i.e. algorithms that leverage the compute power of many devices for training. The communication overhead is a key bottleneck that hinders perfect scalability. Various recent works proposed to use quantization or sparsification techniques to reduce the amount of data that needs to be communicated, for instance by only sending the most significant entries of the stochastic gradient (top-k sparsification). Whilst such schemes showed very promising performance in practice, they have eluded theoretical analysis so far. In this work we analyze Stochastic Gradient Descent (SGD) with k-sparsification or compression (for instance top-k or random-k) and show that this scheme converges at the same rate as vanilla SGD when equipped with error compensation (keeping track of accumulated errors in memory). That is, communication can be reduced by a factor of the dimension of the problem (sometimes even more) whilst still converging at the same rate. We present numerical experiments to illustrate the theoretical findings and the better scalability for distributed applications.
Cited by
- OptiNIC: A Resilient and Tail-Optimal RDMA NIC for Distributed ML Workloads
- Communication Compression for Distributed Learning with Aggregate and Server-Guided Feedback
- Timely Parameter Updating in Over-the-Air Federated Learning
- ACE-Sync: An Adaptive Cloud-Edge Synchronization Framework for Communication-Efficient Large-Scale Distributed Model Training
- A Systems-Theoretic View on the Convergence of Algorithms under Disturbances
- DRIVE: One-bit Distributed Mean Estimation
- DP-CSGP: Differentially Private Stochastic Gradient Push with Compressed Communication
- CurvaDion: Curvature-Adaptive Distributed Orthonormalization
- Distributed Online Randomized Gradient-Free Optimization with Compressed Communication
- Efficient Covariance Estimation for Sparsified Functional Data
- On the Gradient Complexity of Private Optimization with Private Oracles
- An Efficient Gradient-Aware Error-Bounded Lossy Compressor for Federated Learning
- TT-Prune: Joint Model Pruning and Resource Allocation for Communication-efficient Time-triggered Federated Learning
- Gradient Projection onto Historical Descent Directions for Communication-Efficient Federated Learning
- An All-Reduce Compatible Top-K Compressor for Communication-Efficient Distributed Learning
- Lightweight Federated Learning in Mobile Edge Computing with Statistical and Device Heterogeneity Awareness
- SpeechLLM Meets Federated Learning for End-to-End ASR: English and Italian Case Studies
- Unbiased Gradient Low-Rank Projection
- SketchGuard: Scaling Byzantine-Robust Decentralized Federated Learning via Sketch-Based Screening
- Composite Optimization with Error Feedback: the Dual Averaging Approach
- FedMuon: Federated Learning with Bias-corrected LMO-based Optimization
- Reconciling Communication Compression and Byzantine-Robustness in Distributed Learning
- From PowerSGD to PowerSGD+: Low-Rank Gradient Compression for Distributed Optimization with Convergence Guarantees
- Experiments with Rich Regime Training for Deep Learning
- Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participation
- DPQuant: Efficient and Differentially-Private Model Training via Dynamic Quantization Scheduling
- Elastic Consistency: A General Consistency Model for Distributed Stochastic Gradient Descent
- Masked Training of Neural Networks with Partial Gradients
- Distributed Online Learning for Joint Regret with Communication Constraints
- Quantized Frank-Wolfe: Faster Optimization, Lower Communication, and Projection Free
- To Talk or to Work: Flexible Communication Compression for Energy Efficient Federated Learning over Heterogeneous Mobile Edge Devices
- Solon: Communication-efficient Byzantine-resilient Distributed Training via Redundant Gradients
- Norm-Constrained Flows and Sign-Based Optimization: Theory and Algorithms
- Permutation Compressors for Provably Faster Distributed Nonconvex Optimization
- A Field Guide to Federated Optimization
- Communication-Efficient Distributed Asynchronous ADMM
- MergeComp: A Compression Scheduler for Scalable Communication-Efficient Distributed Training
- Resource-Aware Aggregation and Sparsification in Heterogeneous Ensemble Federated Learning
- Decentralized Relaxed Smooth Optimization with Gradient Descent Methods
- Decentralized Composite Optimization with Compression
- HeteRo-Select: Informativeness as the Participation Driver in Heterogeneous Federated Learning
- Distributed Optimization and Learning for Automated Stepsize Selection with Finite Time Coordination
- Compressed Decentralized Momentum Stochastic Gradient Methods for Nonconvex Optimization
- Federated Learning with Feature Reconstruction for Vector Quantization based Semantic Communication
- Feature Reconstruction Aided Federated Learning for Image Semantic Communication
- Energy-Efficient Federated Learning for Edge Real-Time Vision via Joint Data, Computation, and Communication Design
- Communication-efficient distributed SGD with Sketching
- A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning
- QLSD: Quantised Langevin stochastic dynamics for Bayesian federated learning
- Toward Efficient Federated Learning in Multi-Channeled Mobile Edge Network with Layerd Gradient Compression
- Unified Optimal Analysis of the (Stochastic) Gradient Method
- Optimal Client Sampling for Federated Learning
- Distributed Fixed Point Methods with Compressed Iterates
- A Low Complexity Decentralized Neural Net with Centralized Equivalence using Layer-wise Learning
- ErrorCompensatedX: error compensation for variance reduced algorithms
- On the Convergence of SGD with Biased Gradients
- FedProf: Selective Federated Learning with Representation Profiling
- Federated Accelerated Stochastic Gradient Descent
- Taming Latency and Bandwidth: A Theoretical Framework and Adaptive Algorithm for Communication-Constrained Training
- Federated Learning over Wireless Networks: A Band-limited Coordinated Descent Approach
- Periodic Stochastic Gradient Descent with Momentum for Decentralized Training
- Linear Convergent Decentralized Optimization with Compression
- Greedy Low-Rank Gradient Compression for Distributed Learning with Convergence Guarantees
- Ampere: Communication-Efficient and High-Accuracy Split Federated Learning
- Beyond Communication Overhead: A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
- TinyProto: Communication-Efficient Federated Learning with Sparse Prototypes in Resource-Constrained Environments
- Communication Efficient, Differentially Private Distributed Optimization using Correlation-Aware Sketching
- Distributed Second Order Methods with Fast Rates and Compressed Communication
- New Bounds For Distributed Mean Estimation and Variance Reduction
- How to Securely Shuffle? A survey about Secure Shufflers for privacy-preserving computations
- Rethinking gradient sparsification as total error minimization
- Dynamic Model Pruning with Feedback
- Pufferfish: Communication-efficient Models At No Extra Cost
- Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
- Understanding Top-k Sparsification in Distributed Deep Learning
- 1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed
- Trustworthy Efficient Communication for Distributed Learning using LQ-SGD Algorithm
- AlphaDecay: Module-wise Weight Decay for Heavy-Tailed Balancing in LLMs
- Mobility-Aware Asynchronous Federated Learning with Dynamic Sparsification
- WOR and p's: Sketches for ℓp-Sampling Without Replacement
- Compressed Communication for Distributed Training: Adaptive Methods and System
- Local SGD With a Communication Overhead Depending Only on the Number of Workers
- Layer-wise Adaptive Gradient Sparsification for Distributed Deep Learning with Convergence Guarantees
- Tight analyses of first-order methods with error feedback
- On the Benefits of Multiple Gossip Steps in Communication-Constrained\n Decentralized Optimization
- Memory-Efficient Distributed Unlearning
- Computation- and Communication-Efficient Online FL for Resource-Constrained Aerial Vehicles
- Distributed Retraction-Free and Communication-Efficient Optimization on the Stiefel Manifold
- Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning
- Quantitative Error Feedback for Quantization Noise Reduction of Filtering over Graphs
- It Takes a Good Model to Train a Good Model: Generalized Gaussian Priors for Optimized LLMs
- On the Interaction of Noise, Compression Role, and Adaptivity under (L0, L1)-Smoothness: An SDE-based Approach
- Hyper-Sphere Quantization: Communication-Efficient SGD for Federated Learning
- COKE: Communication-Censored Decentralized Kernel Learning
- MuLoCo: Muon is a practical inner optimizer for DiLoCo
- Statistical Estimation and Inference via Local SGD in Federated Learning
- DeCAF: Decentralized Consensus-And-Factorization for Low-Rank Adaptation of Foundation Models
- TESSERACT: Gradient Flip Score to Secure Federated Learning Against Model Poisoning Attacks
- A flexible framework for communication-efficient machine learning: from HPC to IoT
- Escaping Saddle Points with Compressed SGD
- LocalKMeans: Convergence of Lloyd's Algorithm with Distributed Local Iterations
- FFT-based Dynamic Subspace Selection for Low-Rank Adaptive Optimization of Large Language Models
- Adaptive Serverless Learning
- A Distributed Synchronous SGD Algorithm with Global Top-k Sparsification for Low Bandwidth Networks
- PowerGossip: Practical Low-Rank Communication Compression in\n Decentralized Deep Learning
- Distributed Newton Can Communicate Less and Resist Byzantine Workers
- Incentivize Contribution and Learn Parameters Too: Federated Learning with Strategic Data Owners
- Communication-Efficient Federated Linear and Deep Generalized Canonical Correlation Analysis
- Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework
- Communication Efficient Federated Learning with Adaptive Quantization
- A Tight Theory of Error Feedback Algorithms in Distributed Optimization
- Communication-Efficient Wireless Federated Fine-Tuning for Large-Scale AI Models
- Distributed Sparse SGD with Majority Voting
- Communication-Censored Distributed Stochastic Gradient Descent
- Distributed Online Randomized Gradient-Free optimization with Compressed Communication
- Analysis of Asynchronous Federated Learning: Unraveling the Interactions between Gradient Compression, Delay, and Data Heterogeneity
- Distributed Optimization over Block-Cyclic Data
- Decentralized Learning with Lazy and Approximate Dual Gradients
- Distributed Optimization with Efficient Communication, Event-Triggered Solution Enhancement, and Operation Stopping
- CatFedAvg: Optimising Communication-efficiency and Classification Accuracy in Federated Learning
- FedFetch: Faster Federated Learning with Adaptive Downstream Prefetching
- Trends and Advancements in Deep Neural Network Communication
- Towards Scalable Distributed Training of Deep Learning on Public Cloud Clusters
- DG-FedReuse: Proxy-Gradient-Gated Cached-Update Reuse with Matched Sparse Uplink Accounting
Related