GraB: Finding Provably Better Data Permutations than Random Reshuffling

Yucheng Lu, Wentao Guo, Christopher De Sa

TL;DR

While Random Reshuffling (RR) is the industry standard for training neural networks, it is mathematically far from optimal. This paper introduces GraB (Gradient Balancing), an algorithm that leverages discrepancy minimization theory to find data orderings that are provably and empirically faster than random shuffling. Crucially, GraB reduces the memory overhead of previous "greedy" ordering methods by over 100x, making smart data permutation viable for larger models.

The Problem with Random Reshuffling

In Stochastic Gradient Descent (SGD), the order in which data is presented to the model significantly impacts convergence. Most practitioners default to Random Reshuffling—shuffling the dataset at the start of every epoch—because it converges faster than simple sampling with replacement.

Researchers have long suspected that "smarter" sequences exist. Recent "greedy" ordering strategies have shown empirical success by actively selecting the next best data point to process. However, these methods suffer from two major flaws:

  1. Lack of Theory: There was no solid proof that these greedy sequences actually converge at a faster rate than random ones.
  2. Resource Intensity: These methods typically require storing the gradient for every single data point (an $O(nd)$ memory footprint) and performing complex sorting ($O(n^2)$ computation). This makes them completely unusable for large-scale models like BERT or ResNet.

Enter GraB: Gradient Balancing

To bridge the gap between optimization and discrepancy theory, the authors formulate an example-ordering framework based on herding. The goal of herding is to sequence a set of vectors such that their prefix sums stay as close as possible to the total mean.

Building on this, the paper's primary contribution is GraB (Gradient Balancing). Instead of storing every gradient, GraB operates "online" during an epoch:

  • Centering: It uses a running average of gradients from the previous epoch to "center" the current gradients.
  • Balancing: For each data point, it decides whether to assign it a positive or negative "sign" based on whether it helps balance out the cumulative gradient error.
  • Reordering: Based on these signs, it constructs the sequence for the next epoch by placing "positive" examples at the front and "negative" examples at the back (in reverse order).
The GraB algorithm pipeline: balancing gradients to minimize discrepancy.

This approach drastically reduces memory requirements. You only need to store a few vectors the size of your model ($O(d)$), regardless of how many millions of images are in your dataset.

Key Insights and Theoretical Breakthroughs

Theoretical comparison of Random Reshuffling, Herding, and GraB.
  • The $O(T^{-2/3})$ Breakthrough: The authors prove that herding-based SGD converges at a rate of $O(T^{-2/3})$ on smooth, non-convex objectives. This is theoretically faster than the $O(n^{1/3}T^{-2/3})$ rate of Random Reshuffling, providing the "missing" theoretical justification for non-random ordering.
  • Stale Gradients are Sufficient: A key insight is that you don't need perfectly fresh gradients to order your data. Using "stale" gradients—those calculated during the previous epoch—is enough to guide the balancing process without doubling the computational cost.
  • Beyond Training Loss: Interestingly, GraB doesn't just minimize training loss faster; it often results in better validation accuracy. This suggests that balanced data ordering might have a regularizing effect that helps models generalize better.

Empirical Results

The authors evaluated GraB across several standard machine learning benchmarks to prove its versatility, including Computer Vision (MNIST, CIFAR-10) and Natural Language Processing (WikiText-2, GLUE benchmarks with BERT-Tiny).

  • Efficiency Gains: On CIFAR-10, GraB reduced the memory overhead from 1.44 GB (required by previous greedy methods) to just 0.46 MB.
  • Scalability: On larger NLP tasks (WikiText and GLUE), previous state-of-the-art greedy methods triggered "Out of Memory" (OOM) errors. In contrast, GraB ran smoothly and outperformed Random Reshuffling.
  • Convergence Speed: GraB consistently reached lower training loss and higher validation accuracy in fewer epochs compared to RR and other baselines like "Shuffle Once" or "FlipFlop."

Limitations and Future Work

While GraB is a significant step forward, it has a few practical limitations. GraB is most effective when it can see gradients for individual examples. Standard deep learning frameworks (like PyTorch) are optimized for batching, making extracting per-example gradients computationally expensive. The authors suggest using JAX or gradient accumulation as workarounds, but native integration into batch-based training remains a challenge.

Additionally, the theoretical bounds assume normalized gradients. While the authors used a "naive" balancing version that ignores normalization and still saw great results, future work could explore if adaptive normalization further stabilizes the algorithm. Finally, specifically tuning learning rates for GraB might unlock even more performance gains.

Summary updated

Abstract

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 \emph{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(n^{1/3}T^{-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(n^2)$ 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\times$.
BibTeX
@inproceedings{lu2022grab,
  author = {Yucheng Lu and Wentao Guo and Christopher De Sa},
  title = {{GraB: Finding Provably Better Data Permutations than Random Reshuffling}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=nDemfqKHTpK},
}
Figure