Function Splitting and Quadratic Approximation of the Primal-Dual Method of Multipliers for Distributed Optimization Over Graphs
Date
2018-02-15
Authors
O'Connor, Matthew
Zhang, Guoqiang
Kleijn, Willem Bastiaan
Abhayapala, Thushara
Journal Title
Journal ISSN
Volume Title
Publisher
IEEE
Abstract
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 l1 and l2 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.
Description
Keywords
distributed optimization, regularization, quadratic, PDMM, ADMM
Citation
Collections
Source
IEEE Transactions on Signal and Information Processing over Networks
Type
Journal article
Book Title
Entity type
Access Statement
License Rights
Restricted until
2037-12-31
Downloads
File
Description