Towards Efficient Scheduling of Federated Mobile Devices Under Computational and Statistical Heterogeneity
Towards Efficient Scheduling of Federated Mobile Devices Under Computational and Statistical Heterogeneity
复制标题
DOI：
10.1109/tpds.2020.3023905
复制
发表时间：
2020-05
影响因子：
5.3
通讯作者：
Cong Wang;Yuanyuan Yang;Pengzhan Zhou
中科院分区：
文献类型：
--
作者：
Cong Wang;Yuanyuan Yang;Pengzhan Zhou
起源于分布式学习，联合学习可以通过共享模型参数来以新的抽象级别保存隐私，而当前的研究主要是在优化学习算法并最大程度地限制通过分布式学习留下的沟通范围在本文中，它是对移动设备的真实实现与当前发电的移动设备的通信相比，瓶颈和现有方法是由移动斗争者进一步的解决计算和统计异质性，我们将数据用作调音旋钮，并提出两种有效的多项式时间算法来安排各种手机上的不同工作负载当数据相同或非分布的数据时，我们将分区和线性瓶颈分配结合在一起，以实现近乎最佳的训练时间，而无需准确的损失。问题和提议贪婪的算法可以在计算时间和准确性之间找到合理的平衡。作为调度算法的输入的设备，我们在带有两个数据集的移动测试床上进行了广泛的实验，与共同的基准相比CIFAR10的准确性增长7％，并使收敛速率提高100％。
Originated from distributed learning, federated learning enables privacy-preserved collaboration on a new abstracted level by sharing the model parameters only. While the current research mainly focuses on optimizing learning algorithms and minimizing communication overhead left by distributed learning, there is still a considerable gap when it comes to the real implementation on mobile devices. In this article, we start with an empirical experiment to demonstrate computation heterogeneity is a more pronounced bottleneck than communication on the current generation of battery-powered mobile devices, and the existing methods are haunted by mobile stragglers. Further, non-identically distributed data across the mobile users makes the selection of participants critical to the accuracy and convergence. To tackle the computational and statistical heterogeneity, we utilize data as a tuning knob and propose two efficient polynomial-time algorithms to schedule different workloads on various mobile devices, when data is identically or non-identically distributed. For identically distributed data, we combine partitioning and linear bottleneck assignment to achieve near-optimal training time without accuracy loss. For non-identically distributed data, we convert it into an average cost minimization problem and propose a greedy algorithm to find a reasonable balance between computation time and accuracy. We also establish an offline profiler to quantify the runtime behavior of different devices, which serves as the input to the scheduling algorithms. We conduct extensive experiments on a mobile testbed with two datasets and up to 20 devices. Compared with the common benchmarks, the proposed algorithms achieve 2-100× speedup epoch-wise, 2–7 percent accuracy gain and boost the convergence rate by more than 100 percent on CIFAR10.