Linear Convergent Decentralized Optimization with Compression
Linear Convergent Decentralized Optimization with Compression
复制标题
DOI：
--
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Xiaorui Liu;Yao Li;Rongrong Wang;Jiliang Tang;Ming Yan
中科院分区：
文献类型：
--
作者：
Xiaorui Liu;Yao Li;Rongrong Wang;Jiliang Tang;Ming Yan
通信压缩已被广泛采用来加速大规模分布式优化。然而，现有的大多数具有压缩功能的去中心化算法在收敛速度和稳定性方面都不尽如人意。在本文中，我们描述了算法设计中的两个关键障碍——数据异构性和压缩误差。我们明确克服这些障碍的尝试催生了一种名为 LEAD 的新型去中心化算法。该算法是\underline{L}in\underline{EA}r中第一个具有通信压缩功能的收敛\underline{D}去中心化算法。我们的理论描述了不准确的模型传播和优化过程的耦合动力学。我们还提供了第一个共识误差界限，而不假设有界梯度。实证实验验证了我们的理论分析，并表明所提出的算法实现了最先进的计算和通信效率。
Communication compression has been extensively adopted to speed up large-scale distributed optimization. However, most existing decentralized algorithms with compression are unsatisfactory in terms of convergence rate and stability. In this paper, we delineate two key obstacles in the algorithm design -- data heterogeneity and compression error. Our attempt to explicitly overcome these obstacles leads to a novel decentralized algorithm named LEAD. This algorithm is the first \underline{L}in\underline{EA}r convergent \underline{D}ecentralized algorithm with communication compression. Our theory describes the coupled dynamics of the inaccurate model propagation and optimization process. We also provide the first consensus error bound without assuming bounded gradients. Empirical experiments validate our theoretical analysis and show that the proposed algorithm achieves state-of-the-art computation and communication efficiency.