A Coordinate Descent Primal-Dual Algorithm and Application to Distributed Asynchronous Optimization

By Pascal Bianchi, Walid Hachem, Franck Iutzeler. 2014

134 citations recorded by the source corpus.

Based on the idea of randomized coordinate descent of α-averaged operators, a randomized primal-dual optimization algorithm is introduced, where a random subset of coordinates is updated at each iteration. The algorithm builds upon a variant of a recent (deterministic) algorithm proposed by Vũ and Condat that includes the well-known Alternating Direction Method of Multipliers as a particular case. The obtained algorithm is used to solve asynchronously a distributed optimization problem. A network of agents, each having a separate cost function containing a differentiable term, seek to find a consensus on the minimum of the aggregate objective. The method yields an algorithm where at each iteration, a random subset of agents wake up, update their local estimates, exchange some data with their neighbors, and go idle. Numerical results demonstrate the attractive performance of the method. The general approach can be naturally adapted to other situations where coordinate descent convex optimization algorithms are used with a random choice of the coordinates.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Martin Jaggi
2. Michael G. Rabbat
3. Guanghui Lan
4. Yi Zhou
5. Mahmoud Assran
6. Lie He
7. An Bian
8. Sebastian U. Stich

In Computational Mechanics

1. Michael G. Rabbat
2. Guanghui Lan
3. Yi Zhou
4. Martin Jaggi
5. Mahmoud Assran
6. An Bian
7. Lie He
8. Simon Lacoste-Julien

In Computer Networks and Communications

1. Martin Jaggi
2. Guanghui Lan
3. Yi Zhou
4. Mahmoud Assran
5. An Bian
6. Lie He
7. Michael G. Rabbat
8. Sebastian U. Stich

Citations in the corpus

• COLA: Decentralized Linear Learning (2018, background): “DADMM+ [Bianchi et al., 2016] is a different primal-dual approach with more efficient closed-form updates in each step (as compared to ADMM), and is proven to converge but without a rate.”
• Asynchronous Gradient Push (2018, background): “, sparse Poisson point process [28], randomized single activation [29], [30], randomized multi-activation [31]–[34]).”
• Asynchronous Decentralized Accelerated Stochastic Gradient Descent (2018, background): “, [23], [25], [26], [27]) has been studied in different asynchronous setting.”
• Decentralized Consensus Optimization With Asynchrony and Delays (2016, unknown): “Consider a strongly connected network G = {V , E} with agents V = { 1 , 2 , · · · , n } and undirected edges E = { 1 , 2 , · · · , m } .”