Linear Convergent Decentralized Optimization with Compression

Abstract

Communication compression has become a key strategy to speed up distributed optimization. However, existing decentralized algorithms with compression mainly focus on compressing DGD-type algorithms. They are unsatisfactory in terms of convergence rate, stability, and the capability to handle heterogeneous data. Motivated by primal-dual algorithms, this paper proposes the first \underline{L}in\underline{EA}r convergent \underline{D}ecentralized algorithm with compression, LEAD. Our theory describes the coupled dynamics of the inexact primal and dual update as well as compression error, and we provide the first consensus error bound in such settings without assuming bounded gradients. Experiments on convex problems validate our theoretical analysis, and empirical study on deep neural nets shows that LEAD is applicable to non-convex problems.

arXiv commentICLR 2021 (International Conference on Learning Representations)

References in corpus (17)

• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• D-ADMM: A Communication-Efficient Distributed Algorithm For Separable Optimization
• A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
• Sparsified SGD with Memory
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• Communication Compression for Decentralized Training
• D${}^2$: Decentralized Training over Decentralized Data
• Error Feedback Fixes SignSGD and other Gradient Compression Schemes
• An Exact Quantized Decentralized Gradient Descent Algorithm
• DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
• Distributed Learning with Compressed Gradient Differences
• On Maintaining Linear Convergence of Distributed Learning and Optimization under Limited Communication
• Moniqua: Modulo Quantized Communication in Decentralized SGD
• Can Primal Methods Outperform Primal-dual Methods in Decentralized Dynamic Optimization?
• A Double Residual Compression Algorithm for Efficient Distributed Learning
• $\text{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression
• On linear convergence of two decentralized algorithms