Graph-aware Weighted Hybrid ADMM for Fast Decentralized Optimization

Meng Ma; Georgios B Giannakis

doi:10.1109/ACSSC.2018.8645558

Graph-aware Weighted Hybrid ADMM for Fast Decentralized Optimization

Meng Ma
, Georgios B Giannakis

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

Abstract

Distributed optimization has gained popularity in many areas because it can to cope with the increasing volume of data, and the corresponding demand for computational resources. A popular distributed solver is the alternating direction method of multipliers (ADMM). Fully decentralized (D) ADMM arises when node-to-node communications have to abide by the underlying network connectivity. DADMM's convergence however, slows down as the network diameter grows large. To deal with this challenge, the recently proposed hybrid (H) ADMM provides considerable performance boost over DADMM by exploiting local topology information. But HADMM only applies to unweighted graphs. The present contribution develops a weighted hybrid (WH) consensus-based ADMM approach that can deal with weighted graphs. The resultant scheme further improves the performance of HADMM through graph-aware weight tuning. Theoretical analysis offers convergence guarantees and establishes linear convergence rate, while numerical tests on various graphs demonstrate the WHADMM merits.

Original language	English (US)
Title of host publication	Conference Record of the 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018
Editors	Michael B. Matthews
Publisher	IEEE Computer Society
Pages	1881-1885
Number of pages	5
ISBN (Electronic)	9781538692189
DOIs	https://doi.org/10.1109/ACSSC.2018.8645558
State	Published - Jul 2 2018
Event	52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018 - Pacific Grove, United States Duration: Oct 28 2018 → Oct 31 2018

Publication series

Name	Conference Record - Asilomar Conference on Signals, Systems and Computers
Volume	2018-October
ISSN (Print)	1058-6393

Conference

Conference	52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018
Country/Territory	United States
City	Pacific Grove
Period	10/28/18 → 10/31/18

Bibliographical note

Funding Information:
This work is supported in part by NSF grants 10121, 12321, 12345.

Publisher Copyright:
© 2018 IEEE.

Keywords

ADMM
decentralized optimization
hybrid ADMM
weighted ADMM

Publisher link

10.1109/ACSSC.2018.8645558

Find It

Find It at U of M Libraries

Cite this

Ma, M., & Giannakis, G. B. (2018). Graph-aware Weighted Hybrid ADMM for Fast Decentralized Optimization. In M. B. Matthews (Ed.), Conference Record of the 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018 (pp. 1881-1885). Article 8645558 (Conference Record - Asilomar Conference on Signals, Systems and Computers; Vol. 2018-October). IEEE Computer Society. https://doi.org/10.1109/ACSSC.2018.8645558

Graph-aware Weighted Hybrid ADMM for Fast Decentralized Optimization. / Ma, Meng; Giannakis, Georgios B.
Conference Record of the 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018. ed. / Michael B. Matthews. IEEE Computer Society, 2018. p. 1881-1885 8645558 (Conference Record - Asilomar Conference on Signals, Systems and Computers; Vol. 2018-October).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Ma, M & Giannakis, GB 2018, Graph-aware Weighted Hybrid ADMM for Fast Decentralized Optimization. in MB Matthews (ed.), Conference Record of the 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018., 8645558, Conference Record - Asilomar Conference on Signals, Systems and Computers, vol. 2018-October, IEEE Computer Society, pp. 1881-1885, 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018, Pacific Grove, United States, 10/28/18. https://doi.org/10.1109/ACSSC.2018.8645558

Ma M, Giannakis GB. Graph-aware Weighted Hybrid ADMM for Fast Decentralized Optimization. In Matthews MB, editor, Conference Record of the 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018. IEEE Computer Society. 2018. p. 1881-1885. 8645558. (Conference Record - Asilomar Conference on Signals, Systems and Computers). doi: 10.1109/ACSSC.2018.8645558

@inproceedings{91e1767adac645c9b0fef1fa517b1b51,

title = "Graph-aware Weighted Hybrid ADMM for Fast Decentralized Optimization",

abstract = "Distributed optimization has gained popularity in many areas because it can to cope with the increasing volume of data, and the corresponding demand for computational resources. A popular distributed solver is the alternating direction method of multipliers (ADMM). Fully decentralized (D) ADMM arises when node-to-node communications have to abide by the underlying network connectivity. DADMM's convergence however, slows down as the network diameter grows large. To deal with this challenge, the recently proposed hybrid (H) ADMM provides considerable performance boost over DADMM by exploiting local topology information. But HADMM only applies to unweighted graphs. The present contribution develops a weighted hybrid (WH) consensus-based ADMM approach that can deal with weighted graphs. The resultant scheme further improves the performance of HADMM through graph-aware weight tuning. Theoretical analysis offers convergence guarantees and establishes linear convergence rate, while numerical tests on various graphs demonstrate the WHADMM merits.",

keywords = "ADMM, decentralized optimization, hybrid ADMM, weighted ADMM",

author = "Meng Ma and Giannakis, \{Georgios B\}",

note = "Funding Information: This work is supported in part by NSF grants 10121, 12321, 12345. Publisher Copyright: {\textcopyright} 2018 IEEE.; 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018 ; Conference date: 28-10-2018 Through 31-10-2018",

year = "2018",

month = jul,

day = "2",

doi = "10.1109/ACSSC.2018.8645558",

language = "English (US)",

series = "Conference Record - Asilomar Conference on Signals, Systems and Computers",

publisher = "IEEE Computer Society",

pages = "1881--1885",

editor = "Matthews, \{Michael B.\}",

booktitle = "Conference Record of the 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018",

}

TY - GEN

T1 - Graph-aware Weighted Hybrid ADMM for Fast Decentralized Optimization

AU - Ma, Meng

AU - Giannakis, Georgios B

PY - 2018/7/2

Y1 - 2018/7/2

N2 - Distributed optimization has gained popularity in many areas because it can to cope with the increasing volume of data, and the corresponding demand for computational resources. A popular distributed solver is the alternating direction method of multipliers (ADMM). Fully decentralized (D) ADMM arises when node-to-node communications have to abide by the underlying network connectivity. DADMM's convergence however, slows down as the network diameter grows large. To deal with this challenge, the recently proposed hybrid (H) ADMM provides considerable performance boost over DADMM by exploiting local topology information. But HADMM only applies to unweighted graphs. The present contribution develops a weighted hybrid (WH) consensus-based ADMM approach that can deal with weighted graphs. The resultant scheme further improves the performance of HADMM through graph-aware weight tuning. Theoretical analysis offers convergence guarantees and establishes linear convergence rate, while numerical tests on various graphs demonstrate the WHADMM merits.

AB - Distributed optimization has gained popularity in many areas because it can to cope with the increasing volume of data, and the corresponding demand for computational resources. A popular distributed solver is the alternating direction method of multipliers (ADMM). Fully decentralized (D) ADMM arises when node-to-node communications have to abide by the underlying network connectivity. DADMM's convergence however, slows down as the network diameter grows large. To deal with this challenge, the recently proposed hybrid (H) ADMM provides considerable performance boost over DADMM by exploiting local topology information. But HADMM only applies to unweighted graphs. The present contribution develops a weighted hybrid (WH) consensus-based ADMM approach that can deal with weighted graphs. The resultant scheme further improves the performance of HADMM through graph-aware weight tuning. Theoretical analysis offers convergence guarantees and establishes linear convergence rate, while numerical tests on various graphs demonstrate the WHADMM merits.

KW - ADMM

KW - decentralized optimization

KW - hybrid ADMM

KW - weighted ADMM

UR - https://www.scopus.com/pages/publications/85062994546

UR - https://www.scopus.com/pages/publications/85062994546#tab=citedBy

U2 - 10.1109/ACSSC.2018.8645558

DO - 10.1109/ACSSC.2018.8645558

M3 - Conference contribution

AN - SCOPUS:85062994546

T3 - Conference Record - Asilomar Conference on Signals, Systems and Computers

SP - 1881

EP - 1885

BT - Conference Record of the 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018

A2 - Matthews, Michael B.

PB - IEEE Computer Society

T2 - 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018

Y2 - 28 October 2018 through 31 October 2018

ER -

Graph-aware Weighted Hybrid ADMM for Fast Decentralized Optimization

Abstract

Publication series

Conference

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this