Distributed optimization methods with random communication skips are gaining
increasing attention due to their proven benefits in accelerating communication
complexity. Nevertheless, existing research mainly focuses on centralized
communication protocols for strongly convex deterministic settings. In this
work, we provide a decentralized optimization method called RandCom, which
incorporates probabilistic local updates. We analyze the performance of RandCom
in stochastic non-convex, convex, and strongly convex settings and demonstrate
its ability to asymptotically reduce communication overhead by the probability
of communication. Additionally, we prove that RandCom achieves linear speedup
as the number of nodes increases. In stochastic strongly convex settings, we
further prove that RandCom can achieve linear speedup with network-independent
stepsizes. Moreover, we apply RandCom to federated learning and provide
positive results concerning the potential for achieving linear speedup and the
suitability of the probabilistic local update approach for non-convex settings.

通过引入随机通信跳过的分布式优化方法，本文提出了一种名为 RandCom 的分散优化方法，并分析了其在随机非凸、凸和强凸环境中的性能，证明其能够通过通信概率来渐进地减少通信开销，并在节点数量增加时实现线性加速。此外，通过将 RandCom 应用于联合学习，得出了在非凸设置中实现线性加速的潜力和概率局部更新方法的适用性的积极结果。