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 Refsgaard Schou, Francesco Silvestri, Mariafiore Tognon
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:754-768, 2026.

Abstract

It is known that RandomShuffle, the without replacement version of Stochastic Gradient Descent (SGD), converges faster than with replacement SGD. However, RandomShuffle requires uniformly performing a random permutation of the input sequence, which is known to have high I/O complexity due to data movement across the memory hierarchy. In this paper, we propose a shuffling algorithm with a linear I/O complexity that generates almost-uniformly random permutations with rigorous mathematical guarantees. Specifically, we show that the shuffling algorithm can generate $2$-wise independent permutations. Furthermore, we can extend to $k$-wise independence with a small error in the probability distribution, if the fast memory has at least $k$ memory blocks. These results allow us to reach the same expected theoretical convergence as RandomShuffle while achieving optimal linear I/O cost.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-afshani26a, title = {The benefits of full data shuffle, now with optimal {I}/{O} cost: $k$-wise independence and matrix transposition to the rescue}, author = {Afshani, Peyman and Chowdhury, Rezaul and Goswami, Mayank and Schou, Jens Kristian Refsgaard and Silvestri, Francesco and Tognon, Mariafiore}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {754--768}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/afshani26a/afshani26a.pdf}, url = {https://proceedings.mlr.press/v306/afshani26a.html}, abstract = {It is known that RandomShuffle, the without replacement version of Stochastic Gradient Descent (SGD), converges faster than with replacement SGD. However, RandomShuffle requires uniformly performing a random permutation of the input sequence, which is known to have high I/O complexity due to data movement across the memory hierarchy. In this paper, we propose a shuffling algorithm with a linear I/O complexity that generates almost-uniformly random permutations with rigorous mathematical guarantees. Specifically, we show that the shuffling algorithm can generate $2$-wise independent permutations. Furthermore, we can extend to $k$-wise independence with a small error in the probability distribution, if the fast memory has at least $k$ memory blocks. These results allow us to reach the same expected theoretical convergence as RandomShuffle while achieving optimal linear I/O cost.} }
Endnote
%0 Conference Paper %T The benefits of full data shuffle, now with optimal I/O cost: $k$-wise independence and matrix transposition to the rescue %A Peyman Afshani %A Rezaul Chowdhury %A Mayank Goswami %A Jens Kristian Refsgaard Schou %A Francesco Silvestri %A Mariafiore Tognon %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-afshani26a %I PMLR %P 754--768 %U https://proceedings.mlr.press/v306/afshani26a.html %V 306 %X It is known that RandomShuffle, the without replacement version of Stochastic Gradient Descent (SGD), converges faster than with replacement SGD. However, RandomShuffle requires uniformly performing a random permutation of the input sequence, which is known to have high I/O complexity due to data movement across the memory hierarchy. In this paper, we propose a shuffling algorithm with a linear I/O complexity that generates almost-uniformly random permutations with rigorous mathematical guarantees. Specifically, we show that the shuffling algorithm can generate $2$-wise independent permutations. Furthermore, we can extend to $k$-wise independence with a small error in the probability distribution, if the fast memory has at least $k$ memory blocks. These results allow us to reach the same expected theoretical convergence as RandomShuffle while achieving optimal linear I/O cost.
APA
Afshani, P., Chowdhury, R., Goswami, M., Schou, J.K.R., Silvestri, F. & Tognon, M.. (2026). The benefits of full data shuffle, now with optimal I/O cost: $k$-wise independence and matrix transposition to the rescue. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:754-768 Available from https://proceedings.mlr.press/v306/afshani26a.html.

Related Material