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, 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 [1].

Imbalanced or long-tailed distributed data is common in real-world applications [2]–[4] 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 [5], [6], robust local training [7]–[10], selective client participation [11], [12], or architectural enhancements [13], 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 [14] and CLIMB [15] pioneered solutions for global step-wise imbalance and non-IID (not independent and identically distributed) client data. Subsequent studies [16]–[20] further tackled federated long-tailed (Fed-LT) learning.

Existing data-level methods (e.g., SMOTE [21]) 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 [4] or rare disease diagnosis [22], 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.

To fill the gap in data-level FL methods, this paper proposes 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.

Unlike traditional data-level methods, such as SMOTE-based [21], [23] or mixup-based approaches [24], [25], 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:

(i) Model-Data Agnosticism: Unlike methods that rely on balanced auxiliary data or explicit class priors [4], [14], 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 [15], [18], [19] 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 8.1).

(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.

2 Related works↩︎

2.0.0.1 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 [26], [27], SMOTE-based techniques [21], [23], [28], or feature interpolation via mixup [24], [25], [29]. 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.

2.0.0.2 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 [5] and FedNova [6] 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 [9], [10] or constrain inter-round model divergence [7]. SCAFFOLD [8] 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.

2.0.0.3 Data heterogeneity with global class imbalance.

Several methods extend FL to settings with global imbalance, primarily via loss reweighting. Ratio-Loss [14] estimates global class priors using auxiliary balanced data, while CLIMB [15] 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 long-tailed distributions. CReFF [18] boosts tail-class performance via aggregated class feature retraining but incurs extra training and doubled communication costs, while FedROD [16] decouples global and local objectives yet may yield suboptimal global models when aggressively balancing local losses. FedETF [17] enforces balanced feature learning via a fixed ETF (Equiangular Tight Frame) classifier head.

Based on the observation that head classes tend to have larger weight norms, FedGraB [20] rescales the gradients of local models by class weight norms to enhance tail-class performance. As a follow-up, FedLOGE [19] further integrates the idea of [17] 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.

2.0.0.4 Other label-related concepts.

FedReLa is related to, but distinct from, learning with noisy labels [30]–[32] and label propagation [33], [34]. 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.

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 [35], addresses heterogeneity using mixup. Still, it requires clients to share local data averages, which may require additional privacy-preserving 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.

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.1 Problem Formulation↩︎

Consider a dataset \(\mathcal{D}\) that contains data pairs \((X,Y) \sim P(x,y)\), where \(x \in \mathcal{X} \subseteq \mathbb{R}^d\), \(y \in \mathcal{Y} = \{1, 2, \ldots, C\}\) and \(P\) represents the joint distribution. Denote the conditional distribution \(X \mid Y = j \sim P_j(x)\) and the prior probability \(\Pr(Y=j)=\pi_j\) for class \(j \in \mathcal{Y}\). The marginal distribution of \(X\) is then \(P_X(x) = \sum_{j\in\mathcal{Y}} \pi_jP_j(x)\). Assume \(\mathcal{D}\) is imbalanced with global imbalance ratio \(\mathrm{IR}(\mathcal{D}) = \max_{j\in\mathcal{Y}}\pi_j/\min_{j\in\mathcal{Y}}\pi_j \gg 1\). Let \(\eta_j(x) = \Pr(Y=j\mid X=x) = \pi_jP_j(x)/P_X(x)\) be the global posterior probability. Recalling that the Bayesian decision theorem [36] defines the optimal estimated \(y^*\) of a sample \(x\) as \(y^* = \mathrm{argmax}_{j\in\mathcal{Y}} \eta_j(x)\), the following result holds.

For \(x\in S_{j,\ell}\), \(\eta_j(x) = \eta_{\ell}(x)\) implies \(P_j(x)/P_{\ell}(x)= \pi_{\ell}/\pi_j\). Then for minority class \(j\) and majority class \(\ell\) with \(\pi_j \ll \pi_{\ell}\), \(S_{j,\ell}\) intrudes deeply into the minority class region, increasing the risk of misclassifying minority class samples. This motivates balancing the ratio \(\pi_{\ell}/\pi_j\) to shift the decision boundary back towards the majority class region, thereby alleviating the adverse effects of class imbalance.

In FL, the dataset \(\mathcal{D}\) is distributed on \(K\) clients with local datasets \(\{\mathcal{D}^{(k)}\}_{k=1}^{K}\) and assumes the class conditional distributions \(\{P_{j}^{(k)}(x)\}_{k=1}^{K}\) are identical across all clients for each class \(j\). In contrast, the class priors \(\{\pi_{j}^{(k)}\}_{k=1}^{K}\) may be different among clients due to data heterogeneity. For classes \(j\) and \(\ell\), we have \(P_{j}^{(1)}(x)/P_{\ell}^{(1)}(x) = \cdots = P_{j}^{(K)}(x)/P_{\ell}^{(K)}(x)=P_j(x)/P_{\ell}(x)\). However, divergent class priors result in different local posterior probability \(\eta_{j}^{(k)}(x)=\pi_{j}^{(k)}P_{j}(x)/\sum_{j_0\in\mathcal{Y}}\pi_{j_0}^{(k)}P_{j_0}(x)\) and misaligned Bayesian decision boundaries among clients. This misalignment affects performance of aggregated classifier and slows down convergence of FL algorithms [1].

Ideally, with properly chosen aggregation weights \(\{w_k\}_{k=1}^{K}\), the decision boundary between classes \(j\) and \(\ell\) of the global aggregated model \(\eta_{j}^{[w]}(x)=\sum_{k=1}^{K}w_k\eta_{j}^{(k)}(x)\) given by \[S_{j,\ell}^{[w]} = \{x\in \mathcal{X}: P_j(x)/P_{\ell}(x)=\pi_{\ell}^{[w]}/\pi_j^{[w]}\},\] which can match \(S_{j,\ell}\) in Lemma 1 by making \(\pi_j^{[w]} = \pi_j\) and \(\pi_{\ell}^{[w]} = \pi_{\ell}\), where \(\pi_j^{[w]} = \sum^K_{k=1} w_k\pi_{j}^{(k)}/\sum^K_{k=1} w_k\) and \(\pi_{\ell}^{[w]} = \sum^K_{k=1} w_k\pi_{\ell}^{(k)}/\sum^K_{k=1} w_k\). For instance, setting \(w_k = |\mathcal{D}^{(k)}|/|\mathcal{D}|\) achieves this alignment. However, the global imbalance ratio \(\pi_{\ell}/\pi_j\) still introduces bias into the aggregated decision boundary of the global model. To address that, several algorithms [37], [38] have been proposed to adjust the ratio \(\pi_{\ell}^{[w]}/\pi_j^{[w]}\) via 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.

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 re-labeling 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 \(\ell\) represent the minority and majority classes.

Let \((X^{(k)},Y^{(k)}) \sim P^{(k)}(x,y)\) denote the data pair for client \(k\) with re-labeled \(\widetilde{Y}^{(k)}\) and consider \(\widetilde{\mathcal{D}}^{(k)}\) the corresponding re-labeled dataset. Denote the probabilities of re-labeling \(\ell\) to \(j\) as \(\rho_{\ell\to j}^{(k)}(x) = \Pr(\widetilde{Y}^{(k)} = j \mid X^{(k)} = x, Y^{(k)} = \ell)\) and re-labeling \(j\) to \(\ell\) as \(\rho_{j\to\ell}^{(k)}(x) = \Pr(\widetilde{Y}^{(k)} = \ell \mid X^{(k)} = x, Y^{(k)} = j)\) for client \(k\), then \[\begin{align} \notag \widetilde{\eta}_{j}^{(k)}(x) & = \Pr(\widetilde{Y}^{(k)} = j \mid X^{(k)} = x)\\ &\notag = \eta_{j}^{(k)}(x)[1 - \rho_{j\to\ell}^{(k)}(x)] + [1-\eta_{j}^{(k)}(x)]\rho_{\ell\to j}^{(k)}(x). \end{align}\]

When \(\pi_{\ell}^{(k)}/\pi_{j}^{(k)} \gg 1\), we seek to achieve \([1-2\rho_{\ell\to j}^{(k)}(x^*)]/[1-2\rho_{j\to\ell}^{(k)}(x^*)]<1\) to locally adjust the decision boundary. Given the scarcity of minority class samples in \(\mathcal{D}^{(k)}\), it is reasonable to restrict re-labeling to occur only from majority class \(\ell\) to minority class \(j\), and set \(\rho_{j\to\ell}^{(k)}(x)=0\). Furthermore, since deeply invaded majority class samples are especially harmful, we design a label re-allocator where the re-labeling probability is proportional to the degree of intrusion. Specifically, with \(\rho_{\ell\to j}^{(k)}(x)\propto \eta_{j}^{(k)}(x)\), the Bayesian decision boundary is
\(\widetilde{S}^{(k)} = \left\{x^{*} \in \mathcal{X}: \frac{P_j(x^*)}{P_{\ell}(x^*)} =[1-2\rho_{\ell\to j}^{(k)}(x^*)] \frac{\pi_{\ell}^{(k)}}{\pi_{j}^{(k)}}\right\}\).

Since \(1-2\rho_{\ell\to j}^{(k)}(x^*) < 1\), \(\widetilde{S}^{(k)}\) on re-labeled data shifts back to the majority class region. Based on re-labeled data \(\widetilde{\mathcal{D}}=\cup_{k=1}^{K}\widetilde{\mathcal{D}}^{(k)}\), we also study the decision boundary of the global aggregated model \(\widetilde{\eta}_{j}^{[w]}(x)=\sum_{k=1}^{K}w_k\widetilde{\eta}_{j}^{(k)}(x)\).

Lemma 3 implies that the label re-allocator balances the global imbalance ratio when \[\label{eq:global95noise95condition} \frac{\sum_{k=1}^{K}w_k\pi_{\ell}^{(k)}[1-2\rho_{\ell\to j}^{(k)}(x)]/\pi_{\ell}}{\sum_{k=1}^{K}w_k\pi_{j}^{(k)}/\pi_j} < 1.\tag{1}\] By choosing \(w_k=|\mathcal{D}^{(k)}|/|\mathcal{D}|\), \(\sum_{k=1}^{K}w_k\pi_{j}^{(k)}/\pi_j=1\), and (1 ) reduces to \(\sum_{k=1}^{K}w_k\pi_{\ell}^{(k)}[1-2\rho_{\ell\to j}^{(k)}(x)]/\pi_{\ell}<1\), which holds naturally when \(\rho_{\ell\to j}^{(k)}(x)>0\) for all \(k\in\{1,\ldots,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.

4 Framework of FedReLa↩︎

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 model-agnostic approach, which is designed as a plug-in module that can be seamlessly integrated into any FL algorithm.

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 in parallel. Specifically, before client \(k\) starts to train the global model \(f(\theta;x)\) with parameter \(\theta=\theta^{\rm global}_{t}\) received at round \(t=T_{\text{relabel}}\), FedReLa re-labels its local dataset \(\mathcal{D}^{(k)}=\{(x_{i}^{(k)}, y_{i}^{(k)})\}_{i=1}^{n_k}\) using a client-specific label re-allocator \(\rho^{(k)}\), resulting in the re-labeled dataset \(\widetilde{\mathcal{D}}^{(k)}=\{(x_{i}^{(k)}, \widetilde{y}_{i}^{(k)})\}_{i=1}^{n_k}=\rho^{(k)}(\mathcal{D}^{(k)})\). Note that the computation of FedReLa only occurs in \(T_{\text{relabel}}\), and the re-labeled local dataset \(\widetilde{\mathcal{D}}^{(k)}\) can be reused in subsequent training rounds \(t > T_{\text{relabel}}\). Thus, the one-shot computations at round \(T_{\text{relabel}}\) for label re-allocators are lightweight and almost negligible to the whole training process. We discuss the computational cost of FedReLa in Appendix 8.1. Each client then updates the global model locally using \(\widetilde{\mathcal{D}}^{(k)}\), and the server aggregates the local updates \(\Delta \theta^{(k)}_{t}\) to produce the updated global model with parameter \(\theta^{\rm global}_{t+1}\).

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 \(|\mathcal{D}^{(k)}|\times|\mathcal{Y}|\) posterior probability matrix \(\mathbf{Q}^{(k)}\) for client \(k\), where \[Q_i^{(k)} = f(\theta^{\rm global}_{t};x_{i}^{(k)})\in \mathbb{R}^{|\mathcal{Y}|}\] is the \(i\)-th row of \(\mathbf{Q}^{(k)}\), denoting the posterior probability vector of the \(i\)-th local instance \(x_{i}^{(k)}\).

Crucially, the global model implicitly integrates cross-client discriminative knowledge across all classes \(\mathcal{Y} = \{1, 2, \dots, 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 non-negligible 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 \[\mathcal{I}_{i}^{(k)}=\{i_0\in\{1,\ldots,n_k\}: y_{i_0}^{(k)}=y_{i}^{(k)}\}\] denote the index set of samples in \(\mathcal{D}^{(k)}\) that share the same label as the \(i\)-th instance. The class-wise mean and standard deviation vectors are computed as \[\begin{align} \mu_{i}^{(k)} &= \frac{1}{|\mathcal{I}_{i}^{(k)}|}\sum_{i_0\in\mathcal{I}_{i}^{(k)}}Q_{i_0}^{(k)}, \\ \sigma_{i}^{(k)} &= \sqrt{\frac{1}{|\mathcal{I}_{i}^{(k)}|-1}\sum_{i_0\in\mathcal{I}_{i}^{(k)}}\left(Q_{i_0}^{(k)}-\mu_{i}^{(k)}\right)^2}, \end{align}\] where \(\mu_i^{(k)} \in \mathbb{R}^{|\mathcal{Y}|}\) and \(\sigma_i^{(k)} \in \mathbb{R}^{|\mathcal{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 \[\mathrm{z}_i^{(k)} = \frac{Q_{i}^{(k)} - \mu_{i}^{(k)}}{\sigma_{i}^{(k)}}. \label{eq:muste}\tag{2}\] As illustrated in Figure 1, the resulting \(z\)-score matrix \(\mathbf{Z}^{(k)}\), with \(i\)-th row \(\mathrm{z}_{i}^{(k)}\), recalibrates \(\mathbf{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: (1) a client-specific threshold \(t_{\rm re}^{(k)}\), which is a tunable hyperparameter that determines the desired re-labeling strength by filtering out samples with weak feature similarity; and (2) a class-wise reweighting vector \(\varpi_j^{(k)}\in \mathbb{R}^{|\mathcal{Y}|}\), computed from local class priors to re-label samples asymmetrically. Specifically, \(\varpi_{j}^{(k)}\) reweighs the re-labeling probability from class \(j\) to any other class \(c \in \mathcal{Y} \setminus \{j\}\) with their class prior difference between \(j\) and \(c\).

Let \(n_{\mathcal{Y}}^{(k)}\in\mathbb{R}^{|\mathcal{Y}|}\) denote the vector of class-wise sample counts in the local dataset \(\mathcal{D}^{(k)}\). We first apply min-max normalization on \(n_{\mathcal{Y}}^{(k)}\) to construct the class-wise reweighting vector \(\varpi^{(k)}= 1 - \texttt{minmax}(n^{(k)}_{\mathcal{Y}})\), defined as: \[\begin{align} \varpi^{(k)}_{j} = \max(\varpi^{(k)} - \varpi^{(k)}[j],0) \label{eq:theta} \end{align}\tag{3}\] For samples belonging to a local tail class \(y_{\text{tail}}\), we have \(\varpi^{(k)}[y_{\text{tail}}] = 1\), which implies that \(\varpi^{(k)}_{y_{\text{tail}}} = 0\). It zeros the re-labeling probabilities from the minority class to other classes, thereby preserving the integrity of minority-class samples.

Let \(\mathbf{Z}^{(k)} \in \mathbb{R}^{N \times C}\) denote the matrix of local \(z\)-scores on client \(k\), where \(\mathbf{Z}_{:,j}^{(k)}\) is its \(j\)-th column collecting class-\(j\) scores over all \(N\) local samples. We use a client-specific, class-wise threshold vector \(\mathbf{t}_{\mathrm{re}}^{(k)} \in \mathbb{R}^{C}\), controlled by the hyperparameter \(\tau \in [0,1]\). For each class \(j\), the threshold is set to the \((1-\tau)\)-quantile of the corresponding local \(z\)-scores: \[t_{\mathrm{re},j}^{(k)} = \mathrm{Quantile}_{1-\tau}\!\left(\mathbf{Z}_{:,j}^{(k)}\right), \quad j = 1, \ldots, C. \label{eq:tre95quantile}\tag{4}\] With this threshold, the re-labeling probability for the \(i\)-th instance on client \(k\) is defined as \[\rho^{(k)}\!\left(x_i^{(k)}\right) = \max\!\left( \tanh\!\left(z_i^{(k)} - t_{\mathrm{re}}^{(k)}\right) \odot \varpi^{(k)}_{y_i},\, 0 \right), \label{eq:fliprate}\tag{5}\] where \(\mathbf{z}_i^{(k)} \in \mathbb{R}^{C}\) is the local \(z\)-score vector of sample \(x_i^{(k)}\), \(\odot\) denotes element-wise multiplication, and \(\boldsymbol{\varpi}^{(k)}_{y_i}\) is the class-prior weight associated with the observed label \(y_i\). Intuitively, \(\mathbf{t}_{\mathrm{re}}^{(k)}\) acts as a tunable, class-wise filter: samples whose \(z\)-scores are insufficiently large relative to the class-specific threshold receive negative values after the \(\tanh(\cdot)\) mapping and are truncated to zero, suppressing re-labeling for instances with weak minority-class similarity. We provide a sensitivity analysis of \(t_{\mathrm{re}}^{(k)}\) in Appendix 8.3.

Based on the local label re-allocator \(\rho^{(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 [alg:2].

4.0.0.1 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 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.

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 re-labeled 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 3, 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.

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 9 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.

5 Experiments↩︎

Datasets: To provide a comprehensive evaluation, we conduct experiments under both step-wise and long-tailed global imbalance settings on Fashion-MNIST (F-MNIST) [39], CIFAR-10/100 [40], and ImageNet-LT (long-tailed) [41] 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 [42]. To simulate cross-client heterogeneity, we employ latent Dirichlet sampling [43] 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\in\{10,50,100\}\) clients in the long-tailed setting and 10 in the step-wise setting. The heterogeneity level is controlled by the parameter \(\alpha \in \{0.1, 0.3,10\}\). We set the client sample rate to 1.

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 [5], FedProx [10], FedNova [6], MOON [9], and CLIMB [15]. For long-tailed imbalance, we compare with FedETF [17] and the latest SOTA method, FedLOGE [19], and FedYoYo [44]. 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 re-labeled data by FedReLa. All methods are trained with sufficient communication rounds to converge. Please refer to Appendix 8 for the communication rounds needed to achieve the convergence of each method.

5.0.0.1 Evaluation Metrics.

All results are evaluated on class-balanced 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 8.0.0.2). Results in Table 1 and 2 are averaged over three runs with different random seeds.

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 \(\alpha=0.3\) (see Appendix 9 for ablation analysis on \(\alpha\)). On Fashion-MNIST and CIFAR-10, FedReLa achieves 6.40%–32.20% minority-class accuracy improvement and 0.81%–4.76% overall accuracy gain under \({\rm IR}=10\). At \({\rm 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\in[10,20]\) (See Table 6).

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, \(\alpha=0.1\)), FedReLa 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.

Large-Scale Dataset Validation on ImageNet-LT: We conduct experiments on ImageNet-LT with data heterogeneity level \(\alpha=0.1\), 20 clients, and 0.4 participation fraction. Another recent SOTA method, FedYoYo [44], is used to demonstrate the algorithmic agnosticism of FedReLa. 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.

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.

5.0.0.2 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. Min-max normalization linearly scales posteriors and is max-value-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). More detailed ablation studies can be found in Appendix 9 for (i) the importance of Z-score standardization, (ii) different data-heterogeneity levels, and (iii) comparing one-shot with multi-shot relabeling.

5.0.0.3 Sensitivity analysis on \(T_{\mathrm{relabel}}\).

We study how this hyperparameter affects performance on long-tailed CIFAR-10 and CIFAR-100 with IF=100 under two heterogeneity levels (\(\alpha=1\) and \(\alpha=10\)); full results are reported in Table 11 (Appendix 8.3). Across both datasets and heterogeneity settings, FedReLa consistently outperforms the FedETF baseline in overall accuracy and, more importantly, in tail-class accuracy, which is the primary objective under class imbalance. Once \(T_{\mathrm{relabel}}\) reaches 60% of the total training rounds, further delaying re-labeling yields only marginal changes, indicating that performance is relatively insensitive to \(T_{\mathrm{relabel}}\) beyond this point. Among the choices examined, \(T_{\mathrm{relabel}}=80\%R\) achieves the strongest overall and tail-class results in most scenarios. We therefore adopt \(T_{\mathrm{relabel}}\approx 80\%R\) as the default in our main experiments for robust performance across datasets and heterogeneity levels.

6 Conclusion↩︎

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 real-world imbalanced federated learning.

Impact Statement↩︎

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.

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).

7 Technical Details and Proofs↩︎

7.0.0.1 Explanation on Aggregated Model Representation

To analyze how re-labeling influences the global decision boundary, we adopt the global model defined via posterior aggregation (i.e., \(\sum_{k=1}^{K} w_k f(x, \theta^{(k)})\), where \(f(x, \theta^{(k)})\) denotes the local posterior of client \(k\) with parameter \(\theta^{(k)}\)) instead of parameter aggregation (i.e., \(f\left(x, \sum_{k=1}^{K} w_k \theta^{(k)}\right)\)). This choice is 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 \(w_k\), 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 \(\theta^{(k)}\) are sufficiently close to a common reference value \(\theta_0\) (a reasonable condition in late-stage FL training when models converge). Expanding both models around \(\theta_0\):

1. For the parameter-aggregated global model: \[\begin{align} f\left(x, \sum_{k=1}^{K} w_k \theta^{(k)}\right) &\approx f(x,\theta_0) + \left.\frac{\partial f(x,\theta)}{\partial\theta}\right|_{\theta=\theta_0} \sum_{k=1}^{K} w_k (\theta^{(k)} - \theta_0) \\ &= f(x,\theta_0) + \sum_{k=1}^{K} w_k \left.\frac{\partial f(x,\theta)}{\partial\theta}\right|_{\theta=\theta_0} (\theta^{(k)} - \theta_0) \end{align}\]

2. For the posterior-aggregated global model (noting \(\sum_{k=1}^{K} w_k = 1\)): \[\begin{align} \sum_{k=1}^{K} w_k f(x, \theta^{(k)}) &\approx f(x,\theta_0) + \left.\frac{\partial f(x,\theta)}{\partial\theta}\right|_{\theta=\theta_0} \left(\sum_{k=1}^{K} w_k \theta^{(k)} - \theta_0\right) \\ &= f(x,\theta_0) + \sum_{k=1}^{K} w_k \left.\frac{\partial f(x,\theta)}{\partial\theta}\right|_{\theta=\theta_0} (\theta^{(k)} - \theta_0) \end{align}\]

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.

7.1 Proof of Lemma 2↩︎

7.2 Proof of Lemma 3↩︎

8 Additional Experiment Details↩︎

The code is available at: https://github.com/guangzhengh/FedReLa.git.

8.0.0.1 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.

8.0.0.2 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 [19], 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.

8.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:

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."

8.1.0.1 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 \[\begin{align} &\mathrm{FLOP}_{\text{train}} = \mathrm{FLOP}_{\text{forward}} +\mathrm{FLOP}_{\text{backpropagation}},\\ &\mathrm{FLOP}_{\text{backpropagation}} \approx 2 \times \mathrm{FLOP}_{\text{forward}}. \end{align}\] Thus, the FLOPs required for \(Q^{(k)} = f(\theta^{\text{global}}_{T_{\text{relabel}}}; X^{(k)})\) can be approximately quantified with: \[\begin{align} \mathrm{FLOP}_{Q^{(k)}} = \mathrm{FLOP}_{\text{forward}} \approx \frac{1}{3} \mathrm{FLOP}_{\text{train}}. \end{align}\] 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 \(T_{\text{relabel}}\). 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.

8.1.0.2 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.

8.2 Additional experiment results↩︎

8.2.0.1 Additional experiment on step-wise setting with recent SOTAs.

Although recent methods, such as FedETF [17] and FedLOGE [19], 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.

8.2.0.2 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 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.

8.2.0.3 Large number of clients on CIFAR100-LT

We extend CIFAR100-LT experiments to 50 and 100 clients, with an imbalance factor \(imb\_factor=100\) and data heterogeneity \(\alpha=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.

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.

8.2.0.4 Tail-Class Accuracy Gain on CIFAR10-LT Under Extreme Heterogeneity

Under \(\alpha=0.1\),  70% of tail classes are absent from clients, simulating extreme real-world heterogeneity.

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.

8.3 Sensitivity analysis↩︎

We perform the sensitivity analysis of re-labeling threshold \(t_{\rm re}^{(k)}\) on long-tailed CIFAR-10 with \(\rm IF = 50\). On each client, the class-wise threshold \(t_{\rm re}^{(k)}\) is determined by the top-\(\tau_{\rm}\) % of z-scores. The threshold \(t_{\rm re}^{(k)}\) controls the re-labeling strength (the amount of re-labeled samples) as demonstrated in Figure 4 (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 4 (a) shows that the amount of re-labeled samples scales linearly with top-\(\tau\) percentiles.

In Figure 4 (b), when \(\tau \leq 5\), tail-class performance gains outweigh head-class losses. When \(\tau> 5\), medium-class accuracy steadily improves and head-class accuracy continues to decline slowly, while tail-class accuracy remains relatively stable. The effect on performance of turning \(t_{\rm re}^{(k)}\) up reveals that: (1) Initially, re-labeled head-class samples with a small \(\tau\) 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).

The threshold-tuning capability allows FedReLa to deliver customized class-wise enhancement, prioritizing tail-class gains (\(\tau = 5\)) while preserving overall performance. This strategic trade-off (suppressing overprivileged head classes to boost tails) is a unique advantage over static algorithm-level approaches [17], [19], as evidenced by the accuracy curves surpassing the baseline (dashed lines) in critical regions. In practice, we can tune the trade-off through \(\tau\) 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 \(\tau\) 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 \(\tau = 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%).

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 [17], [19], as evidenced by the accuracy curves surpassing the baseline (dashed lines) in critical regions. Again, in practice, we can tune the trade-off through \(t_{\rm re}^{(k)}\) by \(\tau\) depending on how much importance we place on minority-class performance.

We report the sensitivity of the re-labeling start round \(T_{\mathrm{relabel}}\) on long-tailed CIFAR-10/100 (IF=100) in Table 11.

Key observations:

• Performance gain over the baseline is relatively insensitive to \(T_{\mathrm{relabel}}\) 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 \(T_{\mathrm{relabel}} \approx 80\%R\) for robust performance across various datasets and heterogeneity levels.

9 Ablation study↩︎

9.0.0.1 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 (\(\alpha=0.1\), \(\mathrm{IF}=50\)) without standardization, and directly using posterior probabilities as flip probabilities.

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.

9.0.0.2 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 \(\alpha\) decreases (i.e., heterogeneity increases), FedReLa demonstrates progressively greater improvements in both minority-class 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 (\(\alpha=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 \(\alpha=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 \(\alpha\leq 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.

9.0.0.3 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.

References↩︎