# On the Computation and Communication Complexity of Parallel SGD with Dynamic Batch Sizes for Stochastic Non-Convex Optimization

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 May 2019.

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

- [AdaptSFL: Adaptive Split Federated Learning in Resource-constrained Edge Networks](https://mlsanity.com/paper/2403.13101/) (2024)
- [What Do We Mean by Generalization in Federated Learning?](https://mlsanity.com/paper/2110.14216/) (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)
- [Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective](https://mlsanity.com/paper/2111.03741/) (2021)
- [Hierarchical Split Federated Learning: Convergence Analysis and System Optimization](https://mlsanity.com/paper/2412.07197/) (2024)
- [Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2205.13746/) (2022)
- [HASFL: Heterogeneity-aware Split Federated Learning over Edge Computing Systems](https://mlsanity.com/paper/2506.08426/) (2025)
- [Taming Resource Heterogeneity In Distributed ML Training With Dynamic Batching](https://mlsanity.com/paper/2305.12213/) (2023)
- [Communication-Efficient Large-Scale Distributed Deep Learning: A Comprehensive Survey](https://mlsanity.com/paper/2404.06114/) (2024)
- [Scavenger: A Cloud Service for Optimizing Cost and Performance of ML Training](https://mlsanity.com/paper/2303.06659/) (2023)
- [Federated Submodel Optimization for Hot and Cold Data Features](https://mlsanity.com/paper/2109.07704/) (2021)
- [GBA: A Tuning-free Approach to Switch between Synchronous and Asynchronous Training for Recommendation Model](https://mlsanity.com/paper/2205.11048/) (2022)
- [FedBIAD: Communication-Efficient and Accuracy-Guaranteed Federated Learning with Bayesian Inference-Based Adaptive Dropout](https://mlsanity.com/paper/2307.07172/) (2023)
- [Communication-Efficient Distributed Deep Learning via Federated Dynamic Averaging](https://mlsanity.com/paper/2405.20988/) (2024)
- [Why Does Adaptive Batching Help LLM Pretraining? A Perspective from Unbounded Variance](https://mlsanity.com/paper/2610.02355/) (2026)

## Abstract (arXiv)

For SGD based distributed stochastic optimization, computation complexity, measured by the convergence rate in terms of the number of stochastic gradient calls, and communication complexity, measured by the number of inter-node communication rounds, are two most important performance metrics. The classical data-parallel implementation of SGD over N workers can achieve linear speedup of its convergence rate but incurs an inter-node communication round at each batch. We study the benefit of using dynamically increasing batch sizes in parallel SGD for stochastic non-convex optimization by charactering the attained convergence rate and the required number of communication rounds. We show that for stochastic non-convex optimization under the P-L condition, the classical data-parallel SGD with exponentially increasing batch sizes can achieve the fastest known O(1/(NT)) convergence with linear speedup using only log(T) communication rounds. For general stochastic non-convex optimization, we propose a Catalyst-like algorithm to achieve the fastest known O(1/√NT) convergence with only O(√NTlog(fracTN)) communication rounds.