Asynchronous Distributed ADMM for Large-Scale Optimization - Part II: Linear Convergence Analysis and Numerical Performance

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

Research output: Contribution to journalArticlepeer-review

36 Scopus citations

Abstract

The alternating direction method of multipliers (ADMM) has been recognized as a versatile approach for solving modern large-scale machine learning and signal processing problems efficiently. When the data size and/or the problem dimension is large, a distributed version of ADMM can be used, which is capable of distributing the computation load and the data set to a network of computing nodes. Unfortunately, a direct synchronous implementation of such algorithm does not scale well with the problem size, as the algorithm speed is limited by the slowest computing nodes. To address this issue, in a companion paper, we have proposed an asynchronous distributed ADMM (AD-ADMM) and studied its worst-case convergence conditions. In this paper, we further the study by characterizing the conditions under which the AD-ADMM achieves linear convergence. Our conditions as well as the resulting linear rates reveal the impact that various algorithm parameters, network delay, and network size have on the algorithm performance. To demonstrate the superior time efficiency of the proposed AD-ADMM, we test the AD-ADMM on a high-performance computer cluster by solving a large-scale logistic regression problem.

Original languageEnglish (US)
Article number7423796
Pages (from-to)3131-3144
Number of pages14
JournalIEEE Transactions on Signal Processing
Volume64
Issue number12
DOIs
StatePublished - Jun 15 2016

Bibliographical note

Funding Information:
The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Ana Perez-Neira. T.-H. Chang is supported by NSFC, China, Grant No. 61571385. M. Hong is supported by NFS Grant No. CCF-1526078, and AFOSR, Grant No. 15RT0767. X. Wang is supported by Shanghai YangFan No. 15YF1403400 and NSFC No. 11501210.

Publisher Copyright:
© 1991-2012 IEEE.

Keywords

  • ADMM
  • Distributed optimization
  • asynchronous
  • consensus optimization

Fingerprint

Dive into the research topics of 'Asynchronous Distributed ADMM for Large-Scale Optimization - Part II: Linear Convergence Analysis and Numerical Performance'. Together they form a unique fingerprint.

Cite this