A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!

Dmitry Kovalev, Anastasia Koloskova, Martin Jaggi, Peter Richtarik, Sebastian U. Stich

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Decentralized optimization methods enable on-device training of machine learning models without a central coordinator. In many scenarios communication between devices is energy demanding and time consuming and forms the bottleneck of the entire system. We propose a new randomized first-order method which tackles the communication bottleneck by applying randomized compression operators to the communicated messages. By combining our scheme with a new variance reduction technique that progressively throughout the iterations reduces the adverse effect of the injected quantization noise, we obtain a scheme that converges linearly on strongly convex decentralized problems while using compressed communication only. We prove that our method can solve the problems without any increase in the number of communications compared to the baseline which does not perform any communication compression while still allowing for a significant compression factor which depends on the conditioning of the problem and the topology of the network. We confirm our theoretical findings in numerical experiments.
Original languageEnglish (US)
Title of host publication24th International Conference on Artificial Intelligence and Statistics (AISTATS)
StatePublished - 2021

Bibliographical note

KAUST Repository Item: Exported on 2021-08-31
Acknowledgements: We acknowledge funding from SNSF grant 200021_175796, as well as a Google Focused Research Award.


Dive into the research topics of 'A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!'. Together they form a unique fingerprint.

Cite this