Distributed Optimization Over Dependent Random Networks

• 成果类型: Article
• 署名作者: Aghajan, Adel; Touri, Behrouz
• 署名单位: University of California System; University of California Santa Barbara; University of California System; University of California San Diego
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3216970
• 发表日期: 2023
• 页码: 4812-4826
• 关键词: Convex optimization; directed graph; distributed optimization; random networks; spanning tree

摘要

We study the averaging-based distributed optimization solvers over random networks. We show a general result on the convergence of such schemes using weight matrices that are row-stochastic almost surely and column-stochastic in expectation for a broad class of dependent weight-matrix sequences. In addition to implying many of the previously known results on this domain, our work shows the robustness of distributed optimization results to link failure. Also, it provides a new tool for synthesizing distributed optimization algorithms. To prove our main theorem, we establish new results on the rate of convergence analysis of averaging dynamics over (dependent) random networks. These secondary results, along with the required martingale-type results to establish them, might be of interest to broader research endeavors in distributed computation over random networks.