论文标题
契据：一般量化方案，用于沟通效率
DEED: A General Quantization Scheme for Communication Efficiency in Bits
论文作者
论文摘要
在分布式优化中，减少通信的流行技术是量化。在本文中，我们为适用于量化方案的不精确梯度下降提供了一个通用分析框架。我们还提出了一个量化方案双重编码和错误减少（契约）。契据可以在三种环境中实现较小的沟通复杂性：频繁的通信大型记忆，频繁的沟通小型记忆和不频繁的交流（例如，联邦学习）。更具体地说，在频繁通信的大型内存设置中，契约可以很容易地与Nesterov的方法结合在一起，因此所需的位总数为$ \ tilde {o}（\sqrtκ\ log 1/ε）$，其中$ \ tilde {o} $ \ tilde {o} $ hide {o} $ hiderical常数和$ \ log log log bog;在频繁通信的小型内存设置中，与SGD相结合的契约仅需要$ \ tilde {o}（κ\ log 1/ε）$在插值制度中的位数。在不频繁的沟通环境中，契据与联邦平均相结合的契约需要比联邦平均值少。所有这些算法以与非量化版本相同的速率收敛，同时使用较少的位。
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.
