Year: 2021

Abstract:
Recently, lots of algorithms have been proposed for learning a fair classifier from centralized data. However, how to privately train a fair classifier on decentralized data has not been fully studied yet. In this work, we first propose a new theoretical framework, with which we analyze the value of federated learning in improving fairness. Our analysis reveals that federated learning can strictly boost model fairness compared with all non-federated algorithms. We then theoretically and empirically show that the performance tradeoff of FEDAVG-based fair learning algorithms is strictly worse than that of a fair classifier trained on centralized data. To resolve this, we propose FEDFB, a private fair learning algorithm on decentralized data with a modified FEDAVG protocol. Our extensive experimental results show that FEDFB significantly outperforms existing approaches, sometimes achieving a similar tradeoff as the one trained on centralized data.

heading: 1 INTRODUCTION
text: As machine learning is now used to make critical decisions that affect human life, culture, and rights, fair learning has recently received increasing attention. Various fairness notions have been introduced in the past few years (Dwork et al., 2012; Hardt et al., 2016; Zafar et al., 2017b;a; Kearns et al., 2018; Friedler et al., 2016). Among various fairness notions, group fairness is the most studied one (Hardt et al., 2016; Zafar et al., 2017a). Group fairness requires the classifier to treat different groups similarly, where groups are defined with respect to sensitive attributes such as gender and race. One of the most commonly used group fairness notions is demographic parity, which requires that different groups are equally likely to receive desirable outcomes.
There has been a large amount of work in training fair classifiers (Zafar et al., 2017c; Hardt et al., 2016; Roh et al., 2021), and almost all of these studies assume that the learner has access to the entire training data. Unfortunately, this is not the case in many critical applications. To see this, consider a scenario where multiple data owners (e.g. courts or financial institutions) have their own private data. Even if they are willing to coordinate with the other institutions to obtain a single model that works well on the combined data, they cannot directly share their data with the others due to the privacy act. This precisely sets the core question we aim to answer in this paper – how can we privately train a fair classifier on decentralized data? To answer this, we first study three existing approaches: Unfederated Fair Learning (UFL), Federated Fair Learning via FEDAVG (FFL via FEDAVG), and Centralized Fair Learning (CFL). See Fig. 1 for illustration.
Unfederated Fair Learning (UFL) and Centralized Fair Learning (CFL) UFL is the most naı̈ve yet most private approach. As the name indicates, this strategy refers to a scenario where multiple data owners simply decide to not coordinate. Instead, each of them learns a fair model on its local data to serve its own users. This approach is completely private as the participating data owners share nothing with the others. However, the overall performance of UFL is expected to be poor, because each data owner may have a highly biased view of the entire data distribution, making their locally trained classifiers fair only on a biased subset of the data, but not on the entire data. To evaluate the performance of this approach, we consider the randomized classifier that makes a prediction using a randomly chosen local classifier. Note that this can be viewed as a random customer model, i.e., a user drawn from the overall data distribution picks and visits one of the institutions, uniformly at random. Another extreme approach is CFL, where a fair model is trained on the pooled data. We expect CFL to achieve the best performance tradeoff, at the cost of no privacy.
Federated Fair Learning via FEDAVG (FFL via FEDAVG) FFL via FEDAVG applies federated learning (Konečnỳ et al., 2017) together with existing fair learning algorithms. Federated learning is
a distributed learning framework, using which many data owners can collaboratively train a model under the orchestration of a central server while keeping their data decentralized. For instance, under FEDAVG, the standard aggregation protocol for federated learning, the central server periodically computes a weighted average of the locally trained model parameters. If each data owner runs a fair learning algorithm on its own data and these locally trained models are aggregated via FEDAVG, then one might hope to obtain a model that is accurate and fair on the overall data distribution. We call this approach Federated Fair Learning via FEDAVG (FFL via FEDAVG).
Goal and Main Contributions The performances of these approaches have not been rigorously analyzed in the literature. In the first place, it has been unknown whether there is any strict performance gap between UFL and FFL via FEDAVG. This makes it unclear whether or not federated learning is necessary at all for decentralized fair learning. The performance comparison between FFL via FEDAVG and CFL also remains unclear. Can FFL via FEDAVG always match the performance of CFL? If not, can we develop a better federated learning approach for decentralized fair learning? Inspired by these open questions, this work rigorously analyzes the performance of the existing approaches and proposes a new solution to decentralized fair learning. Our major contributions can be summarized as follows:
• We develop a theoretical framework for analyzing various approaches for decentralized fair learning. Using this, we prove the strict ordering between the existing approaches, i.e., under some mild conditions, UFL < FFL via FEDAVG < CFL, w.r.t. their fairness-accuracy tradeoffs.
• Improving upon the state-of-the-art algorithm for (centralized) fair learning (Roh et al., 2021), we design FEDFB, a novel approach to learning fair classifiers via federated learning.
• Via extensive experiments, we show that (1) our theoretical findings hold under more general settings, and (2) FEDFB significantly outperforms the existing approaches on various datasets and achieves similar performance as CFL.
To the best of our knowledge, our work is the first theoretical performance comparison of various approaches to fair learning on decentralized data. Moreover, it characterizes the necessity of federated learning for improved fairness-accuracy tradeoff, and we expect this to expedite the adoption of federated learning-based approaches. Our proposed solution FEDFB achieves state-of-the-art performance on many datasets, sometimes achieving a similar tradeoff as the one trained on centralized data.

heading: 2 RELATED WORK
text: Model Fairness Among various algorithms for fair training (Zemel et al., 2013; Jiang & Nachum, 2020; Zafar et al., 2017c;a; Hardt et al., 2016; Roh et al., 2021; 2020), the current state-of-the-art is FairBatch (Roh et al., 2021), which reweights the samples by solving a bi-level optimization problem, whose inner optimizer is the standard training algorithm and outer optimizer aims to find the best weights attached to groups of samples for the sake of model fairness.
Federated Learning Unlike traditional, centralized machine learning approaches, federated learning keeps the data decentralized throughout training, reducing the privacy risks involved in traditional approaches (Konečnỳ et al., 2017; McMahan et al., 2017). FEDAVG (McMahan et al., 2017) is the
first and most widely used federated learning algorithm. The idea is to iteratively compute a weighted average of the local model parameters, with the weights proportional to the local datasets’ sizes. Prior work (Li et al., 2020b) has shown that FEDAVG provably converges under some mild conditions. The design of our proposed algorithm FEDFB is also based on that of FEDAVG.
Federated Fair Learning for Client Parity There have been only a few attempts in achieving fairness under the federated setting. Moreover, the definition of “fairness” used in the existing federated learning work is slightly different from the standard notion used in the centralized setting. One popular definition of fairness in the federated setting is that all clients (i.e. data owners) achieve similar accuracies (or loss values), which we call client parity, and several algorithms have been proposed to achieve this goal (Li et al., 2021; 2020a; Mohri et al., 2019; Yue et al., 2021; Zhang et al., 2020a). To compare our methods with existing federated fair learning algorithms designed for client parity, we also extend our FEDFB such that it can also achieve client parity instead of the standard notion of group fairness. In Sec. 5, we will show that FEDFB can achieve as good client parity as the existing algorithms, though FEDFB is not specifically designed for client parity.
Federated Fair Learning for Group Fairness A few very recent studies (Ezzeldin et al., 2021; Rodrı́guez-Gálvez et al., 2021; Chu et al., 2021; Du et al., 2021; Cui et al., 2021), conducted concurrently with our work, also aim at achieving group fairness under federated learning. In particular, Du et al. (2021), Rodrı́guez-Gálvez et al. (2021) and Chu et al. (2021) mimic the centralized fair learning setting by exchanging information for each local update. In contrast, our FEDFB requires much fewer communication rounds, ensuring higher privacy and lower communication costs. Simlar to FEDFB, Ezzeldin et al. (2021) employs FEDAVG and a reweighting mechanism to
achieve group fairness. However, FAIRFED only applies to the case with one single binary sensitive attribute, while Rodrı́guez-Gálvez et al. (2021) and Chu et al. (2021) are not applicable to demographic parity. Therefore, we summarize the comparison of UFL, FFL via FEDAVG, CFL, FEDFB and AGNOSTICFAIR (Du et al., 2021) in terms of performance and privacy in Fig. 2. There is also work that aims at achieving local fairness for each data owner (Cui et al., 2021). This is in contrast to our work, which instead focuses on achieving global fairness in the overall data distribution. Our setting is more appropriate in domains such as criminal justice and social welfare.

heading: 3 PERFORMANCE ANALYSIS OF UFL, FFL VIA FEDAVG AND CFL
text: In Sec. 3.1, we first show the necessity of federation by proving that FFL via FEDAVG can achieve strictly higher fairness than UFL. We then prove the limitation of FFL via FEDAVG by comparing its performance with an oracle bound of CFL in Sec. 3.2. These two results together imply that federated learning is necessary, but there exists a limit on what can be achieved by FEDAVG-based approaches. We will present informal theoretical statements, deferring the formal versions and proofs to Sec. A.
Problem Setting Denote [N ] := {0, 1, . . . , N − 1} for any N ∈ Z+. We assume I clients, which have the same amount of data. We further assume a simple binary classification setting with a binary sensitive attribute, i.e., x ∈ X = R is the input feature, y ∈ Y = [1] is the outcome and a ∈ A = [A] = [1] is the binary sensitive attribute. Assume x is a continuous variable. The algorithm we will develop later in Sec. 4 will be applicable to general settings.
We now introduce parameters for describing the data distribution. Let y | x ∼ Bern(η(x)) for all client i, where η(·) : X → [0, 1] is a strictly monotone increasing function. Assume x | a = a, i = i ∼ P(i)a , a | i = i ∼ Bern(qi), where i is the index of the client, P(i)a is a distribution, and qi ∈ [0, 1] for a = 0, 1, i ∈ [I]. Let F = {f : X × A → [0, 1]}. Given f ∈ F and data sample (x, a), we consider the following randomized classifier: ŷ | x, a ∼ Bern(f(x, a)). Using these definitions, we now define demographic parity, specialized for a binary sensitive attribute:
Definition 1 (Demographic Parity (binary cases)). P(ŷ = 1 | a = 0) = P(ŷ = 1 | a = 1).
To measure how unfair a classifier is with respect to demographic parity (DP), we measure DP disparity, i.e. the absolute difference between the two positive prediction rates:
DP Disp(f) = |P(ŷ = 1 | a = 0)− P(ŷ = 1 | a = 1)|.

heading: 3.1 NECESSITY OF FEDERATION: FFL VIA FEDAVG IS STRICTLY BETTER THAN UFL
text: UFL Optimization We now present the optimization problem solved in the UFL scenario. Here, for analytical tractability, we will assume the population limit, i.e., the true data distribution is used in optimization. Recall that clients do not coordinate in this scenario, and each of them solves their own optimization problem to train a locally fair classifier. In particular, each client i ∈ [I] first sets its own local fairness constraint εi ∈ [0, 1], and solves the following constrained optimization problem:
min f∈F
P(ŷ 6= y | i = i), s.t. |P(ŷ = 1 | a = 0, i = i)− P(ŷ = 1 | a = 1, i = i)| ≤ εi. (UFL(i, εi))
We denote by fεii the solution to UFL(i, εi). Recall that the overall performance of UFL is defined as the performance of the following mixture of I classifiers:
ŷ | x, a ∼ Bern(fεii (x, a)),w.p. 1/I = Bern (∑ i∈[I] fεii (x, a)/I ) = Bern(fUFLε ),
where fUFLε := ∑ i∈[I] f εi i (x, a)/I , with ε = (ε0, . . . , εI−1).
The question here is whether the resulting classifier fUFLε obtained by UFL can achieve an arbitrary level of fairness. The following lemma shows that UFL cannot achieve a high enough fairness level beyond a certain threshold. Lemma 1 ((Informal) Achievable fairness range of UFL). Let qi = q ∈ (0, 1) for all i ∈ [I]. Under certain conditions, there exists a certain DP disparity threshold δ > 0 such that minε∈[0,1]I DP Disp(fUFLε ) > δ.
A critical condition of Lemma 1 is that the distribution of insensitive attribute x | a is highly heterogeneous on different clients. (See the detailed statements in Sec. A.2.2 and Sec. A.4.) Therefore, Lemma 1 implies that UFL fails to achieve strict fairness requirements even without data heterogeneity on the distribution of sensitive attribute a. The following corollary provides an example satisfying the conditions of Lemma 1. Corollary 2 (Informal). Let I = 2 and q0 = q1 = 0.5, η(x) = 11+e−x ,P (i) a = N (µ(i)a , σ(i)2), where i = 0, 1. Under certain assumptions, if one client has much larger variance than the other, there exists δ > 0 such that minε0,ε1∈[0,1] DP Disp(f UFL ε ) > δ.
Note that the condition that one client has a much larger variance than the other contributes to the “high data heterogeneity” requirement. We provide the explicit form of δ in Corollary 9 in Sec. A.2.2. Corollary 2 implies that under a limiting case of Gaussian distribution, UFL cannot achieve high fairness requirements. In Sec. 5.1, we will numerically demonstrate the same claim holds for more general cases. Next, we give a specific example that satisfies the conditions of Corollary 2, which is visualized in Fig. 3(a).
Example 1. Let µ(0)0 = µ (0) 1 = 0, µ (1) 0 = 3, µ (1) 1 = −1, σ(0) = 70 and σ(1) = 1. Then, δ ≈ 0.21.
FFL via FEDAVG Optimization FFL via FEDAVG enables federated training of a fair classifier on decentralized data. In Sec. A.3.2, we show that the classifier obtained by FFL via FEDAVG is equivalent to fFFL via FedAvgε , the solution to the following constrained optimization problem.
min f∈F
P(ŷ 6= y)
s.t. |P(ŷ = 1 | a = 0, i = i)− P(ŷ = 1 | a = 1, i = i)| ≤ εi. (FFL via FEDAVG(ε))
The following theorem asserts that FFL via FEDAVG can achieve a strictly higher fairness than UFL.
Theorem 3 ((Informal) Fundamental values of federated learning for fairness). Let qi = q ∈ (0, 1) for all i ∈ [I]. Under certain conditions, minε∈[0,1]I DP Disp(fUFLε ) > minε∈[0,1]I DP Disp(f FFL via FedAvg ε ) = 0.
Similar to Lemma 1, the technical assumptions include high enough heterogeneity of x | a across the clients. Thm. 3 shows that even with just two clients (I = 2), a non-trivial gap exists between non-federated algorithms and federated algorithms in their fairness performances. More details are provided in Sec. A.4. The theorem asserts that, under certain distributional assumptions, by using the optimal local fairness budgets εi, FFL via FEDAVG can achieve perfect fairness, while UFL cannot.
Remark 1. Extending Thm. 3 to general cases where qi are not all the same remains open. In particular, the analysis of FFL via FEDAVG for those cases remains open. However, we conjecture that our lemma holds for more general cases, and we numerically support our conjecture in Sec. 5.
Remark 2. There is a stark difference between this phenomenon and the well-known gain of federated learning due to an increased sample size, which is almost negligible with a few number of clients. Our finding on this untapped gain in fairness can better support the need for federated learning even between a small number of clients, which is the case for most cross-silo federated learning scenarios.

heading: 3.2 FFL VIA FEDAVG IS STRICTLY WORSE THAN CFL
text: While we showed that FFL via FEDAVG can achieve perfect fairness on certain distributions, it is still unclear whether or not this is the case for every distribution. In this section, we first present the optimization problem for CFL, whose achievable fairness region can serve as an upper bound on that of all other federated learning algorithms. We then show the existence of data distributions on which FFL via FEDAVG achieves a strictly worse fairness performance than CFL. This implies a strict gap between the performance tradeoff of FFL via FEDAVG and that of CFL.
CFL Optimization We consider the same problem setting as Sec. 3.1. We now model the CFL scenario as the following constrained optimization problem:
min f∈F
P(ŷ 6= y), s.t. |P(ŷ = 1 | a = 0)− P(ŷ = 1 | a = 1)| ≤ ε. (CFL(ε))
Denote the solution to CFL(ε) as fCFLε . It is clear that f CFL ε achieves the best accuracy-fairness tradeoff, at the cost of no privacy. The following lemma shows that there exists some distribution such that FFL via FEDAVG is strictly worse than CFL when the distribution of sensitive attribute a is heterogeneous (qi are not all the same).
Lemma 4 ((Informal) A strict gap between FFL via FEDAVG and CFL). When there exist i 6= j ∈ [I] s.t. qi 6= qj , there exist a distribution such that minε∈[0,1]I DP Disp(fFFL via FedAvgε ) > minε DP Disp(fCFLε ) = 0.
Remark 3. A strict gap exists for certain distributions, but not for all distributions.

heading: 3.3 NUMERICAL COMPARISONS OF ACCURACY-FAIRNESS TRADEOFFS
text: One limitation of our current theoretical results is that they only compare the maximum achievable fairness. Note that such analysis reveals how the tradeoff of accuracy and fairness behaves as the fairness level increases, but it fails at fully characterizing the entire tradeoff curve. Extending our theoretical results to fully characterize such tradeoffs is highly non-trivial, so we leave it as future
work. Instead, we numerically solve each of the optimization problems and visualize the tradeoff curves achieved by different algorithms.
Shown in Fig. 4 are the tradeoff curves for two clients cases. Let x | a = 0, i = 0 ∼ N (3, 1), x | a = 1, i = 0 ∼ N (5, 1), x | a = 0, i = 1 ∼ N (1, 1), x | a = 1, i = 1 ∼ N (−1, 1), a | i = 0 ∼ Bern(q0), a | i = 1 ∼ Bern(q1), η(x) = 11+e−x , and vary the values of q0 and q1. Note that |q1− q0| captures the heterogeneity of the sensitive data a, which increases from left to right. First, one can observe that UFL<FFL via FEDAVG< CFL in terms of the achievable fairness range, as predicted by our theory. Furthermore, we also observe an increasing gap between the tradeoff curves as the data heterogeneity increases. Theoretical understanding of this phenomenon remains open.

heading: 4 FEDFB FOR IMPROVED FEDERATED FAIR LEARNING
text: Our findings in the previous section imply that federated learning is necessary, but the current FEDAVG-based approach might not be the best approach. Can we design a federated learning algorithm that is strictly better than FEDAVG-based approaches? In this section, we propose a new federated learning algorithm for fair learning, which we dub FEDFB (short for Federated FairBatch). Our approach is based on the state-of-the-art (centralized) fair learning algorithm FB (short for FairBatch) (Roh et al., 2021) and has a few desirable theoretical guarantees. Later in Sec. 5, we empirically show that FEDFB outperforms FFL via FEDAVG and closely matches the CFL’s tradeoff on various datasets. Algorithm 1: FEDFB algorithm ClientUpdate(i,w,λ):
Update w(i) according to the sample weights λ; L (i) y,a ← ∑ (i,y,a)=(i,y,a) `(ŷ, y;w),
∀(y, a); Send w(i), L(i)y,a(w) for all (y, a) to
server via a SecAgg protocol;

heading: ServerExecutes:
text: for each iteration do Clients perform updates; w ← SecAgg({w(i)}); Ly,a ← SecAgg({L(i)y,a}), ∀(y, a); λ← Update(λ,Ly,a); Broadcast w and λ to clients;
output :w
We first provide a brief review of the FB algorithm. FB solves a bi-level optimization problem to learn a fair classifier on centralized data. The inner optimization problem solves a weighted empirical risk minimization problem where samples from different groups are reweighted by different weights. The outer optimization problem optimizes the weights used for the inner problem, with the goal of minimizing the unfairness of the classifier. FB works for various group fairness definitions including demographic parity, equalized odds, and equalized opportunity. For the case of demographic parity, the algorithm reduces to the following simple yet intuitive algorithm. The algorithm starts with equal weights for two different groups. After training a model with the initial weights, it computes the sign of the difference between the two positive prediction rates P(ŷ = 1 | a = 0) − P(ŷ = 1 | a = 1). If this quantity is zero, then DP Disp is zero, so the sample weights are not updated. If this is positive,
it decreases the weights for the samples whose y = 1, a = 0 and increases the weights for the samples whose y = 1, a = 1 so that after retraining, P(ŷ = 1 | a = 0) decreases and P(ŷ = 1 | a = 1) increases. And vice versa for the other case.
FEDFB is a simple modification of the original FB, which closely simulates the centralized FB applied to the entire data. Recall that under the FEDAVG protocol, clients periodically share their locally trained model parameters with the server. Our modification is based on the following simple observation: the bi-level structure of FB naturally fits the hierarchical structure of federated learning.
More specifically, note that if the clients also share their group-specific positive prediction rates, then the centralized server can immediately reconstruct the difference between the two positive prediction rates, measured on the entire data distribution. Therefore, the update rules for the outer optimization of the original FB algorithm can be implemented at the central server given the extra information. Then, the central server can broadcast the updated group weights with the clients, which can then locally train models with the newly reweighted samples.
This precisely describes the essence of FEDFB, and shown in Alg. 1 is the pseudocode of the FEDFB framework. Note that the update rule for group weights (denoted by λ in the pseudocode) only requires the sum of the group losses, which enables secure aggregation. In Sec. B.1, we present the detailed description of the algorithm, which consists of the local training algorithm with
Table 1: Comparison of accuracy and DP disparity on the synthetic, Adult, COMPAS, and Bank datasets.
FEDFB significantly outperforms the other approaches on all the tested datasets, sometimes nearly matching the performance of CFL. Note that FFL via FEDAVG sometimes gets a strictly worse performance than FEDAVG. This can be explained by noting that the average of two fair models may not be fair at all.
SYNTHETIC ADULT COMPAS BANK METHOD ACC.(↑) DP DISP.(↓) ACC.(↑) DP DISP.(↓) ACC.(↑) DP DISP.(↓) ACC.(↑) DP DISP.(↓)
FEDAVG .886±.003 .406±.009 .829±.012 .153±.022 .655±.009 .167±.037 .898±.001 .026±.003
UFL .727±.194 .248±.194 .825±.008 .034±.028 .620±.019 .088±.055 .892±.002 .014±.006 FFL VIA FEDAVG .823±.102 .305±.131 .801±.043 .123±.071 .595±.005 .059±.009 .893±.000 .017±.001 FEDFB (OURS) .613±.007 .011±.009 .765±.001 .001±.001 .542±.001 .001±.001 .883±.000 .000±.000
CFL .726±.009 .028±.016 .816±.010 .045±.024 .616±.033 .036±.028 .883±.000 .000±.000
reweighted samples, the model/loss aggregation protocol, the group-weight update algorithm, and the model/group-weight distribution protocol. We highlight a few advantages of FEDFB. First, it provably converges under some mild technical conditions. We proved it by leveraging the analysis tools for federated learning and FB – See Thm. 23 for more details. Second, our algorithm is a strict improvement of FB even in centralized data cases. The original FB algorithm was not applicable if the sensitive attributes are not binary. We made appropriate changes to the algorithm (with theoretical guarantees) so that it can also handle more general cases. Thus, we use our version of FB by default for fair learning in the rest of this paper.
One can note that under FEDFB, clients exchange additional information with the server by communicating real-valued loss values in addition to the model parameters. To limit the information leakage, we also consider a variant of FEDFB, which exchanges the quantized loss values. For instance, “FEDFB(10bits)” means each loss value is uniformly quantized using 10 bits. Such a loss quantization scheme limits the amount of additional information shared between the clients and the server, at the cost of potentially inaccurate group weight updates.

heading: 5 EXPERIMENTS
text: In this section, we numerically study the performance of UFL, FFL via FEDAVG, and CFL for more general cases, and evaluate the empirical performance of FEDFB. We investigate the fundamental limitation of UFL under general Gaussian distribution. We compare the accuracy-fairness tradeoff of UFL, FFL via FEDAVG, and CFL by numerically solving UFL(i, εi), FFL via FEDAVG(ε), and CFL(ε). More specifically, we first characterize the solutions to these problems up to an unknown scalar, which can be numerically optimized. See Sec. A for more details. Moreover, we evaluate FEDFB on both demographic parity and client parity. In each simulation study, we report the summary statistics across five replications. Similar to the experimental settings used in (Roh et al., 2020), we train all algorithms using a two-layer ReLU neural network with four hidden neurons to evaluate the performance of FEDFB for the non-convex case. The results for logistic regression are provided in Sec. C. We also investigate the empirical relationship between the performance of FEDFB and the number of clients and incorporate differential privacy to further strengthen the power of FEDFB. More implementation details are included in Sec. C. 5.1 LIMITATION OF UFL ON GENERAL CASES The first experiment examines the fairness range of UFL under a more general Gaussian distribution, which does not satisfy the conditions of Corollary 2. For instance, if the variance of two clients is similar, then the conditions do not hold. However, we still conjecture that the same phenomenon holds for more general distributions, and we corroborate our conjecture with numerical experiments. Shown in Fig. 3(b,c) are the numerically computed lower bound on UFL’s achievable fairness. In particular, for (b), we let x | a = 0, i = 0 ∼ N (10, 0.22), x | a = 1, i = 0 ∼ N (9.8, 0.22), x | a = 0, i = 1 ∼ N (0.2, 0.22), x | a = 1, i = 1 ∼ N (0, 0.22), a ∼ Bern(0.2), and for (c), we let x | a = 0, i = 0 ∼ N (3, 1), x | a = 1, i = 0 ∼ N (5, 1), x | a = 0, i = 1 ∼ N (1, 1), x | a = 1, i = 1 ∼ N (−1, 1), a ∼ Bern(0.5). For both cases, we set η(x) = 11+e−x . It is easy to check that these distributions do not satisfy the conditions of Corollary 2. In particular, the distribution (b) corresponds to the case that the same group is favored on both clients, and the positive rates of each group in different clients are distinctive. The distribution (c) represents the case that different groups are favored on two clients. In both cases, we can see that UFL fails to achieve perfect fairness, i.e., δ > 0. We also observe that δ is large on the distribution (c), where different groups are favored on two clients. This supports our conjecture that UFL’s fairness performance is strictly limited not only on certain data distributions but also on more general ones.

heading: 5.2 ACCURACY-FAIRNESS TRADEOFFS OF UFL, FFL VIA FEDAVG AND CFL
text: The second experiment extends the experiments conducted in Sec. 3.3. We assess the relationship between the data heterogeneity and the gap between the three fair learning scenarios with three clients.
As shown in Fig. 8, FFL via FEDAVG is observed to achieve a strictly worse tradeoff than CFL and a strictly higher maximum fairness value than UFL. The results corroborate the benefit and limitation of FEDAVG-based federated learning in improving fairness. A very interesting observation is that UFL is observed to obtain a strictly higher accuracy than FFL via FEDAVG. Indeed, this could be attributed to the fact that the average of locally fair models might not be fair to any sub-distribution, while UFL at least ensures that each component of the mixture classifier is fair on some sub-distribution.

heading: 5.3 FEDFB EVALUATION ON DEMOGRAPHIC PARITY
text: We assess the empirical performance of FEDFB for both convex and non-convex cases on four datasets and the performance of FEDFB under different data heterogeneity. We focus on demographic parity and report DP disparity = maxa∈[A] |P(ŷ = 1 | a = a)− P(ŷ = 1)|, where A is the number of groups. Note that this is slightly different from the definition we used in the previous sections, which was used specifically for the case of one binary sensitive attribute.
Baselines We employ three types of baselines: (1) decentralized non-fair training (FEDAVG); (2) decentralized fair training (UFL, FFL via FEDAVG); (3) centralized fair training (AGNOSTICFAIR, CFL). Here, for all the algorithms that involve fair training, we use our improved version of FB, which is the state-of-the-art fair learning algorithm on centralized data. for fairer comparison and better performance, the implementation of UFL, FFL via FEDAVG, and CFL are all based on FB. Note that UFL is absolutely private, CFL violates the privacy policy, FEDAVG, FFL via FEDAVG, and FEDFB share some information at communication rounds without directly sharing the data, and AGNOSTICFAIR exchanges information for each local update. To have a fairer comparison between FFL via FEDAVG and FEDFB, we also equalize their differential privacy guarantees (Dwork, 2008) and compare their performances. See Sec. C for more details. We also report the performance of FAIRFED, a recently proposed algorithm for achieving demographic parity for binary sensitive groups in the federated setting (Ezzeldin et al., 2021), and AGNOSTICFAIR in Sec. C.
Datasets (synthetic) We follow Roh et al. (2021) for data generation, but with a slight modification to make the dataset more unbalanced. To study the empirical relationship between accuracy, fairness, and data heterogeneity, we split the dataset in different ways to obtain desired levels of data heterogeneity. More details are given in Sec. C.2. (real) We use three benchmark datasets: Adult (Dua & Graff, 2017) with 48,842 samples, COMPAS (ProPublica, 2021) with 7,214 samples, and Bank (Moro et al., 2014) with 45,211 samples. We follow Du et al. (2021)’s method to preprocess and split Adult into two clients and Jiang & Nachum (2020)’s method to preprocess COMPAS and Bank. Then, we split COMPAS into two clients based on age and split Bank into three clients based on the loan decision. Note that all the datasets are split in heterogeneous ways.
FEDFB nearly matches the performance of CFL.
Results We present the results for two-layer ReLU neural networks in Table 1 and leave the results for logistic regression in Sec. C. Table 1 reports the test accuracy and DP disparity of four baselines and FEDFB. We see a substantial fairness improvement obtained by FEDFB. As expected, the resulting fairness level of FEDFB is close to that of CFL and AGNOSTICFAIR. Besides, we observe the poor performance of UFL and FFL via FEDAVG, which is due to the fundamental limitation of UFL and FFL via FEDAVG. Table 2 reports the accuracy and fairness of each method under different data heterogeneity. FedFB is observed to be robust to data heterogeneity. This agrees with our expectation as FEDFB mimics the operation of CFL – which is not affected by data heterogeneity – as
much as possible by design. We make a more thorough comparison between CFL and FEDFB by plotting the accuracy-fairness tradeoff curves in Fig. 5. To demonstrate the performance gain does not come at the cost of privacy loss, we restrict FEDFB to only exchange 10 bits of information per communication round. Fig. 5 showcases the benefit of FEDFB in terms of accuracy, fairness and privacy. In Table 7 and Table 8 in Sec. C, we compare FEDFB and FAIRFED. One can observe that FEDFB can achieve a strictly improved fairness than FAIRFED. Also, FEDFB is observed to be more
robust to data heterogeneity. Table 9 in Sec. C shows that FEDFB achieves similar performance as AGNOSTICFAIR, at much lower cost of privacy.

heading: 5.4 FEDFB EVALUATION ON CLIENT PARITY
text: We evaluate the performance of FEDFB in achieving client parity (CP) and compare it with the state-of-the-art algorithms for CP. We will measure CP disparity = maxi 6=j∈[I] |L(i) − L(j)|. Here L(i) is the loss in ith client, see Sec. B.4 for more detail.
Baselines We consider GIFAIR (Yue et al., 2021), Q-FFL (Li et al., 2020a), DITTO (Li et al., 2021), and the unconstrained baseline FEDAVG (McMahan et al., 2017). GIFAIR and Q-FFL are the most similar ones to FEDFB. Similar to FEDFB, both GIFAIR and Q-FFL propose a modified aggregation protocol, under which clients share some additional information with the central server, which then accordingly adjust the objective function used for the next round of training. The key difference is that while FEDFB optimizes the coefficients for the primary objective terms (i.e. sample reweighting) by solving a bi-level optimization problem, GIFAIR updates the coefficient for the penalty terms, and Q-FFL implicitly updates the weights on each objective term based on nonlinear behaviors of polynomial functions, which is equivalent to the α-fairness algorithm used in networking (Mo & Walrand, 2000). The DITTO algorithm combines multitask learning with federated learning to learn a personalized classifier for each client, improving the accuracy of the clients with low accuracy.
Datasets We use the same datasets as Sec. 5.3, but split the datasets according to their sensitive attributes to simulate the same setting as assumed by GIFAIR, Q-FFL, and DITTO.
Results Fig. 6 shows that FEDFB offers competitive and stable performances in mitigating the model bias, especially in the high fairness region. Although Q-FFL achieves better accuracy and fairness on the synthetic data, under strict fairness constraint, FEDFB and its private variant nearly achieves the highest accuracy on the other three datasets.

heading: 6 CONCLUSIONS
text: Summary We have investigated how one can achieve group fairness under a decentralized setting. For the first time in the literature, we developed a theoretical framework for decentralized fair learning algorithms and analyzed the performance of UFL, FFL via FEDAVG, and CFL. As a result, we provide novel insights that (1) federated learning can significantly boost model fairness even with only a handful number of participating clients, and (2) FEDAVG-based federated fair learning algorithms are strictly worse than the oracle upper bound of CFL. To close the gap between FEDAVG-based fair learning algorithms and CFL, we propose FEDFB, a new federated fair learning algorithm. The key idea behind FEDFB is that each client shares extra information about the unfairness of its local classifier with the server, which then computes the optimal samples weights that need to be used for the following round of local training. Our extensive experimental results demonstrate that our proposed solution FEDFB achieves state-of-the-art performance, while still ensuring data privacy.
Open questions (Theory) While we characterized some fundamental limits on tradeoffs of various approaches, there still remains a large number of open questions. First, as we briefly mentioned in Sec. 3.3, full theoretical characterization of accuracy-fairness tradeoff still remains open. Our current theoretical results only study the extreme ends of the tradeoff curves. Moreover, as shown in Sec. 5.2, some of our experimental results reveal a highly nontrivial phenomenon. Studying this phenomenon and identifying the exact relationship between various learning algorithms is an interesting open problem. Furthermore, a three-way tradeoff between accuracy, fairness, and privacy remains widely open. (Algorithm) It remains open whether or not our proposed solution FEDFB can be applied for achieving different fairness notions used in the federated setting. In particular, proportional fairness, i.e., clients who contribute more should receive more rewards (Zhang et al., 2020b; Lyu et al., 2020b;a), is another popular notion of fairness used in the federated setting, and our current FEDFB cannot handle it. Extending FEDFB to handle proportional fairness is one future research direction.

heading: ETHICS STATEMENT
text: This work will improve the well-being of individuals in our society by solving ethical issues of AI, such as the implicit discrimination in machine learning algorithms and the privacy of sensitive data. Our theoretical and empirical findings assert that a fair machine learning model can be reliably trained on decentralized data without compromising much privacy.

heading: REPRODUCIBILITY STATEMENT
text: We have released our implementation in anonymous github1, which contains the code for all the experiments, including the datasets we use and the implementation of data processing steps. For the theoretical results, we provide all the necessary assumptions and proof in the Appendix.

heading: A APPENDIX - UFL, FFL VIA FEDAVG, CFL ANALYSIS
text: In this section, we provide the concrete analysis for UFL, FFL via FEDAVG, and CFL. For illustration purposes, we will start by discussing two clients cases, and then extend the analysis into more clients cases in Sec. A.4. We begin with the analysis of CFL in Sec. A.1. Then we analyze UFL and FFL via FEDAVG. To be specific, in Sec. A.2, we analyze the limitation of UFL and present the formal version of Lemma 1 under two clients cases and Corollary 2. In Sec. A.3, we analyze FFL via FEDAVG and compare it with UFL and CFL, then we present the formal two-client version of Thm. 3 and Lemma 4. All the multi-client statements are included in Sec. A.4 We summarize the commonly used notations in Table 3 .

heading: A.1 CFL ANALYSIS
text: In this section, we analyze the CFL classifier fCFLε given in CFL(ε). We mainly derive the solution of CFL(ε) in Lemma 5. In Lemma 6 and Lemma 7 we summarize the properties of fCFLε . Lemma 5. Let q ∈ (0, 1). Define g(·) : [−max(q, 1− q),max(q, 1− q)]→ [−1, 1] as
g(λ) = ∫ [η−1( 12− λ 2(1−q) ),+∞] dP0 − ∫ [η−1( 12 + λ 2q ),+∞] dP1,
then fCFLε = {Js(x, a) > 0K + αJs(x, a) = 0K : α ∈ [0, 1]}, where s(x, 0) = 2η(x) − 1 + λ1−q , s(x, 1) = 2η(x) − 1 − λq , λ = g−1(sign(g(0)) min{ε, |g(0)|}). Here we denote the indicator function as JEK : JEK = 1 if E is true, zero otherwise.
Proof. The proof is similar as Menon & Williamson (2018). To solve CFL(ε), we first write the error rate and the fairness constraint as a linear function of f . Let pa(·) be the pdf of Pa, where a = 0, 1. Denote the joint distribution of x and a as px,a(x, a). Note that
P(ŷ 6= y)
= ∫ X ∑ a∈A [f(x, a)(1− η(x)) + (1− f(x, a))η(x)] px,a(x, a) dx
=Ex,af(x, a)(1− 2η(x)) + P(y = 1) and
P(ŷ = 1 | a = 0)− P(ŷ = 1 | a = 1)
= ∫ X f(x, 0)p0(x) dx− ∫ X f(x, 1)p1(x) dx
= ∫ X ∑ a∈A Ja = 0Kf(x, 0)px,a(x, a) P(a = 0) dx− ∫ X ∑ a∈A Ja = 1Kf(x, 1)px,a(x, a) P(a = 1) dx
=Ex,a [ f(x, 0)
Ja = 0K 1− q − f(x, 1) Ja = 1K q
] .
Consequently, our goal becomes solving
minf∈F Ex,af(x, a)(1− 2η(x)) + P(y = 1) s.t. |Ex,a [ f(x, 0) Ja=0K1−q − f(x, 1) Ja=1K q ] | ≤ ε. (1)
Denote the function that minimizes the error rate (ERM) as f̃ ∈ F . It is easy to see that,
f̃(x) ∈ {Jη(x) > 1/2K + αJη(x) = 1/2K : α ∈ [0, 1]} .
Next, consider the following three cases. In particular, we provide the proof for |MD(f̃)| ≤ ε and MD(f̃) > ε. The proof for MD(f̃) < −ε is similar as the proof for MD(f̃) > ε.
Case 1. |MD(f̃)| ≤ ε: ERM is already fair.
The solution to (1) and CFL(ε) is f̃ .
Case 2. MD(f̃) > ε: ERM is favoring group 0 over group 1.
We will show that solving (1) is equivalent to solving an unconstrained optimization problem.
First, we will prove by contradiction that the solution f? ∈ F to (1) satisfies MD(f?) = ε. We use f? ∈ F to denote the solution of (1). Suppose the above claim does not hold. Then we have MD(f?) < ε. To show the contradiction, we construct a f ′ ∈ F that satisfies the fairness constraint and has a lower error rate than that of f?. Let f ′ be a linear combination of f? and f̃ :
f ′ = af? + (1− a)f̃ ,
where a = MD(f̃)−ε MD(f̃)−MD(f?) ∈ (0, 1). Then we obtain
MD(f ′) = aMD(f?) + (1− a)MD(f̃) = ε(MD(f̃)−MD(f ?))
MD(f̃)−MD(f?) = ε.
Denote the error rate P {ŷ 6= y} as e : F → [0, 1]. Then the error rate of f ′ is
e(f ′) = ae(f?) + (1− a)e(f̃) < e(f?), which is inconsistent to the optimality assumption of f?. Therefore, MD(f?) = ε.
Now, solving CFL(ε) is equivalent to solving
minf∈F Ex,af(x, a)(1− 2η(x)) + P(y = 1) s.t. |Ex,a [ f(x, 0) Ja=0K1−q − f(x, 1) Ja=1K q ] | = ε.
Furthermore, the optimization problem above is also equivalent to minf∈F Ex,af(x, a)(1− 2η(x))− λEx,a ( f(x, 0)
Ja = 0K 1− q − f(x, 1) Ja = 1K q
) (2)
s.t. |Ex,a [ f(x, 0)
Ja = 0K 1− q − f(x, 1) Ja = 1K q
] | = ε, (3)
for all λ ∈ R. Next, our goal is to select a suitable λ such that the constrained optimization problem above becomes an unconstrained problem, i.e., we will select a suitable λ such that the minimizer to the unconstrained optimization problem (2) satisfies equality constraint (3).
Note that
Ex,af(x, a)(1− 2η(x))− λEx,a ( f(x, 0)
Ja = 0K 1− q − f(x, 1) Ja = 1K q ) =Ex,af(x, a) ( 1− 2η(x)− λJa = 0K
1− q + λ Ja = 1K q
) ,
then the solution to unconstrained optimization problem (2) is
f̄ ∈ {Js(x, a) > 0K + αJs(x, a) = 0K : α ∈ [0, 1]} ,
where
s(x, a) = { −1 + 2η(x) + λ1−q a = 0 −1 + 2η(x)− λq a = 1 .
Since the range of η(x) is [0,1], f̄ with λ > max(q, 1 − q) is no different from f̄ with λ = max(q, 1 − q); f̄ with λ < −max(q, 1 − q) is no different from f̄ with λ = −max(q, 1 − q). Therefore, the only thing left is to find the λ ∈ [−max(q, 1− q),max(q, 1− q)] such that f̄ satisfies the constraint (3).
Now consider the mean difference between the positive rate of two groups:
MD(f̄) = P(ŷ = 1 | a = 0)− P(ŷ = 1 | a = 1)
= ∫ +∞ −∞ Jη(x) > 1 2 − λ 2(1− q)K dP0 − ∫ +∞ −∞ Jη(x) > 1 2 + λ 2q K dP1
= ∫ [η−1( 12− λ 2(1−q) ),+∞] dP0 − ∫ [η−1( 12 + λ 2q ),+∞] dP1
= g(λ).
Note that g(·) : [−max(q, 1−q),max(q, 1−q)]→ [−1, 1] is a strictly monotone increasing function. Consequently, if and only if λ = g−1(ε), f̄ satisfies (3). Recall that optimization problem (2) with constraint (3) is equivalent as CFL(ε). Thus, let λ = g−1(ε) and f̄ is the solution of CFL(ε).
Case 3. MD(f̃) < −ε: ERM is favoring group 1 over group 0.
Similarly, like Case 2, we obtain that the solution CFL(ε) is
f̄ ∈ {Js(x, a) > 0K + αJs(x, a) = 0K : α ∈ [0, 1]} , where
s(x, a) = { −1 + 2η(x) + λ1−q a = 0 −1 + 2η(x)− λq a = 1 ,
and λ = g−1(−ε). Combining all the cases above yields the desired conclusion. The proof is now complete.
Remark 4. Select α = 0, then the solution to CFL(ε) can be written as
f(x, a) = { Jη(x) > 12 − λ2(1−q)K a = 0 Jη(x) > 12 + λ2q K a = 1 . (4)
Therefore, Lemma 5 implies that the best classifier of the CFL problem is equivalent to simply applying a constant threshold to the class-probabilities for each value of the sensitive feature.
Lemma 5 suggests the following property of the solution to CFL(ε). Lemma 6. If f and g are two solutions to CFL(ε), then f = g almost everywhere.
For illustration purposes, we denote
λCFLε = g −1(sign(g(0)) min{ε, |g(0)|}). (5)
Below we summarize some useful properties of λCFLε . Lemma 7. The sign of λCFLε and MD(fCFLε ) are determined by g(0).
1. If ε < |g(0)|, then MD(fCFLε ) = λCFLε 6= 0, and g(λCFLε ) = sign(g(0))ε. If |g(0)| ≤ ε, then λCFLε = 0 and MD(f CFL ε ) = g(λ CFL ε ) = g(0).
2. If g(0) > 0 or g(0) < 0, then for any ε ≥ 0, we have λ ≤ 0 or λ ≥ 0, respectively.
Proof. The first property follows directly from the definition of λCFLε . Next, we prove the second property.
When ε > |g(0)|, we have λ = 0 and the first property holds. When g(0) > ε > 0, by the definition of λCFLε , we have λ = g
−1(ε) < g−1(g(0)) = 0. When g(0) < −ε < 0, we have λ = g−1(−ε) > g−1(g(0)) = 0. Combining all the cases above yields the desired conclusion.

heading: A.2 UFL ANALYSIS
text: With the analysis of CFL in Sec. A.1, in this section, we analyze the UFL classifier UFL(i, εi) for the case of two clients. For illustration purpose, with I = 2, we denote fUFLε0,ε1 = f UFL ε = (f ε0 0 + f ε1 1 )/2. In Sec. A.2.1 we introduce some notations for the UFL classifier fUFLε0,ε1 that follows from Lemma 5. In Sec. A.2.2 we analyze the limitation of fUFLε0,ε1 as stated in Sec. 3.1. To be more specific, we present the two clients’ version of Lemma 1, formal version of Corollary 2 and conclude their proof. In Sec. A.2.3, we analyze the performance gap between fUFLε0,ε1 and CFL classifier f CFL ε .

heading: A.2.1 PROBLEM SETTING
text: By Lemma 5, the solution to UFL(i, εi) is
fεii (x, a) = Jη(x) > 12 − λ UFLi εi
2(1−q)K a = 0 Jη(x) > 12 + λ UFLi εi 2q K a = 1 ,
where the associated λUFLiεi is defined as
λUFLiεi = g −1 i (sign(gi(0)) min(εi, |gi(0)|)) (6)
and gi(λ) = ∫ [η−1( 12− λ 2(1−q) ),+∞) dP(i)0 − ∫ [η−1( 12 + λ 2q ),+∞) dP(i)1 . Note that gi(λ) is the mean difference on ith client Ex∼P(i)0 f(x, 0)− Ex∼P(i)1 f(x, 1) of the classifier of the form (4). Now, the demographic disparity for fUFLε0,ε1 can be written as
DP Disp(fUFLε0,ε1) = ∣∣∣∣∣12 1∑ i=0 [P(ŷ = 1 | a = 0, i = i)− P(ŷ = 1 | a = 1, i = i)] ∣∣∣∣∣
= ∣∣∣∣∣∣14 1∑
i,j=0
[ E
x∼P(i)0 f εj j (x, 0)− Ex∼P(i)1 f εj j (x, 1) ]∣∣∣∣∣∣ = |1
4
( g0(λ UFL0 ε0 ) + g0(λ UFL1 ε1 ) + g1(λ UFL0 ε0 ) + g1(λ UFL1 ε1 ) ) |.
For ease of notation, we define local mean difference on ith client as MDi(f) = P(ŷ = 1 | a = 0, i = i) − P(ŷ = 1 | a = 1, i = i) and local demographic disparity on ith client as
DP Dispi(f) = |MDi(f)|, where i = 0, 1. Since the overall distribution of the data samples is x | a = a ∼ Pa = P(0)a /2 + P(1)a /2, a = 0, 1, g (see the definition of g in Lemma 5) and g0, g1 has the following relation:
g(λ) = 1
2 g0(λ) +
1 2 g1(λ).

heading: A.2.2 LIMITATION OF UFL
text: In this section, we mainly analyze the limitation of UFL in Lemma 8, which shows that fUFLε0,ε1 can not achieve 0 demographic disparity in certain cases. Corollary 9 is a specific example of Lemma 8. Lemma 8 (Formal version of Lemma 1 under two clients cases). Let q ∈ (0, 1). Let c = min{|g0(0)|, |g1(0)|}. Define ψ : [0, c]× [0, c]→ [−1, 1] as
ψ(ε0, ε1) = MD(fUFLε0,ε1) = 1
4 g0(g
−1 1 (sign(g1(0))ε1)) +
1 4 g1(g −1 0 (sign(g0(0))ε0))
+ 1
4 sign(g0(0))ε0 +
1 4 sign(g1(0))ε1.
(7)
If g0(0)g1(0) < 0 and ψ(ε0, ε1)(g0(0) + g1(0)) > 0 for all ε0, ε1 ∈ [0, c], then for all ε0, ε1 ∈ [0, 1], DP Disp(fUFLε0,ε1) ≥ δ = min{|ψ(ε0, ε1)| : ε0, ε1 ∈ [0, c]} > 0.
Proof. Define δ = min{|ψ(ε0, ε1)| : ε0, ε1 ∈ [0, c]}. The goal is to show that the demographic disparity has a positive lower bound. Note that the mean difference can be expressed as
MD(fUFLε0,ε1) = 1
4
( g0(λ UFL0 ε0 ) + g0(λ UFL1 ε1 ) + g1(λ UFL0 ε0 ) + g1(λ UFL1 ε1 ) ) . (8)
In the following proof, we will show, the mean difference cannot reach 0.
Without any loss of generality, assume |g0(0)| < |g1(0)|. First we consider g1(0) > 0. We will discuss g1(0) < 0 later. By g0(0)g1(0) < 0 and ψ(ε0, ε1)(g0(0) + g1(0)) > 0 for all ε0, ε1 ∈ [0, c], we have g0(0) < 0 and ψ(ε0, ε1) > 0 for all ε0, ε1 ∈ [0, c]. First, we will prove that UFL achieves its lowest mean difference when ε0, ε1 ∈ [0, c]. In what follows, we consider five different cases to derive the desired result.
Case 1. ε0 > |g0(0)|, ε1 > |g1(0)|: ERM is fair on both clients.
By (6), we have λUFL0ε0 = λ UFL1 ε1 = 0. Recall gi(·) is a monotone increasing function, we combine g1(0) > 0 and Lemma 7 to have g0(g−11 (0)) < g0(0) < 0. Applying the above conclusion yields
(8) = 1
2 g0(0) +
1 2 g1(0) > 2
( 1
4 g0(0) +
1 4 g1(0) + 1 4 g0(g −1 1 (0))
) = 2ψ(g0(0), 0) ≥ δ.
Case 2. ε0 ≤ |g0(0)|, ε1 > |g1(0)|: ERM is unfair on client 0, but fair on client 1.
Applying (6) results in λUFL1ε1 = 0. By the fact that gi(·) is a strictly monotone increasing function, we have λUFL0ε0 = g −1 0 (−ε0) > g−10 (g0(0)) = 0. Applying the above conclusion yields
(8) =− 1 4 ε0 + 1 4 g1(0) + 1 4 g0(0) + 1 4 g1(λ UFL0 ε0 ) ( λUFL0ε0 > 0, g1(λ UFL0 ε0 ) > g1(0), g0(0) < −ε0 ) > 1
2 g0(0) +
1 2 g1(0) > 2ψ(g0(0), 0) ≥ δ.
Case 3. ε0 ≤ |g0(0)|, ε1 ≤ |g1(0)|: ERM is unfair on both client 0 and client 1.
Applying (6) we have λUFL0ε0 = g −1 0 (−ε0), λUFL1ε1 = g−11 (ε1). Then we have
(8) = 1
4
( −ε0 + ε1 + g0(g−11 (ε1)) + g1(g−10 (−ε0)) ) ≥ 1
4
( −ε0 + ε0 + g0(g−11 (ε0)) + g1(g−10 (−ε0)) ) = ψ(ε0, ε0) ≥ δ.
Case 4. ε0 > |g0(0)|, ε1 ≤ |g0(0)|: ERM is fair on client 0 and very unfair on client 1.
By (6), we have λUFL0ε0 = 0, λ UFL1 ε1 = g −1 1 (ε1) > g −1 1 (0). Then we obtain
(8) = 1
4
( g0(0) + g0(λ UFL1 ε1 ) + g1(0) + ε1 ) > (g0(0) + g0(g −1 1 (0)) + g1(0))/4 = ψ(g0(0), 0) ≥ δ.
Case 5. ε0 > |g0(0)|, |g0(0)| ≤ ε1 < |g1(0)|: ERM is fair on client 0 and unfair on client 1.
Applying (6) implies λUFL1ε1 = g −1 1 (ε1) > g −1 1 (0). Therefore,
(8) = 1
4
( g0(0) + g0(g −1 1 (ε1)) + ε1 + g1(0) ) > (g0(0) + g1(0) + g0(g −1 1 (0)) + ε1)/4 > ψ(g0(0), 0) ≥ δ.
Combining all the cases above, we conclude that when g1(0) > 0 DP Disp(fUFLε0,ε1) ≥ δ = min{|ψ(ε0, ε1)| : ε0, ε1 ∈ [0, c]} > 0 for all ε0, ε1 ∈ [0, 1]. Now we consider g1(0) < 0, by the setting |g0(0)| < |g1(0)| and the assumption g0(0)g1(0) < 0 and ψ(ε0, ε1)(g0(0) + g1(0)) > 0, we have g0(0) > 0 and ψ(ε0, ε1) < 0 for all ε0, ε1 ∈ [0, c]. Following similar computation above, Case 1 - Case 5 become:
Case 1. ε0 > |g0(0)|, ε1 > |g1(0)|. Now we have 0 < g0(0) < g0(g−11 (0)), thus
(8) < 2
( 1
4 g0(0) +
1 4 g1(0) + 1 4 g0(g −1 1 (0))
) = 2ψ(g0(0), 0) ≤ −δ.
Case 2. ε0 ≤ |g0(0)|, ε1 > |g1(0)|. Now we have g0(0) > ε0, g1(λUFL0ε0 ) < g1(0), thus
(8) < 1
2 g0(0) +
1 2 g1(0) < 2ψ(g0(0), 0) ≤ −δ.
Case 3. In this case we have
(8) = 1
4
( ε0 − ε1 + g0(g−11 (−ε1)) + g1(g−10 (ε0)) ) = ψ(ε0, ε1) ≤ −δ.
Case 4. Now we have λUFL1ε1 = g −1 1 (−ε1) < g−11 (0), thus
(8) < (g0(0) + g0(g −1 1 (0)) + g1(0))/4 = ψ(g0(0), 0) ≤ −δ.
Case 5. Now we have λUFL1ε1 = g −1 1 (−ε1) < g−11 (0), thus
(8) = (g0(0) + g1(0) + g0(g −1 1 (0))− ε1)/4 < ψ(g0(0), 0) ≤ −δ.
Then we conclude the proof.
Remark 5. Note that c is the smallest local demographic disparity the ERM achieves on clients. The condition g0(0)g1(0) < 0 implies that the ERM is favoring different groups in different clients. The condition ψ(ε0, ε1)(g0(0) + g1(0)) > 0 for all ε0, ε1 ∈ [0, c] implies that fUFLε0,ε1 favors the same group as ERM when the constraint is very tight. If the conditions above hold, Lemma 8 suggests that there exists a lower bound of all the demographic disparity that UFL can achieve. In particular, if the conditions above hold, UFL fails to achieve perfect demographic parity.
Among the conditions of Lemma 8, g0(0)g1(0) < 0 can be satisfied by the distribution with high data heterogeneity. To demonstrate the condition ψ(ε0, ε1)(g0(0) + g1(0)) > 0 for all ε0, ε1 ∈ [0, c] can be satisfied, we consider a limiting Gaussian case. The following corollary serves as an example that satisfies the conditions of Lemma 8, and provides a more explicit expression of the lowest demographic disparity UFL can reach in the Gaussian case.
Corollary 9 (Formal version of Corollary 2). Let q = 0.5, η(x) = 11+e−x ,P (i) a = N (µ(i)a , σ(i)2) where (µ(0)0 − µ (0) 1 )(µ (1) 0 − µ (1) 1 ) < 0. Then DP Disp(f UFL ε0,ε1) ≥ δ ≈ 14 |g0(0) + g1(0)| > 0 for all ε0, ε1 ∈ [0, 1] if one of the following condition holds:
1. σ(0) σ(1), |µ(0)0 |, |µ (0) 1 |, |µ (1) 0 |, |µ (1) 1 | and µ (1) 0 > µ (1) 1 : client 0 has much larger variance
than client 1, and client 1 is favoring group 0;
2. σ(1) σ(0), |µ(0)0 |, |µ (0) 1 |, |µ (1) 0 |, |µ (1) 1 | and µ (0) 0 > µ (0) 1 : client 1 has much larger variance
than client 0, and client 0 is favoring group 0.
Proof. In this example, note that local mean difference function of λ can be written as:
gi(λ) = Φ( η−1( 12 + λ)− µ (i) 1
σ(i) )− Φ(η
−1( 12 − λ)− µ (i) 0
σ(i) ), (9)
where Φ(·) is the CDF of the standard Gaussian distribution. We only provide the proof for condition 1, and the proof for condition 2 is similar. Assume condition 1 holds. By (µ(0)0 − µ (0) 1 )(µ (1) 0 − µ (1) 1 ) < 0 and µ (1) 0 − µ (1) 1 > 0, we have µ (0) 0 − µ (0) 1 < 0. By (9), we have g0(0) < 0 and g1(0) > 0. Consequently, combining Lemma 7 and (7) yields
ψ(ε0, ε1) = 1
4
( g0(g −1 1 (ε1)) + g1(g −1 0 (−ε0))− ε0 + ε1 ) .
First we show that ψ(ε0, ε1) reachs its minimum either at (c, 0) or (0, c) by taking the derivative of ψ, where c = min{|g0(0)|, |g1(0)|} is the smallest local demographic disparity. And then, we will estimate the minimum of ψ on [0, 1]× [0, 1]. We take the derivative of ψ with respect to εi and get
∂ψ ∂εi (ε0, ε1) = sign(gi(0))
( 1 + g′1−i(g −1 i (sign(gi(0))εi))
g′i(g −1 i (sign(gi(0))εi))
) /4.
By condition 1, we have g0(0) = Φ(−µ (0) 1 σ(0) )−Φ(−µ (0) 0 σ(0) ) ≈ 0, thus |g0(0)| |g1(0)| and c = |g0(0)|. Since gi are increasing function, i = 0, 1, we have g′i(·) > 0, and thus ∂ψ∂ε0 < 0, ∂ψ ∂ε1
> 0. Therefore, ψ reaches its extreme value at (0, c) and (c, 0).
Now, we evaluate
ψ(0, c) = (g0(g −1 1 (c)) + g1(g −1 0 (0))− g0(0))/4 > g1(0)− g0(0) + g0(g−11 (c)) 4 ,
where the inequality comes from g0(0) < 0 to have g1(g−10 (0)) > g1(0). And at (c, 0), we have
ψ(c, 0) = (g0(g −1 1 (0)) + g1(0) + g0(0))/4.
In what follows, we will show that min {ψ(c, 0), ψ(0, c)} ≈ δ = g1(0)+g0(0)4 by proving that 0 > g0(g −1 1 (c)) > g0(g −1 1 (0)) ≈ 0.
Consider ψ(c, 0) and ψ(0, c). Since g1(0) > c, g0(0) < 0, we have
g0(g −1 1 (0)) < g0(g −1 1 (c)) < g0(0) < 0.
Therefore, the only thing left is to show g0(g−11 (0)) ≈ 0. We divide the rest of the proof into the following three cases.
Case 1. µ(1)1 < µ (1) 0 < 0: on client 1, the local classifier is favoring group 0 over group 1, and the positive rate of both groups are under 12 .
Clearly, under this case, we have ∫
[η−1( 12 ),∞) dP(1)0 = ∫ [0,∞) dP (1) 0 < 1 2 . We select λ ′ < 0 such
that η−1( 12 + λ ′) = µ (1) 1 . Then we have ∫ [η−1( 12 +λ ′),∞) dP (1) 1 = ∫ [µ (1) 1 ,∞)
dP(1)1 = 12 , while∫ [η−1( 12− λ′ 2(1−q) ),∞)
dP(1)0 < 0. Thus we get g1(λ′) < 0. Combining g1(0) > 0 and intermediate value theorem results in λ′ < g−11 (0) < 0. Then we obtain
µ (1) 1 = η
−1( 1
2 + λ′) < η−1(
1 2 + g−11 (0)) < 0
−µ(1)1 = η−1( 1 2 − λ′) > η−1(1 2 − g−11 (0)) > 0 (η(x)− 1 2 is odd)
. (10)
By plugging (10) into (9), we have the other side of g0(g−11 (0)) < 0 is bounded by g0(λ ′) = Φ( µ (1) 1 −µ (1) 1
σ(1) )− Φ(−µ (1) 1 −µ (1) 0 σ(1) ). Since σ(1) |µ(1)1 |, |µ (0) 1 |, we get g0(g−11 (0)) ≈ 0.
Case 2. 0 < µ(1)1 < µ (1) 0 : on client 1, the local classifier is favoring group 0 over group 1, and the positive rate of both groups are above 12 .
This proof of this case is similar to Case 1.
Case 3. µ(1)1 < 0 < µ (1) 0 : with respect to the local classifier trained by client 1, the positive rate of group 0 is above 12 while that of group 1 is under 1 2 .
Without any loss of generality, we assume |µ(1)1 | < |µ (1) 0 |. Select λ′′ < 0 such that η( 12 −λ′′) = µ (1) 0 . Clearly ∫
[η−1( 12−λ′′),+∞) dP(1)0 = ∫ [µ (1) 0 ,+∞)
dP(1)0 = 12 , while∫ [η−1( 12 +λ ′′),+∞) dP(1)1 = ∫ [−µ(1)0 ,+∞) dP(1)1 > ∫ [−µ(1)1 ,+∞) dP(1)1 > 1 2 .
Consequently, we get g1(λ′′) < 0 and λ′′ < g−11 (0) < 0. Then we draw the same conclusion as (10). Therefore, g0(g−11 (0)) ≈ 0. Combining all three cases above, we get δ > 0. Then applying Lemma 8 we complete the proof.

heading: A.2.3 COMPARISON BETWEEN UFL AND CFL
text: In this section, we compare the performance of UFL and CFL. In Lemma 10 and Lemma 11, we illustrate the conditions for UFL to have the same performance as CFL. In Lemma 12, Lemma 13 and Lemma 14, we illustrate the scenarios when CFL outperforms UFL.
To do the comparison, first we introduce some additional notations. Define the accuracy of a classifier f as
Acc(f) = P(ŷ = y) = P(y = 0)Ex,a|y=0[1− f(x, a)] + P(y = 1)Ex,a|y=0f(x, a).
Given the required global demographic disparity ε, define the performance of fUFLε0,ε1 as:
UFL(ε0, ε1; ε) = { Acc(fUFLε0,ε1) DP Disp(f UFL ε0,ε1) ≤ ε
0 o.w. ,
and define performance of fCFLε as:
CFL(ε) = Acc(fCFLε ).
Now we are able to compare the performance between UFL and CFL with the metric UFL(ε0, ε1; ε) and CFL(ε). In particular, we will show that, under some mild conditions, maxε0,ε1 UFL(ε0, ε1; ε) < CFL(ε), which implies the gap between UFL and CFL is inevitable.
We begin with the following two lemmas, which describe the cases that UFL(ε0, ε1; ε) = CFL(ε).
Lemma 10. Let q ∈ (0, 1). Given an UFL classifier fUFLε0,ε1 such that DP Disp(fUFLε0,ε1) ≤ ε and a CFL classifier fCFLε , we have UFL(ε0, ε1; ε) ≤ CFL(ε). The equality holds if and only if λUFL0ε0 = λUFL1ε1 = λ CFL ε , where λ CFL ε is defined in (5), λ UFL0 ε0 , λ UFL1 ε1 are defined in (6).
Proof. The proof is straightforward. Clearly, since fCFLε is the optimizer to CFL(ε), we have UFL(ε0, ε1; ε) ≤ CFL(ε). By Lemma 5, according to the form of the solution to CFL(ε), fUFLε0,ε1 is the solution to CFL(ε) if and only if λUFL0ε0 = λ UFL1 ε1 = λ CFL ε . Thus complete the proof.
Lemma 11. Let q ∈ (0, 1). If the ERM is already fair, i.e., ε ≥ |g(0)|, then max ε0,ε1 UFL(ε0, ε1; ε) = CFL(ε).
Proof. Since the ERM is already fair, fCFLε is ERM= Jη(x) > 1/2K. Therefore, we take ε0 = ε1 = 1, and fUFLε0,ε1 also equals to ERM. Thus we conclude the lemma.
The next two lemmas describes the cases that UFL(ε0, ε1; ε) < CFL(ε).
Lemma 12. Let q ∈ (0, 1). If g0(0)g1(0) < 0, maxε0,ε1 UFL(ε0, ε1; ε) < CFL(ε) for all ε < |g(0)|.
Proof. In this proof, we only consider the case that g1(0) > 0, |g1(0)| ≥ |g0(0)|. The proof for g1(0) > 0 or |g1(0)| ≥ |g0(0)| is similar. Next, we divide the proof into two cases. Case 1. maxε0,ε1 UFL(ε0, ε1; ε) = 0: UFL cannot achieve ε global demographic disparity.
The conclusion holds.
Case 2. maxε0,ε1 UFL(ε0, ε1; ε) > 0: UFL can achieve ε global demographic disparity.
Since ε < |g(0)|, by Lemma 7, we have λCFLε 6= 0. Next, we solve fUFLε0,ε1 by solving the local version of CFL(ε). Combining Lemma 7, g1(0) > 0 and g0(0) < 0 yields λUFL0ε0 ≥ 0, λUFL1ε1 ≤ 0. If λUFL0ε0 = λ UFL1 ε1 , then λ UFL0 ε0 = λ UFL1 ε1 = 0 6= λCFLε . Thus, we conclude the lemma by applying Lemma 10.
Remark 6. Lemma 12 implies that if ERM is favoring different groups in different clients, there exists an inevitable gap between the performance of UFL and that of CFL.
Lemma 13. Let q ∈ (0, 1). Let τ = min { |g(0)|,max{sign(g(0))g(g−10 (0)), sign(g(0))g(g−11 (0))} } .
If g0(0)g1(0) > 0, we have
max ε0,ε1
UFL(ε0, ε1; ε) {
= CFL(ε) for all ε ≥ τ < CFL(ε) o.w. .
Proof. Without any loss of generality, assume g0(0), g1(0) > 0. Then by Lemma 7, we have λUFL0ε0 ≤ 0, λUFL1ε1 ≤ 0 for all ε0, ε1 ∈ [0, 1], and g(0) = (g0(0) + g1(0))/2 > 0. To study the performance of UFL when g0(0)g1(0) < 0, recall that we use fεii to denote the local classifier trained by client i in UFL analysis. Therefore, f0i is the local classifier trained by client i that achieves perfect local fairness.
Next, we discuss two cases to prove the result. In Case 1, we will show that τ = 0, and then prove that maxε0,ε1 UFL(ε0, ε1; ε) = CFL(ε); in Case 2, we will show that τ > 0, and then prove that maxε0,ε1 UFL(ε0, ε1; ε) < CFL(ε) when ε < τ .
Case 1. f00 = f01 : the two local classifiers that achieve perfect local fairness are equal.
When ε ≥ g(0), the conclusion holds by directly applying Lemma 11. Therefore, in what follows, we focus on the case that ε < g(0).
Next, we will first, show that when ε = 0, λUFL00 = λ UFL1 0 = λ CFL 0 , which implies that f 0 0 = f 0 1 = fCFL0 .
Since f00 = f 0 1 , we have λ UFL0 0 = λ UFL1 0 , and thus g −1 0 (0) = g −1 1 (0). Consequently, we get
g(λUFL00 ) = g(λ UFL1 0 ) = g(g −1 0 (0)) =
g0(g −1 0 (0)) + g1(g −1 1 (0))
2 = 0 = g(λCFL0 ).
By the monotonicity of g, we have λUFL00 = λ UFL1 0 = λ CFL 0 and τ = 0. Next, we will show that, for ε 6= 0, there also exists ε0, ε1 ∈ [0, 1] such that λUFL0ε0 = λUFL1ε1 = λCFLε , which implies fUFL0ε0 = f UFL1 ε0 = f CFL ε .
Consider ε 6= 0. Select εi = gi(λCFLε ), i = 0, 1. By Lemma 5 and the monotonicity of g, we have λCFL0 < λ CFL ε < 0. Therefore, εi = gi(λ CFL ε ) > gi(λ CFL 0 ) = 0. By Lemma 5, we get λUFLiεi = g −1 i (εi) for i = 0, 1. By the selection of εi, we have λ CFL ε = g −1 i (εi). Therefore, λCFLε = λ UFL0 ε0 = λ UFL1 ε1 when ε 6= 0.
Combining all the discussion above yields fUFLε0,ε1 = f CFL ε for all ε < g(0), thus we conclude maxε0,ε1 UFL(ε0, ε1; ε) = CFL(ε) for all ε < g(0). Consequently, the lemma holds under Case 1.
Case 2. f00 6= f01 : the two local classifiers that achieve perfect local fairness are different.
The key idea of this proof is: when MD0(fCFLε ),MD1(f CFL ε ) ≥ 0, then we can always select ε0 = g0(λCFLε ) = MD0(f CFL ε ) > 0, ε1 = g1(λ CFL ε ) = MD1(f CFL ε ) > 0 such that λUFL0ε0 = g −1 0 (ε0) = λ CFL ε and λ UFL1 ε1 = g −1 1 (ε1) = λ CFL ε , thus f UFL ε0,ε1 = f CFL ε ; when MD0(fCFLε )MD1(f CFL ε ) = g0(λ CFL ε )g1(λ CFL ε ) < 0, however, by Lemma 7, for all ε0, ε1 ∈ [0, 1] × [0, 1], we have g0(λUFL0ε0 )g1(λUFL1ε1 ) > 0 > g0(λCFLε )g1(λCFLε ), thus there exist i ∈ {0, 1} such that λUFLiεi 6= λCFLε and fUFLε0,ε1 6= fCFLε . Next, we will give rigorous proof.
Since f00 6= f01 , we have λUFL00 6= λUFL10 . By Lemma 5, we get g−10 (0) 6= g−11 (0). Without any loss of generality, assume g−10 (0) < g −1 1 (0), which implies g1(g −1 0 (0)) < g1(g −1 1 (0)) = 0 and g0(g −1 0 (0)) = 0 < g0(g −1 1 (0)). Thus we get
g1(g −1 0 (0)) < 0 < g0(g −1 1 (0)).
Combining the inequality above and g = g0+g12 yields
g(g−10 (0)) = g1(g −1 0 (0)) < 0 = g(g −1(0)) < g0(g −1 1 (0)) = g(g −1 1 (0)). (11)
Thus we have τ = max{sign(g(0))g(g−10 (0)), sign(g(0))g(g−11 (0))} = g(g−11 (0)).
When ε ≥ |g(0)|, by Lemma 11, clearly we have maxε0,ε1 UFL(ε0, ε1; ε) = CFL(ε). For the other case ε < |g(0)|, by Lemma 7 we have λ = g−1(ε). Similar to Case 1, in order to achieve λUFL0ε0 = λ UFL1 ε1 = λ CFL ε , we select εi = gi(λ CFL ε ).
When ε < g(g−11 (0)),
g1(λ CFL ε ) = g1(g −1(ε)) < g1(g −1(g(g−11 (0)))) = 0.
Since g1(0) > 0, by Lemma 7 we have g1(λUFL1ε1 ) ≥ 0, from the monotonicity of g1 we conclude λUFL1ε1 6= λCFLε . By Lemma 10, we have maxε0,ε1 UFL(ε0, ε1; ε) < CFL(ε) for all ε ≤ τ . When ε ≥ g(g−11 (0)), applying (11) we have
gi(0) > εi = gi(λ) = gi(g −1(ε)) ≥ gi(g−1(g(g−1i (0)))) = 0,
where the first inequality comes from Case 1. Thus, λi = g−1(εi) = λ as desired, and we obtain fUFLε0,ε1 = f CFL ε .
Combining both cases above yields the desired conclusion.
Remark 7. Recall that we use fεii to denote the local classifier trained by client i in UFL analysis. In the expression of τ :
min { |g(0)|,max{sign(g(0))g(g−10 (0)), sign(g(0))g(g−11 (0))} } ,
|g(0)| is the demographic disparity of ERM, sign(g(0))g(g−10 (0)) is the demographic disparity of local classifier f00 , and sign(g(0))g(g −1 1 (0)) is the demographic disparity of local classifier f 0 1 . According to the proof of Lemma 13, we obtain max{sign(g(0))g(g−10 (0)), sign(g(0))g(g−11 (0))} > 0 if and only if two local classifiers which achieves perfect local fairness is equal, i.e., f00 = f 0 1 . Therefore, Lemma 13 implies that, if the ERM is favoring the same group on different clients and the two local classifiers which achieve perfect local fairness are unequal, then UFL performs strictly worse than CFL when the required demographic disparity is smaller than a certain value.
So far we assume a ∼ Bern(q) for both client 0 and client 1. When both clients do not share the same q, we can conclude that CFL outperforms UFL in the following lemma. Lemma 14. Assume a ∼ Bern(qi) in client i, and q0 6= q1 ∈ (0, 1). Then maxε0,ε1 UFL(ε0, ε1; ε) < CFL(ε) for all ε < |g(0)|.
Proof. We assemble the dataset from two clients to have x | a = a ∼ Pa = q0q0+q1P (0) a + q1 q0+q1 P(1)a , a = 0, 1. We let fCFLε be the solution to CFL(ε), with q = q0+q1 2 :
fCFLε = Js(x, a) > 0K,
where s(x, 0) = 2η(x)− 1 + λ CFL ε 1− q , s(x, 1) = 2η(x)− 1− λCFLε q .
Given an UFL classifier fUFLε0,ε1 = (f ε0 0 + f ε1 1 )/2 such that DP Disp(f UFL ε0,ε1) ≤ ε, the solution reads
fεii = Jsi(x, a) > 0K,
where si(x, 0) = 2η(x)− 1 + λUFLiεi 1− qi , si(x, 1) = 2η(x)− 1− λUFLiεi qi .
We prove the lemma by contradiction argument. If Acc(fUFLε0,ε1) = CFL(ε), then f UFL ε0,ε1 is a solution to CFL(ε) with q = q0+q12 . Since ε < |g(0)|, by Lemma 7 we have λCFLε 6= 0. Without any loss of generality, assume λCFLε < 0. Below we discuss three cases.
Case 1. λUFL0ε0 = λ UFL1 ε1 = 0: the UFL classifier is ERM.
In this case, fε00 = f ε1 1 . We have f UFL ε0,ε1(x, 0) = 1 for η(x) > 1 2 , and f CFL ε = 0 for η(x) < (1− λCFLε /(1− q))/2. By Lemma 6, fUFLε0,ε1 is not a solution to CFL(ε). Case 2. λUFL0ε0 6= 0 or λUFL1ε1 6= 0, and λUFL0ε0 λUFL1ε1 = 0: the UFL classifier is not ERM, but one of the local classifier is ERM.
Without any loss of generality, let λUFL0ε0 = 0, λ UFL1 ε1 < 0. Then f ε0 0 (x, 0) = 1 for η(x) > 1 2 , while fε11 (x, 0) = 0 for η(x) < (1− λUFL0ε0 (1− q1))/2. Thus we get
fUFLε0,ε1(x, 0) = 1
2 for
1 2 < η(x) < (1− λUFL1ε1 (1− q1))/2.
By Lemma 6, fUFLε0,ε1 is not a solution to CFL(ε).
Case 3. λUFL0ε0 λ UFL1 ε1 6= 0: The local classifiers are not ERM.
When λUFL0ε0 1−q0 6= λUFL1ε1 1−q1 , without loss of generality, let λUFL0ε0 1−q0 > λUFL1ε1 1−q1 . Then by the same argument in Case 2, we have
fUFLε0,ε1(x, 0) = 1
2 for
1− λ UFL0 ε0
1−q0 2
< η(x) < 1− λ
UFL1 ε1 1−q1 2 .
By Lemma 6, fUFLε0,ε1 is not a solution to CFL(ε).
When λUFL0ε0 q0 6= λ UFL1 ε1 q1 , similarly, fUFLε0,ε1 is not a solution to CFL(ε).
When λUFL0ε0 q0 = λUFL1ε1 q1 and λUFL0ε0 1−q0 = λUFL1ε1 1−q1 , since λ UFL0 ε0 λ UFL1 ε1 6= 0, we have
q0
λUFL0ε0 =
q1
λUFL1ε1 , 1− q0 λUFL0ε0 = 1− q1 λUFL1ε1 ,
which leads to 1 λ
UFL0 ε0
= 1 λ
UFL1 ε1
and thus q0 = q1. This contradicts with the assumption that q0 6= q1.
Combining all three cases yields desired conclusion.

heading: A.3 FFL VIA FEDAVG ANALYSIS
text: In this section, we analyze FFL via FEDAVG for the case of two clients. For purpose of illustration, with I = 2, we denote fFFL via FedAvgε0,ε1 = f FFL via FedAvg ε to be the solution to FFL via FEDAVG(ε). In Sec. A.3.1, we present a formal version of Thm. 3 and show that compared to UFL, FFL via FEDAVG has strictly higher fairness. In Sec. A.3.2 we derive the solution to FFL via FEDAVG(ε), and show it is equivalent to FFL via FEDAVG. In Sec. A.3.3, we analyze the limitation of FFL via FEDAVG and present a formal version of Lemma 4.
A.3.1 IMPROVE FAIRNESS VIA FEDERATED LEARNING
Different to UFL, FFL via FEDAVG can reach any ε demographic disparity: Theorem 15 (Formal version of Thm. 3 under two clients cases). Let q ∈ (0, 1). For all ε ∈ [0, 1], there exists ε0, ε1 ∈ [0, 1] such that DP Disp(fFFL via FedAvgε0,ε1 ) ≤ ε. Thus under the condition in Lemma 8, we have
min ε0,ε1∈[0,1] DP Disp(fUFLε0,ε1) > minε0,ε1∈[0,1] DP Disp(fFFL via FedAvgε0,ε1 ) = 0.
Proof. For any ε ∈ [0, 1], let ε0 = ε1 = ε. Then the global DP disparity becomes DP Disp(fFFL via FedAvgε0,ε1 ) = |Ex|a=0f(x, 0)− Ex|a=1f(x, 1)|
= |( ∫ X f(x, 0) dP(0)0 + ∫ X f(x, 0) dP(1)0 )/2
− ( ∫ X f(x, 1) dP(0)1 + ∫ X f(x, 1) dP(1)1 )/2| = |MD0(fFFL via FedAvgε0,ε1 )/2 + MD1(fFFL via FedAvgε0,ε1 )/2| ≤ DP Disp0(fFFL via FedAvgε0,ε1 )/2 + DP Disp1(fFFL via FedAvgε0,ε1 )/2 ≤ (ε0 + ε1)/2 = ε.

heading: A.3.2 THE BEST CLASSIFIER OF FFL VIA FEDAVG
text: For FFL via FEDAVG, we directly consider multi-client cases. To visualize the gap between UFL, FFL via FEDAVG, and CFL, in our numerical experiments, we draw finite samples from Gaussian distribution, and then we optimize the empirical risk with the fairness constraint to obtain the classifier trained by FFL via FEDAVG. The following lemma provides the solution to FFL via FEDAVG(ε) when X is finite. Lemma 16. For finite X , the solution to FFL via FEDAVG(ε) is given by
f(x, a) = J ∑ i∈[I] si(x, a)p (i) a (x) > 0K,
where si(x, a) = 2η(x)− 1 + Iλi Ja=0K1−q − Iλi Ja=1K q , for certain λ0, . . . λI−1 ∈ R.
Proof. This proof is based on Menon & Williamson (2018). The key idea of this proof is to use the Lagrangian approach. Before we applying the Lagrangian approach, we will show that FFL via FEDAVG(ε) is expressible as a linear program, and thus the strong duality holds.
Since X is finite, f is a vector of finite dimension. Based on the proof of Lemma 5, the error rate can be written as
P(ŷ 6= y) = ∑
x∈X ,a∈A f(x, a)(1− 2η(x))P(x = x, a = a) + P(y = 1),
and the fairness constraints can be written as
P(ŷ = 1 | a = 0, i = i)− P(ŷ = 1 | a = 1, i = i) = ∑ x∈X [ f(x, 0) P(x = x | a = 0, i = i) P(a = 0) − f(x, 1)P(x = x | a = 1, i = i) P(a = 1) ] ,
for i ∈ [I]. Let u(x, a) = (1 − 2η(x))P(x = x, a = a), u′ = P(y = 1), and vi(x, a) = (Ja = 0K− Ja = 1K)P(x = x | a = a, i = i)/P(a = a), for x ∈ X , a ∈ A, i ∈ [I]. Note that u, v0, v1 are vectors of the same dimension of f . For ease of notation, we allow ≤ to be applied to pairs of vectors in an element-wise manner. Therefore, the optimization is
min f
u>f + u′
s.t. v>i f ≤ εi 0 ≤ f ≤ 1,
which is a linear objective with linear constraint. Therefore, the strong duality holds for FFL via FEDAVG(ε). Next, we apply Lagrangian approach to solve the FFL via FEDAVG(ε).
Recall that
P(ŷ 6= y) =1 I EaEx∼P(i)a f(x, a)(1− 2η(x)) + P(y = 1),
and P(ŷ = 1 | a = 0, i = i)− P(ŷ = 1 | a = 1, i = i)
=EaEx∼P(i)a
[ f(x, 0)
Ja = 0K 1− q − f(x, 1) Ja = 1K q
] .
By strong duality, for λ′0, . . . , λ ′ 2I−1 ≥ 0, the corresponding Lagrangian version of FFL via FEDAVG(ε) is
min f∈F P(ŷ 6= y)− ∑ i∈[I] [ λ′2i[P(ŷ = 1 | a = 0, i = i)− P(ŷ = 1 | a = 1, i = i)− εi] (12)
+ λ′2i+1[εi − P(ŷ = 1 | a = 0, i = i)− P(ŷ = 1 | a = 1, i = i)] ]
Let λi = λ′2i − λ′2i+1, i ∈ [I], then we get
(12) = min f∈F EaEx∼P(i)a
[ 1
I f(x, a)(1− 2η(x))− ∑ i∈[I] ( λif(x, 0) Ja = 0K 1− q − λif(x, 1) Ja = 1K q )]
= min f∈F ∫ X ∑ a∈A −1 I f(x, a)[ ∑ i∈[I] si(x, a)p (i) a (x)]dx.
where si is defined in Lemma 16. Thus the above equation reaches its minimum at f(x, a) = J ∑ i∈[I] si(x, a)p (i) a (x) > 0K.
Remark 8. Based on the proof of Lemma 16, FFL via FEDAVG(ε) is equivalent to solving
min f∈F P(ŷ 6= y)− I−1∑ i=0 λi(P(ŷ = 1 | a = 0, i = i)− P(ŷ = 1 | a = 1, i = i)).
Under certain conditions (assumptions 1 to 4 in Li et al. (2020b)), we have solving FFL via

heading: FEDAVG(ε) is equivalent to minimizing
text: P(ŷ 6= y | i = i)− λi(P(ŷ = 1 | a = 0, i = i)− P(ŷ = 1 | a = 1, i = i)) locally and applying FEDAVG (Theorem 1 in Li et al. (2020b)).

heading: A.3.3 COMPARISON OF FFL VIA FEDAVG AND CFL
text: Lemma 17 (Formal version of Lemma 4 under two clients cases). When a | i = 0 ∼ Bern(0), a | i = 1 ∼ Bern(1) and DP Disp(fCFL1 ) > 0, we have
min ε0,ε1
DP Disp(fFFL via FedAvgε0,ε1 ) = DP Disp(f CFL 1 ) > min ε DP Disp(fCFLε ) = 0.
Proof. Since a | i = 0 ∼ Bern(0), a | i = 1 ∼ Bern(1), the constraints in FFL via FEDAVG(ε) vanish. When ε = 1, the constraint in CFL(ε) always holds and thus also vanishes. Thus in such scenario the solution to FFL via FEDAVG(ε) becomes fCFL1 . Then from the assumption we have
DP Disp(fFFL via FedAvgε0,ε1 ) = DP Disp(f CFL 1 ) > DP Disp(f CFL 0 ) = 0.

heading: A.4 EXTENSION TO MULTI-CLIENT CASES
text: In this subsection, we perform the analysis of UFL and FFL via FEDAVG for the multi-client cases. We present a more general version of Lemma 8, Thm. 15 and Lemma 17.
The following lemma shows the fundamental limitation of UFL:
Lemma 18 (Formal version of Lemma 1). Let q ∈ (0, 1). Consider a partition which divides I clients into two subsets. Denote the mixture distribution of each subset as x | a = a, j = j ∼ P̃(j)a , where j is the index of the subset, and P̃(j)a is a distribution, for a, j = 0, 1. Similar to two clients case, define g̃j(λ) = ∫ [η−1( 12− λ 2(1−q) ),+∞) dP̃(j)0 − ∫ [η−1( 12 + λ 2q ),+∞)
dP̃(j)1 . Consider the case that qi = q for all i ∈ [I] and q ∈ (0, 1). Denote the proportion of the two subset as J0 and J1, where J0, J1 > 0 and J0 + J1 = 1. Let c = min {|g̃0(0)|, |g̃1(0)|}. Define ψ̃ : [0, c]× [0, c]→ [−1, 1] as
ψ̃(ε̃0, ε̃1) = J0J1g̃0(g̃ −1 1 (sign(g̃1(0))ε̃1)) + J0J1g̃1(g̃ −1 0 (sign(g̃0(0))ε̃0))
+ J20 sign(g̃0(0))ε̃0 + J 2 1 sign(g̃1(0))ε̃1.

heading: If there exists a partition such that g̃0(0)g̃1(0) < 0 and ψ̃(ε̃0, ε̃1)(g̃0(0) + g̃1(0)) > 0 for all ε̃0, ε̃1 ∈
text: [0, c], then for all ε̃0, ε̃1 ∈ [0, 1], DP Disp(fUFLε ) ≥ δ̃ = min{|ψ̃(ε̃0, ε̃1)| : ε̃0, ε̃1 ∈ [0, c]} > 0.
Proof. By Lemma 8, we conclude the achievable fairness range of UFL is strictly smaller than that of CFL. Therefore, pooling the datasets in one subset and perform fair learning can clearly achieve a wider range of fairness than perform fair learning on each client individually. Thus, we can consider the two subsets as two clients with uneven amounts of data, which is almost the same case Lemma 8 considers. Therefore, we follow the same proof idea as Lemma 8 to prove our claim.
Denote the assembled classifier trained from two pooled datasets as f̃UFLε̃0,ε̃1 . Note that the mean difference can be expressed as
MD(f̃UFLε̃0,ε̃1) = J 2 0 g̃0(λ̃ UFL0 ε̃0 ) + J0J1g̃0(λ̃ UFL1 ε̃1 ) + J0J1g̃1(λ̃ UFL0 ε̃0 ) + J21 g̃1(λ̃ UFL1 ε̃1 ). (13)
In the following proof, we will show, the mean difference cannot reach 0.
Without any loss of generality, assume |g̃0(0)| < |g̃1(0)| and g̃1(0) > 0. By g̃0(0)g̃1(0) < 0 and ψ̃(ε̃0, ε̃1)(g̃0(0) + g̃1(0)) > 0 for all ε̃0, ε̃1 ∈ [0, c], we have g̃0(0) < 0 and ψ̃(ε̃0, ε̃1) > 0 for all ε̃0, ε̃1 ∈ [0, c]. Without any loss of generality, assume J0 ≤ J1. First, we will prove that UFL achieves its lowest mean difference when ε̃0, ε̃1 ∈ [0, c]. In what follows, we consider five different cases to derive the desired result.
Case 1. ε̃0 > |g̃0(0)|, ε̃1 > |g̃1(0)|: ERM is fair on both clients.
By (6), we have λ̃UFL0ε̃0 = λ̃ UFL1 ε̃1 = 0. Recall g̃i(·) is a monotone increasing function, combine g̃1(0) > 0 and Lemma 7, and thus g̃0(g̃−11 (0)) < g̃0(0) < 0. Applying the above conclusion yields
(13) = J0g̃0(0) + J1g̃1(0) > 1
J1
( J20 g̃0(0) + J 2 1 g̃1(0) + J0J1g̃0(g̃ −1 1 (0)) ) = 1
J1 ψ̃(g̃0(0), 0) ≥ δ̃.
Case 2. ε̃0 ≤ |g̃0(0)|, ε̃1 > |g̃1(0)|: ERM is unfair on client 0, but fair on client 1.
Applying (6) results in λUFL1ε1 = 0. By the fact that g̃i(·) is a strictly monotone increasing function, we have λ̃UFL0ε̃0 = g̃ −1 0 (−ε̃0) > g̃−10 (g̃0(0)) = 0. Applying the above conclusion yields
(13) =− J20 ε̃0 + J21 g̃1(0) + J0J1g̃0(0) + J0J1g̃1(λ̃UFL0ε̃0 )
>J0g̃0(0) + J1g̃1(0) > 1
J1 ψ̃(g̃0(0), 0) ≥ δ̃.
In the first equality we used λ̃UFL0ε̃0 > 0, g̃1(λ̃ UFL0 ε̃0 ) > g̃1(0), g̃0(0) < −ε̃0. Case 3. ε̃0 ≤ |g̃0(0)|, ε̃1 ≤ |g̃1(0)|: ERM is unfair on both client 0 and client 1.
Applying (6) we have λ̃UFL0ε̃0 = g̃ −1 0 (−ε̃0), λ̃UFL1ε̃1 = g̃ −1 1 (ε̃1). Then we have
(13) = −J20 ε̃0 + J21 ε̃1 + J0J1g̃0(g̃−11 (ε̃1)) + J0J1g̃1(g̃−10 (−ε̃0)) ≥ −J20 ε̃0 + J21 ε̃0 + J0J1g̃0(g̃−11 (ε̃0)) + J0J1g̃1(g̃−10 (−ε̃0)) = ψ̃(ε̃0, ε̃0) ≥ δ̃.
Case 4. ε̃0 > |g̃0(0)|, ε̃1 ≤ |g̃0(0)|: ERM is fair on client 0 and very unfair on client 1.
By (6), we have λ̃UFL0ε̃0 = 0, λ̃ UFL1 ε̃1 = g̃−11 (ε̃1) > g̃ −1 1 (0). Then we obtain
(13) = J20 g̃0(0) + J0J1g̃0(λ̃ UFL1 ε̃1 ) + J0J1g̃1(0) + J 2 1 ε̃1
> J20 g̃0(0) + J0J1g̃0(g̃ −1 1 (0)) + J 2 1 g̃1(0) = ψ̃(g̃0(0), 0) ≥ δ̃.
Case 5. ε̃0 > |g̃0(0)|, |g̃0(0)| ≤ ε̃1 < |g̃1(0)|: ERM is fair on client 0 and unfair on client 1.
Applying (6) implies λ̃UFL1ε̃1 = g̃ −1 1 (ε̃1) > g̃ −1 1 (0). Therefore,
(13) =J20 g̃0(0) + J0J1g̃0(g̃ −1 1 (ε̃1)) + J 2 1 ε̃1 + J0J1g̃1(0)
> J20 g̃0(0) + J0J1g̃1(0) + J0J1g̃0(g̃ −1 1 (0)) + J 2 1 ε̃1 > ψ̃(g̃0(0), 0) ≥ δ̃.
Combining all the cases above, we conclude that when g̃1(0) > 0, DP Disp(f̃UFLε̃0,ε̃1) ≥ δ̃ = min{|ψ̃(ε̃0, ε̃1)| : ε̃0, ε̃1 ∈ [0, c]} > 0 for all ε̃0, ε̃1 ∈ [0, 1].
Remark 9. Based on the proof above, we can conclude, for the cases with multiple clients, the fundamental limitation of UFL still exists.
The following theorem shows that FFL via FEDAVG can reach any ε DP disparity: Theorem 19 (Generalized version of Thm. 15). Let qi = q ∈ (0, 1) for all i ∈ [I]. For all ε ∈ [0, 1], let εi ≤ ε for all i ∈ [I], then DP Disp(fFFL via FedAvgε ) ≤ ε. Thus under the condition in Lemma 18, we have
min ε∈[0,1]I DP Disp(fUFLε ) > min ε∈[0,1]I DP Disp(fFFL via FedAvgε ) = 0.
Proof. When εi ≤ ε the global DP disparity becomes DP Disp(fFFL via FedAvgε ) = |Ex|a=0f(x, 0)− Ex|a=1f(x, 1)|
= |( I−1∑ i=0 ∫ X f(x, 0) dP(i)0 )/I − ( I−1∑ i=0 ∫ X f(x, 1) dP(i)1 )/I|
= | I−1∑ i=0 MDi(fFFL via FedAvgε )/I| ≤ I−1∑ i=0 DP Dispi(f FFL via FedAvg ε )/I ≤ I−1∑ i=0 εi/I = ε.
The following theorem shows the limitation of FFL via FEDAVG: Lemma 20 (Generalized version of Lemma 17). Let a | i = i ∼ Bern(0) or a | i = i ∼ Bern(1) for all i ∈ [I]. When DP Disp(fCFL1 ) > 0, we have
min ε∈[0,1]I
DP Disp(fFFL via FedAvgε ) = DP Disp(f CFL 1 ) > min ε DP Disp(fCFLε ) = 0.
Proof. Since a | i = i ∼ Bern(0) or a | i = i ∼ Bern(1), the constraints in (FFL via FEDAVG(ε)) vanish. When ε = 1, the constraint in CFL(ε) always holds and thus also vanishes. Thus in such scenario the solution to (FFL via FEDAVG(ε)) becomes fCFL1 . Then from the assumption we have
DP Disp(fFFL via FedAvgε ) = DP Disp(f CFL 1 ) > DP Disp(f CFL 0 ) = 0.

heading: B APPENDIX - FEDFB ANALYSIS AND ALGORITHM DESCRIPTION
text: In this section, we provide our bi-level optimization formulation for FEDFB for four fairness notions: demographic parity, equal opportunity, equalized odds and client parity, and design the corresponding update rule. This development can also be applied to centralized case. Then, we provides more details of how we incorporate FB with federated learning.
To explain how to optimize the weights of different groups, we introduce some necessary notations first. Denote the kth sample as (xk, yk, ak, ik), k = 1, . . . , n. Here xk ∈ X is the input feature, yk ∈ {0, 1} is the label, ak ∈ A = [A] is the sensitive attribute and ik ∈ [I] is the index of the client that the sample belongs to. A represents the total amount of sensitive attribute and I represents the total amount of clients. Denote the number of samples in group a as n?,a := |{k : ak = a}|. Let ny,a := |{k : yk = y, ak = a}| be the number of samples in group a of label y, and n (i) y,a := |{k : yk = y, ak = a, ik = i}| be the number of samples belong to client i of label y and sensitive attribute a. Define the loss function as `(y, ŷ). Let Ly,a(w) be the empirical risk aggregated over samples subject to y = y, a = a, i.e., Ly,a(w) := ∑ k:yk=y,ak=a `(yk, ŷk)/ny,a, where ny,a := |{k : yk = y, ak = a}|. We then define the local version of Ly,a as L(i)y,a(w) :=∑ k:yk=y,ak=a,ik=i `(yk, ŷk)/n (i) y,a.
B.1 FEDFB w.r.t DEMOGRAPHIC PARITY
To extend Roh et al. (2021) to multiple groups cases, we propose a different bi-level optimization problem w.r.t demographic parity. This development can also be applied to the centralized setting. The following proposition gives a necessary sufficient condition for demographic parity, which can be directly obtained from Roh et al. (2021). For completeness, we also include the proof here. Proposition 21 (Necessary sufficient condition for demographic parity, Proposition 2 in Roh et al. (2021)). Consider 0-1 loss: `(y, ŷ) = Jy 6= ŷK. Let L′y,a(w) := ny,an?,aLy,a(w), then
− L′0,0(w) + L′1,0(w) + L′0,a(w)− L′1,a(w) + n0,0 n?,0 − n0,a n?,a = 0 (14)
for all a ∈ [A] is a necessary sufficient condition for demographic parity.
Proof. We denote by P the empirical probability. The demographic parity is satisfied when P(ŷ = 1 | a = 0) = P(ŷ = 1 | a = a) holds for all a ∈ [A]. Thus,
P(ŷ = 1, y = 0 | a = 0) + P(ŷ = 1, y = 1 | a = 0) =P(ŷ = 1, y = 0 | a = a) + P(ŷ = 1, y = 1 | a = a)
For 0-1 loss, we have `(|1− y|, ·) = 1− `(y, ·), thus 1
n?,0 ∑ k:yk=0,ak=0 (1− ` (yk, ŷk)) + 1 n?,0 ∑ k:yk=1,ak=0 ` (yk, ŷk)
= 1
n?,a ∑ k:yk=0,ak=a (1− ` (yk, ŷk)) + 1 n?,a ∑ k:yk=1,ak=a ` (yk, ŷk) .
By replacing ∑ k:yk=y,ak=a
` (yk, ŷk) = ny,aLy,a(w), we have n0,0 n?,0 (1− L0,0(w)) + n1,0 n?,0 L1,0(w)
= n0,a n?,a (1− L0,a(w)) + n1,a n?,a L1,a(w).
Remark 10. Proposition 21 provides us a way to measure demographic disparity using group-specific losses. However, since 0-1 loss is noncontinuous, in practice, we use the “continuous surrogate” of it, which is cross entropy.
The necessary sufficient condition for demographic parity (14) inspires us to achieve demographic parity by connecting one group with all the other groups for non-binary sensitive attribute settings. To achieve demographic parity, we introduce another parameter: λ = (λ0, . . . , λA−1), the weights attached to samples. We formalize the reweighting task into the following bi-level optimization problem, where the outer objective function captures the demographic parity criterion:
min λ∈Λ Fdp(λ) := min λ∈Λ A−1∑ a=1 ( −L′0,0(wλ) + L′1,0(wλ) + L′0,a(wλ)− L′1,a(wλ) + n0,0 n?,0 − n0,a n?,a )2 ︸ ︷︷ ︸
(15)outer
wλ := arg min w L(w,λ) = arg min w A−1∑ a=0 [ λaL ′ 0,a(w) + (2 n?,a n − λa)L′1,a(w) ] ︸ ︷︷ ︸
(15)inner
, (15)
where Λ = [0, 2n?,0n ]× · · · × [0, 2 n?,A−1 n ].
We make the following assumption to our loss function to have the decreasing direction in Lemma 22. Assumption 1. L′y,a(·) is twice differentiable for all y ∈ {0, 1}, a ∈ [A], and
A−1∑ a=0 [ λa∇2L′0,a(w) + (2 n?,a n − λa)∇2L′1,a(w) ] 0 for all λ ∈ Λ. (16)
If L′y,a(wλ) is convex for all y ∈ {0, 1}, a ∈ [A], the condition (16) holds unless for all a, L′0,a(·), L′1,a(·) share their stationary points, which is very unlikely (see Remark 1 in Roh et al. (2021)).
The following lemma provides a decreasing direction of the outer objective function Fdp, which inspired us to design the update rule of λ. Lemma 22 (Decreasing direction of Fdp). If Assumption 1 holds, then on the direction µ(λ) = (µ0(λ), . . . , µA−1(λ)) where
µ0(λ) = − A−1∑ a=1 ( −L′0,0(wλ) + L′1,0(wλ) + L′0,a(wλ)− L′1,a(wλ) + n0,0 n?,0 − n0,a n?,a ) , µa(λ) = −L′0,0(wλ) + L′1,0(wλ) + L′0,a(wλ)− L′1,a(wλ) + n0,0 n?,0 − n0,a n?,a (17)
for all a ∈ {1, . . . , A− 1}, we have µ(λ) ·∇Fdp(λ) ≤ 0, and the equality holds if only if µ(λ) = 0.
Proof. We compute the derivative as
∂Fdp(λ)
∂λj = 2 A−1∑ a=1 [( − L′0,0(wλ) + L′1,0(wλ) + L′0,a(wλ)− L′1,a(wλ) + n0,0 n?,0 − n0,a n?,a ) ( −∇L′0,0(wλ) +∇L′1,0(wλ) +∇L′0,a(wλ)−∇L′1,a(wλ) )]∂wλ ∂λj . (18)
Note that wλ is the minimizer to (15)inner, we have
A−1∑ a=0 [ λa∇L′0,a(wλ) + (2 n?,a n − λa)∇L′1,a(wλ) ] = 0.
We take the λj derivative to the above equation and have
∇L′0,j(wλ)−∇L′1,j(wλ) + A−1∑ a=0 [ λa∇2L′0,a(wλ) + (2 n?,a n − λa)∇2L′1,a(wλ) ]∂wλ ∂λj = 0.
Thus we get
∂wλ ∂λj = (A−1∑ a=0 [ λa∇2L′0,a(wλ) + (2 n?,a n − λa)∇2L′1,a(wλ) ])−1 [∇L′1,j(wλ)−∇L′0,j(wλ)].
(19)
Then on the direction µ(λ) given by (17), we combine (18) and (19) to have
µ(λ) · ∇Fdp(λ)
= 2 (A−1∑ a=1 [( − L′0,0(wλ) + L′1,0(wλ) + L′0,a(wλ)− L′1,a(wλ) + n0,0 n?,0 − n0,a n?,a ) ( −∇L′0,0(wλ) +∇L′1,0(wλ) +∇L′0,a(wλ)−∇L′1,a(wλ)
)]) (A−1∑ a=0 [ λa∇2L′0,a(wλ) + (2 n?,a n − λa)∇2L′1,a(wλ)
])−1 ( − A−1∑ a=1 [( − L′0,0(wλ) + L′1,0(wλ) + L′0,a(wλ)− L′1,a(wλ) + n0,0 n?,0 − n0,a n?,a
) ( −∇L′0,0(wλ) +∇L′1,0(wλ) +∇L′0,a(wλ)−∇L′1,a(wλ) )]) ≤ 0
where we have used Assumption 1, and the equality holds only when µ(λ) = 0.
Inspired by Lemma 22, in each communication round t = 0, 1, . . . , we design update rule for λ as:
λ(t+1)a = λ (t) a + αt ‖µ(λ(t))‖2 µa(λ (t)), for a ∈ [A], (20)
where αt is the step size.
Now we introduce how clients collaborate to solve the bi-level optimization problem (15).
First, we focus on the outer objective function (15)outer and introduce how clients collaborate to update the weight λ. Note that the central server can compute L′y,a(wλ(t)) by weight-averaging the local group loss L(i)y,a(wλ(t)) sent from clients at communication rounds as
L′y,a(wλ(t)) = ∑ i∈[I] n (i) y,a n?,a L(i)y,a(wλ(t)),
thereby obtain µ(λ(t)) and update λ(t) by (20).
Next, we focus on the inner objective function (15)inner and introduce how clients collaborate to update the model parameterswλ using FEDAVG. Note that we can decompose the objective functionL(w,λ) into L(w,λ) = ∑ i∈[I] L (i)(w,λ), where L(i)(w,λ) := ∑A−1 a=0 [λan (i) 0,aL (i) 0,a/n?,a + (2 n?,a n − λa)n (i) 1,aL (i) 1,a/n?,a] is the client objective function of client i. The global objective can be seen as a weighted sum of the client objective function. Therefore, we can use FEDAVG to solve the inner optimization problem.
We present the pseudocode of FEDFB w.r.t demographic parity in Algorithm 2.
Algorithm 2: FEDFB w.r.t Demographic Parity

heading: Server executes:
text: input :Learning rate {αt}t∈N; Initialize λa as n?,a n for all a ∈ [A]\ {0}; for each iteration t = 1, 2, . . . do Clients perform updates; wλ ← SecAgg { w(i) } for all i;
Ly,a ← SecAgg { L (i) y,a } for all (y, a);
L′y,a ← ny,an?,aLy,a for all y ∈ {0, 1}, a ∈ [A]; µ0 ← − ∑A−1 a=1 ( −L′0,0 + L′1,0 + L′0,a − L′1,a + n0,0n?,0 − n0,a n?,a ) ; µa ← −L′0,0 + L′1,0 + L′0,a − L′1,a + n0,0n?,0 − n0,a n?,a
, a ∈ [A]\{0}; λa ← λa + αt‖µ‖2µa, for all a ∈ [A]; Broadcast wλ and λ to clients;
end output :wλ
ClientUpdate(i,w,λ): w(i) ← Gradient descent w.r.t objective function∑A−1
a=0
[ λaL ′(i) 0,a (w) + (2 n?,a n − λa)L ′(i) 1,a (w) ] ;
Send w(i), L(i)0,a(w), L (i) 1,a(w) for all a ∈ [A] to server via a SecAgg protocol;
Next, we analyze the convergence performance of FEDFB. We need to make the following assumptions on the objective function L(i)(w,λ), i ∈ [I]. For simplicity, we drop the λ here and use the notations L(i)(w) and L(w) instead. We use w(i)t to denote the model parameters at t-th iteration in i-th client. The assumptions below are proposed by work Li et al. (2020b):
Assumption 2 (Strong convexity, Assumption 1 in Li et al. (2020b)). L(i)(w) is µ-strongly convex for i ∈ [I], i.e., for all v and w, w, L(i)(v) ≥ L(i)(w) + (v −w)>∇L(i)(w) + µ2 ‖v −w‖ 2 2.
Assumption 3 (Smoothness, Assumption 2 in Li et al. (2020b)). L(i)(w) is L-smooth for i ∈ [I], i.e., for all v and w, L(i)(v) ≤ L(i)(w) + (v −w)>∇L(i)(w) + L2 ‖v −w‖ 2 2.
Assumption 4 (Bounded variance, Assumption 3 in Li et al. (2020b)). Let ξ(i)t be sampled from i-th device’s local data uniformly at random, where t ∈ [T ], and T is the total number of every client’s SGDs. The variance of stochastic gradients in each device is bounded:
E ∥∥∥∇L(i)(w(i)t , ξ(i)t )−∇L(i)(w(i)t )∥∥∥2 <∞ for i ∈ [I].
Assumption 5 (Bounded gradients, Assumption 4 in Li et al. (2020b)). The expected squared norm of stochastic gradients is uniformly bounded, i.e., E ∥∥∥∇L(i)(w(i)t , ξ(i)t )∥∥∥ <∞ for all i ∈ [I], t ∈ [T ]. In FEDAVG, first, the central server broadcasts the lastest model to all clients, then, every client performs local updates for a number of iterations, last, the central server aggregates the local models to produce the new global model(see Algorithm Description in Li et al. (2020b) for more detailed explanation).
We denote E as the number local iterations performed in a client between two communications, and R be the total number of every client’s iteration. Thus RE is the number of communications.
With the above assumptions, the following theorem shows the convergence of FedFB in the case of two clients.
Theorem 23. Consider the case of A = 2. Let Assumption 2, 3, 4, 5 on {L(i)(·,λ)}i∈[I] and Assumption 1 on {L′y,a(·)}y,a∈{0,1} hold. Choose {αt}∞t=1 such that limt→∞ αt = 0, ∑∞ t=1 αt =∞. Suppose we use FEDAVG with R and E satisfying E 2
R → 0 to solve (15)inner between two λ update rounds. We can find sufficiently large T such that with high probability, applying update rule (20) leads to |λ(T )a − λ?a| ≤ max { |λ(0)a − λ?a| − ∑T t=1 αt, αT } → 0, where λ? is the local minimizer on
direction µ(λ).
Proof. We first derive the update rule in the case of A = 2. From (20), we have µ0 = −µ1. Denote
f(λ(t)) = −L′0,0(wλ(t)) + L′1,0(w(t)λ ) + L′0,1(w (t) λ )− L′1,1(w (t) λ ) + n0,0 n?,0 − n0,1 n?,1 .
Then the update rule becomes
λ (t+1) 0 = λ (t) 0 −
√ 2
2 αtsign(f(λ(t)))
λ (t+1) 1 = λ (t) 1 +
√ 2
2 αtsign(f(λ(t))).
(21)
Then we apply FEDAVG with R number of total iterations to solve minw L(w;λ(t)), and obtain w
(t) R . Then in the update round from λ (t) to λ(t+1), by Thm. 1 in Li et al. (2020b), we have
E[L(w(t)R ;λ (t))]− L(wλ(t) ;λ(t)) = O (E2 R ) ,
E ∥∥∥w(t)R −wλ(t)∥∥∥2 = O(E2R ),
where wλ(t) = arg min w
L(w;λ(t)). By Markov’s inequality, with probability 1− δ,
L(w (t) R ;λ (t))− L(wλ(t) ;λ(t)) = O (E2 δR ) ,∥∥∥w(t)R −wλ(t)∥∥∥2 = O(E2δR).
Then taking the union bound over T updating iterations of λ(t), the conclusions above hold with probability at least 1 − Tδ for all λ(t), t = 1, 2, · · · , T . Therefore, with sufficiently large R = R(δ) such that E 2
δR → 0, for all λ(t) in the T iteration, |L(w (t) R ;λ (t)) − L(wλ(t) ;λ(t))| 1, ‖w(t)R −wλ(t)‖ 1. By Lemma 22, Fdp(λ) has a local minimizer λ? on direction µ(λ). By update rule (21), we can find large T > 0 to have
|λ(T )a − λ?a| ≤ max { |λ(0)a − λ?a| − T∑ t=1 αt, αT } → 0,
where a ∈ {0, 1}.
Remark 11. Note that Thm. 23 assumes FEDFB does not update λ in each communication round and there are infinite rounds of aggregations between two λ updating round. However, for computation efficiency, we update λ at every communication round in practice.
B.2 FEDFB w.r.t EQUAL OPPORTUNITY
Similar to Proposition 21, we design the following bi-level optimization problems to capture equal opportunity:
min λ∈Λ Feo(λ) = min λ∈Λ A−1∑ a=1 (L1,a(wλ)− L1,0(wλ))2
wλ = arg min w A−1∑ a=1 λaL1,a(w) + ( n1,? n − A−1∑ a=1 λa)L1,0(w) + n0,? n L0,?(w). (22)
Here Λ = {(λ1, . . . , λA−1) : λ1 + · · ·+ λA−1 ≤ n1,?n , λa ≥ 0 for all a = 1, . . . , A− 1}. For equal opportunity, we make the following assumption:
Assumption 6. Ly,a(·) is twice differentiable for all y ∈ {0, 1}, a ∈ [A], and A−1∑ a=1 λa∇2L1,a(wλ) + ( n1,? n − A−1∑ a=1 λa)∇2L1,0(wλ) + n0,? n ∇2L0,?(wλ) 0
for all λ ∈ Λ.
With the above assumption, the following lemma provides the update rule:
Lemma 24. If Assumption 6 holds, then on the direction
µ(λ) = (L1,1(wλ)− L1,0(wλ), . . . , L1,A−1(wλ)− L1,0(wλ)), (23)
we have µ(λ) · ∇Feo(λ) ≤ 0, and the equality holds if only if µ(λ) = 0.
Update rule for equal opportunity:
λ(t+1)a = λ (t) a + αt ‖µ(λ(t))‖2 (L1,a(wλ(t))− L1,0(wλ(t))).
Proof of Lemma 24. We compute the derivative as
∂Feo(λ)
∂λj = 2 A−1∑ a=1 (L1,a(wλ)− L1,0(wλ))(∇L1,a(wλ)−∇L1,0(wλ)) ∂wλ ∂λj . (24)
Note that wλ is the minimizer to (22), we have
A−1∑ a=1 λa∇L1,a(wλ) + ( n1,? n − A−1∑ a=1 λa)∇L1,0(wλ) + n0,? n ∇L0,?(wλ) = 0.
We take the λj derivative to the above equation and have[A−1∑ a=1 λa∇2L1,a(wλ) + ( n1,? n − A−1∑ a=1 λa)∇2L1,0(wλ) + n0,? n ∇2L0,?(wλ) ] ∇L1,j(wλ)−∇L1,0(wλ) +
∂wλ ∂λj = 0.
Thus we get
∂wλ ∂λj = [A−1∑ a=1 λa∇2L1,a(wλ) + ( n1,? n − A−1∑ a=1 λa)∇2L1,0(wλ) + n0,? n ∇2L0,?(wλ) ]−1 [∇L1,0(wλ)−∇L1,j(wλ)]. (25)
Then on the direction µ(λ) given by (23), we combine (24) and (25) to have
µ(λ) · ∇Feo(λ)
= 2 [A−1∑ a=1 (L1,a(wλ)− L1,0(wλ))(∇L1,a(wλ)−∇L1,0(wλ)) ]
[A−1∑ a=1 λa∇2L1,a(wλ) + ( n1,? n − A−1∑ a=1 λa)∇2L1,0(wλ) + n0,? n ∇2L0,?(wλ) ]−1 [A−1∑ a=1 (L1,a(wλ)− L1,0(wλ))(∇L1,0(wλ)−∇L1,a(wλ)) ] ≤ 0,
where we have used Assumption 6, the equality holds only when µ(λ) = 0.
We present the FEDFB algorithm w.r.t equal opportunity in Algorithm 3.
Algorithm 3: FEDFB w.r.t Equal Opportunity

heading: Server executes:
text: input :Learning rate {αt}t∈N; Initialize λa as n1,a n for all a ∈ [A]\ {0}; for each iteration t = 1, 2, . . . do Clients perform updates; wλ ← SecAgg { w(i) } for all i;
Ly,a ← SecAgg { L (i) y,a } for all y ∈ {0, 1}, a ∈ [A]\ {0};
µa ← L1,a − L1,0, a ∈ [A]\ {0}; λa ← λa + αt‖µ‖2µa, for all a ∈ [A]\ {0}; Broadcast wλ and λ to clients;
end output :wλ
ClientUpdate(i,w,λ): w(i) ← Gradient descent w.r.t objective function∑A−1
a=1 λaL (i) 1,a(w) + ( n1,? n − ∑A−1 a=1 λa)L (i) 1,0(w) + n0,? n L (i) 0,?(w);
Send w(i), L(i)0,a(w), L (i) 1,a(w) for all a ∈ [A] to server via a SecAgg protocol;
B.3 FEDFB w.r.t EQUALIZED ODDS
For equalized odd, we design the following bi-level optimization problem:
min λ∈Λ Feod(λ) = min λ∈Λ A−1∑ a=1 [ (L1,a(wλ)− L1,0(wλ))2 + (L0,a(wλ)− L0,0(wλ))2 ] wλ = arg min
w A−1∑ a=1 (λ0,aL0,a(w) + λ1,aL1,a(w))
+ ( n0,? n − A−1∑ a=1 λ0,a)L0,0(w) + ( n1,? n − A−1∑ a=1 λ1,a)L1,0(w). (26)
Here
Λ = {(λ0,1, . . . , λ0,A−1, λ1,1, . . . , λ1,A−1) : A−1∑ a=1 λ0,a ≤ n0,? n , A−1∑ a=1 λ1,a ≤ n1,? n ,
λ0,a, λ1,a ≥ 0, for all a = 1, . . . , A− 1}.
For equalized odds, we make the following assumption:
Assumption 7. Ly,a(·) is twice differentiable for all y ∈ {0, 1}, a ∈ [A], and A−1∑ a=1 [ (λ1,a∇2L1,a(wλ) + λ0,a∇2L0,a(wλ) + ( n0,? n − A−1∑ a=1 λ0,a)∇2L0,0(wλ)
+ ( n1,? n − A−1∑ a=1 λ1,a)∇2L1,0(wλ)) ] 0
for all λ ∈ Λ.
With the above assumption, the following lemma provides the update rule:
Lemma 25. If Assumption 7 holds, then on the direction
µ(λ) = (µ0,1(λ), . . . , µ0,A−1(λ), µ1,1(λ), . . . , µ1,A−1(λ)), with
µy,a(λ) = Ly,a(wλ)− Ly,0(wλ), y ∈ {0, 1}, a ∈ [A], (27) we have µ(λ) · ∇Feod(λ) ≤ 0, and the equality holds if only if µ(λ) = 0.
Update rule for equalized odd:
λ(t+1)y,a = λ (t) y,a + αt ‖µ(λ(t))‖2 (Ly,a(wλ(t))− Ly,0(wλ(t))) for y ∈ {0, 1}, a ∈ [A].
Proof of Lemma 25. We compute the derivative as
∂Feod(λ)
∂λy,j = 2 A−1∑ a=1 [ (L1,a(wλ)− L1,0(wλ))(∇L1,a(wλ)−∇L1,0(wλ))
+ (L0,a(wλ)− L0,0(wλ))(∇L0,a(wλ)−∇L0,0(wλ)) ] ∂wλ ∂λy,j .
(28)
Note that wλ is the minimizer to (26), we have
A−1∑ a=1 (λ0,a∇L0,a(wλ) + λ1,a∇L1,a(wλ))
+ ( n0,? n − A−1∑ a=1 λ0,a)∇L0,0(wλ) + ( n1,? n − A−1∑ a=1 λ1,a)∇L1,0(wλ) = 0.
We take the λy,j derivative to the above equation and have
∇Ly,j(wλ)−∇Ly,0(wλ) + [A−1∑ a=1 (λ0,a∇2L0,a(wλ) + λ1,a∇2L1,a(wλ))
+ ( n0,? n − A−1∑ a=1 λ0,a)∇2L0,0(wλ) + ( n1,? n − A−1∑ a=1 λ1,a)∇2L1,0(wλ) ] ∂wλ ∂λy,j = 0.
Thus we get
∂wλ ∂λy,j = [A−1∑ a=1 (λ0,a∇2L0,a(wλ) + λ1,a∇2L1,a(wλ))
+ ( n0,? n − A−1∑ a=1 λ0,a)∇2L0,0(wλ) + ( n1,? n − A−1∑ a=1 λ1,a)∇2L1,0(wλ) ]−1
[∇Ly,0(wλ)−∇Ly,j(wλ)]. (29)
Then on the direction µ(λ) given by (27), we combine (28) and (29) to have µ(λ) · ∇Feod(λ)
= 2 [A−1∑ a=1 [(L1,a(wλ)− L1,0(wλ))(∇L1,a(wλ)−∇L1,0(wλ))
+ (L0,a(wλ)− L0,0(wλ))(∇L0,a(wλ)−∇L0,0(wλ))] ]
[A−1∑ a=1 (λ0,a∇2L0,a(wλ) + λ1,a∇2L1,a(wλ))
+ ( n0,? n − A−1∑ a=1 λ0,a)∇2L0,0(wλ) + ( n1,? n − A−1∑ a=1 λ1,a)∇2L1,0(wλ) ]−1
[A−1∑ a=1 [(L1,a(wλ)− L1,0(wλ))(∇L1,0(wλ)−∇L1,a(wλ))
+ (L0,a(wλ)− L0,0(wλ))(∇L0,0(wλ)−∇L0,a(wλ))] ] ≤ 0
where we have used Assumption 7, and the equality holds only when µ(λ) = 0.
The full procedure is described in Algorithm 4.
Algorithm 4: FEDFB w.r.t Equalized Odds

heading: Server executes:
text: input :Learning rate {αt}t∈N; Initialize λy,a as ny,a n for all y ∈ {0, 1} , a ∈ [A]\ {0}; for each iteration t = 1, 2, . . . do Clients perform updates; wλ ← SecAgg { w(i) } for all i;
Ly,a ← SecAgg { L (i) y,a } for all y ∈ {0, 1}, a ∈ [A]\ {0};
µy,a ← Ly,a − Ly,0 for all y ∈ {0, 1} , a ∈ [A]\{0}; λy,a ← λy,a + αt‖µ‖2µy,a, for all a ∈ [A]\ {0}; Broadcast wλ and λ to clients;
end output :wλ
ClientUpdate(i,w,λ): w(i) ← Gradient descent w.r.t objective function∑A−1a=1 (λ0,aL(i)0,a(w) + λ1,aL(i)1,a(w))+ ( n0,? n − ∑A−1 a=1 λ0,a)L (i) 0,0(w) + ( n1,? n − ∑A−1 a=1 λ1,a)L (i) 1,0(w);
Send w(i), L(i)0,a(w), L (i) 1,a(w) for all a ∈ [A] to server via a SecAgg protocol;
B.4 FEDFB w.r.t CLIENT PARITY
For client parity, we slightly abuse the notation and define the loss over client i as L(i)(w) :=∑ ik=i `(yk, ŷk)/n (i), with n(i) = |{k : ik = i}|. Note that the L(i)(w) here is different from the one in Sec. B.1. We design the following bi-level optimization problem:
min λ∈Λ Fcp(λ) = min λ∈Λ I−1∑ i=1 ( L(i) (wλ)− L(0) (wλ) )2 ,
wλ = arg min w I−1∑ i=1 λ(i)L(i)(w) + (1− I−1∑ i=1 λ(i))L(0)(w). (30)
Here
Λ = {(λ(1), . . . , λ(I−1)) : 0 ≤ λ(i) ≤ 1, I−1∑ i=1 λ(i) ≤ 1}.
For client parity, we make the following assumption: Assumption 8. L(i)(·) is twice differentiable for all i = 1, . . . , I − 1, and
I−1∑ i=1 λ(i)∇2L(i)(wλ) + (1− I−1∑ i=1 λ(i))∇2L(0)(wλ) 0.
With the above assumption, the following lemma provides the update rule: Lemma 26. If Assumption 8 holds, then on the direction
µ(λ) = (L(1)(wλ)− L(0)(wλ), . . . , L(I−1)(wλ)− L(0)(wλ)), (31) we have µ(λ) · ∇Fcp(λ) ≤ 0, and the equality holds if and only if µ(λ) = 0.
Then we update λ(t) = (λ(1) (t) , . . . , λ(I−1) (t) ) as follows:
Update rule for client parity:
λ(i) (t+1) = λ(i) (t) + αt
‖µ(λ(t))‖2 (L(i)(wλ(t))− L(0)(wλ(t))) for i = 1, . . . , I − 1.
Proof of Lemma 26. We compute the derivative as
∂Fcp(λ) ∂λ(j) = ( 2 I−1∑ i=1 [L(i)(wλ)− L(0)(wλ)][∇L(i)(wλ)−∇L(0)(wλ)] ) ∂wλ ∂λ(j) . (32)
Note that wλ is the minimizer to (30), we have I−1∑ i=1 λ(i)∇L(i)(wλ) + (1− I−1∑ i=1 λ(i))∇L(0)(wλ) = 0.
We take the λ(j) derivative to the above equation and have
∇L(j)(wλ) + I−1∑ i=1 λ(i)∇2L(i)(wλ) ∂wλ ∂λj −∇L(0)(wλ) + (1− I−1∑ i=1 λ(i))∇2L(0)(wλ) ∂wλ ∂λj = 0.
Thus we get
∂wλ ∂λ(j) = [ I−1∑ i=1 λ(i)∇2L(i)(wλ)+(1− I−1∑ i=1 λ(i))∇2L(0)(wλ) ]−1 [∇L(0)(wλ)−∇L(j)(wλ)]. (33)
Then on the direction given by (31), we combine (32) and (33) to have µ(λ) · ∇Fcp(λ)
= 2 ( I−1∑ i=1 [L(i)(wλ)− L(0)(wλ)][∇L(i)(wλ)−∇L(0)(wλ)] )
[ I−1∑ i=1 λ(i)∇2L(i)(wλ) + (1− I−1∑ i=1 λ(i))∇2L(0)(wλ) ]−1
I−1∑ i=1 ( [L(i)(wλ)− L(0)(wλ)][∇L(0)(wλ)−∇L(i)(wλ)] ) ≤ 0,
where we have used Assumption 8, and the equality holds only when µ(λ) = 0.
The Algorithm 5 gives the full description.
Algorithm 5: FEDFB w.r.t Client Parity

heading: Server executes:
text: input :Learning rate {αt}t∈N; Initialize λ(i) as n (i)
n for all i ∈ [I]\ {0}; for each iteration t = 1, 2, . . . do
Clients perform updates; wλ ← SecAgg { w(i) } for all i; µ(i) ← L(i) − L(0), i ∈ [I]\{0}; λ(i) ← λ(i) + αt‖µ‖2µ
(i), for all i ∈ [I]\ {0}; Broadcast wλ and λ to clients;
end output :wλ
ClientUpdate(i,w,λ): w(i) ← Gradient descent w.r.t objective function Ji 6= 0Kλ(i)L(i)(w) + Ji = 0K(1−∑I−1j=1 λ(ij)L(0)(w);
Send w(i) to server via a SecAgg protocol; Send L(i)(w) to server;

heading: C APPENDIX - EXPERIMENTS
text: We continue from Sec. 5 and provide more details on experimental settings, and other supplementary experiment results.

heading: C.1 EXPERIMENT SETTING
text: The reported statistics are computed on the test set, and we set 10 communication rounds and 30 local epochs for all federated learning algorithms except AGNOSTICFAIR. We run 300 epochs for other methods. For all tasks, we randomly split data into a training set and a testing set at a ratio of 7:3. The batch size is set to be 128. For all methods, we choose learning rate froom {0.001, 0.005, 0.01}. We solve FEDFB with sample weight learning rates α ∈ {0.001, 0.05, 0.08, 0.1, 0.2, 0.5, 1, 2} in parallel and select the α which achieves the highest fairness. All benchmark models are tuned according to the hyperparameter configuration suggested in their original works. We perform cross-validation on the training sets to find the best hyperparameter for all algorithms.

heading: C.2 SYNTHETIC DATASET GENERATION
text: We generate a synthetic dataset of 5,000 examples with two non-sensitive attributes (x1, x2), a binary sensitive a, and a binary label y. A tuple (x1, x2, y) is randomly generated based on the two Gaussian distributions: (x1, x2) | y ∼ N ([−2;−2], [10, 1; 1, 3]) and (x1, x2) | y = 1 ∼ N ([2; 2], [5, 1]), where y ∼ Bern(0.6). For the sensitive attribute a, we generate biased data using an unfair scenario px1,x2((x ′ 1, x ′ 2) | y = 1)/[px1,x2((x′1, x′2) | y = 0) + px1,x2((x′1, x′2) | y = 1)], where px1,x2 is the pdf of (x1, x2). We split the data into three clients in a non-iid way. We randomly assign 50%, 30%, 20% of the samples from group 0 and 20%, 40%, 40% of the samples from group 1 to 1st, 2nd, and 3rd client, respectively. To study the empirical relationship between the performance of FEDFB and data heterogeneity, we split the dataset into other ratios to obtain the desired level of data heterogeneity. To get the dataset with low data heterogeneity, we draw samples from each group into three clients in a ratio of 33%, 33%, 34% and 33%, 33%, 34%. For dataset with high data heterogeneity, the ratio we choose is 70%, 10%, 20% and 10%, 80%, 10%.

heading: C.3 SUPPLEMENTARY EXPERIMENT RESULTS
text: Fig. 8 shows the accuracy versus fairness violation for the 3 clients’ cases. We see a clear advantage of FFL via FEDAVG over the UFL in both 2 clients’ cases and 3 clients’ cases. The achievable fairness range of FFL via FEDAVG is much wider than that of UFL, though the accuracy of FEDAVG is not guaranteed when the data heterogeneity increases.
The data heterogeneity is increasing from left to right. The green dotted vertical line describes the lower bound of unfairness FFL via FEDAVG can achieve, and and the orange dotted vertical line describes the lower bound of unfairness UFL can achieve. Here the distribution setting is x | a = 0, i = 0 ∼ N (3, 1), x | a = 1, i = 0 ∼ N (5, 1), x | a = 0, i = 1 ∼ N (1, 1), x | a = 1, i = 1 ∼ N (−1, 1), x | a = 0, i = 2 ∼ N (1, 1), x | a = 1, i = 2 ∼ N (2, 1), a | i = i ∼ Bern(qi) for i = 0, 1, 2. The data heterogeneity here is captured by |q2 − q0|. (a) q0 = q1 = q2 = 0.5. (b) q0 = 0.4, q1 = 0.5, q2 = 0.6. (c): q0 = 0.3, q1 = 0.5, q2 = 0.7. (d): q0 = 0.2, q1 = 0.5, q2 = 0.8.
We also compare FEDAVG, UFL, FFL via FEDAVG, FEDFB, AGNOSTICFAIR and CFL on logistic regression. Table 4 shows that our method outperforms UFL and FFL via FEDAVG, while achieving similar performance as AGNOSTICFAIR and CFL but ensuring higher privacy.

heading: C.4 EVALUATION OF DIFFERENTIALLY PRIVATE FEDFB
text: Since FEDFB exchanges more information than FFL via FEDAVG, we employ differential privacy to decrease information leakage. We apply the Laplace mechanism to make the information exchanged in each communication round ε-differentially private. We report the test accuracy and DP disparity of FFL via FEDAVG and FEDFB with different differential privacy levels in Table 5. Interestingly, we observe that a higher level of differential privacy even helps to improve fairness (see FFL via FEDAVG column), though the accuracy is decreased. This phenomenon is to be expected since larger noise helps to protect sensitive information, thereby improving fairness and lower accuracy. Still, Table 5 implies that FEDFB still outperforms FFL via FEDAVG with restrictions on the information exchange.

heading: C.5 EMPIRICAL RELATIONSHIP BETWEEN ACCURACY, FAIRNESS, AND THE NUMBER OF CLIENTS
text: We investigate the empirical relationship between accuracy, fairness, and the number of clients. We generate three synthetic datasets of 3,333, 5,000, and 6,667 samples, and split them into two, three, and four clients, respectively. Table 6 shows that our method outperforms under the three cases.

heading: C.6 COMPARISON WITH FAIRFED
text: As suggested in Ezzeldin et al. (2021), we use logistic regression to compare our approach with FAIRFED. Since FAIRFED is only applicable to single binary sensitive attribute cases, we report the performance of FAIRFED on synthetic and Adult datasets in Table 7. We observe that our FEDFB outperforms FAIRFED in terms of both accuracy and fairness, while FAIRFED also outperforms FFL via FEDAVG thanks to the additional client reweighting step.
To make fairer comparison, we follow the exact same setting as Ezzeldin et al. (2021) to re-split Adult and COMPAS dataset, employ |SPD| = |P(ŷ = 1 | a = 0)−P(ŷ = 1 | a = 1)| as unfairness metric and present the results in Table 8. We observe that FEDFB achieves higher fairness than FAIRFED while being robust to data heterogeneity.

heading: C.7 COMPARISON WITH AGNOSTICFAIR
text: Lastly, we compare our method with AGNOSTICFAIR (Du et al., 2021), which exchanges the model parameters and the other information after every gradient update to mimic the performance of CFL with FAIRNESSCONSTRAINT implementation (Zafar et al., 2017c). Table 9 shows that our FEDFB achieves similar performance as AGNOSTICFAIR, at much lower cost of privacy.

Review summaries:
This paper investigates how one can achieve group fairness under a decentralized setting. The authors develop a theoretical framework for decentralized fair learning algorithms and analyzed the performance of existing approaches including UFL, FFL via FedAvg, and CFL. They provide novel insights showing that UFL<FFL via FedAvg<CFL. They also propose a new federated fair learning algorithm FEDFB by letting each client share extra information about the unfairness of its local classifier with the server, which then computes the optimal samples weights for the following round of local training. The experimental results demonstrate that FEDFB achieves state-of-the-art performance, while still ensuring data privacy. 

The authors propose a novel algorithm to train statistical models respecting fairness criteria like client parity or demographic parity. This problem has been investigated in the literature for the centralized setting and the authors propose to extend FairBatch (FB) to the federated setting. Finally, the authors show experimentally that their algorithm FedFB provides better fairness than when a server centralizes all the clients data. This work is quite novel but its theoretical statements solely rely on very specific use cases and lack clarity.