# Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 33 references that are in the map.
- First posted on arXiv 3 Feb 2022.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Not All Samples Are Created Equal: Deep Learning with Importance Sampling](https://mlsanity.com/paper/1803.00942/) (2018)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Why Random Reshuffling Beats Stochastic Gradient Descent](https://mlsanity.com/paper/1510.08560/) (2015)
- [Variance Reduction in SGD by Distributed Importance Sampling](https://mlsanity.com/paper/1511.06481/) (2015)
- [Manipulating SGD with Data Ordering Attacks](https://mlsanity.com/paper/2104.09667/) (2021)
- [Random Shuffling Beats SGD after Finite Epochs](https://mlsanity.com/paper/1806.10077/) (2018)
- [How Good is SGD with Random Shuffling?](https://mlsanity.com/paper/1908.00045/) (2019)
- [A Unified Convergence Analysis for Shuffling-Type Gradient Methods](https://mlsanity.com/paper/2002.08246/) (2020)
- [Closing the convergence gap of SGD without replacement](https://mlsanity.com/paper/2002.10400/) (2020)
- [A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates](https://mlsanity.com/paper/1806.10188/) (2018)
- [Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond](https://mlsanity.com/paper/2110.10342/) (2021)
- [Choosing the Sample with Lowest Loss makes SGD Robust](https://mlsanity.com/paper/2001.03316/) (2020)
- [Safe Adaptive Importance Sampling](https://mlsanity.com/paper/1711.02637/) (2017)
- [Permutation-Based SGD: Is Random Optimal?](https://mlsanity.com/paper/2102.09718/) (2021)
- [Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates](https://mlsanity.com/paper/2103.02351/) (2021)
- [Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization](https://mlsanity.com/paper/1603.00570/) (2016)

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

- [On The Impact of Machine Learning Randomness on Group Fairness](https://mlsanity.com/paper/2307.04138/) (2023)
- [Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond](https://mlsanity.com/paper/2303.07160/) (2023)
- [GraB: Finding Provably Better Data Permutations than Random Reshuffling](https://mlsanity.com/paper/2205.10733/) (2022)
- [AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms](https://mlsanity.com/paper/2310.20452/) (2023)
- [On the Last-Iterate Convergence of Shuffling Gradient Methods](https://mlsanity.com/paper/2403.07723/) (2024)
- [Coordinating Distributed Example Orders for Provably Accelerated Training](https://mlsanity.com/paper/2302.00845/) (2023)
- [On Convergence of Incremental Gradient for Non-Convex Smooth Functions](https://mlsanity.com/paper/2305.19259/) (2023)
- [Select without Fear: Almost All Mini-Batch Schedules Generalize Optimally](https://mlsanity.com/paper/2305.02247/) (2023)
- [Understanding the Training Speedup from Sampling with Approximate Losses](https://mlsanity.com/paper/2402.07052/) (2024)
- [The Order Is The Message](https://mlsanity.com/paper/2603.25047/) (2026)
- [TideGS: Scalable Training of Over One Billion 3D Gaussian Splatting Primitives via Out-of-Core Optimization](https://mlsanity.com/paper/2605.20150/) (2026)
- [Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling](https://mlsanity.com/paper/2411.05868/) (2024)
- [Ordering for Non-Replacement SGD](https://mlsanity.com/paper/2306.15848/) (2023)
- [Stochastic optimization with arbitrary recurrent data sampling](https://mlsanity.com/paper/2401.07694/) (2024)
- [Shuffling Heuristic in Variational Inequalities: Establishing New Convergence Guarantees](https://mlsanity.com/paper/2509.04133/) (2025)
- [CFR without Unbiasedness: Deterministic Guarantees for Persistent Public-Chance Schedules](https://mlsanity.com/paper/2608.14761/) (2026)

## Abstract (arXiv)

While SGD, which samples from the data with replacement is widely studied in theory, a variant called Random Reshuffling (RR) is more common in practice. RR iterates through random permutations of the dataset and has been shown to converge faster than SGD. When the order is chosen deterministically, a variant called incremental gradient descent (IG), the existing convergence bounds show improvement over SGD but are worse than RR. However, these bounds do not differentiate between a good and a bad ordering and hold for the worst choice of order. Meanwhile, in some cases, choosing the right order when using IG can lead to convergence faster than RR. In this work, we quantify the effect of order on convergence speed, obtaining convergence bounds based on the chosen sequence of permutations while also recovering previous results for RR. In addition, we show benefits of using structured shuffling when various levels of abstractions (e.g. tasks, classes, augmentations, etc.) exists in the dataset in theory and in practice. Finally, relying on our measure, we develop a greedy algorithm for choosing good orders during training, achieving superior performance (by more than 14 percent in accuracy) over RR.