Information theoretic limits of data shuffling for distributed learning

Mohamed Adel Attia, Ravi Tandon

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Scopus citations

Abstract

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 computation, which leads to communication bottlenecks. The focus of this paper is on formalizing and understanding the fundamental information-theoretic tradeoff between storage (per worker) and the worst-case communication overhead for the data shuffling problem. We completely characterize the information theoretic tradeoff 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. We propose a novel and systematic data delivery and storage update strategy for each data shuffle iteration, which preserves the structural properties of the storage across the workers, and aids in minimizing the communication overhead in subsequent data shuffling iterations.

Original languageEnglish (US)
Title of host publication2016 IEEE Global Communications Conference, GLOBECOM 2016 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781509013289
DOIs
StatePublished - 2016
Event59th IEEE Global Communications Conference, GLOBECOM 2016 - Washington, United States
Duration: Dec 4 2016Dec 8 2016

Publication series

Name2016 IEEE Global Communications Conference, GLOBECOM 2016 - Proceedings

Other

Other59th IEEE Global Communications Conference, GLOBECOM 2016
Country/TerritoryUnited States
CityWashington
Period12/4/1612/8/16

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Hardware and Architecture
  • Safety, Risk, Reliability and Quality

Fingerprint

Dive into the research topics of 'Information theoretic limits of data shuffling for distributed learning'. Together they form a unique fingerprint.

Cite this