# Communication-Efficient Variance-Reduced Decentralized Stochastic Optimization over Time-Varying Directed Graphs

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2021.

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

- [On the Convergence of Decentralized Federated Learning Under Imperfect Information Sharing](https://mlsanity.com/paper/2303.10695/) (2023)
- [Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization](https://mlsanity.com/paper/2104.02596/) (2021)
- [Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance](https://mlsanity.com/paper/2604.16620/) (2026)
- [Improved Convergence Analysis and SNR Control Strategies for Federated Learning in the Presence of Noise](https://mlsanity.com/paper/2307.07406/) (2023)
- [Fed-QSSL: A Framework for Personalized Federated Learning under Bitwidth and Data Heterogeneity](https://mlsanity.com/paper/2312.13380/) (2023)
- [Communication Compression for Decentralized Learning with Operator Splitting Methods](https://mlsanity.com/paper/2205.03779/) (2022)
- [FedNMUT -- Federated Noisy Model Update Tracking Convergence Analysis](https://mlsanity.com/paper/2403.13247/) (2024)
- [RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolation](https://mlsanity.com/paper/2603.22155/) (2026)
- [Communication-Efficient Zeroth-Order Distributed Online Optimization: Algorithm, Theory, and Applications](https://mlsanity.com/paper/2306.05655/) (2023)

## Abstract (arXiv)

We consider the problem of decentralized optimization over time-varying directed networks. The network nodes can access only their local objectives, and aim to collaboratively minimize a global function by exchanging messages with their neighbors. Leveraging sparsification, gradient tracking and variance-reduction, we propose a novel communication-efficient decentralized optimization scheme that is suitable for resource-constrained time-varying directed networks. We prove that in the case of smooth and strongly-convex objective functions, the proposed scheme achieves an accelerated linear convergence rate. To our knowledge, this is the first decentralized optimization framework for time-varying directed networks that achieves such a convergence rate and applies to settings requiring sparsified communication. Experimental results on both synthetic and real datasets verify the theoretical results and demonstrate efficacy of the proposed scheme.