A Primal-Dual SGD Algorithm for Distributed Nonconvex Optimization  

作　　者：Xinlei Yi Shengjun Zhang Tao Yang Tianyou Chai Karl Henrik Johansson 

机构地区：[1]Division of Decision and Control Systems,School of Electrical Engineering and Computer Science,KTH Royal Institute of Technology,and also affiliated with the Digital Futures,Stockholm 10044,Sweden [2]Department of Electrical Engineering,University of North Texas,Denton,TX 76203 USA [3]IEEE [4]State Key Laboratory of Synthetical Automation for Process Industries,Northeastern University,Shenyang 110819,China

出　　处：《IEEE/CAA Journal of Automatica Sinica》2022年第5期812-833,共22页自动化学报（英文版）

基　　金：supported by the Knut and Alice Wallenberg Foundation;the Swedish Foundation for Strategic Research;the Swedish Research Council;the National Natural Science Foundation of China(62133003,61991403,61991404,61991400)。

摘　　要：The distributed nonconvex optimization problem of minimizing a global cost function formed by a sum of n local cost functions by using local information exchange is considered.This problem is an important component of many machine learning techniques with data parallelism,such as deep learning and federated learning.We propose a distributed primal-dual stochastic gradient descent(SGD)algorithm,suitable for arbitrarily connected communication networks and any smooth(possibly nonconvex)cost functions.We show that the proposed algorithm achieves the linear speedup convergence rate O(1/(√nT))for general nonconvex cost functions and the linear speedup convergence rate O(1/(nT)) when the global cost function satisfies the Polyak-Lojasiewicz(P-L)condition,where T is the total number of iterations.We also show that the output of the proposed algorithm with constant parameters linearly converges to a neighborhood of a global optimum.We demonstrate through numerical experiments the efficiency of our algorithm in comparison with the baseline centralized SGD and recently proposed distributed SGD algorithms.

关 键 词：Distributed nonconvex optimization linear speedup Polyak-Lojasiewicz(P-L)condition primal-dual algorithm stochastic gradient descent 

分 类 号：O224[理学—运筹学与控制论]