# A linear algorithm for optimization over directed graphs with geometric convergence

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Mar 2018.

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

- [RelaySum for Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2110.04175/) (2021)
- [BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning](https://mlsanity.com/paper/2111.04287/) (2021)
- [Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks](https://mlsanity.com/paper/2106.07243/) (2021)
- [Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization](https://mlsanity.com/paper/2104.02596/) (2021)
- [Decentralized Event-Triggered Federated Learning with Heterogeneous Communication Thresholds](https://mlsanity.com/paper/2204.03726/) (2022)
- [Decentralized Directed Collaboration for Personalized Federated Learning](https://mlsanity.com/paper/2405.17876/) (2024)
- [Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable](https://mlsanity.com/paper/2503.20117/) (2025)
- [Asymmetrically Decentralized Federated Learning](https://mlsanity.com/paper/2310.05093/) (2023)
- [Distributed saddle point problems for strongly concave-convex functions](https://mlsanity.com/paper/2202.05812/) (2022)
- [Decentralized Federated Learning with Gradient Tracking over Time-Varying Directed Networks](https://mlsanity.com/paper/2409.17189/) (2024)
- [Variance reduced stochastic optimization over directed graphs with row and column stochastic weights](https://mlsanity.com/paper/2202.03346/) (2022)
- [Robust Fully-Asynchronous Methods for Distributed Training over General Architecture](https://mlsanity.com/paper/2307.11617/) (2023)
- [Communication Efficient ConFederated Learning: An Event-Triggered SAGA Approach](https://mlsanity.com/paper/2402.18018/) (2024)
- [Quantization Avoids Saddle Points in Distributed Optimization](https://mlsanity.com/paper/2403.10423/) (2024)
- [Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs](https://mlsanity.com/paper/2107.12065/) (2021)
- [Push--Pull with Device Sampling](https://mlsanity.com/paper/2206.04113/) (2022)
- [Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2601.11435/) (2026)
- [Resource-Constrained Decentralized Federated Learning via Personalized Event-Triggering](https://mlsanity.com/paper/2211.12640/) (2022)
- [Accelerated Distributed Aggregative Optimization](https://mlsanity.com/paper/2304.08051/) (2023)
- [Distributed Learning over Arbitrary Topology: Linear Speed-Up with Polynomial Transient Time](https://mlsanity.com/paper/2503.16123/) (2025)
- [Diffusion Learning with Partial Agent Participation and Local Updates](https://mlsanity.com/paper/2505.11307/) (2025)
- [Local Updates in Distributed Optimization: Provable Acceleration and Topology Effects](https://mlsanity.com/paper/2601.03442/) (2026)
- [Provably Convergent Decentralized Optimization over Directed Graphs under Generalized Smoothness](https://mlsanity.com/paper/2601.03566/) (2026)
- [Sporadic Gradient Tracking over Directed Graphs: A Theoretical Perspective on Decentralized Federated Learning](https://mlsanity.com/paper/2602.00791/) (2026)
- [Convergence of Byzantine-Resilient Gradient Tracking via Probabilistic Edge Dropout](https://mlsanity.com/paper/2604.00449/) (2026)

## Abstract (arXiv)

In this letter, we study distributed optimization, where a network of agents, abstracted as a directed graph, collaborates to minimize the average of locally-known convex functions. Most of the existing approaches over directed graphs are based on push-sum (type) techniques, which use an independent algorithm to asymptotically learn either the left or right eigenvector of the underlying weight matrices. This strategy causes additional computation, communication, and nonlinearity in the algorithm. In contrast, we propose a linear algorithm based on an inexact gradient method and a gradient estimation technique. Under the assumptions that each local function is strongly-convex with Lipschitz-continuous gradients, we show that the proposed algorithm geometrically converges to the global minimizer with a sufficiently small step-size. We present simulations to illustrate the theoretical findings.