On the Linear Speedup of the Push-Pull Method for Decentralized Optimization over Digraphs

The linear speedup property is essential for demonstrating the advantage of distributed algorithms over their single-node counterparts.

In this paper, we study the stochastic Push-Pull method, a widely adopted decentralized optimization algorithm over directed graphs (digraphs).

Unlike methods that rely solely on row-stochastic or column-stochastic mixing matrices, Push-Pull avoids nonlinear correction and has shown superior empirical performance across a variety of settings.

However, its theoretical analysis remains challenging, and the linear speedup property has not been generally establishe--revealing a significant gap between empirical success and limited theoretical understanding.

To bridge this gap, we propose a novel analysis framework and prove that Push-Pull achieves linear speedup over arbitrary strongly connected digraphs.

Our results provide the comprehensive theoretical understanding for stochastic Push-Pull, aligning its theory with empirical performance.

Code: this https URL.