Distributed Optimization Over Dependent Random Networks

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.

Automated summary

We researched the averaging-based distributed optimization solvers over random networks. We proved the convergence of such schemes for a broad class of dependent weight-matrix sequences. Our work shows the robustness of distributed optimization results to link failure and provides a new tool for synthesizing distributed optimization algorithms. The secondary results and martingale-type results we established for proving the main theorem might be of interest to broader research in distributed computation over random networks.