Skip to main content
Article
Asynchronous Distributed ADMM for Large-Scale Optimization—Part II: Linear Convergence Analysis and Numerical Performance
IEEE Transactions on Signal Processing
  • Tsung-Hui Chang, The Chinese University of Hong Kong
  • Wei-Cheng Lao, University of Minnesota - Twin Cities
  • Mingyi Hong, Iowa State University
  • Xiangfeng Wang, East China Normal University
Document Type
Article
Publication Version
Accepted Manuscript
Publication Date
1-1-2016
DOI
10.1109/TSP.2016.2537261
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.
Comments

This is a manuscript of an article from IEEE Transactions on Signal Processing 64 (2016): 3131, DOI: 10.1109/TSP.2016.2537261. Posted with permission.

Rights
© 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Copyright Owner
IEEE
Language
en
File Format
application/pdf
Citation Information
Tsung-Hui Chang, Wei-Cheng Lao, Mingyi Hong and Xiangfeng Wang. "Asynchronous Distributed ADMM for Large-Scale Optimization—Part II: Linear Convergence Analysis and Numerical Performance" IEEE Transactions on Signal Processing Vol. 64 Iss. 12 (2016) p. 3131 - 3144
Available at: http://works.bepress.com/mingyi_hong/22/