Communication-Efficient Distributed Primal-Dual Algorithm for Saddle Point Problems

Yaodong Yu, Sulin Liu, Sinno Jialin Pan
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:171-180, 2017.

Abstract

Primal-dual algorithms, which are proposed to solve reformulated convex-concave saddle point problems, have been proven to be effective for solving a generic class of convex optimization problems, especially when the problems are ill-conditioned. However, the saddle point problem still lacks a distributed optimization framework where primal-dual algorithms can be employed. In this paper, we propose a novel communication-efficient distributed optimization framework to solve the convex-concave saddle point problem based on primal-dual methods. We carefully design local subproblems and a central problem such that our proposed distributed optimization framework is communication-efficient. We provide a convergence analysis of our proposed algorithm, and extend it to address non-smooth and non-strongly convex loss functions. We conduct extensive experiments on several real-world datasets to demonstrate competitive performance of the proposed method, especially on ill-conditioned problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-yu17a, title = {Communication-Efficient Distributed Primal-Dual Algorithm for Saddle Point Problems}, author = {Yu, Yaodong and Liu, Sulin and Pan, Sinno Jialin}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {171--180}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/yu17a/yu17a.pdf}, url = {https://proceedings.mlr.press/r15/yu17a.html}, abstract = {Primal-dual algorithms, which are proposed to solve reformulated convex-concave saddle point problems, have been proven to be effective for solving a generic class of convex optimization problems, especially when the problems are ill-conditioned. However, the saddle point problem still lacks a distributed optimization framework where primal-dual algorithms can be employed. In this paper, we propose a novel communication-efficient distributed optimization framework to solve the convex-concave saddle point problem based on primal-dual methods. We carefully design local subproblems and a central problem such that our proposed distributed optimization framework is communication-efficient. We provide a convergence analysis of our proposed algorithm, and extend it to address non-smooth and non-strongly convex loss functions. We conduct extensive experiments on several real-world datasets to demonstrate competitive performance of the proposed method, especially on ill-conditioned problems.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Communication-Efficient Distributed Primal-Dual Algorithm for Saddle Point Problems %A Yaodong Yu %A Sulin Liu %A Sinno Jialin Pan %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-yu17a %I PMLR %P 171--180 %U https://proceedings.mlr.press/r15/yu17a.html %V R15 %X Primal-dual algorithms, which are proposed to solve reformulated convex-concave saddle point problems, have been proven to be effective for solving a generic class of convex optimization problems, especially when the problems are ill-conditioned. However, the saddle point problem still lacks a distributed optimization framework where primal-dual algorithms can be employed. In this paper, we propose a novel communication-efficient distributed optimization framework to solve the convex-concave saddle point problem based on primal-dual methods. We carefully design local subproblems and a central problem such that our proposed distributed optimization framework is communication-efficient. We provide a convergence analysis of our proposed algorithm, and extend it to address non-smooth and non-strongly convex loss functions. We conduct extensive experiments on several real-world datasets to demonstrate competitive performance of the proposed method, especially on ill-conditioned problems. %Z Reissued by PMLR on 04 October 2026.
APA
Yu, Y., Liu, S. & Pan, S.J.. (2017). Communication-Efficient Distributed Primal-Dual Algorithm for Saddle Point Problems. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:171-180 Available from https://proceedings.mlr.press/r15/yu17a.html. Reissued by PMLR on 04 October 2026.

Related Material