Catalyst Acceleration of Error Compensated Methods Leads to Better Communication Complexity

Xun Qian, Hanze Dong, Tong Zhang, Peter Richtarik
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:615-649, 2023.

Abstract

Communication overhead is well known to be a key bottleneck in large scale distributed learning, and a particularly successful class of methods which help to overcome this bottleneck is based on the idea of communication compression. Some of the most practically effective gradient compressors, such as TopK, are biased, which causes convergence issues unless one employs a well designed error compensation/feedback mechanism. Error compensation is therefore a fundamental technique in the distributed learning literature. In a recent development, Qian et al (NeurIPS 2021) showed that the error-compensation mechanism can be combined with acceleration/momentum, which is another key and highly successful optimization technique. In particular, they developed the error-compensated loop-less Katyusha (ECLK) method, and proved an accelerated linear rate in the strongly convex case. However, the dependence of their rate on the compressor parameter does not match the best dependence obtainable in the non-accelerated error-compensated methods. Our work addresses this problem. We propose several new accelerated error-compensated methods using the catalyst acceleration technique, and obtain results that match the best dependence on the compressor parameter in non-accelerated error-compensated methods up to logarithmic terms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-qian23a, title = {Catalyst Acceleration of Error Compensated Methods Leads to Better Communication Complexity}, author = {Qian, Xun and Dong, Hanze and Zhang, Tong and Richtarik, Peter}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {615--649}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/qian23a/qian23a.pdf}, url = {https://proceedings.mlr.press/v206/qian23a.html}, abstract = {Communication overhead is well known to be a key bottleneck in large scale distributed learning, and a particularly successful class of methods which help to overcome this bottleneck is based on the idea of communication compression. Some of the most practically effective gradient compressors, such as TopK, are biased, which causes convergence issues unless one employs a well designed error compensation/feedback mechanism. Error compensation is therefore a fundamental technique in the distributed learning literature. In a recent development, Qian et al (NeurIPS 2021) showed that the error-compensation mechanism can be combined with acceleration/momentum, which is another key and highly successful optimization technique. In particular, they developed the error-compensated loop-less Katyusha (ECLK) method, and proved an accelerated linear rate in the strongly convex case. However, the dependence of their rate on the compressor parameter does not match the best dependence obtainable in the non-accelerated error-compensated methods. Our work addresses this problem. We propose several new accelerated error-compensated methods using the catalyst acceleration technique, and obtain results that match the best dependence on the compressor parameter in non-accelerated error-compensated methods up to logarithmic terms.} }
Endnote
%0 Conference Paper %T Catalyst Acceleration of Error Compensated Methods Leads to Better Communication Complexity %A Xun Qian %A Hanze Dong %A Tong Zhang %A Peter Richtarik %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-qian23a %I PMLR %P 615--649 %U https://proceedings.mlr.press/v206/qian23a.html %V 206 %X Communication overhead is well known to be a key bottleneck in large scale distributed learning, and a particularly successful class of methods which help to overcome this bottleneck is based on the idea of communication compression. Some of the most practically effective gradient compressors, such as TopK, are biased, which causes convergence issues unless one employs a well designed error compensation/feedback mechanism. Error compensation is therefore a fundamental technique in the distributed learning literature. In a recent development, Qian et al (NeurIPS 2021) showed that the error-compensation mechanism can be combined with acceleration/momentum, which is another key and highly successful optimization technique. In particular, they developed the error-compensated loop-less Katyusha (ECLK) method, and proved an accelerated linear rate in the strongly convex case. However, the dependence of their rate on the compressor parameter does not match the best dependence obtainable in the non-accelerated error-compensated methods. Our work addresses this problem. We propose several new accelerated error-compensated methods using the catalyst acceleration technique, and obtain results that match the best dependence on the compressor parameter in non-accelerated error-compensated methods up to logarithmic terms.
APA
Qian, X., Dong, H., Zhang, T. & Richtarik, P.. (2023). Catalyst Acceleration of Error Compensated Methods Leads to Better Communication Complexity. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:615-649 Available from https://proceedings.mlr.press/v206/qian23a.html.

Related Material