# Communication-Efficient, 2D Parallel Stochastic Gradient Descent for Distributed-Memory Optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 38 references that are in the map.
- First posted on arXiv 13 Jan 2025.

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

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training](https://mlsanity.com/paper/1712.01887/) (2017)
- [Stochastic Controlled Averaging for Federated Learning with Communication Compression](https://mlsanity.com/paper/2308.08165/) (2023)
- [CoCoA: A General Framework for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1611.02189/) (2016)
- [Distributed Optimization with Arbitrary Local Solvers](https://mlsanity.com/paper/1512.04039/) (2015)
- [Avoiding communication in primal and dual block coordinate descent methods](https://mlsanity.com/paper/1612.04003/) (2016)
- [Avoiding Communication in Logistic Regression](https://mlsanity.com/paper/2011.08281/) (2020)
- [Scalable Dual Coordinate Descent for Kernel Methods](https://mlsanity.com/paper/2406.18001/) (2024)
- [Avoiding Synchronization in First-Order Methods for Sparse Convex Optimization](https://mlsanity.com/paper/1712.06047/) (2017)

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

- [Evolution of Optimization Methods: Algorithms, Scenarios, and Evaluations](https://mlsanity.com/paper/2604.12968/) (2026)
- [Mixed-Precision Communication-Avoiding SGD for Generalized Linear Models on GPUs](https://mlsanity.com/paper/2606.18463/) (2026)

## Abstract (arXiv)

Distributed-memory implementations of numerical optimization algorithm, such as stochastic gradient descent (SGD), require interprocessor communication at every iteration of the algorithm. On modern distributed-memory clusters where communication is more expensive than computation, the scalability and performance of these algorithms are limited by communication cost. This work generalizes prior work on 1D s-step SGD and 1D Federated SGD with Averaging (FedAvg) to yield a 2D parallel SGD method (HybridSGD) which attains a continuous performance trade off between the two baseline algorithms. We present theoretical analysis which show the convergence, computation, communication, and memory trade offs between s-step SGD, FedAvg, 2D parallel SGD, and other parallel SGD variants. We implement all algorithms in C++ and MPI and evaluate their performance on a Cray EX supercomputing system. Our empirical results show that HybridSGD achieves better convergence than FedAvg at similar processor scales while attaining speedups of 5.3× over s-step SGD and speedups up to 121× over FedAvg when used to solve binary classification tasks using the convex, logistic regression model on datasets obtained from the LIBSVM repository.