Optimization over time-varying directed graphs with row and column-stochastic matrices

Abstract

In this paper, we provide a distributed optimization algorithm, termed as TV-$\mathcal{A}\mathcal{B}$, 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 row- and column-stochastic weights to achieve agreement towards the optimal solution when the underlying graph is directed. We show that TV-$\mathcal{A}\mathcal{B}$ 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 paper.

References in corpus (7)

• Constrained Consensus
• Decentralized Quasi-Newton Methods
• Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
• Convergence Rates of Distributed Nesterov-like Gradient Methods on Random Networks
• Calculating Determinants of Block Matrices
• Online Learning of Dynamic Parameters in Social Networks
• Achieving Linear Convergence in Distributed Asynchronous Multi-agent Optimization

Cited by in corpus (3)

• Distributed stochastic optimization with gradient tracking over strongly-connected networks
• Variance-Reduced Decentralized Stochastic Optimization with Gradient Tracking--Part I: GT-SAGA
• A Survey of Distributed Optimization Methods for Multi-Robot Systems