Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911833222283264 |
|---|---|
| author | Song, Zhuoqing Shi, Lei Pu, Shi Yan, Ming |
| author_facet | Song, Zhuoqing Shi, Lei Pu, Shi Yan, Ming |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2106_07243 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks Song, Zhuoqing Shi, Lei Pu, Shi Yan, Ming Optimization and Control Distributed, Parallel, and Cluster Computing Machine Learning Multiagent Systems Signal Processing 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. |
| title | Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks |
| topic | Optimization and Control Distributed, Parallel, and Cluster Computing Machine Learning Multiagent Systems Signal Processing |
| url | https://arxiv.org/abs/2106.07243 |