Sparsified SGD with Memory

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.

to appear at NIPS 2018

Cited by in corpus (139)

• On the Convergence of FedAvg on Non-IID Data
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• From Distributed Machine Learning to Federated Learning: A Survey
• Over-the-Air Federated Learning from Heterogeneous Data
• Local SGD Converges Fast and Communicates Little
• Federated Learning: A Signal Processing Perspective
• A Field Guide to Federated Optimization
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Federated Learning in Mobile Edge Networks: A Comprehensive Survey
• PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization
• Edge Intelligence: Paving the Last Mile of Artificial Intelligence with Edge Computing
• Optimal Client Sampling for Federated Learning
• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• Dynamic Model Pruning with Feedback
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Joint Optimization of Communications and Federated Learning Over the Air
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• On Maintaining Linear Convergence of Distributed Learning and Optimization under Limited Communication
• Understanding Top-k Sparsification in Distributed Deep Learning
• Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedback
• Communication optimization strategies for distributed deep neural network training: A survey
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• FetchSGD: Communication-Efficient Federated Learning with Sketching
• FedLab: A Flexible Federated Learning Framework
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• A Federated Learning Framework for Healthcare IoT devices
• On-Device Machine Learning: An Algorithms and Learning Theory Perspective
• EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• Moniqua: Modulo Quantized Communication in Decentralized SGD
• Hyper-Sphere Quantization: Communication-Efficient SGD for Federated Learning
• An Efficient Statistical-based Gradient Compression Technique for Distributed Training Systems
• Decentralized Deep Learning with Arbitrary Communication Compression
• A Double Residual Compression Algorithm for Efficient Distributed Learning
• Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
• Distributed Learning in Wireless Networks: Recent Progress and Future Challenges
• Federated Learning with Compression: Unified Analysis and Sharp Guarantees
• Towards Scalable Distributed Training of Deep Learning on Public Cloud Clusters
• $\text{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression
• Federated Accelerated Stochastic Gradient Descent
• A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning
• Rethinking gradient sparsification as total error minimization
• On the Utility of Gradient Compression in Distributed Training Systems
• Stragglers Are Not Disaster: A Hybrid Federated Learning Algorithm with Delayed Gradients
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks
• Communication-efficient distributed SGD with Sketching
• Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning
• 1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed
• Sparse Communication for Training Deep Networks
• On the Convergence of SGD with Biased Gradients
• LASG: Lazily Aggregated Stochastic Gradients for Communication-Efficient Distributed Learning
• Layer-wise Adaptive Gradient Sparsification for Distributed Deep Learning with Convergence Guarantees
• rTop-k: A Statistical Estimation Approach to Distributed SGD
• Gradient Descent with Compressed Iterates
• FedNL: Making Newton-Type Methods Applicable to Federated Learning
• To Talk or to Work: Flexible Communication Compression for Energy Efficient Federated Learning over Heterogeneous Mobile Edge Devices
• Linear Convergent Decentralized Optimization with Compression
• Local SGD With a Communication Overhead Depending Only on the Number of Workers
• Quantized Frank-Wolfe: Faster Optimization, Lower Communication, and Projection Free
• Distributed Second Order Methods with Fast Rates and Compressed Communication
• Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs
• FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching
• Communication Efficient Distributed Learning with Censored, Quantized, and Generalized Group ADMM
• Faster Non-Convex Federated Learning via Global and Local Momentum
• DRIVE: One-bit Distributed Mean Estimation
• Federated Learning over Wireless Device-to-Device Networks: Algorithms and Convergence Analysis
• On Communication Compression for Distributed Optimization on Heterogeneous Data
• A Distributed Synchronous SGD Algorithm with Global Top-$k$ Sparsification for Low Bandwidth Networks
• Periodic Stochastic Gradient Descent with Momentum for Decentralized Training
• Large-Scale Deep Learning Optimizations: A Comprehensive Survey
• Wyner-Ziv Gradient Compression for Federated Learning
• Error Compensated Distributed SGD Can Be Accelerated
• Communication-efficient SGD: From Local SGD to One-Shot Averaging
• PowerGossip: Practical Low-Rank Communication Compression in Decentralized Deep Learning
• Distributed Optimization over Block-Cyclic Data
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent
• Elastic Consistency: A General Consistency Model for Distributed Stochastic Gradient Descent
• COKE: Communication-Censored Decentralized Kernel Learning
• CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression
• Communication-Efficient Distributed SGD with Error-Feedback, Revisited
• Distributed Fixed Point Methods with Compressed Iterates
• On the Benefits of Multiple Gossip Steps in Communication-Constrained Decentralized Optimization
• Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergence
• Pufferfish: Communication-efficient Models At No Extra Cost
• On the Convergence of Decentralized Adaptive Gradient Methods
• Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation
• Distributed Newton Can Communicate Less and Resist Byzantine Workers
• LocalNewton: Reducing Communication Bottleneck for Distributed Learning
• New Bounds For Distributed Mean Estimation and Variance Reduction
• Decentralized Composite Optimization with Compression
• Trends and Advancements in Deep Neural Network Communication
• A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework
• Faster Distributed Deep Net Training: Computation and Communication Decoupled Stochastic Gradient Descent
• Adaptive Serverless Learning
• APMSqueeze: A Communication Efficient Adam-Preconditioned Momentum SGD Algorithm
• Optimal Gradient Quantization Condition for Communication-Efficient Distributed Training
• Decentralized Optimization On Time-Varying Directed Graphs Under Communication Constraints
• Variance Reduction with Sparse Gradients
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• 1-bit LAMB: Communication Efficient Large-Scale Large-Batch Training with LAMB's Convergence Speed
• Compressing gradients by exploiting temporal correlation in momentum-SGD
• A flexible framework for communication-efficient machine learning: from HPC to IoT
• QLSD: Quantised Langevin stochastic dynamics for Bayesian federated learning
• 1-Bit Compressive Sensing for Efficient Federated Learning Over the Air
• Federated Learning over Wireless Networks: A Band-limited Coordinated Descent Approach
• Trajectory Normalized Gradients for Distributed Optimization
• A Low Complexity Decentralized Neural Net with Centralized Equivalence using Layer-wise Learning
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization
• On Faster Convergence of Scaled Sign Gradient Descent
• ErrorCompensatedX: error compensation for variance reduced algorithms
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing
• Error Compensated Loopless SVRG, Quartz, and SDCA for Distributed Optimization
• Solon: Communication-efficient Byzantine-resilient Distributed Training via Redundant Gradients
• Communication-Censored Distributed Stochastic Gradient Descent
• Distributed Sparse SGD with Majority Voting
• CADA: Communication-Adaptive Distributed Adam
• On the Convergence of Memory-Based Distributed SGD
• Experiments with Rich Regime Training for Deep Learning
• Communication Efficient Federated Learning with Adaptive Quantization
• Decentralized Learning with Lazy and Approximate Dual Gradients
• WOR and $p$'s: Sketches for ${\ell }_p$-Sampling Without Replacement
• CSER: Communication-efficient SGD with Error Reset
• FedProf: Selective Federated Learning with Representation Profiling
• Statistical Estimation and Inference via Local SGD in Federated Learning
• Communication-Compressed Adaptive Gradient Method for Distributed Nonconvex Optimization
• Compressed Communication for Distributed Training: Adaptive Methods and System
• Sparsification as a Remedy for Staleness in Distributed Asynchronous SGD
• Quantizing data for distributed learning
• Toward Efficient Federated Learning in Multi-Channeled Mobile Edge Network with Layerd Gradient Compression
• Scalable Projection-Free Optimization
• Masked Training of Neural Networks with Partial Gradients
• TESSERACT: Gradient Flip Score to Secure Federated Learning Against Model Poisoning Attacks
• Communication Efficient Generalized Tensor Factorization for Decentralized Healthcare Networks
• Communication-Efficient Federated Linear and Deep Generalized Canonical Correlation Analysis
• CatFedAvg: Optimising Communication-efficiency and Classification Accuracy in Federated Learning
• MergeComp: A Compression Scheduler for Scalable Communication-Efficient Distributed Training
• Escaping Saddle Points with Compressed SGD
• Rate distortion comparison of a few gradient quantizers