Zijian Liu's new proof shows that random reshuffling beats standard SGD assumptions once training loops over a fixed dataset multiple times, closing a gap between textbook analysis and how optimizers actually run on real finite data.
@konstmish This applies even to random data augmentation https://arxiv.org/abs/2404.00498
Quite enjoyed reading the proofs in this paper.
For anyone who doesn't know, you're no longer using SGD when doing multiple passes over your data. Most papers studying SGD essentially assume infinite amount of data, which isn't always the case in practice. The real algo is RR.
Classic SGD bounds assumed infinite data streams, but every practical multi-epoch run already permutes the dataset each pass. The new rate holds for any reasonable step size and any number of epochs without the old restrictions that forced worse bounds.
The result covers smooth convex finite-sum problems only; non-convex deep-learning cases and concrete speed-ups on models like those tested on CIFAR-10 remain outside the current guarantees.
Users expressed interest in the paper showing random reshuffling outperforms SGD for finite data, noting it was new information to them.
No Digg Deeper questions have been answered for this story yet.
https://arxiv.org/abs/2606.32005
Quite enjoyed reading the proofs in this paper.
For anyone who doesn't know, you're no longer using SGD when doing multiple passes over your data. Most papers studying SGD essentially assume infinite amount of data, which isn't always the case in practice. The real algo is RR.
@konstmish huh I thought this was common knowledge no?
@kellerjordan0 oh that's interesting, I didn't know that!
