Bounding and Approximating Intersectional Fairness through Marginal Fairness
Authors: Mathieu Molina
Patrick Loiseau
Venue: NeurIPS 2022 Accept (2022)
Keywords: Intersectional Fairness
Supervised Machine Learning

Abstract: Discrimination in machine learning often arises along multiple dimensions (a.k.a. protected attributes); it is then desirable to ensure \emph{intersectional fairness}---i.e., that no subgroup is discriminated against. It is known that ensuring \emph{marginal fairness} for every dimension independently is not sufficient in general. Due to the exponential number of subgroups, however, directly measuring intersectional fairness from data is impossible. In this paper, our primary goal is to understand in detail the relationship between marginal and intersectional fairness through statistical analysis. We first identify a set of sufficient conditions under which an exact relationship can be obtained. Then, we prove bounds (easily computable through marginal fairness and other meaningful statistical quantities) in high-probability on intersectional fairness in the general case. Beyond their descriptive value, we show that these theoretical bounds can be leveraged to derive a heuristic improving the approximation and bounds of intersectional fairness by choosing, in a relevant manner, protected attributes for which we describe intersectional subgroups. Finally, we test the performance of our approximations and bounds on real and synthetic data-sets.

Bounding and Approximating Intersectional Fairness through Marginal Fairness
Mathieu Molina Inria FairPlay team 91 120 Palaiseau, France mathieu www.mmmiiiiaa......mmmm.mmmm.a..
Patrick Loiseau Inria FairPlay team 91120 Palaiseau, France lotriik..oiseauuinria..f.
Abstract
Diserimination in machine learning often arises along multiple dimensions (a.k.a. protected attributes); then desirable to ensure intersectional fairness-i.e -.. that subgroup is discriminated against. It is known that ensuring marginal fairness for every dimension independently is not sufficient in general. Due to the exponential number of subgroups, however, directly measuring intersectional fairness from data is impossible. In this paper, our primary goal is to understand detail the relationship between marginal and intersectional fairness through statistical analysis. We first identify a set of sufficient conditions under which an exact relationship can be obtained. Then, we prove bounds (easily computable through marginal fairness and other meaningful statistical quantities) in high- probability on intersectional fairness in the general case. Beyond their descriptive value, we show that these theoretical bounds can be leveraged to derive heuristic improving the approximation and bounds of intersectional fairness by choosing, in relevant manner, protected attributes for which we describe intersectional subgroups. Finally, we test the performance of our approximations and bounds on real and synthetic data-sets.
Introduction
Research on fairness in machine learning has been very active in recent years, in particular on fair classification under group fairness notions, see e.g., [16 30
28]. Such notions define demographic groups based on so-called protected allributes (e.g., gender, race, religion), and impose that some statistical quantity constant across the groups. For instance, demographic parity imposes that the class-1 classification rate is the same for all groups, but other notions were defined such as equal opportunity (16] calibration by group [7]-see a survey in 4. As exact fairness is too constraining, one often measures unfairness, which roughly quantifies the distance to the faireess constraint.
Most works on fair classification consider a single protected attribute and hence only two (or a small number of) groups Then, they measures of unfairness evaluate and penalize classifiers in order make them more fair. This is making an implicit but very fundamental assumption that one can estimate the unfairness measure from the data hand. With only few groups, this assumption is indeed easily satisfied as there are sufficiently many data points for each group.
In many-if not most-real-worid applications, there multiple protected attributes (typically 10-20) along which discrimination is prohibited 2 It is then desirable to consider the strong notion of intersectional fairness, which roughly specifies that subgroup (defined by arbitrary combination of protected attributes) is unfavorably treated. In that case, however, estimating the unfaimess measure becomes very challenging: the number of groups is exponentially large (e.g., 210 for 10 binary protected attributes), it is very likely that the dataset has at least one subgroup
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

for which there are very few (or zero) data point. A potential solution is to treat each protected attribute separately through its marginal unfairness (which is easy to estimate); but it was observed in several
and algorithmic examples that it is not sufficient to ensure intersectional faimeess 8 5 21 22]. This raises the question: How to estimate intersectional fairness from data, and what is its precise relation to marginal fairness? To date, only very few papers have tackled this issue. 121 [2] adopt a definition of intersectional fairness that weights the unfairness of each group by its size. This allows them to get large-samples generalization guarantees of empirical estimates (hence solving the estimation issue), but then it does not protect minorities since allows a very high unfairness for tiny subgroups- which is contradictory to the intuitively desired behavior.
17 makes a similar assumption by considering only subgroups above a minimum size, which eases estimate generalization. [14] on the other hand uses the more natural definition of intersectional fairness based on the worst treated group irrespective of its size; but they consider only a few protected attributes, precisely to have enough data points on each subgroup to estimate intersectional unfairness.
13 extends this work by proposing methods to interpolate for subgroups for which too few points are available, based on Bayesian machine learning models. However, this work is empirical and does not give any guarantee on the estimates obtained. In this paper, we also use the natural (strong) definition of intersectional fairness but we take instead a purely statistical approach. We view the protected attributes as random variables to understand intersectional fairness and how it related to marginal fairess more finely.
We identify sufficient conditions under which intersectional fairness can be exactly derived from marginal densities, which clarifies when marginal unfairness is good estimate of intersectional unfairness. We prove probabilistic bounds on intersectional unfairness based on marginal densities and independence measures of the protected attributes, that we show are easy to estimate. We propose a method to improve the approximation of intersectional unfairness and the theoretical bound based on grouping carefully some of the protected attributes together, which we do through a heuristic by leveraging the independence measures exhibited in our bounds. We perform experiments on real and synthetic datasets that illustrate the performance of our approach. In particular, we show that grouping with our heuristic does improve the approximation of intersectional unfairness. To the best of our knowledge, to better understand and estimate intersectional (un)fairness. Our work is fairly general and can be instantiated for variety of standard fairness notions (demographic parity, equal opportunity, etc.). For simplicity, we focus on discrete protected attributes and on classification, but most of the core results can be extended to other cases.
Contributions:
work is the first work to exploit statistical information
[31 proposes a unified framework to train a fair classifier under intersec- tional fairness metrics, but without taking into account regimes with sparse group membership data. Some works propose to audit the accuracy of fairness metrics in contexts other than intersectionality. when there are missing data (35) or when there are unlabeled examples [18). Others tackle the problem of interscctionality beyond group fairness, e.g., [32] considers causal intersectional fairness. Finally there has been some interest (4 10 in different formulation of intersectional group fairness as a mujti-oobeective optimization problem where each objective is the discrimination faced by a given protected group. Another interesting approach to faimess is individual faimess developed in [12]. however this is quite different from group faimess metrics on which we focus on and our techniques do not apply.
Further Related Works:
Setting and Models
2.1 Basic Setting
Notational convention: Wherever useful, for any two random variables V and W, we will use the short- hand (v)r)= pv.w Pr(V =u, w) and pv (v w) pw)= =v W ww)
Consider a multi-class classification task. A given individual is described by a tuple of random variables (X,A,X drawn according to a distribution D where X is the features vector, Y is the label with values in )/ and A = (AI,.., Aa) is a c'tuple of protected attributes. The only variable used to make a prediction is X and the only variable to measure unfairness is A, but otherwise there are no constraints and A can be part of X. We denote the support of X, Y. A and A for 1 < k < d, by X. V/ and A respectively. We assume that A is finite (hence discrete). For a deterministic classifier h, Y = +((X) is the predicted class for a random individual. The classifier h fixed, as we are interested in measuring its faimeess and not finding fair classifier.

---

To compare the discrimination between groups, we consider second random variable A'' such that (A') Y) is independent and identically distributed (i.i.d.) to (A Y). Some authors look at the difference in the treatment of protected groups as a ratio [14], and some others as a difference [2I]. Here we choose to study discrimination in terms of ratio. We further apply a logarithm to symmetrize the discrimination measure between two protected groups and for ease of computation. We will consider Statistical Parity for simplicity of exposition, but other group faimess metrics can be either derived directly or adapted using the methods developed in this paper (see Appendix A.I) We define measure of unfaireess as follows:
Definition 2.1. For a distribution D and a classifier h, we define the intersectional unfairness and the ttth protected attribute marginal unfairness as: u uly a, a'), and u (v.or.af)E)'x
sup
sup
uk (y, ais d'p)
(1)
(E.x,"")XXxAP
with (v, log Pr(rÝ= - - Pr(Y==y|A'=d)) us ak oh) oh)= 1 log Prr(Y= = A - Pr(Y== = -
(2)
One could think that if the marginal unfairness of each protected attribute is smaller than some > 0, then the overall unfairness is smaller than e; measuring uM ssup "4 corresponds to this idea. As stated in the introduction this is not sufficient to describe unfairness and we can still have u" >>'" uuM We can rewrite T as u = supyyoggsupp A ///a/ inf A PyJa), and similarly for uz. This means that to measure unfarmess we only need to analyze the function PYJA-
2.2 Estimation of Unfairness
If we want to estimate unfairness, the most straightforward approach is to estimate the probability mass function PA.y and then to compute the unfairness over these estimated distributions. The main difficulty in estimating the unfairness estimating inf P A as we can upper bound the sup by 1, but we cannot easily lower bound the inf. For a data-set of n samples and d protected attributes, we denote for (a, y) E AAx x y the counts by group and prediction as Na.9 = Σ.= 1((A(), y(()) (a, v)] where (A))) (() is the i-th i.i.d. realization of (A, Y). The empirical probability is then defined as Pr(Ý=y, A= = =Na.y/ n.. [14 shows in Theorem VIII. that the error made by using empirical estimates is decreasing in No. which means that there needs to be sufficient data for each protected group to estimate u². When there are many protected groups the probability that least one group receives no sample is high, and in this case there is at least one a in A for which the empirical probability Pr(Ý== = I A A=aa a) is undefined, hence the inf and sup cannot be computed. [13] and [4 alleviate this issue of O-counts by using a Dirichlet prior of uniform parameter a > This yield the Bayesian estimates (Na.y + a + |A)))),,, that are then used to compute the estimator up- They also propose other methods to estimate Prja which empirically performs better, but without guarantees; whereas ug has the nice property that U is a consistent estimator of u². This is because of the consistency of the Bayesian probability estimates and by applying the Continuous Mapping Theorem for max and min which are continuous. Note that the empirical estimator (with a = 0) is also consistent, but has infinite bias.
Nonetheless, ug has the drawback that for a low amount of samples and when the number of protected groups is high, it is almost determined deterministically by the parameter and cannot be trusted. If N. 0 for a protected group the estimated distribution is uniform on Ý A ==a and this group does not affect the computation of the sup and inf. Hence if the most discriminated group is among the undiscovered one, we risk making important error the estimation. When N, increases, gain more information on the distribution of Y A. However, when No is still low for all groups, the estimated distribution of the inf of Ý A= a is almost entirely determined by the prior parameter a.
2.3 Probabilistic Unfairness
When the number of protected subgroups grows arbitrarily large, it may be useless to try to guarantee fairness for every single one of them, regardless on how many people this truly affects. Should a decision maker sacrifice any potential predictive performance in order to guarantee faimess?? It could be argued that an algorithm which discrininates person among a 1000 can be described as fair to an extent. We may even be able to directly compensate the small amount of persons discriminated against if possible. Let us consider another example: if a company has clients on which it leverages machine learning predictions to make decisions, it would seem very limiting to guarantee fairness
3

---

for clients among specific protected groups for whom we will almost never deal with. Nevertheless, if the underlying clients distribution changes, our decision making process should also reflect this change in terms of fairness. This motivates looking at unfaimesss probabilistically (Y, A, A'). To do that we define the random unfairness U = = , A, A') the random variable which corresponds to randomly choosing prediction, and then independently selecting two protected groups according to PAIY to compare them. We now define our notion of probabilistic unfairness:
[0, 1], we say that classifier h over distribution D is (c,,))-rrbbbbb Definition 2.2. For 2 O and 5 E
intersectionally fair if Pr(U <) 5.
can be seen for some given E as a statement on the expected size of the population that is not being discriminated too much against. Probable intersectional fairness corresponds to searching for quantiles of U. We define the d-probabilistic unfairness as c" (6)) = minfc E I. Pr(U > c) S 8). is the (1 - qu-unnte of U.. We also know by definition that any classifiers over any distributions is (u* py-orbbayyy intersectionally fair, as we have U S u" with probability 1. This shows that probabilistic fairness is relaxed version of the hard intersectional unfairness as lims--o 6" (6) = u", and thus can be made arbitrarily close to intersectional fairness. order to give more intuition on what this measure of fairness represents, we will briefly only for this paragraph consider discrimination of protected groups compared to the predictions distribution py instead of between groups, meaning that we now measure log(p') / / )l. Suppose that a prediction model will be deployed over population of individuals. Then if the classifier is (c. 5) p-oobabb intersectionally fair, this means that A.Y [E!_, [[((((), (()) > e]] the expected number of people that faces a discrimination more than e is less than nó. This allows us to measure and control the size of the population that may face difference in treatment that would be deemed too high. It corresponds to the notion of fairness we were searching for. For more comparisons between these different notions, see Appendix AA.3
As a remark, looking at E[U), it can serve as lower bound of u² because B[U] Eya Py, AA (V, a, a' d')u(yy a, a²) S u². This represents the average discrimination in popu- lation between two protected groups. This weaker than the notion presented above and is only mentioned in passing.
Probabilistic fairness can be especially relevant in the context where A continuous sensitive attributes. Indeed, even for a very basic multivariate normal distribution on A, we will end up with u" =0= which is unhelpful. Yet by considering this notion of probabilistic fairness end up with finite (hence comparable) measures of unfairness where the discriminated population size can be explicitly controlled; see Appendix [A.4 for some examples. All in all, this notion of probabilistic unfairness, beyond its main interest of being a relaxed version of intersectional unfairness, could be in itself helpful for decision makers.
3 Measures of Independence and Theoretical Bounds
We now focus on providing valid (c, 5) couples for probable intersectional fairness. First note that while the intersectional unfairness u² is hard estimate, it is much easier to estimate the marginal unfaimess MM The work done by [22] in the different setting of weighted unfairness, however, shows through experiments that across multiple classifiers and data-sets, u" and uM can be uncorrelated, correlated, or even equal. Building on this observation, we would like to approach u" using marginal quantities estimable for reasonably-sized data-sets.
3.1 Intersectional Unfairness with Independence
Since the intersectional unfairness takes into account the interactions between all the protected attributes Ag. one could guess that if the Aş are mutually independent, this implies that u" is close to uM, Our first result is not far from this intuition, but we also need to take into account the influence from the classifier h. Indeed, even if the protected attributes are independent, since the classifier makes predictions based on X which may encode redundant information from some As. there can be interaction between those protected attributes through the classifier. See Appendix [ for a counter example with the independence of the Aş only but no clear relationship between marginal and intersectional fairness.
Proposition 3.1. If the protected attributes As are mutually independent and mutually independent conditionally on Y, then
" sup VE
sup usly, aks d())
<
(3)
k= (ox af

---

Sketch of proof. The main idea is to decompose PA and Paiy as their products of marginals using the independence assumptions, and using the fact that the sup taken over product of functions with independent variables is distributed over the product. The inequality is obtained because the sup of sum is smaller than the sum of the sup. See proof in Appendix B.2
This theorem gives us a first sense on how intersectional unfairness relates with marginal unfairness in some contexts. This shows us that if the independence conditions are fulfilled, then u(" becomes easy to estimate. What we provide here are conditions and a equation to derive direct relationship between the intersectional unfairness and the marginal unfairness of each Ag. These are unfortunately too strong conditions to actually expect and are almost never randomly satisfied, but they help us give insight into the relationship between marginal and intersectional fairness. It also drives the analysis conducted in the next sub sub-section. We would like to relax the independence criteria while still using marginal information from the problem.
3.2 Bounds on Probable Intersectional Fairness
In order to bound the probable intersectional unfairness and relate it with the strictly independent case, we want to use some measure of independence. We want to bound in probability the joint
probability density Pr(A=a) with the product of its marginals I Pr(A==as) We will use one of the possible multivariable generalization of Mutual Information known Total Correlation (29
C(A)=EA Tog
PA(A)
Σ aEA
Pa(a)log
PA(a)
Σ H(A))) (A), (4)
d
I PA (ax)
I PA, (Ax)
where (A) is the Shannon Entropy of A. Similarly we define the conditional total correlation as II& PA,IS (As - H (Ax (Y) - (AA IY) where
C(A| -[A,)) (loggp (A) H (Al is the conditional entropy of A given Y. Note that both can also be written in terms of a KL or expectation in Ý over conditional KL divergence, which means that C(A) 2 and C(A| O. From these measures of independence, we intuitively define the following two random variables, log((, (A)/ II, PAs (A+)) and L, = log(p A ( II PA,IS (Ax ()). By definition we have that = (A)) and E E, C(A] We denote a and By the standard deviation of these two variables. We have the following property:
- A& + C(A) = 0 + o 0 and 1 A& + C(A = 0 +> By 00 (5) The equivalence between independence and C(A) 0 comes from rewriting C(A) as a KL and the fact that QL)PII) -0 if and only if P= Q almost everywhere. For = ( @ PAI1=y)) we also use that the expectation of a positive random variable is 0 if and only the variable is 0 almost everywhere. When = then - constant which means that P.4 =I PA. es, and using that the probabilities must sum to 1 we have e-= 1 hence c= 0. The same arguments apply for dy- We denote T(VV W) = (V)- H(V W) the mutual information between variable V and W. With these definitions, we can now derive the following theorem which bounds the probable intersectional fairness with independence measures and functions of marginal densities:
Theorem 3.2. For d E (0, 1). any classifier h over a distribution D is (e1, 6) and (f2, opprbbayy intersectionally fair with,
él =1=2 suu NEY
Σ sup ucly, unly,ax, (k,)) dh)
ak
(6)
k= of JEA
Ps (1)
62 = 22 +up yEy
log
inf EAr P&lA, (1llaa)))) )
(7)
Vō
where
8" = (02/3 + oy 2/3/3/2 and ((A))) Σ ((A,, ((A
(8)
Sketch of proof. We apply Chebyshev's inequality to T. and T.y for some introduced parameters a to bound the tails of these random variables, while making sure that overall the probability bounds stay larger than 1 - 5. We can then compute inequalities on PA and P PApy and take the inf for and sup for a. This leads to a constrained minimization problem that can be solved, which yields s*. The full proof is in Appendix B.3 For c2 we additionally use that AAdd I 1 as y is discrete.
5

---

We observe that both 6 and 6g are composed of one term in s' related with the 6-confidence, and a quantity with marginal information. Aditionnaly c2 also includes a term in y that corresponds to some form of mutual information correction. We can control the confidence in this bound with the parameter 5. Because s* = if and only if o = By = and combined with (5) we can see that s* somewhat measures how far we are from the conditions of Proposition 3.1 With 61 we see that when
s* goes to zero, we recover exactly the conditions of Proposition 3.1
In order to prove Theorem 3.2 we used Chebyshev's inequality. We can derive a similar proof for other concentration inequalities, specifically with Chernoff bounds through the estimation of the moment generating function, which often leads to tighter bounds. However this leads to harder quantities estimate in addition having to solve a non-convex optimization problem, see Appendix B44
To conclude this section we provide additional intuition on the relationship between marginal and intersectional fairness. We can then derive the following corollary from the proof of the above
Theorem:
Corollary 3.3. Denoting T2,r)) Pr) the probability space on which (Y AAA,A A') is defined, there exists an event F so that for J(y, a) = I (PP (y) ux)/pg(()) we have for U the random unfairness:
2525* Vō
[(Y,AA) (w))
2V2s* v8
[[OY,A) ((Ý)A))
+ sup W
log
$ sup U(w)
S
sup WEF
log
(w) (9)
f(Y, A)
WEF
with Pr(F) 2 1-6. 8.
The proof can be found in Appendix B.3 This means that there is fraction of the relevant pairs population of size bigger than 1 - 6, for which we can give an interval for the maximum random unfairness over this fraction F. This interval is centered and reduce around unique quantity as s* goes to O, with 8* and 8 determining the length of this interval. When ò goes to O, we have (r) + 1 hence supwer Uww) + u² because we are dealing with finite random variables. Notice also that when both 5 and s* go to O, we recover Proposition 3.1 as suPwEr goes toward the quantity derived in this Proposition when 8 goes to 0.
3.3 Estimation of the measures of independence
Theorem 3.2 trades the precise estimation of u² with upper bound, but with much easier quantities to estimate. More specifically, as they are information measures, we can leverage the extensive literature statistical estimators and entropy estimation. We can intuitively see that the estimation of s and y will be easier to handle because even the estimation with the empirical distribution PAAY is always well defined, and is Maximum Likelihood Estimator (MLE) as continuous functions of MLE. They are well defined because s* and 7 are functions of entropies and of the quantities Q(P)=E: log(p:)² for a probability distribution P, which is finite event for p. = 0 because x + x log( and x + x: log(z)² are continuous at O. Contrarily to ug we do not have to use any prior to obtain well defined estimator. In addition, using the delta method the sum of entropies, for which the MLE is asymptotically normal (See [27] 3.1), shows that 7 is asymptotically normal. For more information on the estimation of entropy, mutual information or total correlation we defer to (27 26 3 6 15] to name but a few. Moreover even with the very simple MLE, we can obtain Le error upper-bounds for (P) in ([log([P)))/m
where |P| is the number of outcomes for a discrete distribution P (20). This bound depends only on the number of outcomes (supposed known), and not the actual distribution. Using the same tools, we derive a rough error bound for Q(P):
Proposition 3.4.
log log)"(n) (I(((P)-((P))) - ( (
(10)
72
Sketch of proof. We apply the methods described in (0 that bounds the bias using approximation theory for Bernstein polynomials and bounds the variance using the Efron-Stein inequality. See proof in Appendix [.6)
More efficient estimators can be created using methods of 19. nevertheless the main interest of this proposition is to show that these quantities have an error rate depending on the number of samples n, and not the number of samples per group N.. which is much better.

---

Beyond the practical use of these inequalities and approximations, these theorems also show one crucial idea; we can relate intersectional and marginal unfairness with the help of information on the independence of the protected attributes.
Refined approximations and inequalities
In the previous section, we have derived conditions for marginal unfairness to directly relate to u², and bounds on probable intersectional fairness. We now would like to propose approximation of u using similar ideas. Looking at (6). (3) and indirectly through Corollary 3.3 seems natural to propose as one possible approximation of u" the following quantity:
B
(x axs d'))- DEY k= (E.44)))
sup
sup
(1I)
For the rest of the article, we thus now only focus on s and uy. Compared with ug the estimator with Bayesian prior, it does not depend on prior parameter, and is usually well defined as we only need Na,,y the number of samples per a; and y to be strictly positive instead of all Na.g. However this estimator of u is not consistent. We will show that the previous bounds can be improved and that we can make our estimator consistent by gradually grouping together the protected attributes as the number of samples increases.
4.1 Grouping protected Attributes together
Until now, we have always decomposed the protected attributes A on their marginals A,, However it may be that we have more than just marginal information available. Take the example of 4 protected attributes A (A], A2, A3. A4). For a set t S {1, 3, 4), we define A, = (Aş) We may not have enough data to compute the full intersectional unfairness, but may be possible to compute it for the grouped protected attributes A11.2)= = (A,, A2) and A[3,4)- We can use the same decomposition as we did before on the new marginals attributes (which corresponds to flattening A and A2 together) with support A(1,2) A1 x A and A(3.4) = A3 x As.
More generally. let q be partition of {1...., d)- = [d]. For partition 9. denote A = (At) This is only a different way to group together the marginal attributes, and is the same as A. Whenever quantities are changed according to some partition q, it will be indicated with (q). For each of the new marginal attributes defined by set i of g. the new marginal unfairness u. corresponds to the intersectional unfairness of the (Ag)Ret- If the A, are independent, and independent conditionally on Y, we can apply Proposition 3.1 and obtain directly u* through the newly defined marginals. If we relax the independence conditions, the same arguments of the previous section still apply. and we can look at the bounds and upproximations defined by these new marginal densities. We denote the new approximation with partition by (q) = supyey Σie, ai) Ue ae o)) where we are using the new marginals defined by g. If we use the partition of singletons then u (4) = and if we use the trivial partition (the whole set) then u =u= The constraints of independence for these new marginals should be more feasible than the original marginals, hence it is possible that the A, fulfill the independence conditions, even the Ag do not (the trivial partition is such an example). If we have enough data to compute the marginal densities derived from 9 and the A, fulfill the independence conditions, we can then compute u² through the partition q. Of course most of the time the independence conditions are not satisfied satisfied for partition q. Nonetheless because s* measures how far we are from the independence conditions, we can more carefully select a partition among those for which we can compute the new marginal densities.
4.2 Efficient Partition Selection
Let Q be the set of all feasible partitions q. that is Q= E P((d) Vt E q. Y.y E A. x Y. Nar.y > 0} with P([d)) the set of all partitions of [d]. This set represents the set of partitions for which we can compute the newly defined marginals without having to use prior parameter. Note that Q is random set that converges to P([d) almost surely as the number of samples increases. If q' E Q, then any partitions g finer than g' (meaning that any element of q is a subset of an element of g') is in Q as well. We will say that g can be merged further if there exists partition g' Q so that g is finer than g'. Note that the choice a partition & does not change the value of u² but
only that of ( We therefore want to find good feasible partition q in Q so that can expect
7

---

heuristically ( u²I to be the lowest among the partitions. There are two criteria that should help us decide which partition E Q to choose from.
If a partition q' is coarser than
(which means that q is finer than q'), then reasonably the approximation is better with q' than q. The reasoning is that by taking coarser partitions, we are taking more interactions be- tween the protected attributes into ac- count. For example the coarsest parti- tion which is the whole set gives the interscctional unfairness as mentioned earlier. However because the 'finer- than' relationship is only partial or- der, are not able choose between any two sets. Because Theorem 3.2 seems to hint that there is relation- ship between the error Ju] -c" and the distance to the independence con- ditions 8", the second criterion will be to select the partitions q with the smallest s* (q) defined as s* but taking the marginals in g. These two criteria are closely linked. Selecting coarser partitions does tend to yield partitions with smaller s", but not always. We give some details on relationship between s" s²(g) of partition compared to a coarser one in Appendix C.2 More crucially, finding good partition with a small s* (q) will also improve our inequalities as they are a function of s* (q) which decreases on average as shown in Figure 5 as the number of sample grows (and as the partitionns get coarser).
Algorithm Greedy Partition Finder
Protected attributes data and occurrences of Y require: The partition of singletons is feasible q" < the partition of singletons
input:
repeat
.M -M=
*min <- +000
for in M do
g is feasible and s'(() (q) < min then (s q²) + (s (g)) .))
end if end for
until M = 0 or mnnn = oo (Nothing possible to merge)
return: 9²
In principle, finding the best partition according to our criteria requires enumerating all feasible partitions which is computationally intractable. Instead we propose a greedy heuristic that describe in Algorithm|] [ We start from the finest partition (the partition of singlctons), look at all the feasible partitions (with enough data) that can be obtained from merging two elements of the current partition, select the one with the smallest s", and repeat until there are no coarser partitions with enough data. Note that when we want to verify that there is enough data available, we may need to do it multiple times for the same subset of protected attributes. This is an expensive call so it is more efficient to do memoization and remember if there enough data available for given subset once encountered, which we do using a hash table to reduce the lookup time. We denote this partition q² We have the following property with the proof in Appendix C.T.
(4") is consistent estimator of u² Proposition 4.1. The estimator ut
(9") is relevant in estimating u", while not needing to use a Bayesian This proposition shows that 47 prior with parameters that may overwhelmingly affect the estimation. Note that instead of using Q which ensures that N Na.. > O, we can instead use Q, for E N which ensures that for any q 2,. Na. > t for t E g.
5 Experiments
In this section, we present experimental results that show how our inequalities and approximations perform on real and synthetic data-sets, seta, and compare their estimation eгror rates as the number of samples grow. All the code used in our experiments can be found in the supplementary material or at Fairness
5.1 Data-sets and processing
In order to compare how well ugg and u, perform as estimators on data on datasets with a high number of protected attributes, we need to compute u" which is as discussed above inherently difficult. We will always measure the unfairness with respects to the empirical distribution of the dataset. For this empirical distribution to yield well defined fairnsss measure, we need that Na,, 0 for all and This means that if we want to take into account a high number of sensitive attributes, we have to pick very large dataset.
8

---

We used US Census data from 1990 [1] which contains n= 2, 458, 285 samples, and for which we identified many potential protected attributes. We then train a Random Forest binary classifier on a poverty binary label, where we weight the labels differently so as to obtain about the same number of predictions for each outcome. However we still do not have Na. alleviate this issue, we will consider subsets of the protected attributes for which this is true, and we will measure fairness with respect to these subsets. We obtain about 100 different subsets with d = protected attributes, that we denote as D, which is the original dataset where we only kept the i-th subset of protected attributes and the predictions Y. Each of these subsets yield different values of u² and s". We pick 12 (for computational reasons) different D; with various values of u² and s*. Some examples of the final protected attributes include sex, not speaking English at home, being overweight, being Hispanic, and others. We will always take 5 0.1 when relevant.
on the whole dataset. To
We also conduct experiments on synthetic data. We generate (A, Y) probability distributions from a Dirichlet distribution, thus we can directly compute u" without dealing with very large dataset. We take 10 This synthetic data is one of the worst case for the approximation of u² with uy as the marginal distributions are a sum of 2d-1 i..d. random variables that all converges to 1/2 as d grows. We therefore will not plot 2, for the synthetic data (it is close to 0). Nonetheless, this synthetic data remains useful in order to compare the error rates between " and 8* and their respective true value. We denote by P. generated probability distribution. We generate 12 of them.
5.2 Experiments Results
We first want to compare the convergence rate of Ug. S" and U to their asymptotic value. To do that, and because they can take different values, we compute for each estimator Tn, that converges in probability to T the relative expected Lg error rate L)(T,) E T)²/T²) We fix a number of available samples n from 100 to 2, 000, and we sample without replacement from the datasets. From these available samples, we compute all our estimators. We denote by ú, the estimator of u computed with the empirical marginal densities for n samples. In order to compute I, for each subset and each sample size n, we sample from D, and P. 20 times for each fixed number of samples n..
We see in Figure on the left-most plot, that ú, is reasonably close to u² on average. Still the gap between e" and 61 is quite big. Other bounds such as 62 or with other concentration inequalities are generally a bit more efficient but still loose, nevertheless we focus here on comparing the error rates between s" and U gg- and on how 2 performs. The other two plots look the L3 for the various estimators, with the middle one being with the real datasets D., and the right on the synthetic datasets P,. We can see that 8* and ûn converges much faster than u-- Moreover, it seems that the difference in error rate will only grow bigger as d increases, as there is bigger gap for P.. We can also see that "g unreliable, because the error rate varies a lot depending on a, and can even increase. This is because the parameter a dominates the computation of ug as discussed earlier.
Relaove BFTEF
307
0.5
Mp.4 0.033
24.5: 355
Hy 3.1
29 3.02
1000
On the left-most plot, each point represents one real dataset D:, and we compare 61, c", and uy with u². The dotted line corresponds to the equation x = y for reference. The middle plot describes the average over the D; of LE as n increases for ûU s*, and ä* Un is computed for multiple values of a. The right-most plot is similar, but uses the synthetic datasets P..
Figure 1:
We now conduct similar experiments, but this time using partitions. We can see the middle plot of Figure 2 that af(") performs better. The choice of r the count threshold for grouping always gives reasonable approximations, with
being close to ug. and T big makes it close to uy. Most importantly, the apparent good error rate of u is merely an artifact of the current range of u" being above the starting values of "g for these a. clear that " is unreliable by looking at the left plot in Figure 2 the estimation with ug 2000 for different values of varies very little when

---

2" varies (it is almost not function of u²). This means that ug depends very little on the data low amount of samples. Even if not perfect, uj still has better performance and is more coherent. We note that the approximation performs well comparatively only when d is high, and considering more sensitive attributes should make an even bigger difference. These results combined
with Proposition 4.1 show that (9") is relevant estimator of u" with searce data and high number of protected attributes. Concerning s" (q") the right-most plot shows that while is not completely monotone, s" (q") does decreases average when using partitions the number of sample increases. The upper bound will become tighter as n grows, which will make bigger groupings of protected attributes possible.
10P
2.75
2.50
2.2
500
1000
1500
2000
500
1000
1500
2000
Figure 2: Each point of the same color and shape represent the estimation for one dataset D.. The estimations computed for 2000. The middle plot is the as above, but with af?" this time. The rightmost plot is the average evolution of s* (q²) for T = 10 as n. increases.
Discussion
In this work, we presented new methods to approximate and to bound (in high probability) a strong intersectional unfairness measure, based statistical information computable from reasonable dataset. Our results highlight the key role independence of the protected attributes conditionally the classifier, and propose to approach it via a smart grouping of some attributes-wii theoretical bound allows us to compute via an efficient heuristic.
Our experiments show that the approximations proposed here perform reasonably well for data-sets with high number protected attributes, but that our bounds are not very effective. However their main interest is that it gives insight into the link between marginal and intersectional fairesss, which was main goal of this work. also helps us derive the proposed approximation. We expect that more effective bounds could be derived for our notion of probabilistic fairness, for instance by making additional ussumptions on the distribution, but presumably without an explicit dependence on independence measures and marginal densities, making the link between marginal and intersectional fairness harder to see.
In order to train fair models using the proposed approximations bounds of this paper, we can use soft counts to compute the empirical densities (based the classifier score for instance) as suggested in [14]. This makes the approximations and bounds differentiable, and ensure that we can apply gradient based methods so as solve a constrained or penalized optimization problem using these quantities.
We hope that our approach will enable the development of improved bounds, raise interest in the proposed notion of probabilistic unfairness which we think is crucial to the development of fair algorithms, as well as the use of our approximations to penalize classifiers in order to train intersectionally fair classifiers.
Acknowledgments
This work has been partially supported by MIAI @ Grenoble Alpes (ANR-19- P3IA-0003), by the French National Research Agency (ANR) through grant ANR-20-CE23-0000 and by TAILOR (a project funded by EU Horizon 2020 research and innovation programme under GA No 952215). The authors are hosted at the CREST lab (CNRS, GENES, Ecole Polytechnique, Institut Polytechnique de Paris).
10

---

References
[1] Equal Credit Opportunity Act, 1974.
[2] Code du Travail. Chapitre II: Principe de con-dscrimination, 2020.
[3] Evan Archer, II Memming Park, and Jonathan W. Pillow. Bayesian entropy estimation for countable discrete distributions. Journal of Machine Learning Research, 15(1):2833-2868, 2014.
[4] Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning. fairml- book.org, 2019. httt::/www.fairee fai.://wwwaaaammmmmmmma..m... book.oro.... org
[5] Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in com- mercial gender classification. In Proceedings of the 1st Conference on Fairness, Accountability and Transparency (FAT*), volume 81, pages 77-91, 2018.
[6] Pengyu Cheng, Weituo Hao, and Lawrence Carin. Estimating total correlation with mutual information bounds. Available as arXiv:201 1.04794, 2020.
[7] Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data, 5 2: 153-163, 2017.
[8] Kimberle Crenshaw. Demarginalizing the intersection of race and sex: A black feminist critique of antidiserimination doctrine, feminist theory and antiracist policies. University of Chicago Legal Forum, 1989(1): 11:919999911 1989.
[9] A. Dembo and O. Zeitouni. Large Deviations Techniques and Applications. Stochastic Mod- elling and Applied Probability. Springer Berlin Heidelberg, 2009.
[10] Emily Diana, Wesley Gill, Michael Kearns, Krishnaram Kenthapadi, and Aaron Roth. Minimax group fairness: Algorithms and experiments. In Proceedings of the 2021 AAAI/ACM Conference on Al, Ethics, and Society (AIES), page 66-76, 2021.
[11] Dheeru Dua and Casey Graff. UCI machine learning repository. 2017.
[12] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS), page 214-226, 2012.
[13] James R. Foulds, Rashidul Islam, Kamrun Keya, and Shimei Pan. Bayesian modeling of inter- sectional fairness: The variance of bias. In Proceedings of the SIAM International Conference on Data Mining (SDM), 2020.
[14] James R. Foulds, Rashidul Islam, Kamrun Naher Keya, and Shimei Pan. An intersectional definition of fairness. In Proceedings of the 2020 IEEE 36th International Conference on Data Engineering (ICDE), pages 1918-1921 2020.
[15] Yanjun Han, Jiantao Jiao, and Tsachy Weissman, Minimax estimation of divergences between discrete distributions. IEEE Journal on Selected Areas in Information Theory, 1(3):814-823, 2020.
[16] Moritz Hardt, Eric Price, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Proceedings of the Thirtieth Conference on Neural Information Processing Systems (NeurIPS), 2016.
[17] Ursula JohnrttJohnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibra- tion: Calibration for the Coomputaiioaally-ienniiii International Conference on Machine Learning (ICML), pages 1939-192 1948, 2018
masses. In Proceedings of the 35th
[18] Disi Ji, Padhraic Smyth, and Mark Steyvers. Can trust my fairness metric? assessing fairness with unlabeled data and bayesian inference. Proceedings of the Thirty-fourte Conference on Neural Information Processing Systems (NeurIPS), pages 18600-18612, 2020.
11

---

[19] Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman. Minimax estimation of functionals of discrete distributions. IEEE Trans. Inf. Theor. 61(5):2835-28855 2015.
[20] Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman. Maximum likelihood estimation of functionals of discrete distributions. IEEE Transactions on Information Theory, 63(10);6774- 6798, 2017.
[21] Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing faimess gerryman- dering: Auditing and learning for subgroup fairesss. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 2564-2572, 2018.
[22] Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. An empirical study of rich subgroup fairness for machine learning. In Proceedings of the Conference on Fairness, Accountability, and Transparency (FAT*), page 100-109, 2019.
[23] Elena Kosygina. Introductory examples and definitions. cramér's s theorem, 2018. https wawae/effddddaaaaaaaaaaaaaa auffing/SNAf Citila//Notss.p..e
//sites meites.math......
wwt.sa.att.......aaaeeeme www.twwwterrnn.ommmmoo edu/ hatpeeootttetteeeeeeeeeaaaaaaa
[24] Natalia Martinez, Martin Bertran, and Guillermo Sapiro. Minimax pareto fairesss: A multi objective perspective. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 6755-6764, 2020.
[25] Jeremie Mary, Clément Calauzènes, and Noureddine El Karoui. Fairness-aware learning for continuous attributes and treatments. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 4382-4391, 2019..
[26] Ilya Nemenman, F. Shafee, and William Bialek. Entropy and inference, revisited. In Proceedings of the Conference on Neural Information Processing Systems (NIPS), 2001.
[27] Liam Paninski. Estimation of entropy and mutual information. In Neural Computation, volume 15, pages 1191-1253, 2003.
[28] Yaniv Romano, Stephen Bates, and Emmanuel Candes. Achieving equalized odds by resampling sensitive attributes. In Proceedings of the Thirty-fourth Conference on Neural Information Processing Systems (NeurIPS), pages 361-371, 2020.
[29] Satosi Watanabe. Information theoretical analysis of multivariate correlation. In IBM Journal of Research and Development, volume 4, pages 66-82, 1960.
[30] Blake Woodworth, Suriya Gunasekar, Mesrob I. Ohannessian, and Nathan Srebro. Learning non non-diseriminatory predictors. Proceedings of the 2017 Conference on Learning Theory (COLT), pages 1920-1953, 2017.
[31] Forest Yang, Mouhamadou Cisse, and Sanmi Koyejo. Fairness with overlapping groups; probabilistic perspective. In Proceedings of the Thirty-fourth Conference on Neural Information Processing Systems (NeurIPS), pages 4067-4078, 2020.
[32] Ke Yang, Joshua R. Loftus, and Julia Stoyanovich. Causal Intersectionality and Fair Ranking. In Proceedings of the 2nd Symposium on Foundations of Responsible Computing (FORC), pages 7:1-7:20, 2021.
[33] Muhammad B. Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna Gummadi. Fair- ness Constraints: Mechanisms for Fair Classification. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 070.970, 2017.
[34] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P. Gummadi. Fairness beyond disparate treatment & disparate impact: Learning classification without dis- parate mistreatment. In Proceedings of the 26th International Conference on World Wide Web (WWW), page 1171-1180, 2017.
[35] Yiliang Zhang and Qi Long. Assessing faimess in the presence of missing data. In Proceedings of the Thirty-fftth Conference on Neural Information Processing Systems (NeurIPS), pages 16019 2021.
12


Reviews:
[{"review_id": "vXYLraq7mSt", "reviewer": "Reviewer_U9ky", "summary": "This paper studies how to estimate intersectional fairness when there are a large number of protected attribute combinations. The paper first show that if the protected attributes are mutually independent and mutually independent conditionally on the prediction, the intersectional fairness can be easily computed from the marginal fairness. Then, the paper relaxes the independent assumptions and provides bounds on probable intersectional fairness. After that, the paper offers a bound directly on the intersectional fairness. The idea is to find a partition in order to get closer to the independence conditions so that the intersectional fairness computed under the independence assumptions could be a good approximation. Experiments using real-world and synthetic data show that the proposed bounds are more reliable than the Bayesian estimator.", "questions": "1.\tAre u^q_ind upper bounds or lower bounds? Or both cases are possible? In that case, why is u_ind in Figure 1 constantly smaller than u*?\n\n2.\tAre epsion_1 and epsilon’_1 upper bounds? What is epsilon* in Figure 1? Any explanation of why epsilon* is smaller than u*?\n\n3.\tThe authors said that the proposed approach will enable the use of the approximations to penalize classifiers in order to train intersectionally fair classifiers. Is that possible to include some discussions about the differentiability of the proposed method that is necessary for the approximations to be integrated into gradient-based optimization? \n", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\nThis paper systematically studies the bounding and approximating of intersectional fairness through marginal fairness. It provides a sufficient condition for accurately computing intersectional fairness from marginal fairness. Then, it provides both probabilistic bounds and hard approximations of the intersectional fairness, which are easily computable from the data. \n\nWeakness\n\nThe paper does not provide a convincing example showing why ensuring intersectional fairness for a very large number of subgroups (e.g., 100 subgroups) is a meaningful and practical requirement for decision-makers. Although this paper studies the measurement of fairness not the achievement of fairness, the measurement is meaningful only when we have the requirement to achieve fairness.\n\nThere are too many notations, which make the paper difficult to follow.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VfezjyGm18U", "reviewer": "Reviewer_xViZ", "summary": "The paper aims at the task of bounding and approximating intersectional fairness, with a main motivation of cases where multiple protected attributes exist, and a finite training from which such approximation of the statistical fairness criterion could be difficult due to scarcity of datapoints for marginal subsets which are the intersections of such variable values. The paper establishes theoretical bounds, connecting marginal fairness (for varying, single, protected attributes) and intersectional fairness, by using a measure of total correlation. Namely, the idea is to bound how far the product of the marginal measures is from being independent (across the different protected attributes), and use the bound to upper bound the intersectional measure. The paper establishes these bounds as a function of the mutual information between the made predictions and the protected attributes, and as a function of the standard deviation of the total correlation measures. The bounds serve as an inspiration then for a proposed heuristic approach for estimating the intersectional fairness, which is based on greedy selection of groupings of protected attributes, which minimize the distance from independence using the bounds, allowing for better estimation. The paper ends with an evaluation of the proposed scheme on US census data from 1990, as well as on synthetic data.", "questions": "1. In Theorem 3.2, for the bound on \\eps_1^', inside the log parantheses, what are the variables for which the probabilities are taken?\n\n2. I wonder, how effective are the established upper bounds in terms of bounding the intersectional fairness from a finite sample? There is no illustration or provided examples which could be helpful in assessing the significance of such bounds in practice. Should we only expect the upper bounds to be meaningful when protected attributes are very close to being independent?", "limitations": "1. There is no discussion of the limitations of the work in the main body of the paper. I would expect to see a more elaborate one in the summary.\n\n2. Effectiveness of theoretical bounds - please see in the \"questions\" section.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality:\nStrengths:\n1. The theoretical bounds, connecting intersectional fairness to marginal fairness, decomposing the problem in terms of the dependence between the protected attribute are interesting, and give conceptual insight, as well as estimation (upper) bounds that rely only on the total number of samples (not the marginal).\n2. The proposed attribute grouping-based heuristic compares favorably with prior work (using a Dirichlet prior).\n\nQuality:\nThe results in the paper seem to be well supported, though I have only glanced at the appendix. The relevant related work is mentioned, and code is attached in the supplementary file.\n\nClarity:\nThe paper is mostly well-written. The experiments section, and the description of the results were a bit difficult to interpret and could be improved.\n\nSignificance:\nStrengths:\nThe problem in question is highly motivated. The ability to give reliable statistical estimation of intersectional fairness with finite data is important and could have practical implications. The proposed greedy heuristic based algorithm of grouping seems to compare favorably with formerly proposed methods.\n\nWeaknesses:\nIt is, however, still not completely clear to me how useful are the established upper bounds in practical scenarios. Please see \"questions\" section of my review.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0i5V83fGYvf", "reviewer": "Reviewer_WyGu", "summary": "This paper presents new methods to approximate and bound intersectional unfairness. Intersectional fairness is connected with marginal fairness with the mutual independence and conditional independence of protected attributes given predictions. Then the dependence conditions are relaxed via the quantification of total correlations and their variance. A grouping technique is provided to relax the mutual independence of A to the dependence of groups of A. The experiments compare the approximation gaps and show the effectiveness of proposed approximations.", "questions": "NA", "limitations": "- The motivation is very clear. But there are too many uncertainties between u* and u_{ind}. The major concern is that the relationship between u* and u_{ind} is unclear to me in general.\n\n- The work would be complete if it shows how the approximation is used for intersectional unfairness elimination.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The motivation is simple and clear.\n- The proposed approximation connects intersectional farness and marginal fairness through independence. The new approximation and relaxed version are easy to calculate with known techniques.\n- The grouping technique shows another relaxation direction.\n\n--- \n- The mutual independence and conditional independence imply no more than one protected attribute is correlated with Y. Let one start with A={A_1, A_2, ... A_d} and let \\hat{Y} = f(A_1, A_2, ... A_d, X). The graphical representation is A1, A2, ... A_d, X -> Y. Given A are mutually independent and the definition of d-separation, the protected attributes cannot be conditionally independent. In another word, mutual independence, conditional independence, and \\hat{Y} = f(A_1, A_2,... A_d, X) cannot be achieved simultaneously. Theorem 3.1 & 3.2, as well as u_{ind}, are based on this independence assumption. It is unclear whether they are affected by the prediction function \\hat{Y} = f(A_1, A_2,... A_d, X).  A straightforward impact I see is s^* cannot be zero unless no more than one protected attribute is used for prediction.\n\n- Thm 3.2 connects u* with an upper bound containing u_{ind}. There is an intuitive relationship between u* and u_{ind}, but it is unclear why it seems **natural** to propose u_{ind} as a good approximation in theory. In another word, the relationship between u* and u_{ind} is unclear in general settings.\n\n- Sec 4.2 and Algorithm 1: it is unclear why small s^* leads to small |u^q_{ind} - u^*|. Given that \\epsilon_1 is an upper bound of u*, the relationships between u_{ind}, s^* and u* are still unclear.\n\n- The notations are really difficult to follow. I suggest the authors revise the notations and fix typos, e.g. u_k(y, a, a') in Eq (6), A_i in Eq (25).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept