Revisiting the Primal-Dual Method of Multipliers for Optimisation Over Centralised Networks

The primal-dual method of multipliers (PDMM) was originally designed for solving a decomposable optimisation problem over a general network. In this paper, we revisit PDMM for optimisation over a centralised network. We first note that the recently proposed method FedSplit [1] implements PDMM for a...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on signal and information processing over networks 2022, Vol.8, p.228-243
Main Authors: Zhang, Guoqiang, Niwa, Kenta, Kleijn, W. Bastiaan
Format: Article
Language:English
Subjects:
Convergence
Distributed optimisation
fedsplit
Handheld computers
Information processing
Multipliers
Optimization
Parameters
PDMM
Peer-to-peer computing
SCAFFOLD
Scaffolds
Scalability
Servers
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The primal-dual method of multipliers (PDMM) was originally designed for solving a decomposable optimisation problem over a general network. In this paper, we revisit PDMM for optimisation over a centralised network. We first note that the recently proposed method FedSplit [1] implements PDMM for a centralised network. In [1], Inexact FedSplit (i.e., gradient based FedSplit) was also studied both empirically and theoretically. We identify the cause for the poor reported performance of Inexact FedSplit, which is due to the suboptimal initialisation in the gradient operations at the client side. To fix the issue of Inexact FedSplit, we propose two versions of Inexact PDMM, which are referred to as gradient-based PDMM (GPDMM) and accelerated GPDMM (AGPDMM), respectively. AGPDMM accelerates GPDMM at the cost of transmitting two times the number of parameters from the server to each client per iteration compared to GPDMM. We provide a new convergence bound for GPDMM for a class of convex optimisation problems. Our new bounds are tighter than those derived for Inexact FedSplit. We also investigate the update expressions of AGPDMM and SCAFFOLD to find their similarities. It is found that when the number K of gradient steps at the client side per iteration is K=1 , both AGPDMM and SCAFFOLD reduce to vanilla gradient descent with proper parameter setup. Experimental results indicate that AGPDMM converges faster than SCAFFOLD when K >1 while GPDMM converges slightly slower than SCAFFOLD.
ISSN:2373-776X
2373-776X
2373-7778
DOI:10.1109/TSIPN.2022.3161077