Accelerated Distributed Optimization with Compression and Error Feedback

Yuan Gao, Anton Rodomanov, Jeremy Rack, Sebastian U Stich
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:3304-3312, 2026.

Abstract

Modern machine learning tasks often involve massive datasets and models, necessitating distributed optimization algorithms with reduced communication overhead. Communication compression, where clients transmit compressed updates to a central server, has emerged as a key technique to mitigate communication bottlenecks. However, the theoretical understanding of stochastic distributed optimization with contractive compression remains limited, particularly in conjunction with Nesterov acceleration—a cornerstone for achieving faster convergence in optimization. In this paper, we propose a novel algorithm, ADEF (\textbf{A}ccelerated \textbf{D}istributed \textbf{E}rror \textbf{F}eedback), which integrates Nesterov acceleration, contractive compression, error feedback, and gradient difference compression. We prove that ADEF achieves the first accelerated convergence rate for stochastic distributed optimization with contractive compression in the general convex regime. Numerical experiments validate our theoretical findings and demonstrate the practical efficacy of ADEF in reducing communication costs while maintaining fast convergence.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-gao26c, title = { Accelerated Distributed Optimization with Compression and Error Feedback }, author = {Gao, Yuan and Rodomanov, Anton and Rack, Jeremy and Stich, Sebastian U}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {3304--3312}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/gao26c/gao26c.pdf}, url = {https://proceedings.mlr.press/v300/gao26c.html}, abstract = { Modern machine learning tasks often involve massive datasets and models, necessitating distributed optimization algorithms with reduced communication overhead. Communication compression, where clients transmit compressed updates to a central server, has emerged as a key technique to mitigate communication bottlenecks. However, the theoretical understanding of stochastic distributed optimization with contractive compression remains limited, particularly in conjunction with Nesterov acceleration—a cornerstone for achieving faster convergence in optimization. In this paper, we propose a novel algorithm, ADEF (\textbf{A}ccelerated \textbf{D}istributed \textbf{E}rror \textbf{F}eedback), which integrates Nesterov acceleration, contractive compression, error feedback, and gradient difference compression. We prove that ADEF achieves the first accelerated convergence rate for stochastic distributed optimization with contractive compression in the general convex regime. Numerical experiments validate our theoretical findings and demonstrate the practical efficacy of ADEF in reducing communication costs while maintaining fast convergence. } }
Endnote
%0 Conference Paper %T Accelerated Distributed Optimization with Compression and Error Feedback %A Yuan Gao %A Anton Rodomanov %A Jeremy Rack %A Sebastian U Stich %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-gao26c %I PMLR %P 3304--3312 %U https://proceedings.mlr.press/v300/gao26c.html %V 300 %X Modern machine learning tasks often involve massive datasets and models, necessitating distributed optimization algorithms with reduced communication overhead. Communication compression, where clients transmit compressed updates to a central server, has emerged as a key technique to mitigate communication bottlenecks. However, the theoretical understanding of stochastic distributed optimization with contractive compression remains limited, particularly in conjunction with Nesterov acceleration—a cornerstone for achieving faster convergence in optimization. In this paper, we propose a novel algorithm, ADEF (\textbf{A}ccelerated \textbf{D}istributed \textbf{E}rror \textbf{F}eedback), which integrates Nesterov acceleration, contractive compression, error feedback, and gradient difference compression. We prove that ADEF achieves the first accelerated convergence rate for stochastic distributed optimization with contractive compression in the general convex regime. Numerical experiments validate our theoretical findings and demonstrate the practical efficacy of ADEF in reducing communication costs while maintaining fast convergence.
APA
Gao, Y., Rodomanov, A., Rack, J. & Stich, S.U.. (2026). Accelerated Distributed Optimization with Compression and Error Feedback . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:3304-3312 Available from https://proceedings.mlr.press/v300/gao26c.html.

Related Material