# Convergence Analysis of Distributed Stochastic Gradient Descent with Shuffling

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Sep 2017.

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

- [BGL: GPU-Efficient GNN Training by Optimizing Graph Data I/O and Preprocessing](https://mlsanity.com/paper/2112.08541/) (2021)
- [Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond](https://mlsanity.com/paper/2110.10342/) (2021)
- [On the Last-Iterate Convergence of Shuffling Gradient Methods](https://mlsanity.com/paper/2403.07723/) (2024)
- [Distributed Random Reshuffling over Networks](https://mlsanity.com/paper/2112.15287/) (2021)
- [On Batching Variable Size Inputs for Training End-to-End Speech Enhancement Systems](https://mlsanity.com/paper/2301.10587/) (2023)
- [Expansive Supervision for Neural Radiance Field](https://mlsanity.com/paper/2409.08056/) (2024)
- [Fundamental Limitations of Favorable Privacy-Utility Guarantees for DP-SGD](https://mlsanity.com/paper/2601.10237/) (2026)
- [The challenge of reproducible ML: an empirical study on the impact of bugs](https://mlsanity.com/paper/2109.03991/) (2021)
- [I/O in Machine Learning Applications on HPC Systems: A 360-degree Survey](https://mlsanity.com/paper/2404.10386/) (2024)
- [Sparse Checkpointing for Fast and Reliable MoE Training](https://mlsanity.com/paper/2412.15411/) (2024)
- [PGT-I: Scaling Spatiotemporal GNNs with Memory-Efficient Distributed Training](https://mlsanity.com/paper/2507.11683/) (2025)
- [Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization](https://mlsanity.com/paper/2111.03820/) (2021)
- [Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/2310.15976/) (2023)
- [SignSGD with Federated Voting](https://mlsanity.com/paper/2403.16372/) (2024)
- [Graph Learning at Scale: Characterizing and Optimizing Pre-Propagation GNNs](https://mlsanity.com/paper/2504.13266/) (2025)
- [cPNN: Continuous Progressive Neural Networks for Evolving Streaming Time Series](https://mlsanity.com/paper/2603.03040/) (2026)
- [KAKURENBO: Adaptively Hiding Samples in Deep Neural Network Training](https://mlsanity.com/paper/2310.10102/) (2023)
- [CycleSL: Server-Client Cyclical Update Driven Scalable Split Learning](https://mlsanity.com/paper/2511.18611/) (2025)
- [Quantifying the Impact of Lossy Compression on Neural Generative Surrogate Modeling](https://mlsanity.com/paper/2606.15959/) (2026)
- [Data-driven and machine-learning based prediction of wave propagation behavior in dam-break flood](https://mlsanity.com/paper/2209.08729/) (2022)
- [Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimization](https://mlsanity.com/paper/2410.22297/) (2024)
- [Implicit Modeling for Transferability Estimation of Vision Foundation Models](https://mlsanity.com/paper/2510.23145/) (2025)
- [VersaDB: A High-Performance AI Storage Database for Unifying Mutimodal Datasets](https://mlsanity.com/paper/2608.22795/) (2026)

## Abstract (arXiv)

When using stochastic gradient descent to solve large-scale machine learning problems, a common practice of data processing is to shuffle the training data, partition the data across multiple machines if needed, and then perform several epochs of training on the re-shuffled (either locally or globally) data. The above procedure makes the instances used to compute the gradients no longer independently sampled from the training data set. Then does the distributed SGD method have desirable convergence properties in this practical situation? In this paper, we give answers to this question. First, we give a mathematical formulation for the practical data processing procedure in distributed machine learning, which we call data partition with global/local shuffling. We observe that global shuffling is equivalent to without-replacement sampling if the shuffling operations are independent. We prove that SGD with global shuffling has convergence guarantee in both convex and non-convex cases. An interesting finding is that, the non-convex tasks like deep learning are more suitable to apply shuffling comparing to the convex tasks. Second, we conduct the convergence analysis for SGD with local shuffling. The convergence rate for local shuffling is slower than that for global shuffling, since it will lose some information if there's no communication between partitioned data. Finally, we consider the situation when the permutation after shuffling is not uniformly distributed (insufficient shuffling), and discuss the condition under which this insufficiency will not influence the convergence rate. Our theoretical results provide important insights to large-scale machine learning, especially in the selection of data processing methods in order to achieve faster convergence and good speedup. Our theoretical findings are verified by extensive experiments on logistic regression and deep neural networks.