Asynchronous distributed alternating direction method of multipliers: Algorithm and convergence analysis

Tsung Hui Chang, Mingyi Hong, Wei Cheng Liao, Xiangfeng Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

Alternating direction method of multipliers (ADMM) has been recognized as an efficient approach for solving many large-scale learning problems over a computer cluster. However, traditional synchronized computation does not scale well with the problem size, as the speed of the algorithm is limited by the slowest workers. In this paper, we propose an asynchronous distributed ADMM (AD- ADMM) which can effectively improve the time efficiency of distributed optimization. Our main interest lies in characterizing the convergence conditions of the AD-ADMM, under the popular partially asynchronous model which is defined based on a maximum tolerable delay in the network. Specifically, by considering general and possibly non-convex cost functions, we show that the AD-ADMM converges to the set of Karush-Kuhn-Tucker (KKT) points as long as the algorithm parameters are chosen appropriately according to the network delay. We also show that the asynchrony of ADMM has to be handled with care, as a slightly different implementation can significantly jeopardize the algorithm convergence.

Original languageEnglish (US)
Title of host publication2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages4781-4785
Number of pages5
ISBN (Electronic)9781479999880
DOIs
StatePublished - May 18 2016
Event41st IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Shanghai, China
Duration: Mar 20 2016Mar 25 2016

Publication series

NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Volume2016-May
ISSN (Print)1520-6149

Other

Other41st IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016
CountryChina
CityShanghai
Period3/20/163/25/16

Keywords

  • Distributed optimization
  • alternating direction method of multipliers
  • asynchronous algorithm

Fingerprint Dive into the research topics of 'Asynchronous distributed alternating direction method of multipliers: Algorithm and convergence analysis'. Together they form a unique fingerprint.

  • Cite this

    Chang, T. H., Hong, M., Liao, W. C., & Wang, X. (2016). Asynchronous distributed alternating direction method of multipliers: Algorithm and convergence analysis. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Proceedings (pp. 4781-4785). [7472585] (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 2016-May). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICASSP.2016.7472585