A fast proximal gradient algorithm for decentralized composite optimization over directed networks
From MaRDI portal
(Redirected from Publication:1680665)
Abstract: This paper proposes a fast decentralized algorithm for solving a consensus optimization problem defined in a directed networked multi-agent system, where the local objective functions have the smooth+nonsmooth composite form, and are possibly nonconvex. Examples of such problems include decentralized compressed sensing and constrained quadratic programming problems, as well as many decentralized regularization problems. We extend the existing algorithms PG-EXTRA and ExtraPush to a new algorithm PG-ExtraPush for composite consensus optimization over a directed network. This algorithm takes advantage of the proximity operator like in PG-EXTRA to deal with the nonsmooth term, and employs the push-sum protocol like in ExtraPush to tackle the bias introduced by the directed network. With a proper step size, we show that PG-ExtraPush converges to an optimal solution at a linear rate under some regular assumptions. We conduct a series of numerical experiments to show the effectiveness of the proposed algorithm. Specifically, with a proper step size, PG-ExtraPush performs linear rates in most of cases, even in some nonconvex cases, and is significantly faster than Subgradient-Push, even if the latter uses a hand-optimized step size. The established theoretical results are also verified by the numerical results.
Recommendations
- ExtraPush for convex smooth decentralized optimization over directed networks
- EXTRA: an exact first-order algorithm for decentralized consensus optimization
- Decentralized proximal splitting algorithms for composite constrained convex optimization
- On arbitrary compression for decentralized consensus and stochastic optimization over directed networks
- Distributed quasi-monotone subgradient algorithm for nonsmooth convex optimization over directed graphs
Cites work
- A Proximal Gradient Algorithm for Decentralized Composite Optimization
- Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
- Breakdown points of affine equivariant estimators of multivariate location and covariance matrices
- Consensus in Ad Hoc WSNs With Noisy Links—Part I: Distributed Estimation of Deterministic Signals
- Decentralized Sparse Signal Recovery for Compressive Sleeping Wireless Sensor Networks
- Distributed iterative thresholding for ℓ0/ℓ1-regularized linear inverse problems
- Distributed Optimization Over Time-Varying Directed Graphs
- Distributed Sparse Linear Regression
- Distributed Subgradient Methods for Multi-Agent Optimization
- EXTRA: an exact first-order algorithm for decentralized consensus optimization
- ExtraPush for convex smooth decentralized optimization over directed networks
- Multi-Agent Distributed Optimization via Inexact Consensus ADMM
- On Nonconvex Decentralized Gradient Descent
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
Cited in
(12)- Multi-step-length gradient iterative algorithm for equation-error type models
- On the linear convergence of two decentralized algorithms
- On arbitrary compression for decentralized consensus and stochastic optimization over directed networks
- An efficient PID-based optimizer loop and its application in De Jong's functions minimization and quadratic regression problems
- ExtraPush for convex smooth decentralized optimization over directed networks
- EXTRA: an exact first-order algorithm for decentralized consensus optimization
- Distributed regularized online optimization using forward-backward splitting
- A fixed step distributed proximal gradient push‐pull algorithm based on integral quadratic constraint
- A decentralized smoothing quadratic regularization algorithm for composite consensus optimization with non-Lipschitz singularities
- A Unified Framework for Continuous-Time Unconstrained Distributed Optimization
- A decentralized Nesterov gradient method for stochastic optimization over unbalanced directed networks
- Multi-step-length gradient iterative method for separable nonlinear least squares problems.
This page was built for publication: A fast proximal gradient algorithm for decentralized composite optimization over directed networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1680665)
