Decentralized Composite Optimization with Compression
arXiv:2108.04448
Abstract
Decentralized optimization and communication compression have exhibited their great potential in accelerating distributed machine learning by mitigating the communication bottleneck in practice. While existing decentralized algorithms with communication compression mostly focus on the problems with only smooth components, we study the decentralized stochastic composite optimization problem with a potentially non-smooth component. A \underline{Prox}imal gradient \underline{L}in\underline{EA}r convergent \underline{D}ecentralized algorithm with compression, Prox-LEAD, is proposed with rigorous theoretical analyses in the general stochastic setting and the finite-sum setting. Our theorems indicate that Prox-LEAD works with arbitrary compression precision, and it tremendously reduces the communication cost almost for free. The superiorities of the proposed algorithms are demonstrated through the comparison with state-of-the-art algorithms in terms of convergence complexities and numerical experiments. Our algorithmic framework also generally enlightens the compressed communication on other primal-dual algorithms by reducing the impact of inexact iterations, which might be of independent interest.
References in corpus (21)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- 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
- Optimal algorithms for smooth and strongly convex distributed optimization in networks
- Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
- Communication Compression for Decentralized Training
- D: Decentralized Training over Decentralized Data
- Error Feedback Fixes SignSGD and other Gradient Compression Schemes
- DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
- An Exact Quantized Decentralized Gradient Descent Algorithm
- DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
- Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
- Distributed Learning with Compressed Gradient Differences
- Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis
- On Maintaining Linear Convergence of Distributed Learning and Optimization under Limited Communication
- Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
- : Decentralization Meets Error-Compensated Compression
- Dual-Free Stochastic Decentralized Optimization with Variance Reduction
- Quantized Distributed Gradient Tracking Algorithm with Linear Convergence in Directed Networks