DEED: A General Quantization Scheme for Communication Efficiency in Bits

Abstract

In distributed optimization, a popular technique to reduce communication is quantization. In this paper, we provide a general analysis framework for inexact gradient descent that is applicable to quantization schemes. We also propose a quantization scheme Double Encoding and Error Diminishing (DEED). DEED can achieve small communication complexity in three settings: frequent-communication large-memory, frequent-communication small-memory, and infrequent-communication (e.g. federated learning). More specifically, in the frequent-communication large-memory setting, DEED can be easily combined with Nesterov's method, so that the total number of bits required is $\tilde{O}(\sqrt{\kappa }\log 1/\epsilon )$, where $\tilde{O}$ hides numerical constant and $\log \kappa$ factors. In the frequent-communication small-memory setting, DEED combined with SGD only requires $\tilde{O}(\kappa \log 1/\epsilon )$ number of bits in the interpolation regime. In the infrequent communication setting, DEED combined with Federated averaging requires a smaller total number of bits than Federated Averaging. All these algorithms converge at the same rate as their non-quantized versions, while using a smaller number of bits.

References in corpus (14)

• TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• MXNet: A Flexible and Efficient Machine Learning Library for Heterogeneous Distributed Systems
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Local SGD Converges Fast and Communicates Little
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
• Distributed Learning with Compressed Gradient Differences
• Yet Another Accelerated SGD: ResNet-50 Training on ImageNet in 74.7 seconds
• First Analysis of Local GD on Heterogeneous Data
• Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
• Accelerating SGD with momentum for over-parameterized learning
• Distributed learning with compressed gradients

Cited by in corpus (1)

• CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression