Push-Pull Gradient Tracking for Directed Networks

This direction is merged into another direction: directed graph consensus, dual-matrix consensus. Its last version stays readable and citable here.

Version 1 of 122 papers32 conceptsfrozen 2026-10-04

In decentralized optimization, a group of agents must collaboratively minimize a global function—typically the average of their local cost functions—without a central server. Traditionally, this requires a "balanced" communication network where information flows symmetrically. However, real-world systems like IoT sensors or autonomous fleets often operate over directed graphs (digraphs), where a node might send data to a neighbor without receiving anything in return.

Recent research has converged on a powerful framework to solve this: the Push-Pull (or AB) architecture. This approach decouples the two fundamental tasks of decentralized optimization—reaching a consensus and tracking the global gradient—using two distinct types of communication matrices.

The Symmetry Problem

Most early decentralized algorithms rely on doubly-stochastic matrices. In these networks, the weights of incoming and outgoing edges for every node must sum to one. This symmetry ensures that as agents average their values, the global average remains unchanged.

In directed networks, constructing such a matrix is difficult and often requires agents to know the global network topology. Without this symmetry, standard consensus methods suffer from "weight imbalance," where influential nodes (those with many outgoing edges) bias the entire network toward their local data.

The Dual-Matrix Solution

To overcome this, researchers like Ying Sun and Gesualdo Scutari in their work on SONATA proposed using two different matrices simultaneously:

  1. The "Pull" (Row-Stochastic Matrix A): This matrix is used to update the agents' decision variables. Because it is row-stochastic, each agent computes a weighted average of its neighbors' values. This "pulls" all agents toward a common consensus.
  2. The "Push" (Column-Stochastic Matrix B): This matrix is used to track the gradient. Because it is column-stochastic, it ensures that the "mass" of the gradient information is preserved as it moves through the network. This "pushes" local gradient information across the graph so that every agent can estimate the global average gradient.

By separating these roles, the Push-Pull framework allows for linear convergence on directed graphs without requiring agents to estimate complex network parameters like the Perron vector, a common bottleneck in older "push-sum" methods.

Tracking the Global Gradient

The core engine of these algorithms is Gradient Tracking (GT). In a simple decentralized gradient descent, agents only use their local gradient. If Agent A’s data is very different from Agent B’s, they will never reach the true global optimum.

Gradient tracking fixes this by maintaining a secondary variable that estimates the average gradient of the entire network. Ran Xin and Usman A. Khan demonstrated in the GT-SAGA and GT-SVRG papers that combining gradient tracking with local variance reduction allows the network to achieve "linear speedup." This means that as you add more nodes, the time required for each node to compute its update decreases, yet the network still converges to the exact solution as if it were a single powerful machine.

Robustness to Real-World Constraints

The Push-Pull framework has proven remarkably adaptable to the "messiness" of real-world networks:

  • Time-Varying Networks: In many applications, links between agents appear and disappear. Angelia Nedich and colleagues have extended these methods to time-varying directed graphs, showing that as long as the network is "strongly connected" over a window of time, the dual-matrix approach still converges.
  • Device Sampling: In large-scale federated learning, not every device is active at once. Yu-Guan Hsieh and Jerome Malick introduced PPDS (Push-Pull with Device Sampling), which maintains linear convergence even when only a random subset of nodes participates in each round.
  • Adversarial Resilience: Even if some agents are malicious, the RP3 algorithm uses trust-based mechanisms within the push-pull structure to filter out harmful updates, ensuring the network reaches a consensus on the correct optimal value.

Beyond Simple Minimization

The versatility of the row/column-stochastic decoupling has recently allowed researchers to tackle more complex mathematical structures. Farzad Yousefian developed IR-Push-Pull for bilevel problems, while Yaoshuai Ma and others introduced FAB to handle bilevel optimization over time-varying graphs without needing expensive second-order derivatives (Hessians).

By treating consensus and gradient tracking as two separate communication flows, the Push-Pull direction has turned the "problem" of directed communication into a flexible architectural choice, enabling robust, scalable optimization in the most challenging network environments.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_push_pull_gradient_tracking_for_directed_b1eb814c,
  title = {Push-Pull Gradient Tracking for Directed Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/push-pull-gradient-tracking-for-directed-networks/rdr_b1eb814c5df240729f9ce42f569d451d},
  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_push_pull_gradient_tracking_for_directed_b1eb814c_v1,
  title = {Push-Pull Gradient Tracking for Directed Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/push-pull-gradient-tracking-for-directed-networks/rdr_b1eb814c5df240729f9ce42f569d451d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}