Decentralized Consensus Optimization with Asynchrony and Delay

Tianyu Wu, Kun Yuan, Qing Ling, Wotao Yin, and Ali H. Sayed

Status:

Overview

We propose an asynchronous, decentralized algorithm for consensus optimization. The algorithm runs in a network of agents, where the agents perform local computation and communicate with neighbors. We design our algorithm so that the agents can compute and communicate independently, at different times, for different durations. This reduces the time that would be wasted in waiting for the slowest agent or longest communication delay. Furthermore, it also eliminates the need for a global clock.

Mathematically, our algorithm involves both primal and dual variables, uses fixed parameters, and has convergence guarantees under a random agent assumption. The delays can be either bounded or unbounded.

When running synchronously, its performance matches the current state-of-the-art algorithms (for example, PG-EXTRA, which however fails to converge without synchronization.) Through simulations, we demonstrate that our asynchronous algorithm converges much faster that it does under synchronization.

 

Citation

T. Wu, K. Yuan, Q. Ling, W. Yin, and A.H. Sayed, Decentralized consensus optimization with asynchrony and delay, in Proceedings of IEEE Asilomar Conference on Signals, Systems, and Computers, 2016.

Related papers


« Back