论文标题
关于在有方向网络上分散的共识和随机优化的任意压缩
On Arbitrary Compression for Decentralized Consensus and Stochastic Optimization over Directed Networks
论文作者
论文摘要
我们研究了在静态有向图上的压缩通信的分散性共识和随机优化问题。我们提出了一种基于迭代梯度的算法，该算法根据所需的压缩比压缩消息。事实证明，所提出的方法在每个通信回合中都会减少网络上的通信开销。与现有文献相反，我们允许在传达的消息中建立任意压缩比。我们在共识问题上显示了提出的方法的线性收敛速率。此外，我们为分散的随机优化问题提供了明确的收敛速率，即（i）强烈凸，（ii）凸，或（iii）非凸面。最后，我们提供数值实验，以说明在任意压缩比和算法的通信效率下的收敛性。
We study the decentralized consensus and stochastic optimization problems with compressed communications over static directed graphs. We propose an iterative gradient-based algorithm that compresses messages according to a desired compression ratio. The proposed method provably reduces the communication overhead on the network at every communication round. Contrary to existing literature, we allow for arbitrary compression ratios in the communicated messages. We show a linear convergence rate for the proposed method on the consensus problem. Moreover, we provide explicit convergence rates for decentralized stochastic optimization problems on smooth functions that are either (i) strongly convex, (ii) convex, or (iii) non-convex. Finally, we provide numerical experiments to illustrate convergence under arbitrary compression ratios and the communication efficiency of our algorithm.
