ExtraPush for Convex Smooth Decentralized Optimization over Directed Networks

Jinshan Zeng and Wotao Yin

Published in Journal of Computational Mathematics, Special Issue on Compressed Sensing, Optimization, and Structured Solutions


In this note, we extend the existing algorithms Extra and subgradient-push to a new algorithm called ExtraPush for convex consensus optimization over a directed network. When the network is stationary, we propose a simplified algorithm called Normalized ExtraPush. These algorithms use a fixed step size like in Extra and accept the column-stochastic mixing matrices like in subgradient-push. 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.


J. Zeng and W. Yin, ExtraPush for convex smooth decentralized optimization over directed networks, Journal of Computational Mathematics 35(4), 381-394, Special Issue on Compressed Sensing, Optimization, and Structured Solutions, 2017.

« Back