Linear Convergence in Decentralized Optimization over Directed Networks

17 concepts12 papers1 proposal

In decentralized optimization, a network of independent agents collaborates to minimize a global objective function:

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

Each agent $i$ only knows its local cost function $f_i(x)$ and must coordinate with its neighbors via a communication graph to find the global optimum $x^*$.

When the communication network is undirected, this problem is well-understood. Agents can easily construct a doubly-stochastic weight matrix to govern their updates. In a doubly-stochastic matrix, both rows and columns sum to one. This mathematical property ensures a "conservation of mass": as agents average their local states with their neighbors, information flows evenly across the network without accumulating anywhere disproportionately.

However, real-world networks—such as wireless sensor arrays, edge computing devices, or autonomous fleets—are often directed. Information frequently flows one way due to asymmetric transmission power or channel interference. In a directed graph, constructing a doubly-stochastic matrix requires global coordination or bidirectional feedback loops. Without it, standard consensus algorithms cause information to pool at highly connected "sink" nodes, biasing the optimization process toward those nodes' local objectives and stalling convergence.

To overcome this asymmetry and achieve fast, linear convergence rates, researchers have developed mechanisms that track and cancel out network bias.

Correcting Asymmetry: Push-Sum vs. Row-Stochastic Matrices

Early attempts to handle directed graphs focused on explicitly balancing the network. For instance, Makhdoumi et al. in Graph balancing for distributed subgradient methods over directed graphs utilized a weight-balancing mechanism to counteract network asymmetry, though first-order subgradient methods in this domain were still bounded by a sublinear convergence rate of $O(1/\sqrt{T})$.

To dynamically correct the imbalance without global graph balancing, two main matrix paradigms emerged:

1. Column-Stochastic Matrices and Push-Sum

If a matrix is column-stochastic, each node controls how it distributes its own information to its out-neighbors (the columns sum to one), but it cannot control how much total information it receives (the rows do not sum to one). This causes spatial bias.

The Push-Sum protocol resolves this by introducing an auxiliary scalar variable for each node. This scalar acts as a running tally of the cumulative network "influence" or "mass" the node has received. By dividing their primary optimization variables by this scalar weight estimate before performing local computations, nodes mathematically cancel out the network's directional bias. Nedic et al. applied this to stochastic optimization in Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs, proving that tracking this running scale factor allows the network to converge at an accelerated $O(\ln t / t)$ rate for strongly convex functions.

2. Row-Stochastic Matrices without Out-Degree Knowledge

While column-stochastic methods work well, they require each node to know its exact out-degree (how many neighbors it is successfully transmitting to) so it can divide its weights properly. In broadcast-based wireless environments, a node might transmit a packet without knowing which neighbors successfully received it.

To bypass this constraint, Xi et al. flipped the paradigm in Linear Convergence in Optimization Over Directed Graphs With Row-Stochastic Matrices. By utilizing row-stochastic matrices, nodes only need to know their in-degree (who they are receiving information from), which is easily determined in practice. To counteract the resulting column imbalance, the authors introduced an auxiliary variable mechanism that tracks and compensates for the information drift, enabling linear convergence without requiring any global topology or out-degree knowledge.

Column-Stochastic (Push-Sum)          Row-Stochastic (FROST / ADD-OPT)
   Nodes know OUT-degree                 Nodes know IN-degree
   [Node i] ---> Sends 1/d_out           [Node i] <--- Receives from neighbors
   Tracks incoming "mass" via scalar     Tracks information drift via auxiliary vector

Achieving Linear Convergence via Gradient Tracking

Even with asymmetry corrected, traditional distributed gradient methods suffer from a fundamental limitation: they must use a diminishing step size to force consensus. This happens because the local gradient $\nabla f_i(x)$ at a given node does not vanish at the global optimum $x^*$. If a fixed step size is used, the local gradients act as persistent steady-state noise, causing the algorithm to wander around a neighborhood of the optimum rather than converging exactly. Diminishing step sizes eliminate this chatter, but they drag the convergence speed down to slow sublinear rates.

To achieve linear (geometric) convergence ($O(\mu^k)$ where $0 < \mu < 1$) with a fixed step size, the network must employ Gradient Tracking.

In a gradient tracking framework, nodes do not just exchange their optimization variables; they also maintain and update a running estimate of the average global gradient across the entire network. As the nodes approach the global optimum, these tracked gradient estimates naturally drive toward zero, neutralizing the local gradient mismatch.

This dual-tracking approach—tracking both the positions and the network-wide gradients—is what unlocks high-speed convergence on directed graphs:

Robustness to Practical Constraints

With the theoretical foundations of gradient tracking and asymmetry compensation established, subsequent research focused on adapting these algorithms to real-world system constraints.

Uncoordinated Step Sizes

In large-scale deployments, forcing every device to agree on a single, uniform optimization step size requires centralized synchronization. To eliminate this bottleneck, Xin et al. developed the FROST framework in FROST - Fast row-stochastic optimization with uncoordinated step-sizes. By pairing row-stochastic weights with gradient tracking, FROST allows each agent to independently select its own local step size while maintaining fast, linear convergence over directed networks.

Accelerated and Stochastic Dynamics

To further accelerate convergence, Xi et al. proposed ADD-OPT: Accelerated Distributed Directed Optimization, which expands the stable step-size range of directed optimization methods and delivers state-of-the-art linear convergence rates for strongly convex objectives.

When local data streams are noisy or stochastic, gradient tracking remains highly resilient. Nedich demonstrated in Distributed Stochastic Optimization with Gradient Tracking over Time- Varying Directed Networks that tracking mechanisms can successfully absorb stochastic gradient noise under time-varying directed topologies. To combat the communication overhead inherent to these multi-variable tracking systems, Chen et al. in Communication-Efficient Variance-Reduced Decentralized Stochastic Optimization over Time-Varying Directed Graphs integrated variance reduction techniques, ensuring that edge devices can maintain high-speed linear convergence without saturating the network's communication channels.

Key Foundational Work

Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs (2014) — contributed 1 concept elements to this direction.
Graph balancing for distributed subgradient methods over directed graphs (2015) — contributed 1 concept elements to this direction.
ExtraPush for Convex Smooth Decentralized Optimization over Directed Networks (2015) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_fast_convergence_in_directed_graphs_7d068d41,
  title = {fast convergence in directed graphs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fast-convergence-in-directed-graphs/rdr_7d068d417b564f259f65d83734f85105},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_fast_convergence_in_directed_graphs_7d068d41_v1,
  title = {fast convergence in directed graphs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fast-convergence-in-directed-graphs/rdr_7d068d417b564f259f65d83734f85105/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake