期刊
JOURNAL OF COMPUTATIONAL MATHEMATICS
卷 35, 期 4, 页码 383-396出版社
GLOBAL SCIENCE PRESS
DOI: 10.4208/jcm.1606-m2015-0452
关键词
Decentralized optimization; Directed graph; Consensus; Non-doubly stochastic; Extra
资金
- NSF [DMS-1317602, ECCS-1462398, 11501440]
- Directorate For Engineering [1462397] Funding Source: National Science Foundation
In this note, we extend the algorithms Extra [13] and subgradient-push [10] to a new algorithm ExtraPush for consensus optimization with convex differentiable objective functions over a directed network. When the stationary distribution of the network can be computed in advance, we propose a simplified algorithm called Normalized ExtraPush. Just like Extra, both ExtraPush and Normalized ExtraPush can iterate with a fixed step size. But unlike Extra, they can take a column-stochastic mixing matrix, which is not necessarily doubly stochastic. Therefore, they remove the undirected-network restriction of Extra. Subgradient-push, while also works for directed networks, is slower on the same type of problem because it must use a sequence of diminishing step sizes. We present preliminary analysis for ExtraPush under a bounded sequence assumption. For Normalized ExtraPush, we show that it naturally produces a bounded, linearly convergent sequence provided that the objective function is strongly convex. In our numerical experiments, ExtraPush and Normalized ExtraPush performed similarly well. They are significantly faster than subgradient-push, even when we hand-optimize the step sizes for the latter.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据