# Fast decentralized non-convex finite-sum optimization with recursive variance reduction

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Aug 2020.

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

- [BEER: Fast O(1/T) Rate for Decentralized Nonconvex Optimization with Communication Compression](https://mlsanity.com/paper/2201.13320/) (2022)
- [Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD](https://mlsanity.com/paper/2105.08023/) (2021)
- [Momentum Tracking: Momentum Acceleration for Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2209.15505/) (2022)
- [DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization](https://mlsanity.com/paper/2110.01165/) (2021)
- [Convergence and Privacy of Decentralized Nonconvex Optimization with Gradient Clipping and Communication Compression](https://mlsanity.com/paper/2305.09896/) (2023)
- [Robust Decentralized Learning with Local Updates and Gradient Tracking](https://mlsanity.com/paper/2405.00965/) (2024)
- [An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2212.02387/) (2022)
- [Towards Faster Decentralized Stochastic Optimization with Communication Compression](https://mlsanity.com/paper/2405.20114/) (2024)
- [Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax Problems](https://mlsanity.com/paper/2304.10902/) (2023)
- [Communication-Efficient Stochastic Distributed Learning](https://mlsanity.com/paper/2501.13516/) (2025)
- [Variance reduced stochastic optimization over directed graphs with row and column stochastic weights](https://mlsanity.com/paper/2202.03346/) (2022)
- [A Variance-Reduced Stochastic Gradient Tracking Algorithm for Decentralized Optimization with Orthogonality Constraints](https://mlsanity.com/paper/2208.13643/) (2022)
- [On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/2402.02569/) (2024)
- [Communication Efficient ConFederated Learning: An Event-Triggered SAGA Approach](https://mlsanity.com/paper/2402.18018/) (2024)
- [Decentralized Sum-of-Nonconvex Optimization](https://mlsanity.com/paper/2402.02356/) (2024)
- [Faster Adaptive Decentralized Learning Algorithms](https://mlsanity.com/paper/2408.09775/) (2024)
- [A Unified Framework for Center-based Clustering of Distributed Data](https://mlsanity.com/paper/2402.01302/) (2024)

## Abstract (arXiv)

This paper considers decentralized minimization of N:=nm smooth non-convex cost functions equally divided over a directed network of n nodes. Specifically, we describe a stochastic first-order gradient method, called GT-SARAH, that employs a SARAH-type variance reduction technique and gradient tracking (GT) to address the stochastic and decentralized nature of the problem. We show that GT-SARAH, with appropriate algorithmic parameters, finds an ε-accurate first-order stationary point with Obig(maxbigN^frac12,n(1-λ)-2,n^frac23m^frac13(1-λ)-1bigLε-2big) gradient complexity, where (1-λ)∈(0,1] is the spectral gap of the network weight matrix and L is the smoothness parameter of the cost functions. This gradient complexity outperforms that of the existing decentralized stochastic gradient methods. In particular, in a big-data regime such that n = O(N^frac12(1-λ)3), this gradient complexity furthers reduces to O(N^frac12Lε-2), independent of the network topology, and matches that of the centralized near-optimal variance-reduced methods. Moreover, in this regime GT-SARAH achieves a non-asymptotic linear speedup, in that, the total number of gradient computations at each node is reduced by a factor of 1/n compared to the centralized near-optimal algorithms that perform all gradient computations at a single node. To the best of our knowledge, GT-SARAH is the first algorithm that achieves this property. In addition, we show that appropriate choices of local minibatch size balance the trade-offs between the gradient and communication complexity of GT-SARAH. Over infinite time horizon, we establish that all nodes in GT-SARAH asymptotically achieve consensus and converge to a first-order stationary point in the almost sure and mean-squared sense.