Exploring Representativity in Device Scheduling for Wireless Federated Learning
Exploring Representativity in Device Scheduling for Wireless Federated Learning
复制标题
DOI：
10.1109/twc.2023.3281765
复制
发表时间：
2024-01
影响因子：
10.4
通讯作者：
Zhixiong Chen;Wenqiang Yi;A. Nallanathan
中科院分区：
文献类型：
--
作者：
Zhixiong Chen;Wenqiang Yi;A. Nallanathan
无线联邦学习（FL）中现有的设备调度工作主要集中于选择具有最大梯度范数或损失函数的设备，并要求所有设备在每轮中进行本地训练。这可能会产生额外的训练成本并安排具有相似数据统计的设备，从而降低学习性能。为了缓解这些问题，我们首先从理论上描述所考虑的 FL 系统的收敛行为，发现学习性能因调度设备的聚合梯度与完全参与梯度之间的差异而降低。受此启发，我们建议找到代表性设备的子集和相应的预设备步长来近似完全参与聚合梯度。考虑到有限的无线带宽，我们提出了一个问题，通过优化设备调度和带宽分配策略来捕获代表性和延迟之间的权衡。我们的分析表明，当所有调度设备具有相同的延迟时，即可实现最佳带宽分配。然后，通过证明问题的非单调子模性，我们开发了一种双贪心算法来求解设备调度策略。为了避免未调度设备的本地训练，我们利用设备的历史梯度信息来估计当前梯度以进行设备调度设计。与现有的调度算法相比，所提出的代表性感知设备调度算法在异构本地数据分布下的两个典型数据集（MNIST 和 CIFAR-10）上分别提高了 6.7% 和 4.02% 的精度。此外，与单独基于延迟和代表性的调度算法相比，所提出的延迟和代表性感知调度算法为 MNIST 和 CIFAR-10 数据集节省了超过 16% 和 12% 的训练时间。
Existing device scheduling works in wireless federated learning (FL) mainly focused on selecting the devices with maximum gradient norm or loss function and require all devices to perform local training in each round. This may produce extra training costs and schedule devices with similar data statistics, thus degrading learning performance. To mitigate these problems, we first theoretically characterize the convergence behaviour of the considered FL system, finding that the learning performance is degraded by the difference between the aggregated gradient of scheduled devices and the full participation gradient. Inspired by this, we propose to find a subset of representative devices and the corresponding pre-device stepsizes to approximate the full participation aggregated gradient. Considering the limited wireless bandwidth, we formulate a problem to capture the trade-off between representativity and latency by optimizing device scheduling and bandwidth allocation policies. Our analysis reveals optimal bandwidth allocation is achieved when all scheduled devices have the same latency. Then, by proving the non-monotone submodularity of the problem, we develop a double greedy algorithm to solve the device scheduling policy. To avoid the local training of unscheduled devices, we utilize the historical gradient information of devices to estimate the current gradient for device scheduling design. Compared to existing scheduling algorithms, the proposed representativity-aware device scheduling algorithm improves 6.7% and 4.02% accuracies on two typical datasets under heterogeneous local data distributions, i.e., MNIST and CIFAR-10, respectively. In addition, the proposed latency- and representativity-aware scheduling algorithm saves over 16% and 12% training time for MNIST and CIFAR-10 datasets than the scheduling algorithms based on either latency and representativity individually.