Distributed deterministic asynchronous algorithms in time-varying graphs through Dykstra splitting
From MaRDI portal
Abstract: Consider the setting where each vertex of a graph has a function, and communications can only occur between vertices connected by an edge. We wish to minimize the sum of these functions. For the case when each function is the sum of a strongly convex quadratic and a convex function, we propose a distributed version of Dykstra's algorithm. The computations to optimize the dual objective function can run asynchronously without a global clock, and in a distributed manner without a central controller. Convergence to the primal minimizer is deterministic instead of being probabilistic, and is guaranteed as long as in each cycle, the edges where two-way communications occur connects all vertices. We also look at an accelerated algorithm, and an algorithm for the case when the functions on the nodes are not strongly convex.
Recommendations
- Distributed asynchronous deterministic and stochastic gradient optimization algorithms
- Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
- Distributed asynchronous algorithms with stochastic delays for constrained optimization problems with conditions of time drift
- Distributed asynchronous incremental subgradient methods
- A distributed flexible delay-tolerant proximal gradient algorithm
Cites work
- A Coordinate Descent Primal-Dual Algorithm and Application to Distributed Asynchronous Optimization
- A cyclic projection algorithm via duality
- A Distributed Boyle--Dykstra--Han Scheme
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
- A splitting algorithm for dual monotone inclusions involving cocoercive operators
- A successive projection method
- Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
- Alternating projection methods.
- An Algorithm for Restricted Least Squares Regression
- An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization
- ARock: an algorithmic framework for asynchronous parallel coordinate updates
- Asynchronous block-iterative primal-dual decomposition methods for monotone inclusions
- Asynchronous Distributed Optimization Via Randomized Dual Proximal Gradient
- Asynchronous parallel algorithms for nonconvex optimization
- Best approximation in inner product spaces
- Constrained Consensus and Optimization in Multi-Agent Networks
- Convergence of a block coordinate descent method for nondifferentiable minimization
- Convex analysis and monotone operator theory in Hilbert spaces
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Distributed Optimization Over Time-Varying Directed Graphs
- Distributed stochastic subgradient projection algorithms for convex optimization
- Dual block-coordinate forward-backward algorithm with application to deconvolution and deinterlacing of video sequences
- Dualization of signal recovery problems
- EXTRA: an exact first-order algorithm for decentralized consensus optimization
- General Projective Splitting Methods for Sums of Maximal Monotone Operators
- scientific article; zbMATH DE number 3833218 (Why is no real title available?)
- scientific article; zbMATH DE number 5454133 (Why is no real title available?)
- scientific article; zbMATH DE number 3973706 (Why is no real title available?)
- On Projection Algorithms for Solving Convex Feasibility Problems
- On the convergence of alternating minimization for convex programming with applications to iteratively reweighted least squares and decomposition schemes
- On the convergence of block coordinate descent type methods
- On the Convergence Rate of Incremental Aggregated Gradient Algorithms
- Proximity for sums of composite functions
- The supporting halfspace-quadratic programming strategy for the dual of the best approximation problem
- Two generalizations of Dykstra's cyclic projections algorithm
Cited in
(4)- Dykstra's splitting and an approximate proximal point algorithm for minimizing the sum of convex functions
- Asynchronous deterministic rendezvous in graphs
- A Fenchel dual gradient method enabling regularization for nonsmooth distributed optimization over time-varying networks
- Convergence Rate Analysis of a Dykstra-Type Projection Algorithm
This page was built for publication: Distributed deterministic asynchronous algorithms in time-varying graphs through Dykstra splitting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4624929)
