# Distributed optimization over time-varying directed graphs

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

## Key facts

- Cited by 78 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2013.

## Built on by (most cited first, 30 of 78)

- [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022)
- [Exponential Graph is Provably Efficient for Decentralized Deep Training](https://mlsanity.com/paper/2110.13363/) (2021)
- [FedAvg with Fine Tuning: Local Updates Lead to Representation Learning](https://mlsanity.com/paper/2205.13692/) (2022)
- [Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices](https://mlsanity.com/paper/2103.03239/) (2021)
- [Communication-Efficient Topologies for Decentralized Learning with O(1) Consensus Rate](https://mlsanity.com/paper/2210.07881/) (2022)
- [Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization](https://mlsanity.com/paper/2210.07863/) (2022)
- [Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization](https://mlsanity.com/paper/2105.00321/) (2021)
- [SWIFT: Rapid Decentralized Federated Learning via Wait-Free Model Communication](https://mlsanity.com/paper/2210.14026/) (2022)
- [Epidemic Learning: Boosting Decentralized Learning with Randomized Communication](https://mlsanity.com/paper/2310.01972/) (2023)
- [BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning](https://mlsanity.com/paper/2111.04287/) (2021)
- [DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization](https://mlsanity.com/paper/2202.01268/) (2022)
- [Decentralized SGD and Average-direction SAM are Asymptotically Equivalent](https://mlsanity.com/paper/2306.02913/) (2023)
- [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)
- [Networked Signal and Information Processing](https://mlsanity.com/paper/2210.13767/) (2022)
- [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)
- [On Generalization of Decentralized Learning with Separable Data](https://mlsanity.com/paper/2209.07116/) (2022)
- [Sparse-Push: Communication- & Energy-Efficient Decentralized Distributed Learning over Directed & Time-Varying Graphs with non-IID Datasets](https://mlsanity.com/paper/2102.05715/) (2021)
- [On Faster Convergence of Scaled Sign Gradient Descent](https://mlsanity.com/paper/2109.01806/) (2021)
- [MDPGT: Momentum-based Decentralized Policy Gradient Tracking](https://mlsanity.com/paper/2112.02813/) (2021)
- [Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable](https://mlsanity.com/paper/2503.20117/) (2025)
- [Boost Decentralized Federated Learning in Vehicular Networks by Diversifying Data Sources](https://mlsanity.com/paper/2209.01750/) (2022)
- [Asymmetrically Decentralized Federated Learning](https://mlsanity.com/paper/2310.05093/) (2023)
- [DRACO: Decentralized Asynchronous Federated Learning over Row-Stochastic Wireless Networks](https://mlsanity.com/paper/2406.13533/) (2024)
- [FedSPD: A Soft-clustering Approach for Personalized Decentralized Federated Learning](https://mlsanity.com/paper/2410.18862/) (2024)
- [Improved Convergence Analysis and SNR Control Strategies for Federated Learning in the Presence of Noise](https://mlsanity.com/paper/2307.07406/) (2023)
- [Log-Scale Quantization in Distributed First-Order Methods: Gradient-based Learning from Distributed Data](https://mlsanity.com/paper/2406.00621/) (2024)
- [DIGing--SGLD: Decentralized and Scalable Langevin Sampling over Time--Varying Networks](https://mlsanity.com/paper/2511.12836/) (2025)
- [Decentralized Federated Learning with Gradient Tracking over Time-Varying Directed Networks](https://mlsanity.com/paper/2409.17189/) (2024)

## Abstract (arXiv)

We consider distributed optimization by a collection of nodes, each having access to its own convex function, whose collective goal is to minimize the sum of the functions. The communications between nodes are described by a time-varying sequence of directed graphs, which is uniformly strongly connected. For such communications, assuming that every node knows its out-degree, we develop a broadcast-based algorithm, termed the subgradient-push, which steers every node to an optimal value under a standard assumption of subgradient boundedness. The subgradient-push requires no knowledge of either the number of agents or the graph sequence to implement. Our analysis shows that the subgradient-push algorithm converges at a rate of O(ln(t)/√t), where the constant depends on the initial values at the nodes, the subgradient norms, and, more interestingly, on both the consensus speed and the imbalances of influence among the nodes.