Linearly convergent decentralized consensus optimization with the alternating direction method of multipliers

Wei Shi, Qing Ling, Kun Yuan, Gang Wu, Wotao Yin

Abstract

In the decentralized consensus optimization problem, a network of agents minimizes the summation of their local objective functions on a common set of variables, allowing only information exchange among neighbors. The alternating direction method of multipliers (ADMM) has been shown to be a powerful tool for solving the problem with empirically fast convergence. This paper establishes the linear convergence rate of the ADMM in decentralized consensus optimization. The theoretical convergence rate is a function of the network topology, properties of the local objective functions, and the algorithm parameter. This result not only gives a performance guarantee for the ADMM but also provides a guideline to accelerate its convergence rate for the decentralized consensus optimization problems.
BibTeX
@inproceedings{shi2013linearly,
  author = {Wei Shi and Qing Ling and Kun Yuan and Gang Wu and Wotao Yin},
  title = {{Linearly convergent decentralized consensus optimization with the alternating direction method of multipliers}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2013},
  doi = {10.1109/icassp.2013.6638534},
}

Loading related content...

Figure