# Variance reduced stochastic optimization over directed graphs with row and column stochastic weights

arXiv: https://arxiv.org/abs/2202.03346 · HTML: https://mlsanity.com/paper/2202.03346/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 37 references that are in the map.
- First posted on arXiv 7 Feb 2022.

## Builds on (most cited first, 22 of 22)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Stochastic Gradient Push for Distributed Deep Learning](https://mlsanity.com/paper/1811.10792/) (2018)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018)
- [An improved convergence analysis for decentralized online stochastic non-convex optimization](https://mlsanity.com/paper/2008.04195/) (2020)
- [Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence](https://mlsanity.com/paper/1912.04230/) (2019)
- [Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs](https://mlsanity.com/paper/1406.2075/) (2014)
- [A general framework for decentralized optimization with first-order methods](https://mlsanity.com/paper/2009.05837/) (2020)
- [A linear algorithm for optimization over directed graphs with geometric convergence](https://mlsanity.com/paper/1803.02503/) (2018)
- [Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions](https://mlsanity.com/paper/1811.03982/) (2018)
- [Fast decentralized non-convex finite-sum optimization with recursive variance reduction](https://mlsanity.com/paper/2008.07428/) (2020)
- [Cloud K-SVD: A Collaborative Dictionary Learning Algorithm for Big, Distributed Data](https://mlsanity.com/paper/1412.7839/) (2014)
- [ADD-OPT: Accelerated Distributed Directed Optimization](https://mlsanity.com/paper/1607.04757/) (2016)
- [A fast randomized incremental gradient method for decentralized non-convex optimization](https://mlsanity.com/paper/2011.03853/) (2020)
- [S-ADDOPT: Decentralized stochastic first-order optimization over directed graphs](https://mlsanity.com/paper/2005.07785/) (2020)
- [Distributed stochastic optimization with gradient tracking over strongly-connected networks](https://mlsanity.com/paper/1903.07266/) (2019)
- [Decentralized Optimization Over the Stiefel Manifold by an Approximate Augmented Lagrangian Function](https://mlsanity.com/paper/2112.14949/) (2021)
- [Push-SAGA: A decentralized stochastic algorithm with variance reduction over directed graphs](https://mlsanity.com/paper/2008.06082/) (2020)
- [Distributed Nesterov gradient methods over arbitrary graphs](https://mlsanity.com/paper/1901.06995/) (2019)
- [A Communication Efficient Quasi-Newton Method for Large-scale Distributed Multi-agent Optimization](https://mlsanity.com/paper/2201.03759/) (2022)

## Built on by (most cited first, 2 of 2)

- [Distributed saddle point problems for strongly concave-convex functions](https://mlsanity.com/paper/2202.05812/) (2022)
- [Communication Efficient ConFederated Learning: An Event-Triggered SAGA Approach](https://mlsanity.com/paper/2402.18018/) (2024)

## Abstract (arXiv)

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.