We study decentralized non-convex finite-sum minimization problems described over a network of nodes, where each node possesses a local batch of data samples. In this context, we analyze a single-timescale randomized incremental gradient method, called GT-SAGA. GT-SAGA is computationally efficient as it evaluates one component gradient per node per iteration and achieves provably fast and robust performance by leveraging node-level variance reduction and network-level gradient tracking. For general smooth non-convex problems, we show the almost sure and mean-squared convergence of GT-SAGA to a first-order stationary point and further describe regimes of practical significance where it outperforms the existing approaches and achieves a network topology-independent iteration complexity respectively. When the global function satisfies the Polyak-Lojaciewisz condition, we show that GT-SAGA exhibits linear convergence to an optimal solution in expectation and describe regimes of practical interest where the performance is network topology-independent and improves upon the existing methods. Numerical experiments are included to highlight the main convergence aspects of GT-SAGA in non-convex settings.


翻译:我们研究在节点网络上描述的分散的非convex有限和最小化问题,每个节点都拥有当地一组数据样品;在这方面,我们分析一个单一时间尺度的随机递增梯度方法,称为GT-SAGA。GT-SAGA在计算效率上是有效的,因为它评估了每个节点的一个组成部分梯度,并且通过利用节点水平差异减少和网络水平梯度跟踪,取得了可以衡量的快速和强效业绩。对于一般顺利的无节点问题,我们显示了GT-SAGA与一级固定点的几乎肯定和平均的趋同,并进一步描述了其超越现有方法并分别达到网络地貌独立的迭代复杂度的具有实际意义的制度。当全球功能满足了Polyak-Lojaciewisz条件时,我们表明GT-SAGA展示了线性趋同预期的最佳解决办法,并描述了在业绩是网络地形依赖和改进现有方法的情况下的实际利益制度。Nummerical实验包括突出GT-SAA在非CONGA中的主要趋同方面。

0
下载
关闭预览

相关内容

剑桥大学《数据科学: 原理与实践》课程,附PPT下载
专知会员服务
49+阅读 · 2021年1月20日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
39+阅读 · 2020年9月6日
【Google】平滑对抗训练,Smooth Adversarial Training
专知会员服务
48+阅读 · 2020年7月4日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
已删除
将门创投
5+阅读 · 2018年11月15日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Arxiv
5+阅读 · 2017年12月14日
VIP会员
相关资讯
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
已删除
将门创投
5+阅读 · 2018年11月15日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Top
微信扫码咨询专知VIP会员