# ADD-OPT: Accelerated Distributed Directed Optimization

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2016.

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

- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2102.06752/) (2021)
- [Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks](https://mlsanity.com/paper/2106.07243/) (2021)
- [Discretized Distributed Optimization over Dynamic Digraphs](https://mlsanity.com/paper/2311.07939/) (2023)
- [Log-Scale Quantization in Distributed First-Order Methods: Gradient-based Learning from Distributed Data](https://mlsanity.com/paper/2406.00621/) (2024)
- [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)
- [Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs](https://mlsanity.com/paper/2107.12065/) (2021)
- [Online Distributed Learning with Quantized Finite-Time Coordination](https://mlsanity.com/paper/2307.06620/) (2023)
- [Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2601.11435/) (2026)
- [D-SVM over Networked Systems with Non-Ideal Linking Conditions](https://mlsanity.com/paper/2304.06667/) (2023)
- [Distributed Learning over Arbitrary Topology: Linear Speed-Up with Polynomial Transient Time](https://mlsanity.com/paper/2503.16123/) (2025)
- [Machine Learning and CPU (Central Processing Unit) Scheduling Co-Optimization over a Network of Computing Centers](https://mlsanity.com/paper/2510.25176/) (2025)

## Abstract (arXiv)

In this paper, we consider distributed optimization problems where the goal is to minimize a sum of objective functions over a multi-agent network. We focus on the case when the inter-agent communication is described by a strongly-connected, directed graph. The proposed algorithm, ADD-OPT (Accelerated Distributed Directed Optimization), achieves the best known convergence rate for this class of problems,~O(μk),0<μ<1, given strongly-convex, objective functions with globally Lipschitz-continuous gradients, where~k is the number of iterations. Moreover, ADD-OPT supports a wider and more realistic range of step-sizes in contrast to existing work. In particular, we show that ADD-OPT converges for arbitrarily small (positive) step-sizes. Simulations further illustrate our results.