Distributed Optimization over Non-Symmetric Network Topologies

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2447 papers541 conceptsfrozen 2026-10-04

In decentralized optimization, a network of agents—such as a swarm of drones, a cluster of GPUs, or a grid of sensors—collaborates to solve a global problem without a central coordinator. Traditionally, these systems rely on a "symmetry assumption": if Agent A can send information to Agent B, Agent B can send it back with equal weight.

Mathematically, this symmetry allows the network to be represented by a doubly stochastic matrix, where the rows and columns both sum to one. This property ensures that as agents average their local parameters with their neighbors, the "mass" of the system is conserved, and everyone eventually converges to the same global truth.

However, real-world communication is rarely so tidy. In wireless sensor networks, power grids, or satellite constellations, signals are often one-way or asymmetric due to varying transmission power and interference. These are directed graphs, and they break the fundamental mechanisms of standard decentralized algorithms.

The Challenge of Asymmetric Flow

When communication is directed, the network can no longer be described by a doubly stochastic matrix. Instead, we are often stuck with matrices that are only row-stochastic (each agent decides how to weight incoming info) or column-stochastic (each agent decides how to distribute its own info).

As Alex Olshevsky, Angelia Nedić, and Wei Shi point out in Geometrically Convergent Distributed Optimization with Uncoordinated Step-Sizes, this asymmetry introduces a "bias" in the consensus process. If one node has many outgoing edges but few incoming ones, its local data will disproportionately influence the rest of the network, leading the group away from the true global optimum.

Gradient Tracking: Correcting the Drift

To solve this, researchers have moved beyond simple parameter averaging toward a mechanism called Gradient Tracking. In algorithms like DIGing and ATC-DIGing, agents don't just track their local estimate of the solution; they also maintain a secondary variable that "tracks" the average of all local gradients across the network.

The intuition is that even if the communication is lopsided, the tracking variable acts as a buffer that cancels out the steady-state error caused by the network's asymmetry. Ran Xin and Usman A. Khan demonstrate in Gradient tracking and variance reduction for decentralized optimization and machine learning that this approach allows agents to achieve "linear convergence"—finding the optimal solution exponentially fast—even on complex directed topologies.

Recovering Balance via Push-Sum

When a doubly stochastic matrix is unavailable, how do we ensure every agent's data is weighted equally? The most common solution is the Push-Sum protocol.

In a Push-Sum architecture, agents maintain a "weight" variable alongside their parameter estimates. As they send information across directed links, they also "push" portions of their weight to their neighbors. By dividing their parameter estimate by this accumulated weight, agents can locally recover the global average.

This logic is central to algorithms like S-ADDOPT, introduced by Muhammad I. Qureshi and Ran Xin in S-ADDOPT: Decentralized stochastic first-order optimization over directed graphs. It allows for decentralized stochastic gradient descent (DSGD) to function effectively in environments where bidirectional communication is impossible.

Scaling to Massive Data

While gradient tracking fixes the network bias, it doesn't solve the "noise" inherent in using stochastic gradients (SGD) for large-scale machine learning. To handle this, the field has integrated Variance Reduction techniques.

Algorithms like GT-SVRG, detailed by Ran Xin and Usman A. Khan in Variance-Reduced Decentralized Stochastic Optimization with Gradient Tracking - Part II: GT-SVRG, combine the network-balancing power of gradient tracking with the computational efficiency of SVRG. This dual-layer approach ensures that:

  1. The network asymmetry is corrected (via Gradient Tracking).
  2. The sampling noise from local data is suppressed (via Variance Reduction).

Robustness in the Wild

Recent work has focused on making these directed-graph algorithms more practical. Kun Yuan and Sulaiman A. Alghunaim have shown in An Enhanced Gradient-Tracking Bound for Distributed Online Stochastic Convex Optimization that gradient tracking is far more robust to sparse network connections than previously thought.

Furthermore, Vivek Khatana introduced D-DistADMM in D-DistADMM: A O(1/k) Distributed ADMM for Distributed Optimization in Directed Graph Topologies, proving that even complex primal-dual methods like ADMM can be adapted for directed graphs using finite-time consensus protocols.

By moving away from the crutch of symmetric communication, this research direction enables decentralized learning to deploy in truly "wild" environments—from low-power sensor arrays to ad-hoc mobile networks—where the flow of information is inherently one-way.

Papers in this version

Showing 60 of 447 papers.

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 1, frozen text):

@misc{lacuna_distributed_optimization_over_non_symmet_895c7d84_v1,
  title = {Distributed Optimization over Non-Symmetric Network Topologies},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/distributed-optimization-over-non-symmetric-network-topologies/rdr_895c7d843a474af38229cc09ee3afc17/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}