# ExtraPush for convex smooth decentralized optimization over directed networks

arXiv: https://arxiv.org/abs/1511.02942 · HTML: https://mlsanity.com/paper/1511.02942/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2015.

## Built on by (most cited first, 4 of 4)

- [Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks](https://mlsanity.com/paper/2106.07243/) (2021)
- [Asymmetrically Decentralized Federated Learning](https://mlsanity.com/paper/2310.05093/) (2023)
- [Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2601.11435/) (2026)
- [Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs](https://mlsanity.com/paper/2602.20567/) (2026)

## Abstract (arXiv)

In this note, we extend the algorithms Extra and subgradient-push 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.