Information Theoretic Limits of Data Shuffling for Distributed Learning
Information Theoretic Limits of Data Shuffling for Distributed Learning
复制标题
分布式学习数据洗牌的信息论限制
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
R. Tandon
中科院分区：
文献类型：
--
作者：
M. Attia;R. Tandon
数据洗牌是分布式学习算法的基本构建块之一，它增加了学习过程每个步骤的统计增益。在每次迭代中，不同的混洗数据点由中心节点分配给一组分布式工作人员来执行本地计算，这会导致通信瓶颈。本文的重点是形式化和理解数据洗牌问题的存储（每个工作人员）和最坏情况通信开销之间的基本信息论权衡。对于任何存储容量值，我们完全描述了 K = 2 和 K = 3 工作人员的信息论权衡，并表明增加工作人员之间的存储可以通过利用编码来减少通信开销。我们为每个数据洗牌迭代提出了一种新颖且系统的数据传输和存储更新策略，该策略保留了工作人员之间存储的结构属性，并有助于最大限度地减少后续数据洗牌迭代中的通信开销。
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.