FedCGD: Collective Gradient Divergence Optimized Scheduling for Wireless Federated Learning

Tan Chen, Jintao Yan, Yuxuan Sun, Sheng Zhou, Zhisheng Niu

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.

System model of wireless Federated Learning with imbalanced local data and bandwidth constraints.

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.

Geometric representation of gradient divergence, showing how group selection (Point A) can minimize distance to the global gradient.

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:

  1. 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.
  2. 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

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, i.e., data heterogeneity of devices and limited bandwidth. Many papers have investigated device scheduling strategies considering the two issues. However, most of them recognize data heterogeneity as a property of individual devices. 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). The device-level CGD refers to the gradient divergence of the scheduled device group, instead of the sum of the individual device divergence. The sample-level CGD is statistically upper bounded by sampling variance, which is inversely proportional to the total number of samples scheduled for local update. To derive a tractable form of the device-level CGD, we further consider a classification problem and transform it into the weighted earth moving distance (WEMD) between the group distribution and the global distribution. Then we propose FedCGD algorithm to minimize the sum of multi-level CGDs by balancing WEMD and sampling variance, within polynomial time. 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, and flexibly switches between reducing WEMD and reducing sampling variance.
BibTeX
@misc{chen2025fedcgd,
  author = {Tan Chen and Jintao Yan and Yuxuan Sun and Sheng Zhou and Zhisheng Niu},
  title = {{FedCGD: Collective Gradient Divergence Optimized Scheduling for Wireless Federated Learning}},
  year = {2025},
  eprint = {2506.07581},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.07581},
}
Figure