@Article{JCM-35-4,
author = {Zeng, Jinshan and Yin, Wotao},
title = {ExtraPush for Convex Smooth Decentralized Optimization over Directed Networks},
journal = {Journal of Computational Mathematics},
year = {2017},
volume = {35},
number = {4},
pages = {383--396},
abstract = {<p style="text-align: justify;">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. <br/>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. <br/>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.</p>},
issn = {1991-7139},
doi = {https://doi.org/10.4208/jcm.1606-m2015-0452},
url = {https://global-sci.com/article/84525/extrapush-for-convex-smooth-decentralized-optimization-over-directed-networks}
}