Fetching the paper…

Reading the bibliography…

2016

Information Theoretic Limits of Data Shuffling for Distributed Learning

Attia, Mohamed, Tandon, Ravi

Original
PDF
Post on X

Understand

Data shuffling is one of the fundamental building blocks for distributed learning algorithms, that increases the statistical gain for each step of the learning process.

In each iteration, different shuffled data points are assigned by a central node to a distributed set of workers to perform local computations, which leads to communication bottlenecks.
The focus of this paper is on formalizing and understanding the fundamental information-theoretic trade-off between storage (per worker) and the worst-case communication overhead for the data shuffling problem.
We completely characterize the information theoretic trade-off for $K=2$, and $K=3$ workers, for any value of storage capacity, and show that increasing the storage across workers can reduce the communication overhead by leveraging coding.

Information Theoretic Limits of Data Shuffling for Distributed Learning · Around

Built on

J. Dean and S. Ghemawat, “MapReduce: Simplified data processing on large clusters,” in Proceedings of the 6th Symposium on Operating System Design and Implementation (OSDI) , 2004
2004
Earlier work this paper cites.
M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica, “Spark: Cluster computing with working sets,” in Proceedings of the 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud) , 2010
2010
Earlier work this paper cites.
M. Gürbüzbalaban, A. Ozdaglar, and P. Parrilo, “Why random reshuffling beats stochastic gradient descent,” CoRR , vol. abs/1510.08560, 2015. [Online]. Available: https://arxiv.org/abs/1510.08560
Original
2015
Earlier work this paper cites.

Similar

S. Ioffe and C. Szegedy, “Batch normalization accelerating deep network training by reducing internal covariate shift,” CoRR , vol. abs/1502.03167, 2015. [Online]. Available: https://arxiv.org/abs/1502.03167
Original
2015
Cited alongside, same era.
M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” IEEE Transactions on Information Theory , vol. 60, no. 5, pp. 2856–2867, Feb. 2015
2015
Cited alongside, same era.
S. Li, M. A. Maddah-Ali, and S. Avestimehr, “Coded MapReduce,” in Proceedings of the 53rd Annual Allerton conference on Communication, Control, and Computing, Monticello, IL , Sep. 2015
2015
Cited alongside, same era.

Then

K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran, “Speeding up distributed machine learning using codes,” in Proceedings of Neural Information Processing Systems Conference (NIPS) , Dec. 2015
Original
2015
Later among the works it cites.
O. Shamir, “Without-replacement sampling for stochastic gradient methods: Convergence results and application to distributed optimization,” CoRR , vol. abs/1603.00570v2, 2016. [Online]. Available: https://arxiv.org/abs/1603.00570v2
Original
2016
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…