Distributed optimization methods with probabilistic local updates have recently gained attention for their provable ability to communication acceleration. Nevertheless, this capability is effective only when the loss function is smooth and the network is sufficiently well-connected. In this paper, we propose the first linear convergent method MG-Skip with probabilistic local updates for nonsmooth distributed optimization. Without any extra condition for the network connectivity, MG-Skip allows for the multiple-round gossip communication to be skipped in most iterations, while its iteration complexity is $\mathcal{O}\left(\kappa \log \frac{1}{\epsilon}\right)$ and communication complexity is only $\mathcal{O}\left(\sqrt{\frac{\kappa}{(1-\rho)}} \log \frac{1}{\epsilon}\right)$, where $\kappa$ is the condition number of the loss function and $\rho$ reflects the connectivity of the network topology. To the best of our knowledge, MG-Skip achieves the best communication complexity when the loss function has the smooth (strongly convex)+nonsmooth (convex) composite form.

基于概率局部更新的分布式优化方法在通信加速方面引起了人们的关注，然而，这种能力只在损失函数平滑且网络连接充分的情况下有效。本文提出了第一种具有概率局部更新的线性收敛方法MG-Skip用于非平滑分布式优化，无需额外条件对网络连接性能，大多数迭代可以跳过多轮“传闲话”通信，其迭代复杂度为O(κ log(1/ε))，通信复杂度仅为O(√(κ/(1-ρ)) log(1/ε))，其中κ是损失函数的条件数，ρ反映了网络拓扑的连通性。据我们所知，当损失函数具有平滑（强凸）+非平滑（凸）复合形式时，MG-Skip实现了最佳的通信复杂度。

MG-Skip：用于非光滑分布式优化的随机多八卦跳跃方法