Improving Fairness via Federated Learning
Authors: Yuchen Zeng
Hongxu Chen
Kangwook Lee
Venue: ICLR 2022 Submitted (2022)

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.

Under review as a conference paper at ICLR 2022
IMPROVING FAIRNESS VIA FEDERATED LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
Recently, lots of algorithms have been proposed for learning fair classifier from centralized data. However, how to privately train fair classifier on decentralized data has not been fully studied yet. In this work, we first propose a new thcoretical 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 fair classifier trained 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.
INTRODUCTION
As machine learning 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 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. 2017 7c Hardt et al. 2016 Roh al., 2021), and almost all of these studies assume that the learner has access 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. for illustration.
Unfederated Fair Learning (UFL) and Centralized Fair Learning (CFL) UFL is the most naive 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 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 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 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., 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 FEDAYG) FFL via FEDAVG fedeertee federated learning (Konečný al. 2017) together with existing fair learning algorithms. Federated learning is

---

Under review as a conference paper at ICLR 2022
more private
fairer
UFL
FFL via FEDAVG
FedFB (Ours)
CFL
Training
Fair
fo
Fair Training
SUAN
Fed
Fair Training
f
Training
Fair
fi Sec.
Fair Training
Sec.
S
Sec.
(Thm.
Sec. Lemma
Figure 1: A high-level illustration of various approaches to fair learning on decentralized data and our contributions. Assuming two data owners, from left right, we show UFL (Unfederated Fair Learning). FFL via FEDAVG (Federated
Learning via FEDAVG), FEDFB (ours), and CFL (Centralized Fair Learning.. UFI, each data owner trains a locally fair model on own data, and the customer picks one of them at random. FFL via FEDAVG applies FEDAYG together with off-the-shelf fair training algorithms for local training. Our proposed solution FedFB consists of a modified FEDAVG protocol with custom-designed fair learning algorithm. CFL is the setting where fair model trained on the pooled data. In this work, theoretically characterize strict ordering between existing approaches and empirically demonstrate superior performance of FedFB.
distributed learning framework, using which many data owners can collaboratively train 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, has been unknown whether there is any strict perfor- mance gap between UFL and FFL via FEDAVG. This makes it unclear whether or not federated learning 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, 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 sfate-of-the-art algorithm for (centralized) fair learning (Roh et al. (021), we design FEDFB, 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 CFL.
To the best of our knowledge, our work is the first theoretical performance comparison of various approaches to fair learning decentralized data. Moreover, it characterizes the necessity of federated learning for improved fairness-accuracy tradeoff, and we expect this to expedite the adoption of feder- ated 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.
2 RELATED WORK
Model Fairness Among various algorithms for fair training Zemel et al., 2013 Jiang & Nachum
2020 Zafar al. 2017c at Hardt al.) 2016)] Roh et al. 2021
| 2220). the current state-of-the-r the-art is FairBatch (Roh et al. 2022 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 (Konečný al. 2017 McMahan et al. 2017). FEDAVG (MeMahan et al. 2017) is the
2

---

Under review as a conference paper at ICLR 2022
first and most widely used federated learning algorithm. The idea is to iteratively compute 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 FRDFB is also based on that of FEDAVG.
Federated Fair Learning for Client Parity There have been only 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 faimess 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.) [021] 2020aa] Mohri et al.) 2019; Yue et al.) [202]] Zhang et al. 2020a). To compare our methods with existing federated fair learning algorithms designed for client parity, we also extend our FEDFB B such that it can also achieve client parity instead of the standard notion of group fairness. In Sec. [ 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 stud- ies (Ezzeldin et al.) 202T Rodríguez- et al. [021] Chu et al.) [021] 1IFL
A
FiL. Falkuy
Du et al. 2021 Cui et al. 2021). conducted concurrently with our work, also aim achieving group fairness under federated learning. In particular, Du et al. (2021). J. Rodríguez- Gälvez et al.] (2021) and Chu et al. (202T) mimic
AguestiFar
CFL
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. (202T) 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--Gálezz et al. (2021) and Chu et al. (2021) are not applicable to demo- graphic parity. Therefore, we summarize the comparison of UFI., FFL via FEDAVG, CFI,, FEDFB and AGNOSTICFATR (Du et al.] (02T) 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. 202I). This is in contrast to our work, which instead focuses achieving global faimess in the overall data distribution. Our
Ausueacy porformmnce
Figure 2: Compar- ison of various fair lcarning methods..
setting is more appropriate in domains such as criminal justice and social welfare.
PERFORMANCE ANALYSIS OF UFL, FFL VIA FEDAVG AND CFL
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
In Sec. 3.1
Problem Setting Denote [NV] := (,, 1, NV 1} for any N E Σt. We assume I clients, which have the same amount of data. We further assume simple binary classification setting with a binary sensitive attribute, i.e., x E X IR is the input feature, y E y [1] is the outcome and E A- = [A] = [1] is the binary sensitive attribute. Assume x is a continuous variable. The algorithm we will develop later in Sec. will be applicable to general settings.
We now introduce parameters for describing the data distribution. Let | x ~ Bern()(x)) for all client i, where 17(-) : X -> [0, 1] is a strictly monotone increasing function. Assume a a, i = in Bern(g.), ). where i is the index of the client, P( is distribution, and q. E [0, 1] for a = 0, 1, E [M]. Let J { : X x A + [o, 1]}. Given f E F and data sample (x, a), we consider the following randomized classifier: & x, a ~ Bern(f a)).
i i~ p(.)
Using these definitions, we now define demographic parity, specialized for a binary sensitive attribute:
Definition 1 (Demographic Parity (binary cases)). IPý- = a = 0) = P(y = ||a- a 1).
To measure how unfair classifier is with respect to demographic parity (DP), we measure DP disparity, iee. the absolute difference between the two positive prediction rates:
DP Disp(S) = IP(C a = 0) - TP(- = | a = 1))-
3

---

Under review as a conference paper at ICLR 2022
(b)
0.2
DP Danu
D4 Des
0.10
0.9
0.9
0.0
0.5
0.3
0.5
0.3
0.5
03
1.0
0.0
1.0
Figure 3: Fundamental limitation of UFL in terms of fairness range. We visualize the DP disparity of UFL function of local unfairness budgets on three simple Gaussian distributions. The blue horizontal plane is of perfect fairness. The pink horizontal plane visualizes the value of & (the lowest DP disparity that UFL achieve). (a) (Example[]) On distribution that satisfies the conditions Corollary 2 (b, e) On distributions that do not satisfy the conditions of Corollary 2 5 > O.
In all three cases, the UFL cannot achieve perfect faimess, i.e.,
3.1
NECESSITY OF FEDERATION: FFL VIA FEDAVG IS STRICTLY BETTER THAN UFL
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 used in optimization. Recall that clients do not coordinate in this scenario, and each of them solves their own optimization problem to train locally fair classifier. In particular, each client E [7] first sets its own local faimess constraint E, E [0. 1]. and solves the following constrained optimization problem:
min P(ý # y i), s.t. Pp /EF
0,i 1)
Fý 1 1, i) S Ex- (UFL(i,E:))
We denote by f. the solution to UFL(i, E3) Recall that the overall performance of UFL is defined as the performance of the following mixture of / classifiers:
y x, a
w.p. 1/1 = Bern
Σ LE
(x, = Berr(ff UFF))
where FL = Eiemy J. ax,xax) with e = (co....,,1-11 11-1)
The question here is whether the resulting classifier JuFF, obtained by UFL can achieve an arbitrary level of fairness. The following lemma shows that UFL cannot achieve a high enough faimnsss level beyond certain threshold.
Lemma 1 (Anformal) Achievable fairness range of UFL). Let 9: = E (0,1) for all e [7]. Under certain conditions, there exists certain DP disparity threshold 8 >> O such that min DP Dispi FUFL) 5.
critical condition of Lemma D is that the distribution of insensitive attribute x a is highly heterogeneous on different clients. (See the detailed statements in Sec. Sec.(A.2.2]and Sec. (A.4) Therefore, Lemma immpies 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= and qo -1 = 0.5, 7(x) --t Ple = -((ua (.12), where i = O, 1. Under certain assumptions, if one client has much larger variance than the other, there exists > O such that mineo.ere(u.1] DP Disp([EEP)
Corollary 2 (Informal). Let
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. Sec. we will numerically demonstrate the same claim holds for more general cases. Next, we give specific example that satisfies the conditions of Corollary 2 which is visualized in Fig. a)).
(0) Example 1. Let PD = = -0,40 (1) = 3. (1) 1, = -70 and o (1) = 1. Then, 5 Rz 0.21.
FFL via FEDAVG Optimization FFL via FEDAVG enables federated training of fair classifier on decentralized data. In Sec. A.3.2 we show that the classifier obtained by FFL via FEDAVG is equivalent to f
FodAvg the solution to the following constrained optimization problem.
min P * y)
JeF
(FFL. via FEDAVG(E))
s.t. PP
P( a= 6..
The following theorem asserts that FFL via FEDAVG can achieve strictly higher fairness than UFL.
4

---

Under review as a conference paper at ICLR 2022
higher dota heterogeneity
0.5 0.5
0.4
0.3 0.7
0.2. 08
0.85
Accursey
0.80
0.75
Fallog
DP Disparity
Figure 4: Aceuracy-fairnen tradcoff curves of CFL, FFL via FEDAVG, and UFL for two elients cases. Here q. denotes the proportion of group 1 in client i E [0, 1). so |y: qui captures the data heterogeneity of the distribution. The green dotted vertical line describes the lower bound on DP disparity FFL via FEDAVG achieve, and the orange dotted vertical line describes predicted in Thm. and Lemma FFL via FEDAVG's maximum faimess is strictly higher than that of UFL but strictly lower than that of CFL. Morcover, the tradcoff curves are strictly ordered in the same order.
lower bound on disparity UFL can achieve. As
Theorem 3 ((nformal) Fundamental values of federated learning for fairness). Let q =
4 E (0,1) for all E [/]. Under certuin conditions, mingeeoo.1) DP Disp(JeeL) > eFFL via FedArg)- O. min DP Disp(fe
Similar to Lemma 1 the technical assumptions include high enough heterogeneity of x across the clients. Thm. shows that even with just two clients (7 = 2), 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 E,, FFL via FEDAVG can achieve perfect fairness, while UFL cannot.
Remark 1. Extending Thm. 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, conjecture that our lemma holds for more general cases, and we numerically support our conjecture in Sec. 5
Remark There is a stark difference between this phenomenon and the well-known gain of federated learning due an increased sample size, which is almost negligible with few number of clients. Our finding on this unlapped gain in fairness can better support the need for federated learning even between small number clients, which is the case for most cross-silo federated learning scenarios.
3.2 FFL VIA FEDAVG IS STRICTLY WORSE THAN CFL
While we showed that FFL via FEDAVG can achieve perfect fairness on certain distributions, 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 FFL via FEDAVG achieves a strictly worse fairness performance than CFL. This implics a strict gap between the performance tradeoff of FFL via FEDAVG and that of CFL.
which
CFL Optimization We consider the same problem setting as Sec. scenario the following constrained optimization problem:
3.1
We now model the CFL
min P F), s.t. [P 1 0) P(ś FEF
1) S
(CFL(E))
Denote the solution to (F) as JCFL It is clear that JCF achieves the best accuracy-fait fairness tradeoff, 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 is heterogeneous (9, are not all the same).
Lemma 4 (Anformal) A strict gap between FFL via FEDAVG and CFL). When there exist i + j E [T] s.t. di # Q₁ there exist distribution such that minge(o,11 DP Disp(JE FFF. via Fed ming DP Disp([CHL)= O.
Remark 3. strict gap exists for certain distributions, but not for all distributions.
3.3 NUMERICAL. COMPARISONS OF ACCURACY-FAIRNESS TRADEOFFS
One limitation our current theoretical results that they only compare the maximum achievable faimess. Note that such analysis reveals how the tradeoff of accuracy and faimess 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, we leave it future
5

---

Under review as a conference paper at ICLR 2022
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 tradcoff curves for two clients cases. Let a 0,
W/3
a = 1, = (5, 1), a = 0, = (V1, 1), a = 1,i = 1 1)) i= Bern(qu),
Bgrn(g1): 17()) 14e-r- and vary the values of 2o and 91- Note that |91 Qol captures the heterogeneity of the sensitive data 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 increasing gap between the tradeoff curves as the data heterogeneity increases. Theoretical understanding of this phenomenon remains open.
FEDFB FOR IMPROVED FEDERATED FAIR LEARNING
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 federated learning algorithm that is strictly better than FEDAVG-based approaches? In this section, we propose new federated learning algorithm for fair learning, which we dub FEDFB (short for Federated FairBatch). Our approach is based on the state-of- -ftte-arrt (centralized) fair learning algorithm FB (short for FairBatch) (Roh et al., 202I) and has few desirable theoretical guarantees. Later in Sec. [ we empirically show that FEDFB outperforms FFL. via FEDAVG and closely matches the CFL's tradeoff on various datasets.
We first provide brief review of the FB algorithm. FB solves a bi-level optimization problem to learn fair classifier on centralized data. The inner opti- mization problem solves a weighted empirical risk minimization problem where samples from differ- ent groups are reweighted by different weights. The outer optimization problem optimizes the weights used for the inner problem, with the goal of min- imizing the unfairness of the classifier. FB works for various group fairness definitions including de- mographic 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 predic- tion rates P(ý If this quantity is zero, then DP Disp is zero, so the sample weights are updated. If this is positive, it decreases the weights for the samples whose y 1, = 0 and increases the weights for the samples whose y = 1, a so that after retraining, P(ý increases. And vice versa for the other case.
Algorithm 1: FEDFB algorithm
ClientUpdate(i, w, A):
Update ((( according to the sample
weights X;
(+) + ((...a)=(haaa)) E(y. w)), V(y,a);
Send (t( L (w) for all (y. a) to
server via a SecAgg protocol;
ServerExecutes:
for each iteration do
Clients perform updates;
SecAgg((
L y.a < SecAgg( L.fa }), V(y,a) a);
< Update(A Lyya); Broadcast and À to clients;
o
0) IP(y = 1 = 1).
a 0) decreases and PP-- = 1
FEDFB is 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. is the pseudocode of the FEDFB framework. Note that the update rule for group weights (denoted by X in the pseudocode) only requires the sum of the group losses, which enables secure aggregation. In Sec. B... we present the detailed description of the algorithm, which consists of the local training algorithm with

---

Under review as a conference paper at ICLR 2022
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 strictly worse performance than FEDAVG. This can explained by noting that the average of two fair models may not be fair all.
SYNTHETIC
ADULT
COMPAS
BANK
Mirmoon
Acc
DP Disn(L)
Arc-(1)
DP Desn(()
ACC-(t)
DP (U)
Anc((t)
DP Dise(()
FUDAYG
8865 003
406=.009 009
829:.012
.153 002
.655 009
.6672.057
.98.2.00 001
.064 003
UFL
7272 194
.248=.19 194
825 008
0544. 028
.600 019
088 055
8914: 002
0144 006
FFI. VIA FRnAvG
8232 102
305=-151
801 + 043
.233 071
.5952 005
0592 009
8914: 000
0177 001
FEDFB (OURS)
.6132 007
.011=,009
7654..001
.0011.001
.522..00 001
.0011.001
$8341.000
.0001.000
CFL
.226+.009
.028=.016
8116+.010
.0455.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-weiggh 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 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 com- municating 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 quantization scheme limits the amount of additional information shared between the clients and the server, at the cost of potentially inaccurate group weight updates.
means each loss value is uniformly quantized using 10 bits. Such a loss
EXPERIMENTS
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-fairnes. tradeoff of UFL., FFL via FRDAVG, and CFL by numerically solving UFL-G, eq) FFI. via FEDAVG( and CFL(e) 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 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 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. [ 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.
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. (,c)) are the numerically computed lower bound on UFL's achievable fairness. In particular, for (b), we let x a = 0, = 0 ~ (10, 0.22), x a = 1, = O ~ N(9.8, 0.22), (orn(..2), and for (c), we let
0,i x a = - 0, 0~,,3 1), (0rn(..5). For both cases, we set 17(x)) = I-e- It is easy 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., 8 > O. 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.
(0.2. 0.2 x 1, ~ (10 0.2 ) 1),x a = 0, = 1 ~ 1), a =
a 1,i
Ai=1~N(-1,1))
5.2 ACCURACY-FAIRNERS TRADEOFFS OF UFL, FFL VIA FEDAVG AND CFL
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.
7

---

Under review as a conference paper at ICLR 2022
Table 2: Comparison of accuracy and DP disparity on the synthetic dataset with varying heterogeneity, FEDFB achieves good performance on all the tested levels of heterogeneity. This is because by design, FEDFB closely matches the operation of CFL, whose performance is independent of data heterogeneity.
Low DATA HETRROGENETTY
MEDUM DATA HITFROGEAFITY
HIGH DATA HETTROGENNTT
METHOD
ACC,(1)
DP DisP(()
Acc.(t)
DP DISP.()
ACC.(1)
DP DISP.(.)
FEDEB (OuRS)
669m 040
028- 042
613+ 007
.0112.009 .028:2016
.677.0019
.030 .22
CFL
.226.009 009
.08 .016
.226:..00 .009
.726:1.009
.028:1.01
As shown in Fig. 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 HEDAVG-basel federated learning in improving fairness. A very interesting observation is that UFL observed 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 fair on some sub-distribution.
5.3 FEDFB EVALUATION ON DEMOGRAPHIC PARITY
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 = max IP(8- = 1 a = a) - (p = 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-ar fair learning algorithm better performance, the implementation of UFL, FFL via FEDAVG, and CFL are all based on FB, Note that UFL 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 fairer comparison between FFL via FEDAVG and FEDFB, we also equalize their differential privacy guarantees (Dwork) (208) and compare their performances. See Sec. C for more details. We also report the performance of FATRFED, a recently proposed algorithm for achieving demographic parity for binary sensitive groups in the federated setting (Ezzeldin et al. 2021), and AGNOSTICFAIR in Scc.
centralized data. for fairer comparison and
Datasets (synthetic) We follow Roh al. (02T] for data generation, but with a slight modifica- tion 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.c.C.. (real) We use three benchmark datasets: Adult (Dua & Graff 2017) with 48,842 samples, COMPAS (ProPublica 202I) with 7,214 samples, and Bank (Moro et al. 20144) with 45,211 I samples. We follow Du et al. (222)'s ''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.
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 reports the test accuracy and DP disparity of four baselines and FEDFB. We see substantial fairness improvement obtained by FEDFB As ex-
Aceurcey
0.8
0.7
RdIBB [MIE))e)))
pected, 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 repoots 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-fairnes 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 shoocassss the benefit of FEDFB in terms of accuracy, faimess and privacy. In Table 7 and Table Sec. C we compare FEDFB and FAIRFED. One can observe that FEDFB can achieve strictly improved fairness than FAIR Also, FEDFB is observed to be more
0.0
0.5
DP Disparity
Figure 5: Accuracy-
fairness tradeoff curves on the synthetic dataset. FEDFB nearly matches the performance of CFL.
8

---

Under review as a conference paper at ICLR 2022
Syntandic
Adbult
COMPAS
Bonk
0.86
0.90
Accuacy
0.65
0.8
0.84
0.50
0.7
0.82
0.60
0.0
0.2
0.0
0.2
0.00
0.05
0.10
0.0
0.2
CP Disparity
Figure 6: Comparison of accuracy and Client Parity (CP) disparity on the synthetic, Adult, COMPAS, and Bank datasets. Even though our algorithm is not specifically designed for CP, it closely matches the performance of the ofate-of-the-ans art fair federated learning algorithms designed for CP.
robust to data heterogeneity. Table in Sec. C shows that FEDFB achieves similar performance as AGNOSTICFAIR, at much lower cost of privacy.
5.4 FEDFB EVALUATION ON CLIENT PARITY
We evaluate the performance of FEDFB in achieving client parity (CP) and compare it with the otate-of-the-art algorithms for CP. We will measure CP disparity [a [Z I Here
( the loss in ith client, see Sec. B.4 for more detail.
Baselines We consider GIFAIR (uue et al. (021), Q-FFL. ( et al. 2020a). DITTO at. [021] and the unconstrained baseline FEDAVG MMeMah 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 a-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. 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.
CONCLUSIONS
Summary We have investigated how one can achieve group faimess under 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 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) AaD federated fair learning algorithms are strictly worse than the oracle upper bound of CFL. To close the gap between FEDAVG-base fair learning algorithms and CFL, we propose FEDFB, 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- performance, while still ensuring data privacy.
Open questions (Theory) While we characterized some fundamental limits on tradeoffs of various approaches, there still remains large number of open questions. First, as we briefly mentioned in Sec. 3.3 full theoretical characterization of securac--firress tradeoff still remains open. Our current theoretical results only study the extreme ends of the tradeoff curves. Moreover, as shown in Sec. 5.22 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, three-way tradeoff between accuracy, fairness, and privacy remains widely open. (Algorithm) 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 faimess used in the federated setting, and our current FEDFB cannot handle it. Extending FEDFB to handle proportional fairness is one future research direction.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
This work will improve the well-being of individuals in our society by solving ethical issues of AI, such 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.
REPRODUCIBILITY STATEMENT
We have released our implementation anonymous github 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.
REFERENCES
Lingyang Chu, Lanjun Wang, Yanjie Dong, Jian Pei, Zirui Zhou, and Yong Zhang. Fedfair: Training fair models in cross-silo federated learning. arXiv preprint arXiv:2 (0Kiv:2/09.05000 05662, 2021.
Sen Cui, Weishen Pan, Jian Liang. Changshui Zhang, and Fei Wang. Addressing algorithmic disparity and performance inconsistency in federated learning. In Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
Wei Du, Depeng Xu, Xintao Wu, and Hanghang Tong. Fairness-awarr agnostic federated learning. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 181-189, 2021.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http:://acchhaie ics. uci, edu/ml
Cynthia Dwork. Differential privacy: A survey of results. In International conference on theory and applications of models of computation, pp. 1-19, 2008.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS 12, pp. 214 226, 2012. ISBN 9781450311151. https://doi wwt.oo/........10111111 1145/2090236.6 2te.2229022226222225552
doi: 10.1445/090023.2290055.. URL
Yahya H Ezzeldin, Shen Yan, Chaoyang He, Emilio Ferrara, and Salman Avestimehr. Fairfed:
Enabling group fairness federated learning. arXiv preprint 10X00221 2021.
Sorelle A. Friedler, Carlos Scheidegger, and Suresh Venkatasubrammnnia. On the (im)possibility of fairness, 2016.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in learinng in Neural Information Processing Systems (NIPS), volume 29, pp. 3315-3323, 2016.
Iearning. In Advances
Heinrich Jiang and Ofir Nachum. Identifying and correcting label bias in machine learning. In
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 702-712, 2020. URL http
//proceedings. ml press / / /ass/jjnngaa jiang20a html
Michael Kearns. Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing faimness gerrymandering: Auditing and learning for subgroup fairness. In Proceedings of the 35th International Conference Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pp. 2564-2572, 2018. URL hattt:://proceeeinngg .ll.
httmllmmmmm..mm html
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv wweppimmmmxxhh-71110040022221120
https://ancnymonnn 4open sci wwwpa/eeeeeeeeeeeeeriiiiiiioniie riciinnsss-eee -
10

---

Under review as a conference paper at ICLR 2022
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated
learning. In International Conference on Learning Representations (ICLR), 2020a. URL https
//openreview.oo http//iiwwweeteeeeeeeeeeeeeeeeee net/ htt/:/oommmmmnmeeeee-e /e0pe//sseeee...s../rrmaaaaaaaaa
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In Proceedings of the 38th International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pp. 6357-6368,
2021. URL httt:::/proceeedeeeeee
ml press/ hatesss/v39//111 httm
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In Internationall Conference on Learning Representations (ICLR), 2020b.
URL https::///// httpt:ttttpppeeeeeeeeeee /ttp:////peeeeeeeeeeeeeom net/ wtt.:rruneeeeeeeeeeeeeeemaaoamae Hadd-dh-HHVVLtt.
L. Lyu, J. Yu, K. Nandakumar, Li, X. Ma, J. Jin, H. Yu, and K. Ng. Towards fair and privaey- preserving federated deep models. IEEE Transactions on Parallel & Distributed Systems, 31(11): 2524-2541, 2020a. ISSN 1558-2 1588- doi: 10.1 202.PPDD..00..992222
Lingjuan Lyu, Xinyi Xu, Qian Wang. and Han Yu. Collaborative faimess in federated learning. In Federated Learning, pp. 189-204. Springer, 2020b.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agtiera Arcas. coamunication-efficeee learning of deep networks from decentralized data. In International Con- ference Artificial Intelligence and Statistics (AISTATS), volume 54 of Proceedings of Machine Learning Research, pp. 1273-1282, 2017. URL http::
m wt..ss....../
Iomahaan 7a h
Aditya Krishna Menon and Robert C Williamson. The cost of fairness in binary classification. In Proceedings of the 1st Conference on Fairness, Accountability and Transparency, volume 81 of Proceedings of Machine Learning Research, pp. 107-118, 2018. URL http:::/pprocceeiiinig
mlr. m.r.spess/ v8 w 1/wen/nnnnnn 8a. html
Jeonghoon Mo and Jean Walrand. Fair end-to-end window-based congestion control. IEEE/ACM Transactions on networking, 8(5):556-567, 2000.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Proceed- ings of the 36th International Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pp. 4625- 2019. URL http://proceedinggs mlr
press/v971 wttp:////mmmmmmraa.ma html
Sérgio Moro, Paulo Cortez, and Paulo Rita. A data-driven approach to predict the success of bank telemarketing. Decision Support Systems, 62:22-31, 2014. ISSN 0167-9236. doi: https:// do..org/10.11166jdsss.000044 200...0.40........000 wtthttts:tttttttttettttts htt.tp::/www..cceeceeleeeeee
com/ ceam/science/
ProPublica. URL
Compas
recidivism
risk
score data and analysis.
2021.
www.:pppppbl.c......aaaaatataaae https:/
Borja Rodríguez-GGälve,, Filip Granqvist, Rogier van Dalen, and Matt Seigel. Enforcing faimness in private federated learning via the modified method of differential multipliers. arXiv preprint arXiv:2109.08604 2021.
Yuji Roh, Kangwook Lee, Steven Whang, and Changho Suh. FR-train: A mutual information- based approach to fair and robust training. In Proceedings of the 37th International Conference on Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pp. html
8147-8157, 2020. URL hetttp:://prceeeiinng ..l. www.ppess//vll/...
Yuji Roh, Kangwook I Lee, Steven Fuijong Whang, and Changho Suh. Fairbatch: Batch selection for model fairness. In International Conference on Learning Representations (ICLR), 2021. URL
https::/
net/ forum? id -ddYYnaAAeKCKKx
Xubo Yue, Maher Nouiched, and Raed Al Kontar. Gifair-fl: An approach for group and individual fairness in federated learning. arXiv preprint arXiv:2108.02744 2021.

---

Under review as a conference paper at ICLR 2022
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P. Gummadi. Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreat- ment. In Proceedings of the 26th International Conference World Wide Web, pp. 1171-1180, 2017a.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, Krishna P. Gummadi, and Adrian Weller. From parity to preference- based notions of fairness in classification. Advances in Neural Information Processing Systems (NIPS), NIPS' 17, pp. 228 238, 2017b. ISBN 118669944
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P. Gummadi. Fair- ness Constraints: Mechanisms for Fair Classification. International Conference on Artificial Intelligence and Statisticc (AISTATS), volume 54, pp. 962-970, 2017c.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International conference on machine learning, pp. 325-333, PMLR, 2013.
Daniel Yue Zhang, Ziyi Kou, and Dong Wang. Fairfl: A fair federated learning approach to reducing demographic bias in privacy-sensitive classification models. 2020 IEEE International Conference on Big Data (Big Data), pp. 1051-1060, 2020a. doi: 10.1 http:/B/DDD.55002222200000099550
Jingfeng Zhang, Cheng Li, Antonio Robles- Kelly, and Mohan Kankanhalli. Hierarchically fair federated learning. arXiv preprint arXiv:2004. 2020b.
12

---

Under review as a conference paper at ICLR 2022
Symbol
Meaning
Symbol
Meaning
Symbol
Meaning
feature
[-]]
indicator function
C₁ DP Disp(f) Sen
bias in client a ~ Bern(g) unfairness of UFL classifier
a
sensitive attribute
f
randomized classifier
client index
distribution
predicted class
n(a))
= =
Table 3: Commonly used notations.
A APPENDIX UFL, FFL VIA FEDAVG, CFL ANALYSIS
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.I Then we analyze UFL and FFL via FEDAVG. To be specific, Sec. A.2 we analyze the limitation of UFL and present the formal version under two clients cases and Corollary 2 In Sec. A.3 we analyze FFL via FEDAVG and compare with UFL and CFL, then we present the formal two-client version of Thm. and Lemma All the multi-client statements are included in Sec. A.4 We summarize the commonly used notations in Table 3
of Lemma] |
A.1 CFL ANALYSIS
In this section, we analyze the CFL classifier fCFL given in CFL(E) We mainly derive the solution of CFL(()) in Lemma 5 In Lemma and Lemma 7 we summarize the properties of fCFL.
Lemma 5. Let (0, Define g()) [- max (g. -gg, max(g, 1 - 9)1 [-1,1] as
9(A) == =f
dPo S
1/ x1-1) x1-o)) tc]
|n- dP1.
then sCFL {[s(,,a) a) 0] + aa[s(z, 0] a E [], where s(x, 2n(x) 1+ -
s(x, 1) = 2))(x) 1 3. = g (sign(g(0)) minfe, (00)))). Here denote the indicator
function as [E] [E]] 1 if E is true, zero otherwise.
Proof. The proof similar as Menon & Williamson (018 To solve CFL(E) we first write the error rate and the fairness constraint as a linear function of f. Let (-(.) be the pdf of Pa, where = 0, 1. Denote the joint distribution of x and a as pxa(x, a). Note that
P(ś + y) 1
-1- f(2, Px.o a) dx
BEA
Bxa. (x, a)(3a))(22))))) 2n((x) Py 1)
and
P(ý- -P a = 1)
/ f(x, ()po())) de
[1x (1)
Σ la = 0lf 0) (I, a)
Px.a a)
P(a dx - [[f==][(x11)
(pa = dr
X a
nEA
f(x, aa la=0) f(x, 1)
= 11]
=Ex,a
1-q
q
Consequently, goal becomes solving
minser (x,
a)(1 2n(x)) + Ply
s.t. EE..a
[(x,
0)
[a=0|
f(x, 1) |ل=م||
(I)
I-q
13

---

Under review as a conference paper at ICLR 2022
Denote the function that minimizes the error rate (ERM) f F. It is easy that,
f(x) E (1v(()) > 1/21 + alv(a) - 1/2] : a E 1]].
Next, consider the following three cases. In particular, provide the proof for MD(()) S and MD(f) The proof for MD(f) - is similar the proof for MD(f) E.
Case 1. IMD(f) S e: ERM already fair.
The solution i and CFL(E i8 f.
Case 2. MD(f) E: ERM is favoring group over group I.
We will show that solving ! is equivalent solving an unconstrained optimization problem.
First, we will prove by contradiction that the solution f* F to I satisfies MD(J*) = e. We F to denote the solution of ( Suppose the above claim does not hold. Then have MD(f*) < E. To show the contradiction, we construct a f' E JF that satisfies the fairness constraint and has lower enror rate than that of f". Let f' be a linear combination of f" and f:
=f + (1-a))f
where a MD(/)=e MD(()) E0,11) 1). Then we obtain
MD(f") aMD(ff*) a)MD(}) =MD(() MD(ff))
MD(f) MD(f*)
Denote the error rate P (ÿ yy e: F 10, 11. Then the error rate of f' is
<(f') = ae + (1 a)e(A) < e(f"),
which is inconsistent to the optimality assumption of f Therefore, MD(f*)
Now, solving CFL(s) is equivalent to solving
min Ex,af(x, a)
2n(x)) + Ply = 1) |==0l f(x, 1) للتجاا =
s.t. Ex,a f(x, 0) 1-q
Furthermore, the optimization problem above is also equivalent to
[a 0]
[a [aa 1]
minseF Ex.a a1 - 27)(x)) - AEx,
[(x, 0)
[xx
(2)
1 1
f(x, 0) [a = 0]
[a = 1]
s.t. [xx
f(x,
1)
=
(3)
for all À E R.
Next, our goal is select suitable such that the constrained optimization problem above becomes an unconstrained problem, i.e., we will select suitable X such that the minimizer to the unconstrained optimization problem (2) satisfies equality constraint
Note that
aa 0]
aa
1]
Ex, ax) ALEx,
f(x, 0)
f(x,
=Ix, (1 2n(x) 1 [aa 0]
[a 1]
q
then the solution to unconstrained optimization problem 2 is
j E {Is((r,a) > 0] + al[s(2; a) 0] [0,
14

---

Under review as a conference paper at ICLR 2022
1.0
s(0)
0.5
0.0
(c)
-0.5
[g(A)]
-1.0
0.4
-0.2
0.0
0.2
0.4
Figure
Visualization of (A) and I9())). When g(0) = MD( the corresponding of the best classifier À 9 (c) < O.
where
- 1 + 2n(x) + X a=0 -1 2n(x)
s(x, a)
I-9
a=1
Since the range of 7Tx) is [0.1], f with À max(q, g) is different from f with À max(q, 1 - g): with < max - q) is no different from f with À max(g, q). Therefore, the only thing left is to find the x E max(q, g). max(q. q)] such that satisfies the constraint
Now consider the mean difference between the positive rate of two groups:
MD(J) P 0)
PPý
a = 1)
1 A
1 + dPi
[n(x)
dPo
[T(())
IdP
2
2(1 - 9)
2
24
00
dPo
dP1
10-1(1 (1- - X00
+ +,00
(())
Note that g(-) [- max(q. 1-q). 9). max (g. 1-1)1- 9)1 [-1, a strietly monotone increasing function.
Consequently, if and only if constraint (3) equivalent as CFL(e) Thus, let
(s), satisfies 3 Recall that optimization problem (2) with
(e) and f is the solution of CFL((
Case 3. MD(F) -E: ERM is favoring group I over group
Similarly, like Case 2, we obtain that the solution CFL(e) is
f E {[[s(z,a) a) > 0] + al|s(z, a) 0] : [0.1]}
where
s(x, = -1 2n(x) I- a=0 -1 2n(x)
a=1'
and A >= 1 Combining all the cases above yiclds the desired conclusion. The proof is now complete.
Remark 4. Select a 0, then the solution to CFL(E) can be written as
f(x, 1--[[m [n(()) 1 [n(xx)
a=0
(4)
a=
Therefore, Lemma implies that the best classifier of the CFL problem is equivalent to simply applying constant threshold to the class-probabilitiss for each value of the sensitive feature.
15

---

Under review as a conference paper at ICLR 2022
Lemma 5 suggests the following property of the solution to CFL(E)
Lemma 6. If f and are two solutions to CFL(s) then f = 9 almost everywhere.
For illustration purposes, we denote
x g (sig min le(O)))).
(5)
Below we summarize some useful properties of X
Lemma 7. The sign of XE and MDF are determined by g(0).
1. If 19(0)), then MD( (EFL) ACFL * 0, and g(xe sign(g(0)) If (o() e, then
x CFL and MD(Je ((FL) g(A = g(0).
2. If (0) > 0 or g(0) < 0, then for any E 2 0, we have X < 0 or X 2 0, respectively.
Proof. The first property follows directly from the definition of X Next, we prove the second property.
When E (g(0), we have 0 and the first property holds. When g(0) > > 0, by the definition of CFI. we have À = g (a) < g (g(0)) O. When g(0) - < 0, we have
--- (-8) > agg (g(0)) = Combining the cases above yields the desired conclusion. n
A.2 UFL ANALYSIS
With the analysis of CFL in Sec. A.1 in this section, analyze the UFL classifier UFL E, for the case of two clients. For illustration purpose, with I = 2, we denote f1IF. = fl ff + f
In Sec. 1.2.1 we introduce some notations for the UFL classifier [50.51 that follows from Lemma
In Sec. A.2.2 analyze the limitation of pUTT, stated in Sec. 3.1 To be
specifie, present the two clients' version of Lemma [ formal version of Corol lary 2 and conclude their proof. In
Sec. A.2.3 analyze the performance gap between f and CFL classifier fCFL.
A.2.1
PROBLEM SETTING
By Lemma 5 the solution to UFL(1, s;) is
[n(xx) > [m((()) >
Ae
f (xx a)
-(-17 97
=
where the associated LFL, is defined as
UFL 9, (sign(g (0)) min(e,, la (0)))
(6)
and
9:(A) /
dp(() J
dp(
1(3 7
In 1 2 )00)
Note that (x()) is the mean difference on ith client E p(o [x, 0) - E x (x, 1) of the classifier of the form Now, the demographic disparity for JUBL can be written
DP Disp( Disp(Ftrr))
[F 1 a - Ppý
1,i i)
Exppit (3) 15 (x, -E x 19 (x, 1)}
i (oo(2! + go ( UIFI.) + (i + (2 J.
For ease of notation, we define local mean difference on ith client as MD,(f) = P(y = 1 1, i) and local demographic disparity ith client as
= 0, = i) P(ý
16

---

Under review as a conference paper at ICLR 2022
DP (f) [ where 0, Since the overall distribution of the data samples is x a a ~ Pa = - /2 + PP /2, = 0, 1, (see the definition in Lemma 5) and go: 91 has the following relation:
(() _ (00(2) ()) + 1+tz900
(2). (2).
A.2.2 LIMITATION OF UFL
In this section, we mainly analyze the limitation of UFL in Lemma which shows that fUFL. can not achieve 0 demographic disparity in certain cases. Corollary 9 is specific example of Lemma g
Lemma 8 (Formal version of Lemma under two clients cases). Let E (0, Let
min(lgo(0)) ( (0))). Define &a [0, c| 0. + [-1.1]
1
(E = MD(
4 90 1 (sign( (0))s))) + 19 " (sign(g0)))))))
(7)
+ (0)) + (ig)()
If go((0) (0) < 0 and vp(co, E1) (g) 91 (0)) > for all eo, E [0, then all co, 61 E [0,
DP (i FUPL 2 min e1)l &1 [0,c]] >
Proof. Define = min (Voo, e1)l cu, &1 E c0. The goal is to show that the demographic disparity has positive lower bound. Note that the mean difference can be expressed
MD 4 ( + go (A + gi (AEo ) + + t1 (AEHt)).
(8)
In the following proof, we will show, the mean difference cannot reach O.
Without any loss of generality, assume [0)( (0)]- First we consider gn (0) 0. We will discuss 9r (0) < O later. By go g0) (0) < and (h(Eo, (9o.))))) + (0)) > for all co. 61 E [0,
we have go (0) < 0 and & > 0 for all 60, [0,
First, we will prove that UFL achieves its lowest mean difference when 6p, E [0,c] In what follows, consider five different cases to derive the desired result.
Case 1. cn > (go(0)), > 191 (0)l: ERM is fair on both clients.
By (6). have XUFL.
As 2 = 0. Recall ge(-) is monotone increasing function, combine
9i (0) and Lemma to have go( (0)) < (0) < Applying the above conclusion yields
4 (0) + 9 (0) 1 =0000r'
(0(0) 70h > 2
2nb(go (0), 2 5.
Case 2. eo S (0o(0)), 191 (0)]: ERM is unfair on client O, but fair on client
Applying have
results in UFL, 0. By the fact that gi(() is strictly monotone increasing function,
90 (-sp) 90 (g) 0. Applying the above conclusion yields
1
1
co
4 (1)
+ 4 ()(
1 g2 (AUFLO) (AUFLO 0. (2 g1(0), (o -Eu)
1
2 (0) +
2 91 (0) 20 (0) 2
Case 3. Eu < (0), E1 (0]] ERM is unfair both client 0 and client 1.
Applying 6 we have UFLa = 90 - (-eo), UFL (E1). Then we have
(-c0 + g (EI)) + g1 (g (-so)))
2 (-ou t gol (Eo) + ga (gp (-Eo))) = ()(, 2
17

---

Under review as a conference paper at ICLR 2022
Case 4. Eo > 19o(0)), E1 (o)( ERM is fair on client 0 and very unfair client 1.
By 6 we have A = 0, A1
UFL1 (E1) > 91 (0). Then we obtain
4 (00(0) + 90 ( + (0) + +1
(0) + 90 1 (0)) + 91 (0)) (g))
Case 5. Eo > [9o(0)], 9o (0) S 1 < 19 (0):: ERM is fair on client and unfair on client 1.
Applying (6 implies UFL1 = 91 - (61) > 91 1 (0). Therefore,
1 (90(0) + 9 (=1) + + g1)))
4 > (0)(0) (0) 9 (0)) + /1/ (0)((0)))) 2
Combining all the cases above, we conclude that when 91 (0) 0 DP Disp ( 2 8 min())((E,$1)) co. E1 [0,c]] > 0 for all ED, [0.
Now we consider @1 (0) < 0, by the setting [0)( < 99 (0) and the assumption (0(())1()) <
and (bEE,, (9) + 91 (0)) > 0, we have (0) 0 and E1( < 0 for all Eq [0.c].
Following similar computation above, Case Case become:
Case 1. Eo > (9o( E1 [0)] Now have go(0) go(oT (0)),
(0)), thus
88)
2
4 ()(
1 (0:(0))
4
00000 (0)) 24)(00 0) s -5.
Case 2. co S 19o(0)), 21 19:(0)) Now we have (0) > ED. 91 (AUFLo) < 91 (0), thus
1 90 (0) 2v(g0(0),,) s 8.
8 (0)(0)
Case 3. In this case we have
1
4 (50 - E1 61 (-E)) gi (9o (so))) = (100 s -8.
Case Now we have X = 97 1 (-81) < .6 (0), thus
g
(0o(0) + 9o (0) (0)) + (0)) = (0o(0)) S -8.
Case 5. Now have XUFI.1 = -1 (-21) 91 (0), thus
(0) + (0) + go ( (0)) - -x1)/4 < (0)0(0)) s -8.
Then we conclude the proof.
Remark 5. Note that c the smallest local demographic disparity the ERM achieves on clients. The condition go (1) (0) 0 implies that the ERM is favoring different groups in different clients. The condition 36(Eo. 61 (g) + 91 (0)) > 0 for all Eo, 61 E [0,c] implies that FUFL favors the same group as ERM when the constraint very fight. the conditions above hold, Lemma Auggesss 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.
suggessts that
go (0) < 0 can be satisfied by the distribution with high data heterogeneity. To demonstrate the condition (EEE. E (0) + gi (0)) > 0 for all Eu. E1 E [0, cj be satisfied, consider limiting Gaussian case. The following corollary serves that satisfies the conditions of Lemma g and provides a more explicit expression of the lowest demographic disparity UFL can reach in the Gaussian case.
Among the conditions of Lemma 8
example
18

---

Under review as a conference paper at ICLR 2022
Corollary (Formal version of Corollary P. Let q 0.5, nyxx) I+- pa -N(ua , {()))
where (10) (0) pi (0)) (ug" ( < O. Then DP Disp( 2 ô ~ (0 91 (0) for all
80 [0, 1] if one of the following condition holds:
1. o(0) > 0(1) 1 ( 1,116" Ix() and Mo pi ())
(1)
client 0 has much larger variance
than client 1, and client is favoring group 0;
2. g(1) >> 000)
1pu I. 1p1 10)
(0)
(2) 1u1 (1) and Mui
(0)
> p1 (0);
client has much larger variance
than client and client 0 is favoring group O.
Proof. In this example, note that local mean difference function of À can be written
9: (A) $5( 7 ( + -
(2 A) 140
+
o(4)
g(6)
where (() is the CDF of the standard Gaussian distribution.
We only provide the proof for condition 1, and the proof for condition is similar. Assume condition
1 holds. By (Ho (0) (0) (Ho)) (1) p1 (1)) < 0 and Ho 11 > O, we have Hn μi < 0. By 9
(0) (0)
we have (0) < 0 and g1 (0) > Consequently, combining Lemma 7 and 7 yields
1
(EE, E1)
4 (golg) (s1)) + 91 9 (-co)) Eu Eo +1).
First we show that (5 51) reachs its minimum either at (c, 0) or (0, c) by taking the derivative of v), where e min (0)), ( (0)) the smallest local demographic disparity. And then, we will estimate the minimum of // on [0, 1] x [0, 1].
We take the derivative of &p with respect to E; and get
Oup 0c,
(1+ 5i (sign(s, (g,(())())))) (0))::))
(co, 61) = sign(a((0)
/4.
L/g, (0))
By condition 1, we have (0) = 2 1
=e 0, thus [0)
< 191 (0) and = (0)
c 00
Since 9i increasing function, = 0, have (.( 0, and thus
0e
0, dy
0. Therefore, de
dev
reaches its extreme value at (0, c) and (c, 0).
Now, we evaluate
(0)) (0))/44 (0) 000 go(oi (0, (go(o) 91 91 (0))
where the inequality comes from (0) 0 have 91 (gp '(0) gi (0). And at (c, 0), we have (c, 0) = (go (0)) + 91 (0) + (0))/4.
In what follows, we will show that min (b(c,, (0, c)} = = 91 gg) by proving that 0 > go (c)) > go ( (0)) x O.
Consider (bc,, 0) and (0, c). Since 9 (0) c, 90 (0) 0, we have
go(o)>(0) - (c) < go (0) < 0.
Therefore, the only thing left is to show g (0)) z We divide the rest of the proof into the following three cases.
Case 1. p1 pb (1) O: client 1, the local classifier is favoring group 0 over group and the positive rate of both groups are under
(1)
19

---

Under review as a conference paper at ICLR 2022
Clearly, under this case, we have (g),o) dP( 10 dp))) (1) that ( + X) = ui Then we have J1 x2)+ dp -uff ,o) dp(") = 2 while
<2 We select X such
dp 0. Thus we get gi (X) < Combining 91 (0) and intermediate
value theorem results in X < 91 (0) < 0. Then we obtain
1
11 = (
+ +X) < <
+ DT (0)) <0
2
(10)
1
1
1
11 n 1-1
1 n7 ( 91 (0)) (n12))
odd)
2
By plugging (10 into we have the other side of go (0)) < 0 is bounded by 9u(X') =
Since σ(1) >> |m( 11 we get go (91 (0)) 0.
Case 2. 0 < 14 Po client I, the local classifier is favoring group 0 over group I, and the positive rate of both groups are above 2.
(1)
This proof of this case is similar to Case 1.
Case 3. 11 < Mn ( with respect to the local classifier trained by client 1, the positive rate of group above while that of group is under 1 2'
Without any loss of generality, we assume
1R1 1p0 0 Select X" 0 such that n( - X") M40 (1)
Clearly (1n dp!l) -J (10g)+00)) (00) dp())
while
/ ji-m!") (+0)) (000)
dp(1) =
dp(")
dp())
[1='(++\"),+oo0)
(-n(")
+00)
2
Consequently, we get 91 (X") < and X" < .. (0) < 0. Then we draw the same conclusion as 10
Therefore, ( (0) = 0.
Combining all three cases above, we get d 0. Then applying Lemma g we complete the proof.
A.2.3 COMPARISON BETWEEN UFL AND CFL
In this section, we compare the performance of UFL and CFL. In Lemma 10 and Lemma I1 illustrate the conditions for UFL to have the same performance as CFL. In Lemma 12 Lemma T3 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
Acc(f) P y) = Py O) f(xx a)] + Ply 1lEx of a).
Given the required global demographic disparity
dispariit e, define the performance of FUFL. as:
UFL(Eo,e1;E) ( AAc(SJur) LUFL
DP DFFF S
o.w.
and define performance of JCFL as:
CFL(6) = Am
Now we are able to compare the performance between UFL and CFL with the metric (1; and CFL(s). In particular, will show that, under some mild conditions, max.0.51 UFL(E), CFL(e), which implies the gap between UFL and CFL is inevitable.
We begin with the following two lemmas, which describe the cases that (EF(()0,11;) = CFL((E).
20

---

Under review as a conference paper at ICLR 2022
Lemma 10. Let (0, 1). Given UFL classifier Jea.e: such that DP Disp (Jaee) ) I and CFL classifier fePL we have UFL(E0, E1ie) CFL(E). The equality holds if and only if AUFLo X XFF, where X is defined in UFlo, A1 UPI, are defined in 6
Proof. The proof is straightforward. Clearly, since f is the optimizer CFL(2)
we have Sso is
UFL(E0, E1:E) < CFL(s). By Lemma 5 according to the form of the solution to CFL(() the solution to CFL(E) if and only if X XU X Thus complete the proof.
Lemma 11. Lef y E (0,1). the ERM is already fair, i.e., 2 lo(0)), then max UFL(E,, = CFF(E).
Proof. Since the ERM is already fair, JCR. is ERM= [m(x) 1/2]. Therefore, we take En = 51 LUFI. also equals to ERM. Thus we conclude the lemma.
and Jo
The next two lemmas describes the cases that UFL(Ee, S1;8) < CFL(e).
Lemma 12. Let q E (0, If (0)))) 0, maX UFL(E,.E1:E) < CFL(E) for all e < lo()))-
Proof. In this proof, we only consider the case that 91 (0) > 0, | (0)l 2 [go(D)]- The proof for 91 (0) > 0 or 191 (0)) 2 [0)( is similar. Next, we divide the proof into two cases.
Case 1. maXeo.e1 UFL(En,81;e) 0: UFL cannot achieve global demographic disparity.
The conclusion holds.
Case 2. maXep.e, UFL(E0.E1:E) > O: UFL can achieve global demographic disparity.
* 0. Next, solve JULL by solving the local version of CFL(E) Combining Lemma 7 91 (0) and go( yields UFL 2 A UFL, s
Since Ig) by Lemma have
X CFL
UFL LF. then UFL.
UFF.1 * CTL. 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 UUI and that of CFI.
Lemma 13. Let E (0, 1). Lett min {lo(0)), max max(sign !f go (0) (0) > 0, we have
(0))
CFL(E) for all CFL(E) o.w.
max (1F(5))811i)) Eo.E1
Proof. Without any loss of generality, assume go go( (0) 0. Then by Lemma we have UFLa 0, XULL < 0 for all Eo, $1 E [0, 1], and g(0) = (go(0) + (0))/2 > 0. Ag
To study the performance of UFL when go (0)g) (0) O, recall that we use f.fx denote the local classifier trained by client in UFL analysis. Therefore, l 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 t = O, and then prove that max;,.s; UFL(E0, E);E) = CFL(s); Case 2, we will show that > and then prove that maxxo.e; e1 UFL E1;)) < CFL((E) when <.
Case 1. /8 =f: the two local classifiers that achieve perfect local fairness equal.
21

---

Under review as a conference paper at ICLR 2022
When 2 g(0), the conclusion holds by directly applying Lemma 11 Therefore, in what follows, we focus on the case that E < g(0).
Next, we will first, show that when E = O, Ao UPLo JOFL.
X0
UFL1
10 CFL, which implies that f8 fP
Since fo = fi. we have Ao CPL = Ao UPLI and thus 90 (0) = -1 (0). Consequently, we get
s(A0PLo) g(Ao = ul9o (0)) 90(9 (0)) + g1 (9 (0)) 0 = g(Ao
2
By the monotonicity of g. we have X = 2o UPL = A and T = 0. Next, we will show
that, for & + D, there also exists ED, E1 E [0, 1] such that A = UUFL = ACHL, which implies PUFLo = SEU -
D: (A ) 0. By Lemma 5 and the monotonicity of 9. we Consider & * O. Select Therefore, E, (ACRL) > g: (; CFL) 0. By Lemma 5 we get have X1 CL XCLL
9: (5x) for i 0.1. By the selection of Es, we have XC 9, (Ex). Therefore. XCL = xURLo UFL when s * O.
XURL
Combining all the discussion above yields Seor: FCFL for all & < ((),, thus we conclude max UFL E1;E) = CFL(s) for all & < g(0). Consequently, the lemma holds under Case
Case 2. fo & ff: the two local classifiers that achieve perfect local fairness are different.
The key idea of this proof is: when MDo(JE
CCLL) ), MD, (fen)) 2 O, then we can always se- M > such that s thus fuL
lect EO (1 MDo(JE 0,51 (1
XUFLo
9o (so)
XCHL and AUFL
91 (si)
S when
MDo (FFL)DDDD (S.TL)
(o 0g (ACFL) < O. however, by Lemma 7 for all Eo, 51 E
[0, 1J x [0, 1J. we have go (A Igi (AUFL) > 0 9o()C (ACH)), thus there exist i E {0, 1}
such that UUFL o XCFL and PUEL # JCL Next, will give rigorous proof.
Since f8 * ff. we have A UFL + Ag UFL.1 By Lemma we get 90 95' (0) * 91 (0). Without any loss of generality, assume 90 (0) < 9 (0), which implies 9n (g (0)) < ( (0)) = 0 and
go( (o())((()) = < -0(0)'100000 (0)). Thus we get
gi ( (0)) < 0 < go (0))..
Combining the inequality above and g 2o # yields
5 = 91 (0) < 0 9 -o (0)) = g
(11)
Thus we have
T= == (())) (0)) signn (0)) .69 (0)).
When lg(0)), by Lemma 11 clearly we have max UFL CFL(s).
For the other case E <
()) by Lemma 7 we have x (E). Similar to Case 1, in order to we select E, = gi ).CF..)
achieve UF.. X L CH..
When < 1
(A = (t)) < gi (o(o 0.
Since (0) > 0, by Lemma we have 91 (AUFL) > 0, from the monotonicity of 9i we conclude
XUFL * CF.. By Lemma 10 we have max UFL(E,,E1:E) < CFL(s) for all E S
When & . ( (0)), applying 11 we have
(0) > E, = (g (E)) 2 ( 1 "9(6 (0))) =0
where the first inequality comes from Case 1. Thus, X; g (c,) À desired, and obtain JUAL - CFL
Combining both cases above yields the desired conclusion.
22

---

Under review as a conference paper at ICLR 2022
Remark 7. Recall that use f;" denote the local classifier trained by client i in UFL analysiss.
In the expression of
min [19(0)] (
lo(0) is the demographic disparity of ERM, sign(g(0))9(96 (0)) is the demographic disparity of local classifier fü. and sign(g(() (9 (0)) is the demographic disparity of local classifier fi. According to the proof of Lemma 13 we obtain
(0)), sign( (ig)(g(0))g{gi (0))} > if and only if two local classifers which achieves perfect local fairness equal, ie.. fo ff. Therefore, Lemma 13 implies that, if the ERM is favoring the same group on different clients and the two local classifters which achieve perfect local fairness are unequal, then UFL performs strictly worse than CFL when the required demographic disparity is smaller than certain value.
So far we assume ~ (q) for both client O and client 1. When both clients do not share the same 9, we can conclude that CFL outperforms UFL in the following lemma.
Lemma 14. Assume a Bern((.) in client i, and qo
+
41
E
(0,
Then
maXeo.e: UFL(Eu, E1;E) < for all (g(0)]-
Proof. We assemble the dataset from two clients to have a a= a Pa
90
Pa
T P!!.
40
90
0, We let fe be the solution to CFL(e) with q t.
,CFL.
[s( a) > 0],
CFL
s(x, 1) = 2n(xx) - XF
where s(x, = 21((z) - 1 I- q"
q
Given an UFL classifier Seare (S0 + //1)/2 such that DP Disp ) S s, the solution reads
f = [2; a) > 0].
UFL.
where s1 0) 2n(xx) 1
E,
s1(2; 1) 21((x)
E
%
4:
prove the lemma by contradiction argument. Ace JUL CFL(e), then feot is solution to CFL(E) with q 2-m Since < (g())), by Lemma we have X # O. Without any loss of generality, assume ACHL < 0. Below we discuss three cases.
Case 1. UFL UFL, 0: the UFL classifier ERM.
In this case, 100 l We have UUL (Ir, 0) for vT(x) 3. and JCFL for v(()) <
(1- X CFL /(1 22) By Lemma UUL
is not a solution to CFL(E)
Case 2. XUFLa + 0 or AUFLa * 0, and Aorlo UFL, 0: the UFL classifier is not ERM, but one of A
the local classifier is ERM.
Without any loss of generality, let Ag = 0, AULL < 0. Then f60 0) = for v]()) > $.. while
1 (x, 0) 0 for n7x)) < (1 A (1 91) /22 Thus we get
UFLO
Sum (x, 0) for 2
< (2)) < (1 UFL (1-)))22)
By Lemma 6 UUL is not solution CFL(e)
Case 3. UFLa XUFla * The local classifiers are not ERM.
AURo T-go Case 2, we have
X UR
When
+ T-q without loss of generality, let A
Then by the same argument in
T-go
T-
X
1
1
(z. 0) = for
I I-go go
< T
<
I-91
2
2
23

---

Sec. A.3.I] we present formal version of Thm. 3and show that compared UFL, FFL via FEDAVG has strictly higher fairness. In Sec. A.3.2 we derive the solution to FFL via FEDAVG(E) and show analyze the limitation of FFL via FEDAVG and Under review as a conference paper at ICLR 2022
By Lemma 6
UUI..
is not solution to CFL(E)
A
When
+
similarly, JUFL is not a solution to (F)(e)
90
91
When
and
since
UFLo
UFL1 51
* 0, we have
T-00
T-oi
90
1
1-91 91
Aco
AC1
URL.
Aco
LFFT.
ACT
which leads
and thus Qo = q1 This contradicts with the assumption that go * q1
Auo
A=
Combining all three cases yields desired conclusion.
A.3 FFL VIA FEDAVG ANALYSIS
In this section, we analyze FFL via FEDAVG for the case of two clients. For purpose of illustration, with I = 2, we denote ,FFL FedAvg = fe FFLL FodAvg to be the solution to FFL via FEDAVG(e) In fEo.51
equívalent FFL via FEDAVG. In Sec. A.3.3
present a formal version of Lemma
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 (0,1). For all E E [0, 1], there exists 6 [0, 1] such that DP Disp(J (S FedAug) e. Thus under the condition in
Lemma we have
min co.c1E(0,1]
DP Disp(Jeart)
PUFL
DP Disp( E
min
FFLL via PedAvs) =0 0.
Proof. For any E E [0, 1], let Eg = =1 =. Then the global DP disparity becomes
FFI. via FedAvg) DP Disp(J
= |x o 0) - Exja=11(xx 1)]
= 11 11fe f(x, 0) ap!
+ / [(x, ())(()))())))
ff f(z, 1) dP(()
/ f(x, 1) ()dd(())
/
IMD (FLL FedAve)
1/2 MD, (FFF FodAve) /21
s DP Dispo (s FFF via FodAve)
1/2 2 + DP Disp, (SEEL via FedAvg) 3/2
< (Eo + 61)/2
A.3.2 THE BEST CLASSIFIER OF FFL VIA FEDAVG
For FFL via FEDAVG, 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 faimess constraint obtain the classifier trained by FFL via FEDAVG. The following lemma provides the solution to FFL via FEDAVG(E) when is finite.
Lemma 16. For X. the solution to FFL via FEDAVG(E)) is given by
f(x, a) =
s,(z, a app (x) > O],
EE[T]
where () 21)(x) - 1X,
|==0]
TX
[a=1] for certain Xo. A-11
I-4
24

---

Under review as a conference paper at ICLR 2022
Proof. This proof is based on Menon & Williamson 2018). The key idea of this proof is to the Lagrangian approach. Before we applying the Lagrangian approach, we will show that FFL via FEDAVG(E) is expressible
linear program, and thus the strong duality holds.
Since X' is finite, f a vector of finite dimension. Based on the proof of Lemma the error rate can be written
P(y x))
E
f(x a) 2n(x)))((x== a,a = a) P 1),
zEX'aEd
and the fairness constraints be written
P( = 1 = 0,1= P0 Pf==1|a==,i--
P(x I a==0
P(x= x aa 1==0=a=11o 1a=1,i=
Σ TEX
f(x, 0)
f(z, 1)
P(a=0)
1)a==1)
= O] - Ia = 1])P(x= x a= a, i/ a), for E X2 A, i [7]. Note that tı, top U1
for i E Let -
a), Ply = 1), and ui a) = (Ia =
vectors the same dimension of f. For ease of notation, we allow I to be applied to pairs of vectors in element wise manner. Therefore, the optimization is
min T f /+00 u f
s.t. u S
0sfsl.
which is a linear objective with linear constraint. Therefore, the strong duality holds for FFL via FEDAVG(E) Next, apply Lagrangian approach to solve the FFL via FEDAVG(E))
Recall that
P( + = E. xxpp( f(x, - 2n(xx) P(y = 1),
and
P 0,i PP a 1, i)
f(x,0) [a 0]
f(xx aa = 1]
=E, EE, EE xxp((1)
By strong duality, for .o...., N22 2 0, the corresponding Lagrangian version of FFL via FE DAvG(E)
min P(y xv)
Σ
N/21 (f ) F
eal
(12)
FEF
kE(T]
+ X21+1 PPý = 0,
P = [0]
Let A₁ = N/i 11 i E [4]. then we get
12
min E. E
(1x,a)(1-22(()) 2n(x))
Σ (Nif(x,
(>) [a=
xx 1-
[a la=11) 111)
xp)
JEF
SEMM
min Σ ((, JeF
(x (x))2 (z))dz.
x aEA
SE[T]
where is defined in Lemma 16
Thus the above equation reaches its minimum at
f(z,a) = Σ
(z d) (z) 0].
25

---

Under review as a conference paper at ICLR 2022
Remark 8. Based on the proof of Lemma
FFL via FEDAVG( is equivalent solving
1-1 = 0,1= P(y || 1,i= i)). Σ (T(
m x
JEF
Under certain conditions (assumptions 1 4 in
Li et al. 2020b) we have solving FFL via
FEDAVG(E) is equivalent to minimizing
P( y = AP((( = aati0=llaaai 0 P(P 1,i=))
locally and applying FEDAVG (Theorem in et al. (020b)).
A.3.3 COMPARISON OF FFL VIA FEDAVG AND CFL
Lemma 17 (Formal version of Lemma 4 under two clients cases). When a | ~~~ Bern(0),
i= 1 ~ Bern(1) and DP DiFL( 0, we have
min DP Disp( (FFL Fedlvg c0:51
DP Disp > min DP Disp( (CFL) O.
Bern(1), the constraints in FFL via FRDAVG(e) vanish. When 1, the constraint in CHL(() always holds and thus also vanishes. Thus in such
Proof. Since a = ~ Bern(0),
scenario the solution to FFL via FEDAVG(E) becomes fCFL, Then from the assumption we have
DP Disp(fee.t via FodAvg) DP Disp (1 > DP Disp (iss((( 0.
A.4 EXTENSION TO MULTI-CLIENT CASES
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 Thm. and Lemma 17
The following lemma shows the fundamental limitation of UFL:
Lemma 18 (Formal version of Lemma I. Let q (0, 1). Consider a partition which divides clients into two subsets. Denote the mixture distribution of each subset as a= a. a.jaaj= = j-~ P(i) where j the index of the subset, and p(ù) is distribution, for a.j 0, 1. Similar to two clients case, define Øj (A) = -[n-'(3 =2 to))
dP(()) Consider the case that d'p()) - S (1+ ),++
for all E [T] and q E (0, 1). Denote the proportion of the two subset as Jo and J1, where Jo. J1 > 0 and Jo + J1 = Let min (0)), lā (0)]}- Define & i0, cl x [0,c] - [-1, 1] as
T(E,,E) 1 (
Jn. (ā (s)g)((((0))Eo))
+ J sign To (0)) + J² ()
there exists partition such that ğo (0)g1 (0) and (56 E ()) ôn (0)) > f all &, &1 [0, c), then for all ε., E 1], DP Disp(fe 2 8 minfl & Eb, [0,c]] 0.
Proof. By Lemma 8 conclude the achievable faimess range of UFL is strictly smaller than that of CFL. Therefore, pooling the datasets in one subset and perform fair learning can clearly achieve 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 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 JUFL. Note that the mean
difference can be expressed as
MDRF 10 + JoJ1 (UULL)) JoJ1nn (A (ULLO + 17
(13)
In the following proof, will show, the mean difference cannot reach O.
26

---

Under review as a conference paper at ICLR 2022
Without any loss of generality, assume [o0 (0) < [0)( and θ1(0) > 0. By (o (0) < 0 and
(En, & (ū)(0) + ộ1 (0)) 0 for all εo, E [), we have 0o(0) and (EE, 61) for all Eo, E [ Without any loss of generality, assume Jo S J1.
First, will prove that UFL achieves its lowest mean difference when 60, [0, c0. In what follows, we consider five different cases to derive the desired result.
Case 1. én (0)(
(0)]: ERM is fair on both clients.
A UFL 0. Recall ās(-) is monotone increasing function, combine T1 (0) and Lemma 7 and thus ( (0)) < (0)
By 16, we have XUFLa
0. Applying the above conclusion yields
1
1
113 (0) + J( > J, (J) J (0) + JoJi ( (0)) - J v6 (O), 8.
Case 2. Eo < (0)(0), > (g) (0)): ERM is unfair on client 0, but fair on client 1.
Applying
results in XLHL 0. By the fact that gi(-) is strictly monotone increasing function,
we have UF 9o (-6)) > 9o (e) = 0. Applying the above conclusion yields
13
-e + J7 (0) + (0) (0) + InJiă (Xttto)
> Jogo + J191 > - (0) 0) 2
J1
In the first equality we used iUFLO 0, g1 (AE > 91 (0), go (0) < -E0-
Case 3. én S (0)()) S 17: (0)]: ERM is unfair on both client O and client
Applying we have UFFLa ( (- UFL (.,). Then we have
13 = - -3550 + J& + Jo ( (E1)) JoJ (o (-5o))
2 - Je + J7Eo + Jáo (Eu) + JoJ1 (0 (-Eo)) = ( Eu) 2 8.
Case 4. Eu (0,(0)), (0) ERM is fair on client 0 and very unfair client 1.
By 6
have XUFLo
0, dUn ( 9T (0). Then obtain
13
(0) JoJ (1URL)) JoJi J7
> (0) + JoJião(0
(0)) + J.g. (0))
- ((0
= Case 5. En (5)) < 5, < 17. (0)): ERM fair on client and unfair on client
Applying ( implies UUFL 01 (81) 91 (0). Therefore,
(0) + Jn (5)) f& + (0) > (1) + J1 11 (0) + Jo (0)) + J&ā > (1), 0) 2
PUF Combining all the cases above, we conclude that when 91 (0) > 0, DP Disp min((1((E,,é)) Eo [0.c] > for all Eo. 10.
2 8 =
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 E DP disparity:
Theorem 19 (Generalized version of Thm. 15). Let qi q E (0, 1) for all [4]. For all s [0. let E; S a for all i E [4] then DP Disp( FF FedAvg < E. Thus under the condition in Lemma 18 we have
min DP Disp(JLFL)> min DP Disp(SE =E(0,1]
FFL via FedAvg = 0.
=E(0,1
27

---

Under review as a conference paper at ICLR 2022
Proof.
When E S the global DP disparity becomes
DP Disp(Se FT via FedAvg) = | (x, 0) 1 1)1
/ f(z, dPP
f(z 0) dP!
Σ ==
==
I-1
1-1
MD (JE via FedAwg)/1
5
DP (fe
(.F... FedAve) 1/1
Σ E5/I=E.
=
The following theorem shows the limitation of FFL via FEDAVG: Lemma 20 (Generalized version of Lemma 17p. Let all E [4]. When DP Disp( (f2%) > 0, we have
i i= i in Bern(0) or in Bern(1) (er
min DP Disp(Je fe. via RedAvg DP Disp ((P)) eE|0,1]
min DP Disp(f 0.
Proof. Since a ii= Bern(0) or a i= Bern(1), the constraints in (FFL via FEDAVG(E) vanish. When 1. the constraint in (F)(E) always holds and thus also vanishes. Thus in such scenario the solution to (FFL. via FEDAVG
becomes /CFL, Then from the assumption we have
DP Disp(fe ( via FedAvg)
DP Disp(
DP Disp(fo 0.
B APPENDIX FEDEB ANALYSIS AND ALGORITHM DESCRIPTION
In this section, provide bi-level optimization formulation for FEDFB for four faimess 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 lcarning.
To explain how optimize the weights of different groups, we introduce some necessary notations first. Denote the kth sample as (Xk. Yk. ag,ig), 1x), & = 1...., n. Here X E X is the input feature, Y& E {0, 1} is the label, ag E A [A] the sensitive attribute and in [Z] is the index of the client that the sample belongs to. A represents the total amount of sensitive attribute and / represents the total amount of clients. Denote the number of samples in group a as 14..0 : 1 a aHl. Let yyya [[k: y& a. ag a}l be the number of samples in group of label y, and
ny.a := [k yk = a, = ig = ' be the number of samples belong to client i of label and sensitive attribute a. Define the loss function E(y,8). Let Ly ) be the empirical risk
aggregated over samples subject to = y, a = a, iee,, I=g.a(w)) (w) = 2k:y= E(yk, 8k)/ng.a.
where Ry.a = Kk Yk = y, at|. We then define the local version of Ly.o as L (w)) == Eky E(yk, ((),)E))// /n
B. FEDFB w.n/ DEMOGRAPHIC PARITY
To extend Roh al. 202T) multiple groups cases, we propose different bi-level optimization problem w.r./ demographic parity. This development can also be applied to the centralized setting. The following proposition gives necessary sufficient condition for demographic parity, which can be directly obtained from Roh et al. (2021). For completeness,
also include the proof here.
Proposition 21 (Necessary sufficient condition for demographic parity, Proposition 2 in Roh et al. (2021)). Consider 0-1 loss: f(y, 8) [[y + v]. Let I (w)
My.a T (wr), then
n.aa
-1, + Li, + L/ (w)) - Lí,a (w) + 70.0
140.a
(14)
n. n1.0
for all E [A] is necessary sufficient condition for demographic parity.
28

---

Under review as a conference paper at ICLR 2022
Proof. We denote by P the empirieal probability. The demographic parity is satisfied when P(ý
1 = 0) = P(- = a = a) holds for all a E [A]. Thus,
IP 1,
0) + Py 1,
a a
=P = 1, 0 a) + PPP = 1, = a=
For 0-1 loss, we have E(11 - y1. = - ((y, thus
E
(1 8 (yn,
Σ
Syn:
Tx,0 ke 00, =0
T0.,0 koy =ly
Σ
(1 l (yk,
Σ
Tx.00 k.y, =0,
Th,o kiya =1,
By replacing Ekyy 9t) = ny (yyat.,a(())
we have
70.00 (1 Lo,o(w)) + 11.. L (ww)
n,,0
T0.00
70.a (1 (u,)(w)) + n1.a
L (w).
11,a
Remark 10. Proposition provides us way to measure demographic disparity using group-specite losses. However, since 0-7 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: À = (Ao,... ... AA-1), the weights attached samples. We formalize the reweighting task into the following bi-level optimization problem, where the outer objective function captures the demographic parity criterion:
min = min ΛEλ
[l,o()x)))))))))))))))))))) + (wx) + I
- [1xx((x)) +
1o,00
70,aa
AEA
n,,0
nh.a
d=1
A-1
wx == arg min L(w, A) = arg min w
Pa (w)) + (2 Toa
d (a)L)a(w))
(15)
a=0
Snnerr
where A [0, 01
-
We make the following assumption to our loss function to have the decreasing direction Lemma Assumption 1. (+) is twice differentiable for all y E (0, 1}, a E [A], and
Na V ( (w) + (2 nh.a
n >a) Va) (w))
0 for all X A.
(16)
If L (wx) is convex for all y 10,1),a [A], the condition (16) holds unless for all
L Lga( (), L4 (-)(()) share their stationary points, which is very unlikely (see Remark in Roh al. (2021).
The following lemma provides decreasing direction of the outer objective function Fap- which inspired us to design the update rule of A.
Lemma 22 (Decreasing direction of Fap). If Assumption i holds, then the direction μ(A)
(Ao,)),... .......,A-1- ( where
A-1
(o(A) = Σ aml
(Loo(w)) + ()x) + (oo((w)) (1)() +
710,0
11.a
n+.0
(17)
(A) = -T%,o(wx) + (())( + 1ioo(uxx) - I/ (1x) +
110.0
710.a
R4.00
7+.a
29

---

Under review as a conference paper at ICLR 2022
for all {l,...,AA-
A- 1}, we have p(2) Fapp(A) S O, and the equality holds if onty if p()) 0.
Proof. We compute the derivative as
(P)
A-1
Σ
( (wo) + (()x + Lo (2x,(2xx)
70.0
n0,a
=
na,0
nh,a (18)
a=1
(- (-VLoo( + VL),o(wx)) VL VLi,a(
Oera
0d,
Note that ux is the minimizer
15 inners have
Σ
Xa V (wx) + (2 ne,a
>a) V 0.
n
We take the Xy derivative to the above equation and have
(wx)) (
Aa 2 17,0 + (2_ra Xa) (2) (w))
Ows = 0. 07,
a=0
Thus we get
Our
da 2 Ig (wx) +(2 Mzza Xa)) v2) I. (wx))
-1 " (wx))
(w>)]-
a=0
(19)
Then the direction (x( given by (17 combine 18 and 19 to have
(A)) (A)
1-1
2 (wx) + (w)) + Lo,a
L',a(2s, +
11,,0
1o.0
n..0
n,,0
V L (wx) + Vl(,)(w>)) + (oga - -VLi,o (11))
da 22 (wx)) (2 Xa) V2) [1,
n
Σ [( (wx) + L),o((x) [/,((w>)) (2x(
100.0
no.a
n2,0
n,,a
(.,o(w))) + vl),o(u>)) + VLga(w)) - VLi,o(u))) 50
and the equality holds only when μ²A) O. where we have used Assumption i
Inspired by Lemma 22 in each communication round t = 0, 1,..., we design update rule for as:
(1+1) A(
At |((a))]22 Ma (2)),, for [A],
(20)
where 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 louter and introduce how clients collaborate to
update the weight A. Note that the central server can compute L' (w ( by weight-averaging the
(8) local group loss Lyja (x())) sent from clients communication rounds as
I' Ty (1xx)) =
Ny.a (() "ya (w0))))
R4,a
iE(1]
30

---

Under review as a conference paper at ICLR 2022
thereby obtain ju ()) and update (+) by (20).
Next, we focus on the inner objective function 15 inner and introduce how clients collaborate to update the model parameters wA using FEDAVG. Note that
decompose the objective function L(w, A) - -2
into L(w, A) = EiE(n (w, 2), where (w,, A) := Ex=o Do / +
Ae A (6) /n. is the client objective function of client v. 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.rt demographic parity in Algorithm
Algorithm 2: FEDFB w.Y Demographic Parity
Server executes:
input :Learning rate far hes; Initialize Åo as Ru. for all a E [A]] {0):
for each iteration = 1, ... do
Clients perform updates;
wx + SecAgg (w)+) } for all i;
Lyga < SecAgg [r((0) } for all (y, a); 1g.a
I v.a n.c
Pue Lyy.a for all y E (0,1)a E [A];
Po - - 2a=1 (-16,0 + 11,0 + 4u,0 L/,a + no.0
n0.a
Ne f - -6,u + L1,0 + Lb,0 Li.a + na. noa
E [A];
Ay t Aa + TTulla Ma: for all [A];
at
Broadcast wx and to clients;
end output: w
ClientUpdateff w. A):
wi()) +- Gradient descent w.r.f objective function
A-1
== Aa (o "2
Xa >a) r(6)
(w)]:
Send (()) Lo (w), (.) (w) for all [A] server via SecAgg protocol;
Next, we analyze the convergence performance of FEDFB. We need to make the following assump- tions on the objective function [(0) A), i [7]. For simplicity, we drop the À here and use the notations ( (w)) wv) and L(w) instead. We use un
(i) denote the model parameters at f-th iteration in
i-th client. The assumptions below are proposed by work Li et al. (2020b):
Assumption 2 (Strong convexity, Assumption in Li et al.
2022bb) ). ( (w) is p-strongly convex
for E [ i.e., for all and w, w, T,(((v))
7,00
(w)
+
(v
V V (w)
E/2 1|0 w|/
Assumption (Smoothness, Assumption in Li et al.
2020b ). [((( (w) is L-smooth for i E [7].
i.e. for all v and w, L (v) < (w)) + ( (v- w) V (L)))()) (w)
||0 w
Assumption 4 (Bounded variance, Assumption 3 in Li et al. (2020b). Let 5 be sampled from i-th device's 's local data uniformly at random, where t E [T], and T the total num- ber of every client's SGDs. The variance of stochastic gradients in each device is bounded:
V ww)"
(1)
VL I| < for [T]
Assumption 5 (Bounded gradients, Assumption 4 in Li ct al. 2020b)) of stochastic gradients is uniformly bounded, i.c., E V (w)
The expected squared norm co for all i E [[] e [T].
In FEDAVG, first, the central server broadcasts the lastest model to all clients, then, every client performs local updates for number of iterations, last, the central server aggregates the local models to produce the new global model(see Algorithm Description Li et al, (2020b) for more detailed explanation).
31

---

Under review as a conference paper at ICLR 2022
We denote E as the number local iterations performed in client between two communications, and R be the total number of every client's ' iteration. Thus R is the number of communications. E
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 hold. Choose {ar such that littl 0o Oz2 - 0, Ei=1 Or = oo.
on (I.00, A) Nein and
Assumption D on
Suppose we use FEDAVG with R and E satisfying It rounds. We find sufficiently large T such that with high probability, applying update rule (20)
E² - 0 to solve 15 inner between two X update
leads to (T) X I max {1A! - Xal Et= on, ar + 0, where X is the local minimizer on direction {(
Proof. We first derive the update rule in the case of A =. From (20). we have 140
-11
Denote
f(A()) = ( + _2,)(1²²)) ) + (w)))
x2) +
11000
10,1
n..0
R2.1
Then the update rule becomes
v2
1 (e+1) =x
(1)
ax sign sfgnn((())()) (()
2
(21)
V2
((+1) = X1 + a (f ())).
2
Then we apply FEDAVG with R number of total iterations to solve min, L L(w; ( and obtain w (t) Then in the update round from (()) A ((++1), by Thm. in Li et 2020b), we have
A (t))] T(W ((1) 0 E R
B[L(w
(0)
xx(1)) | 0 E (1)
E
u
where wxie
arg (w: ( By Markov's inequality, with probability - 6,
w
E
L(w (t) (t); ((0) L(Wx(0) A (()) O
5R
w/ wx 2 =
E
8R
Then taking the union bound over T updating iterations of X (t), the conclusions above hold with
probability at least 1 - T8 for all A = 1,2,-.. , Therefore, with sufficiently large R R(6) such that g²
оæ - 0, for all (1) in the T iteration, [L (t) (()) L( < w < 1.
By Lemma 22 (A) has a local minimizer X on direction u(A). By update rule we can find large T > to have
T + 0,
P A11 < max [2 - -X - Σ
az aT
1=1
where a E (0, 1).
Remark 11. Note that Thm. assumes FEDFB does not update X in each communication round and there are infinite rounds of aggregations between two À updating round. However, for computation efficiency, we update X at every communication round in practice.
32

---

Under review as a conference paper at ICLR 2022
B.2 FEDFB W.E. EQUAL OPPORTUNITY
Similar to Proposition opportunity:
21
we design the following bi-level optimization problems to capture equal
A-1
min Feo (A) min AEA a=1
(L2)
L),o(2x))
A-1
A-1
ux arg min
Σ
(2))) + +
Σ
no,+ (w. (22) da L1
W
n
n
Here A {(A( {(A1, A
AA-1 Aa for all a 1, A A-13
For equal opportunity, we make the following assumption:
Assumption 6. Ly,a()) ()) is twice differentiable for all y E (0, 1}. a E [A], and
A-
A-1
Aa 22 (w)) +
R1 n
+ Ro. v2 Lo. (wx) >
for all X A.
With the above assumption, the following lemma provides the update rule: Lemma 24. If Asssumptiin h holds, then on the direction
p(A) (L1,1(wx) L1,0(xx), ..... L (wx) L1,0(2x)),
(23)
we have μ(A)- Feo < 0, and the equality holds if only if ((A) O.
Update rule for equal opportunity:
X (++1) = (t) +
|((()))22 (L1a( L))((w)))).
Proof of Lemma 24
We compute the derivative as
OF (A)
A-1
Owx
2
Σ
(wx) (1,(w)))(Vh)a(n)) - V[no(())) O),
(24)
07j
a=1
Note that wx the minimizer
have
1-1
Aa ( + B1. Aa VL,,0wx))+ + no v (wo) = 0.
a=1
We take the Xy derivative to the above equation and have
Aa 2 L1 (wx) +
+
71
Σ
\a) 2 L1,((2x)
nu. 22 (wx))
n
a=1
(L1,(WX)) - VL1,(())) + Owx = 0.
Og,
Thus get
Owx
Σ
A-1
Au 2 L1a(wx)) + 11, + Σ
1-1
Xa) V
no. V2 Lo.
(25)
1=1
a=1
(V1 - VL1,(Wus)].
33

---

Under review as a conference paper at ICLR 2022
Then the direction ()(A) given by 23
combine 24 and (5 to have
px(x). V Foo
A-1
(Lx))(xx)= (,.((x))((VL,ll)
A-1
Aa L1 +
PL.
Σ
Xa)
12) + no., V² Lo, (w)))
Σ (L. LL
6=1
where we have used Assumption
c the equality holds only when (()) O.
We present the FEDFB algorithm w.s equal opportunity in Algorithm B
Algorithm 3: FEDFB wen Equal Opportunity
Server executes:
input :Learning rate {atheN;
Initialize A, as Fis for all a E [A]] {0); n for each iteration = 1, 2.. do
Clients perform updates;
Wx + SecAgg (wl+) } for all i; Ly,a SecAgg L 4.
(4) \ for all y {0, 10,1),a E [A]) (0):
Me +- L1.0 L1.0, E [A]] {0};
Aa + Aa + TTtla Ma: for all [A]] [A]]
Broadcast wx and À to clients; end wutput:wy
ClientUpdate(i, w. A):
(i) Gradient descent w.E. objective function
AA-1 == (1 (w) ( ΣA-1 (0) + no., 1 (w))
(i)
n Send (f) L0.0 (w), ( (w) for all [A] server via SecAgg protocol;
B.3 FEDFB W.F/ EQUALIZED ODDS
For equalized odd, we design the following bi-level optimization problem:
min Food = min AEλ
(L), -I,o(w>))² + (Lo,a(wx) - Lo.o(w>>)
A-1
= arg min
(A La.ataaa))))) + )1aaaa,,
10.*
To.o()) +
M1.
Σ
X1 Tr
(26)
n
n
Here
A-1
A-1
A (1o,, A0,4-1, (oo.l,..,,,,,-11. . (I,A-1)
no.
Σ
A1
n1
n
n
Ao A1 2 0,
for all 1, 1,..., A 1}.
34

---

Under review as a conference paper at ICLR 2022
For equalized odds, make the following assumption:
Assumption 7. Lyja()) is twice differentiable for all E (0, a E [A], and
A-1
(A1,0 (wx)) + N0,a V2 (w,a(wr))+ + RO.+
Σ
10 V2 Lo,o(w>)
n
a=1
a=1
A-1
+ N1
Σ a=1
00
for all X E A.
With the above assumption, the following lemma provides the update rule: Lemma 25. If Assumption 7 holds, then on the direction
μ(A) (Nu 1 "...a with
My (A) L,y,awxx Lu,)) y E 10, [A],
(27)
we have (( Fe (A) O, and the equality holds if only if μ(A = 0.
Update rule for equalized odd:
(t+1)
(()
||((1))122 (Ly - Ly,o((xx()) for E [0,1), [A].
Oft
y.a
Proof of Lemma 25
We compute the derivative as
0Feod (A)
A-1
Σ
(L1,a(W>>) - LLo(wx))(VLLL ((1,0(w>))
ONys
(28)
Ewo
+ (Lo,((xx) Lono(w)))VLa,auuu)) [[o,0(2>))]]
Odys
Note that wx the minimizer (26 we have
(aaa V.,a((w>) + AI,a (lI,(a))))
A-1
A-1
no
No Vo,,((W)) + T1,
Σ
) (L,,((>)) 0.
We take the Ao.j derivative to the above equation and have
Vhy (wx) (Ly.0(uux)
(No.a 2 2 (w,) + \ı,a V2 (
N0.*
A-1
No,a ) [=T,o(( +
11.
4-1
Owo 0. Ody.i
a=1
Thus we get
Owx
A-1
Σ
(No,a 2 Lo.o >1 22 (2L1)((ux)
TAys
a=1
A-1
A-1
n0.+
No ( Lo,o(wx) +
11
\1,a) 2 L)o(wx))
n
(Vy ([yy(
(29)
35

---

Under review as a conference paper at ICLR 2022
Then the direction je (A) given by (27 combine 28 and 29 to have
(a))-
(A)
A-1
2
Σ (W)), LV.o(x)) (w>) - ((1,0(22))
a=1
+ (wu,a(2>>) L0,u (V.(( (wx)) - [Lo.0(2>))]]
A-1
(A Vo + AI ((L1a(xx))
A-1
A-1
Rd,+
V + n1
Σ
)1a) 22 L1 L1,0(
π
n
A
(L1,a(Wxs) (1,0()))( - (L1,a(wx))
6=1
+ (wx, - To,o(wx)) (VLo,, - (lo,a( }]]
0
where we have used Assumption 7 and the equality holds only when ((A)
The full procedure is described in Algorithm
Algorithm 4: FEDFB w.st Equalized Odds
Server executes:
input :Learning rate {ar heN; Initialize Ay.a as Ryo for all E [0,1), E [A]\ (0);
for each iteration = 1,2... do
Clients perform updates;
wx + SecAgg [wo for all i;
Ly.a + SecAgg [gg f for all y E 10,1 E [A]] (0):
My.a 5 Ly.a - Ly.0 for all y E {0, 11,,,,, E [A]][O):
Xy.a f- Xy.a + Inlla My,a; for all a [A]) (0);
Broadcast wA and to clients; end output : ClientUpdate((,
w. w.,)) A):
(()) Gradient descent w.r.f objective function ΣA-1 (2 (w) )1.a (w) +
no.. -AA- du,a) Lo.0 (w) + ( Σ 11 (1)
(6)
Send (t) (()) (w), (2) (w) for all [A] to server via SecAgg protocol;
B.4 FEDFB W.F/ CLIENT PARITY
For client parity, we slightly abuse the notation and define the loss over client as (w)) = Σi f(yx, yr) (n, with (1) = [(k is = i)). Note that the T, 7,09 here is different from the one in Sec. B.T We design the following bi-level optimization problem:
I-1
min Pop(A) = min XEA
( (wx) - - (w>))²
AEA
1=1
Wx arg min
(1) 1 + (1 Σ
(30)
w
1=1
1=1
36

---

Under review as a conference paper at ICLR 2022
Here
1-1
A ((a)) "..,,, - 1. Σ x 1
For client parity, we make the following assumption:
Assumption 8. L (() (-) is twice differentiable for all i 1....... 1, and
I-1
10 w + (w))
With the above assumption, the following lemma provides the update rule: Lemma 26. If Sitmmpptionnholl then on the direction
p²)) = (I. I, (wx).... I II (wxx) [,0x
(31)
we have p()). FF & 0, and the equality holds if and only if (a() = O.
Then update ( (A
(11-1200) follows:
Update rule for client parity:
(()(H))) =1
on [A())) (I. (wxx) I (wx()) for =1,1,.... 1.....,
Proof of Lemma 26
We compute the derivative as
(Ap
Owx
2
(7 (wx) ( (Ix) (ux)))
(32)
OAGI
Note that wx is the minimizer
30 have
LO (x)) +1
(0 v =0
take the ( derivative to the above equation and have
I-1
Ows (
1-1
10 10 (w>) Owx = 0.
(w)) +
Σ
v + + Σ
ad,
0g,
im
iml
Thus we get
Owx OXG)
1-1 (1)
wx + +11-111
Σ 1 10. (wx)
(v)) (w,))-ZZ)))00 (wx)). (33)
Then on the direction given by (1). we combine
and to have
m(A)
P (A)
(2xx) 1 (w>) (V) Vz (wxa))
1-1
(1) (wxx + +
Σ (
(0) (wx)
((x)))))) - (wx)) S
where we have used Assumption 8 and the equality holds only when (e()) = 0.
The Algorithm 5 gives the full description.
37

---

Under review as a conference paper at ICLR 2022
Algorithm 5: FEDFB w.r/ Client Parity Server executes:
input :learrning rate {ar Hes; Initialize ( = for all i [4]] (0);
for each iteration t = 2.... do
Clients perform updates;
ux +- SecAgg (w)
} for all i;
((() ((t) ( i [4M;
A A0o + at
T v for all i [4] (0):
Broadcast wx and to clients;
end output: =
ClientUpdate((. w. A):
(+()) +- Gradient descent w.r. objective function
+ (0 + j 0] Ef=
Send w0()) server via SecAgg protocol; Send L (w) to server;
C APPENDIX EXPERIMENTS
We continue from Sec. and provide more details on experimental settings, and other supplementary experiment results.
C.I EXPERIMENT SETTING
The reported statistics are computed the test set, and 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 training set and a testing set at 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.013. 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 a which achieves the highest fairesss. 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.
C.2 SYNTHETIC DATASET GENERATION
We generate synthetic dataset of 5,000 examples with two non-sensitive attributes (x1, x2), a binary
sensitive a, and a binary label y. A tuple (x,, X2,y) y) is randomly generated based on the two Gaussian
distributions: (X1, X2) y
([[2;; 2; -2), [10, 1; 1, 3)) and (x1, y
([[2 2). [5, 1)).
where Bern(0.6). For the sensitive attribute
we generate biased data using an unfair scenario = 0) + Px ((xx
y = =1)], where Px,,gg is the pdf of (x1,x2). X2). We split the data into three clients in non-iid way. We randomly assign 50%, 30%, 20% of the samples from group 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, 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%.
Px,,z (x1, x2) y = 1)/(xx, .x, (xxx x))
=
draw samples from each
C.3 SUPPLEMENTARY EXPERIMENT RESULTS
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 much wider than that UFL, though the accuracy of FEDAVG not guaranteed when the data heterogeneity increases.
38

---

Under review as a conference paper at ICLR 2022
higher data heterogeneity
(b)
(d)
Accuracy
0.80
CPL
0.75
FEL via PsLAvE
CPL
0.0
0.5
0.0
0.5
0.0
0.5
0.0
0.5
DP Disparity
Figure 8: Accuracy-Fairee Fairness tradeoff curves of CFL, FFL via FEDAVG, and UFL. for three clients cases. The data heterogeneity increasing from left right. The green dotted vertical line describes the lower bound unfairness FFL via FEDAVG can achieve, and and the orange dotted vertical line describes lower bound of unfairness UFL can achieve. Here the distribution setting is x a = 0, = 0 ~ (3,, 1),x a 1,i 1, = (),,11) a = 0, = (11, 1),x
0 ~ (5, x),x
0, 1 ~ (11, x),x Bern(g.) for i 1, 2. The data heterogeneity here is captured by lga gol. (a) go qI qa 0.5. (b) go 0.4, qı 0.5, q2 0.6. (c): go 0.3, Q1 0.5, q2 0.7. (d):
1,1 2 (2, 1),
4o = 0.2, 41 = 0.5, 42
0.8.
Table 4: Comparison accuracy and fairness in the synthetic, Adult, COMPAS, and Bank datasets w.r.t demographic parity (DP) on logistic regression. The implementation of UFL, FFL via FEDAVG, and CFL are all based on FB.
SYNTHBTE DISP(()
ADULI
COMPAS
BANK.
METHOD
ACc.(f)
ACC.(T)
DP DisP(()
ACC.(t)
DP DISR(
ACC.(1)
DiSP((]
PIDAYG
8884 001
419=0006
837
.1442.00 015
.6582 006
1494
.00-t 000
026: 001
UFL
7112: 198
266_.175
8191006
052:1 031
60622 018
0891 058
$88.1. 005
008:1 007
FEL VIA FEDANO
.789-4.138
1922-192
828-4.00
098-4.008
.500-.000
.300..002 002
$92-4.000
.013--0000
.085_000
.0111:002
PAIK
62244.011
.028=.008
.768 000
.033. 000
.568- 0188
.034 023
.83-4.000
.0001.000
.6622
1077 020
8102 009
0544
.5872 003
033 002
887d:
.0002.000
We also compare FEDAVG, UFL, FFL via FEDAVG, FEDFB, AGNOSTICFAIR and CFL logistic regression. Table shows that our method outperforms UFL and FFL via FEDAVG, while achieving similar performance AGNOsTICFAIR and CFL but ensuring higher privacy.
C.4 EVALUATION OF DIFFERENTIALLY PRIVATE FEDEB
Since FEDFB exchanges more information than FFL via FEDAVG, we employ differential privacy to decrease information leakage. We apply the Laplace mechanism make the information exchanged in each communication round e-differentially private. We report the test accuracy and DP disparity of FFL via FEDAVG and FEDFB with different differential privacy levels in Table Interestingly, we observe that higher level of differential privacy even helps to improve faimeess (see FFL via FEDAVG column), though the accuracy is decreased. This phenomenon is to expected since larger noise helps to protect sensitive information, thereby improving fairness and lower accuracy. Still, Table 5 iimplies that FEDFB still outperforms FFL via FEDAVG with restrictions on the information exchange.
C.5 EMPIRICAL RELATIONSHIP BETWEEN ACCURACY, FAIRNESS, AND THE NUMBER OF CLIENTS
We investigate the empirical relationship between accuracy, faimess, and the number of clients. We generate three synthetic datasets 3,333, 5,000, and 6,667 samples, and split them into two, three, and four clients, respectively. Table shows that our method outperforms under the three cases.
39

---

Under review as a conference paper at ICLR 2022
Table 5:
Performance comparison under e-differential private information exchange in each communication round on synthetic dataset.
FFL VIA FEDAYG
FEDFB
Acc.(t)
DP DIsP.(L)
Acc.(f)
DP DISP.(
0.1
.5831.255
.185:.254
517=.110
0861.192
1
.582+.261
.189-.249
-508+.191
.103+.188
10
.645+.315
.3734.217
.616+.119
.091+.204
Table 6: Comparison of accuracy and fairness in the synthetic datasets with different numbers of clients w.r. demographie parity (DP). The implementation of UFL, FFL via FEDAVG, and CFL are all based on FB.
TWO CLIENTS
THREE CLIENTS
FOUR CLIENTS
METHOD
Acc.(f)
DP (L)P.
Acc.(t)
DP DISP.())
Acc.(t)
DP DISP.
FEDAVG
8799..004
.300..013
883+.003
4024.018
.899+.003
.382+.005
UFL
77802.000
.1611.157
.79
22561.193
.7201.192
.2461.180
FEL VIA PEDAVO
.8661.002
4291.0017
.7461.307
.4781.079
.6081.367
.9111.102
FEDEB
.679=007
.047:.012
.613+.007
.011+.009
.705+.004
.005+.003
CFL
.28
.0631.035
.6931.030
.0511.020
.6701.035
.064.1.020
C.6 COMPARISON WITH FAIRFED
Table 7: Comparison accuracy and fairness the synthetic and Adult dataset w.r. demographic parity (DP) on logistic regression.
SYNTHETIC
ADULT
Acc.(t)
DISP(()
Acc.(t)
DISP(())
FAIRFID (OLaS)
.5092: 099
092
.357 003
009
.756
As suggested in Ezzeldin et al. )021), use logistic regression compare approach with FAIRFED. Since FAIRFED only applicable to single binary sensitive attribute cases, we report the performance of FAIRFED synthetic and Adult datasets in Table We observe that FEDFB outperforms FAIRFED in terms of both accuracy and fairness, while FAIRFED also outperforms FFL. via FEDAVG thanks to the additional client reweighting step.
Table 8: Comparison of accuracy and fairness under the same setting as Ezzeldin et al. 2021 The
statistics of FAIRFED are from Ezzeldin al. 2021).
ADULT HETEROGENBITY LEVEL a
COMPAS
METHOD
HETEROGENEITY LEVEL &
0.1
0.2
0.5
10
5000
0.1
0.2
0.5
10
5000
FAIRFED
.775
.794
.819
.824
.824
.94
.586
.608
.636
.640
Acc.(t)
FEDEB (OURS)
.764
.761
.762
.764
.759
.688
.655
.541
.666
.666
FAIRFED
.021
.037
.061
.065
.065
.048
.040
.072
.108
.115
(SPD|(L)
FEDEB (OURS)
.003
.003
.003
.000
.009
.009
.017
.000
.050
.006
To make fairer comparison, follow the exact same setting as Ezzeldin 2021
re-split Adult
and COMPAS dataset, employ |SPD| = [f = 1
0) Ply
1)] as unfairness metric
and present the results in Table We observe that FEDFB achieves higher fairness than FAIRFED while being robust to data heterogeneity.
C.7 COMPARISON WITH AGNOSTICFAIR
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 FAIRNESSCONSTRAING implementation (Zafar et al,, 2017c). achieves similar performance AGNOSTICFAIR, much lower cost of privacy.
that our FEDEB
40

---

Under review as a conference paper at ICLR 2022
Table 9: Comparison of accuracy and faireess in the synthetic, Adult, COMPAS and Bank datascts w.F demographic parity (DP) multilayer perceptron.
SYNTHETIC DISP(()
ADULT
COMPAS
Acc.(t)
(ISP(()
ACC((T>
DISP.
DISP((L)
FxnEB (Qurs)
613-t
.011:0009
765- 001
.001
5424
.011+.001 .0001.000
883-4.000 8832
.000 .00220000
AGNOSTIC
0322 044
.7672 004
0011
.412 000
41


Reviews:
[{"review_id": "wOzU3fcEla0", "reviewer": "Reviewer_6XNC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n- The topic of fair federated learning is important and useful.\n- This paper first gives a theoretical analysis of existing algorithms for fair federated learning. I enjoy reading this part.\n- The empirical results are complete and confusing.\n\nQuestion:\n- ", "summary_of_the_paper": "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.\n", "summary_of_the_review": "Overall, I recommend the paper. It considers an important problem, fair federated learning, analyzes and compares existing approaches, and proposes a convincing framework. The writing is nice and clear, especially the discussion in Section 3.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "sFFuAfHiZjM", "reviewer": "Reviewer_q1zx", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors proposition appears to be novel: fairness in Federated Learning is currently understudied, despite being a critical aspect for a wider adoption. Authors did a great job at introducing their work and rigorously used a mathematical definition for fairness evaluation (Demographic Parity) which is often lacking in this field.\n- Could you please explain in more details UFL ? \nUFL accounts for the case where clients do not participate to FL. With UFL, every client trains a fair model on its data. However, could you elaborate why considering a random classifier that makes a prediction by randomly selecting a client classifier makes a good baseline? \nFrom a theoretical point of view, I do not see yet the use of UFL nor what the resulting model means. Finally, I do not see what the disparity of UFL is measuring. Giving some context would be very appreciated.\nUnfortunately this work should have prioritized its main content over appendix: this work is not clear enough and always requires going to the appendix for full understanding of what the authors are claiming. Therefore, unless UFL is strongly important to the conclusions of this work, Section 3.1 could have been suppressed to focus on other sections instead.\n\n- Could you please elaborate on the statements of Lemma 4? If we consider a setting where clients return the same model, e.g. clients have identical data, wouldn’t FFL via FedAvg and CFL be identical problems while $q_0 \\neq q_1$?\n\n- Section 4 would really benefit from having the code of FedFB and explanation of the theoretical work in Section B.1. You state that “it [FedFB] provably converges under some mild technical conditions […] See Theorem 23 for more details”. I have the following questions regarding this theorem:\n  - This work seems to rely on Assumption 2-5 for the local loss functions that are standard in Federated Learning and on Assumption 1 “to have a decreasing direction in Lemma 22”. Could you please cite previous work using such an Assumption? Also, you say that with convexity Assumption 1 holds. Could you please prove it or provide references for the proof of that statement?\n  - Theorem 23 relies on the work of Li et al. to bound the impact of FedAvg over one iteration. As a result, the obtained bound only depends on the amount of local work $R$. It is standard to consider that the amount of aggregations $T$ goes to infinity but not for the amount of local work $R$. Am I missing something here? Please elaborate or point me to a reference? Especially considering that most work done on FL optimization (including the one of Li et al., or Wang et al. Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization) shows that the convergence rate and thus the asymptotic convergence bound are proportional to $R$\n  - Can you elaborate on the steps to obtain the bound obtained on $\\lambda_a$? It seems to me that the first term in the maximum is always smaller than the left term of the inequality as $\\alpha_t$ is positive.\n  - Lastly, do you know under which condition we could generalize to A>2?\n\n - The experiments consider 10 communication rounds and 30 local epochs when considering two clients. Also, the values of some hyperparameters are missing. The experiments like the theory are very specific and do not seem to cover realistic FL cases: could you communicate other parameters lr, batch size, $\\epsilon$ ?\n\n - Also, do you have an explanation why CFL is providing worse fairness than FedFB? The authors speak about extending with their work FB. It would be interesting to compare FedFb with FB where every clients data is centralized on the server.\n", "summary_of_the_paper": "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.", "summary_of_the_review": "The authors proposition appears to be novel and with a genuine interest. Authors did a great job at scoping their work and rigorously used a mathematical definition for fairness evaluation.\nHowever, paper structure needs some rework: some keys components, required for the reader to understand the paper, are not in the main content but are in the appendix. Some elements (e.g. UFL) are presented as keys, but their impact on the overall demonstration is not clear and may be moved to appendix. Also, some claims are not fully supported yet.\nFinally, experimental cases, and some proofs, are not straightforward to generalize enough mainly due to binary class problems only and federating only two clients.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "nDDHlK-NFB", "reviewer": "Reviewer_pTFp", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. The 0-1 loss is a non-continuous function. Thus the most assumptions in B.1 are valid. For example, the convexity and twice differential assumptions. In addition, could you elaborate more on how to perform client updates in Algorithm 1? Given the noncontinuity of the 0-1 loss function, do you perform any approximation for the client updates? If there is no approximation, how can it be optimized? In addition, how can the DEMOGRAPHIC PARITY constraint be satisfied in FedFB?\n2. The experiments in the paper are not extensive. The proposed methods have not been compared with some recent papers on this topic. For example, \na. Du W, Xu D, Wu X, Tong H. Fairness-aware Agnostic Federated Learning. InProceedings of the 2021 SIAM International Conference on Data Mining (SDM) 2021 (pp. 181-189). Society for Industrial and Applied Mathematics.\nThe authors use the data setting in the above paper but fail to compare it.\n3. What is the data distribution among the clients in the experiments? It seems the authors use the iid setting across the clients and it is not a practical setting.\n4. The notations in the main body and appendix are not consistent. For example, in the main body  $\\cal A$ is used for the sensitivity attributes set but $[A]$ is used in the appendix. This type of inconsistency makes the paper really hard to follow. If I misunderstand something, please clarify these notations in the paper.\n5. The authors may also discuss the privacy of the proposed method. Is there any increased risk of leaking the information from passing $L$ other than only transmitting model weights $w$.", "summary_of_the_paper": "This paper tried to propose a generic federated learning method to train a fairness model. It compared the ", "summary_of_the_review": "1. The paper is not well-written and hard to follow. Some of the details are missing, which makes me hard to justify the claims.\n2. The complete convergence analysis of the proposed algorithm is missing.\n3. The experiments are not performed extensively. Thus, the claims in the paper are not fully supported.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-hpK0G7dqGI", "reviewer": "Reviewer_V46Y", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper provides a novel analysis on fair training in three different settings. I'm concerned about part of this paper's main theoretically claim that UFL provides weaker guarantee then FFL via FedAvg. It is unclear to me why it is necessary to compute the \\hat{y}|x,a across all clients instead of evaluating Demographic Parity just separately on individual clients. Basically in this scenario local clients are not collaborating and they are just training separate global model. In fact, client 0 and client 1 even use different models to produce \\hat{y}. Why does studying the joint distribution of \\hat{y}|x,a matters here?\n\nIt is also not clear how do the authors optimize the FairBatch objective in the FL setting. I assume the step of solving the optimal global to follow the standard FedAvg algorithm. It is not clear, however, how the group-specific loss is calculated. From Figure 4 it seems that the authors are summing over that loss over all the clients? Could you explain on this part?\n\nThis paper also compares the empirical results of FedFB with other fair FL training methods and demonstrates an advantage of using FedFB over other methods for fairness. However, the results of several baselines in this paper look confusing to me. In the section of client parity, the qffl accuracy is surprisingly low for adult, which does not match up with the results in the original qffl paper. It is also not clear to me why FedFB outperforms CFL in some cases. Could you explain why this happens?\n", "summary_of_the_paper": "This paper compares and analyzes the fairness guarantee(Demographic Parity in particular) provided in three different settings: training local models, training FedAvg with local fair training, training fair global model. This paper provides a method on how to enforce group fairness into federated learning by applying a current fair training method, FairBatch, into FL.", "summary_of_the_review": "This paper focuses on fairness in FL from an interesting angle. However, the current comparison between UFL and FFL via FedAvg doesn't make sense to me. More explanations are also needed for both algorithm and empirical results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors consider the problem of training a fair classifier on decentralized data, and compare three methods: training locally, training the proposed FedAvg algorithm with local fairness, and a global fairness approach.

The reviewers agreed that the setting was interesting and novel, but had concerns about the writing quality, experimental setup, and, most importantly, the organization of the paper, with several reviewers complaining that necessary information was relegated to the appendix.

Overall, this work is not quite ready for publication. With that said, the reviewers agreed that it was interesting and highly promising (it just needs refinement). Please seriously consider the reviewers' recommendations, which on the whole were very constructive and, if followed, should lead to a significant improvement in your manuscript.
Decision: Reject