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:
- Push-Sum + Gradient Tracking: In ExtraPush for Convex Smooth Decentralized Optimization over Directed Networks, Zeng et al. integrated gradient tracking with the push-sum protocol, demonstrating that combining these two tracking mechanisms allows fixed step-size methods to achieve linear convergence on static directed graphs.
- Handling Dynamic Networks: Nedic et al. expanded this concept to time-varying topologies in Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs via the DIGing and Push-DIGing algorithms. They proved that even if the directed communication links flicker or change at every single iteration, the dual-tracking mechanism preserves geometric convergence.
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.