In the standard practice of training neural networks, we treat data shuffling as a solved problem. We use Random Reshuffling (RR)—permuting the dataset at the start of each epoch—because it is known to converge faster than sampling with replacement. However, recent research suggests that "random" is not "optimal." By carefully choosing the order in which a model sees training examples, we can significantly accelerate convergence beyond the limits of random chance.
The Intuition: Gradient Balancing
To understand why data order matters, consider what happens during a single epoch of Stochastic Gradient Descent (SGD). In each step, we calculate a gradient based on a small batch and update our weights. Our goal is for the sum of these stochastic gradients to match the true gradient of the entire dataset.
Random Reshuffling relies on the law of large numbers to ensure that, on average, these errors cancel out. But as Yucheng Lu and Christopher De Sa argue in their work on GraB (Gradient Balancing), we don't have to leave this to chance. If the first example in an epoch pulls the model weights in one direction, we should intentionally pick a second example that pulls them back in the opposite direction.
By "balancing" gradients in this way, we minimize the cumulative error throughout the epoch. While RR achieves a convergence rate of $O(1/T^2)$ for certain smooth functions, GraB provides a theoretical rate of $O(T^{-2/3})$, outperforming random permutations by actively reducing the variance of the gradient estimates.
Exploiting Geometric Structure
The benefit of specific orderings often depends on the geometry of the optimization landscape. For example, Shashank Rajput and Dimitris Papailiopoulos demonstrated that for quadratic functions, a simple strategy called FLIPFLOP—which involves reversing the data permutation every other epoch—can drastically speed up training.
This suggests that the "gold standard" of random shuffling is actually a minimax strategy: it is the best we can do if we know nothing about our data. But as Amirkeivan Mohtashami, Martin Jaggi, and Sebastian U. Stich show in Characterizing & Finding Good Data Orderings, when we have high-variance gradients, greedy algorithms that sequence data points based on their contribution to the total gradient can outperform RR by over 14% in accuracy. Even simple heuristics, such as processing examples with the largest initial gradients first, can lead to faster error reduction in convex and deep learning tasks.
Scaling to Distributed Systems
The challenge of data ordering becomes more complex in distributed settings, where data is spread across multiple workers. If every worker independently performs its own balanced shuffling, the global update might still be suboptimal.
To solve this, A. Feder Cooper and colleagues developed CD-GraB (Coordinated Distributed Gradient Balancing). The algorithm uses a technique called "PairBalance" to coordinate how parallel workers sequence their data. By ensuring that the gradients are balanced not just locally on one machine, but globally across the entire cluster, they achieve a provable linear speedup in convergence relative to the number of workers.
The Fundamental Limits of Ordering
While these informed permutations offer significant gains, researchers have also sought to find the theoretical "ceiling" of this approach. How much better than random can we actually get?
In Tighter Lower Bounds for Shuffling SGD, Jaeyoung Cha and Chulhee Yun established "perfectly tight" lower bounds for any permutation-based policy. Their analysis confirms that algorithms like GraB have reached a fundamental performance limit. This means that while we can certainly do better than random reshuffling by using gradient information, we have now identified the mathematical boundary of how much training efficiency can be squeezed out of data ordering alone.