# D-SPIDER-SFO: A Decentralized Optimization Algorithm with Faster Convergence Rate for Nonconvex Problems

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Nov 2019.

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

- [Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2102.04761/) (2021)
- [LMC: Fast Training of GNNs via Subgraph Sampling with Provable Convergence](https://mlsanity.com/paper/2302.00924/) (2023)
- [A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2102.06752/) (2021)
- [DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization](https://mlsanity.com/paper/2110.01165/) (2021)
- [Decentralized Riemannian Algorithm for Nonconvex Minimax Problems](https://mlsanity.com/paper/2302.03825/) (2023)
- [Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax Problems](https://mlsanity.com/paper/2304.10902/) (2023)
- [Decentralized Stochastic Variance Reduced Extragradient Method](https://mlsanity.com/paper/2202.00509/) (2022)
- [Serverless Federated AUPRC Optimization for Multi-Party Collaborative Imbalanced Data Mining](https://mlsanity.com/paper/2308.03035/) (2023)
- [Distributed Random Reshuffling Methods with Improved Convergence](https://mlsanity.com/paper/2306.12037/) (2023)
- [Faster Adaptive Decentralized Learning Algorithms](https://mlsanity.com/paper/2408.09775/) (2024)
- [Decentralized Non-convex Stochastic Optimization with Heterogeneous Variance](https://mlsanity.com/paper/2602.11789/) (2026)

## Abstract (arXiv)

Decentralized optimization algorithms have attracted intensive interests recently, as it has a balanced communication pattern, especially when solving large-scale machine learning problems. Stochastic Path Integrated Differential Estimator Stochastic First-Order method (SPIDER-SFO) nearly achieves the algorithmic lower bound in certain regimes for nonconvex problems. However, whether we can find a decentralized algorithm which achieves a similar convergence rate to SPIDER-SFO is still unclear. To tackle this problem, we propose a decentralized variant of SPIDER-SFO, called decentralized SPIDER-SFO (D-SPIDER-SFO). We show that D-SPIDER-SFO achieves a similar gradient computation cost---that is, O(ε-3) for finding an ε-approximate first-order stationary point---to its centralized counterpart. To the best of our knowledge, D-SPIDER-SFO achieves the state-of-the-art performance for solving nonconvex optimization problems on decentralized networks in terms of the computational cost. Experiments on different network configurations demonstrate the efficiency of the proposed method.