arXiv CSopen access

FedReLa: Imbalanced Federated Learning via Re-Labeling

FedReLa: Imbalanced Federated Learning via Re-Labeling

Guangzheng Hu 1 Patricia Menéndez 1 Feng Liu 2 Mingming Gong 1 Guanghui Wang 3 Liuhua Peng 1

arXiv:2606.26037v1 [stat.ML] 24 Jun 2026

Abstract

such as differences in participation capacity, and geographic or demographic factors, data often exhibit significant heterogeneity over clients, leading to disparate model updates and suboptimal global model (Zhao et al., 2018).

Federated learning has emerged as the foremost approach for decentralized model training with privacy preservation. The global class imbalance and cross-client data heterogeneity naturally coexist, and the mismatch between local and global imbalances exacerbates the performance degradation of the aggregated model. The agnosticism of global class distribution poses significant challenges for data-level methods, especially under extreme conditions with severe class absence across clients. In this paper, we propose FedReLa, a novel data-level approach that tackles the coexistence of data heterogeneity and class imbalance in federated learning. By re-labeling samples with a feature-dependent label re-allocator, FedReLa corrects biased global decision boundaries without requiring knowledge of the global class distribution. This modular, model-agnostic approach can be integrated with algorithmic methods to deliver consistent improvements without additional communication overhead. Through extensive experiments, our method significantly improves the accuracy of minority classes and the overall accuracy on stepwise-imbalanced and long-tailed datasets, outperforming the previous state of the art.

Imbalanced or long-tailed distributed data is common in real-world applications (Azaria et al., 2014; Fotouhi et al., 2019; Shingi, 2020) and even more prevalent in FL. Due to client-level data heterogeneity, two types of imbalance often coexist: local imbalance (within individual clients) and global imbalance (across the entire federation), both of which pose challenges for FL classification. Although both data- and algorithm-level methods are important for addressing class imbalance, research on imbalanced federated learning has largely focused on algorithm-level methods. Data-level approaches remain underdeveloped due to strict privacy constraints. Early algorithm-level work primarily tackles local imbalance via improved aggregation (McMahan et al., 2017; Wang et al., 2020), robust local training (Acar et al., 2021; Karimireddy et al., 2019; Li et al., 2021; 2020), selective client participation (Chen et al., 2020; Fraboni et al., 2021), or architectural enhancements (Duan et al., 2019), while assuming all the classes are equally represented globally, a condition rarely met in practice. Recent algorithmic works focus on more realistic scenarios where global class imbalance (e.g., step-wise or long-tailed distributions) coexists with data heterogeneity. Ratio-loss (Wang et al., 2021) and CLIMB (Shen et al., 2021) pioneered solutions for global step-wise imbalance and non-IID (not independent and identically distributed) client data. Subsequent studies (Chen & Chao, 2021b; Li et al., 2023; Shang et al., 2022; Xiao et al., 2024; 2023) further tackled federated long-tailed (Fed-LT) learning.

1. Introduction Federated learning (FL) facilitates collaborative model training across distributed clients without exchanging raw data, thereby preserving data privacy. Each client trains a model locally on private data and only shares parameter updates to a global server. Due to variations in client environments,

Existing data-level methods (e.g., SMOTE (Chawla et al., 2002)) rely on global class prior information to identify minority classes before synthesizing new samples. However, in FL, local class priors are private, making access to global information or exchange of local class distributions impossible. Even in scenarios such as fraud detection (Shingi, 2020) or rare disease diagnosis (Tan et al., 2023), where global minority classes can be naturally identified, insufficient or even absent local minority samples in clients render synthesis unfeasible, leaving data-level methods underdeveloped.

1 School of Mathematics and Statistics, University of Melbourne, Victoria, Australia 2 School of Computing and Information Systems, University of Melbourne, Victoria, Australia 3 School of Statistics and Data Science, LPMC, KLMDASR, and LEBPS, Nankai University. Correspondence to: Liuhua Peng <[email protected]>.

Proceedings of the 43 rd International Conference on Machine Learning, Seoul, South Korea. PMLR 306, 2026. Copyright 2026 by the author(s).

To fill the gap in data-level FL methods, this paper proposes 1

FedReLa: Imbalanced Federated Learning via Re-Labeling

2. Related works

a novel data-level method that eliminates the reliance on global class prior knowledge, incurs no additional communication overhead, and involves no training overhead caused by extra trainable parameters, so as to improve the FL performance in challenging scenarios where both data heterogeneity and global class imbalance coexist.

Imbalanced Learning. Imbalanced learning has been extensively studied in centralized settings, where data-level methods augment minority classes by generating synthetic samples using generative models (Odena et al., 2017; Mariani et al., 2018), SMOTE-based techniques (Chawla et al., 2002; Han et al., 2005; He et al., 2008), or feature interpolation via mixup (Chou et al., 2020; Ramasubramanian et al., 2024; Zhang et al., 2017). However, their effectiveness is severely limited in FL due to scarcity of minority samples and absence of local classes, as well as the unavailability of global class priors, which prevents reliable identification of global minority classes and adjustment of augmentation strength for prior data-level methods.

Unlike traditional data-level methods, such as SMOTEbased (Chawla et al., 2002; He et al., 2008) or mixup-based approaches (Chou et al., 2020; Ramasubramanian et al., 2024), our method operates purely in the label space, without synthesizing new features. Our novel method re-labels local data through a carefully designed feature-dependent label re-allocator that leverages minority-class information embedded in the global model. Specifically, it identifies local majority class samples that intrude into the global minority-class feature space and implements asymmetric selective relabeling, implicitly enlarging the minority-class decision boundary. As a data-level approach for heterogeneous and class-imbalanced data in Federated Learning via Re-Labeling, FedReLa has three key characteristics:

FL for data heterogeneity. FL performance is primarily influenced by model aggregation, client updates, and local data distributions. Numerous FL methods primarily focus on client update and model aggregation to mitigate the adverse effects of skewed local datasets. During model aggregation, FedAvg (McMahan et al., 2017) and FedNova (Wang et al., 2020) pioneered weighted averaging local models based on local dataset sizes or batch sizes. For client update, regularization terms are incorporated into loss functions to penalize discrepancies between global and local models (Li et al., 2021; 2020) or constrain inter-round model divergence (Acar et al., 2021). SCAFFOLD (Karimireddy et al., 2019) introduced control variates to correct biased local gradients. However, these methods perform suboptimally on global minority/tail classes, as they mainly tackle local imbalance from data heterogeneity but neglect global class imbalance.

(i) Model-Data Agnosticism: Unlike methods that rely on balanced auxiliary data or explicit class priors (Shingi, 2020; Wang et al., 2021), FedReLa is agnostic to model architecture, data format, and class distribution, and inherently improves data quality without domain-specific constraints. (ii) Lightweight Plug-in Adaptation: Unlike prior methods (Shang et al., 2022; Shen et al., 2021; Xiao et al., 2024) that require extra communicational or training cost from optimizing/uploading newly introduced parameters, FedReLa re-purposes the global model as a label re-allocator without introducing new trainable parameters, requiring no extra training or communicational burden (see Appendix B.1).

Data heterogeneity with global class imbalance. Several methods extend FL to settings with global imbalance, primarily via loss reweighting. Ratio-Loss (Wang et al., 2021) estimates global class priors using auxiliary balanced data, while CLIMB (Shen et al., 2021) removes this requirement by introducing learnable loss weights, at the cost of increased training and communication overhead. Recent studies extend the scope from step-wise imbalance to longtailed distributions. CReFF (Shang et al., 2022) boosts tailclass performance via aggregated class feature retraining but incurs extra training and doubled communication costs, while FedROD (Chen & Chao, 2021b) decouples global and local objectives yet may yield suboptimal global models when aggressively balancing local losses. FedETF (Li et al., 2023) enforces balanced feature learning via a fixed ETF (Equiangular Tight Frame) classifier head.

(iii) Universal Composability: Operating solely in the label space, FedReLa integrates seamlessly with algorithm-level approaches and delivers consistent performance gains. We evaluate FedReLa on Fashion-MNIST, CIFAR-10, CIFAR-100, and ImageNet under step-wise and long-tailed class imbalance, across varying degrees of data heterogeneity. FedReLa consistently improves existing algorithm-level methods, achieving state-of-the-art performance. In the most extreme cases, FedReLa boosts minority/tail-class accuracy by up to 38.30% (step-wise) and 30.17% (long-tailed) while maintaining overall accuracy superiority (Tables 1 and 2). These results conclusively demonstrate the superiority and applicability of FedReLa in FL. The code is available at: https://github.com/guangzhengh/ FedReLa.git.

Based on the observation that head classes tend to have larger weight norms, FedGraB (Xiao et al., 2023) rescales the gradients of local models by class weight norms to enhance tail-class performance. As a follow-up, FedLOGE (Xiao et al., 2024) further integrates the idea of Li et al. 2

FedReLa: Imbalanced Federated Learning via Re-Labeling

3.1. Problem Formulation

(2023) by rescaling the weights of the fixed ETF classifier using the weight norms of an auxiliary classifier head. Despite this, our empirical findings in Section 5 reveal that weight norms become unreliable under high heterogeneity.

Consider a dataset D that contains data pairs (X, Y ) ∼ P (x, y), where x ∈ X ⊆ Rd , y ∈ Y = {1, 2, . . . , C} and P represents the joint distribution. Denote the conditional distribution X | Y = j ∼ Pj (x) and the prior probability Pr(Y = j) = πj for class j ∈PY. The marginal distribution of X is then PX (x) = j∈Y πj Pj (x). Assume D is imbalanced with global imbalance ratio IR(D) = maxj∈Y πj / minj∈Y πj ≫ 1. Let ηj (x) = Pr(Y = j | X = x) = πj Pj (x)/PX (x) be the global posterior probability. Recalling that the Bayesian decision theorem (Duda et al., 2006) defines the optimal estimated y ∗ of a sample x as y ∗ = argmaxj∈Y ηj (x), the following result holds.

Other label-related concepts. FedReLa is related to, but distinct from, learning with noisy labels (Goldberger & Ben-Reuven, 2022; Manwani & Sastry, 2013; Frénay & Verleysen, 2013) and label propagation (Iscen et al., 2019; Chapelle et al., 2006). Noisy-label methods typically aim to suppress harmful label corruption so that training is not misled, whereas FedReLa deliberately applies a controlled, minimal relabeling step to reshape biased decision boundaries induced by federated long-tailed and non-IID data. Label propagation, in contrast, transfers information from labeled to unlabeled instances via graph-based similarity, often requiring global graph construction; FedReLa instead relabels local labeled majority examples into minority classes and operates without building a global propagation graph. FedReLa is a federated boundary-correction strategy tailored to class imbalance. We therefore position FedReLa alongside these lines of work while emphasizing its novelty as intentional, locally executed relabeling for federated imbalance rather than noise removal or graph-based label diffusion.

Lemma 1. The optimal Bayesian decision boundary between two classes j ̸= ℓ ∈ Y is Sj,ℓ = {x ∈ X : ηj (x) = ηℓ (x) > ηℓ′ (x) ∀ ℓ′ ∈ Y \ {j, ℓ}}. For x ∈ Sj,ℓ , ηj (x) = ηℓ (x) implies Pj (x)/Pℓ (x) = πℓ /πj . Then for minority class j and majority class ℓ with πj ≪ πℓ , Sj,ℓ intrudes deeply into the minority class region, increasing the risk of misclassifying minority class samples. This motivates balancing the ratio πℓ /πj to shift the decision boundary back towards the majority class region, thereby alleviating the adverse effects of class imbalance. In FL, the dataset D is distributed on K clients with local datasets {D(k) }K k=1 and assumes the class conditional (k) distributions {Pj (x)}K k=1 are identical across all clients

Motivations: Existing methods tackle data imbalance through algorithmic adjustments. Why not improve local data quality directly? The reason is apparent: conventional data augmentation relies on global data distribution knowledge, which violates FL privacy constraints. The most relevant work, FedMix (Wicaksana et al., 2022), addresses heterogeneity using mixup. Still, it requires clients to share local data averages, which may require additional privacypreserving mechanisms and increase communication costs. To our knowledge, no data-level FL approach mitigates the coexistence of data heterogeneity and global imbalance while achieving: (1) not requiring auxiliary datasets, (2) having a negligible additional computation cost with zero communication cost and no extra parameter training burden, and finally (3) being agnostic to global data distribution. This motivates FedReLa, a data-level method that simultaneously achieves all of the above requirements while significantly improving performance under extreme conditions.

(k)

for each class j. In contrast, the class priors {πj }K k=1 may be different among clients due to data heterogeneity. (1) (1) For classes j and ℓ, we have Pj (x)/Pℓ (x) = · · · = (K)

(K)

Pj (x)/Pℓ (x) = Pj (x)/Pℓ (x). However, divergent class priors result in different local posterior probability P (k) (k) (k) ηj (x) = πj Pj (x)/ j0 ∈Y πj0 Pj0 (x) and misaligned Bayesian decision boundaries among clients. This misalignment affects performance of aggregated classifier and slows down convergence of FL algorithms (Zhao et al., 2018). Ideally, with properly chosen aggregation weights {wk }K k=1 , the decision boundary between classes j and ℓ of the global PK [w] (k) aggregated model ηj (x) = k=1 wk ηj (x) given by [w]

[w]

[w]

Sj,ℓ = {x ∈ X : Pj (x)/Pℓ (x) = πℓ /πj }, [w]

which can match Sj,ℓ in Lemma 1 by making πj = πj PK [w] [w] (k) PK and πℓ = πℓ , where πj = k=1 wk πj / k=1 wk PK [w] (k) PK and πℓ = k=1 wk πℓ / k=1 wk . For instance, setting wk = |D(k) |/|D| achieves this alignment. However, the global imbalance ratio πℓ /πj still introduces bias into the aggregated decision boundary of the global model. To address that, several algorithms (Menon et al., 2020; Tan et al., [w] [w] 2020) have been proposed to adjust the ratio πℓ /πj via

3. Federated Learning via Re-Labeling In this section, we first analyze how local and global imbalances affect decision boundaries and why heterogeneity in globally imbalanced data exacerbates the performance impact of imbalanced data on global models. We then introduce the label re-allocator and analyze how re-labeled samples implicitly rebalance the biased global decision boundaries. 3

FedReLa: Imbalanced Federated Learning via Re-Labeling

alternative weighting schemes. Moreover, data heterogeneity can cause mismatches between global and local imbalance ratios, further complicating the class imbalance issue and amplifying bias in the aggregated decision boundary. See Example 1 in the Appendix for an illustration.

label re-allocator where the re-labeling probability is proportional to the degree of intrusion. Specifically, with (k) (k) ρℓ→j (x) ∝ ηj (x), the Bayesian decision boundary is   (k) π (k) P (x∗ ) Se(k) = x∗ ∈ X : Pjℓ (x∗ ) = [1 − 2ρℓ→j (x∗ )] ℓ(k) . πj

Remark 1. We adopt a global model based on posterior aggregation rather than parameter aggregation for two reasons. First, posterior aggregation renders changes in the decision boundary explicit and easier to quantify, which is essential for analyzing the effect of re-labeling in the next section. Second, it aligns with principles of statistical model averaging, offering a flexible and natural framework for heterogeneous FL. Furthermore, the two aggregation paradigms are approximately equivalent under mild regularity conditions, see Appendix A for detailed discussions.

(k) Since 1 − 2ρℓ→j (x∗ ) < 1, Se(k) on re-labeled data shifts back to the majority class region. Based on re-labeled data e = ∪K D e (k) , we also study the decision boundary of the D k=1 PK [w] (k) global aggregated model ηej (x) = k=1 wk ηej (x).

Lemma 3. The optimal Bayesian decision boundary of the [w] global aggregated model ηej (x) is ( Pj (x∗ ) Se[w] = x∗ ∈ X : Pℓ (x∗ ) ) PK (k) (k) k=1 wk πℓ [1 − 2ρℓ→j (x)]/πℓ πℓ = · . PK (k) πj wk π /πj

3.2. Aggregated decision boundary with re-labeled data We introduce a novel data-level approach that reallocates data labels to adjust the decision boundary by balancing class prior ratios at both local and global levels. This strategy also alleviates the mismatch between global and local imbalance ratios, and improves the robustness of the FL model. Our proposed FedReLa is motivated by how relabeling shifts decision boundaries locally and globally. We first analyze its effect on a local client k, and then extend the discussion to model aggregation. Without loss of generality, we consider a binary classification setting where classes j and ℓ represent the minority and majority classes.

k=1

Lemma 3 implies that the label re-allocator balances the global imbalance ratio when (k) (k) k=1 wk πℓ [1 − 2ρℓ→j (x)]/πℓ < 1. PK (k) k=1 wk πj /πj

PK

(k)

holds naturally when ρℓ→j (x) > 0 for all k ∈ {1, . . . , K}. Thus, the label re-allocator can balance both the local and global decision boundary. Data heterogeneity gives rise to a mismatch between local and global class imbalances in federated learning, where the global minority class becomes the local majority class for some clients. To mitigate the issues caused by such mismatches, we determine the relabeling direction based on local class priors, which avoids unexpected relabeling and enables correction of both global and local decision boundaries. A detailed discussion and formal derivation of this mechanism are presented in Remark 2 of the Appendix.

(k)

X (k) = x, Y (k) = ℓ) and re-labeling j to ℓ as ρj→ℓ (x) = Pr(Ye (k) = ℓ | X (k) = x, Y (k) = j) for client k, then (k) ηej (x) = Pr(Ye (k) = j | X (k) = x) (k)

(k)

(k)

= ηj (x)[1 − ρj→ℓ (x)] + [1 − ηj (x)]ρℓ→j (x). (k)

(k)

Lemma 2. Assume ρℓ→j (x∗ ) ≤ 0.5 and ρj→ℓ (x∗ ) ≤ 0.5 for any x∗ ∈ Se(k) , then the optimal Bayesian decision e (k) boundary  based on D for client k is  Se(k) =

P (x∗ )

x∗ ∈ X : Pjℓ (x∗ ) =

(k)

(k)

When πℓ /πj

≫

(k)

1−2ρℓ→j (x∗ ) (k)

1−2ρj→ℓ (x∗ )

4. Framework of FedReLa

(k)

·

πℓ

(k)

πj

(1)

PK (k) By choosing wk = |D(k) |/|D|, k=1 wk πj /πj = 1, and PK (k) (k) (1) reduces to k=1 wk πℓ [1 − 2ρℓ→j (x)]/πℓ < 1, which

Let (X (k) , Y (k) ) ∼ P (k) (x, y) denote the data pair for e (k) the corclient k with re-labeled Ye (k) and consider D responding re-labeled dataset. Denote the probabilities (k) of re-labeling ℓ to j as ρℓ→j (x) = Pr(Ye (k) = j |

(k)

j

.

Motivated by decision boundary adjustment through data re-labeling, as analyzed in Section 3.2, we propose FedReLa to mitigate performance degradation caused by data heterogeneity and class imbalance in FL. FedReLa is a modelagnostic approach, which is designed as a plug-in module that can be seamlessly integrated into any FL algorithm.

1, we seek to achieve [1 −

(k) (k) 2ρℓ→j (x∗ )]/[1 − 2ρj→ℓ (x∗ )]

< 1 to locally adjust the decision boundary. Given the scarcity of minority class samples in D(k) , it is reasonable to restrict re-labeling to occur only from majority class ℓ to minority class j, and (k) set ρj→ℓ (x) = 0. Furthermore, since deeply invaded majority class samples are especially harmful, we design a

As shown in Figure 1, FedReLa works as a local data one-shot preprocessor between communication rounds of any FL algorithm, with each client applying it locally and 4

FedReLa: Imbalanced Federated Learning via Re-Labeling Local data

Posterior Probability Matrix

Global Model

. . .

𝑐=1

Client 1 𝑐=1 2

...

Feature extractor

𝐶

0.1

0

0

0

0

0.2

0.1

0

0.6

0

0

0.2

0.1

0

0.2

0

. . .

Classifier head

0.5

0.2

0.1

0

Normalization

Z-score Standardlization

Client 2

𝑐=𝐶

0.7

. . .

𝑐=1

𝑐=𝐶

𝑐=1

9

3.1

-0.1

-0.1 -0.1

-0.1

4.2

0

0.4

0

0

0

0

0.7

Client 𝑲

0.4

-0.1

7

-0.1 -0.1

5.2

2.3

0

0

0.4

0

0

0.9

0.2

0

0.6

0

. . .

. . .

. . .

5.7

4.5

2.2

-0.1

𝑐=𝐶

. . .

-0.1

5.2

-0.1

0

0.6

0

Communication Round

0

𝑤𝑔𝑇=𝑖

Figure 1. FedReLa Framework. At round t = Trelabel , FedReLa re-labels the local dataset with the label re-allocator based on the global model before the local training starts.

in parallel. Specifically, before client k starts to train the global model f (θ; x) with parameter θ = θtglobal received at round t = Trelabel , FedReLa re-labels its local (k) (k) k dataset D(k) = {(xi , yi )}ni=1 using a client-specific (k) label re-allocator ρ , resulting in the re-labeled dataset e (k) = {(x(k) , ye(k) )}nk = ρ(k) (D(k) ). Note that the D i i i=1 computation of FedReLa only occurs in Trelabel , and the e (k) can be reused in subsequent re-labeled local dataset D training rounds t > Trelabel . Thus, the one-shot computations at round Trelabel for label re-allocators are lightweight and almost negligible to the whole training process. We discuss the computational cost of FedReLa in Appendix B.1. Each client then updates the global model locally using e (k) , and the server aggregates the local updates ∆θt(k) to D global produce the updated global model with parameter θt+1 .

Crucially, the global model implicitly integrates crossclient discriminative knowledge across all classes Y = {1, 2, . . . , C}, making it assign non-zero posterior probabilities even to classes absent from a client’s local data. Due to global imbalance and data heterogeneity, these posterior estimates for minority (tail) classes tend to be systematically biased downward. To address posterior underestimation and obtain a well-calibrated label re-allocator, we introduce two key normalization steps: (1) z-score Standardization, and (2) tanh Normalization. Class-wise z-score Standardization: Samples near decision boundaries often share features with other classes, thus exhibiting relatively high posterior probabilities for ambiguous ones. As a result of biased global decision boundaries towards minority classes, most dominant-class samples exhibit vanishingly small posterior probabilities for minority classes. Despite this, we empirically observe that a non-trivial subset of majority-class samples retains nonnegligible probabilities for minority classes—insufficient to trigger misclassification but indicative of proximity to minority-class regions in the feature space. To better calibrate these underestimated posteriors, particularly for minority classes, we apply class-wise z-score standardization, which rescales the posterior distributions within each class. This highlights candidate samples with shared features for re-labeling. Specifically, for the i-th instance in client k, let

The inspiration of FedReLa is to “reallocate” the shared feature space that is encroached upon by the majority class (due to biased decision boundaries) to the minority class. This is achieved by selectively re-labeling the majority-class samples that intrude into the minority-class feature space with similar features as minority-class samples. Building upon the analysis in Section 3, we let the re-labeling probabilities be proportional to the posterior probabilities of minority classes, and we utilize the global model distributed to each client to perform local inference. This yields a |D(k) | × |Y| posterior probability matrix Q(k) for client k, where (k)

Qi

(k)

Ii

(k)

= f (θtglobal ; xi ) ∈ R|Y|

is the i-th row of Q(k) , denoting the posterior probability (k) vector of the i-th local instance xi .

(k)

(k)

= {i0 ∈ {1, . . . , nk } : yi0 = yi }

(2)

denote the index set of samples in D(k) that share the same label as the i-th instance. The class-wise mean and standard 5

FedReLa: Imbalanced Federated Learning via Re-Labeling

deviation vectors are computed as X 1 (k) (k) Qi0 , µi = (k) |Ii | (k) i0 ∈Ii v 2 u X  (k) 1 (k) (k) σi = u Qi0 − µi , t (k) |Ii | − 1 (k)

With this threshold, the re-labeling probability for the i-th instance on client k is defined as       (k) (k) (k) ρ(k) xi = max tanh zi − t(k) ⊙ ϖ , 0 , (8) re yi

(3)

(k)

i0 ∈Ii

(k)

(k)

where µi ∈ R|Y| and σi ∈ R|Y| are the class-wise mean and standard deviation vectors of the posterior probabilities over this set. The z-score vector for the i-th instance is then given by (k) (k) Q −µ (k) zi = i (k) i . (5) σi

Based on the local label re-allocator ρ(k) , each client applies probabilistic re-labeling to its data to generate the re-labeled data before local training; this is the only difference FedReLa makes from the standard FL, which adjusts the decision boundaries and thus achieves significant improvement on the performance of minority/tail classes. The full procedure is summarized in Algorithm 1.

As illustrated in Figure 1, the resulting z-score matrix Z(k) , (k) with i-th row zi , recalibrates Q(k) , amplifying underestimated posterior probabilities of minority (tail) classes and highlighting samples near class boundaries. Normalization via tanh: To ensure that the re-labeling rates in the label re-allocator lie within [0, 1], we rescale the z-scores to the range [−1, 1] using a tanh transformation. This normalization incorporates two critical components: (k) (1) a client-specific threshold tre , which is a tunable hyperparameter that determines the desired re-labeling strength by filtering out samples with weak feature similarity; and (k) (2) a class-wise reweighting vector ϖj ∈ R|Y| , computed from local class priors to re-label samples asymmetrically. (k) Specifically, ϖj reweighs the re-labeling probability from class j to any other class c ∈ Y \ {j} with their class prior difference between j and c. (k) Let nY

Algorithm 1 Re-Allocator re-labels local data (k)

(k)

k Input: local datasets D(k) = {(xi , yi )}ni=1 , classifier global f (·; ·), global model θt (k) Parameters: Threshold tre , re-labeling round Trelabel

for client k ∈ K at communication round t = Trelabel do: (k) Compute ϖ(k) by (6) with nY (k) (k) e (k) do: for (x , y ) ∈ D i (k)

i

(k)

Qi ← f (θtglobal ; xi ) (k) (k) for (xi , yi ) ∈ D(k) do: (k) (k) Compute zi by (5) with Qi (k) (k) ϖ (k) ← max(ϖ(k) − ϖ(k) [yi ], 0)

|Y|

∈ R denote the vector of class-wise sample counts in the local dataset D(k) . We first apply min-max (k) normalization on nY to construct the class-wise reweight(k)

yi

ing vector ϖ(k) = 1 − minmax(nY ), defined as: (k) ϖj = max(ϖ(k) − ϖ(k) [j], 0)

(k)

where zi ∈ RC is the local z-score vector of sample xi , (k) ⊙ denotes element-wise multiplication, and ϖ yi is the class-prior weight associated with the observed label yi . In(k) tuitively, tre acts as a tunable, class-wise filter: samples whose z-scores are insufficiently large relative to the classspecific threshold receive negative values after the tanh(·) mapping and are truncated to zero, suppressing re-labeling for instances with weak minority-class similarity. We pro(k) vide a sensitivity analysis of tre in Appendix B.3.

(4)

(k)

Compute ρ(k) (xi ) by (8) (k) U ∈ R|Y| ← Bernoulli(ρ(k) (xi )) if U contains 1 then: (k) (k) yei ← Y[argmax(ρ(k) (xi ))] e (k) ← {(x(k) , ye(k) )}nk return D i i i=1

(6)

For samples belonging to a local tail class ytail , we have (k) ϖ(k) [ytail ] = 1, which implies that ϖytail = 0. It zeros the re-labeling probabilities from the minority class to other classes, thereby preserving the integrity of minority-class samples.

Robust to biased posteriors. To demonstrate how FedReLa calibrates underestimated posterior probabilities and identifies majority-class samples with feature similarities to minority classes, we first clarify the rationale of z-score standardization. The z-score quantifies the degree to which a posterior probability deviates from the distribution of its own class, rather than relying on the absolute value of the posterior. Even when the global model yields biased and severely underestimated posterior probabilities for minority classes, the relative ranking of these deviations across

Let Z ∈ RN ×C denote the matrix of local z-scores on (k) client k, where Z:,j is its j-th column collecting class-j (k)

scores over all N local samples. We use a client-specific, (k) class-wise threshold vector tre ∈ RC , controlled by the hyperparameter τ ∈ [0, 1]. For each class j, the threshold is set to the (1 − τ )-quantile of the corresponding local z-scores:   (k) (k) tre,j = Quantile1−τ Z:,j , j = 1, . . . , C. (7) 6

FedReLa: Imbalanced Federated Learning via Re-Labeling

5. Experiments

samples remains intact. The standardization step via z-score maps this preserved relative ranking to a standardized range, enabling the selection of samples with the highest feature similarity to minority classes.

Datasets: To provide a comprehensive evaluation, we conduct experiments under both step-wise and long-tailed global imbalance settings on Fashion-MNIST (F-MNIST) (Xiao et al., 2017), CIFAR-10/100 (Krizhevsky & Hinton, 2009), and ImageNet-LT (long-tailed) (Liu et al., 2019) datasets. For step-wise imbalance, we undersample 10% or 30% of the classes with an imbalance ratio (IR) of 10 or 20. For long-tailed imbalance, the datasets are sampled into a long-tailed class distribution using an imbalance factor (IF) of 50 or 100 as in (Cao et al., 2019). To simulate cross-client heterogeneity, we employ latent Dirichlet sampling (Chen & Chao, 2021a) to partition the data in a non-IID fashion across clients. Specifically, we use K = 100 clients for the step-wise versions of Fashion-MNIST and CIFAR-10, and K = 40 for their long-tailed versions. For CIFAR-100, we use K ∈ {10, 50, 100} clients in the long-tailed setting and 10 in the step-wise setting. The heterogeneity level is controlled by the parameter α ∈ {0.1, 0.3, 10}. We set the client sample rate to 1.

By further incorporating tanh normalization, FedReLa computes well-calibrated re-labeling probabilities from these standardized scores. Consequently, even when posteriors are underestimated by a biased global model, our method can still effectively identify majority-class samples that share salient features with minority classes. We validate the proposed mechanism by examining relabeled samples randomly selected from multiple clients’ local data on CIFAR-10-LT, inspecting their underestimated original posterior probabilities and calibrated re-labeling probabilities. As shown in Figure 2, these samples exhibit strong feature affinity with their target classes, stemming from both inherently similar categories (e.g., automobile–truck, deer–horse) and instance-level visual similarities even for classes with low overall correlation (e.g., airplane–ship, bird–frog–horse). Despite their generally small underestimated posteriors, these samples are still assigned high re-labeling probabilities, confirming that FedReLa effectively extracts valuable information from biased posterior distributions to guide proper sample re-labeling.

Baseline and prior SOTA: We compare FedReLa with prior baselines and SOTA methods under both step-wise and long-tailed imbalance settings. For step-wise imbalance, we evaluate against FedAvg (McMahan et al., 2017), FedProx (Li et al., 2020), FedNova (Wang et al., 2020), MOON (Li et al., 2021), and CLIMB (Shen et al., 2021). For longtailed imbalance, we compare with FedETF (Li et al., 2023) and the latest SOTA method, FedLOGE (Xiao et al., 2024), and FedYoYo (Yan et al., 2025). As a data-level method, FedReLa can seamlessly integrate with the above methods, offering further improvements. We thus compare methods trained on original-labeled data with those trained on relabeled data by FedReLa. All methods are trained with sufficient communication rounds to converge. Please refer to Appendix B for the communication rounds needed to achieve the convergence of each method.

To validate the significance of z-score standardization in FedReLa, we conduct an ablation study comparing its performance using standardized re-labeling probabilities against directly employing underestimated posterior probabilities. Results are presented in Appendix C Table 12, confirming that z-score standardization facilitates balanced label re-allocation and yields a more favorable trade-off between Head, Medium, and Tail class performance.

automobile

airplane

Posterior: 0.30 Re-label Prob: 0.99

Posterior: 0.02 Re-label Prob: 1.00

Posterior: 0.01 Re-label Prob: 0.97

Posterior: 0.23 Re-label Prob: 1.00

Posterior: 0.03 Re-label Prob: 0.99

Posterior: 0.02 Re-label Prob: 0.99

truck

bird

deer

Posterior: 0.15 Re-label Prob: 1.00

Posterior: 0.26 Re-label Prob: 0.99

Posterior: 0.01 Re-label Prob: 0.91

Posterior: 0.10 Re-label Prob: 1.00

Posterior: 0.14 Re-label Prob: 0.81

Posterior: 0.11 Re-label Prob: 1.00

Posterior: 0.03 Re-label Prob: 0.81

Posterior: 0.10 Re-label Prob: 0.89

Posterior: 0.22 Re-label Prob: 0.93

ship

frog

Evaluation Metrics. All results are evaluated on classbalanced test sets. Under step-wise imbalance, we report overall, majority-class, and minority-class test accuracy. Under long-tailed imbalance, we report overall, head, med, and tail test accuracy, where head, med, and tail classes are defined by the cumulative training-sample proportions of 75% and 95% (detailed in Appendix B). Results in Table 1 and 2 are averaged over three runs with different random seeds.

horse

Performance comparison: For step-wise imbalance scenarios, Table 1 shows that FedReLa consistently enhances accuracy for both minority classes and overall performance across varying imbalance ratios (IR) and minority class proportions at heterogeneity level of α = 0.3 (see Appendix C for ablation analysis on α). On Fashion-MNIST and CIFAR-

Figure 2. FedReLa re-labeling examples on CIFAR-10-LT. Top red: original head classes; bottom blue: re-labeled tail classes. “Posterior”: underestimated tail-class posterior P (ytail |x); “Relabel Prob”: assigned re-labeling probabilities.

7

FedReLa: Imbalanced Federated Learning via Re-Labeling Dataset

IR

10 F-MNIST 20

10 CIFAR-10 20

10 CIFAR-100 20

Methods FedAvg FedProx FedNova MOON CLIMB FedAvg FedProx FedNova MOON CLIMB FedAvg FedProx FedNova MOON CLIMB FedAvg FedProx FedNova MOON CLIMB FedAvg FedProx FedNova MOON CLIMB FedAvg FedProx FedNova MOON CLIMB

Majority 88.43(87.40)-1.03 88.23(87.43)-0.80 86.81(87.46)+0.65 88.41(87.83)-0.58 89.05(89.98)+0.93 88.64(88.07)-0.57 89.37(87.77)-1.60 88.46(88.37)-0.09 89.07(88.07)-1.00 90.30(90.32)+0.02 60.10(59.84)-0.26 60.66(61.18)+0.52 58.54(58.60)+0.06 58.62(60.33)+1.71 81.62(82.68)+1.06 60.33(60.70)+0.37 59.33(60.58)+1.25 61.77(62.77)+1.00 58.75(59.72)+0.97 79.53(80.34)+0.81 58.67(58.08)-0.59 58.14(58.03)-0.11 58.67(57.90)-0.77 57.55(57.70)+0.15 47.96(48.28)+0.32 59.34(59.01)-0.33 58.86(58.18)-0.68 59.16(58.49)-0.67 57.89(57.43)-0.46 47.91(47.21)-0.70

10% Minority Minority 52.50(77.00)+24.50 53.20(76.80)+23.60 67.10(77.50)+10.40 47.00(73.00)+26.00 65.52(76.24)+10.72 49.00(73.10)+24.10 44.58(73.60)+29.02 52.34(71.30)+18.96 32.40(66.60)+34.20 51.28(71.34)+20.06 27.80(55.70)+27.90 30.02(58.70)+28.68 29.90(57.00)+27.10 17.10(49.30)+32.20 37.45(46.18)+8.73 17.25(51.60)+34.35 15.60(53.90)+38.30 26.05(57.80)+31.75 10.12(47.70)+37.58 28.38(40.21)+11.83 12.30(23.10)+10.80 13.00(26.00)+13.00 13.40(23.90)+10.50 13.22(23.92)+10.70 10.50(24.90)+14.40 6.80(15.80)+9.00 5.00(14.10)+9.10 7.30(17.80)+10.50 6.65(18.02)+11.37 5.02(16.25) +11.23

Overall 84.84(86.36)+1.52 84.73(86.37)+1.64 84.84(86.46)+1.62 84.27(86.35)+2.08 86.70(88.61)+1.91 84.68(86.57)+1.89 84.89(86.35)+1.46 84.85(86.66)+1.81 83.40(85.92)+2.52 86.40(88.43)+2.03 56.87(59.43)+2.56 57.60(60.93)+3.33 55.68(58.44)+2.76 54.47(59.23)+4.76 77.20(79.03)+1.83 56.02(59.79)+3.77 54.96(59.91)+4.95 58.20(62.27)+4.07 53.89(58.52)+4.63 74.42(76.33)+1.91 54.03(54.58)+0.55 53.63(54.83)+1.20 54.14(54.50)+0.36 53.12(54.32)+1.20 44.21(45.94)+1.73 54.09(54.69)+0.60 53.47(53.77)+0.30 53.97(54.42)+0.45 52.77(53.49)+0.72 43.62(44.12)+0.50

Majority 89.86(90.17)+0.31 90.60(88.14)-2.46 88.41(86.83)-1.58 90.61(89.24)-1.37 93.00(92.30)-0.70 90.44(87.33)-3.11 90.69(87.37)-3.32 85.94(87.27)+1.33 91.13(88.63)-2.50 94.34(90.28)-4.05 65.93(62.14)-3.79 67.66(60.79)-6.87 65.23(62.70)-2.53 66.67(63.21)-3.46 86.82(87.47)+0.65 67.39(61.51)-5.88 67.69(61.96)-5.73 66.97(60.12)-6.85 64.51(60.77)-3.74 87.75(85.81)-1.94 58.67(57.07)-1.60 58.84(58.10)-0.74 59.49(58.00)-1.49 58.60(56.83)-1.77 49.16(47.44)-1.72 58.73(57.50)-1.23 59.49(56.93)-2.56 59.60(58.11)-1.49 59.36(56.14)-3.22 49.22(46.42)-2.80

30% Minority Minority 60.67(70.50)+9.83 60.07(70.40)+10.33 69.77(76.17)+6.40 59.80(69.87)+10.07 67.23(75.47)+8.24 50.50(75.70)+25.20 50.00(74.90)+24.90 55.03(77.90)+22.87 44.43(74.77)+30.34 53.27(73.60)+20.33 22.67(41.33)+18.66 22.80(45.10)+22.30 23.47(39.20)+15.73 23.63(38.67)+15.04 33.59(43.26)+9.67 13.82(47.97)+34.15 15.02(47.87)+32.85 18.20(53.03)+34.83 7.65(40.03)+32.38 24.03(38.77)+14.74 14.37(25.70)+11.33 14.93(22.03)+7.10 13.53(23.23)+9.70 16.37(23.93)+7.56 10.83(25.87)+15.04 5.90(11.93)+6.03 6.03(13.23)+7.20 6.03(13.57)+7.54 5.90(13.87)+7.97 4.34(13.44)+9.10

Overall 81.10(84.27)+3.17 81.44(82.82)+1.38 82.82(83.63)+0.81 81.37(83.43)+2.06 85.27(87.25)+1.98 78.46(83.84)+5.38 78.48(83.63)+5.15 76.67(84.46)+7.79 77.12(84.47)+7.35 82.02(85.28)+3.26 52.95(55.90)+2.95 54.20(56.08)+1.88 52.70(55.65)+2.95 53.76(55.85)+2.09 70.85(74.21)+3.36 51.32(57.45)+6.13 51.89(57.73)+5.84 52.34(57.99)+5.65 47.45(54.55)+7.10 68.64(71.70)+3.06 45.38(47.66)+2.28 45.67(47.28)+1.61 45.70(47.57)+1.87 45.93(46.96)+1.03 37.66(40.97)+3.31 42.88(43.83)+0.95 43.45(43.82)+0.37 43.53(44.75)+1.22 43.32(43.46)+0.14 35.76(36.53)+0.77

Table 1. Test accuracies (in %) in the format of original (+FedReLa)+ enhancement / -trade-off of different methods on step-wise imbalance datasets at heterogeneity level of α = 0.3.

improves overall accuracy by +17.08% on CIFAR-10-LT and +8.87% on CIFAR-100-LT over the FedLOGE baseline. Overall, these results suggest that FedReLa rebalances performance toward tail classes without requiring a uniform sacrifice in head accuracy; in several regimes, both overall and tail accuracy improve simultaneously, which is desirable for long-tailed federated learning. On CIFAR-100-LT, we further scale the number of clients to K = 50 and K = 100; results in Table 8 show that FedReLa consistently improves overall accuracy, achieves competitive state-of-the-art performance, and remains robust as the client population grows.

10, FedReLa achieves 6.40%–32.20% minority-class accuracy improvement and 0.81%–4.76% overall accuracy gain under IR = 10. At IR = 20, the approach further elevates minority-class accuracy by 11.83%–38.30% and overall accuracy by 1.46%–7.79%. On CIFAR-100, FedReLa delivers a steady 6.03%–15.04% boost in minority-class accuracy while maintaining overall accuracy superiority. We note slightly degraded majority-class accuracy in the 30%-minority-class setting, as improved minority-class performance inevitably impairs over-privileged majority-class performance. This aligns with the fundamental trade-off characteristic shared by all imbalanced learning methods. For the 10%-minority-class scenario, FedReLa exhibits a negligible impact on majority-class accuracy and even improves it on CIFAR-10. This stems from label rectification by FedReLa, which relieves class overlap and thereby reduces outlier-induced interference for majority classes, particularly on clients with local-global IR mismatch. We further conducted additional experiments on FedETF and FedLoGe on step-wise setting, and FedReLa delivers 6.13% and 13.72% improvements on overall accuracy at heterogeneity level 0.1 for IR ∈ [10, 20] (See Table 6).

Method

Overall (%)

H/M/T (%)

FedYoYo +FedReLa FedLoGe +FedReLa

38.15 38.78 30.52 31.70

41.19/39.42/31.08 40.73/40.06/33.71 46.29/28.01/15.02 45.43/30.44/18.02

Table 3. Results on ImageNet-LT (H=Head, M=Medium, T=Tail).

Large-Scale Dataset Validation on ImageNet-LT: We conduct experiments on ImageNet-LT with data heterogeneity level α = 0.1, 20 clients, and 0.4 participation fraction. Another recent SOTA method, FedYoYo (Yan et al., 2025), is used to demonstrate the algorithmic agnosticism of Fe-

On long-tailed datasets (Table 2), FedReLa yields consistent gains when built upon FedLOGE, especially under stronger data heterogeneity and more severe class imbalance. In the most challenging setting (IF=100, α = 0.1), FedReLa 8

FedReLa: Imbalanced Federated Learning via Re-Labeling Dataset

IF

50 CIFAR-10 100

50 CIFAR-100 100

Heterogeneity α = 0.1 α = 0.3 α = 10 Method/Metrics H/M/T-shots Overall H/M/T-shots Overall H/M/T-shots FedETF 85.07/41.03/5.40 47.96 79.60/67.93/43.10 65.15 88.77/73.22/56.81 +(FedReLa) 78.70/65.20/35.57 61.71 74.95/71.57/55.63 68.14 86.80/76.62/71.59 FedLOGE 56.51/58.98/59.74 58.22 82.81/76.90/67.98 76.59 88.32/81.32/72.40 +(FedReLa) 69.55/70.13/53.09 64.78 80.09/78.47/76.86 78.63 83.79/83.32/84.12 FedETF 66.90/36.80/24.40 40.87 72.05/37.13/25.32 42.88 92.16/69.52/50.13 +(FedReLa) 57.60/44.53/36.95 45.42 72.59/40.11/30.47 46.00 90.17/70.73/66.91 FedLOGE 44.93/50.27/41.30 45.08 86.71/67.52/57.89 69.43 91.90/75.07/62.50 +(FedReLa) 70.60/59.60/57.75 62.16 78.62/68.10/69.39 71.77 84.58/75.48/79.70 FedETF 62.97/44.65/20.12 42.35 68.89/46.87/20.28 44.83 71.11/48.78/18.80 +(FedReLa) 56.81/48.60/29.20 44.71 61.79/51.20/30.38 47.41 56.37/53.09/34.30 FedLOGE 32.92/37.70/34.64 35.09 59.40/47.76/31.40 45.87 68.37/52.31/26.45 +(FedReLa) 51.22/46.82/30.37 42.73 63.93/51.99/30.04 48.25 67.65/51.30/29.77 FedETF 64.48/42.64/13.72 37.11 68.75/48.13/14.93 39.63 71.76/47.48/16.45 +(FedReLa) 56.10/46.73/24.14 40.19 61.01/51.24/25.02 42.70 56.05/50.78/29.86 FedLOGE 27.00/36.41/25.62 29.21 50.80/43.67/25.26 37.75 69.55/50.40/22.98 +(FedReLa) 49.25/47.98/23.11 38.08 62.36/52.15/23.98 42.89 66.28/50.43/25.92 Table 2. Test accuracies (in %) of different methods on long-tailed CIFAR-10/100.

dReLa. Although FedYoYo falls outside our core comparison scope, as it requires each client to upload the estimated local distribution for aggregation on the server (raising concerns about data privacy), we still include this comparison to demonstrate that FedReLa can consistently enhance performance on the large-scale dataset across various algorithmic methods.

More detailed ablation studies can be found in Appendix C for (i) the importance of Z-score standardization, (ii) different data-heterogeneity levels, and (iii) comparing oneshot with multi-shot relabeling. Sensitivity analysis on Trelabel . We study how this hyperparameter affects performance on long-tailed CIFAR-10 and CIFAR-100 with IF=100 under two heterogeneity levels (α = 1 and α = 10); full results are reported in Table 11 (Appendix B.3). Across both datasets and heterogeneity settings, FedReLa consistently outperforms the FedETF baseline in overall accuracy and, more importantly, in tailclass accuracy, which is the primary objective under class imbalance. Once Trelabel reaches 60% of the total training rounds, further delaying re-labeling yields only marginal changes, indicating that performance is relatively insensitive to Trelabel beyond this point. Among the choices examined, Trelabel = 80%R achieves the strongest overall and tail-class results in most scenarios. We therefore adopt Trelabel ≈ 80%R as the default in our main experiments for robust performance across datasets and heterogeneity levels.

The result in Table 3 confirms that FedReLa’s sample-level re-labeling mechanism avoids the scalability bottlenecks of feature-space methods (e.g., SMOTE) and maintains effectiveness on the large-scale dataset. The consistency of performance gains validates FedReLa’s inherent scalability for real-world large-scale federated learning scenarios. Table 4. Ablation on normalization strategies for relabeling probability calibration on CIFAR-100 (IF=100). All variants use a 5% relabeling threshold for fairness. Strategy

Overall

Head

Medium

Tail

Baseline (FedETF) Min-max norm Z-score + tanh

42.81 43.33 44.54

71.73 70.41 67.53

51.44 52.03 54.01

19.82 21.46 24.52

Overall 74.52 79.18 81.45 83.75 68.56 75.04 75.09 79.90 44.83 47.18 47.88 48.57 39.67 42.51 42.87 43.36

6. Conclusion Ablation study To validate superiority over alternatives, we further compare with min-max normalization. As shown in Table 4, z-score + tanh achieves the largest gains in both overall and tail-class accuracy (the core goal of imbalanced learning). Although min-max normalization also improves performance, its gain on tail-class accuracy is limited. Minmax normalization linearly scales posteriors and is maxvalue-sensitive, squeezing mildly deviant samples to small relabeling probabilities (e.g., z-scores of 10 and 15 are both mapped to near 1 by tanh, reflecting their high relabeling priority rather than being overshadowed by extreme values).

We propose FedReLa, a data-level approach for addressing class imbalance and data heterogeneity in FL. By asymmetrically re-labeling local data by a feature-dependent label re-allocator, FedReLa rectifies decision boundaries without relying on global class priors or additional communication. Empirical results across step-wise and long-tailed settings demonstrate consistent improvements in minority-class and overall accuracy over existing methods, especially under extreme heterogeneity. FedReLa is easy to integrate into algorithmic methods, offering a practical solution for realworld imbalanced federated learning. 9

FedReLa: Imbalanced Federated Learning via Re-Labeling

Impact Statement

Chou, H.-P., Chang, S.-C., Pan, J.-Y., Wei, W., and Juan, D.-C. Remix: rebalanced mixup. In European conference on computer vision, pp. 95–110. Springer, 2020.

This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

Duan, M., Liu, D., Chen, X., Tan, Y., Ren, J., Qiao, L., and Liang, L. Astraea: Self-balancing federated learning for improving classification accuracy of mobile deep learning applications. In 2019 IEEE 37th international conference on computer design (ICCD), pp. 246–254. IEEE, 2019.

Acknowledgements FL is supported by the Australian Research Council (ARC) (Grant No. DE240101089, LP240100101, DP230101540) and the NSF&CSIRO Responsible AI program (Grant No. 2303037). MG was supported by ARC DP240102088. GW was supported by the National Natural Science Foundation of China (Grant No. 12471255), and the Fundamental Research Funds for the Central Universities (Grant No. 63263103). LP is supported by ARC (Grant No. LP240100101).

Duda, R. O., Hart, P. E., et al. Pattern classification. John Wiley & Sons, 2006. Fotouhi, S., Asadi, S., and Kattan, M. A comprehensive data level analysis for cancer diagnosis on imbalanced data. Journal of biomedical informatics, 90:103089, 2019. Fraboni, Y., Vidal, R., Kameni, L., and Lorenzi, M. Clustered sampling: Low-variance and improved representativity for clients selection in federated learning. In International Conference on Machine Learning, pp. 3407– 3416. PMLR, 2021.

References Acar, D. A. E., Zhao, Y., Navarro, R. M., Mattina, M., Whatmough, P. N., and Saligrama, V. Federated learning based on dynamic regularization. arXiv preprint arXiv:2111.04263, 2021.

Frénay, B. and Verleysen, M. Classification in the presence of label noise: a survey. IEEE transactions on neural networks and learning systems, 25(5):845–869, 2013.

Azaria, A., Richardson, A., Kraus, S., and Subrahmanian, V. S. Behavioral analysis of insider threat: A survey and bootstrapped prediction in imbalanced data. IEEE Transactions on Computational Social Systems, 1(2):135– 155, 2014.

Goldberger, J. and Ben-Reuven, E. Training deep neuralnetworks using a noise adaptation layer. International conference on learning representations, 2022. Han, H., Wang, W.-Y., and Mao, B.-H. Borderline-smote: a new over-sampling method in imbalanced data sets learning. International conference on intelligent computing, 2005.

Cao, K., Wei, C., Gaidon, A., Arechiga, N., and Ma, T. Learning imbalanced datasets with label-distributionaware margin loss. In Advances in Neural Information Processing Systems, 2019.

He, H., Bai, Y., Garcia, E., and Li, S. Adasyn: Adaptive synthetic sampling approach for imbalanced learning. 2008 IEEE international joint conference on neural networks, 2008.

Chapelle, O., Schölkopf, B., and Zien, A. Label Propagation and Quadratic Criterion, pp. 193–216. 2006. Chawla, N., Bowyer, K., Hall, L., and Kegelmeyer, W. P. Smote: synthetic minority over-sampling technique. Journal of artificial intelligence research, 16:321–357, 2002.

Iscen, A., Tolias, G., Avrithis, Y., and Chum, O. Label propagation for deep semi-supervised learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.

Chen, H.-Y. and Chao, W.-L. On bridging generic and personalized federated learning for image classification. arXiv preprint arXiv:2107.00778, 2021a.

Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S. J., Stich, S. U., and Suresh, A. T. Scaffold: Stochastic controlled averaging for on-device federated learning. arXiv preprint arXiv:1910.06378, 2(6), 2019.

Chen, H.-Y. and Chao, W.-L. On bridging generic and personalized federated learning for image classification. arXiv preprint arXiv:2107.00778, 2021b.

Krizhevsky, A. and Hinton, G. Learning multiple layers of features from tiny images. Technical Report 0, University of Toronto, Toronto, Ontario, 2009. URL https://www.cs.toronto.edu/ ~kriz/learning-features-2009-TR.pdf.

Chen, W., Horvath, S., and Richtarik, P. Optimal client sampling for federated learning. arXiv preprint arXiv:2010.13723, 2020. 10

FedReLa: Imbalanced Federated Learning via Re-Labeling

Li, Q., He, B., and Song, D. Model-contrastive federated learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 10713– 10722, 2021.

Shingi, G. A federated learning based approach for loan defaults prediction. In 2020 International Conference on Data Mining Workshops (ICDMW), pp. 362–368, 2020. doi: 10.1109/ICDMW51313.2020.00057.

Li, T., Sahu, A. K., Zaheer, M., Sanjabi, M., Talwalkar, A., and Smith, V. Federated optimization in heterogeneous networks. Proceedings of Machine learning and systems, 2:429–450, 2020.

Tan, J., Wang, C., Li, B., Li, Q., Ouyang, W., Yin, C., and Yan, J. Equalization loss for long-tailed object recognition, 2020. URL https://arxiv.org/abs/2003. 05176.

Li, Z., Shang, X., He, R., Lin, T., and Wu, C. No fear of classifier biases: Neural collapse inspired federated learning with synthetic and fixed classifier. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pp. 5319–5329, October 2023.

Tan, Y. N., Tinh, V. P., Lam, P. D., Nam, N. H., and Khoa, T. A. A transfer learning approach to breast cancer classification in a federated learning framework. IEEE Access, 11:27462–27476, 2023. doi: 10.1109/ACCESS.2023. 3257562.

Liu, Z., Miao, Z., Zhan, X., Wang, J., Gong, B., and Yu, S. X. Large-scale long-tailed recognition in an open world. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.

Wang, J., Liu, Q., Liang, H., Joshi, G., and Poor, H. V. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in neural information processing systems, 33:7611–7623, 2020.

Manwani, N. and Sastry, P. Noise tolerance under risk minimization. IEEE transactions on cybernetics, 43(3): 1146–1151, 2013. Mariani, G., Scheidegger, F., Istrate, R., Bekas, C., and Malossi, C. Bagan: Data augmentation with balancing gan, 2018. URL https://arxiv.org/abs/1803. 09655. McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication-efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. 1273–1282. PMLR, 2017.

Wang, L., Xu, S., Wang, X., and Zhu, Q. Addressing class imbalance in federated learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10165–10173, 2021. Wicaksana, J., Yan, Z., Zhang, D., Huang, X., Wu, H., Yang, X., and Cheng, K.-T. Fedmix: Mixed supervised federated learning for medical image segmentation, 2022. URL https://arxiv.org/abs/2205.01840. Xiao, H., Rasul, K., and Vollgraf, R. Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms. arXiv e-prints, art. arXiv:1708.07747, August 2017. doi: 10.48550/arXiv.1708.07747.

Menon, A. K., Jayasumana, S., Rawat, A. S., Jain, H., Veit, A., and Kumar, S. Long-tail learning via logit adjustment. arXiv preprint arXiv:2007.07314, 2020.

Xiao, Z., Chen, Z., Liu, S., Wang, H., Feng, Y., Hao, J., Zhou, J. T., Wu, J., Yang, H., and Liu, Z. Fed-grab: Federated long-tailed learning with self-adjusting gradient balancer. Advances in Neural Information Processing Systems, 36:77745–77757, 2023.

Odena, A., Olah, C., and Shlens, J. Conditional image synthesis with auxiliary classifier gans, 2017. URL https://arxiv.org/abs/1610.09585. Ramasubramanian, S., Rangwani, H., Takemori, S., Samanta, K., Umeda, Y., and Radhakrishnan, V. B. Selective mixup fine-tuning for optimizing non-decomposable metrics. In The Twelfth International Conference on Learning Representations, 2024.

Xiao, Z., Chen, Z., Liu, L., Feng, Y., Wu, J., Liu, W., Zhou, J. T., Yang, H. H., and Liu, Z. Fedloge: Joint local and generic federated learning under long-tailed data. arXiv preprint arXiv:2401.08977, 2024.

Shang, X., Lu, Y., Huang, G., and Wang, H. Federated learning on heterogeneous and long-tailed data via classifier re-training with federated features. arXiv preprint arXiv:2204.13399, 2022.

Yan, S., Li, Z., Wu, C., Pang, M., Lu, Y., Yan, Y., and Wang, H. You are your own best teacher: Achieving centralized-level performance in federated learning under heterogeneous and long-tailed data. arXiv preprint arXiv:2503.06916, 2025.

Shen, Z., Cervino, J., Hassani, H., and Ribeiro, A. An agnostic approach to federated learning with class imbalance. In International Conference on Learning Representations, 2021.

Zhang, H., Cisse, M., Dauphin, Y. N., and Lopez-Paz, D. mixup: Beyond empirical risk minimization. arXiv preprint arXiv:1710.09412, 2017. 11

FedReLa: Imbalanced Federated Learning via Re-Labeling

Zhang, J., Li, Z., Li, B., Xu, J., Wu, S., Ding, S., and Wu, C. Federated learning with label distribution skew via logits calibration. In International Conference on Machine Learning, pp. 26311–26329. PMLR, 2022. Zhao, Y., Li, M., Lai, L., Suda, N., Civin, D., and Chandra, V. Federated learning with non-iid data. arXiv preprint arXiv:1806.00582, 2018.

12

FedReLa: Imbalanced Federated Learning via Re-Labeling

A. Technical Details and Proofs Example 1. We use an extreme example to illustrate that the mismatches between global and local imbalance ratios can amplify the bias in the aggregated decision boundary. Consider a binary classification problem with two classes, j and ℓ, and two clients, k1 and k2 . Assume that the global class priors satisfy πℓ ≫ πj , where πj = mj /n, πℓ = mℓ /n and n = |D(k1 ) | + |D(k2 ) |. Here, mj and mℓ , satisfying mj + mℓ = n, are the number of data points in class j and ℓ, respectively. Suppose the local dataset D(k1 ) contains (mj − 1) samples from the global minority class j and one sample from the global majority class ℓ, while the local dataset D(k2 ) contains (mℓ − 1) samples from class ℓ and one sample from class j. The local decision boundaries on D(k1 ) and D(k2 ) are:     Pj (x) 1 Pj (x) x∈X : = and x ∈ X : = mℓ − 1 . Pℓ (x) mj − 1 Pℓ (x) [w]

(k )

(k )

In FL, consider the global aggregated model ηj (x) = wk1 ηj 1 (x) + wk2 ηj 2 (x). Suppose the aggregation weights are chosen as wk1 ∝ |D(k1 ) | and wk2 ∝ |D(k2 ) |, which is widely used in imbalanced classification in the literature. Since |D(k1 ) | = mj and |D(k2 ) | = mℓ , it follows that wk1 = πj and wk2 = πℓ , implying wk1 ≪ wk2 . In addition, the local imbalance ratios are IR(D(k1 ) ) = 1/(mj − 1) and IR(D(k2 ) ) = mℓ − 1, so [w] [w] that IR(D(k1 ) ) ≪ IR(D(k2 ) ). Thus, the decision boundary of the global aggregated model ηj (x) is Sj,ℓ = {x ∈ X : [w]

[w]

[w]

[w]

Pj (x)/Pℓ (x) = πℓ /πj } with πℓ = πj (mj −1)/mj +πℓ /mℓ and πj = πj /mj +πℓ (mℓ −1)/mℓ . As a result, during model aggregation in each communication round, the global imbalance is exacerbated due to the dominant contribution from client k2 , amplified by both its large aggregation weight wk2 and local imbalance ratio IR(D(k2 ) ). [w]

Even under the uniform averaging with wk1 = wk2 = 1/2, the decision boundary of the global aggregated model ηj (x) [w]

[w]

[w]

[w]

[w]

is Sj,ℓ = {x ∈ X : Pj (x)/Pℓ (x) = πℓ /πj } with πℓ = (mj − 1)/(2mj ) + 1/(2mℓ ) and πj 1)/(2mℓ ). The decision boundary is still biased due to the global imbalance.

= 1/(2mj ) + (mℓ −

Remark 2. Due to data heterogeneity, local class distribution can deviate significantly from the global one. It is possible for a class that is globally a minority to become a majority within certain clients. As local clients lack access to the global class prior ratios, the mismatch can lead to re-labeling in unexpected directions. For instance, when re-labeling class j samples to class ℓ even if πℓ ≫ πj globally. To handle this, we let the re-labeling direction be determined by local priors: on client k, (k) (k) if πℓ > πj , then class ℓ samples are re-labeled to class j, and vice versa. This results in the following Bayesian decision boundary on client k: ) (k) (k) (k) 1 − 2ρℓ→j (x∗ ) · I(πℓ > πj ) πℓ(k) Pj (x∗ ) = · (k) . x ∈X : (k) (k) (k) Pℓ (x∗ ) 1 − 2ρ (x∗ ) · I(π < π ) π

( Se(k) =

∗

j→ℓ

j

ℓ

j

[w]

Then, the Bayesian decision boundary of the global aggregated model ηej (x) takes the form: ( e[w]

S

=

) PK (k) (k) (k) (k) > πj )/πℓ πℓ Pj (x∗ ) k=1 wk πℓ [1 − 2ρℓ→j (x)]I(πℓ x ∈X : = PK · . (k) (k) (k) (k) Pℓ (x∗ ) wk π [1 − 2ρ (x)]I(π < π )/πj πj ∗

k=1

j

j→ℓ

ℓ

j

PK (k) (k) (k) (k) > πj ) > k=1 I(πℓ < πj ), meaning k=1 I(πℓ (k ) (k ) more clients locally reflect the global imbalance than contradict it. Furthermore, even if πℓ 0 < πj 0 for some client (k0 ) (k0 ) k0 , its weight wk0 ∝ |D | is often small as |D | is less than double of the total number of class-j samples in the

Under global imbalance where πℓ ≫ πj , we typically observe that

PK

full dataset D. As a result, we still expect a correction in the decision boundary of the global aggregated model with (k) (k) (k) (k) k=1 wk πℓ [1−2ρℓ→j (x)]I(πℓ >πj )/πℓ (k) (k) (k) (k) k=1 wk πj [1−2ρj→ℓ (x)]I(πℓ <πj )/πj

PK PK

< 1.

Explanation on Aggregated Model Representation To analyze P how re-labeling influences the global decision boundary, K we adopt the global model defined via posterior aggregation (i.e., k=1 wk f (x, θ(k) ), f (x, θ(k) ) denotes the local  where P K (k) (k) posterior of client k with parameter θ ) instead of parameter aggregation (i.e., f x, k=1 wk θ ). This choice is 13

FedReLa: Imbalanced Federated Learning via Re-Labeling

motivated by two key considerations: (1) the posterior-aggregated form renders changes in the decision boundary more explicit and easier to quantify, which aligns with our focus on analyzing re-labeling’s effect; (2) it is consistent with statistical model averaging ideas, providing a flexible framework for heterogeneous FL scenarios. No specific constraints are imposed on the aggregation weights wk , and our only assumption is that the aggregated global model can be expressed as a weighted average of local posteriors, which we explicitly formalize. Furthermore, the two aggregation paradigms (parameter-aggregated and posterior-aggregated) are approximately equivalent under mild regularity conditions, as justified by first-order Taylor expansion: Assume all local parameters θ(k) are sufficiently close to a common reference value θ0 (a reasonable condition in late-stage FL training when models converge). Expanding both models around θ0 : 1. For the parameter-aggregated global model: ! K K X X ∂f (x, θ) (k) wk (θ(k) − θ0 ) f x, wk θ ≈ f (x, θ0 ) + ∂θ θ=θ0 k=1

k=1

= f (x, θ0 ) +

K X

wk

k=1

2. For the posterior-aggregated global model (noting K X k=1

∂f (x, θ) (θ(k) − θ0 ) ∂θ θ=θ0

PK

k=1 wk = 1):

∂f (x, θ) wk f (x, θ(k) ) ≈ f (x, θ0 ) + ∂θ θ=θ0 = f (x, θ0 ) +

K X

wk

k=1

K X

! wk θ(k) − θ0

k=1

∂f (x, θ) (θ(k) − θ0 ) ∂θ θ=θ0

The two expansions are identical, confirming that the parameter-aggregated and posterior-aggregated global models are first-order equivalent when local parameters are sufficiently close. This justifies our use of the posterior-aggregated form for analyzing decision boundary changes, as it does not introduce substantive deviations from standard parameter-aggregated FL while offering greater analytical tractability. A.1. Proof of Lemma 2 e (k) is Proof. As we are considering the binary classification setting, the optimal Bayesian decision boundary based on D n o (k) (k) Se(k) = x∗ ∈ X : ηej (x∗ ) = ηeℓ (x∗ ) , where (k)

(k)

(k)

(k)

(k)

ηeℓ (x) = ηℓ (x)[1 − ρℓ→j (x)] + ηj (x)ρj→ℓ (x). (k)

Given the formulation of ηej (x), we need (k)

(k)

(k)

(k)

(k)

(k)

(k)

(k)

(k)

(k)

(k)

(k)

ηj (x∗ )[1 − ρj→ℓ (x∗ )] + ηℓ (x∗ )ρℓ→j (x∗ ) = ηℓ (x∗ )[1 − ρℓ→j (x∗ )] + ηj (x∗ )ρj→ℓ (x∗ ), which is equivalent to (k)

(k)

ηj (x∗ )[1 − 2ρj→ℓ (x∗ )] = ηℓ (x∗ )[1 − 2ρℓ→j (x∗ )]. P (k) (k) (k) Regarding the fact that ηj (x) = πj Pj (x)/ j0 ∈Y πj0 Pj0 (x), the above equation can be simplified to (k)

(k)

πj Pj (x∗ )[1 − 2ρj→ℓ (x∗ )] = πℓ Pℓ (x∗ )[1 − 2ρℓ→j (x∗ )], and the final result follows immediately. 14

FedReLa: Imbalanced Federated Learning via Re-Labeling

A.2. Proof of Lemma 3 Proof. The global aggregated model satisfies [w]

ηej (x) =

K X

(k)

wk ηej (x) =

k=1

K X

n o (k) (k) (k) wk ηj (x) + ηℓ (x)ρℓ→j (x)

k=1

and K X

[w]

ηeℓ (x) =

(k)

wk ηeℓ (x) =

k=1

K X

(k)

(k)

wk ηℓ (x)[1 − ρℓ→j (x)].

k=1

∗

Then, for x on the Bayesian decision boundary, it requires that [w]

ηej (x∗ ) =

K X

n o (k) (k) (k) wk ηj (x∗ ) + ηℓ (x∗ )ρℓ→j (x∗ )

k=1

=

K X

(k)

(k)

[w]

wk ηℓ (x∗ )[1 − ρℓ→j (x∗ )] = ηeℓ (x∗ ),

k=1

which can be simplified to K X k=1 (k)

(k)

Applying ηj (x) = πj Pj (x)/

(k)

wk ηj (x∗ ) =

K X

(k)

(k)

wk ηℓ (x∗ )[1 − 2ρℓ→j (x∗ )].

k=1

(k) j0 ∈Y πj0 Pj0 (x) again, we get the desired result.

P

B. Additional Experiment Details The code is available at: https://github.com/guangzhengh/FedReLa.git. Training details. To ensure fair comparison, all global models are trained until full convergence with communication rounds adapted per method. Specifically, baseline methods require 500 rounds for convergence, while CLIMB, which introduces class-wise loss reweighting parameters, demands extended training: 2000 rounds on Fashion-MNIST and CIFAR-10, and 1000 rounds on CIFAR-100. As we do not intend to compare these algorithm-level methods, we use the SGD optimizer with the same weight decay and momentum as they reported in their original implementations: weight decay of 0.00001 and momentum 0.9 for all methods except long-tailed-oriented methods FedETF and FedLOGE, which follow their original implementations with zero weight decay and momentum 0.5. All experiments were conducted with three distinct random seeds, and their average results are reported in the tables. Evaluation metrics. A balanced test dataset is used to evaluate the overall accuracy performance of the global model. Additionally, the average test accuracy for both minority and majority classes is reported for the step-wise imbalanced setting. For long-tailed datasets, we report the accuracy over head, medium, and tail classes as Many-, Medium-, and Few-shot, respectively. Adhering to the long-tailed federated learning protocol established in (Xiao et al., 2024), we categorize classes into three disjoint subsets based on sample size distribution: head (majority), medium, and tail (minority) class groups, constituting 75%, 20%, and 5% of total samples, respectively. To evaluate model performance through stratified accuracy metrics, we report Head/Medium/Tail-shot accuracies corresponding to these partitions in Table 2. B.1. Computational cost All experiments were conducted on a Spartan cluster on a single node equipped with one NVIDIA H100 GPUs (80GB memory) 10GB RAM with 12 CPU cores. Before approximating the computational cost of FedReLa, we would like to clarify the fundamental difference between extra Local training and extra local computation: 15

FedReLa: Imbalanced Federated Learning via Re-Labeling

1. Local training overhead involves gradient updates for new parameters or module. For example, methods that introduce new optimizable parameters (e.g., CLIMB, FedLOGE, etc.) require extra per-round local training overhead to update the gradients of these parameters. 2. ONE-TIME Model Inference: FedReLa only performs one-time model inference during a single round to obtain posterior probabilities, without updating the model or gradients. Therefore, we describe FedReLa as operating "without extra local training." Approximate one-time computation cost of FedReLa. The strength of FedReLa as a data-level method lies in its requirement for only a single computational step during a single round to refine the imbalanced data distribution, thereby achieving long-lasting improvements in model performance. The core operation of FedReLa is model inference (forward pass) to obtain the local posterior probability matrix Q(k) . We approximately consider FLOPtrain = FLOPforward + FLOPbackpropagation , FLOPbackpropagation ≈ 2 × FLOPforward . Thus, the FLOPs required for Q(k) = f (θTglobal ; X (k) ) can be approximately quantified with: relabel FLOPQ(k) = FLOPforward ≈

1 FLOPtrain . 3

The total computation cost of FedReLa is approximately 1/3 of the computation cost of a single training round. This cost is One-Time only during the single round of Trelabel . More importantly, the local posterior probabilities can be naturally collected during training epochs. This allows the computation cost of this one-time model inference to be merged with the normal training overhead. Runtime comparison. Unlike methods requiring from-scratch training, FedReLa enhances classifier performance solely through one-shot re-labeling during the fine-tuning phase. Consequently, its computational overhead is primarily determined by the base federated learning algorithm it augments. For instance, each communication round of FedLOGE requires an average of 72.36 seconds on CIFAR100. When FedReLa enhances FedLOGE with a one-shot computation for label re-allocator, the average communication round time increased to 73.06 seconds, which is negligible. B.2. Additional experiment results Additional experiment on step-wise setting with recent SOTAs. Although recent methods, such as FedETF (Li et al., 2023) and FedLOGE (Xiao et al., 2024), are long-tail-oriented approaches, we conducted additional experiments on CIFAR-10 with step-wise imbalance. The results in Table 6 demonstrate that FedReLa still achieves SOTA performance on step-wise imbalance. FedReLa brings significant improvements, especially under higher imbalance ratios and more heterogeneous data. α = 0.3 α = 0.1 Method Minority/Majority Overall Minority/Majority Overall FedETF 74.21/93.79 84.01 44.14/96.46 70.30 10 +FedReLa 82.11/91.72 86.92 68.28/84.52 76.43 FedLOGE 80.49/92.12 86.32 61.57/86.05 73.81 +FedReLa 85.81/89.73 87.77 68.7/81.64 75.17 FedETF 69.31/87.73 78.52 43.65/72.55 58.10 20 +FedReLa 82.75/83.74 83.11 67.85/75.75 71.82 FedLOGE 79.30/85.9 82.60 45.61/63.79 54.70 +FedReLa 79.60/84.21 81.90 59.18/70.73 64.95 IR

Table 6. Performance on Step-wise-imbalanced CIFAR-10.

Additional experiment on higher proportion of minority classes. In addition to 10% and 30% minority classes for step-wise-imbalanced datasets, we further extend the proportion to 50% to examine the consistency of enhancement from 16

FedReLa: Imbalanced Federated Learning via Re-Labeling

FedReLa on extreme conditions. As demonstrated in Table 7, FedReLa delivers significant performance gains even in the extreme case where minority classes constitute 50% of the data. Without the FedReLa boost, baseline methods exhibit pronounced accuracy degradation as the proportion of the minority class increases. Our proposed label re-allocator effectively mitigates this performance deterioration while simultaneously enhancing overall accuracy. These results strongly validate FedReLa’s capability to provide robust performance enhancements for federated learning methods that face substantial minority class presence.

Method FedAvg FedProx FedNova MOON CLIMB

Fashion-MNIST Minority Overall 63.44(77.10)+13.66 78.29(82.90)+4.61 63.78(77.24)+13.46 78.62(82.62)+4.00 77.60(80.50)+2.90 81.89(83.30)+1.41 64.68(76.60)+11.92 79.22(82.74)+3.52 75.47(79.90)+4.43 85.22(87.14)+1.92

IR=10 with 50% Minority Classes CIFAR-10 Minority Overall 16.94(44.42)+27.48 48.67(56.72)+8.05 16.32(43.54)+27.22 48.20(56.52)+8.32 23.47(39.20)+15.73 52.70(55.65)+2.95 11.20(38.54)+27.34 46.35(54.69)+8.34 31.35(42.85)+11.50 69.68(72.01)+2.33

CIFAR-100 Minority Overall 12.17(25.27)+13.10 42.48(46.76)+4.28 12.83(23.13)+10.30 41.97(46.28)+4.31 13.53(23.23)+9.70 45.70(47.57)+1.87 11.17(24.23)+13.06 42.53(46.56)+4.03 11.00(24.48)+13.48 30.71(34.79)+4.08

Table 7. Test accuracies (in %) of different methods on step-wise imbalance datasets under IR=10 with 50% minority classes at heterogeneity level α = 0.3 in the format of original (+FedReLa) + enhancement.

Large number of clients on CIFAR100-LT We extend CIFAR100-LT experiments to 50 and 100 clients, with an imbalance factor imb_f actor = 100 and data heterogeneity α = 0.1. The participation fractions are set to 0.2 and 0.1, respectively. As the number of clients increases, class absences become increasingly severe. This setup aims to verify FedReLa’s robustness to extreme class imbalance and its compatibility with diverse algorithmic approaches.

Method

50 Clients

100 Clients

Overall Accuracy (%)

H/M/F Accuracy (%)

Overall Accuracy (%)

H/M/F Accuracy (%)

FedLC (Zhang et al., 2022) +FedReLa

32.81 34.76

56.20/32.42/9.74 49.92/35.24/17.21

23.72 25.13

46.41/20.74/4.23 39.82/28.34/7.02

FedYoYo (Yan et al., 2025) +FedReLa

40.89 41.31

54.32/41.95/24.12 53.62/42.24/25.91

30.73 32.13

34.12/29.64/27.92 33.90/32.72/29.22

FedETF +FedReLa

31.89 33.94

60.67/40.45/9.22 55.12/43.61/15.12

28.71 31.50

59.00/33.72/9.73 52.21/38.73/16.53

FedLoGe +FedReLa

34.83 35.62

57.12/42.21/17.29 57.01/44.32/18.00

33.08 34.32

62.71/38.78/13.75 59.90/42.22/16.00

Table 8. Performance comparison on CIFAR100-LT with 50/100 clients (H=Head, M=Medium, F=Few-shot). FedReLa consistently boosts few-shot accuracy across baselines.

Table 8 demonstrates three key conclusions: (1) FedReLa delivers consistent enhancements for all baselines; (2) Even with 100 clients (a large-scale client setup), FedReLa maintains performance gains, validating its scalability to distributed environments with numerous clients and its robustness to severe class absence; (3) The consistent improvements across diverse algorithmic paradigms further confirm FedReLa’s algorithm-agnostic property as a data-level plug-in.

Tail-Class Accuracy Gain on CIFAR10-LT Under Extreme Heterogeneity Under α = 0.1, 70% of tail classes are absent from clients, simulating extreme real-world heterogeneity. 17

FedReLa: Imbalanced Federated Learning via Re-Labeling

Method

IF

+FedReLa

Med+Tail Gain (%)

Overall Gain (%)

α=0.1

α=0.3

α=10

α=0.1

α=0.3

α=10

FedETF FedETF

50 100

+54.34 +20.28

+16.17 +8.13

+18.18 +17.99

+13.75 +4.55

+2.99 +3.12

+4.66 +6.48

FedLoGe FedLoGe

50 100

+4.50 +25.78

+10.45 +12.08

+13.72 +17.61

+6.56 +17.08

+2.04 +2.34

+2.30 +4.81

Table 9. Accuracy gains of +FedReLa on CIFAR-10-LT vs. the matching baseline in Table 2. Med+Tail gain is the sum of medium- and tail-class improvements.

As presented in Table 9, FedReLa yields its largest accuracy improvements under the most extreme long-tailed and heterogeneous settings, with gains in both overall and medium-/tail-class performance becoming markedly more pronounced as the imbalance factor increases and client data grow more non-IID. In contrast, improvements are comparatively modest under milder regimes where the long-tail effect is weaker and client distributions are closer to IID. These results confirm that FedReLa is explicitly designed for federated scenarios with severe class absence and strong heterogeneity: its deferred re-labeling strategy and calibrated posterior estimation enable selective identification of majority-class samples that resemble absent minorities, avoiding blind re-labeling and delivering robust performance gains where baseline methods struggle most. B.3. Sensitivity analysis (k)

We perform the sensitivity analysis of re-labeling threshold tre on long-tailed CIFAR-10 with IF = 50. On each client, the (k) (k) class-wise threshold tre is determined by the top-τ % of z-scores. The threshold tre controls the re-labeling strength (the amount of re-labeled samples) as demonstrated in Figure 3(a). This serves as a safeguard to regulate the number of samples re-labeled by FedReLa. For instance, using the top 1% z-score as the re-labeling threshold limits the number of re-labeled samples to be less than 1% of local data. Figure 3(a) shows that the amount of re-labeled samples scales linearly with top-τ percentiles. In Figure 3(b), when τ ≤ 5, tail-class performance gains outweigh head-class losses. When τ > 5, medium-class accuracy steadily improves and head-class accuracy continues to decline slowly, while tail-class accuracy remains relatively stable. (k) The effect on performance of turning tre up reveals that: (1) Initially, re-labeled head-class samples with a small τ mostly invade tail-class feature space. (2) After re-labeling these critical samples, further label re-allocating relieves the head-class invasion of the medium-class feature space. (3) FedReLa prioritizes re-labeling samples that most severely invade tail-class regions. We observe similar results on the CIFAR100-LT (Table 10 in the appendix). (a) Average Number of Relabeled Sample per Client

175

Relabeled Samples

150

100

70.0% Accuracy (%)

Noise Count

80.0%

Overall Accuracy Head Classes Medium Classes Tail Classes

125

75

60.0% 50.0%

50

40.0%

25

30.0% 1

3 5 7 9 15 Re-labeling threshold at top-τ %

(b) Performance with varying τ

90.0%

20.0%

20

1

3 5 7 9 15 Re-labeling threshold at top-τ %

20

Figure 3. Sensitive analysis respect to τ , which controls the re-labeling strength.

The threshold-tuning capability allows FedReLa to deliver customized class-wise enhancement, prioritizing tail-class gains (τ = 5) while preserving overall performance. This strategic trade-off (suppressing overprivileged head classes to boost 18

FedReLa: Imbalanced Federated Learning via Re-Labeling

tails) is a unique advantage over static algorithm-level approaches (Li et al., 2023; Xiao et al., 2024), as evidenced by the accuracy curves surpassing the baseline (dashed lines) in critical regions. In practice, we can tune the trade-off through τ depending on how much importance we place on minority-class performance. Recall the conclusion from observations on CIFAR-10-LT: (1) Initially, re-labeled head-class samples with a small proportion τ mostly invade tail-class feature space. (2) After re-labeling these critical samples, further label re-allocating relieves the head-class invasion of the medium-class feature space. (3) FedReLa prioritizes re-labeling samples that most severely invade tail-class regions. We observe similar results on the CIFAR-100-LT dataset, which are presented in Table 10. We anticipate that the optimal parameters will exhibit slight differences across datasets with varying posterior probability distributions and degrees of class overlap. When τ = 3, FedReLa achieves maximum performance gain on CIFAR-100-LT, where the degree of class overlap is more severe. Although the parameter range 1–20% consistently provides performance gain on both CIFAR-10 and CIFAR-100, with the principle of minimizing data-editing, we recommend using slightly conservative relabeling strength (3%–5%). Table 10. Sensitivity analysis on CIFAR-100-LT (IF=50, α = 0.1). Original denotes the FedETF baseline; other columns use FedReLa with top-τ % relabeling. The τ = 5% column matches the +FedReLa entry in Table 2.

top-τ % Overall Many-shot Medium-shot Few-shot Relabeled

Original

1

3

5

7

9

15

20

42.4 63.0 44.7 20.1 0

44.6 62.2 45.5 21.8 51

45.1 57.8 49.2 28.4 157

44.7 56.8 48.6 29.2 194

44.6 57.1 49.8 27.5 216

44.9 56.8 49.4 28.9 276

44.5 56.2 50.7 27.6 317

44.6 56.0 51.1 26.8 364

The threshold-tuning capability enables FedReLa to deliver customized class-wise enhancements, prioritizing tail-class gains while preserving overall performance. This strategic trade-off (suppressing overprivileged head classes to boost tails) is a unique advantage over static algorithm-level approaches (Li et al., 2023; Xiao et al., 2024), as evidenced by the accuracy (k) curves surpassing the baseline (dashed lines) in critical regions. Again, in practice, we can tune the trade-off through tre by τ depending on how much importance we place on minority-class performance. We report the sensitivity of the re-labeling start round Trelabel on long-tailed CIFAR-10/100 (IF=100) in Table 11. Table 11. Sensitivity analysis of the relabeling start round Trelabel on long-tailed CIFAR-10/100 (IF=100). Trelabel is expressed as a fraction of the total training rounds R. Entries report Overall / Head / Med / Tail accuracy (%).

Dataset

Trelabel

α = 1 (O / H / M / T)

α = 10 (O / H / M / T)

CIFAR-10

40%R 60%R 80%R FedETF baseline

75.55 / 90.84 / 73.72 / 65.46 76.52 / 91.04 / 75.02 / 66.76 76.65 / 91.43 / 75.72 / 66.26 74.23 / 93.17 / 74.83 / 59.57

75.31 / 91.72 / 75.78 / 62.65 76.80 / 92.95 / 76.77 / 64.71 76.95 / 92.90 / 77.21 / 64.79 74.80 / 93.67 / 76.03 / 59.72

CIFAR-100

40%R 60%R 80%R FedETF baseline

40.00 / 67.62 / 53.70 / 16.63 43.53 / 64.43 / 49.83 / 28.06 43.84 / 65.13 / 50.12 / 28.12 42.60 / 72.41 / 50.11 / 21.19

40.80 / 65.98 / 56.80 / 15.61 44.01 / 64.32 / 54.40 / 25.11 44.54 / 67.53 / 54.01 / 24.52 42.81 / 71.73 / 51.44 / 19.82

Key observations: • Performance gain over the baseline is relatively insensitive to Trelabel once it reaches 60% of the total training rounds, across different datasets and heterogeneity levels. • Results show clear gains in both overall accuracy and minority (tail-class) accuracy compared to the baseline across all tested scenarios. • We recommend setting Trelabel ≈ 80%R for robust performance across various datasets and heterogeneity levels. 19

FedReLa: Imbalanced Federated Learning via Re-Labeling

C. Ablation study Ablation study on the importance of Z-score standardization Z-score standardization is critical for enabling FedReLa to utilize the underestimated posterior probabilities output by biased models. To validate its necessity, we conducted ablation experiments on CIFAR-10-LT (α = 0.1, IF = 50) without standardization, and directly using posterior probabilities as flip probabilities. Method FedLOGE +FedReLa +FedReLa w/o Z-score

Overall 57.5 70.0 59.7

Many-shot 83.0 76.0 82.1

Medium-shot 61.1 72.7 72.3

Few-shot 19.8 59.4 17.4

Table 12. Performance of FedReLa with/without Z-score Standardization.

Without z-score standardization, the Few-shot performance fails to show improvement. This is attributed to the fact that the posterior probabilities are underestimated by the biased global model for tail classes and are typically extremely small. Directly utilizing them as flipping probabilities hinders the effective conversion of these samples into global minority classes. Meanwhile, the Medium-shot performance exhibits improvement as these classes possess more samples than tail classes, resulting in the model underestimating their posterior probabilities to a lesser extent. Thus, head-class samples with similar features are preferentially flipped to the medium class, rather than to the tail classes with tiny posterior probabilities. Applying z-score standardization to the underestimated posterior probabilities enables a balanced label re-allocating behavior, which achieves a better balanced trade-off among the performance of Head, Medium, and Tail classes. Ultimately, this contributes to the superior Overall accuracy. Ablation study on data-heterogeneity. To evaluate FedReLa’s performance under higher imbalance ratios across varying degrees of data heterogeneity, we increased the imbalance ratio (IR) to 20 and the number of clients to K = 100 on the Fashion-MNIST dataset with 3 minority classes. Results in Table 14 depict consistent performance improvements by FedReLa across different levels of data heterogeneity on the Fashion-MNIST dataset for each algorithm-level method. This highlights the robustness of FedReLa in mitigating the impact of data heterogeneity through enhancements to both data and classifiers. Improved percentage shows that the improvement achieved by FedReLa increases with higher data heterogeneity, indicating that FedReLa-boosted models exhibit significantly improved robustness to heterogeneous data distributions compared to baseline methods. As α decreases (i.e., heterogeneity increases), FedReLa demonstrates progressively greater improvements in both minorityclass accuracy (+8.13% to +35.40%) and overall accuracy (+1.83% to +10.82%), with the most significant gains observed under extreme non-IID scenarios (α = 0.1). While baseline methods exhibit varied sensitivity to heterogeneity, CLIMB shows inherent robustness but limited enhancement headroom, and MOON suffers significant performance drops at α = 0.1. Yet FedReLa consistently mitigates these limitations through adaptive calibration, offering consistent enhancement. Notably, FedReLa reduces minority-class accuracy disparities by 23-37% across α ≤ 1 while maintaining global model stability, particularly excelling in balancing the accuracy trade-off between dominant and rare classes. These results position FedReLa as a versatile solution for real-world federated learning deployments, offering three key advantages: 1) enhanced robustness to severe data heterogeneity without requiring client-specific tuning, 2) compatibility with existing aggregation frameworks, and 3) simultaneous optimization of both class-balanced and global model performance in non-IID environments.

20

FedReLa: Imbalanced Federated Learning via Re-Labeling Table 13. Sensitivity to relabel refresh period on CIFAR-10/100 (overall test accuracy in %). Columns “FedETF” and “+FedReLa (one-shot)” report the baseline and a single end-of-training relabeling pass for reference. Columns “Period 1”–“Period 5” refresh the relabel mapping every 1–5 communication rounds, respectively, and report the best overall accuracy achieved during training.

CIFAR-10, IF=100, α = 0.3 CIFAR-100, IF=50, α = 0.1

FedETF

+FedReLa (one-shot)

Period 1

Period 2

Period 3

Period 4

Period 5

42.88 42.35

46.00 44.71

48.53 45.04

48.78 44.70

49.17 44.48

48.56 44.67

48.92 44.57

One-shot vs. Periodic We compare a single end-of-training relabeling pass (one-shot) with periodically refreshed mappings (Period 1–5), where the relabeling rule is updated every few communication rounds. Periodic refresh incurs a modest additional local computation cost, but Table 13 shows that it can pay off: on CIFAR-10, periodic strategies consistently yield stronger overall gains than one-shot alone, whereas on CIFAR-100 the extra benefit is more limited. One-shot relabeling already improves over the FedETF baseline on both datasets; when the compute budget allows, adopting a periodic refresh schedule is a practical way to push performance further, especially in the CIFAR-10 regime.

FedAvg FedProx FedNova MOON CLIMB FedAvg FedProx FedNova MOON CLIMB FedAvg FedProx FedNova MOON CLIMB FedAvg FedProx FedNova MOON CLIMB FedAvg FedProx FedNova MOON CLIMB

Original (+FedReLa) Performance Improved Percentage (%) Minority Accuracy Overall Accuracy Minority Accuracy Overall Accuracy α = 10 51.70 (81.83) 79.57 (84.56) +30.13 +4.99 51.57 (81.83) 79.35 (84.40) +30.26 +5.05 52.00 (82.27) 79.35 (84.61) +30.27 +5.26 45.77 (81.17) 78.35 (85.60) +35.40 +7.25 55.80 (69.57) 82.39 (86.14) +13.77 +3.75 α=5 45.27 (78.53) 77.80 (84.42) +33.26 +6.62 45.57 (78.03) 77.90 (84.27) +32.46 +6.37 46.10 (78.60) 78.18 (84.30) +32.50 +6.12 45.57 (79.73) 78.21 (85.51) +34.16 +7.30 56.10 (69.53) 82.67 (86.35) +13.43 +3.68 α=1 50.67 (75.57) 79.06 (84.12) +24.90 +5.06 50.10 (74.60) 78.95 (84.25) +24.50 +5.30 50.10 (75.93) 78.91 (84.47) +25.83 +5.56 44.87 (74.97) 77.94 (84.95) +30.10 +7.01 61.17(69.3) 83.78(85.93) +8.13 +2.15 α = 0.3 50.50 (75.70) 78.46 (83.84) +25.20 +5.38 50.00 (74.90) 78.48 (83.63) +24.90 +5.15 55.03 (77.90) 76.67 (84.46) +22.87 +7.79 44.43(74.77) 77.12(84.47) +30.34 +7.35 53.43 (64.70) 81.42 (84.56) +11.27 +3.14 α = 0.1 33.83 (67.60) 68.43 (79.25) +33.77 +10.82 34.40 (68.27) 69.37 (79.35) +33.87 +9.98 70.43 (82.83) 74.25 (82.10) +12.40 +7.85 22.59 (45.82) 67.44 (77.88) +23.23 +10.44 56.97 (65.20) 81.78 (83.61) +8.23 +1.83

Table 14. Ablation study on α. The overall accuracy and average accuracy of minority classes (in %) on step-wise Fashion-MNIST with 3 minority classes (30%) for IR = 20 with 100 clients. The results in brackets show the FedReLa enhanced performance.

21

FedReLa: Imbalanced Federated Learning via Re-Labeling

Symbol

Definition

1. Datasets & Sets D Global dataset (union of all local datasets) D(k) Local dataset of client k e (k) D Re-labeled local dataset of client k (by FedReLa) X Feature space (x ∈ X ⊆ Rd ) Y Label space (Y = {1, 2, ..., C}, C: number of classes) Y (k) Original label set of client k (k) e Y Re-labeled label set of client k (k) (k) Ii Index set of samples in D(k) with the same label as xi 2. Model & Parameters θ Model parameter vector θtglobal Global model parameter at communication round t θ(k) Local model parameter of client k f (θ; x) Global model (maps feature x to posterior probabilities) Trelabel Communication round for FedReLa’s one-shot re-labeling 3. Probability & Distribution πj Global prior probability of class j (πj = Pr(Y = j)) (k) πj Local prior probability of class j on client k [w] πj Weighted aggregated prior of class j (server-side) ηj (x) Global posterior probability of class j given x (k) ηj (x) Local posterior probability of class j given x on client k (k) e (k) ηe (x) Posterior probability of class j on D j [w]

ηej (x) Pj (x) (k) Pj (x)

Aggregated posterior probability of class j (server-side) Class-conditional distribution of X|Y =j Local class-conditional distribution of X|Y =j on client k

4. FedReLa Core Parameters (k) ρℓ→j (x) Re-labeling probability from local majority class ℓ to local minority class j on client k (k) ρj→ℓ (x) Re-labeling probability from class j to ℓ on client k (set to 0) Q(k) Posterior probability matrix of D(k) (|D(k) | × C) (k) (k) zi Class-wise z-score vector of sample xi on client k (k) µi Class-wise mean of posterior probabilities (for z-score) (k) σi Class-wise std of posterior probabilities (for z-score) (k) tre Client-specific re-labeling threshold (tunable via τ ) (k) ϖj Class-wise reweighting vector (from local class priors π (k) ) (k) nY Class-wise sample count vector of D(k) τ Hyperparameter controlling re-labeling strength (top-τ % z-scores) 5. Imbalance & Heterogeneity IR(D) Global imbalance ratio (maxj πj / minj πj ) IF Imbalance factor (for long-tailed datasets) α Heterogeneity control parameter (Latent Dirichlet Sampling) K Number of clients in the federation wk Aggregation weight of client k (FedAvg: wk = |D(k) |/|D|) 6. Decision Boundaries Sj,ℓ Optimal Bayesian decision boundary between classes j and ℓ (k) e e (k) S Decision boundary of client k on re-labeled local dataset D Table 5. Notation Table: Key Symbols and Definitions.

22