Innovation compression for communication-efficient distributed optimization with linear convergence
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,...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/170700 |
| _version_ | 1826120735686393856 |
|---|---|
| author | Zhang, Jiaqi You, Keyou Xie, Lihua |
| author2 | School of Electrical and Electronic Engineering |
| author_facet | School of Electrical and Electronic Engineering Zhang, Jiaqi You, Keyou Xie, Lihua |
| author_sort | Zhang, Jiaqi |
| collection | NTU |
| description | 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 achieves linear convergence for a class of δ-contracted compressors, and we explicitly quantify how the compression affects the convergence rate. Interestingly, our results strictly improve existing results for the quantized consensus problem. Numerical experiments demonstrate the advantages of COLD under different compressors. |
| first_indexed | 2024-10-01T05:21:19Z |
| format | Journal Article |
| id | ntu-10356/170700 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T05:21:19Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | ntu-10356/1707002023-09-26T06:01:44Z Innovation compression for communication-efficient distributed optimization with linear convergence Zhang, Jiaqi You, Keyou Xie, Lihua School of Electrical and Electronic Engineering Engineering::Electrical and electronic engineering Distributed Optimization Linear Convergence 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 achieves linear convergence for a class of δ-contracted compressors, and we explicitly quantify how the compression affects the convergence rate. Interestingly, our results strictly improve existing results for the quantized consensus problem. Numerical experiments demonstrate the advantages of COLD under different compressors. This work was supported by Technology and Innovation Major Project of the Ministry of Science and Technology of China under Grant 2020AAA0108403, the National Natural Science Foundation of China under Grant no. 62033006 and Tsinghua University Initiative Scientific Research Program. 2023-09-26T03:14:59Z 2023-09-26T03:14:59Z 2023 Journal Article Zhang, J., You, K. & Xie, L. (2023). Innovation compression for communication-efficient distributed optimization with linear convergence. IEEE Transactions On Automatic Control, 1-8. https://dx.doi.org/10.1109/TAC.2023.3241771 0018-9286 https://hdl.handle.net/10356/170700 10.1109/TAC.2023.3241771 2-s2.0-85148447851 1 8 en IEEE Transactions on Automatic Control © 2023 IEEE. All rights reserved. |
| spellingShingle | Engineering::Electrical and electronic engineering Distributed Optimization Linear Convergence Zhang, Jiaqi You, Keyou Xie, Lihua Innovation compression for communication-efficient distributed optimization with linear convergence |
| title | Innovation compression for communication-efficient distributed optimization with linear convergence |
| title_full | Innovation compression for communication-efficient distributed optimization with linear convergence |
| title_fullStr | Innovation compression for communication-efficient distributed optimization with linear convergence |
| title_full_unstemmed | Innovation compression for communication-efficient distributed optimization with linear convergence |
| title_short | Innovation compression for communication-efficient distributed optimization with linear convergence |
| title_sort | innovation compression for communication efficient distributed optimization with linear convergence |
| topic | Engineering::Electrical and electronic engineering Distributed Optimization Linear Convergence |
| url | https://hdl.handle.net/10356/170700 |
| work_keys_str_mv | AT zhangjiaqi innovationcompressionforcommunicationefficientdistributedoptimizationwithlinearconvergence AT youkeyou innovationcompressionforcommunicationefficientdistributedoptimizationwithlinearconvergence AT xielihua innovationcompressionforcommunicationefficientdistributedoptimizationwithlinearconvergence |