Distributed Optimization Over Time-Varying Graphs With Imperfect Sharing of Information

• 成果类型: Article
• 署名作者: Reisizadeh, Hadi; Touri, Behrouz; Mohajer, Soheil
• 署名单位: University of Minnesota System; University of Minnesota Twin Cities; University of California System; University of California San Diego
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3207866
• 发表日期: 2023
• 页码: 4420-4427
• 关键词: Convex optimization; distributed multiagent system; distributed optimization; gradient descent algorithms; time-varying graphs

摘要

We study strongly convex distributed optimization problems where a set of agents are interested in solving a separable optimization problem collaboratively. In this article, we propose and study a two-time-scale decentralized gradient descent algorithm for a broad class of lossy sharing of information over time-varying graphs. One time-scale fades out the (lossy) incoming information from neighboring agents, and one time-scale regulates the local loss functions' gradients. We show that assuming a proper choice of step-size sequences, certain connectivity conditions, and bounded gradients along the trajectory of the dynamics, the agents' estimates converge to the optimal solution with the rate of O(T-1/2). We also provide novel tools to study distributed optimization with diminishing averaging weights over time-varying graphs.