On the Convergence of Decentralized Stochastic Minimax Optimization Algorithm with Compressed Communication

Yihan Zhang, Xinghua Shi, Meikang Qiu, Yu Wang, Hongchang Gao
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:158298-158362, 2026.

Abstract

The stochastic minimax optimization problem has widespread applications in machine learning. Recently, numerous distributed minimax optimization algorithms have been developed to handle distributed training data. However, most of these algorithms suffer from high communication costs. To address this issue, we develop a novel communication-efficient decentralized stochastic gradient descent ascent with momentum algorithm based on the error feedback mechanism. Importantly, our algorithm demonstrates how to balance the full-precision update and the compression residual with novel designs for coefficients regarding variables and gradients to guarantee convergence. However, compressing the primal and dual variables (and their gradients) of stochastic minimax optimization problems with the error feedback mechanism presents significant challenges for convergence analysis. In particular, it incurs the circle dependence among consensus errors and compression errors. To overcome this challenge, we propose novel strategies that enable the establishment of the convergence rate for our algorithm. Our theoretical results demonstrate how the compression operator influences the convergence rate. Finally, extensive experimental results confirm the efficacy of our proposed algorithm.

Cite this Paper


BibTeX
@InProceedings{pmlr-v306-zhang26fe, title = {On the Convergence of Decentralized Stochastic Minimax Optimization Algorithm with Compressed Communication}, author = {Zhang, Yihan and Shi, Xinghua and Qiu, Meikang and Wang, Yu and Gao, Hongchang}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {158298--158362}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/zhang26fe/zhang26fe.pdf}, url = {https://proceedings.mlr.press/v306/zhang26fe.html}, abstract = {The stochastic minimax optimization problem has widespread applications in machine learning. Recently, numerous distributed minimax optimization algorithms have been developed to handle distributed training data. However, most of these algorithms suffer from high communication costs. To address this issue, we develop a novel communication-efficient decentralized stochastic gradient descent ascent with momentum algorithm based on the error feedback mechanism. Importantly, our algorithm demonstrates how to balance the full-precision update and the compression residual with novel designs for coefficients regarding variables and gradients to guarantee convergence. However, compressing the primal and dual variables (and their gradients) of stochastic minimax optimization problems with the error feedback mechanism presents significant challenges for convergence analysis. In particular, it incurs the circle dependence among consensus errors and compression errors. To overcome this challenge, we propose novel strategies that enable the establishment of the convergence rate for our algorithm. Our theoretical results demonstrate how the compression operator influences the convergence rate. Finally, extensive experimental results confirm the efficacy of our proposed algorithm.} }
Endnote
%0 Conference Paper %T On the Convergence of Decentralized Stochastic Minimax Optimization Algorithm with Compressed Communication %A Yihan Zhang %A Xinghua Shi %A Meikang Qiu %A Yu Wang %A Hongchang Gao %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-zhang26fe %I PMLR %P 158298--158362 %U https://proceedings.mlr.press/v306/zhang26fe.html %V 306 %X The stochastic minimax optimization problem has widespread applications in machine learning. Recently, numerous distributed minimax optimization algorithms have been developed to handle distributed training data. However, most of these algorithms suffer from high communication costs. To address this issue, we develop a novel communication-efficient decentralized stochastic gradient descent ascent with momentum algorithm based on the error feedback mechanism. Importantly, our algorithm demonstrates how to balance the full-precision update and the compression residual with novel designs for coefficients regarding variables and gradients to guarantee convergence. However, compressing the primal and dual variables (and their gradients) of stochastic minimax optimization problems with the error feedback mechanism presents significant challenges for convergence analysis. In particular, it incurs the circle dependence among consensus errors and compression errors. To overcome this challenge, we propose novel strategies that enable the establishment of the convergence rate for our algorithm. Our theoretical results demonstrate how the compression operator influences the convergence rate. Finally, extensive experimental results confirm the efficacy of our proposed algorithm.
APA
Zhang, Y., Shi, X., Qiu, M., Wang, Y. & Gao, H.. (2026). On the Convergence of Decentralized Stochastic Minimax Optimization Algorithm with Compressed Communication. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:158298-158362 Available from https://proceedings.mlr.press/v306/zhang26fe.html.

Related Material