Push-SAGA: A decentralized stochastic algorithm with variance reduction over directed graphs
This addresses the problem of efficient distributed learning in directed communication networks, which is incremental but novel for this specific setting.
The paper tackles decentralized optimization over directed networks by proposing Push-SAGA, a stochastic algorithm that achieves linear convergence to exact solutions for smooth and strongly convex problems, making it the first such method for arbitrary strongly connected directed graphs.
In this paper, we propose Push-SAGA, a decentralized stochastic first-order method for finite-sum minimization over a directed network of nodes. Push-SAGA combines node-level variance reduction to remove the uncertainty caused by stochastic gradients, network-level gradient tracking to address the distributed nature of the data, and push-sum consensus to tackle the challenge of directed communication links. We show that Push-SAGA achieves linear convergence to the exact solution for smooth and strongly convex problems and is thus the first linearly-convergent stochastic algorithm over arbitrary strongly connected directed graphs. We also characterize the regimes in which Push-SAGA achieves a linear speed-up compared to its centralized counterpart and achieves a network-independent convergence rate. We illustrate the behavior and convergence properties of Push-SAGA with the help of numerical experiments on strongly convex and non-convex problems.