ExtraPush for convex smooth decentralized optimization over directed networks
arXiv:1511.02942 · doi:10.4208/jcm.1606-m2015-0452
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.
16 pages, 3 figures
References in corpus (3)
Cited by in corpus (22)
- A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
- Accelerated Distributed Nesterov Gradient Descent
- AsySPA: An Exact Asynchronous Algorithm for Convex Optimization Over Digraphs
- Asynchronous Gradient-Push
- Throughput-Optimal Topology Design for Cross-Silo Federated Learning
- DC-DistADMM: ADMM Algorithm for Constrained Distributed Optimization over Directed Graphs
- On the Linear Convergence of Distributed Optimization over Directed Graphs
- Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
- Improved Convergence Rates for Distributed Resource Allocation
- A Push-Pull Gradient Method for Distributed Optimization in Networks
- Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development
- Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization
- Linear Convergence of First- and Zeroth-Order Primal-Dual Algorithms for Distributed Nonconvex Optimization
- A Survey of Distributed Optimization Methods for Multi-Robot Systems
- Exact Diffusion for Distributed Optimization and Learning --- Part II: Convergence Analysis
- Exponential Convergence for Distributed Smooth Optimization Under the Restricted Secant Inequality Condition
- Distributed Dual Gradient Tracking for Resource Allocation in Unbalanced Networks
- A Unification and Generalization of Exact Distributed First Order Methods
- FlexPD: A Flexible Framework Of First-Order Primal-Dual Algorithms for Distributed Optimization
- On linear convergence of two decentralized algorithms
- A Fast Proximal Gradient Algorithm for Decentralized Composite Optimization over Directed Networks
- A Robust Gradient Tracking Method for Distributed Optimization over Directed Networks