# Linear convergence in optimization over directed graphs with row-stochastic matrices

arXiv: https://arxiv.org/abs/1611.06160 · HTML: https://mlsanity.com/paper/1611.06160/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2016.

## Built on by (most cited first, 12 of 12)

- [RelaySum for Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2110.04175/) (2021)
- [Distributed Adaptive Learning Under Communication Constraints](https://mlsanity.com/paper/2112.02129/) (2021)
- [Asynchronous speedup in decentralized optimization](https://mlsanity.com/paper/2106.03585/) (2021)
- [Decentralized Federated Learning with Gradient Tracking over Time-Varying Directed Networks](https://mlsanity.com/paper/2409.17189/) (2024)
- [Federated Learning in Wireless Networks via Over-the-Air Computations](https://mlsanity.com/paper/2305.04630/) (2023)
- [Locally Differentially Private Gradient Tracking for Distributed Online Learning over Directed Graphs](https://mlsanity.com/paper/2310.16105/) (2023)
- [Decentralized Multi-Task Online Convex Optimization Under Random Link Failures](https://mlsanity.com/paper/2401.02011/) (2024)
- [Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs](https://mlsanity.com/paper/2107.12065/) (2021)
- [Decentralized Optimization in Time-Varying Networks with Arbitrary Delays](https://mlsanity.com/paper/2405.19513/) (2024)
- [Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2601.11435/) (2026)
- [Distributed Optimization via Kernelized Multi-armed Bandits](https://mlsanity.com/paper/2312.04719/) (2023)
- [AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network](https://mlsanity.com/paper/2606.19185/) (2026)

## Abstract (arXiv)

This paper considers a distributed optimization problem over a multi-agent network, in which the objective function is a sum of individual cost functions at the agents. We focus on the case when communication between the agents is described by a directed graph. Existing distributed optimization algorithms for directed graphs require at least the knowledge of the neighbors' out-degree at each agent (due to the requirement of column-stochastic matrices). In contrast, our algorithm requires no such knowledge. Moreover, the proposed algorithm achieves the best known rate of convergence for this class of problems, O(μk) for 0<μ<1, where k is the number of iterations, given that the objective functions are strongly-convex and have Lipschitz-continuous gradients. Numerical experiments are also provided to illustrate the theoretical findings.