2026
The benefits of full data shuffle, now with optimal I/O cost: $k$-wise independence and matrix transposition to the rescue
Peyman Afshani, Rezaul Chowdhury, Mayank Goswami, Jens Kristian R Schou, Francesco Silvestri, Mariafiore Tognon
ICML 2026poster
It is known that RandomShuffle, the without replacement version of Stochastic Gradient Descend (SGD), converges faster than with-replacement SGD. However, RandomShuffle requires to uniformly perform a random permutation of the input sequence, which is known to have an high I/O complexity due to data…