论文标题
八卦算法中的异步和加速度
Asynchrony and Acceleration in Gossip Algorithms
论文作者
论文摘要
本文认为，在通信网络的节点上派遣了一系列平滑且强烈凸的功能的最小化。以前关于该主题的工作要么集中在同步算法上，这些算法可以通过一些缓慢的节点（Straggler问题）大大减慢，要么考虑一个异步操作模型（Boyd等人，2006年），其中相邻节点在Poisson Points Posseces的瞬间进行通信。我们有两个主要贡献。 1) We propose CACDM (a Continuously Accelerated Coordinate Dual Method), and for the Poisson model of asynchronous operation, we prove CACDM to converge to optimality at an accelerated convergence rate in the sense of Nesterov et Stich, 2017. In contrast, previously proposed asynchronous algorithms have not been proven to achieve such accelerated rate.尽管CACDM基于离散更新，但其收敛的证明至关重要地取决于连续的时间分析。 2）我们介绍了一种基于损失网络的新通信方案，该方案可以完全异步和分散的方式进行编程，这与异步操作的泊松模型不同，该模型无法捕获异步方面的基本方面，例如非执行通信和计算。在这种异步的损失网络模型下，我们为CDM（一种坐标二种方法）建立了收敛速率，该融合速率是根据局部有效延迟加权的图表的laplacian eigengap。我们认为，对于异步优化的收敛速率，这种特征是一种基本瓶颈。最后，我们从经验上验证CACDM在异步模型中享有加速的收敛速率。
This paper considers the minimization of a sum of smooth and strongly convex functions dispatched over the nodes of a communication network. Previous works on the subject either focus on synchronous algorithms, which can be heavily slowed down by a few slow nodes (the straggler problem), or consider a model of asynchronous operation (Boyd et al., 2006) in which adjacent nodes communicate at the instants of Poisson point processes. We have two main contributions. 1) We propose CACDM (a Continuously Accelerated Coordinate Dual Method), and for the Poisson model of asynchronous operation, we prove CACDM to converge to optimality at an accelerated convergence rate in the sense of Nesterov et Stich, 2017. In contrast, previously proposed asynchronous algorithms have not been proven to achieve such accelerated rate. While CACDM is based on discrete updates, the proof of its convergence crucially depends on a continuous time analysis. 2) We introduce a new communication scheme based on Loss-Networks, that is programmable in a fully asynchronous and decentralized way, unlike the Poisson model of asynchronous operation that does not capture essential aspects of asynchrony such as non-instantaneous communications and computations. Under this Loss-Network model of asynchrony, we establish for CDM (a Coordinate Dual Method) a rate of convergence in terms of the eigengap of the Laplacian of the graph weighted by local effective delays. We believe this eigengap to be a fundamental bottleneck for convergence rates of asynchronous optimization. Finally, we verify empirically that CACDM enjoys an accelerated convergence rate in the Loss-Network model of asynchrony.
