DEED: A General Quantization Scheme for Communication Efficiency in Bits
This addresses communication bottlenecks in distributed and federated learning, offering incremental improvements over existing quantization methods.
The paper tackles communication inefficiency in distributed optimization by proposing DEED, a general quantization scheme that reduces the total number of bits required while maintaining convergence rates, achieving complexities such as $ ilde{O}( \sqrt{\kappa} \log 1/\varepsilon)$ in large-memory settings.
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κ \log 1/ε)$, where $\tilde{O}$ hides numerical constant and $\log κ$ factors. In the frequent-communication small-memory setting, DEED combined with SGD only requires $\tilde{O}( κ\log 1/ε)$ 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.