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
 |
| 出版日期 | 2022 |
| 卷号 | 9期号:5页码:812-833 |
| 关键词 | Distributed nonconvex optimization linear speedup Polyak-Łojasiewicz (P-Ł) condition primal-dual algorithm stochastic gradient descent |
| ISSN号 | 2329-9266 |
| DOI | 10.1109/JAS.2022.105554 |
| 英文摘要 | 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. |
| 源URL | [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. |
入库方式： OAI收割
来源：自动化研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。