AFed: Algorithmic Fair Federated Learning

At a high level, algorithmic fairness notions adopted in centralized machine learning can be categorized as two different families: the statistical notion and individual notion [6]. The statistical notions require specific statistical measures to be comparable across all of these groups [22, 5]. The individual notions aim at fairness between specific pairs of individuals: Give similar predictions to similar individuals [13]. Individual notions offer a meaningful fairness guarantee but need to make significant assumptions, some of which present non-trivial challenges in fairness. We adopt statistical notions, more specifically, demographic parity [18] as fairness metric in this paper.

Debiasing methods can be classified as pre-processing, in-processing, and post-processing, respectively [11]. Pre-processing improves fairness by eliminating bias present in the training dataset. The model is subsequently trained and applied on the modified data [15, 21]. For instance, Kamiran et al. [21] propose reweighting samples in the training dataset to correct for biased treatment. Xu et al. [37] proposed FairGAN, which generates fair data from the original training data and uses the generated data to train the model. In-processing achieves fairness by adding constraints during training. Berk et al. [3] integrated a family of fairness regularizers into the objective function for regression issues. Zhang et al. [42] borrowed the ideal of adversarial training to restrict a model’s bias. The general methodology of post-processing methods is to adjust the decision thresholds of different groups following specific fairness standards [5, 18, 4]. However, existing methods assume centralized access to the data, which is invalid in FL. Each client can only access its own data, and the server does not know the local data distribution. As such, it remains challenging to train a fair model in FL.

Fairness can be defined from different aspects in FL. A body of work focuses on accuracy disparity, i.e., trying to minimize the performance gaps between different clients [24]. A model with a more uniform performance distribution is considered fairer. The goal, in this case, is to address any statistical heterogeneity during the training phase by using techniques like data augmentation [50], client selection [38] and reweighting [19], multi-task learning [35], etc. Another area of focus is good-intent fairness [31], ensuring that the training procedure does not overfit a model to any client at the expense of others. In this instance, the objective is to train a robust model against an unknown testing distribution.

However, these two lines of work don’t address the algorithmic fairness issues in FL. To date, there are limited works about algorithmic fairness in FL. Du et al. [12] formulated a distributed optimization problem with fairness constraints. Gálvez et al. [16] cast fairness as a constraint to an optimization problem. To protect privacy, the constraint problem is optimized based on statistics provided by clients. Chu et al. [8] and Cui et al. [10] took a similar path, imposing fairness constraints on the learning problem. To avoid intruding on the data privacy of any client, the fairness violations are locally calculated by each client. Zhang et al. [43] focused on client selection, using a team Markov game to select clients to ensure fairness. Ezzeldin et al. [14] proposed a fairness-aware aggregation method that amplifies local debiasing by weighting clients whose fairness metric aligns well with the global one. Wang et al. [36] explore the relationship between local group fairness and propose a regularized objective for achieving global fairness. Zeng et al. [41] extend FairBatch [33], a fair training method in centralized machine learning, to FL. In their design, each client shares extra information about the unfairness of its local classifier with the server. Chu et al. [7] propose estimating global fairness violations by aggregating the fairness assessments made locally by each client. They then constrain the model training process based on the global fairness violation.

Currently, most FL research focuses on accuracy disparity, which is more closely related to data heterogeneity rather than the potentially unfair decisions the model may make. Comparatively, less research has been conducted regarding algorithmic fairness in FL. The difficulty of ensuring algorithmic fair FL stems from the privacy restriction of FL, i.e., the data never leaves the device. In the presence of client-specific data heterogeneity, however, local debiasing may fail to provide acceptable performance for the entire population. Existing works have attempted to circumvent this restriction by providing server statistics or calculating fairness constraints locally. However, they fail to adequately address the non-i.i.d. challenge in FL. For example, in the presence of non-i.i.d. data, the estimated global fairness violation in [7] could be inaccurate. Our approach distinguishes itself from existing methods in two key ways: 1) Alternative methodology: We explore a different direction by leveraging local data augmentation to enhance debiasing efforts; 2) Enhanced practicality: We address the non-i.i.d. challenges inherent in FL when training fair models. Our local data augmentation technique effectively mitigates these non-i.i.d. issues.

This research focuses on addressing fairness issues in the context of binary classification tasks to illustrate our method. Note that our methods can be extended to the general multi-class classification problem since we didn’t explicitly require the target label to be binary. Denote $\mathcal{X}\in\mathbb{R}^{m}$ as the input space. $\mathcal{Z}\in\mathbb{R}^{p}$ is the latent feature space with $p<m$. $\mathcal{Y}=\left\{0,1\right\}$ is the output space, and $\mathcal{A}=\left\{0,1\right\}$ is the set of all possible sensitive attribute values. The classification model $f$ parameterized by $\boldsymbol{\theta}^{f}\coloneqq\boldsymbol{\theta}^{E}\circ\boldsymbol{\theta}^{y}$ consists of two parts: a feature extractor $E:\mathcal{X}\mapsto\mathcal{Z}$ and a classification head $h^{y}:\mathcal{Z}\mapsto\Delta^{\mathcal{Y}}$, where $\Delta^{\mathcal{Y}}$ stands for the probability simplex over $\mathcal{Y}$. In addition, we train another classification head $h^{a}:\mathcal{Z}\mapsto\Delta^{\mathcal{A}}$ parameterized by $\boldsymbol{\theta}^{a}$ to classify sensitive attribute $a$. In AFed-G, a conditional generator $G$ parameterized by $\boldsymbol{w}^{G}$ is trained at the server side to synthesize fake representations condition on $a$: $\mathcal{A}\mapsto\mathcal{Z}$. In AFed-GAN, we replace $G$ with conditional GAN parameterized by $\boldsymbol{w}\coloneqq\boldsymbol{w}^{G}\circ\boldsymbol{w}^{D}$. The discriminator $D:\boldsymbol{z}\times a\mapsto\left[0,1\right]$ is trained to distinguish fake samples from real ones.

A FL system comprises $N$ local clients and a central server. Each client possesses a specific dataset $\mathcal{D}^{k}$, $k\in\left\{1,2,...,N\right\}$ and the $i$-th data sample is represented as $\xi_{i}\coloneqq\left\{\boldsymbol{x}_{i},y_{i},a_{i}\right\}$, where $\boldsymbol{x}_{i}$ is the features, $y_{i}$ is the ground-true label, and $a_{i}$ is the sensitive attribute. The amount of data of the $k$-th client is denoted as $n_{k}$. The goal of FL is to minimize the empirical risk over the samples of all clients, i.e.,

where $\ell_{k}$ is the loss objective of the $k$-th client. Unlike central machine learning, which assumes centralized access to all train data $\mathcal{D}=\cup_{k\in N}\mathcal{D}_{k}$, the client’s training data is never exposed to the server. Only gradients/model parameters are transmitted to the server for aggregation.

At the $t$-th training round, the server randomly selects a set of clients $\mathcal{S}$ to train the current global model $\boldsymbol{w}^{t}$. Selected clients first receive $\boldsymbol{w}^{t}$ from the server, then train it on their local dataset $\mathcal{D}^{k},k\in\mathcal{S}$,

where $\eta$ denotes the learning rate and $\mathcal{B}_{t}^{k}$ is a mini-batch of training data sampled from $\mathcal{D}_{k}$ in the $t$-th iteration. The local training process could run for multiple rounds. After that, the trained model $\boldsymbol{\theta}_{k}^{t}$ or equivalently gradients $\Delta\boldsymbol{\theta}\coloneqq\boldsymbol{\theta}_{k}^{t+1}-\boldsymbol{\theta}^{t}$ is send back to the server for aggregation,

where $\omega_{k}=n_{k}/{\sum_{k\in\mathcal{S}}n_{k}}$ is the aggregation weight. $\boldsymbol{\theta}^{t+1}$ is used as the initial model for the next training round. This interaction between clients and the server is repeated until a certain criterion (e.g., accuracy) is satisfied.

Fairness in FL can be defined in different ways. This paper focuses on algorithmic fairness, especially group fairness, which is measured by the disparities in the algorithm decisions made for different groups determined by sensitive attributes, such as gender, race, etc. Here, we have opted for demographic parity as the fairness metric in this paper.

The task of fair supervised learning is to train a classification model $f$ that can accurately label samples while minimizing discrimination. The discrimination level in terms of demographic parity can be measured by the absolute difference in the model’s outcomes between groups

The smaller $\Delta\textrm{DP}(f)$ is, the fairer $f$ will be. $\Delta\textrm{DP}(f)=0$ iif $f(x)\perp A$, i.e., demographic parity is achieved.

GAN was first proposed by [17] as a min-max game between the generator $G$ and discriminator $D$. The aim is to approximate a target data distribution so that the generated data can’t be separated from the true data by $D$. The objective function of the generator is formed as

where $p(x)$ is the real data distribution.

There exist various kinds of generators to generate synthetic data for different purposes. Among these, we chose conditional GAN [30] to generate synthetic data conditional on the given input. The conditional GAN differs from the unconditional GAN by providing the generator and discriminator condition information. The learning objective of conditional GAN is formulated as follows:

The additional information $a$ is fed to the generator and the discriminator during training. After convergence, the generator can generate fake data conditional on $a$.

The non-i.i.d. nature of local data distributions in a typical FL system presents a significant challenge for local debiasing. Certain groups may dominate a client’s data, while others may have limited representation. To illustrate this challenge, we create a toy FL system with four clients, each with a unique local dataset having different distributions. We generated the data from a mixture of four Gaussian distributions and grouped them based on the attribute $a$ into two categories. In this example, 85% of a client’s data is sampled from one Gaussian distribution, while the remaining 15% is evenly distributed across the other three Gaussian distributions.

In this situation, local debiasing is futile because none of the clients completely understand the data distribution across all clients. For example, client 1 has very few samples from group 1 (i.e., $a=1$), as shown in Fig. 1(a). Even less is the proportion when all clients’ data is considered. Therefore, it is difficult for client 1 to debias the classification model, given that client 1 has almost no knowledge of group 1. The same issue arises with the other clients. Our theoretical analysis in Section V confirms this. The performance of the local model on the global distribution depends on the quantity and similarity of the data, making it challenging to achieve a fair FL model through local debiasing alone.

To address this problem, in AFed, a conditional generator/GAN is trained collectively by all clients to extract knowledge about the local data distribution. The result is illustrated in Fig. 2. It can be seen that the generated data has a similar distribution to that of all client data, indicating that the generator was successful in extracting the knowledge about the local data distribution. The extracted knowledge can be shared with all clients to help local debiasing. With the generated sample, clients can access the global data distribution and achieve a more accurate debiasing outcome. Fig. 3 illustrates the approach.

This section details the proposed AFed framework, summarized in Algorithm 1. Fig.3 shows the general description of AFed, which involves two learning tasks. As shown on the left part of Fig.3, the first task is to extract knowledge about local distribution. To this end, we train a conditional generator/GAN to learn clients’ local data distribution. We then aggregate the extracted distributions to form a global distribution embedded in a conditional generator $G$.

In the right part of Fig.3, our second task is to train a fair and accurate model $f$, consisting of a feature extractor and classification head. The accuracy loss $\mathcal{L}_{\textrm{acc}}$ is obtained on real samples. To debias the model, the generator produces a corresponding fake latent feature with a different attribute value for each latent feature. We mix the true features with the fake ones and require the model to make consistent predictions on the mixed samples, which gives the fairness loss $\mathcal{L}_{\textrm{fair}}$. Each of these two tasks is discussed in more detail in the following.

Our first task is to learn the global data distribution. We draw inspiration from the field of knowledge extraction [51, 39]. We extract local data distribution information before aggregating it to form a global distribution. We chose to perform this task in the latent space $\mathcal{Z}\in\mathbb{R}^{p}$ instead of input space $\mathcal{X}\in\mathbb{R}^{d}$ for both privacy and practical concerns. Because 1) sample-specific information is compressed in the latent space, only class-related information is retained; and 2) the latent space $\mathcal{Z}$ is more compact than the input space $\mathcal{X}$, making optimization more manageable. Note that the object of this paper is to train an algorithmic fair FL model without accessing client data, which is understudied in the literature. We leave both private and fair FL to our future work.

The feature extractor $E$ trained with $h^{y}$ will only retain the information relevant to $y$. While information about the attribute $a$ may be compressed. To address this, we designed an auxiliary classification head $h^{a}$ that can assist $E$ in extracting informative latent features. The benefit of $h^{a}$ is twofold: first, it provides feedback to the extractor $E$, allowing it to extract more informative latent features; second, $h^{a}$ embeds the relationships between the latent feature $z$ and the sensitive attribute $a$, i.e., $P(A|Z)$. This knowledge is crucial for the server to learn a global data distribution in AFed-G.

For the $k$-th client, the training process of the feature extractor $E(\cdot;\boldsymbol{\theta}^{E}_{k})$ and the classification head $h^{a}(\cdot;\boldsymbol{\theta}^{a}_{k})$ is formulated as follows:

where $\ell_{CE}$ is the cross-entropy loss.

A typical federated learning (FL) system faces the challenge of non-i.i.d. data, where each client possesses a distinct data distribution. As a result, a model that is fair in the local data may be unfair when applied to data sampled from the global data distribution. To address this issue, we propose augmenting local data with generated samples. The key is to capture the global data distribution without violating the privacy constraints of the FL system. To achieve this, we introduce two approaches.

The second task is performed on the client side. It aims to train a fair and accurate classifier $f$ with the help of $G$. The classification model $f$ is trained on both true and mixed samples, and the objective function is defined as

where ${\mathcal{L}}^{y}_{k}(\boldsymbol{\theta}^{f}_{k})$ and ${\mathcal{L}}^{fair}_{k}(\boldsymbol{\theta}^{f}_{k})$ are model’s classification loss and fairness violation loss, respectively. $\lambda$ controls the trade-off between the model’s accuracy and fairness. A larger $\lambda$ indicates a greater emphasis on fairness, while a smaller $\lambda$ improves the model’s overall accuracy at the expense of fairness. The empirical loss $\hat{\mathcal{L}}^{y}_{k}(\boldsymbol{\theta}^{f}_{k})$ is obtained on $\mathcal{D}_{k}$,

We focus on DP [18] in this work, which requires the prediction $\hat{Y}$ to be independent of the sensitive attribute $A$. The straightforward idea is to treat the discrimination level as a regularizer [26], i.e., ${\mathcal{L}}^{fair}_{k}(\boldsymbol{\theta}^{f}_{k})\coloneqq\lambda\Delta DP(f)$.

However, in FL, the data is partitioned among all clients, with each holding only a subset of the total. Debiasing with only local data will fail in global data distribution. Thus, we propose augmenting the local dataset with synthetic data. More specifically, for a real sample $(\boldsymbol{x}_{t},y_{t},a_{0})$ from the training dataset $\mathcal{D}_{k}$, the corresponding latent feature is $z_{t}=E(\boldsymbol{x}_{t})$, where $E$ is the feature extractor. We generate a fake latent feature with a different sensitive attribute $a_{1}$:

where $\epsilon\sim N(0,\boldsymbol{I})$ is the noise input. We mix the true feature with the fake one to get an augmented sample [44]:

where $t\sim\textrm{Beta}(\alpha,\alpha)$, for $\alpha\in(0,\infty)$.

One assumption made in the mixup is that feature linear interpolations can be translated into label linear interpolations. Incorporating this kind of prior knowledge implicitly helps to broaden the model’s training data distribution and, in turn, its ability to make accurate predictions on new data. Similarly, the sensitive attribute of $\bar{z}$ can be assumed as $\bar{a}=ta_{0}+(1-t)a_{1}$. To ensure fairness, the model’s prediction should be invariant to the interpolation degree $t$ and consequently the intermediate value of sensitive attribute [9]:

The penalized optimization problem is now formulated as follows:

By minimizing Eq. 21, we are optimizing the model $\boldsymbol{\theta}^{f}_{k}$ to, on the one hand, fit the local data distribution of dataset $\mathcal{D}_{k}$, and on the other hand, regularize the model’s disparate predictions on the mixed distribution of $z^{t}$ and $z^{f}$.

Fig. 4(a) shows the one classification head case. The resultant extractor $E$ tends only to retain information pertinent to label $y$ and compresses all other information. $\{x_{1},y_{1}=0,a_{1}=1\}$ and $\{x_{2},y_{2}=0,a_{2}=0\}$ are mapped to the same area due to the same label $y=1$ despite having different attribute values $a$. This brings confusion when training conditional GAN in this feature space.

When training conditional GAN, the generated sample should resemble the training data. In other words, the fake samples should be close to the real ones in the feature space. Near $z_{2}$, within the area $s_{0}$, there are samples with attribute values $a=0$ and $a=1$. As a result, feeding the generator with attribute value $a=0$ will produce samples similar to group $a=0$ or group $a=1$, as depicted in Fig. 5(a). The same holds for the group $a=1$.

To address this, we propose adding an auxiliary classification head $h^{a}$ to provide more feedback for the extractor as shown in Fig.4(b). With the guidance of $h_{y}$ and $h^{a}$, the extracted features contain information about $y$ and $a$. Samples from groups defined by $y$ and $a$ are mapped to four distinct feature space regions. On this basis, we can train a generator capable of generating samples conditional on $a$.

Fig. 5 shows the results of the single and two classification head cases. The inputs to $E$ are sampled from the CelebA dataset. As shown in Fig. 5(a), the generated data fails to match the real data. For $a=0$, the generated features (purple cross) overlap with the real features with attributes $a=1$ and $a=0$. As a comparison, Fig. 5(b) demonstrates that the auxiliary feedback signal from $h^{a}$ significantly improves generator performance. The extracted features are divided into four parts, corresponding to the four groups defined by $y$ and $a$. Since the features are well-separated, the GAN can learn the maps from $a$ to $\boldsymbol{z}$ flawlessly.

Our first method AFed-G trains a conditional generator $G$ to approximate the $P(Z|A)$ using the knowledge embedded in the classification head $\{\boldsymbol{\theta}_{k}^{a}\}_{k=1}^{|S|}$, i.e. $p_{k}(a|z)$. The second method, AFed-GAN, is more direct. A discriminator guides training to train a conditional GAN to learn the distribution $p_{k}(z|a)$. The former enjoys simplicity (only a generator is added) and can be carried out on the server’s side, which reduces the client’s training and communication load. In comparison, the latter performs better in learning the local data distribution.

Since introduced in [17], numerous researchers have successfully implemented GAN to learn the target distribution [27, 30]. In the context of FL, [32] demonstrates the convergence of GAN training in FL with non-i.i.d. data. Here, we focus on analyzing the shortcomings of the AFed-G approach.

Optimizing Eq. 12 comprises three terms. The first minimizes the KL divergence between the conditional generator $G$ distribution and the ground-truth joint distribution of $N$ clients, which is our target, matching the $Q_{A,Z}$ with $\prod\limits_{k=1}^{N}{P^{k}_{A,Z}}$. However, the second term maximizes the KL divergence between the marginal generator $Q_{Z}$ and target joint distributions $\prod\limits_{k=1}^{N}{P^{k}_{Z}}$. This contradicts our goal and will degrade the generator’s performance by pushing the marginal distribution away from the ground truth distribution. The last term is the conditional entropy of label $A$ of data sampled from the generator distribution $Q$. Minimizing the last term will decrease the data’s diversity by making generated $\boldsymbol{z}$ be classified as $A$ with higher confidence, i.e., away from the decision boundary. This is in accordance with our intuition that only the feedback from classification head $\boldsymbol{\theta}_{k}^{a}$ is available. This is to say, only information related to the decision boundary is provided, and the model will learn to generate ”safe” examples that can be correctly classified by $\boldsymbol{\theta}_{k}^{a}$. As a result, the generated data may fail to distribute in the space spanned by real data.