# S-ADDOPT: Decentralized stochastic first-order optimization over directed graphs

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2020.

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

- [Integrating LLMs with ITS: Recent Advances, Potentials, Challenges, and Future Directions](https://mlsanity.com/paper/2501.04437/) (2025)
- [Improving the Transient Times for Distributed Stochastic Gradient Methods](https://mlsanity.com/paper/2105.04851/) (2021)
- [Distributed Random Reshuffling over Networks](https://mlsanity.com/paper/2112.15287/) (2021)
- [Distributed Adaptive Learning Under Communication Constraints](https://mlsanity.com/paper/2112.02129/) (2021)
- [Log-Scale Quantization in Distributed First-Order Methods: Gradient-based Learning from Distributed Data](https://mlsanity.com/paper/2406.00621/) (2024)
- [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)
- [Distributed Random Reshuffling Methods with Improved Convergence](https://mlsanity.com/paper/2306.12037/) (2023)
- [Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs](https://mlsanity.com/paper/2107.12065/) (2021)
- [Logarithmically Quantized Distributed Optimization over Dynamic Multi-Agent Networks](https://mlsanity.com/paper/2410.20345/) (2024)
- [Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2601.11435/) (2026)
- [Machine Learning and CPU (Central Processing Unit) Scheduling Co-Optimization over a Network of Computing Centers](https://mlsanity.com/paper/2510.25176/) (2025)
- [Using Non-Lipschitz Signum-based Functions for Distributed Optimization and Machine Learning: Trade-off Between Con-vergence Rate and Optimality Gap](https://mlsanity.com/paper/2608.01220/) (2026)

## Abstract (arXiv)

In this report, we study decentralized stochastic optimization to minimize a sum of smooth and strongly convex cost functions when the functions are distributed over a directed network of nodes. In contrast to the existing work, we use gradient tracking to improve certain aspects of the resulting algorithm. In particular, we propose the~textbftextttS-ADDOPT algorithm that assumes a stochastic first-order oracle at each node and show that for a constant step-size~α, each node converges linearly inside an error ball around the optimal solution, the size of which is controlled by~α. For decaying step-sizes~O(1/k), we show that~textbftextttS-ADDOPT reaches the exact solution sublinearly at~O(1/k) and its convergence is asymptotically network-independent. Thus the asymptotic behavior of~textbftextttS-ADDOPT is comparable to the centralized stochastic gradient descent. Numerical experiments over both strongly convex and non-convex problems illustrate the convergence behavior and the performance comparison of the proposed algorithm.