# GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learning

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 53 references that are in the map.
- First posted on arXiv 4 May 2021.

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

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [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)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Non-convex Finite-Sum Optimization Via SCSG Methods](https://mlsanity.com/paper/1706.09156/) (2017)
- [Collaborative Deep Learning in Fixed Topology Networks](https://mlsanity.com/paper/1706.07880/) (2017)
- [On Nonconvex Decentralized Gradient Descent](https://mlsanity.com/paper/1608.05766/) (2016)
- [Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimization](https://mlsanity.com/paper/1905.05920/) (2019)
- [DSA: Decentralized Double Stochastic Averaging Gradient Algorithm](https://mlsanity.com/paper/1506.04216/) (2015)
- [Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimization](https://mlsanity.com/paper/1802.06903/) (2018)
- [Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach](https://mlsanity.com/paper/1910.05857/) (2019)
- [Dictionary Learning over Distributed Models](https://mlsanity.com/paper/1402.1515/) (2014)
- [Cubic Regularization with Momentum for Nonconvex Optimization](https://mlsanity.com/paper/1810.03763/) (2018)
- [Distributed Stochastic Multi-Task Learning with Graph Regularization](https://mlsanity.com/paper/1802.03830/) (2018)
- [A Decentralized Second-Order Method with Exact Linear Convergence Rate for Consensus Optimization](https://mlsanity.com/paper/1602.00596/) (2016)
- [Decentralized Quasi-Newton Methods](https://mlsanity.com/paper/1605.00933/) (2016)
- [Distributed Linear Model Clustering over Networks: A Tree-Based Fused-Lasso ADMM Approach](https://mlsanity.com/paper/1905.11549/) (2019)
- [Variance-Reduced Decentralized Stochastic Optimization with Gradient Tracking -- Part II: GT-SVRG](https://mlsanity.com/paper/1910.04057/) (2019)
- [Distributed Learning in the Non-Convex World: From Batch to Streaming Data, and Beyond](https://mlsanity.com/paper/2001.04786/) (2020)

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

- [Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints](https://mlsanity.com/paper/2311.00678/) (2023)
- [INTERACT: Achieving Low Sample and Communication Complexities in Decentralized Bilevel Learning over Networks](https://mlsanity.com/paper/2207.13283/) (2022)
- [DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2202.00255/) (2022)
- [Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax Problems](https://mlsanity.com/paper/2304.10902/) (2023)
- [Serverless Federated AUPRC Optimization for Multi-Party Collaborative Imbalanced Data Mining](https://mlsanity.com/paper/2308.03035/) (2023)
- [Stochastic Gradient Methods with Compressed Communication for Decentralized Saddle Point Problems](https://mlsanity.com/paper/2205.14452/) (2022)
- [Faster Adaptive Decentralized Learning Algorithms](https://mlsanity.com/paper/2408.09775/) (2024)
- [Achieving Linear Speedup in Decentralized Stochastic Compositional Minimax Optimization](https://mlsanity.com/paper/2307.13430/) (2023)

## Abstract (arXiv)

Decentralized nonconvex optimization has received increasing attention in recent years in machine learning due to its advantages in system robustness, data privacy, and implementation simplicity. However, three fundamental challenges in designing decentralized optimization algorithms are how to reduce their sample, communication, and memory complexities. In this paper, we propose a underlinegradient-underlinetracking-based underlinestochastic underlinerecursive underlinemomentum (GT-STORM) algorithm for efficiently solving nonconvex optimization problems. We show that to reach an ε2-stationary solution, the total number of sample evaluations of our algorithm is tildeO(m1/2ε-3) and the number of communication rounds is tildeO(m-1/2ε-3), which improve the O(ε-4) costs of sample evaluations and communications for the existing decentralized stochastic gradient algorithms. We conduct extensive experiments with a variety of learning models, including non-convex logistical regression and convolutional neural networks, to verify our theoretical findings. Collectively, our results contribute to the state of the art of theories and algorithms for decentralized network optimization.