论文标题
用于分散优化的线性收敛算法：免费发送更少的位！
A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!
论文作者
论文摘要
分散的优化方法可以在没有中央协调员的情况下对机器学习模型进行设备培训。在许多情况下，设备之间的通信是能量需求和耗时，并构成了整个系统的瓶颈。 我们提出了一种新的随机一阶方法，该方法通过将随机压缩操作员应用于通信的消息来解决通信瓶颈。通过将我们的方案与一种新方差降低技术相结合，该技术在整个迭代中逐渐降低了注入的量化噪声的不利影响，我们获得了第一个方案，该方案仅在使用压缩通信的同时在强烈凸出的分散问题上线性收敛。 我们证明，与基线相比，我们的方法可以解决问题而不会增加通信的数量，而基线没有执行任何通信压缩，同时仍允许重要的压缩因子，这取决于问题的条件和网络的拓扑结构。我们的关键理论发现得到了数值实验的支持。
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.
