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