Communication Efficient Primal-Dual Algorithm for Nonconvex Nonsmooth Distributed Optimization

Congliang Chen, Jiawei Zhang, Li Shen, Peilin Zhao, Zhiquan Luo
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:1594-1602, 2021.

Abstract

Decentralized optimization problems frequently appear in the large scale machine learning problems. However, few works work on the difficult nonconvex nonsmooth case. In this paper, we propose a decentralized primal-dual algorithm to solve this type of problem in a decentralized manner and the proposed algorithm can achieve an $\mathcal{O}(1/\epsilon^2)$ iteration complexity to attain an $\epsilon-$solution, which is the well-known lower iteration complexity bound for nonconvex optimization. To our knowledge, it is the first algorithm achieving this rate under a nonconvex, nonsmooth decentralized setting. Furthermore, to reduce communication overhead, we also modifying our algorithm by compressing the vectors exchanged between agents. The iteration complexity of the algorithm with compression is still $\mathcal{O}(1/\epsilon^2)$. Besides, we apply the proposed algorithm to solve nonconvex linear regression problem and train deep learning model, both of which demonstrate the efficiency and efficacy of the proposed algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-chen21c, title = { Communication Efficient Primal-Dual Algorithm for Nonconvex Nonsmooth Distributed Optimization }, author = {Chen, Congliang and Zhang, Jiawei and Shen, Li and Zhao, Peilin and Luo, Zhiquan}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {1594--1602}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/chen21c/chen21c.pdf}, url = {https://proceedings.mlr.press/v130/chen21c.html}, abstract = { Decentralized optimization problems frequently appear in the large scale machine learning problems. However, few works work on the difficult nonconvex nonsmooth case. In this paper, we propose a decentralized primal-dual algorithm to solve this type of problem in a decentralized manner and the proposed algorithm can achieve an $\mathcal{O}(1/\epsilon^2)$ iteration complexity to attain an $\epsilon-$solution, which is the well-known lower iteration complexity bound for nonconvex optimization. To our knowledge, it is the first algorithm achieving this rate under a nonconvex, nonsmooth decentralized setting. Furthermore, to reduce communication overhead, we also modifying our algorithm by compressing the vectors exchanged between agents. The iteration complexity of the algorithm with compression is still $\mathcal{O}(1/\epsilon^2)$. Besides, we apply the proposed algorithm to solve nonconvex linear regression problem and train deep learning model, both of which demonstrate the efficiency and efficacy of the proposed algorithm. } }
Endnote
%0 Conference Paper %T Communication Efficient Primal-Dual Algorithm for Nonconvex Nonsmooth Distributed Optimization %A Congliang Chen %A Jiawei Zhang %A Li Shen %A Peilin Zhao %A Zhiquan Luo %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-chen21c %I PMLR %P 1594--1602 %U https://proceedings.mlr.press/v130/chen21c.html %V 130 %X Decentralized optimization problems frequently appear in the large scale machine learning problems. However, few works work on the difficult nonconvex nonsmooth case. In this paper, we propose a decentralized primal-dual algorithm to solve this type of problem in a decentralized manner and the proposed algorithm can achieve an $\mathcal{O}(1/\epsilon^2)$ iteration complexity to attain an $\epsilon-$solution, which is the well-known lower iteration complexity bound for nonconvex optimization. To our knowledge, it is the first algorithm achieving this rate under a nonconvex, nonsmooth decentralized setting. Furthermore, to reduce communication overhead, we also modifying our algorithm by compressing the vectors exchanged between agents. The iteration complexity of the algorithm with compression is still $\mathcal{O}(1/\epsilon^2)$. Besides, we apply the proposed algorithm to solve nonconvex linear regression problem and train deep learning model, both of which demonstrate the efficiency and efficacy of the proposed algorithm.
APA
Chen, C., Zhang, J., Shen, L., Zhao, P. & Luo, Z.. (2021). Communication Efficient Primal-Dual Algorithm for Nonconvex Nonsmooth Distributed Optimization . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:1594-1602 Available from https://proceedings.mlr.press/v130/chen21c.html.

Related Material