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.

提出了一种新的基于随机压缩算子的一阶随机算法和方差约简技术，能够在去除了通信中数据量的一定压缩的前提下，快速地在分散的装置上完成模型的机器学习训练并收敛于最优解。