# Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2014.

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

- [Decentralized Federated Learning through Proxy Model Sharing](https://mlsanity.com/paper/2111.11343/) (2021)
- [RelaySum for Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2110.04175/) (2021)
- [Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices](https://mlsanity.com/paper/2103.03239/) (2021)
- [Epidemic Learning: Boosting Decentralized Learning with Randomized Communication](https://mlsanity.com/paper/2310.01972/) (2023)
- [Improving the Transient Times for Distributed Stochastic Gradient Methods](https://mlsanity.com/paper/2105.04851/) (2021)
- [Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization](https://mlsanity.com/paper/2104.02596/) (2021)
- [Decentralized Stochastic Optimization with Inherent Privacy Protection](https://mlsanity.com/paper/2205.03884/) (2022)
- [Noiseless Privacy-Preserving Decentralized Learning](https://mlsanity.com/paper/2404.09536/) (2024)
- [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)
- [On the Tradeoff between Privacy Preservation and Byzantine-Robustness in Decentralized Learning](https://mlsanity.com/paper/2308.14606/) (2023)
- [Quantization enabled Privacy Protection in Decentralized Stochastic Optimization](https://mlsanity.com/paper/2208.04845/) (2022)
- [Boosting Asynchronous Decentralized Learning with Model Fragmentation](https://mlsanity.com/paper/2410.12918/) (2024)
- [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)
- [Straggler-Resilient Decentralized Learning via Adaptive Asynchronous Updates](https://mlsanity.com/paper/2306.06559/) (2023)
- [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)
- [Locally Asynchronous Stochastic Gradient Descent for Decentralised Deep Learning](https://mlsanity.com/paper/2203.13085/) (2022)
- [On Arbitrary Compression for Decentralized Consensus and Stochastic Optimization over Directed Networks](https://mlsanity.com/paper/2204.08160/) (2022)
- [Push--Pull with Device Sampling](https://mlsanity.com/paper/2206.04113/) (2022)
- [Decentralized Hyper-Gradient Computation over Time-Varying Directed Networks](https://mlsanity.com/paper/2210.02129/) (2022)
- [Fair Decentralized Learning](https://mlsanity.com/paper/2410.02541/) (2024)
- [Improved Convergence Analysis of Topology Dependence in Decentralized SGD](https://mlsanity.com/paper/2606.09154/) (2026)
- [Fast Butterfly-Core Community Search For Large Labeled Graphs](https://mlsanity.com/paper/2401.10642/) (2024)
- [MUSIC: Accelerated Convergence for Distributed Optimization With Inexact and Exact Methods](https://mlsanity.com/paper/2403.02589/) (2024)
- [DFCA: Decentralized Federated Clustering Algorithm](https://mlsanity.com/paper/2510.15300/) (2025)
- [A Unified Convergence Analysis for Semi-Decentralized Learning: Sampled-to-Sampled vs. Sampled-to-All Communication](https://mlsanity.com/paper/2511.11560/) (2025)

## Abstract (arXiv)

We investigate the convergence rate of the recently proposed subgradient-push method for distributed optimization over time-varying directed graphs. The subgradient-push method can be implemented in a distributed way without requiring knowledge of either the number of agents or the graph sequence; each node is only required to know its out-degree at each time. Our main result is a convergence rate of O left((ln t)/t right) for strongly convex functions with Lipschitz gradients even if only stochastic gradient samples are available; this is asymptotically faster than the O left((ln t)/√t right) rate previously known for (general) convex functions.