Communication-Efficient Network-Distributed Optimization with Differential-Coded Compressors
Communication-Efficient Network-Distributed Optimization with Differential-Coded Compressors
复制标题
DOI：
10.1109/infocom41043.2020.9155432
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Xin Zhang;Jia Liu;Zhengyuan Zhu-;E. Bentley
中科院分区：
文献类型：
--
作者：
Xin Zhang;Jia Liu;Zhengyuan Zhu-;E. Bentley
近年来，网络分布式优化由于其日益广泛的应用而引起了广泛的关注。然而，经典的去中心化梯度下降（DGD）算法对于大规模、高维的网络分布式优化问题存在通信效率低下的问题。为了解决这一挑战，已经提出了许多基于压缩ddd的算法。然而，现有的工作大多具有较高的复杂性，并且假定压缩机具有有限的噪声功率。为了克服这些限制，本文提出了一种新的差分编码压缩DGD （DC-DGD）算法。DC-DGD的主要特点包括：i) DC-DGD适用于一般的受信噪比约束的压缩机，打破了有界噪声功率的假设；ii)差分编码设计具有与原DGD算法相同的收敛速度；iii) DC-DGD由于具有自降噪效果，具有与原始DGD相同的低复杂度结构。此外，上述特性激发我们开发一种混合压缩方案，该方案提供了一种最小化通信成本的系统机制。最后，我们进行了大量的实验来验证所提出的DC-DGD和混合压缩机的有效性。
Network-distributed optimization has attracted sig-nificant attention in recent years due to its ever-increasing applications. However, the classic decentralized gradient descent (DGD) algorithm is communication-inefficient for large-scale and high-dimensional network-distributed optimization problems. To address this challenge, many compressed DGD-based algorithms have been proposed. However, most of the existing works have high complexity and assume compressors with bounded noise power. To overcome these limitations, in this paper, we propose a new differential-coded compressed DGD (DC-DGD) algorithm. The key features of DC-DGD include: i) DC-DGD works with general SNR-constrained compressors, relaxing the bounded noise power assumption; ii) The differential-coded design entails the same convergence rate as the original DGD algorithm; and iii) DC-DGD has the same low-complexity structure as the original DGD due to a self-noise-reduction effect. Moreover, the above features inspire us to develop a hybrid compression scheme that offers a systematic mechanism to minimize the communication cost. Finally, we conduct extensive experiments to verify the efficacy of the proposed DC-DGD and hybrid compressor.