Decentralized Primal-Dual Learning Over Directed Graphs

Abstract

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 step-size. 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.