A Primal-Dual SGD Algorithm for Distributed Nonconvex Optimization

doi:10.1109/JAS.2022.105554

CASIA OpenIR > 学术期刊 > IEEE/CAA Journal of Automatica Sinica

	A Primal-Dual SGD Algorithm for Distributed Nonconvex Optimization
	Xinlei Yi; Shengjun Zhang; Tao Yang; Tianyou Chai; Karl Henrik Johansson
发表期刊	IEEE/CAA Journal of Automatica Sinica
ISSN	2329-9266
	2022
卷号	9 期号:5 页码:812-833
摘要	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 ${{{\cal{O}}(1/\sqrt{nT})}}$ for general nonconvex cost functions and the linear speedup convergence rate $ {\cal{O}}(1/(nT))$ when the global cost function satisfies the Polyak-Łojasiewicz (P-Ł) 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-Łojasiewicz (P-Ł) condition primal-dual algorithm stochastic gradient descent
DOI	10.1109/JAS.2022.105554
引用统计	被引频次：9[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://ir.ia.ac.cn/handle/173211/47546
专题	学术期刊_IEEE/CAA Journal of Automatica Sinica
推荐引用方式 GB/T 7714	Xinlei Yi,Shengjun Zhang,Tao Yang,et al. A Primal-Dual SGD Algorithm for Distributed Nonconvex Optimization[J]. IEEE/CAA Journal of Automatica Sinica,2022,9(5):812-833.
APA	Xinlei Yi,Shengjun Zhang,Tao Yang,Tianyou Chai,&Karl Henrik Johansson.(2022).A Primal-Dual SGD Algorithm for Distributed Nonconvex Optimization.IEEE/CAA Journal of Automatica Sinica,9(5),812-833.
MLA	Xinlei Yi,et al."A Primal-Dual SGD Algorithm for Distributed Nonconvex Optimization".IEEE/CAA Journal of Automatica Sinica 9.5(2022):812-833.

条目包含的文件		下载所有文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
JAS-2022-0153.pdf（2533KB）	期刊论文	出版稿	开放获取	CC BY-NC-SA	浏览下载