arrow
返回

Push-Pull Gradient Methods for Distributed Optimization in Networks

delete2021-01-01
delete214
delete
OA
AI
S
Shi Pu *
W
Wei Shi
J
Jinming Xu *
A
Angelia Nedić
DOI:10.1109/TAC.2020.2972824delete
delete原文链接
delete分享
delete收藏
查看原文
摘要

摘要

En 中文
In this article, we focus on solving a distributed convex optimization problem in a network, where each agent has its own convex cost function and the goal is to minimize the sum of the agents' cost functions while obeying the network connectivity structure. In order to minimize the sum of the cost functions, we consider new distributed gradient-based methods where each node maintains two estimates, namely an estimate of the optimal decision variable and an estimate of the gradient for the average of the agents' objective functions. From the viewpoint of an agent, the information about the gradients is pushed to the neighbors, whereas the information about the decision variable is pulled from the neighbors, hence giving the name push-pull gradient methods. The methods utilize two different graphs for the information exchange among agents and, as such, unify the algorithms with different types of distributed architecture, including decentralized (peer to peer), centralized (master-slave), and semicentralized (leader-follower) architectures. We show that the proposed algorithms and their many variants converge linearly for strongly convex and smooth objective functions over a network (possibly with unidirectional data links) in both synchronous and asynchronous random-gossip settings. In particular, under the random-gossip setting, push-pull is the first class of algorithms for distributed optimization over directed graphs. Moreover, we numerically evaluate our proposed algorithms in both scenarios, and show that they outperform other existing linearly convergent schemes, especially for ill-conditioned problems and networks that are not well balanced.
Keyword:
Convex optimization
directed graph
distributed optimization
linear convergence
network structure
random-gossip algorithm
spanning tree
AI总结

AI总结

对已上传原文的论文进行重点信息的提取,主要内容包括:简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。

期刊

IEEE Transactions on Automatic Control 封面图
IEEE Transactions on Automatic Control
IF:
7
论文数:
1.3W
被引数:
8.3W

机构

P
princeton university
学者数:
3.0K
论文数: 1.2K
被引数: 2.8W
浙江大学 封面图
浙江大学
学者数:
186
论文数: 75
被引数: 9.6W
T
The Chinese University of Hong Kong, Shenzhen
学者数:
0
论文数: 1
被引数: 5.0K
深
深圳市大数据研究院
学者数:
67
论文数: 48
被引数: 771
学者 查看更多机构
引用论文

引用论文

Model experiments pertaining to the mechanism of action of vitamin B12-dependent α-methyleneglutarate mutase
err1989-01-01
err0
PREAI
errSusan Ashwell; Alwyn G. Davies; Bernard T. Golding; Robyn Hay-Motherwell; Samson Mwesigye-Kibende
err分享
err收藏
err分享
err收藏
Synthesis and biological evaluation of analogs of the marine toxin polycavernoside A
err1999-07-01
err0
PREAI
errLouis Barriault; Serge L. Boulet; Kenshu Fujiwara; Akio Murai; Leo A. Paquette; Mari Yotsu-Yamashita
err分享
err收藏
Newton-Raphson Consensus for Distributed Convex Optimization分布式凸优化的牛顿-拉夫逊一致性
err2016-04-01
err166
errOAAI
errVaragnolo, Damiano; Zanella, Filippo; Cenedese, Angelo; Pillonetto, Gianluigi; Schenato, Luca
err分享
err收藏
学者 查看更多内容