具有通信跳过的方差降低型分散随机优化算法

去中心化优化网络中提出两种通信高效算法DSC-SAGA和DSC-SVRG，通过跳过部分通信回合实现线性收敛，并建立最优通信复杂度公式，实验验证最优通信概率p=O(1/Q)的实用性。

　　

摘要：

在本文中，我们研究了一个分散式优化问题，该问题涉及一个由个计算节点（例如机器）组成的网络。这些节点能够与它们的直接邻居进行通信。每个节点只能访问其自身的成本函数，该成本函数表现为一个有限求和的形式。目标是通过节点之间的合作找到总成本的最小值。为了解决这个问题，我们提出了两种具有方差减少机制的分散式随机控制算法，即DSC-SAGA和DSC-SVRG。与大多数依赖迭代间通信机制的现有方法不同，本文提出的算法会跳过某些通信轮次，也就是说，通信仅在特定的计算轮次之后进行。当目标函数是 - 强凸的，并且是L - 光滑的时，算法能够实现线性收敛。更重要的是，我们为这两种算法建立了先进的通信复杂度理论：对于DSC-SAGA，通信复杂度为mx/Q+Qlog1/?；对于DSC-SVRG，通信复杂度为mx。其中，mx表示每个节点上的样本函数数量最大值，L表示条件数，?表示所需的误差容忍度。我们在各种数据集和多种网络拓扑结构上进行了广泛的实证实验，结果表明我们提出的算法在通信效率上更具优势。此外，我们还通过数值计算证明了理论上得出的最优通信概率(p/在实践中是成立的，这为调整通信概率提供了实用的方法。