Bounding and Approximating Intersectional Fairness through Marginal Fairness

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., . Such notions define demographic groups based on so-called protected attributes (e.g., gender, race, religion), and impose that some statistical quantity be 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 or calibration by group —see a survey in . As exact fairness is too constraining, one often measures unfairness, which roughly quantifies the distance to the fairness constraint.

Most works on fair classification consider a single protected attribute and hence only two (or a small number of) groups. Then, they use measures of unfairness to 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 at hand. With only a few groups, this assumption is indeed easily satisfied as there are sufficiently many data points for each group.

In many—if not most—real-world applications, there are multiple protected attributes (typically 10-20) along which discrimination is prohibited . It is then desirable to consider the strong notion of intersectional fairness, which roughly specifies that no subgroup (defined by an arbitrary combination of protected attributes) is unfavorably treated. In that case, however, estimating the unfairness measure becomes very challenging: as the number of groups is exponentially large (e.g., $2^{10}$ for 10 binary protected attributes), it is very likely that the dataset has at least one subgroup 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 real-world and algorithmic examples that it is not sufficient to ensure intersectional fairness . 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. 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 it allows a very high unfairness for tiny subgroups—which is contradictory to the intuitively desired behavior.

makes a similar assumption by considering only subgroups above a minimum size, which eases estimate generalization. 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. 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 fairness more finely.

Contributions: We identify sufficient conditions under which intersectional fairness can be exactly derived from marginal densities, which clarifies when marginal unfairness is a 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, our work is the first work to exploit statistical information to better understand and estimate intersectional (un)fairness. Our work is fairly general and can be instantiated for a 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.

Further Related Works: proposes a unified framework to train a fair classifier under intersectional 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 or when there are unlabeled examples . Others tackle the problem of intersectionality beyond group fairness, e.g., considers causal intersectional fairness. Finally there has been some interest in a different formulation of intersectional group fairness as a multi-objective optimization problem where each objective is the discrimination faced by a given protected group. Another interesting approach to fairness is individual fairness developed in , however this is quite different from group fairness metrics on which we focus on and our techniques do not apply.

Setting and Models

Notational convention: Wherever useful, for any two random variables $V$ and $W$, we will use the short-hand $p_{V}(v)\!=\!\Pr(V\!=\!v)$, $p_{V,W}(v,w)\!=\!\Pr(V\!=\!v,W\!=\!w)$ and $p_{V\mid W}(v\mid w)\!=\!\Pr(V\!=\!v\mid W\!=\!w)$.

Consider a multi-class classification task. A given individual is described by a tuple of random variables $(X,A,Y)$ drawn according to a distribution $\mathcal{D}$ where $X$ is the features vector, $Y$ is the label with values in $\mathcal{Y}$, and $A=(A_{1},...,A_{d})$ is a $d$-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 a part of $X$. We denote the support of $X$, $Y$, $A$ and $A_{k}$ for $1\leq k\leq d$, by $\mathcal{X}$, $\mathcal{Y}$, $\mathcal{A}$ and $\mathcal{A}_{k}$ respectively. We assume that $\mathcal{A}$ is finite (hence discrete). For a deterministic classifier $h$, $\hat{Y}=h(X)$ is the predicted class for a random individual. The classifier $h$ is fixed, as we are interested in measuring its fairness and not finding a fair classifier.

To compare the discrimination between groups, we consider a second random variable $A^{\prime}$ such that $(A^{\prime}\mid\hat{Y})$ is independent and identically distributed (i.i.d.) to $(A\mid\hat{Y})$. Some authors look at the difference in the treatment of protected groups as a ratio , and some others as a difference . 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 fairness metrics can be either derived directly or adapted using the methods developed in this paper (see Appendix A.1). We define our measure of unfairness as follows:

For a distribution $\mathcal{D}$ and a classifier $h$, we define the intersectional unfairness and the $k^{th}$ protected attribute marginal unfairness as:

One could think that if the marginal unfairness of each protected attribute is smaller than some $\epsilon>0$, then the overall unfairness is smaller than $\epsilon$; measuring $\operatorname{u^{M}}\!=\!\sup_{k}u^{\ast}_{k}$ corresponds to this idea. As stated in the introduction this is not sufficient to describe unfairness and we can still have $u^{\ast}\!>\!\operatorname{u^{M}}$. We can rewrite (1) as $u^{\ast}\!=\!\sup_{\mathcal{Y}}\!\log(\sup_{\mathcal{A}}p_{\hat{Y}\mid A}/\inf_{\mathcal{A}}p_{\hat{Y}\mid A})$, and similarly for $u^{\ast}_{k}$. This means that to measure unfairness we only need to analyze the function $p_{\hat{Y}\mid A}$.

2 Estimation of Unfairness

Nonetheless, $u_{B}$ 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 $\alpha$ and cannot be trusted. If $N_{a}\!=\!0$ for a protected group $a$, the estimated distribution is uniform on $\hat{Y}\mid 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 an important error on the estimation. When $N_{a}$ increases, we gain more information on the distribution of $\hat{Y}\mid A$. However, when $N_{a}$ is still low for all groups, the estimated distribution of the $\inf$ of $\hat{Y}\mid A\!=\!a$ is almost entirely determined by the prior parameter $\alpha$.

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 fairness? It could be argued that an algorithm which discriminates $1$ 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 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 unfairness probabilistically in $(\hat{Y},A,A^{\prime})$. To do that we define the random unfairness $U\!=\!u(\hat{Y},A,A^{\prime})$ the random variable which corresponds to randomly choosing a prediction, and then independently selecting two protected groups according to $p_{A\mid\hat{Y}}$ to compare them. We now define our notion of probabilistic unfairness:

For $\epsilon\geq 0$ and $\delta\in$, we say that classifier $h$ over distribution $\mathcal{D}$ is $(\epsilon,\delta)$-probably intersectionally fair if $\Pr(U>\epsilon)\leq\delta$.

Probabilistic fairness can be especially relevant in the context where $A$ are continuous sensitive attributes. Indeed, even for a very basic multivariate normal distribution on $A$, we will end up with $u^{\ast}\!=\!\infty$ which is unhelpful. Yet by considering this notion of probabilistic fairness we 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.

Measures of Independence and Theoretical Bounds

We now focus on providing valid $(\epsilon,\delta)$ couples for probable intersectional fairness. First note that while the intersectional unfairness $u^{\ast}$ is hard to estimate, it is much easier to estimate the marginal unfairness $\operatorname{u^{M}}$. The work done by in the different setting of weighted unfairness, however, shows through experiments that across multiple classifiers and data-sets, $u^{\ast}$ and $\operatorname{u^{M}}$ can be uncorrelated, correlated, or even equal. Building on this observation, we would like to approach $u^{\ast}$ using marginal quantities estimable for reasonably-sized data-sets.

Since the intersectional unfairness takes into account the interactions between all the protected attributes $A_{k}$, one could guess that if the $A_{k}$ are mutually independent, this implies that $u^{\ast}$ is close to $\operatorname{u^{M}}$. 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 $A_{k}$, there can be interaction between those protected attributes through the classifier. See Appendix B.1 for a counter example with the independence of the $A_{k}$ only but no clear relationship between marginal and intersectional fairness.

If the protected attributes $A_{k}$ are mutually independent and mutually independent conditionally on $\hat{Y}$, then

The main idea is to decompose $p_{A}$ and $p_{A\mid\hat{Y}}$ as their products of marginals using the independence assumptions, and using the fact that the $\sup$ taken over a product of functions with independent variables is distributed over the product. The inequality is obtained because the $\sup$ of a 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^{\ast}$ becomes easy to estimate. What we provide here are conditions and a equation to derive a direct relationship between the intersectional unfairness and the marginal unfairness of each $A_{k}$. 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-section. We would like to relax the independence criteria while still using marginal information from the problem.

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 $\prod_{k=1}^{d}\Pr(A_{k}\!=\!a_{k})$. We will use one of the possible multivariable generalization of Mutual Information known as Total Correlation :

For $\delta\in(0,1]$, any classifier $h$ over a distribution $\mathcal{D}$ is $(\epsilon_{1},\delta)$ and $(\epsilon_{2},\delta)$-probably intersectionally fair with

We apply Chebyshev’s inequality to $L$ and $L_{y}$ for some introduced parameters $\boldsymbol{\alpha}$ to bound the tails of these random variables, while making sure that overall the probability bounds stay larger than $1-\delta$. We can then compute inequalities on $p_{A}$ and $p_{A\mid\hat{Y}}$, and take the $\inf$ for $a$ and $\sup$ for $\boldsymbol{\alpha}$. This leads to a constrained minimization problem that can be solved, which yields $s^{\ast}$. The full proof is in Appendix B.3. For $\epsilon_{2}$ we additionally use that $p_{\hat{Y}\mid A}\leq 1$ as $\mathcal{Y}$ is discrete. ∎

We observe that both $\epsilon_{1}$ and $\epsilon_{2}$ are composed of one term in $s^{\ast}$ related with the $\delta$-confidence, and a quantity with marginal information. Aditionnaly $\epsilon_{2}$ also includes a term in $\gamma$ that corresponds to some form of mutual information correction. We can control the confidence in this bound with the parameter $\delta$. Because $s^{\ast}\!=\!0$ if and only if $\sigma\!=\!\sigma_{y}\!=\!0$ and combined with (5) we can see that $s^{\ast}$ somewhat measures how far we are from the conditions of Proposition 3.1. With $\epsilon_{1}$ 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 to estimate in addition to having to solve a non-convex optimization problem, see Appendix B.4.

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:

Denoting $(\Omega,\mathcal{T},\Pr)$ the probability space on which $(\hat{Y},A,A^{\prime})$ is defined, there exists an event $F$ so that for $f(y,a)=\prod_{k=1}^{d}(p_{\hat{Y}\mid A_{k}}(y\mid a_{k})/p_{\hat{Y}}(y))$ we have for $U$ the random unfairness:

The proof can be found in Appendix B.3. This means that there is a fraction of the relevant pairs population of size bigger than $1-\delta$, for which we can give an interval for the maximum random unfairness over this fraction $F$. This interval is centered and reduce around a unique quantity as $s^{\ast}$ goes to , with $s^{\ast}$ and $\delta$ determining the length of this interval. When $\delta$ goes to , we have $\Pr(F)\rightarrow 1$ hence $\sup_{\omega\in F}U(\omega)\rightarrow u^{\ast}$ because we are dealing with finite random variables. Notice also that when both $\delta$ and $s^{\ast}$ go to , we recover Proposition 3.1 as $\sup_{\omega\in F}|\log(f(\hat{Y},A^{\prime})/f(\hat{Y},A))(\omega)|$ goes toward the quantity derived in this Proposition when $\delta$ goes to .

3 Estimation of the measures of independence

Theorem 3.2 trades the precise estimation of $u^{\ast}$ with an upper bound, but with much easier quantities to estimate. More specifically, as they are information measures, we can leverage the extensive literature on statistical estimators and entropy estimation. We can intuitively see that the estimation of $s^{\ast}$ and $\gamma$ will be easier to handle because even the estimation with the empirical distribution $\hat{p}_{A,\hat{Y}}$ is always well defined, and is a Maximum Likelihood Estimator (MLE) as continuous functions of MLE. They are well defined because $s^{\ast}$ and $\gamma$ are functions of entropies and of the quantities $Q(P)\!=\!\sum_{i}p_{i}\log(p_{i})^{2}$ for a probability distribution $P$, which is finite event for $p_{i}\!=\!0$ because $x\mapsto x\log(x)$ and $x\mapsto x\log(x)^{2}$ are continuous at . Contrarily to $u_{B}$ we do not have to use any prior to obtain a well defined estimator. In addition, using the delta method on the sum of entropies, for which the MLE is asymptotically normal (See 3.1), shows that $\hat{\gamma}$ is asymptotically normal.

For more information on the estimation of entropy, mutual information or total correlation we defer to to name but a few. Moreover even with the very simple MLE, we can obtain $L_{2}$ error upper-bounds for $H(P)$ in $\mathcal{O}(\log(|P|)^{2}/n)$ where $|P|$ is the number of outcomes for a discrete distribution $P$ . 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)$:

We apply the methods described in that bounds the bias using approximation theory for Bernstein polynomials and bounds the variance using the Efron-Stein inequality. See proof in Appendix B.6. ∎

More efficient estimators can be created using methods of , 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_{a}$, 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^{\ast}$, and bounds on probable intersectional fairness. We now would like to propose an approximation of $u^{\ast}$ using similar ideas. Looking at (6), (3), and indirectly through Corollary 3.3 it seems natural to propose as one possible approximation of $u^{\ast}$ the following quantity:

For the rest of the article, we thus now only focus on $s^{\ast}$ and $u_{I}$. Compared with $u_{B}$ the estimator with Bayesian prior, it does not depend on a prior parameter, and is usually well defined as we only need $N_{a_{i},y}$ the number of samples per $a_{i}$ and $y$ to be strictly positive instead of all $N_{a,y}$. However this estimator of $u^{\ast}$ 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.

Until now, we have always decomposed the protected attributes $A$ on their marginals $A_{i}$. However it may be that we have more than just marginal information available. Take the example of 4 protected attributes $A\!=\!(A_{1},A_{2},A_{3},A_{4})$. For a set $t\subseteq\{1,2,3,4\}$, we define $A_{t}\!=\!(A_{k})_{k\in t}$. We may not have enough data to compute the full intersectional unfairness, but it may be possible to compute it for the grouped protected attributes $A_{\{1,2\}}\!=\!(A_{1},A_{2})$ and $A_{\{3,4\}}$. We can use the same decomposition as we did before on the new marginals attributes (which corresponds to flattening $A_{1}$ and $A_{2}$ together) with support $\mathcal{A}_{\{1,2\}}\!=\!\mathcal{A}_{1}\times\mathcal{A}_{2}$ and $\mathcal{A}_{\{3,4\}}\!=\!\mathcal{A}_{3}\times\mathcal{A}_{4}$.

More generally, let $q$ be a partition of $\{1,...,d\}\!=\![d]$. For a partition $q$, we denote $A^{(q)}\!=\!(A_{t})_{t\in q}$. 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 a set $t$ of $q$, the new marginal unfairness $u^{\ast}_{t}$ corresponds to the intersectional unfairness of the $(A_{k})_{k\in t}$. If the $A_{t}$ are independent, and independent conditionally on $\hat{Y}$, we can apply Proposition 3.1 and obtain directly $u^{\ast}$ 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 approximations defined by these new marginal densities. We denote the new approximation with partition $q$ by $u_{I}^{(q)}\!=\!\sup_{y\in\mathcal{Y}}\sum_{t\in q}\sup_{(a_{t},a_{t}^{\prime})\in\mathcal{A}_{t}^{2}}u_{t}(y,a_{t},a_{t}^{\prime})$ where we are using the new marginals defined by $q$. If we use the partition $q$ of singletons then $u_{I}^{(q)}\!=\!u_{I}$, and if we use the trivial partition (the whole set) then $u_{I}^{(q)}\!=\!u^{\ast}$. The constraints of independence for these new marginals should be more feasible than the original marginals, hence it is possible that the $A_{t}$ fulfill the independence conditions, even if the $A_{k}$ do not (the trivial partition is such an example). If we have enough data to compute the marginal densities derived from $q$ and the $A_{t}$ fulfill the independence conditions, we can then compute $u^{\ast}$ through the partition $q$. Of course most of the time the independence conditions are not satisfied satisfied for a partition $q$. Nonetheless because $s^{\ast}$ 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.

2 Efficient Partition Selection

Let $\mathcal{Q}$ be the set of all feasible partitions $q$, that is $\mathcal{Q}\!=\!\{q\in\mathcal{P}([d])\!\mid\!\forall t\in q,\forall(a_{t},y)\in\mathcal{A}_{t}\times\mathcal{Y},N_{a_{t},y}>0\}$ with $\mathcal{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 a prior parameter. Note that $\mathcal{Q}$ is a random set that converges to $\mathcal{P}([d])$ almost surely as the number of samples $n$ increases. If $q^{\prime}\in\mathcal{Q}$, then any partitions $q$ finer than $q^{\prime}$ (meaning that any element of $q$ is a subset of an element of $q^{\prime}$) is in $\mathcal{Q}$ as well. We will say that $q$ can be merged further if there exists a partition $q^{\prime}\in\mathcal{Q}$ so that $q$ is finer than $q^{\prime}$. Note that the choice of a partition $q$ does not change the value of $u^{\ast}$ but only that of $u_{I}^{(q)}$. We therefore want to find a good feasible partition $q$ in $\mathcal{Q}$ so that we can expect heuristically $|u_{I}^{(q)}-u^{\ast}|$ to be the lowest among the partitions. There are two criteria that should help us decide which partition $q\in\mathcal{Q}$ to choose from.

If a partition $q^{\prime}$ is coarser than $q$ (which means that $q$ is finer than $q^{\prime}$), then reasonably the approximation is better with $q^{\prime}$ than $q$. The reasoning is that by taking coarser partitions, we are taking more interactions between the protected attributes into account. For example the coarsest partition which is the whole set gives us the intersectional unfairness as mentioned earlier. However because the ‘finer-than’ relationship is only a partial order, we are not able to choose between any two sets. Because Theorem 3.2 seems to hint that there is a relationship between the error $|u_{I}^{(q)}-u^{\ast}|$, and the distance to the independence conditions $s^{\ast}$, the second criterion will be to select the partitions $q$ with the smallest $s^{\ast}(q)$ defined as $s^{\ast}$ but taking the marginals in $q$. These two criteria are closely linked. Selecting coarser partitions does tend to yield partitions with smaller $s^{\ast}$, but not always. We give some details on relationship between $s^{\ast}(q)$ of a partition $q$ compared to a coarser one in Appendix C.2. More crucially, finding a good partition with a small $s^{\ast}(q)$ will also improve our inequalities as they are a function of $s^{\ast}(q)$ which decreases on average as shown in Figure 5 as the number of sample grows (and as the partitions get coarser).

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 we describe in Algorithm 1. We start from the finest partition (the partition of singletons), 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^{\ast}$, 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 is enough data available for a 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.1:

The estimator $u_{I}^{(q^{*})}$ is a consistent estimator of $u^{\ast}$.

Experiments

In this section, we present experimental results that show how our inequalities and approximations perform on real and synthetic data-sets, and compare their estimation error rates as the number of samples grow. All the code used in our experiments can be found in the supplementary material or at https://github.com/mathieu-molina/BoundApproxInterMargFairness.

In order to compare how well $u_{B}$ and $u_{I}$ perform as estimators on data on datasets with a high number of protected attributes, we need to compute $u^{\ast}$ 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 a well defined fairness measure, we need that $N_{a,y}>0$ for all $a$ and $y$.

This means that if we want to take into account a high number of sensitive attributes, we have to pick a very large dataset.

We used US Census data from 1990 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 $N_{a,y}>0$ on the whole dataset. To 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=8$ protected attributes, that we denote as $D_{i}$ which is the original dataset where we only kept the $i$-th subset of protected attributes and the predictions $\hat{Y}$. Each of these subsets yield different values of $u^{\ast}$ and $s^{\ast}$. We pick $12$ (for computational reasons) different $D_{i}$ with various values of $u^{\ast}$ and $s^{\ast}$. Some examples of the final protected attributes include sex, not speaking English at home, being overweight, being Hispanic, and others. We will always take $\delta\!=\!0.1$ when relevant.

We also conduct experiments on synthetic data. We generate $(A,\hat{Y})$ probability distributions from a Dirichlet distribution, thus we can directly compute $u^{\ast}$ without dealing with a very large dataset. We take $d\!=\!10$. This synthetic data is one of the worst case for the approximation of $u^{\ast}$ with $u_{I}$, as the marginal distributions are a sum of $2^{d-1}$ i.i.d. random variables that all converges to $1/2$ as $d$ grows. We therefore will not plot $u_{I}$ for the synthetic data (it is close to ). Nonetheless, this synthetic data remains useful in order to compare the error rates between $u_{B}$ and $\hat{s}^{*}$ and their respective true value. We denote by $P_{i}$ a generated probability distribution. We generate $12$ of them.

2 Experiments Results

We see in Figure 1 on the left-most plot, that $\hat{u}_{I}$ is reasonably close to $u^{\ast}$ on average. Still the gap between $\epsilon^{*}$ and $\epsilon_{1}$ is quite big. Other bounds such as $\epsilon_{2}$ 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^{\ast}$ and $u_{B}$, and on how $u_{I}$ performs. The other two plots look at the $L_{2}^{r}$ for the various estimators, with the middle one being with the real datasets $D_{i}$, and the right on the synthetic datasets $P_{i}$. We can see that $\hat{s}^{*}$ and $\hat{u}_{I}$ converges much faster than $u_{B}$. Moreover, it seems that the difference in error rate will only grow bigger as $d$ increases, as there is a bigger gap for $P_{i}$. We can also see that $u_{B}$ is unreliable, because the error rate varies a lot depending on $\alpha$, and can even increase. This is because the parameter $\alpha$ dominates the computation of $u_{B}$ as discussed earlier.

We now conduct similar experiments, but this time using partitions. We can see in the middle plot of Figure 2 that $\hat{u}_{I}^{(q^{*})}$ performs better. The choice of $\tau$ the count threshold for grouping always gives reasonable approximations, with $\tau\!=\!1$ being close to $u_{B}$, and $\tau$ big makes it close to $u_{I}$. Most importantly, the apparent good error rate of $u_{B}$ is merely an artifact of the current range of $u^{\ast}$ being above the starting values of $u_{B}$ for these $\alpha$. It is clear that $u_{B}$ is unreliable by looking at the left plot in Figure 2: the estimation with $u_{B}$ at $n=2000$ for different values of $\alpha$ varies very little when $u^{\ast}$ varies (it is almost not a function of $u^{\ast}$). This means that $u_{B}$ depends very little on the data for low amount of samples. Even if it is not perfect, $u_{I}^{(q^{*})}$ 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 $u_{I}^{(q^{*})}$ is a relevant estimator of $u^{\ast}$ with scarce data and high number of protected attributes. Concerning $s^{\ast}(q^{*})$ the right-most plot shows that while it is not completely monotone, $s^{\ast}(q^{*})$ does decreases on average when using partitions as the number of sample increases. The upper bound will become tighter as $n$ grows, which will make bigger groupings of protected attributes possible.

Discussion

In this work, we presented new methods to approximate and to bound (in high probability) a strong intersectional unfairness measure, based on statistical information computable from a reasonable dataset. Our results highlight the key role of independence of the protected attributes conditionally to the classifier, and propose to approach it via a smart grouping of some attributes—which our 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 a high number of 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 fairness, which was the main goal of this work. It 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 assumptions 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 or bounds of this paper, we can use soft counts to compute the empirical densities (based on the classifier score for instance) as suggested in . This makes the approximations and bounds differentiable, and ensure that we can apply gradient based methods so as to 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-0007, 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).

References

Checklist

Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? [Yes]

Did you describe the limitations of your work? [Yes]

Did you discuss any potential negative societal impacts of your work? [Yes] This work is specifically related to Fairness, and as such we highlight in the Introduction existing works which already discuss some of the societal issues that intersectional fairness raises.

Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]

If you are including theoretical results…

Did you state the full set of assumptions of all theoretical results? [Yes]

Did you include complete proofs of all theoretical results? [Yes]

Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes]

Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We specified relevant data processing details, the actual supervised learning model used not being the main interest. More details are given in the code.

Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes]

Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]

If you are using existing assets (e.g., code, data, models) or curating/releasing new assets…

If your work uses existing assets, did you cite the creators? [Yes]

Did you mention the license of the assets? [N/A]

Did you include any new assets either in the supplemental material or as a URL? [N/A]

Did you discuss whether and how consent was obtained from people whose data you’re using/curating? [Yes]

Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes]

If you used crowdsourcing or conducted research with human subjects…

Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]

Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]

Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]

Appendix A Additional elements on Measures of Fairness

Throughout the whole paper, we used a specific measure of fairness for simplicity. Nevertheless, the same arguments apply to a broader set of fairness measures, by modifying $u^{\ast}$.

To define $u^{\ast}$, we decided to take the $\log$ of a ratio. We note that when taking the $\sup$ over all possibles $a$ and $a^{\prime}$ in $\mathcal{A}$, $\sup_{\mathcal{A}^{2}}u(1,\cdot,\cdot)\leq\epsilon$ is equivalent to the definition in , that is to say:

However if we want to define a measure of unfairness between two protected groups, it is reasonable for it to be symmetric in the groups considered. We make it so by applying $\log$ and an absolute value function to the above middle quantity. Other distances and pseudo distances can also be chosen, such as $|\Pr(\hat{Y}=1\mid A=a)-\Pr(\hat{Y}=1\mid A=a^{\prime})|$. It is also symmetric, but may be less useful in comparing models with many protected attributes that are not designed to be fair, as this measure will be close to $1$ most of the time, making the comparison less precise between two different models.

We can also modify $U$ and the definition of probabilistic fairness accordingly to obtain other desirable measures of unfairness. Say that we are only interest in the unfairness related to the outcome $\hat{Y}=1$. Taking $U^{\prime}=u(1,A,A^{\prime})$ and $\Pr(U^{\prime}>\epsilon\mid\hat{Y}=1)\leq\delta$ the new definition of probabilistic fairness in this case, we can derive similar propositions and theorems as done in this paper. We only need to take the expectation and variance with respect to $\Pr(\cdot\!\mid\!\hat{Y}=1)$ for $L$ and $L_{y}$. This yields statistical quantities which are harder to interpret ($\sum_{a\in\mathcal{A}}\Pr(A=a\mid\hat{Y}=1)\log(\Pr(A=a)/\prod_{k=1}^{d}\Pr(A_{k}=a_{k})$) but that should remain easy to estimate as they are always well defined because, considering the empirical distribution $\hat{p}$ we have $\hat{p}_{A}(A=a)=0\implies\hat{p}_{A}(A=a\mid\hat{Y}=1)=0$. The changed definitions would be the following if we are only interested in the outcome $y\in\mathcal{Y}$:

Notably, we obtain a much nicer variant of Proposition 3.1, with $u^{\ast}=\sum_{k=1}^{d}u^{\ast}_{k}$.

Similarly we can also change only the underlying probability distribution. We can replace the underlying probability $\Pr$ by $\Pr_{Y=1}$. Using this new probability measure we see that $u^{\ast}$ is a relaxed version of Equality of Opportunity for a binary predictor defined in by

Indeed, $u^{\ast}=0$ is now equivalent with Equality of Opportunity. Practically, changing the underlying probability does not make much difference as showed in because this amounts to measuring unfairness on the part of the dataset for which $Y=1$.

Finally we can change over which treatment criterion we want to evaluate differences. In this paper we decided to look at the variable $\hat{Y}$. We can similarly define our fairness measure with $Y$. We can actually use any $(X,A,Y)$-measurable random variable $Z$ instead of $\hat{Y}$. For instance $|\hat{Y}-Y|$, which tells us whether or not the prediction is correct for binary classification, can be a good candidate.

Combining all of the above comments, we can consider a wider array of fairness metrics for which variations of the techniques and theorems described in this paper apply.

A.2 Some variants of Theorem 3.2 for modified fairness measures

We consider the following definition of unfairness:

For $\delta\in(0,1]$, any classifier $h$ over a distribution $\mathcal{D}$ is $(\epsilon_{1},\delta)$-probably intersectionally fair with

Intersectional Fairness when comparing to the population average:

We consider the following definition of unfairness:

For $\delta\in(0,1]$, any classifier $h$ over a distribution $\mathcal{D}$ is $(\epsilon_{1},\delta)$-probably intersectionally fair with

A.3 Comparison between other measures of fairness

We will briefly give some inequalities relating these quantities. We have that

Through these equations we see that $w^{*}$ cannot approach $u^{\ast}$.

The advantage of the notion of probable intersectional fairness compared to $w^{*}$ is two-fold: we can be arbitrarily close to $u^{\ast}$, and through $\delta$ we explicitly control the size of the population that faces discrimination.

Additionally we will present an example, which shows that when the number of protected groups grows large, the notion of weighted unfairness can become inadequate for certain scenarios compared to probabilistic unfairness.

We will consider that we have $991$ protected groups with three different protected groups sets of sizes $1$, $495$ and $495$, for which we will denote any of their elements by $a_{1}$, $a_{2}$, and $a_{3}$ respectively. We will consider that $\Pr(A=a_{1})=0.01$, and that the remaining protected groups are distributed uniformly $\Pr(A=a_{2})=\Pr(A=a_{3})=0.001$.

Suppose that $\Pr(\hat{Y}=1\mid A=a_{1})=1$ and $\Pr(\hat{Y}=1\mid A=a_{2})=\Pr(\hat{Y}=1\mid A=a_{3})=1/2$. Then $\Pr(\hat{Y}=1)=1/100+99/200=101/200$. Thus $u(a_{1})=1-101/200=99/200$, $w(a_{1})=99/20000$, $u(a_{2})=u(a_{3})=101/200-1/2=1/200$, and $w(a_{2})=w(a_{3})=1/200000$. Which means that $w^{*}=99/20000$ and the model is $(1/200,0.99)$-probabilistically fair. Now suppose that $\Pr(\hat{Y}=1\mid A=a_{1})=1$, $\Pr(\hat{Y}=1\mid A=a_{2})=1$, and $\Pr(\hat{Y}=1\mid A=a_{3})=0$. Then we have $\Pr(\hat{Y}=1)=101/200$. Thus $u(a_{1})=99/200$, $w(a_{1})=99/20000$, $u(a_{2})=99/200$, $w(a_{2})=99/200000$, $u(a_{3})=101/200$, and $w(a_{3})=101/200000$. Which means that $w^{*}=99/20000$ and the model is $(101/200,0.99)$-probabilistically fair. Here we see from these two examples, that $99\%$ population of their population saw their unfairness multiply by about a $100$ times while $w^{*}$ did not change. But probabilistic unfairness did manage to capture this change.

What we see is that when there is a high number of protected groups, relatively bigger groups tend to determine the weighted measure of unfairness $w^{*}$, but they can still consist of only a very small part of the total population overall.

Let $\mathcal{A}_{\epsilon}=\{a\in\mathcal{A}\mid u(a)\leq\epsilon\}$ and $\mathcal{A}_{\epsilon}^{C}$ its complementary set.

If $a^{*}=\operatorname*{arg\,max}w(a)\in\mathcal{A}_{\epsilon}$ then $w(a^{*})=p_{A}(a^{*})u(a^{*})\leq\epsilon\sup_{\mathcal{A}}p_{A}$. Otherwise using that $\Pr(\mathcal{A}_{\epsilon}^{C})\leq\delta$, we have $w(a)\leq\delta u^{\ast}$.

A.4 Intersectional Fairness and Continuous Protected Attributes

Here we will show that when $A$ is continuous, even for reasonable distributions, we might end up with $u^{\ast}=\infty$. Whereas our definition of probabilistic unfairness still has finite values, and can therefore be used as an interpretable tool to compare unfairness across models.

Suppose that we have a random vector $(A_{1},A_{2},...,A_{d},\hat{Y})$ distributed according to a multivariate normal $\mathcal{N}(\mu,\Sigma)$ with $\mu$ and $\Sigma$ the mean and covariance. Because $\hat{Y}$ is continuous, we will instead use the density $f_{\hat{Y}\mid A}$ in the definition of $u^{\ast}$. Because this vector is distributed according to a multivariate normal, the conditional distribution is still normal and we can derive the exact parameters. The conditional distribution is

with $\bar{\mu}$ a linear form in $a$, and $\bar{\Sigma}$ that depends only in $\Sigma$. Basically, we can make the mean go to $\infty$ by making $a$ go to $\infty$. Hence for a given $y\in\mathcal{Y}$, we have that $\inf_{a\in\mathcal{A}}f_{\hat{Y}\mid A}(y\mid a)=0$ for all $y$, which means that the unfairness is always infinite.

If we want to compare two machine learning models, and we do not want to compare for a specific point $\delta$, then $\epsilon^{*}(\delta)$ can be seen as a function of $\epsilon$, and we can compare these functions. If for two models $h_{1}$ and $h_{2}$ one function is always above the other, we could say that one is more fair than the other.

There are other fairness metrics specifically for continuous attributes, such as in the HGR coefficient between $A$ and $\hat{Y}$, but which may be less interpretable to decision makers.

Appendix B Missing proofs and elements of part 3

Let us define the following probability distribution on $(A_{1},A_{2},\hat{Y})$, with $A_{1}$, $A_{2}$, and $\hat{Y}$ binary:

We have $p_{A}=1/4$, and $p_{A_{1}}=p_{A_{2}}=1/2$. Therefore $A_{1}\perp\!\!\!\perp A_{2}$. We have $p_{\hat{Y}}=1/2$, hence $p_{A_{1}\mid\hat{Y}}(0\mid 0)=p_{A_{2}\mid\hat{Y}}(0\mid 0)=1/2$ and $p_{A_{1},A_{2}\mid\hat{Y}}(0,0,\mid 0)=3/8\neq p_{A_{2}\mid\hat{Y}}(0\mid 0)p_{A_{1}\mid\hat{Y}}(0\mid 0)$, therefore the $A_{k}$ are not independent conditionally on $\hat{Y}$. Because $p_{A_{1}\mid\hat{Y}}=p_{A_{2}\mid\hat{Y}}=1/2$, any form of marginal unfairness is , and $u^{\ast}=\log((3/4)/(1/4))=\log(3)\neq 0$. In this example we have mutual independence of the $A_{k}$, independence between $A_{k}$ and $\hat{Y}$, but still no meaningful relationship between intersectional and marginal fairness because we did not have independence conditionally on $\hat{Y}$.

B.2 Proof of Proposition 3.1

Using the assumed independence, for any $a$ in $\mathcal{A}$ and $y$ in $\mathcal{Y}$ we can rewrite $p_{\hat{Y}\mid A}$ with marginal quantities:

Because the numerator is a product of independent variables (in the functional sense), taking the sup in $\mathcal{A}$ yields:

The inequality is obtained by triangle inequality and because $\sup_{y\in\mathcal{Y}}\sup_{(a_{k},a_{k}^{\prime})\in\mathcal{A}_{k}^{2}}u_{k}(y,a_{k},a_{k}^{\prime})=u^{\ast}_{k}$ by definition.

B.3 Proof of Theorem 3.2 and Corollary 3.3

For $\delta\in(0,1]$, any classifier $h$ over a distribution $\mathcal{D}$ is $(\epsilon_{1},\delta)$ and $(\epsilon_{2},\delta)$-probably intersectionally fair with

We want to show that our classifier is $(\epsilon,\delta)$ probably fair for a given $\delta$.

We will first bound in probability $L$ and $L_{y}$, to be able to approach the joint densities through the product of marginal densities. We will denote by $\mu$, $\mu_{y}$, $\sigma$ and $\sigma_{y}$ the expectations and variances of $L$ and $L_{y}$ Let us apply Chebyshev’s inequality to $L$. We obtain that

Using the fact that $\{|L-\mu|<\alpha_{1}\}\subset\{|L-\mu|\leq\alpha_{1}\}$ and taking the complementary event we can write that

We can do the same for $L_{y}$ with a parameter $\alpha_{2}>0$.

Now we want to consider a condition on the parameters $\boldsymbol{\alpha}=(\alpha_{1},\alpha_{2})$ so that the probability of the conjunction of the events $\{|L-\mu|\leq\alpha_{1}\}$ and $\{|L_{y}-\mu_{y}|\leq\alpha_{2}\}$ is greater than $1-\delta$. For $\delta>0$, $\alpha_{1}>0$ and $\alpha_{2}>0$, a sufficient condition is that $\frac{\sigma^{2}}{\alpha^{2}}+\frac{\sigma^{2}_{z}}{\alpha_{2}^{2}}\leq\delta$. We can show this using complementary event and Boole’s inequality:

We define $g(\boldsymbol{\alpha})=\frac{\sigma^{2}}{\alpha_{1}^{2}}+\frac{\sigma^{2}_{z}}{\alpha_{2}^{2}}-\delta$. For any $\boldsymbol{\alpha}$ such that $g(\boldsymbol{\alpha})\leq 0$ we have with probability at least $1-\delta$ that

where $\varphi(\mu_{y},\mu)=e^{\mu_{y}-\mu}$, $\psi(\boldsymbol{\alpha})=e^{\alpha_{1}+\alpha_{2}}$, and $f(y,a)=\prod_{k=1}^{d}p_{\hat{Y}\mid A_{k}}(y\mid a_{k})/p_{\hat{Y}}(y)^{d}$. Hence by taking the $\sup$ over $a$ and $\inf$ over $\boldsymbol{\alpha}$ on the right hand-side, we obtain

As it is a product of functions of independent variables, $\sup_{a\in\mathcal{A}}f(y,a)$ is just the product of the $\sup$ of each $p_{\hat{Y}\mid A_{k}}$.

We will now solve the constrained optimization problem for $\psi$. We can write $\inf e^{\alpha_{1}+\alpha_{2}}=e^{\inf(\alpha_{1}+\alpha_{2})}$, so we will just need to solve the simpler problem $\inf_{g(\alpha)\leq 0}s(\alpha)$, with $s(\alpha)=\alpha_{1}+\alpha_{2}$. Let us compute the gradients of $s$ and $g$:

We will now show that this is a convex problem. The function $s$ is linear thus convex, and we will now compute the hessian of $g$:

Clearly we have that the determinant of $H_{g}$, $Det(H_{g})$ is strictly positive. Therefore $H_{g}$ is definite positive, and $g$ is convex. And for $\delta>0$ there is a feasible interior point by taking $\alpha_{1}$ and $\alpha_{2}$ big enough, which means that Slater’s conditions hold (e.g. a convex constraint with a feasible interior point). We will now analyze the KKT conditions for minimization with the dual parameter $c\geq 0$:

We obtain that $\alpha_{1}=\sqrt{2c\sigma^{2}}$ and $\alpha_{2}=\sqrt{2c\sigma_{y}^{2}}$ Clearly $c>0$ otherwise the first two lines cannot be 1, hence using the last equation we have $g(\alpha_{1},\alpha_{2})=0$. We now develop this last equality to obtain $c$:

Plugging $c$ in the previous expressions we have

We will now do the same in order to lower bound $p_{A}(\hat{Y}|A)$.

Here we take the $\sup$ over $\boldsymbol{\alpha}$ and $\inf$ over $a$ instead. We have that $\sup\psi(\boldsymbol{\alpha})^{-1}=(\inf\psi(\boldsymbol{\alpha}))^{-1}=\exp(-s^{*}/\sqrt{\delta})$.

Because $U$ involves the two variables $A$ and $A^{\prime}$, we need to bound $L^{\prime}$ and $L^{\prime}_{y}$ the variables $L$ and $L_{y}$ that are taken as a function of $A^{\prime}$ instead of $A$. Because $(A^{\prime},\hat{Y})\sim(A,\hat{Y})$, all the computations above still apply, and we have

Hence we only need to replace $\delta$ by $\delta/2$ in the above inequalities.

Combining everything, we can conclude that when the event $\{|L-\mu|\leq\alpha^{*}_{1}\}\cap\{|L_{y}-\mu_{y}|\leq\alpha^{*}_{2}\}\cap\{|L^{\prime}-\mu|\leq\alpha^{*}_{1}\}\cap\{|L^{\prime}_{y}-\mu_{y}|\leq\alpha^{*}_{2}\}$ occurs, we have

which means that our classifier is $(\epsilon_{1},\delta)$-probably intersectionally fair. Note that $\epsilon_{1}$ is a function of $(\delta,\sigma,\sigma_{y})$.

In order to derive the proof for $\epsilon_{2}$, we simply remark that $p_{\hat{Y}\mid A}\leq 1$ which can be used to upper bound the numerator. Therefore when the event $\{|L-\mu|\leq\alpha^{*}_{1}\}\cap\{|L_{y}-\mu_{y}|\leq\alpha^{*}_{2}\}\cap\{|L^{\prime}-\mu|\leq\alpha^{*}_{1}\}\cap\{|L^{\prime}_{y}-\mu_{y}|\leq\alpha^{*}_{2}\}$ occurs, we have

We can conclude in the same way as for $\epsilon_{1}$.

Looking at the proof, it also holds true that the model will also be $(\min\{\epsilon_{1},\epsilon_{2}\},\delta)$-probably intersectionally fair. ∎

Denoting $(\Omega,\mathcal{T},\Pr)$ the probability space on which $(\hat{Y},A,A^{\prime})$ is defined, there exists an event $F$ so that for $f(y,a)=\prod_{k=1}^{d}(p_{\hat{Y}\mid A_{k}}(y\mid a_{k})/p_{\hat{Y}}(y))$ we have for $U$ the random unfairness:

What we have shown in the above proof of the Theorem before taking the $\sup$ and $\inf$ in $a\in\mathcal{A}$, is that the event $\{|L-\mu|\leq\alpha^{*}_{1}\}\cap\{|L_{y}-\mu_{y}|\leq\alpha^{*}_{2}\}\cap\{|L^{\prime}-\mu|\leq\alpha^{*}_{1}\}\cap\{|L^{\prime}_{y}-\mu_{y}|\leq\alpha^{*}_{2}\}$ is included in $F$, and hence $\Pr(F)\geq 1-\delta$. Using these upper bounds, and simplifying by $p_{\hat{Y}}(\hat{Y})\exp(-\gamma)$ when taking the ratio of $p_{\hat{Y}\mid A}$ and $p_{\hat{Y}\mid A^{\prime}}$ , we have that

Taking the $\sup$ over all elements $\omega$ in $F$ we obtain that

where $\sup_{\omega\in F}U(\omega)$ is the maximum random unfairness over the event $F$.

We cannot recover a form which uses the $u_{k}$, as here the variable $A$ and $A^{\prime}$ are linked through $F$. Notice that we can upper bound $\sup_{\omega\in F}|\log(f(\hat{Y},A^{\prime})/f(\hat{Y},A))(\omega)|$ by $\sup_{\omega\in\Omega}|\log(f(\hat{Y},A^{\prime})/f(\hat{Y},A))(\omega)|$ because $F\subset\Omega$, which then recovers Theorem 3.2 but stated in a slightly different way. The convenient part of this Corollary is that we are also able to lower bound $\sup_{\omega\in F}U(\omega)$, but of course the inconvenience is that $F$ is unknown. ∎

B.4 Additional Bounds on Probable Intersectional Fairness

These moments generating functions can be expressed as functions of Renyi Divergences, indeed

While $\kappa(t)$ can therefore be estimated using techniques of for instance, the estimation of $\kappa_{y}$ is less straightforward.

We will apply the same reasoning used in Appendix B.3 and will only highlight the differences.

We want to ensure that the right hand-side is greater than $1-\delta$. Because we need to make sure that it also holds for $L^{\prime}$ and $L_{y}^{\prime}$, we need $2\delta$ instead of $\delta$. We define the constraint

we need to have $g(\lambda^{+},\lambda^{-})\leq 0$. Hence using feasible values of $\lambda^{+}$ and $\lambda^{-}$, the event $[L_{y}\geq\lambda^{+}]\cap[L\leq\lambda^{-}]$ implies

Using that $\sup_{\mathcal{A}}p_{\hat{Y}\mid A}\leq 1$ we therefore have the following Theorem:

For $\delta\in(0,1]$, any classifier $h$ over a distribution $\mathcal{D}$ is $(\epsilon_{3},\delta)$-probably intersectionally fair, with

Compared to using Chebyshev, this should be both tighter as we are using more information than the first and second moment, and this bound should also be more efficient in terms of probability, as we are using one sided concentration inequalities.

B.5 Properties of the cumulant generating-function

We now want to be able to say a bit more on the properties of this constrained minimization problem. We will show by first recalling and developing useful properties on $\kappa$ that the problem is non convex and differentiable almost everywhere.

We will list the properties about $\kappa$ that will be useful to us developed in , with being a summary containing all the information needed.

We have that $\kappa$ is strictly convex and infinitely many times differentiable. This means that $\kappa^{\prime}$ is strictly increasing and that it can be inverted on $\operatorname{Im}(\kappa^{\prime})$. We will write $\kappa^{\prime(-1)}=\eta$, and for all $x$ so that $\kappa^{\prime\prime}(\eta(x))\neq 0$ we have $\eta^{\prime}=1/\kappa^{\prime\prime}(\eta)$.

We also have that $\kappa(0)=0$, $\kappa^{\prime}(0)=\mu$, and $\kappa^{\prime\prime}(0)=\sigma^{2}$.

From these properties we can conclude that $\eta(\mu)=0$, and that $\eta^{\prime}(\mu)=1/\kappa^{\prime\prime}(\eta(\mu))=1/\sigma^{2}$.

We will recall the definition of the convex conjugate of a function.

We will now list the useful properties about $I=\kappa^{\star}$ also developed in .

The function $I$ is infinitely many times differentiable on $\operatorname{Im}(\kappa^{\prime})$, $I(\mu)=0$, and for every $x\in\operatorname{Im}(\kappa^{\prime})$ we can rewrite $I$ as

The function $I^{+}$ is continuously differentiable on $(-\infty,\sup\kappa^{\prime})$.

We have $\mu\in\operatorname{Im}(\kappa^{\prime})$ because $\kappa^{\prime}(0)=\mu$. Let $f_{x}(t)=tx-\kappa(t)$. If $x<\mu$, then because $\kappa^{\prime}$ is increasing we have for any $t\geq 0$