# Decentralized Sum-of-Nonconvex Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 32 references that are in the map.
- First posted on arXiv 4 Feb 2024.

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

- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [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)
- [Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop](https://mlsanity.com/paper/1901.08689/) (2019)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates](https://mlsanity.com/paper/1704.07807/) (2017)
- [Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development](https://mlsanity.com/paper/1702.05122/) (2017)
- [Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence](https://mlsanity.com/paper/1912.04230/) (2019)
- [LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain](https://mlsanity.com/paper/1607.03463/) (2016)
- [An Optimal Algorithm for Decentralized Finite Sum Optimization](https://mlsanity.com/paper/2005.10675/) (2020)
- [Fast decentralized non-convex finite-sum optimization with recursive variance reduction](https://mlsanity.com/paper/2008.07428/) (2020)
- [DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization](https://mlsanity.com/paper/2110.01165/) (2021)
- [Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization](https://mlsanity.com/paper/1802.03866/) (2018)
- [DSA: Decentralized Double Stochastic Averaging Gradient Algorithm](https://mlsanity.com/paper/1506.04216/) (2015)
- [Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication](https://mlsanity.com/paper/1805.09969/) (2018)
- [Dual-Free Stochastic Decentralized Optimization with Variance Reduction](https://mlsanity.com/paper/2006.14384/) (2020)
- [An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums](https://mlsanity.com/paper/1905.11394/) (2019)
- [A Linearly Convergent Proximal Gradient Algorithm for Decentralized Optimization](https://mlsanity.com/paper/1905.07996/) (2019)
- [Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation](https://mlsanity.com/paper/1510.08896/) (2015)
- [PMGT-VR: A decentralized proximal-gradient algorithmic framework with variance reduction](https://mlsanity.com/paper/2012.15010/) (2020)
- [Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU](https://mlsanity.com/paper/1701.01722/) (2017)
- [Distributed Optimization Based on Gradient-tracking Revisited: Enhancing Convergence Rate via Surrogation](https://mlsanity.com/paper/1905.02637/) (2019)
- [On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization](https://mlsanity.com/paper/2210.13931/) (2022)

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

- [Decentralized Federated Learning by Partial Message Exchange](https://mlsanity.com/paper/2603.01730/) (2026)

## Abstract (arXiv)

We consider the optimization problem of minimizing the sum-of-nonconvex function, i.e., a convex function that is the average of nonconvex components. The existing stochastic algorithms for such a problem only focus on a single machine and the centralized scenario. In this paper, we study the sum-of-nonconvex optimization in the decentralized setting. We present a new theoretical analysis of the PMGT-SVRG algorithm for this problem and prove the linear convergence of their approach. However, the convergence rate of the PMGT-SVRG algorithm has a linear dependency on the condition number, which is undesirable for the ill-conditioned problem. To remedy this issue, we propose an accelerated stochastic decentralized first-order algorithm by incorporating the techniques of acceleration, gradient tracking, and multi-consensus mixing into the SVRG algorithm. The convergence rate of the proposed method has a square-root dependency on the condition number. The numerical experiments validate the theoretical guarantee of our proposed algorithms on both synthetic and real-world datasets.