# Parallel Restarted SPIDER -- Communication Efficient Distributed Nonconvex Optimization with Optimal Computation Complexity

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Dec 2019.

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

- [MARINA: Faster Non-Convex Distributed Learning with Compression](https://mlsanity.com/paper/2102.07845/) (2021)
- [STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning](https://mlsanity.com/paper/2106.10435/) (2021)
- [Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning](https://mlsanity.com/paper/2102.03198/) (2021)
- [Private Non-Convex Federated Learning Without a Trusted Server](https://mlsanity.com/paper/2203.06735/) (2022)
- [DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization](https://mlsanity.com/paper/2202.01268/) (2022)
- [Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning](https://mlsanity.com/paper/2202.06083/) (2022)
- [FedDRO: Federated Compositional Optimization for Distributionally Robust Learning](https://mlsanity.com/paper/2311.12652/) (2023)
- [Local Methods with Adaptivity via Scaling](https://mlsanity.com/paper/2406.00846/) (2024)

## Abstract (arXiv)

In this paper, we propose a distributed algorithm for stochastic smooth, non-convex optimization. We assume a worker-server architecture where N nodes, each having n (potentially infinite) number of samples, collaborate with the help of a central server to perform the optimization task. The global objective is to minimize the average of local cost functions available at individual nodes. The proposed approach is a non-trivial extension of the popular parallel-restarted SGD algorithm, incorporating the optimal variance-reduction based SPIDER gradient estimator into it. We prove convergence of our algorithm to a first-order stationary solution. The proposed approach achieves the best known communication complexity O(ε-1) along with the optimal computation complexity. For finite-sum problems (finite n), we achieve the optimal computation (IFO) complexity O(√Nnε-1). For online problems (n unknown or infinite), we achieve the optimal IFO complexity O(ε-3/2). In both the cases, we maintain the linear speedup achieved by existing methods. This is a massive improvement over the O(ε-2) IFO complexity of the existing approaches. Additionally, our algorithm is general enough to allow non-identical distributions of data across workers, as in the recently proposed federated learning paradigm.