# Proximal Stochastic Recursive Momentum Methods for Nonconvex Composite Decentralized Optimization

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Nov 2022.

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

- [Decentralized Riemannian Algorithm for Nonconvex Minimax Problems](https://mlsanity.com/paper/2302.03825/) (2023)
- [Decentralized gradient descent maximization method for composite nonconvex strongly-concave minimax problems](https://mlsanity.com/paper/2304.02441/) (2023)
- [A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic Composite Optimization](https://mlsanity.com/paper/2302.09766/) (2023)
- [FedCanon: Non-Convex Composite Federated Learning with Efficient Proximal Operation on Heterogeneous Data](https://mlsanity.com/paper/2504.11903/) (2025)
- [Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problems](https://mlsanity.com/paper/2307.07113/) (2023)
- [Argus: Federated Non-convex Bilevel Learning over 6G Space-Air-Ground Integrated Network](https://mlsanity.com/paper/2505.09106/) (2025)
- [Compressed and Sparse Models for Non-Convex Decentralized Learning](https://mlsanity.com/paper/2311.05760/) (2023)
- [Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum](https://mlsanity.com/paper/2504.12742/) (2025)
- [Compressed Proximal Federated Learning for Non-Convex Composite Optimization on Heterogeneous Data](https://mlsanity.com/paper/2603.07654/) (2026)
- [Private Decentralized Optimization with Noise Reduction and Bias Correction](https://mlsanity.com/paper/2609.27658/) (2026)

## Abstract (arXiv)

Consider a network of N decentralized computing agents collaboratively solving a nonconvex stochastic composite problem. In this work, we propose a single-loop algorithm, called DEEPSTORM, that achieves optimal sample complexity for this setting. Unlike double-loop algorithms that require a large batch size to compute the (stochastic) gradient once in a while, DEEPSTORM uses a small batch size, creating advantages in occasions such as streaming data and online learning. This is the first method achieving optimal sample complexity for decentralized nonconvex stochastic composite problems, requiring O(1) batch size. We conduct convergence analysis for DEEPSTORM with both constant and diminishing step sizes. Additionally, under proper initialization and a small enough desired solution error, we show that DEEPSTORM with a constant step size achieves a network-independent sample complexity, with an additional linear speed-up with respect to N over centralized methods. All codes are made available at https://github.com/gmancino/DEEPSTORM.