In this paper, we propose Push-SAGA, a decentralized stochastic first-order method for finite-sum minimization over a directed network of nodes. Push-SAGA combines node-level variance reduction to remove the uncertainty caused by stochastic gradients, network-level gradient tracking to address the distributed nature of the data, and push-sum consensus to tackle the challenge of directed communication links. We show that Push-SAGA achieves linear convergence to the exact solution for smooth and strongly convex problems and is thus the first linearly-convergent stochastic algorithm over arbitrary strongly connected directed graphs. We also characterize the regimes in which Push-SAGA achieves a linear speed-up compared to its centralized counterpart and achieves a network-independent convergence rate. We illustrate the behavior and convergence properties of Push-SAGA with the help of numerical experiments on strongly convex and non-convex problems.
翻译:在本文中,我们建议采用Push-SAGA,这是在指定的节点网络上实现有限和最小化的分层第一阶方法。 Push-SAGA将节点差异减少结合起来,以消除由随机梯度、网络级梯度跟踪处理数据分布性造成的不确定性,并形成应对定向通信连接挑战的推-总共识。我们表明,Push-SAGA实现了线性趋同,以准确解决顺利和强烈交错的问题,因此是针对任意紧密连接的定向图形的第一个线性趋同式求和算法。我们还确定了Push-SAGA相对于中央对口单位实现线性加速并实现网络独立趋同率的制度。我们用对强烈交错和非节点问题进行的数字实验来说明Push-SAGA的行为和趋同性。