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的行为和趋同性。

0
下载
关闭预览

相关内容

专知会员服务
52+阅读 · 2020年11月3日
【KDD2020】最小方差采样用于图神经网络的快速训练
专知会员服务
27+阅读 · 2020年7月13日
开源书:PyTorch深度学习起步
专知会员服务
50+阅读 · 2019年10月11日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
4+阅读 · 2019年4月1日
弱监督语义分割最新方法资源列表
专知
9+阅读 · 2019年2月26日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
carla 学习笔记
CreateAMind
9+阅读 · 2018年2月7日
论文浅尝 | Reinforcement Learning for Relation Classification
开放知识图谱
9+阅读 · 2017年12月10日
Arxiv
19+阅读 · 2020年7月13日
Arxiv
5+阅读 · 2017年12月14日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
4+阅读 · 2019年4月1日
弱监督语义分割最新方法资源列表
专知
9+阅读 · 2019年2月26日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
carla 学习笔记
CreateAMind
9+阅读 · 2018年2月7日
论文浅尝 | Reinforcement Learning for Relation Classification
开放知识图谱
9+阅读 · 2017年12月10日
Top
微信扫码咨询专知VIP会员