Demystifying Local & Global Fairness Trade-offs in Federated Learning Using Partial Information Decomposition
Authors: Faisal Hamman
Sanghamitra Dutta
Venue: ICLR 2024 poster (2024)
Keywords: Fairness
Federated Learning
Machine Learning
Information Theory
Primary area: societal considerations including fairness, safety, privacy
TL;DR: This work presents an information-theoretic perspective to group fairness trade-offs in federated learning (FL)

Abstract: This work presents an information-theoretic perspective to group fairness trade-offs in federated learning (FL) with respect to sensitive attributes, such as gender, race, etc. Existing works often focus on either $\textit{global fairness}$ (overall disparity of the model across all clients) or $\textit{local fairness}$ (disparity of the model at each client), without always considering their trade-offs. There is a lack of understanding regarding the interplay between global and local fairness in FL, particularly under data heterogeneity, and if and when one implies the other. To address this gap, we leverage a body of work in information theory called partial information decomposition (PID), which first identifies three sources of unfairness in FL, namely, $\textit{Unique Disparity}$, $\textit{Redundant  Disparity}$, and $\textit{Masked Disparity}$. We demonstrate how these three disparities contribute to global and local fairness using canonical examples. This decomposition helps us derive fundamental limits on the trade-off between global and local fairness, highlighting where they agree or disagree.  We introduce the $\textit{Accuracy and Global-Local Fairness Optimality Problem}$ (AGLFOP), a convex optimization that defines the theoretical limits of accuracy and fairness trade-offs, identifying the best possible performance any FL strategy can attain given a dataset and client distribution. We also present experimental results on synthetic datasets and the ADULT dataset to support our theoretical findings.

Published as a conference paper at ICLR 2024
DEMYSTIFYING LOCAL & GLOBAL FAIRNESS TRADE-OFFS IN FEDERATED LEARNING USING PARTIAL INFORMATION DECOMPOSITION
Faisal Hamman University of Maryland College Park fhamman und. eduu
Sanghamitra Dutta University of Maryland College Park sanghamde umd. edu
ABSTRACT
This work presents an information-ttheortiii perspective to group fairness trade-off's in federated learning (FL) with respect to sensitive attributes, such as gender, race, etc. Existing works often focus on either global fairness (overall disparity of the model across all clients) or local fairness (disparity of the model at each client), without always considering their trade-offs. There is a lack of understanding re- garding the interplay between global and local fairness in FL., particularly under data heterogeneity, and if and when one implics the other. To address this gap, we leverage body of work in information theory called partial information de- composition (PID), which first identifies three sources of unfairness in FL., namely, Unique Disparity, Redundant Disparity, and Masked Disparity. We demonstrate how these three disparities contribute to global and local fairness using canonical examples. This decomposition helps us derive fundamental limits the trade-off' between global and local fairness, highlighting where they agree or disagree. We introduce the Accuracy and Global-Local Fairness Optimality Problem (AGLFOP), a convex optimization that defines the theoretical limits of accuracy and fairness trade-offs, identifying the best possible performance any FL strategy can attain given a dataset and client distribution. We also present experimental results on synthetic datasets and the ADULT dataset to support our theoretical findings.'
INTRODUCTION
Federated learning (FL) a framework where several parties (clients) collectively train machine learning models while retaining the confidentiality of their local data (Yang, 2020; Kairouz et al., 2021). With the growing use of FL. in various high-stakes applications, such as finance, healthcare, recommendation systems, etc., it is crucial to ensure that these models do not discriminate against any demographic group based on sensitive features such as race, gender, age, nationality, etc. (Smith et al., 2016). While there are several methods to achieve group faimess in the centralized settings (Mehrabi et al., 2021), these methods do not directly apply to a FL setting since each client only has access to their local dataset, and hence, is restricted to only performing local disparity mitigation.
Recent works (Du et al., 2021: Abay et al., 2020; Ezzeldin et al., 2023) focus on finding models that fair when evaluated on the entire dataset across all clients, concept known global fairness. E.g., several banks may decide to engage in FL to train a model that will determine loan qualifications without exchanging data among them. A globally fair model does not discriminate against any protected group when evaluated on the entire dataset across all the banks. On the other hand, local fairness considers the disparity of the model at each client (when evaluated on a client's local dataset). Local faimess is important as the models are ultimately deployed and used locally (Cui et al., 2021).
Global and local fairness can differ, particularly when the local demographics global demographic across the entire dataset (data heterogeneity, e.g., a bank with customers primarily from one race). Prior studies have mainly focused on either global or local fairness, without always considering their interplay. Global and local fairness align when data is i.i.d. across clients (Ezzeldin al., 2023; Cui et al., 2021), but their interplay in other scenarios is not well understood.
client differ from the
Implemmntation is available https: / //g (igitiit www..cco///....... cwm/ 1 sa Hamman / Faa PRI-PID

---

Published as a conference paper at ICLR 2024
This work aims to provide fundamental understanding of group fairness trade-offis in the FL setting. We first formalize the notions of Global and Local Disparity in FL using information theory. Next, we leverage a body of work within information theory called partial information decomposition (PID) to further identify three sources of disparity in FL. that contribute to the Global and Local Disparity, namely; Unique Disparity, Redundant Disparity, and Masked Disparity. This informationnthhoreti decomposition is significant because it helps us derive fundamental limits on the trade-off's between Global and Local Disparity, particularly under data heterogeneity, and provides insights on when they agree and disagree. We introduce the Accuracy and (AGLFOP), a novel convex optimization that rigorously examines the trade-offs between accuracy and both global and local fairesss. This framework establishes the theoretical limits of what any FL technique can achieve terms of accuracy and fairness given a datusel and client distribution. This work provides a more nuanced understanding of the interplay between these two faimess notions that can better inform disparity mitigation techniques and their convergence and effectiveness in practice.
Fairness Optimality Problem
Our main contributions can be summarized as follows:
Partial information decomposition of Global and Local Disparity: We first define Global
Disparity as the mutual information I( Y) where Y is model's prediction and Z is the sensitive attribute (see Definition 2). Then, show that Local Disparity can in fact be represented the conditional mutual information I I(Z; Y| where S denotes the client (see Definition 3). We also demonstrate relationships between these information-thherrtiic quantifications and well- known fairness metries such statistical parity (see Lemma 1). Using an wefformmaion-thhoreee quantification then enables us to further decompose the Global and Local Disparity into three non- negative components: Unique, Redundant, and Masked Disparity. We provide canonical examples to help understand these disparities in the context of FL (see Section 3.1). The significance of our cormmation-thhoreeee decomposition lies in separating the regions of agreement and disagreement of Local and Global Disparity, demystifying their trade-offs.
Fundamental limits on trade-off's between local and global fairness: We show the limitations of achieving global fairness using local disparity mitigation techniques due to Redundant Disparity (see Theorem 1) and the limitations of achieving local faimess even if global fairness is achieved due to Masked Disparity (see Theorem 2). We also identify the necessary and sufficient conditions under which one form of fairness (local global) implies the other (see Theorem 3 and 4), as well as, discuss other conditions that are sufficient but not necessary.
A convex optimization framework for quantifying accuracy-fairness trade-offs: We present the Accuracy and Global-Local Fairness Optimality Problem (AGLFOP) (see Definition 4), a novel convex optimization framework for systematically exploring the trade-offs between accuracy and both global and local fairness metrics. AGLFOP evaluates all potential joint distributions, thereby setting the theoretical boundaries for the best possible performance achievable for a given dataset and client distribution in FL.
Experimental demonstration: We validate our theoretical findings using synthetic and Adult dataset (Dua& & Graff, 2017). We study the trade-offss between accuracy and global-loca faimess by examining the Pareto frontiers of the AGLFOP. We investigate the PID of disparities in the Adult dataset trained within a FL setting with multiple clients under various data heterogeneity scenarios.
Related Works. There are various perspectives to fairness in FL (Shi et al., 2021). One definition is flirnts (Li et al., 2019), which aims to achieve equal performance across all client de- vices (Wang et al., 2023b). In this work, we are instead interested in group fairness, i.e., fairness with respect to demographic groups based on gender, race, etc. Methods for achieving group fairness in a centralized setting (Agarwal et al., 2018; Hardt et al., 2016; Dwork et al., 2012; Kamishima et al., 2011: 1; Pessach & Shmueli, 2022) may not directly apply in FL setting since each client only has access to their local dataset. Existing works on group fairness in FL generally aim to develop models that achieve global fairness, without much consideration for the local fairness at each client (Ezzeldin et al., 2023). For instance, one approach to achieve global fairness in FL poses a constrained optimization problem to find the best model locally, while also ensuring that disparity at client does not exceed threshold and then aggregates those models (Chu et al., 2021; Saariguzz-Gálveed et al., 2021: Zhang et al., 2020). Other techniques involve bi-level optimization that aims to find the optimal global model (minimum loss) under the worst-case faimess violation (Papadaki et al., 2022; Hu et al., 2022: Zeng et al., 2021), or we-weighting mechanisms (Abay et al., 2020; Du al., 2021), both of which often require sharing additional parameters with server.
2

---

Published as a conference paper at ICLR 2024
Cui et al. (2021) argues for local faimess, the model will be deployed at the local client level, and propose constrained multi-objective optimization. While accuracy-faima fairness tradeoffs have been examined in centralized settings (Chen et al., 2018; Dutta et al., 2020a; Kim et al., 2020; Zhao & Gordon, 2022; Liu & Vicente, 2022; Wang et al., 2023a; Kim et al., 2020; Sahato & Yom-Tov, 2020; Menon & Williamson, 2017; Venkatesh al., 2021), such considerations, along with the relationship between local and global fairness, remain largely unexplored in FL. Our work addresses this gap by examining them through the lens of PID.
Information-theoreet measures have been used to quantify group faimess in the centralized setting in Kamishima et al. (2011), Calmon et al. (2017); Ghassami et al. (2018); Dutta et al. (2020b; 2021); Cho et al. (2020); Baharlouei et al. (2019); Grari et al. (2019); Wang et al. (2021); Galhotra et al. (2022); Alghamdi et al. (2022); Kairouz et al. (2019); Dutta & Hamman (2023). PID is also generating interest in other MI. problems (Ehrlich et al., 2022; Tax et al., 2017: Liang et al., 2024; Wollstadt et al., 2023; Mohamadi et al., 2023; Pakman et al., 2021; Venkatesh & Schamberg, 2022). Here, measures
instead of trying minimize information-theoree the fundamental trade-offs between local and global fairness in FL and develop insights on their interplay to better understand what is information theorttiill possible using any technique.
regularizer, our goal is to quantity
PRELIMINARIES
Notations. A client is represented as S E 10. where K the total number of federating clients. A client S=s has dataset D. = [144 yr. (.)+),) where denotes the input features, Y/ E {0. the true label, and 2; E {0,1] the sensitive attribute (assume binary) with 1 indicating the privileged group and 0 indicating the unprivileged group. The term denotes the number of datapoints at client S=s. The collective dataset is given by D = - DD,. When denoting random variable drawn from this dataset, we let X be the input features, Z be the sensitive attribute, and Y be the true label. We also let Y represent the predictions of a model fx( which is parameterized by 0.
Standard FL. aims to minimize the empirical risk: ming L(0) = =ming K Σx= Ot. L.),,()), where (0) J E (E,D)E,, ((fa(z)))) y) is the local objective (or loss) at client s, O, is an importance coefficient (often equal across clients), and U(-,) .) denotes a predefined loss function. To minimize the objective L(0), a decentralized approach is employed. Each client S = s trains on their private dataset D. and provides their trained local model to a centralized server. The server aggregates the parameters of the local models to create a global model fx( (Sah & Singh, 2022). E.g., the FedAvg algorithm (McMahan et al., 2017) is a popular approach that aggregates the parameters of local models by taking their average, which is then used to update the global model. This process is repeated until the global model achieves a satisfactory performance level.
Background on Partial Information Decomposition. PID decomposes the mutual information I(Z; A, B) about a random variable Z contained in the tuple (A, B) into four non negative terms:
I(Z; A, B)- = Un)) + Uni(Z:B]A) + Red(Z:A. B) Syn (A., B)
(I)
denotes the unique information about Z that is present only in A and not in B. E.g.. shopping preferences (A) may provide unique information about gender (Z) that is not present in address (B). Red( Z:A, B) denotes the redundant information about Z that is present in both A and B. E.g., zipcode (A) and county (B) may provide redundant information about race. (r, B) denotes the synergistic information not present in either A B individually, but present jointly in (A, B), e.g., each individual digit of the zipcode may not have information about race but together they provide significant information about race.
Here,
A.Z.A.B)
((Z
Syn (Z: A.B)
II: B)
Uni (Z:AIB)
Numerical Example. Let 7= Zz, Z3) with each Z,~ i.i.d. Bern(12). Let A = (Z,, Z2, Z- ① N), B = (Z,, N), N ~ Bern(4)) is independent of Z. Here, 1(Z; A, B) 3 bits. The unique information about that is contained only in A and not in B is effectively in Zi. and is given by Uni(Z:A(B) = IzZ = bit. The redundant information about Z that is contained in both A and B is effectively in Ze and is given by Red(Z:A, B) = I(Z; Zz) = 1 bit. Lastly, the synergistic information about Z that is not contained in either A or B alone, but is contained in both of them together is effectively in the tuple (Zz 4 N, N).
Red (Z:A.B)
Uni (ZIBIA)
Figure 1: PID of
1(2; A, B).
3

---

Published as a conference paper at ICLR 2024
and is given by Syn(Z:A. @ N, N)) = bit. This accounts for the 3 bits in I(Z: B). Here, we include a popular definition of Un)(Z:A[B) from Bertschinger et al. (2014).
Definition 1 (Unique Information). Let A be the set of all joint distributions (Z, A, B) and Ap be the set of joint distributions with the same marginals on (Z, A) and (Z, B3 as the true distribution, i.e., Ap {QEA: Pr A-o)= Pr( -z A-a) and Pro(Z=
B-b) Pr(Z- B B-b)}-
Then, Uni(Z:A|B) B) = minges, A, Lg(Z; A B), where lo( Z A()) is the conditional mutual informa- tion when (Z, A, B) have joint distribution Q and ( (-) denotes the probability under Q.
Defining any one of the PID terms suffices to obtain the others. Red Z:AA, B) is the sub-volume between [ A) and ((Z; B) (see Fig. 1). Hence, Red( Z B) = I(Z; A) UUniZ:A|B) and Syn A,, B) = T(Z: A, B) (ni(Z:A1 B) - Uni(Z:B| A) Red Z:A, B) (from Equation 1).
3
MAIN RESULTS
We first formalize the notions of Global and Local Disparity in FL using information theory. Definition 2 (Global Disparity). The Global Disparity of model So with respect to Z is defined as I(Z;Y) the mutual information between Z and Y (where y (X)))
This is related to widely-used group fairness notion called statistical parity. Existing works (Agarwal et al., 2018) define the Global Statistical Parity as: Pr(Y = 1| = 1) = Pr(ý 1 = 0). Global Statistical Parity is satisfied when Z is independent of Y. which is equivalent to zero mutual information I Y) O. To further justify our choice of I(: Y) measure of Global Disparity, we provide relationship between the absolute statistical parity gap and mutual information when they are non-zero in Lemma (Proof in Appendix B).
Lemma 1 (Relationship between Global Statistical Parity Gap and I(Z;))). Let Pr(Z=0) a.
The gap Pgtobal = Pr(( = 1|2 = 1) - Pr(r = 1|2 = 0)1 is bounded by v0.5 I(Z.Y)
2a(1-a)
A critical observation that we make in this work is that: local unfairness can be quantified as ([ZY|S) the conditional mutual information between Z and Y conditioned on S. This motivated from Ezzeldin et al. (2023) which defines Local Statistical Parity at a client s as: Pr( S=s) = Pr(Y==12- S=s).
Definition 3 (Local Disparity). The Local Disparity is the conditional mutual information I(Z;
Lemma 2. ((2; if and only if
at all clients
K- The proof (see Appendix B) uses the fact that - (1== s) where T(Z; T(Z s) is the Local Disparity at client 8, and Pr(S=s) = n,/n. the proportion of data points at client s. Similar to Lemma 1, we can also get a relationship between SP, and I(Z; Y = s) when they are non-zero (see Corollary 1 in Appendix B). We can also define other faimesss metrics similarly. For instance, Global Equalized Odds can be formulated in terms of the conditional mutual information, denoted as 1(2; Y and Local Equalized Odds as 1(2; Ý S).
3.1 PARTIAL INFORMATION DECOMPOSITION OF GLOBAL AND LOCAL DISPARITY
We provide decomposition of Global and Local Disparity into three sources of unfairness: Unique, Redundant, and Masked Disparity, and provide examples to illustrate and better understand these disparities in the context of FI..
Proposition 1. The Global and Local Disparity in FL can be decomposed into non-negative terms:
T(Z; Ý) = Uni(Z: + Red Z
(2)
I(Z;\15) Uni(Z:}|S) Syn(Z.Y,
We refer Fig. 2 for an illustration of this result. Equation 2 follows from the relationship between different PID terms while Equation 3 requires the chain rule of mutual information (Cover, 1999). For completeness, show the non-negativity of PID terms in Appendix C.
4

---

Published as a conference paper at ICLR 2024
The term Uni(Z:Y|S) quantifies the unique information the sensitive attribute Z provides about the model prediction y that is not provided by client label S. We refer this as the Unique Disparity. The Unique Disparity contributes to both Local and Global Dis- parity, highlighting the region where they agree. Red(Z:Y, S) quantifies the information about sensitive attribute Z that is common between prediction Y and client S. We call this the Redundant Disparity. The Unique and Redundant Disparities together make up the Global Disparity I( Syn(Z:Y, .S) represents the synergistic information about sensitive attribute Z that is not present in either Y or S' individually, but is present jointly in ()) We refer to this as the Masked Disparity, as it is only observed when Y and S are considered together. Redundant and Masked Disparities cause disagree- ment between global and local fairness.
Global Disparity 1(2:9)
Local Dispariry 1(2:
Redundant Disparity Red (Z:Y.)
Unique Disparity Uni (Z.Y
Masked
Disparity
Syn (2-Y,5)
Canonical Examples. We now examine a loan approval scenario featuring binary- sensitive attributes across two clients, i.e., Y, Z,5 E {0, 1}. Here, (Z Y, ()) i.e., the maximum disparity is bit.
Disagreement Region
Agreoment Region
Disagreement
Region
Figure 2: Venn diagram of PID for Global & Local Disp. with agree- ment and disagreement regions.
Example 1 (Pure Uniqueness). Let Ý = Z and Z IL S. The men (Z 1) and women (Z 0) are identically distributed
across the clients. Suppose, the model only approves men but rejects women for a loan across both clients. This model is both locally and globally unfair, I(Z = 1(;;)[s)) 1. This is case of purely Unique Disparity since all the information about gender derived exclusively from the model predictions; the client S has no correlation with gender Z. Both Global and Local Disparities are in agreement. Here, Uni(Z:
1, Red((ZY S) 0, and Syn(Z.Y,5 =
Example 2 (Pure Redundancy). The client S = 0 has 90% women, while client S = has 90% men. So. there is a correlation between the clients and gender. Suppose, the model approves everyone from client S = 1 while rejecting everyone in S = 0 (i.e., Y = S). Such a model is locally fair because men and women are treated equally within particular client, and T(Z; V O. However, the model is globally unfair since I(Z; Y) 0.53. This a case with pure Redundant Disparity since information about Z is derived from both Y and S. Global and Local Disparities are in disagreement. Here, Uni(Z ( = 0, Red(Z.Y. S) = 0.53, and Syn(Z (Z:Y, S) = O.
In general, pure Redundant Disparity is observed when Z and Ý are correlated and 2 - S - form a Markov chain, i.c., y = S and S = g(Z) for some function g.
Example 3 (Pure Synergy). Let Y Z @ S and Z 11 S. The model approves men (Z = 1) from client S = and women (Z = 0) from client S = 1, while others are rejected. Such a model is locally unfair, as it singularly prefers one gender within each client with I(Z; YIS) = 1. However, it is globally fair since it maintains an equal approval rate for both men and women with I(Z; y) 0. This is a case with pure Masked Disparity as information about Z that is not observable in either Y or S individually is present jointly. Here, Uni(Z:Y\55 0, Red Z:Y, S) = O, and Syn(Z:Y 8) 1.
Merits of PID. These canonical examples demonstrate scenarios with pure uniqueness, redundancy. and synergy. In practice, there usually mixture of all of these disparities. i.c., non-zero Unique, Redundant, and Masked Disparities. In these scenarios, PID serves as a powerful tool that can disen- tangle the regions of agreement and disagreement between Local and Global Disparity, particularly when data is distributed non-identically across clients (also see experiments in Section 4). In contrast, traditional fairness metrics lack the granularity to capture these nuanced interactions, making PID an essential asset for more comprehensive understanding and mitigation of disparities. Using PID, we can uncover the fundamental Eefommation-thooreee limits and trade-offs between Global and Local Disparities, which we will examine in greater depth next.
3.2 FUNDAMENTAL LIMITS ON TRADEOFFS BETWEEN LOCAL AND GLOBAL DISPARITY
We examine the use of local fairness to achieve global fairness, or scenarios where model is trained to achieve local fairness and subsequently deployed at the global level. Since clients have direct
5

---

Published as a conference paper at ICLR 2024
access only to their data, implementing local disparity mitigation techniques at the individual client level is both practical and convenient. Studies such as Cui et al. (2021) argue that local fairness is important models are deployed at the local client level. However, this raises critical question about the impact on global fairness. In Theorem 1, we formally demonstrate that even local clients able use some optimal local mitigation methods and model aggregation techniques achieve local fairness, the Global Disparity may still be greater than zero.
Theorem 1 (Impossibility of Using Local Fairnsss Attain Global Fairness). As long Redundant Disparity (e:(Z.Y, 8) > O, the Global Disparity (Z; Y) > 0 even if Local Disparity goes to O.
In order to achieve local fairness, Unique and Masked Disparities must be reduced to zero. The proof leverages Proposition 1, partieularly relying on non-negativity of Unique and Redundant Disparities (see Appendix D). Recall, Example (Pure Redundancy), where the Local Disparity was zero, but the Global Disparity was 0.53 as result of the Redundant Disparity. This is not uncommon in real- world scenarios. Sensitive attributes like race or ethnicity may be correlated with location. For instance, one hospital may mainly cater to White patients, whereas another could predominantly serve Black patients. A model may be trained to achieve local fairness but would fail to be globally fair due to non-zero Redundant Disparity, highlighting the region of disagreement (see Fig. 2).
We now consider the scenario where model is able to achieve global fairness and is subsequently deployed at the local client level.
Theorem 2 (Global Fairesss Does Not Imply Local Fairness). As long Masked Disparity Syn (in, S)>0, fairess will not be attained even if global is attained.
To achieve global fairness, the Unique and Redundant Disparities must reduce to zero Recall Example 3 (Pure Synergy), where the model accepts men from client S = and women from client S = 1, while rejecting all others. While this model is globally fair, it is not locally fair. This demonstrates that while it is possible to train model achieve global fairness, it may still exhibit disparity when deployed at the local level due to the canceling of disparities between clients. This effect is captured by the Masked Disparity.
We now discuss the necessary and sufficient conditions to achieve global fairness using local fairness. Theorem 3 (Necessary and Sufficient Condition to Achieve Global Faimess Using Local Fairness). If Local Disparity 1( 1(2; Y (S) goes to zero, then Global Disparity 1(Z; Y) also goes to zero, if and only if the Redundant Disparity Red (Z:Y, S)= A sufficient condition for Red(Z:Y 5)== is S.
Theorem 3 suggests that if the sensitive attributes is uniformly distributed across clients the Redundant Disparity will reduce to zero (see proof in Appendix D). Hence, when the Local Disparity goes to zero, the Global Disparity will also decrease to zero. However, in practice, this proportion is fixed since the dataset at each client cannot be changed, i.e., T(Z; 5) fixed. Therefore, we examine another more controllable condition to eliminate Redundant Disparity even when I(Z O.
One might think that potential solution to have Red(Z:Ý, S) 0 is to enforce independence between Y and S, i.e., the model should make predictions at the same rate across all clients. However, interestingly, the PID literature demonstrates counterexamples (Kolchinsky, 2022) where this does not hold. We show that an additional condition of Syn(Z:Ý, .S) 0 is required.
Lemma 3. A sufficient condition for Red( S) 0 is Syn(Z:8, = 0 and V I1 S.
Remark 1. It is worth noting that the independence between Ý and S can be approximately achieved if the true Y and S are independent, as Y is estimation of Y. The mutual information I(Y: S) can provide insights into the anticipated value of I(Y; S). as FL rypically aims to also achieve reasonable level of accuracy. However, it is often the case that 1(Ý; S) is fixed due to the fixed nature of datasets at each client. It may even be possible to enforce Y L. S at the cost of accuracy.
Lastly, we examine conditions attain local faimess through global faimess. Theorem 4. Local disparity will always be less than Global Disparity if and only if Masked Disparity Syn( ZŁ S) = 0. A sufficient condition is when Z Y - S form a Markov chain.
Remark 2 (Extension to Personalized Federated Learning Setting). Interestingly, our results extend to the personalized FL setting, where client can tailor the final global model V =(X) into

---

Published as a conference paper at ICLR 2024
personalized version to improve local performance, Y = fX)). In this case, we can define the global model random variable Y (() and all of the propositions would hold.
3.3 AN OPTIMIZATION FRAMEWORK FOR EXPLORING THE ACCURACY FAIRNESS TRADE-OFF
We investigate the inherent trade-off between model accuracy and fairness in the FL context. We formulate the Accuracy and Global-Local Fairness Optimality Problem (AGLFOP), an optimization to delineate the theoretical boundaries of accuracy and fairness trade-offs, capturing the optimal performance any model or FL technique can achieve for a specified dataset and client distribution.
Let A be the set of all joint distributions defined for (Z. Y, Y). Let A, be set of all joint distributions Q E A that maintain fixed marginals on (Z, S, Y) as determined by a given dataset and client distribution, i.e., Ap {Q E A Pro(Z=z,55)) Y=y) Pr(Z=z, S=s, =y), Vz, y)
Definition& 4 (Accuracy and Global-Loca Fairness Optimality Problem (AGLFOP)). Let To (2; and (2; (I) be Global and Local Disparity under distribution Q. Then, the AGLFOP for specific dataset and client distribution an optimization of the form:
arg min QEAp
err(Q) subject to
[2( Y) S <g. TQ(Z:VIS) S 61,
(4)
where err(Q)=E Prq(Z=z, S=s, - + 9), the classification error under dis- tribution Q (I(-) denotes the indicator function). err(Q) E [0, 1| quantifies the proportion of incorrect predictions, calculated as the summation of the probabilities of misclassifying the true labels. The complement of the classification error, 1 err((QQ) quantifies the accuracy.
Theorem 5. The AGLFOP is a convex optimizatiion problem.
The AGLFOP is a convex optimization problem (see proof Appendix E) that evaluates all potential joint distributions within the set Ap which includes the specific dataset and how they are distributed across clients. The true distribution of this given dataset across clients Pr(Z = 2, 8, Y = y)- This makes it an appropriate framework for investigating the accuracy-faimess trade-off. The Pareto front of this optimization problem facilitates a detailed study the trade-off's, showcasing the maximum accuracy that can be attained for given global and local fairness relaxation (eg: e1).
The set Ap can further restricted for specialized applications, e.g., to constrain to all derived classifiers from optimal classifier (Hardt et al., 2016). We can restrict our optimization space Ap to lie within the convex hull derived by the False Positive Rate (FPR) and True Positive Rate (TPR) of initially trained classifier. This would characterize the accuracy- fairness tradeoff for all derived classifiers from the original trained classifier. The convex hall characterizes the distributions that can be achieved with any derived classifier. The constraints of AGLFOP can also be expressed using PID terms, offering intriguing insights that we will examine in the following section. The AGLFOP can be computed in any FL environment. Specifically, their computation necessitates the characterization of the joint distribution Pr(Z=2, S=s, Y-y) Pr(S=s) Pr (r(==((S=s) Pr(Y=ylZ=z,, -=ss) which can be readily acquired by aggregating pertinent statistics across all participating clients.
Remark 3 (Broader Potential). The AGLFOP currently focuses on independence between Z and Y, but can be adapted to explore other fairness notions. It can also be used to study optimality in situations where different clients have varying fairness requirements, e.g., adhering to statistical parity globally while upholding equalized odds at the local level. Moreover, variants of this optimization problem can be developed to penalize only the worst-case client fairness scenarios.
EXPERIMENTAL DEMONSTRATION
In this section, we provide experimental evaluations synthetic and real-world datasets to validate our theoretical findings.2 We investigate the PID of Global and Local Disparity under various conditions. We also examine the trade-offs between these fairness metrics and model accuracy.
Data and Client Distribution. We consider the following: (1) Synthetic dataset: A 2-D feature vector X= X1) has distribution, i.e., x X 2), (1(-0~ -2), [10 4l).
Implementation is available https: http::s:///tttub.com//////e/ thwb.
Hamman Fai PRI-PPD

---

Published as a conference paper at ICLR 2024
10
Syath L:Ace-darness ont
1.0
Synth E: Unnq Dhop
100
1.0
Sorth Red. Diep
2.20
Synth 1: Mass Disp.
200
60-
0.0
475
08-
6.75
0.0
275
64
0.4
64
0.4
62
0.2
62.
0.2
880
"5b
"8o
Syath
Synth Usiq
Red,
Synth
Local Dispurity Bound E:
0.30
0.6
0.6
62-
6.25
0.2
1.2
02
24 66
30
6.2
0.4
044
66
0.0
Sruth J.Acs Saneess Trade off
Stuth Uni. Disp.
Stuth 7. Red. Disp.
South 2: Mas Disp.
648
0.0
375
68-
6.75
0.6
0.75
6.06
492
6.20
1.0
64-
66.
0.4
02
0.2
02-
0.2
3.25
980
31
055
E4
65
14
88
01
Adidb Aus- faimas Tradbaff
Adul: Uni Dip
1298
Addl: Rod Dip.
8.000
Adul: Max Dip
04-
04-
0.4
1075
61
6.70
03
A325
61
8.02
80
03
02
150
08
83
100
1.00
Global Disparity Bound
Figure 3: AGLFOP Pareto Frontiers for Synthetic and Adult Datasets with PID. (first column) shows maximum accuracy (1 err) that can be achieved on a dataset and client distribution for given global and local fairness relaxation (eg, a). Synthetic data in scenario 1 (first row) is characterized by Unique Disparity. Local and global fairness agree, and accuracy trade-offs balanced between them. Synthetic data in scenario with a = 0.9 (second row) dominated by Redundant Disparity with trade-offss mainly between global fairness and accuracy (an accurate model could have Local Disparity but be globally unfair). Synthetic data in Scenario 3 (third row) is characterized by Masked Disparity with trade-off's mainly between local fairness and accuracy (an accurate model could have zero Global Disparity but be locally unfair). Adult data with heterogeneous split (fourth row: details Appendix F). displaying predominantly Masked Disparity but notable presence of Redundant Disparity, capturing more complex relationships and trade-offs.
Assume binary sensitive attribute Z=1 Xo.>0 and O otherwise to encode a dependence; and (2) Adult dataser (Dua & Graff, 2017) with gender as sensitive attribute. We consider three cases for partitioning the datasets across clients: (Scenario 1) sensitive-attribute independently distributed across clients, i.e., Z IL S, (Scenario high consitive-attribue heterogeneity across clients, i.e.. Z = S with probability a, and (Scenario 3) high sensitive-attribu synergy level across clients, i.c., Y S. Further details are described in Appendix F.
Trade-off Pareto Front. To study the trade- offs between model accuracy and different fairness constraints, we plot the Pareto frontiers for the AGLFOP. We solve for maximum accuracy (1 err) while varying global and local fairness relaxations (cg, e1). We present results for synthetic and Adult datasets as well as PID terms for various data splitting scenarios across clients.3 The three- way trade-off among accuracy, global, and local fairness can be visualized as contour plot (see Fig. 3).
Experiment A:
Interestingly, PID allows us to quantify the agreement and disagreement between local and global fairness. In scenarios characterized by Unique Disparity, local and global fairness agree, and accuracy trade-offss are balanced between them. In cases characterized by Redundant Disparity, the trade-off primarily between accuracy and global fairness (the accuracy changes along the horizontal axis (c)) seemingly nonexistent given (cg)). contrast, scenarios with Masked Disparity exhibit trade-off that is primarily between accuracy and local faimess (the trade-off is across the vertical axis).
We use Python dit package (James al., 2018) for PID computation and evxpy for convex solvers.
8

---

Published as a conference paper at ICLR 2024
Unique
Redundant
Masked
Dispurity (Bits)
2.05
0.08
0.00
0.24
6.0
2:00
6.10
0.23
0.30
0.75
0.8
Scenurio
Socnario 2
Secnario
0
055
Feeterogeeityy
Synergy Lovels À
Figure 4: (left) Plot demonstrating scenarios with Unique, Redundant, and Masked Disparities for the Adult dataset (model trained using FedAvg). Unique Disparity when sensitive attributes are equally distributed across clients. Redundant Disparity when there is dependency between clients and sensitive attributes (scenario 2; a = 0.9). Masked Disparity is dominant with high sensitive attribute synergy level across clients. (middle) Illustrates PID for varying levels of sensitive attribute heterogeneity (a; see details in Appendix F.2). When a is close to 0.3, the data is split evenly across clients (note Pr(Z=0)=0.33 for the Adult dataset), resulting in higher level of Unique Disparity. As a deviates from 0.3, i.e., higher dependency between Z and S. the Unique Disparity decreases while Redundant and Masked Disparity increases. (righr) Illustrates relationship between the synergy level (A; see details in Appendix F.2) and global and local fairness. As the synergy level increases, the Masked and Local Disparity increases expected.
Experiment B: Demonstrating Disparities in Federated Learning Settings. In this experiment, we investigate the PID of disparities on the Adult dataset trained within a FL framework. We employ the FedAvg algorithm (McMahan et al., 2017) for training and analyze:
PID Across Various Splitring Scenarios. We partition the dataset among clients based on Scenarios 1-3, utilize FedAvg for model training in each case, and examine the PID of both Local and Global Disparities (see Fig. 4). For each scenario,
also evaluate the effects of using local disparity mitigation technique. This is achieved by incorporating a statistical parity regularizer at each client. The results and implementation details are presented in Table in Appendix F.2.
PID Under Varying Sensitive Attribute Heterogeneity Level. We partition the dataset across two Pr(Z = 0|S = 0) to control the sensitive attribute heterogeneity level across clients. Our results are summarized in Fig. 4 and Table 2 in Appendix F.2.
clients with varying levels of sensitive attribute heterogeneity. We
Observing Levels of Masked Disparity. We partition the dataset with varying sensitive attribute synergy levels across clients to study the impact on the Masked Disparity. The synergy level X E [0, 1] measures how closely the true label Y aligns with Z @ S (see Definition 10 in Appendix F.2). Results are summarized in Fig. 4 and Table in Appendix F.2.
K= Experiments Involving Multiple Clients. We experiment with multiple clients = 5 and K = 10. Our findings are presented in Fig. 6, Fig. 5 and Table 4 in Appendix F.2.
Discussion. Our information -hheoretic framework provides nuanced understanding of the sources of disparity in FL, namely, Unique, Redundant, and Masked disparity. Our experiments offer insights into the agreement and disagreement between local and global fairness under various data distributions. Our experiments and theoretical results show that depending on the data distribution achieving one can often come at the cost of the other (disagreement). The nature of the data distribution across clients significantly impacts the disparity that dominates. Our optimization framework establishes the accuracy-fairness tradeoffs for a dataset and client distribution.
Importantly, our research can: (i) inform the use of local disparity mitigation techniques and their convergence and effectiveness when deployed in practice; and (ii) also serve as valuable tool for policy decision cacasionn-mate making, shedding light on the effects of model bias at both the global and local levels. This is particularly relevant in the expanding field of algorithmic fairness auditing (Hamman et al., 2023; Yan & Zhang, 2022). Future studies could also investigate how this approach could be extended to more sophisticated fairness measures. The estimation of PID terms largely depends on (i) the empirical estimators of the probability distributions; and (ii) the efficiency of the convex optimization algorithm used for calculating the unique information. As the number of clients or sensitive attributes increases, the computational cost may rise accordingly. Future work could explore alternative efficient PID computation techniques (Belghazi et al., 2018; Venkatesh & Schamberg, 2022; Pakman et al., 2021; Kleinman al., 2021).
9

---

Published as a conference paper at ICLR 2024
REFERENCES
Annie Abay, Yi Zhou, Nathalie Baracaldo, Shashank Rajamoni, Ebube Chuba, and Heiko Ludwig. Mitigating bias in federated learning. arXiv preprint arXiv:2012.02447, 2020.
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A reductions approach to fair classification. International conference on machine learning, pp. 60-69. PMLR, 2018.
Masashi Sode Akihiko Fukuchi, Yoko Yabe. Fairtorch. fairtorch, 2021.
com/ http://ww..wwwwwboeeeee w
Wael Alghamdi, Hsiang Hsu, Haewon Jeong, Hao Wang, Peter Michalak, Shahab Asoodeh, and Flavio Calmon. Beyond adult and compas: Fair multi-class prediction via information projection. In Advances in Neural Information Processing Systems, volume 35, pp. 38747-38760. Curran Associates, Inc., 2022.
Sina Baharlouei, Maher Nouiehed, Ahmad Beirami, and Meisam Razaviyayn. Renyi fair inference. arXiv preprint arXiv: 12005, 2019.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeswar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and R Devon Hjelm. Mine: mutual information neural estimation. arXiv preprint 1oXivv/801.0e 04062, 2018.
Nils Bertschinger, Johannes Rauh, Eckehard Olbrich, Jürgen Jost, and Nihat Ay. Quantifying unique information. Entropy, 16(4):2161-2183, 2014.
Flavio Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R Varshney. Optimized pre- processsssigg for discrimination prevention. Advances neural information processing systems, 30, 2017.
Clément Canonne. A short note on an inequality between kl and tv. arXiv preprint arXiv:2202.07198, 2022.
Irene Chen, Fredrik D Johansson, and David Sontag. Why is my classifier discriminatory? Advances in neural information processing systems, 31, 2018.
Jaewoong Cho, Gycongjo Hwang, and Changho Suh. A fair classifier using mutual information. In 2020 IEEE international symposium on information theory (ISIT), pp. 2521-2526. IEEE, 2020.
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:2109.0566 09.66662. 2021.
Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
Sen Cui, Weishen Pan, Jian Liang, Changshui Zhang, and Fei Wang. Addressing algorithmic disparity and performance inconsistency in federated learning. Advances in Neural Information Processing Systems, 34:26091-26102. 2021.
Wei Du, Depeng Xu, Xintao Wu, and Hanghang Tong. Fairness-aware agnostic federated learning. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 181-189, SIAM, 2021.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http::/arcciiie... ics . uci. sddu/m..
S. Dutta, D. Wei, H. Yueksel, P. Y. Chen, S. Liu, and K. R. Varshney. Is there trade-off between fairness and accuracy? a perspective using mismatched hypothesis testing. International Conference Machine Learning (ICML), pp. 2803-2813, 2020a.
Sanghamitra Dutta and Faisal Hamman. A review of partial information decomposition in algorithmic fairness and explainability. Entropy, 25(5):795, 2023.
10

---

Published as a conference paper at ICLR 2024
Sanghamitra Dutta, Praveen Venkatesh, Piotr Mardziel, Anupam Datta, and Pulkit Grover. An information -etormation-theoreiic quantification discrimination with exempt features. In Proceedings of the AAAI Conference Artificial Intelligence, 2020b.
Sanghamitra Dutta, Praveen Venkatesh, Piotr Mardziel, Anupam Datta, and Pulkit Grover, Fairness under feature exemptions: Counterfactual and observational measures. IEEE Transactions Information Theory, 67(10)6675--6710 2021.
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, pp. 214-226, 2012.
David A Ehrlich, Andreas C Schneider, Michael Wibral, Viola Priesemann, and Abdullah Makkeh. Partial information decomposition reveals the structure of neural representations. arXiv preprini arXiv:2209.10438, 2022.
Yahya H Ezzeldin, Shen Yan, Chaoyang He, Emilio Ferrara, and A Salman Avestimehr. Fairfed: Enabling group fairness in federated learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 7494-7502, 2023.
Sainyam Galhotra, Karthikeyan Shanmugam, Prasanna Sattigeri, and Kush R Varshney. Causal feature selection for algorithmic fairness. Proceedings of the 2022 International Conference on Management of Data, pp. 276-287-22 2022.
AmirEmad Ghassami, Sajad Khodadadian, and Negar Kiyavash. Fairness in supervised learning: An information theoretic approach. In 2018 IEEE international symposium on information theory (ISIT), pp. 176-180. IEEE, 2018.
Ziv Goldfeld and Yury Polyanskiy. The information bottleneck problem and its applications in machine learning. IEEE Journal on Selected Areas Information Theory, 1(1):19-38 38, 2020.
Vincent Grari, Boris Ruf, Sylvain Lamprier, and Marcin Detyniecki. aawre neural reyni minimization for continuous features. arXiv preprint 191 2019.
Faisal Hamman, Jiahao Chen, and Sanghamitra Dutta. Can querying for bias leak protected attributes? achieving privacy with smooth sensitivity. In Proceedings the 2023 ACM Conference on Fairness, Accountability, and Transparency, pp. 1368-1368, 2023.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
Shengyuan Hu, Zhiwei Steven Wu, and Virginia Smith. Provably fair federated learning via bounded group loss. arXiv preprint 2tt::2203.119900 2022.
R. James, C. J. Ellison, and P. Crutchfield, dit: a Python package for discrete information theory. The Journal of Open Source Software, 3(25):738, 2018. doi: https://doi.org/100 10.2 105/joss.00738.
Peter Kairouz, Jiachun Liao, Chong Huang, Maunil Vyas, Monica Welfert, and Lalitha Sankar. Gen- erating fair universal representations using adversarial models. arXiv preprint urXiv:1910.004. 2019.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2))1-2i6 2021.
Toshihiro Kamishima, Shotaro Akaho, and Jun Sakuma. Fairness- learning through regular- ization approach. In 2011 IEEE 11th International Conference on Data Mining Workshops, pp. 643-650. IEBE, 2011.
Jian Kang, Tiankai Xie, Xintao Wu, Ross Maciejewski, and Hanghang Tong. Multifair: Multi group fairness in machine learning. arXiv preprint arXiv:2108 1069, 2021.
11

---

Published as a conference paper at ICLR 2024
Joon Sik Kim, Jiahao Chen, and Ameet Talwalkar. Fact: A diagnostic for group faimess trade-offs. In Interaational Conference on Machine Learning, pp. $264-52744 PMLR, 2020.
Michael Kleinman, Alessandro Achille, Stefano Soatto, and Jonathan C Kao. Redundant information neural estimation. Entropy, 23(7):922, 2021.
Artemy Kolchinsky. A novel approach to the partial information decomposition. Entropy, 24(3):403, 2022.
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. arXiv preprint a905: 1049, 2019.
Paul Pu Liang, Yun Cheng, Xiang Fan, Chun Kai Ling, Suzanne Nie, Richard Chen, Zihao Deng, Nicholas Allen, Randy Auerbach, Faisal Mahmood, et al. Quantifying & modeling multimodal in- teractions: An information decomposition framework. Advances in Neural Information Processing Systems, 36, 2024.
Suyun Liu and Luis Nunes Vicente. Accuracy and fairness trade-offs in machine learning: A stochastic multi-objective approach. Computational Management Science, 19(3):513-55) 2022.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication-
Learning of Deep Networks from Decentralized Data. In Aarti Singh and Jerry Zhu (eds.). Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp. 1273-1282. PMLR, 20-22 Apr 2017.
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey bias and fairness in machine learning. ACM Comput. Surv., 54(6), jul 2021.
Aditya Krishna Menon and Robert C Williamson. The cost of fairness in classification, arXiv preprint arXiv:1705.09055 2017.
Salman Mohamadi, Gianfranco Doretto, and Donald A Adjeroh. More synergy, less redundancy: Exploiting joint mutual information for self-supervised learning, arXiv preprint arXiv:2307.00651, 2023.
Ari Pakman, Amin Nejatbakhsh, Dar Gilboa, Abdullah Makkeh, Luca Mazzucato, Michael Wibral, and Elad Schneidman. Estimating the unique information of continuous variables. Advances in neural information processing systems, 34:20295-20307, 2021.
Afroditi Papadaki, Natalia Martinez, Martin Bertran, Guillermo Sapiro, and Miguel Rodrigues. Minimax demographic group fairness in federated learning. arXiv preprint arXiv:2201.00 08304, 2022.
Dana Pessach and Erez Shmueli. review on fairness in machine learning. ACM Comput. Surv. 55 (3), feb 2022.
Borja Rodríguez--Gälve,, Filip Granqvist, Rogier Dalen, and Matt Seigel. Enforcing faimness in private federated learning via the modified method of differential multipliers. arXiv preprint arXiv:2109.08604 2021.
Sivan Sabato and Elad Yom-Tov. Bounding the fairness and accuracy of classifiers from population statistics. In International conference machine learning, pp. 8316-8322 PMLR, 2020.
Mukund Prasad Sah and Amritpal Singh. Aggregation techniques in federated learning: Compre- hensive survey, challenges and opportunities. In 2022 2nd International Conference on Advance Computing and Innovative Technologies Engineering (ICACITE), pp. 1962-1967, 2022.
Yuxin Shi. Han Yu, and Cyril Leung. A survey of fairness-aware federated learning. arXiv preprint arXiv:2111.0187.. 2021.
Megan Smith, Cacilia Munoz, and D. Patil. Big Risks, Big Opportunities: the Intersection of Big Data and Civil Rights, 2016.
12

---

Published as a conference paper at ICLR 2024
Tycho MS Tax, Pedro AM Mediano, and Murray Shanahan. The partial information decomposition of generative neural network models. Entropy, 19(9):474, 2017.
Praveen Venkatesh and Gabriel Schamberg, Partial information decomposition via deficiency for multivariate gaussians. In 2022 IEEE International Symposium on Information Theory (ISIT), pp. 2892-2897. IEFE, 2022.
Praveen Venkatesh, Sanghamitra Dutta, Neil Mehta, and Pulkit Grover. Can information flows suggest targets for interventions neural circuits? Advances in Neural Information Processing Systems, 34:3149-3162, 2021.
Hao Wang, Hsiang Hsu, Mario Diaz, and Flavio P Calmon. To split or not to split: The impact of disparate treatment classification. IEEE Transactions on Information Theory, 67(10))6733-6777, 2021.
Hao Wang, Luxi He, Rui Gao, and Flavio Calmon. Aleatoric and epistemic discrimination: Fun- damental limits of fairness interventions. Thirty-sevente Conference on Neural Information Processing Systems, 2023a.
Lin Wang, Zhichao Wang, and Xiaoying Tang. Fedeba+: Towards fair and effective federated learning via entropy- model. arXiv preprint arXiv:2301.12407, 2023b.
Patricia Wollstadt, Sebastian Schmitt, and Michael Wibral. A rigorous information-tie -thooretic definition of redundancy and relevancy feature selection based on (partial) information decomposition. Mach. Learn. Res., 24:131-1, 2023.
Tom Yan and Chicheng Zhang. Active faimess auditing. In International Conference on Machine Learning, pp. 24929-24962. PMLR, 2022.
Qiang Yang. Federated learning / Qiang Yang, Yang Liu, Yong Cheng, Yan Kang, Tianjian Chen, Han Yu. Synthesis lectures on artificial intelligence and machine learning, #43. Morgan & Claypool, San Rafael, California, 2020.
Yuchen Zeng, Hongxu Chen, and Kangwook Lee. Improving fairness via federated learning. arXiv preprint arXiv:21 2021.
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 Big Data (Big Data), pp. 1051-1060, 2020.
Han Zhao and Geoffrey J Gordon. Inherent tradeoff's in learning fair representations, The Journal of Machine Learning Research, 23(1):2527-2552 2022.
A RELEVANT BACKGROUND ON INFORMATION THEORETIC MEASURES
We outline key information-theoreiic measures pertinent to this paper's discussions.
Definition (Entropy). Entropy quantifies the uncertainty or unpredictability of random variable Z. It mathematically defined by the equation:
H = Σ Pr = log Pr(Z z).
(5)
Definition 6 (Mutual Information). Mutual Information, T(Z;Y), quantifies the amount of informa- tion obtained about random variable Z through Y. Specifically, measures the degree of dependence between two variables. Z and Y, capturing both linear and non non-linear dependencies:
Pr(Z =
T(Z;V) Σ Pr(Z v log 2.
(6)
Pr(Z = 2) Pr(ý =
13

---

Published as a conference paper at ICLR 2024
Definition 7 (Conditional Mutual Information). The conditional mutual information, I(Z; SS) measures the dependency between Z and Y, conditioned on S:
Pr(Z = 2, 5|S =))
((: = Σ
Pr(S = 8, 2 2, 9)) log 8,2.y
(7)
Pr(Z = 2/5 5) Pr(Y 0 =)
or alternatively,
I(2; Σ Pr(S s]{; = =)).
(8)
Mutual Information as a Measure of Fairness. Mutual information can be used measure of the unfairness or disparity model. Mutual Information has been interpreted as the dependence between sensitive attribute Z and model prediction Y (captures correlation as well as all non-linear dependencies). Mutual information is zero if and only if Z and Y are independent. This means that if the model's predictions are highly correlated with sensitive attributes (like gender or race), that's sign of unfairness. Mutual information has been explored in fairness in the context of centralized machine learning in Kamishima al. (2011); 1); Cho et al. (2020); Kang et al. (2021).
In recent work, Venkatesh al. (2021) provides another interpretation of mutual information I(Z; P) fairness as the accuracy predicting Z from Ý (or the expected probability error in correctly guessing from Y) from Fano's inequality. Even in information bottleneck literature, mutual information has been interpreted measure of how well one random variable predicts (or, aligns with) the other (Goldfeld & Polyanskiy, 2020).
For local fairness, we are interested in the dependence between model prediction Y and sensi- tive attributes Z at each and every client, i.e., the dependence between Y and Z conditioned on the client S. For example, the disparity at client S = 1 is I(2; Y|S =) (the mutual informa- tion (dependence) between model prediction and sensitive attribute conditioned on client S (considering data at client S 1). Our measure for Local Disparity is the conditional mutual information (dependence) between Z and Y conditioned on S, denoted 1(2; Y|S). Local disparity = = (Z: s), average of the disparity each client weighted by the p(s), the proportion data at client S = 8. The Local Disparity is zero and only if all client has zero disparity in their local dataset.
B ADDITIONAL RESULTS AND PROOFS FOR SECTION 3
Lemma 1 (Relationship between Global Statistical Parity Gap and I(Z; Let Pr(Z-0) = a. Pr(ý 1|2 = Pr(ý 1|2 = 0) is bounded by ((.)
The gap SP Pygtobal
2a(1-a)
Proof. Mutual information can be expressed as KL divergence:
I(2;8) = DeL (Pr(t, Z)
(9)
Using Pinsker's Inequality (Canonne, 2022),
drv S (..55.)) (Q
(10)
14

---

Published as a conference paper at ICLR 2024
where, drv ( Q2) is the total variation between two probability distributions Q1 Q2.
drv (Pr(Y, Z), Pr()) 2 Σ Pr(Y = -. 2 0) Pr(Z =
Pr(Z = Σ
Pr(y 2| =) P أ3
0.3
Pr(Z = 1) Pr(P = 1| 1) -Pr(P = 1]] (Pr(v 0/ =1) -P)-Pr(- = 0]]
2
Pr(Z 0)
Prr(Y 1 0) Pr( 1) Pr(y = 0|Z 0) - Pr(ś 0)]
2 a1 aJ|SPI| 2 a0 SPPO
1
+ 2
- -11-=))SPP1 + 20(1 aS|SP
2
= =a(1 a) SP1| + a(1 SSP
(11)
where Pr(Z 0) 1 Pr 1) 1) a, and
SPi Pr(y = z| 1) 1)
Pr(Y = = 2 - 0) = Pr(( i| Pr(ý i).
To complete the proof, we show:
SP = Pr(( 1/% 1) pr(Ý =)
= =Pr(Y- -1/Z 1) (1- = 01)
= =- -11+ --rP = 1|2 = 1) Pr(8 =0)
--Pr(Ý 0|2 =) + Pr(Y 0) SPP..
Hence, |SP1| |SPO]. From Equation 11 we have: 2ax - a) S VO.
Remark (Tightness of Lemma 1). Since our proof exclusively utilizes Pinsker's 's inequality, their tightness is equivalent. Given 1(Z; S min(H( H(Y)} < H(Y) and H(Y) S in binary classification. Hence, T(Z; Y) < 1 which is aligned with the known light regime of Pinsker's s inequality (i.e., (KL(Pl(p)))) S 1) (Canonne, 2022). The inequality tighter with smaller mutual information (Z; Y) values.
Lemma 2. I(Z: if and only if (1a0:///112211....--0111-11--35- at all clients s.
Proof. We aim to establish that T(Z; ÝIS) = 0 if and only Pf 1| 1,5= PP = 1|Z 0, s) for all clients For brevity, we denote Pr(Z 2, = s, Y = y) = (,
Forward Direction: Assume 1(2; Y| O.
From Definition 7, we have:
p(2, B1s))
I(Z;\Is) Σ p(s, 2, 0) log 8,2.8
0.
p(zls)p(ūis)
This implies that log
p(a,91)) p(=]s)p(0 x)
for all s, 2, 9. and consequently
p(a01ss) p(=(s)p(((s)
1sss.
Observing that p(2, ūls) = p(= (= s), we deduce that p(=ls)p((lz.))
1 p(= e)p((ee)
From this, it directly follows that p(0) 2, s) = p(O s). and thus Pr(ř = 1|2 = 1, = =) Pr(ý 1 0)
Reverse Direction: Assume Pr(f = 1 = 1, S = s) = Pr(ý 1 0,5 s) for all 8.
This implies p(0 s,, 2) p(](s) for all s, y. Plugging this into the definition of conditional mutual information, we find T(Z;Y]S) 0.
15

---

Published as a conference paper at ICLR 2024
Thus, both directions of the equivalence proven, concluding the proof.
Corollary 1. The statistical parity each client s can be expressed
V0.5 s)
|SP. S 20, -Oa)
where, Pr(Z 0) = Pr(Z = 1|5 =
Definition 8 (Difference Between Local and Global Disparity). The difference between Global and Local Disparity is: I(Z;Y) - 1() = which, unlike other nutuallinfformation--oaaa measures, can be positive or negative.
This term is the "interaction information,"
Interaction information quantifies the redundancy and synergy present in system. In Fl., positive interaction information indicates a system with high levels of redundancy and Global Disparity, while negative interaction information indicates system with high levels of synergy and Local Disparity. Interaction information can inform the trade-off between Local and Global Disparity.
C PROOF FOR SECTION 3.1
Proposition 1. The Global and Local Disparity in FL can be decomposed into non-negative terms:
I(Z;)) Uni Uni(Z.Y|5) + Red(Z.
(2)
(I:)) = Uni(Z:P|S) Syn(Z:Y,
(3)
Proof. Equation 2 follows directly from the PID terms definition.
Uni(Z:Y|SS) Red(Z:Y, 8)=
min Iq (Z; (|5 I(Z;Y) min IQ(Z: I(Z;
QEap
QEAp
Equation follows from PID terms definition and the chain rule of mutual information.
Uni(Z: + Syn(Z:Ý, S) = min (Z; y + T(Z; 5) 1(Z; - min
[Q V18)
QEA,
QEA,
IIZ + I[Z
=I( Ý ().
Now, we prove the non-negativity property of PID decomposition.
Uni(Z:Ý (S) mingEs, 1q (Z; S|S is non-negative since the conditional mutual information is non-negative by definition.
Syn(Z.Ý, S) = I(Z;\|s) minges, I2(Z: ((: - I(2: =0
The Redundant Disparity:
Red (od( 8) = I(Z;)) - min lQ (z(Z)\1S) = max I0(2; 12(2:81S)
QEA,
QEA,
First equality holds by definition. Second equality holds since marginals on (Ý, 2) is fixed in Ap. hence, maxqea, (Ý: Z) = 2))
To prove non-negativity of redundant disparity, we construct distribution Qo such that:
Pr(Z = y. = Pr(Z z, y = Pr(2 = S =)
Pr(Z 2)
Next, we show Qu E Ap. Recall the set Ap in Definition 1:
A, = (QEA: Pr = z, & v) Pr(2 Z 2, v), Pr ( 2 Pr(Z P =
Q
16

---

Published as a conference paper at ICLR 2024
Pr(Z v,Y 1) Σ Pr(Z 2, = y,S=s)) =Σ Pr(Z = 2, 2r =
Pr(Z 2,5=
Qo
Qo
Pr(Z Pr(Z=2)
Pr(Z = 2, ,, Y= = y) Pr(Z =2)
Σ
Pr(Z- = = 8) Pr(Z = =2, y)
Pr(Z=2, Qo
8) Σ Pr(Z Z = =, =, s) Σ
Pr(Z = =, = y) Pr(Z 2, =
Qu
Pr(Z 2)
Pr(Z 2, 2.
Prr(2 = 2, = -) 2 Pr(Z = 2, 2, s).
Pr(Z =2(
Marginals of Qo satisfy conditions set Ap. hence Qo E Ap Also, note that by construction of Qo.
Y and are independent conditioned on Z, i.e. Too 5|5) = 0. Hence, we have:
Red (Z:Y, 8)
(4) max
()( (2; QEAp
(2:1) Leo (2,(2;11)) 815)
(Z) + HY, 11q. (Z, Y) HQ. HQ, + HQ. (Z, 81))
Too (Y:5) Too (Q: (5:
(0)
( 1e. 5) 2 0.
Here, (a) hold from definition Red Red(2:Ý, ( (b) hold since Qo E Ap. (c)-(d) holds from expressing mutual information in terms of entropy, (e) hold since lgo S|Z) 0, (f) holds from non-negativity property of mutual information.
D ADDITIONAL RESULTS AND PROOFS FOR SECTION 3.2
Theorem 1 (Impossibility of Using Local Fairness to Attain Global Fairness). As long as Redundant Disparity Red(2:Ý, > 0, the Global Disparity 1(2; Ý) > 0 even if Local Disparity goes to O.
Proof. For completeness, we have provided a detailed proof that demonstrates the non-negativity property of the terms involved.
Uni(Z:Ý|.S) = mingeA, ( is non-negative since the conditional mutual information is non-negative by definition.
Syn(Z:Ý, S) = I[Z; ((Z minges, [o(Z) I(Z:i1s) ((5 0.
The Redundant Disparity:
Red (2:Ý, S) I(Z; min To (Z; max TQ 2) - -000=
QEAp
QEA,
First equality holds by definition. Second equality holds since marginals on (Ý, (Z) is fixed in Ap. hence, maxQEa, (Ý; 2) = 2).
To prove non-negativity of redundant disparity, we construct distribution Qu such that:
Pr(Z Z = = v = y, s) Pr(Z 2, = yy Pr(Z = S s) Pr(Z= = 2)
Next, we show Qu E Ap. Recall the set Ap in Definition 1:
Ap = (QEA: Pr = z, & v) = Pr(Z Z = 2,
Pr Pr. = 2, P = =))= =
Q
17

---

Published as a conference paper at ICLR 2024
Pr(Z = z, Y y) Σ Pr(Z 2, = =)) Σ Pr(Z = =2,8= =
Pr(Z 2, S s)
Qo
Pr(Z=z)
Pr(Z 2,Y y)
Σ
Pr(Z =, 5 = 8) Pr(Z = =z,8 =-y= =y).
Pr(Z = 2)
Pr(Z = 2, Y = y) Pr(z = 2, =.S== =
= 2, s) = Σ Pr(Z = = =y, 5) Σ
40
Q0
Pr(Z =z)
1
Pr(Z 7 2, 2,
Σ Pr(Z 2, = =1)= yy) =Pr(Z =, S= s).
Pr(Z= =)
Marginals of Qo satisfy conditions on set Ap, hence Qo E Ap. Also, note that by construction of Qo.
Y and S are independent conditioned on Z, ie.. L. (Y; S|Z) 0. Hence, we have:
Red (2:Y, S)
(a)
(0( - 12; pEAp
max
LQ. (2:Y) -Le (2:
HQo + HQ) HQo (Z, HQ. HQ.((()) + HQ. (Z, 81s)
(Y;;)) -TQ (8;
1o. (Y:5) L 0.
Here, (a) hold from definition of Red SS). (b) hold since Qo Ap: (c)-(d) holds from expressing
mutual information terms entropy, (e) hold since Ig. S)Z) 0, (f) holds from non negativity property of mutual information.
Hence, from proposition 1, we prove Theorem
As Local Disparity I(Z; Y|S) + 0, then Uni(Z.ÿ[S) > 0 and Syn(Z.Ý, S) - 0, therefore the Global Disparity (Z; + Red(Z. S) 20 O.
Theorem 2 (Global Fairness Does Not Imply Local Fairness). As long as Masked Disparity Syn(Z:ř,S)) S)>0, local fairness will not be attained even if global fairness is attained.
Proof. Proof requires the non-negativity property of PID terms (follows similarly from proof of Theorem 1). The argument then goes as follows:
As Global Disparity T(Z; () + 0, then Uni(Z: > and Red(Z.Ý, >> 0, therefore the Local Disparity I(Z; Y|5) > Syn(Z.Ý, 20.
Theorem 3 (Necessary and Sufficient Condition to Achieve Global Fairness Using Local Fairness). If Local Disparity 1(2; Y (S) goes to zero, then Global Disparity I(Z; Y) also goes to zero, if and only if the Redundant Disparity Red
A sufficient condition for Red(Z: - is 7 S.
Proof. From the PID of Local and Global Disparity.
I(Z Uni Red Red(ZłÝ, ,.Y,)))
I(Z; I(Z; = Uni(2:115 + Syn(Z:Ý, S).
Therefore if, T(Z; VIS) = 0. then Uni(Z:ÿ155) = 0. Hence,
I(Z;ý) Red 7:Ý
18

---

Published as a conference paper at ICLR 2024
I ( = = Red(Z:Y,S)) =.
To prove the sufficient condition, we leverage the PID of ((; and the non-negative property of the PID terms:
T(2:5) = Uni(Z:S(V) + Red(Z:Y,S)
1(Z 2 Red( (2:
Hence, S Red((e) = 0.
Lemma 3. A sufficient condition for Redd(ZYY,30 = is
= and Y TL S.
Proof. Interaction information expressed PID terms (see Definition 8):
[ I(Z;)) 12; Ý (S) = Red((. (YYY,)) S) - Syn( (Y
If Masked Disparity Syn(Z;Y, = 0, we have:
I(;;Y:5) I(; - I(2; Red (Z:8, 2
Since the interaction information is positive and symmetric,
1(Ý;5) 2 I(;; ((Z; = Red (2: S).
Therefore, Y 11 S = Red(Z.Y, = 0.
Theorem 4. Local disparity will always be less than Global Disparity if and only if Masked Disparity Syn(Z:V, S) = 0. A sufficient condition is when Y - S form a Markov chain.
Proof. By leveraging the PID of ((Z)))
I(Z Uni(Z:S()) + Syn(Z.Y,
Markov chain - - S implies, I(2; (()) 0. Hence, Syn( (ZY =
Rest of proof follows from nonnegative property of PID terms:
I(2:\15) = Uni(Z:Y|S) < Uni(Z:Y[S) Red((:) =((Z)))
E PROOFS FOR SECTION 3.3
Definition (Convex Function). function f R" said to convex if. for all 3τ, 22 and for all À E [0, 1), the following inequality holds:
IR"
f()x + (1 -X)x2) S + (1-))(())))
(12)
Lemma 4 (Log Sum Inequality). The log-sum inequality states that for any two sequences of non-negative numbers a₁ 02 ........ aa,, and by, bz..... bns the following inequality holds:
.b....,,.
Σ a: log
Σ
log
1iml
(13)
bi
Theorem 5. The AGLFOP a convex optimization problem.
Proof. The Ap is convex set, since for any two points Q1, 21 E Ap. their convex combination also lies in Ap (probability simplex). To prove AGFOP is convex optimization problem, we show each term is convex in Q using the definition of convex function (see Definition 9).
Let Q Ap denote the joint distribution for (Z, Y, For brevity, we denote Pr(Z 2,
Y = y) p(2, 8, v), the fixed marginals on (Z, S.Y). Additionally, we denote Pro 2 = 2,
Y y, V 5) Q 8, y, ÿ) the probability under distribution Q.
19

---

Published as a conference paper at ICLR 2024
To prove that err(Q) is convex, we need to show: err(Qx) & (err(Q1) + (1 N)err(Q2). where
Q = XQ1 + (1 (1- 2)Q2. VQ1, Q2 E Ap, and X E [0, 1].
We first express err( as:
err(Qx)= E Q,(2,8,y,,3 Tly+
+ 1)
2,8.9.9
Σ Q1(z, 1(y + 1) + (1- Σ 2.9.8.8
Q2(2,,,8,83 I(y + D)
2.6.y.8
(er)(Q1) (1 A)er
Thus, err(Q) is convex as it satisfies the convexity condition.
To prove convexity of lo (Z; 9), we show that AQ1, Q2 E Ap and AA E [0, the following inequality holds: IQ, (2 )) S ATo, (2;Y) + (1 X)To, (2:
Note that the marginals are convex in the joint distribution, i.e., Qx = -) E..p 8,
This is not necessarily true for conditionals. However, when some marginals are fixed, convexity holds for some conditionals, i.e., (xlz) = Ex,y Qx 0)/p(2).
Note that the conditional Qx (x(2)) ()) is convex in the joint distribution Qx(z, s,
(x(2)) = Σ (.()/s. =E D..
S.y/
= Σ S.
s.V
Hence, we can show convexity of To (e(Z;)) Y) in (xl=)):
Qx(=,))
(2;8) Σ Qx(2,)) log
Qx(=)Qx(i)
9
(x12))
Σ (x(3)) log
Qx(0)
2
(a)
Σ ((=)(AQ((0))) + (1
x)Q2(0l2)) (1-0)/0))0 log
(QQ(01)) +
+ (1 1)Q22(12)
AQi (1-
(6)
Σ ((l2) log [1(012)
(2(0)z)
+ (1 (1- Σ p(z)(2(01z) log
Qi(
Q2(ÿ)
2
Ale. (2; + (1 x))
Here (a) holds from expressing the linear combinations. Also note that, which can also be expressed as linear combination. The inequality (b) holds from the log-sum inequality (see Lemma 4).
(x)))))()).
To prove the convexity of To (Z; VIS), we show that YQI. Q2 E Ap and vA E [0, 1). the following inequality holds: IQ, (2; Y () < Alo, (2; ÝIS) + (1 A)lo,
Note that the conditional (ū]=z, 8) is convex in the joint distribution
Qx(0l2,s) = Σ
= Σ
3 Σ s. 8
20

---

Published as a conference paper at ICLR 2024
Hence, we can show convexity of (o(Z)Y]S) in @x(0)2,)):
lo (2; (2;815)= = Σ Qx 8, log [x(0i2zs))
(ūls))
2,8,9
(1
Σ p(z,s) (AQ1 + (1- log
XQ1(01s) (1- (012(
2,8,9
(6)
(21(8),,3)
(2(0)2,
p(2, (0lz, s) log
+ +11 A) Σ
p(z, (2(
(0lss)
Q2(0ls)
2.
2,6,9
= Alq. (z: Y S) (1 1)1o. (2:
The equality (a) holds from linear combinations of (x(s)) (x(0012,)))(11l) The inequality (b) holds due to application of the log-sum inequality (see Lemma 4).
F EXPANDED EXPERIMENTAL SECTION
This section includes additional results, expanded tables, figures, and details that provide a more comprehensive understanding of our study.
Dataset. We consider the following datasets:
(I) Synthetic dataset: 2-D feature vector X (Xo, follows a distribution given by X y== (1). Assume Z is a binary sensitive attribute such that 2 = if Xo 0, else Z to encode dependence of Xo with Z.
(2, 2). 1 I.). x ~ (((-2, 22,, 1
(2) Adult dataset: The Adult dataset is publicly available dataset in the UCI repository based on 1994 U.S. census data (Dua Graff, 2017). The goal is to predict whether an individual earns more or less than $50,000 per year based on features such occupation, marital status, and education. We select gender as sensitive attribute, with men as Z= and women as Z=0.
Client Distribution. We strategically partition our datasets across clients to examine scenarios characterized by Unique, Redundant, and Masked Disparities.
Scenario I: Uniform Distribution of Sensitive Attributes Across Clients. The sensitive attribute Z is independently distributed across clients, i.e., Z 1L S. We randomly distribute the data across clients.
Scenario 2:
High Heterogeneity in Sensitive Attribules Across Clients. We split to observe hetero- geneity in the distribution of sensitive attributes across clients, i.e., Z with a probability a. For instance, when is composed of 90% men. For the Adult dataset, we use a = Pr(Z Z = 0 0) as a parameter to regulate this heterogeneity.
0.9, the client with S 0 consists of 90% women, while the client with S = 1
Scenario 3: High Synergy Level Across Clients. The true label Y = Z + S. To emulate this scenario, partition the data such that client S 0 possesses data of males (Z = 1) with true labels Y = 1 and females (Z = 0) with true labels Y = 0. Conversely, client = contains the remaining data, i.e., males with Y and females with Y 1.
We introduce the synergy level (Definition 10) to measure alignment to Y = @ S.
Definition 10 (Synergy Level (A)). The synergy level E [0. of a given dataset and client distribution is defined as the probability that the true label Y is aligned with Z @ S,
Pr(y 2 S),
where x implies perfect alignment between Y and 7 ④ S, and X 0 implies zero alignment.
To set À when splitting data across clients, first split with perfect XOR alignment and then shuffle fractions of the dataset between clients.
Adult Heterogeneous Split. In Fig. 3 (fourth row), we split the Adult dataset to capture various disparities simultancously. We set the synergy level À = 0.8 (see Definition 10). Due to the nature of the Adult dataset, this introduces some correlation between the sensitive attribute Z and client S.
21

---

Published as a conference paper at ICLR 2024
F.1 EXPERIMENT A:
TRADE-OFF OFF PARETO FRONT.
To study the trade-offis between model accuracy and different fairness constraints, we plot the Pareto frontiers for the AGLFOP. We solve for maximum accuracy (1 err) while varying global and local fairness relaxations (cg. q). We present results for synthetic and Adult datasets as well as PID terms for various data splitting scenarios across clients. The three-way way trade-off among accuracy, global, and local fairness can be visualized as a contour plot (see Fig. 3).
For the Adult dataset, we restrict our optimization space Ap lie within the convex hull derived by the False Positive Rate (FPR) and True Positive Rate (TPR) of an initially trained classifier (trained using FedAvg). This characterizes the accuracy-fairness for all derived classifiers from the original trained classifier (motivated by the poot-procsssing technique from Hardt et al. (2016)). The convex hall characterizes the distributions that can be achieved with any derived classifier. The convex hull for each protected group is composed of points, including (0, 0), (TPR, FPR), (TPR, FR) and (1, 1), where TPR and FPR denote the true positive and false positive rates of a predictor that inverts all predictions for a protected group. Future work could explore alternative constraints for various specialized applications.
F.2 EXPERIMENT B: DEMONSTRATING DISPARITIES IN FEDERATED LEARNING SETTINGS.
In this experiment, we investigate the PID of disparities in the Adult dataset trained within a FL framework. We employ the FedAvg algorithm (MeMahan al., 2017) for training.
Setup. Our FL model employs a two-layer architecture with 32 hidden units per layer, using ReLU activation, binary cross-entropy loss, and the Adam optimizer. The server initializes the model weights and distributes them to clients, who train locally partitioned datasets for 2 epochs with batch size of 64. Client-trained weights are aggregated server-side via the FedAvg algorithm, and this process iterates until convergence. Evaluation metrics are estimated using the dit package (James et al., 2018), which includes PID functions for decomposing Global and Local Disparities into Unique, Redundant, and Masked Disparity, following the definition from Bertschinger al. (2014).
We analyze the following scenarios:
PID of Disparity Across Various Splitting Scenarios. We partition the dataset across two clients, each time varying the level of sensitive attribute heterogeneity (a = Pr(Z = OiS = 0)). The Adult dataset exhibits a gender imbalance with male-to-female ratio of 0.33 0.67. Consequently, Pr(Z = 0) = 0.33, making a = Pr(Z- = 0,5 0) = 0.33 the independently distributed case.
In this first setup, distribute the sensitive attribute uniformly across clients (splitting scenario 1) and employ FedAvg for training. The FL model achieves an accuracy of 84.45% with a Global Disparity of 0.0359 bits and a Local Disparity of 0.0359 bits. The PID reveals that the Unique Disparity is 0.0359 bits, with both Redundant and Masked Disparities being negligible. This aligns with our centralized baseline, indicating that the disparity originates exclusively from the dependency between the model's predictions and the sensitive attributes, rather than being influenced by S.
When the dataset is split to introduce high heterogeneity in sensitive attributes across clients (splitting scenario 2). the resulting FL model exhibits Global Disparity of 0.0431 bits and a Local Disparity of 0.0014 bits. PID reveals a Redundant Disparity of 0.0431 bits and a Masked Disparity of 0.0014 bits, with no Unique Disparity.
Next we split and train according to splitting scenario 3 (A = 0.9). The trained model reports a Local Disparity of 0.1761 bits and Global Disparity of 0.0317 bits. The PID decomposition shows Masked Disparity of 0.1761 bits and a Redundant Disparity of 0.0317 bits, with no Unique Disparity observed. The emergence of non-zero Redundant Disparity is attributable to the data splitting, which consequently leads to ((2 = 0.2409 bits.
We summarize the three scenarios in Fig. 4. Additionally, we evaluate the effects of using a naive local disparity mitigation technique on the various disparities present.
Effects of Naive Local Fairness Mitigation Technique. We evaluate the effects of using naive local disparity mitigation technique on the various disparities present. This is achieved by incorporating a statistical parity regularizer to the loss function at each individual client:
22

---

Published as a conference paper at ICLR 2024
Redundart
Masked
8.00
Olcel
Lood
Disgarity
0.00
Orobal
0.00
0:22
0.22
2.01
801
0411
Figure 5: Plot demonstrating scenarios with Unique, Redundant, and Masked Disparities for the Adult dataset 5 client case. Difficulty in splitting to achieve pure Redundant and Masked Disparity due to the proportion of labels the dataset.
client_los = clientt www..rross.ettooy.llss.s.
client.fai reerrnnesssee harpttf.iiressssooss
We use an implementation from FairTorch package (Akihiko Fukuchi, 2021). The term / hyperparameter that trades off between accuracy and fairesss. We use 3 = 0.1 to maintain similarly accurate models. The results are presented in Table
Table I: Table illustrates the effects of using a naive local disparity mitigation technique on the various scenarios. It proved efficacious only when Unique Disparity is present (scenario 1). However, with high redundancy or synergy (scenarios 2 &3), the utilization of the disparity mitigation technique exacerbated disparities.
Loc.
Glob.
Uniq.
Red.
Mas.
Scenario
0.0359
0.0359
0.0359
0.0000
0.0000
fairness
0.0062
0.0062
0.0062
0.0000
0.0000
Scenario 0.0014
0.0431
0.0000
0.0431
0.0014
faimesss
10
0.0626
0.0000
0.0626
0.0110
Scenario 0.1761
0.0317
0.0000
0.0317
0.1761
faimesss
0.0935
0.0418
0.0053
0.0365
0.0882
PID of Disparity under Heterogeneous Sensitive Attribute Distribution. We analyze the PID of Local and Global Disparities under different sensitive attribute distributions across clients. We train the model with two clients, each having equal-sized datasets. We use a Pr(Z 0 = 0) to represent sensitive attribute heterogeneity. Note that for fixed a, the proportions of sensitive attributes the other client are fixed. For example since Pr(Z 0) 0.33 for the Adult dataset, 0.33 results in even distribution of sensitive attributes across the two clients. Our results are summarized in Fig. 4 and Table 2. We also provide results for federating clients in Table 4.
Table 2: The PID of Global and Local Disparity for varying sensitive attribute heterogeneity a
I(Z; S)
Local
Global
Unique
Redundant
Masked
I(Ý;; S)
Accuracy
0.1
0.1877
0.0262
0.0342
0.0000
0.0342
0.0262
0.0080
86.54%
0.2
0.0575
0.0336
0.0364
0.0064
0.0301
0.0273
0.0028
86.95%
0.3
0.0032
0.0363
0.0365
0.0332
0,0032
0.0031
0.0002
86.86%
0.33
0.0000
0.0340
0.0340
0.0340
0.0000
0.0000
0.0000
87.34%
0.4
0.0154
0.0311
0,0319
0.0186
0.0133
0,0125
0.0009
86.70%
0.5
0.0957
0.0368
0.0413
0.0023
0.0390
0.0345
0.0045
86.77%
0.6
0.2613
0.0242
0,0346
0.0000
0,0346
0,0242
0,0104
86.61%
0.66
0.4392
0.0185
0.0325
0.0000
0.0325
0.0185
0.0140
86.36%
Observing Levels of Masked Disparity. We aim to gain deeper understanding of the circumstances with Masked Disparities. Through scenario 3, we showed how high Masked Disparities can occur. However, the level of synergy portrayed in the example may not always be present in practice. We attempt to quantify this using a metric synergy level. The synergy level (A) measures how closely the true labels Y align with the XOR of Z and S (see Definition 10). To achieve high synergy level,
23

---

Published as a conference paper at ICLR 2024
0.0
Borstie Aitiouta Hww.ogeratty
Figure 6: Plot showing the PID of dísparities when the data is near i.idd among K = 10 clients. All types disparities can be observed. The value a 0.33 represents the case where the data is i.i.d. and only Unique Disparity is observed.
apply the method outlined in Scenario To decrease X, we randomly shuffle data points between clients until the synergy level reaches O. We conduct experiments with varying levels of synergy to observe the impact on the Masked Disparity. The results are summarized in Fig. 4 and Table 3.
Table 3: PID of Global and Local Disparity under varying synergy levels À
A
I(Z;5)
Loc.
Glob.
Uniq.
Red.
Mas.
I(Y;S)
Acc.
(ZZ 0) I(Z; -
0
0.0035
0.0402
0.0373
0.0338
0.0035
0.0063
0.0005
85.12%
0.0196
0.0608
0.25
0.0113
0.0486
0,0419
0.0308
0.0111
0.0178
0,0009
85.54%
0.0819
0,0152
0.5
0,0299
0.0536
0.0335
0.0127
0.0208
0.0410
0.0033
85.24%
0.1056
0,0017
0.75
0.0846
0.0932
0.0366
0.0023
0.0343
0.0909
0.0068
85.26%
0.0024
0.1840
0.2409
0.1644
0.0149
0.0000
0.0150
0.1644
0.0201
84.30%
0.0839
0.2450
Multiple Client Case. We examine scenarios involving multiple clients. Observations are similar to the two-client case previously studied. To observe high Unique Disparity, sensitive attributes need be identically distributed across clients. To observe the Redundant Disparity, there must be some dependency between clients and specific sensitive attribute, meaning certain demographic groups are known to belong to a specific client. The Masked Disparity can be observed when there a high level of synergy or XOR behavior between variables Z and S. Note that since S is no longer binary, we can convert its decimal value to binary and then take the XOR.
We experiment with K 5 clients and examine the three disparities. To observe the Unique Disparity by randomly distributing the data among clients. For Redundant Disparity, we divide the data such that the first clients mostly females and the remaining three clients mostly males. For Masked Disparity, we distribute the data similarly to scenario 3 (see Fig. 5 and Fig. 6).
Additional Insights from Experiments. When data is uniformly distributed across clients, Unique Disparity is dominant and contributes to both global and local unfairness (see Fig. 4 Scenario I: model trained using FedAvg the adult dataset and distributed uniformly across clients). In the trade-off Pareto Front (see Fig. 3, row 1). we see that both local and global fairness constraints have balanced tradeoffs with accuracy. The PID decomposition (Fig. 4, row 1, column 2.3.4) explains this as we see the disparity is mainly Unique Disparity, with little Redundant or Masked Disparity. The Unique Disparity highlights where Local and Global Disparity agree.
In the case with sensitive attribute heterogeneity (sensitive attribute imbalance across clients). We observe mainly Redundant Disparity (see Fig. 4, scenario and middle), this globally unfair but locally fair model (recall Proposition 1). Observe in the tradeoff plot (see Fig. 3, row 2) that the accuracy tra with mainly global fairness (an accurate model could have zero Local Disparity but be globally unfair).
In the cases with senritive-attribut synergy across clients. For example, a two-client case (one client is more likely to have qualified women and unqualified men and vice versa at the other client). We observe that the Mask Disparity is dominant (see Fig. 4, Scenario 3). The trade AGLFOP tradeoff plot (see Fig. 3, row 3) is characterized by Masked Disparity with trade-offs mainly between local fairness and accuracy (an accurate model could have zero Global Disparity but locally unfair). The Redundant and Masked Disparity highlights where Local and Global Disparity disagree.
24

---

Published as a conference paper at ICLR 2024
Table 4: PID of Global & Local Disparity for various sensitive attribute distributions across 10 clients.
Unique
Redundant
Masked
Global
Local
Accuracy
0.25
0.0219
0.0190
0.0178
0.0409
0.0409
84.85%
0.33
0.0376
0.0000
0.0000
0.0376
0.0376
85.58%
0.4
0.0268
0.0141
0.0137
0.0410
0.0405
84.85%
0,45
0.0107
0.0289
0.0270
0.0390
0.0377
84.85%
The AGLFOP provides the theoretical boundaries trade-offs, capturing the optimal performance any model or FL technique can achieve for a specified dataset and client distribution. For example, say one wants perfectly globally fair and locally fair model, i.c. (Eg 0, ej 0). Under high sensitive attribute heterogeneity (see Fig. 3, row 2), they cannot have model that does better than 64%.
25


Reviews:
[{"review_id": "sbAhdaeStC", "reviewer": "Reviewer_P5hg", "summary": "This paper introduces information theoretic tools to interpret the relationship among multiple group fairness trade-offs in federated learning. It is commonly known that global and local fairnesses both contribute to unfairness in federated learning, but their relationship (e.g. whether one implies the other) is unknown. The authors identify three fundamental sources of unfairness, and utilize them to derive fundamental limits on the trade-offs between global and local unfairnesses.", "questions": "1. This was mentioned in the Weaknesses section, and I would be very interested in seeing more explanations for choosing those definitions.\n\n2. Under a concrete data set, how are Uni(), Red(), and Syn() efficiently computed? I might be wrong, but my first impression is that, since they are relevant with mutual information, such computation may be expensive?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper provides a novel \"solution\" for unfairness in federated learning. Even if this issue has been extensively studied, there has been few work attempting to investigate the fundamental root that causes unfairness, let alone giving a theoretical explanation. This work uses a mathematically rigorous tool to give a promising attempt to explain unfairness. The theoretical justifications are rigorous and insightful.\n\nIn particular, Theorems 1, 2 and 3 are both conclusive and powerful, so that one may predict the fairness performances based upon those three sources of unfairness.", "weaknesses": "Overall this paper is well-written, but in Section 2, it would be great if the authors could provide some more justifications for Definitions 1 and 2, both mathematically and conceptually, even if the definitions are indeed fairly intuitive. This may be immensely helpful for readers especially those who do not have a strong background in information theory.", "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": "", "extra_scores": {}}, {"review_id": "BjZyW3z2GT", "reviewer": "Reviewer_rTkq", "summary": "This work presents an information-theoretic perspective on group fairness trade-offs in federated learning (FL) with respect to sensitive attributes. This paper leverages partial information decomposition to identify three sources of unfairness in FL. They introduce AGLFOP, a convex optimization that defines the theoretical limits of accuracy and fairness trade-offs, identifying the best possible performance any FL strategy can attain given a dataset and client distribution.", "questions": "1. Could you explain the main difference from [4]?  It seems it is a trivial improvement (Apply the PID analysis on FL) compared with this paper.\n2. Could you provide experiments of different baselines and different datasets, in the FL setting (partial client participation of cross-device FL.)\n3. Could you provide more results for trade-offs on accuracy and global-local fairness?\n4. Could you provide more details about the selection of hyperparameters to ensure optimal trade-off strategy under different data distributions and datasets?\n\n[4] Dutta S, Hamman F. A Review of Partial Information Decomposition in Algorithmic Fairness and Explainability[J]. Entropy, 2023, 25(5): 795.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper studies group fairness from an information theory perspective, which is valuable for the community to understand the group fairness of FL.\n2. The decomposition result is interesting.", "weaknesses": "1. Although this paper proposes an optimization framework with Definition 5, it does not give any solution or algorithm for solving the problem. \n2. The experiments are somehow weak, both the baseline and dataset are rare. There are other works focusing on FL group fairness like [1,2], and also about fairness and accuracy tradeoffs, like [3], that should be compared.\n3. The visualization (table or figure) of accuracy and global-local fairness trade-off results is relatively insufficient relying solely on the Pareto Frontiers shown in Figure 3. \n4. It seems of vital importance to properly set the hyper-parameters $\\epsilon_g$ and $\\epsilon_L$ for the optimal trade-off. The acc-fairness Trade-off figure displayed in Figure 3, lacks discussion based on more experimental settings and datasets.  \n5. The experiment setting details are not clear, for example, what is the used model and parameter settings?\n\n[1]Ezzeldin Y H, Yan S, He C, et al. Fairfed: Enabling group fairness in federated learning[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2023, 37(6): 7494-7502.\n[2]Papadaki A, Martinez N, Bertran M, et al. Minimax demographic group fairness in federated learning[C]//Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency. 2022: 142-159.\n[3]Wang L, Wang Z, Tang X. FedEBA+: Towards Fair and Effective Federated Learning via Entropy-Based Model[J]. ICLR 2023 Workshop ML4IoT.\n\nMinors:\nWhat is the formal definition of global fairness and local fairness?", "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": "", "extra_scores": {}}, {"review_id": "eCLngYKtWy", "reviewer": "Reviewer_GNty", "summary": "The paper considers the problem of trying to achieve fairness in a federated learning setting. There are multiple data sets that are all privately held and a model is trained for each one. The questions are: When are the models fair on each data set? And, when are the models fair on all the data?\n\nThe paper relates fairness in both settings and mutual information. In particular, they show that mutual information between the  model's prediction and the sensitive attribute is an upper bound on the square of statistical parity (Lemma 1). They also define \"local disparity\" as mutual information conditioned on the particular machine. They then analyze mutual information and show it comes from three sources: information only in the predictions or sensitive attributes, information in both individually, or information in both together.\n\nThey prove necessary/sufficient conditions about when mutual information is low depending on the sources of mutual information. I did not check the appendix for the proofs of these results.\n\nThey introduce a convex optimization problem for minimizing classification error subject to constraints that the mutual information and local information are low. They they solve the problem experimentally for different datasets and visualize the results.", "questions": "Lemma 1 upper bounds statistical parity with mutual information, how loose is the upper bound?\n\nWhat are interesting observations from your expeirments?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "• The paper investigates the problem of relating global and local fairness in the federated learning setting. According to them (I have not checked), the problem has not been studied before.\n\n• The use existing literature on partial information decomposition to identify sources of mutual information. \n\n• There are a ton of lemmas and theorems about when mutual information is small. It appears very comprehensive but I'd like a more direct narrative about what I should be surprised and impressed with.\n\n• I like the idea of the convex optimization problem and optimizing for error under mutual information constraints.\n\n• The experiments seem very comprehensive in terms of data sets and different settings of data distributions across clients.", "weaknesses": "• They don't persuade me that mutual information is the \"right\" notion of fairness. Lemma 1 establishes that mutual information is an *upper bound* on statistical parity but it could be a loose upper bound.\n\n• I think the presentation is difficult to follow and the paper should be rewritten in the following ways:\n- Give an example of the way the theorems and lemmas are proved.\n- I was confused by the general approach until I read the examples in Section 3.1. These examples aren't results so I think they should be moved up to the preliminaries section to facilitate understanding.\n- Lemma 1 and Lemma 2 are results proved by the authors but they appear in the preliminaries section. This was confusing to me especially because there was no discussion of how they were proved.\n- Unique information is used in the preliminaries before it is defined in Definition 3. I didn't find this definition helpful and I don't see similar definitions for redundant information or synergistic information. It would be great if you could define these three quantities in a direct and similar way. I don't know if this is true but maybe something like I(Z,Y|A \\cap B) is redundant information and I(Z,Y |A \\cup B) is synergistic information. I found the notation you used excessive.\n- I'm not sure from reading the main result section if the proofs of the theorems/lemmas following trivially from the definitions or not. Please make this clear with a proof of one of them.\n\n• The convex optimization section is very short. I think you should restructure to spend more space here given that it's one of your contributions.\n\n• I got the sense that the experiments were comprehensive but I was missing a discussion about what was interesting here. It'd be great to highlight interesting observations and findings from the experiments. Examples of how the mutual information perspective gives insight into local and global fairness would be great.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)