On the Fundamental Limits of Coded Data Shuffling for Distributed Machine Learning
| Autor: | Soheil Mohajer, Adel M. Elmahdy |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Machine Learning Theoretical computer science Shuffling Distributed database Computer science Computer Science - Information Theory Information Theory (cs.IT) 020206 networking & telecommunications 02 engineering and technology Library and Information Sciences Upper and lower bounds Machine Learning (cs.LG) Computer Science Applications Set (abstract data type) Permutation Computer Science - Distributed Parallel and Cluster Computing Node (computer science) 0202 electrical engineering electronic engineering information engineering Distributed Parallel and Cluster Computing (cs.DC) State (computer science) Cache Information Systems |
| Zdroj: | IEEE Transactions on Information Theory. 66:3098-3131 |
| ISSN: | 1557-9654 0018-9448 |
| DOI: | 10.1109/tit.2020.2964547 |
| Popis: | We consider the data shuffling problem in a distributed learning system, in which a master node is connected to a set of worker nodes, via a shared link, in order to communicate a set of files to the worker nodes. The master node has access to a database of files. In every shuffling iteration, each worker node processes a new subset of files, and has excess storage to partially cache the remaining files, assuming the cached files are uncoded. The caches of the worker nodes are updated every iteration, and they should be designed to satisfy any possible unknown permutation of the files in subsequent iterations. For this problem, we characterize the exact load-memory trade-off for worst-case shuffling by deriving the minimum communication load for a given storage capacity per worker node. As a byproduct, the exact load-memory trade-off for any shuffling is characterized when the number of files is equal to the number of worker nodes. We propose a novel deterministic coded shuffling scheme, which improves the state of the art, by exploiting the cache memories to create coded functions that can be decoded by several worker nodes. Then, we prove the optimality of our proposed scheme by deriving a matching lower bound and showing that the placement phase of the proposed coded shuffling scheme is optimal over all shuffles. Comment: This work has been published in IEEE Transactions on Information Theory. A preliminary version of this work was presented at IEEE International Symposium on Information Theory (ISIT), Jun. 2018 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|