# GraB: Finding Provably Better Data Permutations than Random Reshuffling

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 47 references that are in the map.
- First posted on arXiv 22 May 2022.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Curriculum Learning: A Survey](https://mlsanity.com/paper/2101.10382/) (2021)
- [Automated Curriculum Learning for Neural Networks](https://mlsanity.com/paper/1704.03003/) (2017)
- [Teacher-Student Curriculum Learning](https://mlsanity.com/paper/1707.00183/) (2017)
- [Regularizing and Optimizing LSTM Language Models](https://mlsanity.com/paper/1708.02182/) (2017)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [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)
- [Random Shuffling Beats SGD after Finite Epochs](https://mlsanity.com/paper/1806.10077/) (2018)
- [Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey](https://mlsanity.com/paper/1507.01030/) (2015)
- [Convergence Rate of Incremental Gradient and Newton Methods](https://mlsanity.com/paper/1510.08562/) (2015)
- [Moniqua: Modulo Quantized Communication in Decentralized SGD](https://mlsanity.com/paper/2002.11787/) (2020)
- [Discrepancy Minimization via a Self-Balancing Walk](https://mlsanity.com/paper/2006.14009/) (2020)
- [Permutation-Based SGD: Is Random Optimal?](https://mlsanity.com/paper/2102.09718/) (2021)
- [Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods](https://mlsanity.com/paper/2202.01838/) (2022)
- [Variance Reduced Training with Stratified Sampling for Forecasting Models](https://mlsanity.com/paper/2103.02062/) (2021)
- [On-Line Balancing of Random Inputs](https://mlsanity.com/paper/1903.06898/) (2019)
- [Online Vector Balancing and Geometric Discrepancy](https://mlsanity.com/paper/1912.03350/) (2019)
- [Online Discrepancy Minimization for Stochastic Arrivals](https://mlsanity.com/paper/2007.10622/) (2020)
- [Algorithmic Discrepancy Beyond Partial Coloring](https://mlsanity.com/paper/1611.01805/) (2016)
- [Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization](https://mlsanity.com/paper/1910.01073/) (2019)

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

- [LLMs learn governing principles of dynamical systems, revealing an in-context neural scaling law](https://mlsanity.com/paper/2402.00795/) (2024)
- [Repeated Random Sampling for Minimizing the Time-to-Accuracy of Learning](https://mlsanity.com/paper/2305.18424/) (2023)
- [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)
- [SonicMoE: Accelerating MoE with IO and Tile-aware Optimizations](https://mlsanity.com/paper/2512.14080/) (2025)
- [Mini-Batch Optimization of Contrastive Loss](https://mlsanity.com/paper/2307.05906/) (2023)
- [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)
- [Low-Rank Thinning](https://mlsanity.com/paper/2502.12063/) (2025)
- [Optimizer Memory Makes Shuffle Order a First-Order Source of Fine-Tuning Noise](https://mlsanity.com/paper/2606.29554/) (2026)
- [High Probability Guarantees for Random Reshuffling](https://mlsanity.com/paper/2311.11841/) (2023)
- [Fast Convergence of Random Reshuffling under Over-Parameterization and the Polyak-L ojasiewicz Condition](https://mlsanity.com/paper/2304.00459/) (2023)
- [Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling](https://mlsanity.com/paper/2411.05868/) (2024)
- [GraB-sampler: Optimal Permutation-based SGD Data Sampler for PyTorch](https://mlsanity.com/paper/2309.16809/) (2023)
- [Stochastic optimization with arbitrary recurrent data sampling](https://mlsanity.com/paper/2401.07694/) (2024)
- [Accelerating Federated Learning by Selecting Beneficial Herd of Local Gradients](https://mlsanity.com/paper/2403.16557/) (2024)
- [CFR without Unbiasedness: Deterministic Guarantees for Persistent Public-Chance Schedules](https://mlsanity.com/paper/2608.14761/) (2026)
- [Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, H"older Geometry, and Composite Proximal Extensions](https://mlsanity.com/paper/2609.04578/) (2026)
- [Conflicting Supervision Moves Commitment, Not Capability: A 12.29σ arrangement effect that is exactly zero under a convention-agnostic score](https://mlsanity.com/paper/2610.00234/) (2026)

## Abstract (arXiv)

Random reshuffling, which randomly permutes the dataset each epoch, is widely adopted in model training because it yields faster convergence than with-replacement sampling. Recent studies indicate greedily chosen data orderings can further speed up convergence empirically, at the cost of using more computation and memory. However, greedy ordering lacks theoretical justification and has limited utility due to its non-trivial memory and computation overhead. In this paper, we first formulate an example-ordering framework named herding and answer affirmatively that SGD with herding converges at the rate O(T-2/3) on smooth, non-convex objectives, faster than the O(n1/3T-2/3) obtained by random reshuffling, where n denotes the number of data points and T denotes the total number of iterations. To reduce the memory overhead, we leverage discrepancy minimization theory to propose an online Gradient Balancing algorithm (GraB) that enjoys the same rate as herding, while reducing the memory usage from O(nd) to just O(d) and computation from O(n2) to O(n), where d denotes the model dimension. We show empirically on applications including MNIST, CIFAR10, WikiText and GLUE that GraB can outperform random reshuffling in terms of both training and validation performance, and even outperform state-of-the-art greedy ordering while reducing memory usage over 100×.