Communication-Efficient Network-Distributed Optimization with Differential-Coded Compressors

Thumbnail Image
Date
2019-01-01
Authors
Zhang, Xin
Liu, Jia
Zhu, Zhengyuan
Bentley, Elizabeth
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Person
Zhu, Zhengyuan
Director of the Center for Survey Statistics and Methodology and Professor
Research Projects
Organizational Units
Organizational Unit
Organizational Unit
Statistics
As leaders in statistical research, collaboration, and education, the Department of Statistics at Iowa State University offers students an education like no other. We are committed to our mission of developing and applying statistical methods, and proud of our award-winning students and faculty.
Journal Issue
Is Version Of
Versions
Series
Department
Computer ScienceStatistics
Abstract

Network-distributed optimization has attracted significant 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 {\em 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.

Comments

This is a pre-print of the proceeding Zhang, Xin, Jia Liu, Zhengyuan Zhu, and Elizabeth S. Bentley. "Communication-Efficient Network-Distributed Optimization with Differential-Coded Compressors." arXiv preprint arXiv:1912.03208 (2019).

Description
Keywords
Citation
DOI
Source
Copyright