Push-Pull Gradient Methods for Directed Networks

11 concepts14 papers

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

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

Here, each agent $i$ only has access to its local cost function $f_i(x)$. To find the global optimum without a central coordinator, agents must share information with their immediate neighbors.

When communication is bidirectional (an undirected graph), this problem is well-understood. Agents can use a single doubly-stochastic weight matrix to mix their states. Doubly-stochastic matrices ensure two things simultaneously: all agents' states converge to a common value (consensus), and every agent's local gradient contributes equally to the global objective (unbiased optimization).

However, real-world networks—such as wireless sensor arrays or asymmetric internet routing paths—are often directed. Node A can send data to Node B, but Node B cannot send data back to Node A. Over directed graphs, constructing a doubly-stochastic matrix requires global knowledge of the network topology, which defeats the purpose of a decentralized system. Traditional workarounds, like the non-linear push-sum protocol, require agents to perform coordinate-wise divisions by a running scalar weight, making them highly sensitive to communication noise and computationally cumbersome.

The Push-Pull (or AB) framework resolves this dilemma by abandoning the search for a single doubly-stochastic matrix. Instead, it decouples the two fundamental requirements of distributed optimization into two distinct, asymmetric matrices.

Decoupling Consensus and Tracking

To optimize effectively over a directed graph, an algorithm must manage two distinct types of information flow:

  1. Consensus: Ensuring all agents agree on the decision variable $x$.
  2. Gradient Tracking: Ensuring all agents accurately estimate the average gradient of the entire network, preventing the optimization from biasing toward highly connected nodes.

The core insight of the Push-Pull framework is to maintain two separate variables per agent and update them using two different matrices tailored to these specific tasks. Let $x_i^k$ be agent $i$'s estimate of the optimal solution at iteration $k$, and let $y_i^k$ be its estimate of the network-wide average gradient.

As formalized by Angelia Nedich et al. in Push-Pull Gradient Methods for Distributed Optimization in Networks and Ran Xin et al. in Distributed stochastic optimization with gradient tracking over strongly-connected networks, the updates follow a elegant linear structure:

$$x^{k+1} = A x^k - \alpha y^k$$

$$y^{k+1} = B y^k + \nabla F(x^{k+1}) - \nabla F(x^k)$$

Where $A$ is a row-stochastic matrix and $B$ is a column-stochastic matrix.

Why It Works: The Asymmetric Roles of A and B

To understand why this dual-matrix architecture guarantees exact convergence, we must look at how row-stochasticity and column-stochasticity behave mathematically.

The "Pull" Mechanism (Row-Stochastic Matrix A)

The matrix $A$ is row-stochastic, meaning the entries in each of its rows sum to 1 ($A\mathbf{1} = \mathbf{1}$). When agent $i$ computes its next state, it takes a weighted average of its neighbors' current states:

$$x_i^{k+1} = \sum_{j=1}^n A_{ij} x_j^k - \alpha y_i^k$$

Because the weights sum to 1, this operation is a true convex combination. If every agent already shares the exact same state ($x_i = x_j$), multiplying by $A$ leaves the states unchanged. This property allows the matrix $A$ to act as a pull mechanism, drawing all agents' decision variables toward a common consensus value without distorting the scale of the parameters.

The "Push" Mechanism (Column-Stochastic Matrix B)

The matrix $B$ is column-stochastic, meaning the entries in each of its columns sum to 1 ($\mathbf{1}^T B = \mathbf{1}^T$). Agents use this matrix to broadcast or push their gradient tracking variables to their out-neighbors:

$$y^{k+1} = B y^k + \Delta^{k+1}$$

where $\Delta^{k+1} = \nabla F(x^{k+1}) - \nabla F(x^k)$ is the local change in gradients. If we sum the gradient tracking variables across the entire network, the column-stochasticity of $B$ ensures a conservation law:

$$\mathbf{1}^T y^{k+1} = \mathbf{1}^T B y^k + \mathbf{1}^T \Delta^{k+1} = \mathbf{1}^T y^k + \mathbf{1}^T \Delta^{k+1}$$

By induction, if the tracking variables are initialized to the local gradients ($y_i^0 = \nabla f_i(x_i^0)$), the network-wide sum of $y_i^k$ is exactly preserved and remains equal to the sum of the true local gradients at every single iteration:

$$\sum_{i=1}^n y_i^k = \sum_{i=1}^n \nabla f_i(x_i^k)$$

Even if the directed graph is highly unbalanced—meaning some nodes have many incoming links but few outgoing links—the total "mass" of the gradient information is never lost or artificially amplified. As the matrix $B$ continuously diffuses this information, each local $y_i^k$ converges to the true global average gradient $\frac{1}{n} \sum_{j=1}^n \nabla f_j(x_j^k)$.

By coupling a row-stochastic matrix to handle the consensus of $x$ and a column-stochastic matrix to handle the conservation of $y$, the algorithm achieves exact linear convergence to the true global minimizer using entirely linear updates. This eliminates the need for non-linear coordinate divisions or eigenvector estimation, as originally demonstrated in the early Directed-Distributed Gradient Descent (D-DGD) and DEXTRA variants by Chenguang Xi et al. (Fast distributed optimization over directed graphs; DEXTRA: A Fast Algorithm for Optimization Over Directed Graphs).

Generalizing to Real-World Constraints

Because the Push-Pull framework relies on simple linear combinations, it serves as a robust foundation for more complex, constrained decentralized environments.

Noise and Time-Varying Topologies

In physical networks, communication links drop, and messages are corrupted by noise. Shi Pu introduced R-Push-Pull in A Robust Gradient Tracking Method for Distributed Optimization over Directed Networks, proving that the dual-matrix structure maintains linear convergence to a neighborhood of the optimal solution even under quantization errors and noisy channels. Furthermore, Fakhteh Saadatniaki et al. demonstrated in Decentralized Optimization Over Time-Varying Directed Graphs With Row and Column-Stochastic Matrices that the underlying graphs do not need to be static; as long as the network is jointly strongly connected over a sequence of time steps, consensus and tracking remain stable.

Stochastic Gradients and Variance Reduction

For large-scale machine learning, computing the full gradient $\nabla f_i(x)$ at every step is computationally prohibitive. Instead, agents sample mini-batches to compute stochastic gradients. To combat the variance introduced by this sampling, Muhammad I. Qureshi et al. proposed AB-SAGA (Variance reduced stochastic optimization over directed graphs with row and column stochastic weights), which embeds SAGA-style variance reduction directly into the gradient tracking step, restoring exact linear convergence under stochastic environments.

Asynchrony and Sporadic Communication

In Federated Learning, edge devices have varying computational capacities and battery constraints. Algorithms cannot expect every device to participate in every round.

Advanced Optimization Architectures

The flexibility of decoupling consensus from tracking has allowed researchers to move beyond standard empirical risk minimization:

Key Foundational Work

Distributed dynamic optimization over directed graphs (2016) — contributed 2 concept elements to this direction.
Fast distributed optimization over directed graphs (2016) — contributed 1 concept elements to this direction.
A proximal gradient algorithm for decentralized nondifferentiable optimization (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_dual_matrix_consensus_cc4d093f,
  title = {dual-matrix consensus},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dual-matrix-consensus/rdr_cc4d093f158944c3acb2ecbef4077447},
  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_dual_matrix_consensus_cc4d093f_v1,
  title = {dual-matrix consensus},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dual-matrix-consensus/rdr_cc4d093f158944c3acb2ecbef4077447/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}

See something wrong? Report a mistake