GraB: Finding Provably Better Data Permutations than Random Reshuffling

Yucheng Lu, Wentao Guo, Christopher De

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 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$.

Introduction

In stochastic gradient descent (SGD), the order in which we present data to the model matters. Most practitioners use Random Reshuffling (RR)—shuffling the dataset at the start of every epoch—because it converges faster than sampling with replacement. However, theory suggests that a random order is far from optimal. While "greedy" ordering strategies exist that can beat RR, they suffer from two major flaws: they lack rigorous theoretical justification and they are prohibitively resource-intensive, typically requiring $O(nd)$ memory and $O(n^2)$ computation. This paper introduces GraB (Gradient Balancing), a data-ordering strategy that is provably better than RR, computationally efficient, and memory-light.

Methodology: The Herding Framework and GraB

The authors bridge the gap between optimization and discrepancy theory through a framework called herding. They prove that if a permutation minimizes the "average gradient error," SGD converges at a rate of $O(T^{-2/3})$, which is faster than RR's $O(n^{1/3}T^{-2/3})$ because it removes the dependence on the dataset size $n$ in the dominant term.

To make this practical, they introduce GraB, an online algorithm based on vector balancing:

  • Stale Gradients: GraB uses gradients computed during the previous epoch as estimates to avoid doubling the computational workload.
  • Online Balancing: As gradients are computed, GraB assigns a sign (+1 or -1) to each example based on a running sum of centered gradients, aiming to keep this sum as small as possible.
  • The Reordering Trick: At the end of an epoch, examples are reordered for the next epoch: those assigned +1 are placed at the beginning, while those assigned -1 are placed at the end in reverse order.
The GraB mechanism: (a) illustrates the balancing and reordering process, while (b) shows how reordering significantly reduces the summed norm compared to random ordering.

Key Results

GraB consistently outperformed Random Reshuffling and "Shuffle Once" across all tested datasets (MNIST, CIFAR10, WikiText-2, and GLUE) in terms of both training loss and wall-clock time. It matched or exceeded the performance of state-of-the-art greedy ordering methods while being significantly more efficient.

Comparison of convergence rates and resource requirements. GraB matches the improved $O(T^{-2/3})$ rate of herding while maintaining the efficiency of Random Reshuffling.

On GLUE tasks with BERT, greedy ordering crashed due to Out-Of-Memory (OOM) errors, while GraB ran smoothly with less than 1% of the memory footprint. Furthermore, GraB often resulted in higher validation accuracy, suggesting that "balanced" gradient updates might act as a beneficial regularizer.

Limitations and Future Work

GraB ideally requires per-example gradients. While frameworks like JAX support this efficiently, standard PyTorch accumulates gradients over a batch, requiring workarounds. Additionally, the benefits are most pronounced when reordering at the individual example level; reordering at a coarse batch level reduces statistical gains. Future work may explore more sophisticated balancing subroutines for extremely high-dimensional settings.

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 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},
  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