Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergence
arXiv:2105.06697
Abstract
Information compression is essential to reduce communication cost in distributed optimization over peer-to-peer networks. This paper proposes a communication-efficient linearly convergent distributed (COLD) algorithm to solve strongly convex optimization problems. By compressing innovation vectors, which are the differences between decision vectors and their estimates, COLD is able to achieve linear convergence for a class of -contracted compressors. We explicitly quantify how the compression affects the convergence rate and show that COLD matches the same rate of its uncompressed version. To accommodate a wider class of compressors that includes the binary quantizer, we further design a novel dynamical scaling mechanism and obtain the linearly convergent Dyna-COLD. Importantly, our results strictly improve existing results for the quantized consensus problem. Numerical experiments demonstrate the advantages of both algorithms under different compressors.
arXiv comment14 pages
References in corpus (13)
- QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
- Consensus of Multi-Agent Systems with General Linear and Lipschitz Nonlinear Dynamics Using Distributed Adaptive Protocols
- 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
- An Exact Quantized Decentralized Gradient Descent Algorithm
- Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis
- On Maintaining Linear Convergence of Distributed Learning and Optimization under Limited Communication
- Quantized Decentralized Stochastic Learning over Directed Graphs
- Moniqua: Modulo Quantized Communication in Decentralized SGD
- Decentralized Stochastic Gradient Tracking for Non-convex Empirical Risk Minimization
- Quantized Distributed Gradient Tracking Algorithm with Linear Convergence in Directed Networks