Distributed Learning with Compressed Gradient Differences

Abstract

Training large machine learning models requires a distributed computing approach, with communication of the model updates being the bottleneck. For this reason, several methods based on the compression (e.g., sparsification and/or quantization) of updates were recently proposed, including QSGD (Alistarh et al., 2017), TernGrad (Wen et al., 2017), SignSGD (Bernstein et al., 2018), and DQGD (Khirirat et al., 2018). However, none of these methods are able to learn the gradients, which renders them incapable of converging to the true optimum in the batch mode. In this work we propose a new distributed learning method -- DIANA -- which resolves this issue via compression of gradient differences. We perform a theoretical analysis in the strongly convex and nonconvex settings and show that our rates are superior to existing rates. We also provide theory to support non-smooth regularizers study the difference between quantization schemes. Our analysis of block-quantization and differences between ${\ell }_2$ and ${\ell }_{\infty }$ quantization closes the gaps in theory and practice. Finally, by applying our analysis technique to TernGrad, we establish the first convergence rate for this method.

59 pages; Changes in V3: writing, presentation, and numerical experiments

References in corpus (9)

• Federated Learning: Strategies for Improving Communication Efficiency
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• Communication-Efficient Distributed Dual Coordinate Ascent
• AIDE: Fast and Communication Efficient Distributed Optimization
• Distributed learning with compressed gradients
• Efficient Distributed Hessian Free Algorithm for Large-scale Empirical Risk Minimization via Accumulating Sample Strategy
• Randomized Distributed Mean Estimation: Accuracy vs Communication
• An Accelerated Communication-Efficient Primal-Dual Optimization Framework for Structured Machine Learning

Cited by in corpus (58)

• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Scaling Distributed Machine Learning with In-Network Aggregation
• Federated Learning Based on Dynamic Regularization
• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Natural Compression for Distributed Deep Learning
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• On Biased Compression for Distributed Learning
• EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• Optimal Gradient Compression for Distributed and Federated Learning
• Fed-ensemble: Improving Generalization through Model Ensembling in Federated Learning
• 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
• Recent theoretical advances in decentralized distributed convex optimization
• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• Federated Accelerated Stochastic Gradient Descent
• A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning
• A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent
• BROADCAST: Reducing Both Stochastic and Compression Noise to Robustify Communication-Efficient Federated Learning
• MARINA: Faster Non-Convex Distributed Learning with Compression
• Gradient Descent with Compressed Iterates
• Linear Convergent Decentralized Optimization with Compression
• FedNL: Making Newton-Type Methods Applicable to Federated Learning
• Distributed Second Order Methods with Fast Rates and Compressed Communication
• Stochastic Sign Descent Methods: New Algorithms and Better Theory
• Local SGD: Unified Theory and New Efficient Methods
• On Communication Compression for Distributed Optimization on Heterogeneous Data
• FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning
• Error Compensated Distributed SGD Can Be Accelerated
• Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees
• CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression
• Distributed Fixed Point Methods with Compressed Iterates
• Activations and Gradients Compression for Model-Parallel Training
• 99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it
• Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation
• Is Network the Bottleneck of Distributed Training?
• A Stochastic Derivative Free Optimization Method with Momentum
• Synthetic data shuffling accelerates the convergence of federated learning under data heterogeneity
• New Bounds For Distributed Mean Estimation and Variance Reduction
• Decentralized Composite Optimization with Compression
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• Basis Matters: Better Communication-Efficient Second Order Methods for Federated Learning
• Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization
• Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization
• ErrorCompensatedX: error compensation for variance reduced algorithms
• About some works of Boris Polyak on convergence of gradient methods and their development
• DEED: A General Quantization Scheme for Communication Efficiency in Bits
• Error Compensated Loopless SVRG, Quartz, and SDCA for Distributed Optimization
• Slashing Communication Traffic in Federated Learning by Transmitting Clustered Model Updates
• Local Methods with Adaptivity via Scaling
• FLIX: A Simple and Communication-Efficient Alternative to Local Methods in Federated Learning
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• Det-CGD: Compressed Gradient Descent with Matrix Stepsizes for Non-Convex Optimization
• Secure Distributed Training at Scale
• MURANA: A Generic Framework for Stochastic Variance-Reduced Optimization