Function Splitting and Quadratic Approximation of the Primal-Dual Method of Multipliers for Distributed Optimization over Graphs

Oconnor, M; Zhang, G; Kleijn, WB; Abhayapala, TD

Function Splitting and Quadratic Approximation of the Primal-Dual Method of Multipliers for Distributed Optimization over Graphs

Oconnor, M Zhang, G

Kleijn, WB Abhayapala, TD

Permalink

Publication Type:: Journal Article
Citation:: IEEE Transactions on Signal and Information Processing over Networks, 2018, 4 (4), pp. 656 - 666
Issue Date:: 2018-12-01

Closed Access

	Filename	Description	Size
	08292929.pdf	Published Version	668.1 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Oconnor, M	en_US
dc.contributor.author	Zhang, G https://orcid.org/0000-0003-4521-542X	en_US
dc.contributor.author	Kleijn, WB	en_US
dc.contributor.author	Abhayapala, TD	en_US
dc.date.issued	2018-12-01	en_US
dc.identifier.citation	IEEE Transactions on Signal and Information Processing over Networks, 2018, 4 (4), pp. 656 - 666	en_US
dc.identifier.uri	http://hdl.handle.net/10453/131946
dc.description.abstract	© 2015 IEEE. We propose two algorithms based on the Primal-Dual Method of Multipliers (PDMM) to be used in distributed network optimization: Function Split PDMM (FS-PDMM) and Quadratically Approximated PDMM (QA-PDMM). Our approaches simplify the local subproblems that must be solved for each node, at each update iteration, improving computational efficiency at distributed processors. FS-PDMM allows for simplified updates of distributed problems involving regularized general convex functions, while QA-PDMM allows smooth local cost functions to be approximated quadratically. In both cases, this leads to iterative updates that require mostly simple and analytic computation rather than numerical solutions to more complex subproblems, particularly when using common regularization functions such as the l-1 and l-2 norms. We show that FS-PDMM is theoretically equivalent to performing conventional PDMM on a network twice the size as the physical network, and prove convergence for QA-PDMM for a common class of problems. Experimentally, we demonstrate convergence and reduction in computational complexity for elastic net regularized least squares and ridge regularized logistic regression.	en_US
dc.relation.ispartof	IEEE Transactions on Signal and Information Processing over Networks	en_US
dc.relation.isbasedon	10.1109/TSIPN.2018.2806844	en_US
dc.title	Function Splitting and Quadratic Approximation of the Primal-Dual Method of Multipliers for Distributed Optimization over Graphs	en_US
dc.type	Journal Article
utslib.citation.volume	4	en_US
utslib.for	0805 Distributed Computing	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
utslib.copyright.status	closed_access
pubs.issue	4	en_US
pubs.publication-status	Published	en_US
pubs.volume	4	en_US

Abstract:

© 2015 IEEE. We propose two algorithms based on the Primal-Dual Method of Multipliers (PDMM) to be used in distributed network optimization: Function Split PDMM (FS-PDMM) and Quadratically Approximated PDMM (QA-PDMM). Our approaches simplify the local subproblems that must be solved for each node, at each update iteration, improving computational efficiency at distributed processors. FS-PDMM allows for simplified updates of distributed problems involving regularized general convex functions, while QA-PDMM allows smooth local cost functions to be approximated quadratically. In both cases, this leads to iterative updates that require mostly simple and analytic computation rather than numerical solutions to more complex subproblems, particularly when using common regularization functions such as the l-1 and l-2 norms. We show that FS-PDMM is theoretically equivalent to performing conventional PDMM on a network twice the size as the physical network, and prove convergence for QA-PDMM for a common class of problems. Experimentally, we demonstrate convergence and reduction in computational complexity for elastic net regularized least squares and ridge regularized logistic regression.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/131946