ExtraPush for convex smooth decentralized optimization over directed networks

DOI10.4208/JCM.1606-M2015-0452MaRDI QIDQ4688137zbMATH OpenOpenAlexFDO

Authors Jinshan Zeng, Wotao Yin

Publication date 22 October 2018

Published in Journal of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.02942

zbMATH Keywords

consensusdecentralized optimizationdirected graphExtraPush

Mathematics Subject Classification ID

Convex programming (90C25) Programming involving graphs or networks (90C35)

Abstract: 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.

Recommendations

• A fast proximal gradient algorithm for decentralized composite optimization over directed networks
• EXTRA: an exact first-order algorithm for decentralized consensus optimization
• Revisiting EXTRA for Smooth Distributed Optimization
• Distributed quasi-monotone subgradient algorithm for nonsmooth convex optimization over directed graphs
• Distributed nonconvex constrained optimization over time-varying digraphs

Cited in

(9)

• A fast proximal gradient algorithm for decentralized composite optimization over directed networks
• Distributed optimization over directed graphs with row stochasticity and constraint regularity
• On the linear convergence of two decentralized algorithms
• Solving nonnegative sparsity-constrained optimization via DC quadratic-piecewise-linear approximations
• Revisiting EXTRA for Smooth Distributed Optimization
• ExtraPush
• Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
• Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation
• EXTRA: an exact first-order algorithm for decentralized consensus optimization

This page was built for publication: ExtraPush for convex smooth decentralized optimization over directed networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4688137)