Communication-Censored ADMM for Decentralized Consensus Optimization

By Yaohua Liu, Wei Xu, Gang Wu, Zhi Tian, Qing Ling. 2019

94 citations recorded by the source corpus.

In this paper, we devise a communication-efficient decentralized algorithm, named as communication-censored alternating direction method of multipliers (ADMM) (COCA), to solve a convex consensus optimization problem defined over a network. Similar to popular decentralized consensus optimization algorithms such as ADMM, at every iteration of COCA, a node exchanges its local variable with neighbors, and then updates its local variable according to the received neighboring variables and its local cost function. A different feature of COCA is that a node is not allowed to transmit its local variable to neighbors, if this variable is not sufficiently different to the previously transmitted one. The sufficiency of the difference is evaluated by a properly designed censoring function. Though this censoring strategy may slow down the optimization process, it effectively reduces the communication cost. We prove that when the censoring function is properly chosen, COCA converges to an optimal solution of the convex consensus optimization problem. Furthermore, if the local cost functions are strongly convex, COCA has a fast linear convergence rate. Numerical experiments demonstrate that, given a target solution accuracy, COCA is able to significantly reduce the overall communication cost compared to existing algorithms including ADMM, and hence fits for applications where network communication is a bottleneck.

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

Citations in the corpus

GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, background): “For a large scale network, the communication cost often becomes dominant compared to the computation time, calling for communication eﬃcient distributed optimization (Zhang et al., 2012; McMahan et al., 2017; Park et al., 2018; Jordan et al., 2018; Liu et al., 2019; Sriranga et al., 2019).”
Communication Efficient Distributed Learning with Censored, Quantized, and Generalized Group ADMM (2020, methodology): “For example, using C-ADMM, each worker needs to ﬁnd the transmission power that achieves the transmission rate R = (32 d/ 1 ms ) bits/sec.”
Q-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning (2019, unknown): “…uses per communication round, exchanging model updates can be restricted only to the workers whose computation delays are less than a target threshold [44], or to the workers whose updates are sufﬁciently changed from the preceding updates, with respect to gradients [17], or model parameters [40].”