Decentralized Optimization Over Time-Varying Directed Graphs With Row and Column-Stochastic Matrices
Fakhteh Saadatniaki, Ran Xin, Usman A. Khan
Abstract
In this article, we provide a distributed optimization algorithm, termed as TV-AB, that minimizes a sum of convex functions over time-varying, random directed graphs. Contrary to the existing work, the algorithm we propose does not require eigenvector estimation to estimate the (non-1) Perron eigenvector of a stochastic matrix. Instead, the proposed approach relies on a novel information mixing approach that exploits both rowand column-stochastic weights to achieve agreement toward the optimal solution when the underlying graph is directed. We show that TV-AB converges linearly to the optimal solution when the global objective is smooth and strongly convex, and the underlying time-varying graphs exhibit bounded connectivity, i.e., a union of every C consecutive graphs is strongly connected. We derive the convergence results based on the stability analysis of a linear system of inequalities along with a matrix perturbation argument. Simulations confirm the findings in this article.