Variance reduced stochastic optimization over directed graphs with row and column stochastic weights
This work addresses efficient optimization in decentralized networks with directed communication, which is incremental but improves upon existing methods by using linear updates and handling data heterogeneity.
The paper tackles distributed stochastic optimization over directed graphs by proposing AB-SAGA, a method that uses node-level variance reduction and network-level gradient tracking to handle data dissimilarity and directed communication with linear consensus updates. It shows linear convergence to the global optimum with a constant step-size and demonstrates regimes where it achieves linear speed-up over centralized methods, as supported by numerical experiments.
This paper proposes AB-SAGA, a first-order distributed stochastic optimization method to minimize a finite-sum of smooth and strongly convex functions distributed over an arbitrary directed graph. AB-SAGA removes the uncertainty caused by the stochastic gradients using a node-level variance reduction and subsequently employs network-level gradient tracking to address the data dissimilarity across the nodes. Unlike existing methods that use the nonlinear push-sum correction to cancel the imbalance caused by the directed communication, the consensus updates in AB-SAGA are linear and uses both row and column stochastic weights. We show that for a constant step-size, AB-SAGA converges linearly to the global optimal. We quantify the directed nature of the underlying graph using an explicit directivity constant and characterize the regimes in which AB-SAGA achieves a linear speed-up over its centralized counterpart. Numerical experiments illustrate the convergence of AB-SAGA for strongly convex and nonconvex problems.