Abstract
Federated learning (FL) is a promising paradigm for multiple devices to cooperatively train a model. When applied in wireless networks, two issues consistently affect the performance of FL: data heterogeneity of devices and limited bandwidth. In this paper, we prove that the convergence speed of FL is affected by the sum of device-level and sample-level collective gradient divergence (CGD). We propose the FedCGD algorithm to minimize the sum of multi-level CGDs by balancing weighted earth moving distance (WEMD) and sampling variance. Simulation shows that the proposed strategy increases classification accuracy on the CIFAR-10 dataset by up to 4.2% while scheduling 41.8% fewer devices.
The Challenge of Wireless Federated Learning
Federated Learning allows multiple devices to train a model without sharing raw data. However, two major hurdles remain: data heterogeneity (non-IID data) and limited bandwidth. Current scheduling strategies usually treat data heterogeneity as an individual property—ranking devices by how "bad" their local data is and picking the top ones.
The authors argue this is a missed opportunity. A group of devices, even if each is highly biased individually, can be "collectively" balanced. The challenge is finding a way to measure this collective divergence and optimize scheduling under strict wireless constraints like latency and bandwidth.
The Core Concept: Collective Gradient Divergence (CGD)
The fundamental insight of this work is that the convergence of FL is not just about individual device quality, but the Collective Gradient Divergence (CGD) of the scheduled group.
As shown in the figure above, individual device gradients ($\nabla f_1, \nabla f_2, \nabla f_3$) may diverge significantly from the global gradient ($\nabla F(w)$). However, by carefully selecting a subset of devices, the average gradient of that group (e.g., Point A representing the average of devices 2 and 3) can be much closer to the global target than any single device.
FedCGD focuses on two levels of divergence:
- Device-Level CGD: How much the combined data distribution of the scheduled group deviates from the global distribution. For classification tasks, this is modeled as a Weighted Earth Moving Distance (WEMD) problem.
- Sample-Level CGD: The statistical error introduced by mini-batch sampling (sampling variance), which decreases as more total samples are included in the update.
The FedCGD Approach
To solve the resulting NP-hard optimization problem, the authors introduce two algorithms:
- Greedy Scheduling (GS): A fast heuristic that iteratively adds devices that most reduce the total divergence.
- Fix-Sum Coordinate Descent (FSCD): A more precise algorithm that searches for the optimal group for a fixed number of devices, achieving a tiny 0.19% average error compared to the theoretical optimum.
The system automatically adjusts its focus based on the environment. When data is highly heterogeneous, it prioritizes reducing WEMD; when data is more uniform, it focuses on reducing sampling variance by scheduling more devices.
Key Results
The researchers evaluated their approach using standard image classification benchmarks (CIFAR-10 and CIFAR-100) distributed across 64 simulated wireless devices.
- Higher Accuracy, Lower Cost: On the CIFAR-10 dataset, FedCGD increased classification accuracy by up to 4.2% while scheduling 41.8% fewer devices than standard baselines.
- Efficiency: The FSCD algorithm proved to be highly effective, finding near-optimal scheduling sets within polynomial time, making it practical for real-world wireless systems.
- Complementarity: The algorithm prioritizes "complementary" devices. A device with "bad" data (e.g., only images of cats) is highly valuable if the current group is missing cat data.
Conclusion
FedCGD introduces a "collective" approach to device scheduling. Instead of selecting individual devices with the "best" data, it selects a group whose combined data distribution matches the global target. This significantly improves convergence speed and accuracy while using fewer network resources, offering a robust solution for heterogeneous wireless environments.
Summary updated