TY - GEN
T1 - Asynchronous distributed alternating direction method of multipliers
T2 - 41st IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016
AU - Chang, Tsung Hui
AU - Hong, Mingyi
AU - Liao, Wei Cheng
AU - Wang, Xiangfeng
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/5/18
Y1 - 2016/5/18
N2 - 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.
AB - 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.
KW - Distributed optimization
KW - alternating direction method of multipliers
KW - asynchronous algorithm
UR - https://www.scopus.com/pages/publications/84964605623
U2 - 10.1109/ICASSP.2016.7472585
DO - 10.1109/ICASSP.2016.7472585
M3 - 会议稿件
AN - SCOPUS:84964605623
T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
SP - 4781
EP - 4785
BT - 2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 20 March 2016 through 25 March 2016
ER -