Fundamental Limits of Decentralized Data Shuffling
Fundamental Limits of Decentralized Data Shuffling
复制标题
DOI：
10.1109/tit.2020.2966197
复制
发表时间：
2020-06-01
影响因子：
2.5
通讯作者：
Piantanida, Pablo
中科院分区：
文献类型：
--
作者：
Wan, Kai;Tuninetti, Daniela;Piantanida, Pablo
训练数据在不同计算节点（工人）之间的数据洗牌已被确定为提高现代大规模机器学习算法统计性能的核心要素。数据混洗通常被认为是在这样的系统中，由于沉重的通信负载的最重要的瓶颈之一。在主-工架构下（主节点可以访问整个数据集，只允许主节点和工节点之间的通信），最近已经证明编码可以大大减少通信负载。这项工作考虑了一种不同的通信范式，称为分散的数据洗牌，其中工人被允许通过共享链路相互通信。分散式数据洗牌问题有两个阶段：工人在数据洗牌阶段相互通信，然后工人在存储阶段更新其存储的内容。主要的挑战是通过考虑工作者存储的不对称性（即，基于问题设置，工作者被限制在他们的存储器中存储不同的文件），以便表征该问题的基本限制。对于未编码存储的情况（即，每个工作者直接存储数据集的比特的子集），本文提出了匡威的和可实现的边界（基于分布式干扰对准和分布式干扰覆盖策略），其在彼此的3/2的因子内。所提出的计划也是完全最优的约束下的未编码的存储的大存储大小或最多四个工人在系统中。
Data shuffling of training data among different computing nodes (workers) has been identified as a core element to improve the statistical performance of modern large-scale machine learning algorithms. Data shuffling is often considered as one of the most significant bottlenecks in such systems due to the heavy communication load. Under a master-worker architecture (where a master has access to the entire dataset and only communication between the master and the workers is allowed) coding has been recently proved to considerably reduce the communication load. This work considers a different communication paradigm referred to as decentralized data shuffling, where workers are allowed to communicate with one another via a shared link. The decentralized data shuffling problem has two phases: workers communicate with each other during the data shuffling phase, and then workers update their stored content during the storage phase. The main challenge is to derive novel converse bounds and achievable schemes for decentralized data shuffling by considering the asymmetry of the workers' storages (i.e., workers are constrained to store different files in their storages based on the problem setting), in order to characterize the fundamental limits of this problem. For the case of uncoded storage (i.e., each worker directly stores a subset of bits of the dataset), this paper proposes converse and achievable bounds (based on distributed interference alignment and distributed clique-covering strategies) that are within a factor of 3/2 of one another. The proposed schemes are also exactly optimal under the constraint of uncoded storage for either large storage size or at most four workers in the system.