Decentralized Primal-Dual Learning over Directed Graphs

Distributed adaptation and learning over directed, unbalanced graphs poses unique challenges due to asymmetric communication and heterogeneous data across nodes. In this work, we introduce a novel class of first-order primal–dual stochastic gradient algorithms for such graphs. Our flagship algorithm, called primal-dual pull diffusion stochastic gradient, is designed to update both the decision variables (primal) and the associated multipliers (dual) using two left-stochastic combination matrices. This design maintains data privacy while ensuring that the estimates remain accurate and unbiased. Building on this, we develop pull-based exact diffusion and pull–push variants that reduce communication costs or eliminate the need for prior knowledge of Perron vector. We also provide a mean-square stability analysis for the primal-dual pull diffusion method, demonstrating the steady-state error proportional to the stepsize. Finally, simulation results on randomly generated directed graphs validate the efficiency of the proposed algorithms and show faster convergence or lower steady-state error compared to existing gradient-tracking-type methods.