# On the Trajectories of SGD Without Replacement

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Dec 2023.

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

- [How Neural Networks Learn the Support is an Implicit Regularization Effect of SGD](https://mlsanity.com/paper/2406.11110/) (2024)
- [Optimizer Memory Makes Shuffle Order a First-Order Source of Fine-Tuning Noise](https://mlsanity.com/paper/2606.29554/) (2026)
- [The Effect of Mini-Batch Noise on the Implicit Bias of Adam](https://mlsanity.com/paper/2602.01642/) (2026)
- [Randomised Splitting Methods and Stochastic Gradient Descent](https://mlsanity.com/paper/2504.04274/) (2025)
- [The Order Is The Message](https://mlsanity.com/paper/2603.25047/) (2026)
- [Experience Replay with Random Reshuffling](https://mlsanity.com/paper/2503.02269/) (2025)
- [Does SGD Seek Flatness or Sharpness? An Exactly Solvable Model](https://mlsanity.com/paper/2602.05065/) (2026)
- [Error dynamics of mini-batch gradient descent with random reshuffling for least squares regression](https://mlsanity.com/paper/2406.03696/) (2024)
- [Same Error, Different Function: The Optimizer as an Implicit Prior in Financial Time Series](https://mlsanity.com/paper/2603.02620/) (2026)
- [Do Deep Networks Forget Initialization? A Forgetting-Time View of Practical Inductive Bias](https://mlsanity.com/paper/2605.29152/) (2026)
- [Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework](https://mlsanity.com/paper/2608.03001/) (2026)

## Abstract (arXiv)

This article examines the implicit regularization effect of Stochastic Gradient Descent (SGD). We consider the case of SGD without replacement, the variant typically used to optimize large-scale neural networks. We analyze this algorithm in a more realistic regime than typically considered in theoretical works on SGD, as, e.g., we allow the product of the learning rate and Hessian to be O(1) and we do not specify any model architecture, learning task, or loss (objective) function. Our core theoretical result is that optimizing with SGD without replacement is locally equivalent to making an additional step on a novel regularizer. This implies that the expected trajectories of SGD without replacement can be decoupled in (i) following SGD with replacement (in which batches are sampled i.i.d.) along the directions of high curvature, and (ii) regularizing the trace of the noise covariance along the flat ones. As a consequence, SGD without replacement travels flat areas and may escape saddles significantly faster than SGD with replacement. On several vision tasks, the novel regularizer penalizes a weighted trace of the Fisher Matrix, thus encouraging sparsity in the spectrum of the Hessian of the loss in line with empirical observations from prior work. We also propose an explanation for why SGD does not train at the edge of stability (as opposed to GD).