ExtraPush for Convex Smooth Decentralized Optimization over Directed Networks

Jinshan Zeng and Wotao Yin

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

Overview

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.

Citation

J. Zeng and W. Yin, ExtraPush for convex smooth decentralized optimization over directed networks, UCLA CAM Report 15-61, to appear in Journal of Computational Mathematics, Special Issue on Compressed Sensing, Optimization, and Structured Solutions’17, submitted in 2015.


« Back