Distributed Optimization over Directed Networks

629 concepts430 papers1 proposal

In decentralized optimization, a network of independent agents (such as sensors, robots, or edge devices) collaborates to minimize a global objective function:

$$\min_{x} \frac{1}{n} \sum_{i=1}^n f_i(x)$$

where each agent $i$ only knows its local objective function $f_i(x)$. Because there is no central coordinator, agents must find the global optimum by performing local computations and exchanging messages with their immediate neighbors.

Most foundational decentralized algorithms assume that communication is a two-way street, modeled as an undirected graph. However, real-world networks often feature directed communication constraints due to asymmetric transmission power, broadcast-only protocols, or directional wireless links.

When you move from undirected to directed graphs, standard decentralized optimization algorithms break down entirely. This article explains why network asymmetry introduces a fundamental mathematical bias, and how modern algorithms use state augmentation and gradient tracking to cancel out this bias and restore exact convergence.


The Mathematical Trap: Why Asymmetry Distorts the Truth

To understand why directed graphs are challenging, we have to look at the properties of the network's communication matrix, $W$, where $W_{ij}$ represents the weight agent $i$ assigns to information coming from agent $j$.

For a decentralized algorithm to converge to the true global minimum, the weight matrix $W$ must satisfy two properties simultaneously:

  1. Row-Stochasticity ($\sum_{j} W_{ij} = 1$): Every agent computes a valid weighted average of its neighbors' states. This ensures that all agents eventually reach a consensus (agreement on a single value).
  2. Column-Stochasticity ($\sum_{i} W_{ij} = 1$): The total influence of any single agent's data is preserved across the network. This ensures optimality, meaning the final consensus value treats every agent's local function $f_i(x)$ with equal importance.

A matrix that satisfies both conditions is called doubly-stochastic. On an undirected graph, agents can easily construct a doubly-stochastic matrix using only local information (e.g., by using the Metropolis-Hastings weights based on neighbor degrees).

The Impossibility of Local Balance

On a directed graph, constructing a doubly-stochastic matrix using only local information is mathematically impossible.

An agent knows who it receives information from (its in-neighbors), so it can easily scale its incoming weights to ensure row-stochasticity. However, without global coordination, an agent does not know its exact impact on the rest of the network (its out-neighbors).

If we force the matrix to be only row-stochastic, the network will still reach a consensus, but the consensus value will be heavily skewed. As noted by Ali Makhdoumi et al. in Graph balancing for distributed subgradient methods over directed graphs, asymmetric links cause certain structurally dominant nodes to exert a disproportionate influence on the collective learning process.

Mathematically, a row-stochastic matrix converges to a steady state dictated by its Perron-Frobenius right eigenvector, $\pi$. Instead of minimizing the true average $\frac{1}{n} \sum f_i(x)$, the network inadvertently minimizes a weighted objective:

$$\sum_{i=1}^n \pi_i f_i(x)$$

Nodes with high centrality (large $\pi_i$) dominate the outcome, while peripheral nodes are effectively ignored.


The Solution: Tracking and Canceling the Bias

To overcome this topological bias without requiring a doubly-stochastic matrix, modern directed optimization algorithms rely on two core mechanisms: Push-Sum Consensus and Gradient Tracking.

1. Push-Sum: Dynamic Bias Cancellation

The intuition behind the push-sum protocol is elegant: if the network topology scales your optimization variables by a hidden bias $\pi_i$, you can run a parallel consensus process to discover exactly what that bias is, and then divide it out.

Instead of maintaining just the optimization variable $x_i$, each agent maintains an auxiliary scalar variable $y_i$, initialized to $1$. Agents update both variables using a column-stochastic matrix (which preserves the sum of the variables but doesn't guarantee immediate consensus):

$$x_i^{(k+1)} = \sum_{j \in \text{In}_i} W_{ij} x_j^{(k)}$$ $$y_i^{(k+1)} = \sum_{j \in \text{In}_i} W_{ij} y_j^{(k)}$$

As the iterations progress, both $x_i$ and $y_i$ become biased by the exact same network weights. Specifically, $x_i^{(k)} \to \pi_i \sum x_j^{(0)}$ and $y_i^{(k)} \to \pi_i \cdot n$.

By taking the ratio $\frac{x_i^{(k)}}{y_i^{(k)}}$, the network weight $\pi_i$ cancels out perfectly:

$$\frac{x_i^{(k)}}{y_i^{(k)}} \to \frac{\pi_i \sum x_j^{(0)}}{\pi_i \cdot n} = \frac{1}{n} \sum_{j=1}^n x_j^{(0)}$$

This ratio step allows agents to recover an unbiased global average using only one-way communication.

2. Gradient Tracking: Uncoupling Consensus from Gradients

While push-sum solves the consensus problem, combining it with gradient descent introduces another issue: local gradients change at every step, constantly injecting new imbalances into the system.

To fix this, Chenguang Xi et al. introduced Directed-Distributed Gradient Descent (D-DGD) in On the distributed optimization over directed networks and later refined it into ADD-OPT (Accelerated Distributed Directed Optimization). These methods implement gradient tracking, where agents maintain a running estimate of the average global gradient rather than just utilizing their local gradient.

By tracking the global gradient dynamically, the algorithm ensures that even if a node is structurally weak in the graph, its local gradient information is successfully diffused across the entire network.

┌────────────────────────────────────────────────────────┐
│                   Agent i (Local State)                │
│                                                        │
│  ┌─────────────────┐         ┌──────────────────────┐  │
│  │  Optimization   │         │  Auxiliary Weight    │  │
│  │   Variable (x)  │         │     Variable (y)     │  │
│  └────────┬────────┘         └──────────┬───────────┘  │
│           │                             │              │
│           └──────────────┬──────────────┘              │
│                          ▼                             │
│                [ Ratio Step: x_i / y_i ]               │
│                          │                             │
│                          ▼                             │
│             Unbiased Global Consensus                  │
└────────────────────────────────────────────────────────┘

Algorithmic Evolution

The integration of these mechanisms has driven significant performance breakthroughs over directed topologies:

  • Sublinear to Linear Convergence: Early directed methods were forced to use diminishing step sizes to combat the interaction between gradient noise and network asymmetry, resulting in slow sublinear convergence. By combining gradient tracking with push-sum, Jinshan Zeng et al. developed ExtraPush (ExtraPush for Convex Smooth Decentralized Optimization over Directed Networks), proving that agents can use a fixed step size to achieve fast, linear convergence on directed graphs.
  • Communication Efficiency: Transmitting high-precision floating-point vectors across directed links can saturate bandwidth. To address this, Hossein Taheri et al. in Quantized Decentralized Stochastic Learning over Directed Graphs successfully integrated quantization strategies with the push-sum protocol, demonstrating that communication payload can be reduced by up to 90% without sacrificing the underlying convergence rate.

By shifting the focus from forcing network symmetry to dynamically tracking and dividing out topological bias, these approaches allow decentralized systems to operate reliably in highly asymmetric, real-world communication environments.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 410 papers
  2. Version 1 · 2026-10-04 · 447 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_directed_graph_consensus_895c7d84,
  title = {directed graph consensus},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/directed-graph-consensus/rdr_895c7d843a474af38229cc09ee3afc17},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_directed_graph_consensus_895c7d84_v2,
  title = {directed graph consensus},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/directed-graph-consensus/rdr_895c7d843a474af38229cc09ee3afc17/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake