A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!
This addresses the energy and time costs of communication for on-device machine learning training, offering a novel solution with theoretical guarantees.
The paper tackles the communication bottleneck in decentralized optimization by proposing a randomized first-order method with compression and variance reduction, achieving linear convergence on strongly convex problems without increasing communication rounds compared to uncompressed baselines.
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 the first 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. Our key theoretical findings are supported by numerical experiments.