Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
arXiv:2106.07243 · doi:10.1109/TSP.2022.3160238
Abstract
In this paper, we propose two communication efficient decentralized optimization algorithms over a general directed multi-agent network. The first algorithm, termed Compressed Push-Pull (CPP), combines the gradient tracking Push-Pull method with communication compression. We show that CPP is applicable to a general class of unbiased compression operators and achieves linear convergence rate for strongly convex and smooth objective functions. The second algorithm is a broadcast-like version of CPP (B-CPP), and it also achieves linear convergence rate under the same conditions on the objective functions. B-CPP can be applied in an asynchronous broadcast setting and further reduce communication costs compared to CPP. Numerical experiments complement the theoretical analysis and confirm the effectiveness of the proposed methods.
References in corpus (25)
- QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
- Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks
- Harnessing Smoothness to Accelerate Distributed Optimization
- A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
- A linear algorithm for optimization over directed graphs with geometric convergence
- Sparsified SGD with Memory
- Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
- ADD-OPT: Accelerated Distributed Directed Optimization
- Communication Compression for Decentralized Training
- Error Feedback Fixes SignSGD and other Gradient Compression Schemes
- An Exact Quantized Decentralized Gradient Descent Algorithm
- Distributed Recursive Least-Squares: Stability and Performance Analysis
- DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
- Distributed Learning with Compressed Gradient Differences
- Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
- ExtraPush for convex smooth decentralized optimization over directed networks
- On Biased Compression for Distributed Learning
- A Double Residual Compression Algorithm for Efficient Distributed Learning
- Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
- Optimal Algorithms for Distributed Optimization
- : Decentralization Meets Error-Compensated Compression
- Fully Asynchronous Distributed Optimization with Linear Convergence in Directed Networks
- On Communication Compression for Distributed Optimization on Heterogeneous Data
- Quantized Distributed Gradient Tracking Algorithm with Linear Convergence in Directed Networks
- Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergence