Shuffling the Augmentations Too: Restoring Random Reshuffling's Cancellation in Augmented Training

Almost every deep learning run visits the training set in a fresh random order each epoch, a scheme called random reshuffling. Theory explains why this beats drawing examples independently with replacement. Within an epoch the individual gradient steps are biased, because what remains in the pool depends on what has already been drawn. Over a full pass, though, every example is used exactly once, so the per-example errors add up to zero at the optimum and largely cancel. That argument needs a fixed, finite set of loss terms. Modern training does not have one. Random crops, flips, dropout and mixing mean that "example 17" in epoch 3 is a different loss function from "example 17" in epoch 4. Nothing in the shuffling literature accounts for this.

Our claim is simple and testable. Under random reshuffling, gradient noise splits into two parts. The part that varies between examples is cancelled by shuffling. The part that varies within an example, across its random augmentations, is not cancelled at all and behaves like with-replacement noise. This one fact may explain a known puzzle: order-based speedups that hold on convex problems, such as reversing the order every other epoch, disappear on neural networks. It also suggests a cheap fix. Sample the augmentations "without replacement" as well, by stratifying or freezing them over short blocks of epochs, so that each block is again an exact pass over a finite sum and the cancellation argument applies to the whole noise.

Core Claim

Write the per-step loss as $f_{i,\xi}(x)$, where $i$ indexes the example, $\xi$ is the random augmentation, and $x$ are the parameters. Near a solution $x^*$, the total gradient noise variance $\sigma^2$ splits as

$$ \sigma^2 = \underbrace{\tfrac{1}{n}\textstyle\sum_i \|\mathbb{E}_\xi \nabla f_{i,\xi}(x^*) - \nabla F(x^*)\|^2}_{\sigma_b^2\ \text{(between examples)}} + \underbrace{\tfrac{1}{n}\textstyle\sum_i \mathbb{E}_\xi\|\nabla f_{i,\xi}(x^*) - \mathbb{E}_\xi \nabla f_{i,\xi}(x^*)\|^2}_{\sigma_w^2\ \text{(within an example)}}. $$

Here $n$ is the number of examples and $F$ is the augmentation-averaged objective. We conjecture that, at constant step size $\gamma$, the error floor of random reshuffling with fresh augmentations scales as $c_1 \gamma \sigma_w^2 + c_2 \gamma^2 n \sigma_b^2$, for problem-dependent constants $c_1$ and $c_2$. The two terms combine two known facts. With-replacement noise gives an error of order $\gamma$, and shuffling a finite sum improves the mean-squared error from order $\gamma$ to order $\gamma^2$, as summarized in Shuffling the Data, Extrapolating the Step and analyzed through the "shuffling variance" of Random Reshuffling: Simple Analysis with Vast Improvements.

The consequence is that whenever $\sigma_w^2$ is a sizable fraction of $\sigma^2$, the order-$\gamma$ term dominates. In that regime shuffling buys little over i.i.d. sampling, and any smarter ordering buys even less. The proposed fix, which we call stratified augmentation reshuffling, turns the pair (example, augmentation) into the unit that is permuted. Over a block of $m$ epochs, each example receives a balanced set of $m$ augmentations: for example, flipped in one epoch and unflipped in the next, with crop offsets drawn from a Latin-square design over $m$ cells. The order is reshuffled over all $nm$ items in the block. Within a block, $\sigma_w^2$ then becomes part of a finite sum that cancels at block ends.

Relation to Prior Work

The motivating theory is the epoch-cancellation analysis of Mishchenko et al. and Ahn et al.. These papers prove shuffling's faster rates using the identity that the gradients of all components over a pass sum to the full gradient. Both assume fixed components. We ask what happens when the components are redrawn every epoch, and we restore their assumption by construction rather than relaxing it.

Permutation-Based SGD: Is Random Optimal? identifies the "dilution effect": early steps in an epoch are contracted more than late ones. It proposes FLIPFLOP, which reverses the order every other epoch, and reports that this gives no observable speedup on deep networks. We treat that negative result as a constraint and offer one concrete explanation for it. The reversal cancels the dilution only if epoch $2k$ replays exactly the same functions as epoch $2k-1$, and fresh augmentations break this.

GraB orders examples so that the running sums of their gradients stay close to the mean, and does speed up CIFAR-10 and BERT-Tiny training. A Unified Analysis of SGD with Arbitrary Data Permutations measures this closeness as "order error". Both methods balance gradients from the previous epoch, which were computed under different augmentation draws. Our decomposition predicts that they can only balance the $\sigma_b^2$ part, and we reuse their order-error metric as our main diagnostic.

Random Reshuffling is Not Always Better shows that at large steps in noiseless problems, with-replacement sampling can beat reshuffling. This does not contradict our claim, but it marks a regime where neither term of our floor tells the whole story, so we report results by step size.

The minimax and variational-inequality extensions of shuffling, such as Stochastic Extragradient with Random Reshuffling, and the hardware-oriented 2-wise independent shuffles of Afshani et al. are orthogonal to this work. One practical point does carry over: the stratified scheme needs only seeded augmentation indices, not stored augmented data, so it is compatible with their I/O-efficient permutations.

Research Program

The work has three parts.

Theory on quadratics. We will prove the two-term floor for least squares with random input perturbation, which is the simplest model where $\sigma_w^2$ is explicit. We will then show that stratifying over $m$ augmentations converts the $\gamma\sigma_w^2$ term into an order-$\gamma^2$ term whose constant depends on $m$. We will also show that FLIPFLOP's improved rate is recovered when the augmentation draws are frozen across each forward–reverse pair of epochs. The proof can reuse the finite-sum machinery of the papers above, because frozen blocks are exactly finite sums over $nm$ items.

Measurement on real training. At checkpoints of small networks, we will draw several augmentations per example and compute per-example gradients, which gives an estimate of $\sigma_w^2/\sigma^2$ over the course of training. We will also compute order error under fresh versus frozen augmentations.

Algorithm. We will implement stratified augmentation reshuffling as a drop-in data sampler on top of the GraB-sampler codebase from GraB-sampler, and combine it with FLIPFLOP and GraB to test whether those methods regain their gains.

Baselines

The naive reference is plain random reshuffling with fresh augmentations each epoch, the PyTorch default. Beside it we run i.i.d. with-replacement sampling with the same augmentations. Our decomposition predicts that the gap between these two shrinks as $\sigma_w^2/\sigma^2$ grows, so this pair directly tests the claim.

The strongest existing ordering method is GraB, in the batch-balance and pair-balance variants of GraB-sampler. That paper reports a cost of "8.7% training time overhead and 0.85% peak GPU memory usage overhead" over random reshuffling with LeNet on CIFAR-10. We found no reported accuracy or loss figure on Lacuna for GraB on CIFAR-10 or CIFAR-100, so we will rerun it ourselves. We also run FLIPFLOP from Safran and Shamir, because it is the method our theory predicts should be revived.

For fairness, every method uses the same architecture, augmentation family, step-size grid (eight values with equal tuning budget per method) and epoch count. Every method is run with three schedules: constant step, step decay and cosine. Results are averaged over five seeds. GraB's per-example gradient cost requires models without BatchNorm, a limitation noted in Lu et al.. Our main CIFAR comparisons therefore use GroupNorm ResNet-18 for all methods, with a BatchNorm run reported separately for the methods that do not need per-example gradients.

The method counts as beating these baselines under two conditions. The first is a lower constant-step training-loss floor than random reshuffling and GraB. The second is equal test accuracy, or a confidence interval that excludes a drop, at matched wall-clock time.

Two ablations isolate the key ingredient. In the first, augmentations are stratified but examples are sampled i.i.d. If this ablation helps as much as the full method, the gain comes from lower augmentation variance and not from restored cancellation. In the second, the augmentation pool is frozen but not stratified. This separates the effect of finiteness from the effect of balance.

Why not just…?

Why not just turn off augmentation when studying ordering? Doing so makes the finite-sum theory apply exactly, and it is what our synthetic and LIBSVM experiments effectively do. It also gives up the generalization that augmentation provides, so it answers a question practitioners do not face. Our claim concerns the regime people actually train in. We will report unaugmented runs only as the upper bound on what ordering can achieve.

Why not just use larger batches to shrink augmentation noise? Larger batches shrink $\sigma_b^2$ and $\sigma_w^2$ by the same factor, so their ratio, and therefore which error term dominates, is unchanged. Larger batches also cost generalization at fixed epochs. We will test this directly by sweeping batch size and checking whether the reshuffling-versus-i.i.d. gap tracks $\sigma_w^2/\sigma^2$ rather than batch size.

Why not just use GraB, since it already works on neural networks? GraB is the real threat. If GraB's balancing already absorbs augmentation noise, our scheme adds nothing. Our prediction is that GraB balances stale gradients from other augmentation draws and so reduces only the between-example part. That predicts a specific outcome: GraB's gain over random reshuffling should grow when it is paired with stratified augmentations. If it does not grow, and stratification alone does not beat GraB, we will report that the decomposition fails to explain GraB's success.

Why not just reduce augmentation variance directly, for example with fewer or weaker augmentations? The i.i.d.-plus-stratification ablation is the test for this. If variance reduction alone accounts for the gain, the claim about restored cancellation is wrong, even if the sampler is still useful.

Proposed Experiments

The first testbed is synthetic: the 800-point quadratic on the 100-dimensional sphere from Safran and Shamir, extended with Gaussian input perturbation of tunable size. This lets $\sigma_w^2/\sigma^2$ be swept from 0 to 1. The prediction is that the random-reshuffling advantage over i.i.d. sampling, and FLIPFLOP's further advantage, both decay as this ratio grows, and both return under stratified or frozen blocks.

The second testbed is logistic regression on w8a and ijcnn1 with feature dropout as the augmentation. This checks the same trends on convex real data.

The decisive deep-learning experiment is ResNet-18 on CIFAR-10 and CIFAR-100 with crop and flip augmentation, the setting used in Medyakov et al. and Li et al.. We measure the estimated $\sigma_w^2/\sigma^2$ over training, the order error, the training-loss floor at constant step, and test accuracy. The core claim survives if two things happen together. First, FLIPFLOP shows a measurable training-loss speedup when its forward–reverse pairs share frozen augmentations, where it shows none with fresh ones. Second, the size of the gain across settings tracks the measured within-example fraction.

The claim is refuted if FLIPFLOP stays flat under frozen pairs, or if the gains do not track that fraction. In that case, other differences between networks and quadratics, such as nonlinearity, momentum or schedules, must explain the earlier negative result, and we will say so.

A final check on BERT-Tiny with WikiText-2, using token dropout as the within-example noise, tests whether the effect extends beyond image augmentation.