FedReLa: Imbalanced Federated Learning via Re-Labeling

In federated learning (FL), data heterogeneity (non-IID data) and global class imbalance often coexist, leading to biased global decision boundaries. Traditional data-level methods, such as SMOTE, typically require knowledge of global class distributions or access to balanced auxiliary data, which are often unavailable or prohibited by privacy constraints in FL. This paper asks: can we improve model performance on minority classes by re-labeling local data without requiring global class priors or additional communication overhead?

The authors propose FedReLa, a model-agnostic, data-level approach that operates entirely in the label space. Instead of synthesizing new features, FedReLa uses the global model as a label re-allocator. At specific communication rounds, clients use the current global model to generate posterior probability estimates for their local data. The method identifies majority-class samples that exhibit features similar to minority classes (i.e., samples that 'intrude' into the minority class decision boundary) and re-labels them. This process implicitly shifts the decision boundary to be more favorable to minority classes. Because it only modifies labels locally and does not require new trainable parameters or extra communication, it is highly efficient and compatible with existing algorithmic FL methods.

FedReLa consistently outperforms state-of-the-art methods across various datasets, including Fashion-MNIST, CIFAR-10, CIFAR-100, and ImageNet. In extreme scenarios characterized by stepwise or long-tailed class imbalances, the method significantly boosts accuracy for minority classes—by up to 38.30% in stepwise cases and 30.17% in long-tailed cases—while maintaining or improving overall model accuracy. The authors demonstrate that this approach is robust to varying degrees of data heterogeneity and requires no additional communication or training cost, making it a practical plug-in for real-world FL applications.