Decentralized Consensus Optimization With Asynchrony and Delays

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

12 citations recorded by the source corpus.

We propose an asynchronous, decentralized algorithm for consensus optimization. The algorithm runs over a network in which the agents communicate with their neighbors and perform local computation. In the proposed algorithm, each agent can compute and communicate independently at different times, for different durations, with the information it has even if the latest information from its neighbors is not yet available. Such an asynchronous algorithm reduces the time that agents would otherwise waste idle because of communication delays or because their neighbors are slower. It also eliminates the need for a global clock for synchronization. Mathematically, the algorithm involves both primal and dual variables, uses fixed step-size parameters, and provably converges to the exact solution under a random agent assumption and both bounded and unbounded delay assumptions. When running synchronously, the algorithm performs just as well as existing competitive synchronous algorithms such as PG-EXTRA, which diverges without synchronization. Numerical experiments confirm the theoretical findings and illustrate the performance of the proposed algorithm.

Subfields: 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 Computer Networks and Communications

1. Kun Yuan
2. Ali H. Sayed
3. Ji Liu
4. Wotao Yin
5. Hanlin Tang
6. Qing Ling
7. Xiangru Lian
8. Martin Jaggi

Citations in the corpus

• DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression (2019, methodology): “ahdavian et al. (2015); Recht et al. (2011). In Lian et al. (2015); Liu et al. (2015) authors give theoretical guarantee for acceleration of Asynchronous SGD over Synchronous SGD. Lian et al. (2018); Wu et al. (2018) further explore the feasibility of Asynchronous SGD under decentralized training. 2”
• COLA: Decentralized Linear Learning (2018, methodology): “For the decentralized, asynchronous consensus optimization, [Wu et al., 2018] extends the existing PG-EXTRA and proves convergence of the algorithm.”
• Fast Convergence Rates of Distributed Subgradient Methods With Adaptive Quantization (2018, methodology): “Convergence rates of DSG optimization methods in the presence of communication delays have been studied in [22–25].”
• Decentralized consensus optimization with asynchrony and delays (2016, background): “A short version of this work appeared in the conference publication [1].”