Year: 2021

Abstract:
Previous literature has shown that bias mitigating algorithms were sometimes prone to overfitting and had poor out-of-sample generalisation. This paper is first and foremost concerned with establishing a mathematical framework to tackle the specific issue of generalisation. Throughout this work, we consider fairness trade-offs and objectives mixing statistical loss over the whole sample and fairness penalties on categories (which could stem from different values of protected attributes), encompassing partial de-biasing. We do so by adopting two different but complementary viewpoints: first, we consider a PAC-type setup and derive probabilistic upper bounds involving sample-only information; second, we leverage an asymptotic framework to derive a closed-form limiting distribution for the difference between the empirical trade-off and the true trade-off. While these results provide guarantees for learning fairness metrics across categories, they also point out to the key (but asymmetric) role played by class imbalance. To summarise, learning fairness without having access to enough category-level samples is hard, and a simple numerical experiment shows that it can lead to spurious results.

heading: 1 INTRODUCTION
text: Reducing bias in an algorithm requires a number of steps; first, specify the fairness definitions (and thus fairness metrics) that apply, second, encode them with a penalty so as to measure the discrepancy between outcomes and the perfect fairness scenario, third, choose the trade-off between the original statistical goal and fairness constraints, and, fourth, pick a method to debias (at least partially) the model. There are a number of obstacles to this programme. Indeed, debiasing may come at a cost (Rodolfa et al. (2020)), but there are also theoretical reasons behind this claim. Jointly tackling multiple fairness definitions is usually difficult if not impossible without a decrease in model performance due to a series of impossibility theorems (Kleinberg et al. (2017); Pleiss et al. (2017); Chouldechova (2017); Kim et al. (2020)). Note that these results apply not only to fairnessperformance but also to fairness-fairness trade-offs.
Research has recently been undertaken to tackle specifically learnability and generalisation in fairness-related problems. In particular, Oneto et al. (2020); Oneto et al. (2020) derive provable probabilistic upper bounds in a fairness setting where one estimates an overall statistical loss and monitors disparities across categories. In Chen et al. (2018), the authors have applied bias-variance decomposition techniques to disentangle the sources of unfairness in a classifier. While this is not directly related to this present work, the principle of risk decomposability turns out to be fruitful in both setups. Finally, in Agrawal et al. (2020), a limiting distribution is established in the simple case where there is a partial requirement involving a fairness metric with two categories.
Our contributions. The novelty of our work consists of the application of known techniques such as PAC inequalities and the central limit theorem to the problem of learning under fairness constraints:
• First, we develop a PAC framework for fairness trade-offs, generalising results from Donini et al. (2018); Oneto et al. (2020) and tackling explicitly partial debiasing (see Kim et al. (2020); Agrawal et al. (2020)).
• Second, we show that certain properties of the probabilistic upper bounds lead to the need for sample-efficient bias mitigation techniques. In particular, we show that a new quantity, ZS , which can be understood as measure of sample concentration, plays a crucial role. We
also build on Agrawal et al. (2020) and develop an asymptotic framework with a known limiting distribution; this is useful as PAC bounds may not always be very sharp.
• Third, in both frameworks, we put forward the decomposability of the learning risk, expressed as an upper bound in the PAC realm and a limiting variance in the asymptotic one.
• Last, we illustrate our results on real-life data and show that generalisation is indeed difficult.

heading: 2 FAIRNESS METRICS AND LOSS FUNCTIONS

heading: 2.1 SET-UP AND DEFINITIONS
text: In this article, we define s = 1, · · · , C to be a categorical (protected) attribute, x ∈ X ⊂ Rd to be a set of non-protected features excluding s. y ∈ { − 1,+1} is a binary outcome variable and ŷ ∈ { − 1,+1} is an estimator for y. Finally, z = (x, y, s). Note that ŷ is derived from a learner h ∈ H, whereH is a given functional space. Furthermore, we define S to be the in-sample (training) empirical distribution, and D to refer to the true distribution.
Throughout this paper, we consider the case of an overall objective as a statistical performance objective, L0, plus a fairness loss function φ. The trade-off is tuned by a hyper-parameter λ ≥ 0. As usual, the aim is to minimise the overall objective, i.e., minimise the statistical loss and the lack of fairness. This set-up is typical for partial debiasing and can be found in Kim et al. (2020). Definition 1. The overall objective or fairness trade-off is defined as
LD(h) = L0D(h) + λφ ( L+D,1(h), L − D,1(h), · · · , L + D,C(h), L − D,C(h) ) = L0D(h) + λφ(L ± D(h)),
where we have used the standard notations (see Shalev-Shwartz & Ben-David (2014)): L0D(h) = E [ `0(h, z) ] L+D,a(h) = E [ `+(h, z)|s = a, y = 1
] L−D,a(h) = E [ `−(h, z)|s = a, y = −1
] and the vector notation L±D(h) = [ L+D,1(h), L − D,1(h), · · · , L + D,C(h), L − D,C(h) ]T , for some functions `0, `+ and `−. Remark 1. In the whole paper, we assume that there exists a uniform bound B > 0 on all functions `, i.e., |`(h, z)| ≤ B for all h and z. ` refers to any such function in what follows.
Let us detail two particular cases. If λ = 0, then the overall objective boils down to the usual risk minimisation problem. If `0 = 0 or λ→ +∞, then the trade-off becomes a fairness constraint. We are now in a position to define the empirical counterpart by considering the empirical distribution rather than the true distribution. With the additional notationsN±a = {i ∈ {1, · · · , n} ; si = a, yi = ±1}, |N±a | = n±a , the corresponding sample versions can be defined as L0S(h) = 1n ∑n i=1 `
0(h, zi), L+S,a(h) =
1 n+a ∑ i∈N+a ` +(h, zi) and L−S,a(h) = 1 n−a ∑ i∈N−a ` −(h, zi), where na = n+a + n − a ,
n = ∑C a=1 na, leading to
LS(h) = L0S(h) + λφ ( L±S (h) ) (1)
For the sake of simplicity, we will generally refer to φ(L±T (h)) as φT (h) for T = D,S.

heading: 2.2 FAIRNESS DEFINITIONS AND METRICS
text: One can find multiple technical definitions of fairness in the literature; they have been reviewed in various papers (Narayanan, 2018; Verma & Rubin, 2018; Berk et al., 2018; Kim et al., 2020; Agrawal et al., 2020). We offer an overview of the most frequent metrics in Table 1.
We note that all fairness metrics considered here can be expressed as an equality requirement on probabilities, hence on the expectation of indicator variables. These fall within our framework. However, this framework can also handle other types of functions.

heading: 2.3 FAIRNESS LOSS FUNCTIONS
text: In addition to picking one or multiple fairness definitions, we need to specify φ to measure the discrepancy from perfect fairness, the ideal case.
A first approach, similar to the Calders-Verwer gap (Calders & Verwer, 2010), consists of looking at the discrepancy between two categories a and a′:
∆L,±T,a,a′(h) = L ± T,a(h)− L ± T,a′(h),
for T ∈ {D,S}. It is worth 0 under perfect fairness, but is asymmetric and thus requires defining an advantaged (or benchmark) category a.
To avoid the issue of asymmetry, one can follow Oneto et al. (2020), and define φ as the sum of all absolute discrepancies across categories:
φ(L±T (h)) = ∑ a6=a′ {∣∣∣L+T,a − L+T,a′ ∣∣∣+ ∣∣∣L−T,a − L−T,a′∣∣∣} , (2) for T = D,S. Notice that, thanks to the reverse triangle inequality, the function φ is Lipschitz continuous. One could naturally weigh the various contributions to this fairness function and use another norm than L1. Other functions involving ratios or relative differences, are also possible.
Finally, in Kim et al. (2020), the authors consider a convex combination of multiple loss functions φ(1), · · · , φ(M):
φ(L±T (h)) = M∑ j=1 λjφ (j) ( L±T (h) ) .
Note that if the φ(j)’s are Lipschitz-continuous (with respect to the loss vector L±T (h)), with respective Lipschitz constant K(j), then the overall loss φ is itself Lipschitz-continuous with constant Kφ = ∑M j=1 λjK (j).

heading: 3 LEARNING FAIRNESS TRADE-OFFS
text: In this section, we consider the learning problem from different angles. We start by considering the statistical loss L0 and derive a bound based on the Rademacher complexity observed in each category. To do so, we borrow from the statistical learning toolbox and briefly review Rademacher complexities. We then move on to learning the fairness part per se, namely study the generalisation properties of φS(h). Finally, we bring the two together and derive probabilistic upper bounds on fairness trade-off generalisation.

heading: 3.1 LEARNING THE STATISTICAL LOSS
text: Let us first focus on the statistical component of the loss, i.e., L0T for T ∈ {S,D}. Much of this paper is based on theory of bounds derived from Rademacher complexities, introduced in Bartlett & Mendelson (2003) and surveyed in Boucheron, Stéphane et al. (2005). Recent textbooks such as Shalev-Shwartz & Ben-David (2014); Mohri et al. (2012) provide excellent introductions to the topic. We start by recalling the definition of Rademacher complexities, as indicated in Boucheron, Stéphane et al. (2005):
Definition 2. The Rademacher complexity (or average) of a function ` is given by
R(` ◦ H ◦ S) = E [ sup h∈H 1 n ∣∣∣∣∣ n∑ i=1 σi` (h, zi) ∣∣∣∣∣ ] . (3)
Note that definitions can slightly vary (depending for instance on the presence or absence of the absolute value in the definition), but all downstream results are qualitatively similar, up to some multiplicative constants.
To make this more concrete, we can consider a simple (but usual) case (as describe in ShalevShwartz & Ben-David (2014)). We suppose that almost surely ‖x‖2 ≤ R. In addition, if we let H = {w; ‖w‖2 ≤ R′} and assume that the loss function ` is of the type `(w, (x, y)) = ρ ( wTx, y ) , where |ρ| is bounded by B and is Lρ-Lipschitz, then, almost surely,
R(` ◦ H ◦ S) ≤ L ρRR′√ n .
Rademacher complexities are key to establishing learnability bounds and lead to fundamental results in statistical learning theory. In particular, we will make use of a standard result (see Boucheron, Stéphane et al. (2005)). Proposition 1. With probability at least 1− δ, it holds
sup h∈H |LD(h)− LS(h)| ≤ 2R(` ◦ H ◦ S) +B √ 2 log 2δ n . (4)
It will also be useful to introduce conditional Rademacher complexities that will be used throughout this paper. In particular, since we have a partition of the sample in terms of categories S = ⋃C a=1Na, we can consider the Rademacher complexity of that particular sample:
R(` ◦ H ◦ Na) = E [ sup h∈H 1 na ∣∣∣∣∣∑ i∈Na σi` (h, zi) ∣∣∣∣∣ ] . (5)
Lemma 1. The sample Rademacher complexity can be bounded from above by the weighted sum of conditional Rademacher complexities:
R(` ◦ H ◦ S) ≤ C∑ a=1 na n R(` ◦ H ◦ Na), (6)
where R(` ◦ H ◦ Na) = E [ suph∈H 1 na ∣∣∑ i∈Na σi` (h, zi) ∣∣]. Proof. This comes directly from the sub-additivity of the absolute value and the supremum. One can further interpret the non-negative gap ∑C a=1 na n R(` ◦ H ◦ Na)− R(` ◦ H ◦ S) as a diversification benefit amongst categories. Finally, this leads us to a proposition leveraging our results so far: Proposition 2. With probability at least 1− δ,
sup h∈H ∣∣L0D(h)− L0S(h)∣∣ ≤ 2 C∑ a=1 na n R(`0 ◦ H ◦ Na) +B √ 2 log 2δ n . (7)

heading: 3.2 LEARNING FAIRNESS REQUIREMENTS
text: Let us now move on to the fairness learning part; as before, we would like to find a bound on the distribution fairness loss given the sample fairness loss, i.e., a probabilistic bound on the difference φD(h)− φS(h).
Proposition 3. Under the assumption that φ isKφ-Lipschitz, it holds, with probability at least 1−δ, and where ZS := ∑C a=1 √ n n+a + √ n n−a , that
sup h∈H |φD(h)− φS(h)| ≤ 2Kφ C∑ a=1 R(`+ ◦ H ◦ N+a ) +R(`− ◦ H ◦ N−a )
+KφBZS
√ 2 log 4Cδ
n .
The proof can be found in Appendix C.1 and the role played by ZS is investigated in Section 4.

heading: 3.3 SIMULTANEOUS LEARNING OF STATISTICAL PERFORMANCE AND FAIRNESS
text: We have established probabilistic bounds on both the statistical performance criterion and the fairness penalty. However, we wish to study both jointly, and determine the behaviour of the chosen fairness trade-off. As mentioned previously, this trade-off is very flexible and can accommodate multiple situations.

heading: 3.3.1 BOUNDING LOSS AND FAIRNESS
text: First, we may wish to determine a probabilistic upper bound on L0D(h)−L0S(h) and φD(h)−φS(h) jointly. By a simple application of the union bound, we obtain the following result: Proposition 4. With probability at least 1− δ, it holds jointly that
sup h∈H
∣∣L0D(h)− L0S(h)∣∣ ≤ 2R(`0 ◦ H ◦ S) +B √
2 log 4δ n
sup h∈H |φD(h)− φS(h)| ≤ 2Kφ C∑ a=1 R(`+ ◦ H ◦ N+a ) +R(`− ◦ H ◦ N−a )
+KφBZS
√ 2 log 8Cδ
n .

heading: 3.3.2 BOUNDING THE TRADE-OFF
text: As mentioned above, the existence of various impossibility results and the empirical findings showing that statistical performance tends to decrease as fairness requirements increase have highlighted the interest for partial debiasing methods. It is however important to be able to determine the generalisation properties that such objectives can lead to. We can perform a similar analysis on the trade-off objective LD(h) by using the same arguments to get an upper bound on this objective. Proposition 5. With probability at least 1− δ, it holds
sup h∈H |LD(h)− LS(h)| ≤ 2R(`0 ◦ H ◦ S) +B √ 2 log 4δ n
+2λKφ C∑ a=1 R(`+ ◦ H ◦ N+a ) +R(`− ◦ H ◦ N−a )
+λKφBZS
√ 2 log 8Cδ
n
≤ 2 C∑ a=1 { n+a n R(`0 ◦ H ◦ N+a ) + n−a n R(`0 ◦ H ◦ N−a )
+λKφR(`+ ◦ H ◦ N+a ) + λKφR(`− ◦ H ◦ N−a ) } +B ( 1 + λKφZS )√2 log(8C/δ) n .
The upper bound can be understood as the sum of individual contributions plus the usual O (√ log(1/δ)/n )
factor. Let us now establish a related inequality, linking the distribution value of the trade-off under the distribution optimum and under the sample optimum. Let us denote by h∗T =h∈H LT (h) for T ∈ {D,S} an optimal classifier derived on either the underlying distribution or the sample distribution of the objectives LT . This is an important issue for learnability of fairness as it provides some guarantees on how far the actual optimal trade-off is from the one we would obtain by picking the optimum computed on the sample S. This result provides a fairness pendant to the usual case in statistical learning (see for instance Theorem 26.5 in Shalev-Shwartz & Ben-David (2014)).
Theorem 1. With probability at least 1− δ, it holds
0 ≤ LD(h∗S)− LD(h∗D) ≤ UBS +B ( 1 + λZSK φ ) 3√
2
√ log(16C/δ)
n , (8)
where h∗T =h∈H LT (h) for T ∈ {D,S}, and UBS := 2 ∑C a=1 {n+a n R(` 0 ◦ H ◦ N+a ) + n−a n R(`
0 ◦ H ◦ N−a ) + λKφR(`+ ◦ H ◦ N+a ) + λKφR(`− ◦ H ◦ N−a ) } .
The proof is given in Appendix A. What is particularly interesting about this result is the fact that the upper bound remains the same as in Proposition 5, and only the O (√ log(1/δ)/n ) factor changes.
Let us point out that this result is practical in nature in the sense that one would use h∗S in practice but would still look for out-of-sample generalisation, hence the importance of the term LD(h∗S).

heading: 4 (SOME) PRACTICAL CONSEQUENCES OF PAC FOR FAIRNESS TRADE-OFFS

heading: 4.1 DECOMPOSING UPPER BOUNDS ON GENERALISATION
text: One is led to decompose the overall loss in terms of each category’s contributions to the overall learning upper bound.
Definition 3. The (half-)contribution –denoted by RNa– of each category a = 1, · · · , C, to the fairness trade-off learning upper bound is
RNa := n+a n R(`0 ◦ H ◦ N+a ) + n−a n R(`0 ◦ H ◦ N−a )
+λKφR(`+ ◦ H ◦ N+a ) + λKφR(`− ◦ H ◦ N−a ).
Remark 2. This structure is quite interesting as it shows that the first two terms representing contributions to the statistical loss upper bound are weighted by their proportions of the overall sample. Thus, even if the Rademacher complexity of the category is high, it can be counterbalanced by the fact that it will not affect the overall average loss. On the other hand, the contributions coming from the fairness part are unweighted. In this case, a low sample size would usually lead to a higher Rademacher complexity.
Now, RNa can be decomposed into finer components:
RNa = R 0,+ Na +R 0,− Na +R + Na +R − Na , (9)
with obvious notations. One can then determine the contributions coming from the union of certain categories or of positives or negatives.

heading: 4.2 ZS AS SAMPLE CONCENTRATION
text: First, let us remark that the usefulness of probabilistic upper bounds comes from the fact that the ones that have been established only rely on observable quantities coming from the sample under consideration. This is powerful as a practical check, but it also suggests a way of amending the initial minimisation exercise by including the upper bound to the sample component, i.e., optimise LD(h) + UBS(h).
Second, a quantity that is ubiquitous in our analysis (see, for instance, Theorem 1), is ZS =∑C a=1 √ n n+a + √ n n−a . As noticed previously, this is a measure of concentration within the sample that only depends on in-sample data. The more unequal the count of categories’ sample sizes, the higher ZS . This can be formalised in the following proposition:
Proposition 6. The constant ZS can be expressed in terms of the empirical class sample proportions:
ZS = C∑ a=1 [ (p̂+a ) − 12 + (p̂−a ) − 12 ] = 2C√ M−1/2(p̂) , (10)
where Mα(p̂) is the α-generalised mean 1 of the vector p̂ = (p̂±a ) ± a . In addition, under the assumption that n±a ≥ 1 for all a = 1, · · · , C, and n > 2C − 1, the following inequality holds:
(2C)3/2 ≤ ZS ≤ (2C − 1) √ n+
√ n
n− (2C − 1) . (11)
The proof is straightforward and left to the reader. The bounds on ZS offer two take-aways. First, the lower bound grows super-linearly as a function of the number of categories, which is problematic especially to tackle intersectionality. Second, the upper bound on ZS/ √ (n) converges to a non-zero constant as n goes to infinity. This is an extreme scenario whereby a category can be made up of one individual only, but this stresses the fact that class imbalance can hinder learning in the context of fairness. ZS is model-agnostic and thus useful to determine ex-ante how much debiasing can be applied on a given dataset.

heading: 5 ASYMPTOTIC REGIME
text: One of the possible issues of using PAC learning in practice is the fact that it tends to consider worstcase scenarios (e.g., by deriving probabilistic inequalities over a whole space of possible classifiers). To mitigate this possible drawback, we adopt a very different viewpoint and set ourselves in a framework which generalises Proposition 1 in Agrawal et al. (2020). Our objective is to derive a limiting distribution for the rescaled fairness trade-off after having trained one particular classifier, which we then consider fixed. In doing so, we can thus assess the different contributions to the limiting variance given the choice of classifier. In addition to corresponding to real-life modelling, this also has the benefit of allowing for closed-form results (as opposed to upper bounds in PAC learning). Both approaches are –as will be shown– very complementary.
Let us say a few words about the idealised data generating process that hypothetically produces our observations. In particular, we consider that we have an infinite population of independently and identically distributed datapoints, according to a mixture distribution with probability weights p±a . Conditional on a and y = ±1, we can then draw x. All draws are independent. Let us introduce some additional notation: the intra-category variances are given by ( σ0,±a )2 =
Vs=a,y=±1 [ `0(h, z) ] , (σ±a ) 2 = Vs=a,y=±1 [`±(h, z)]. Furthermore, K±D,a = ∂x±a φD(h), i.e., K±D,a is the entry corresponding to a ± in the gradient ∇φD(h). We can now introduce our main result, which extends Agrawal et al. (2020) to a multi-category and multi-dimensional setting.
Theorem 2. Let h ∈ H, under mild assumptions, we have the following convergence in distribution √ n (LS(h)− LD(h))
d−−−−−→ n→+∞ N (0,Vlim(h)) , (12)
where
Vlim[h] = ∑ a± p±a ( σ0,±a )2 + λ2 (K±a ) 2 p±a ( σ±a )2 + covariance terms (13)
The exact assumptions and the proof can be found in Appendix B. In a nutshell, the variance of the limiting trade-off distribution is the addition of
1The α-generalised mean of K numbers x1, · · · , xK is given by (
1 K ∑K k=1 x α k )1/α .
• The sum of intra-category `0,± losses weighted by their true probabilities p±a ; • The sum of intra-category fairness `± losses weighted by their inverse probabilities p±a ,
as in the uniform convergence framework. In addition, the constant (K±a ) 2 represents the sensitivity of the fairness loss function φ and is bounded from above by [Kφ]2 in these case where φ is Kφ-Lipschitz continuous, while λ is the hyper-parameter governing the trade-off between statistical and fairness performances.
Qualitatively, the results obtained in the asymptotic and uniform frameworks are similar and point to the conclusion that to learn fairness, one must start by learning category samples. A low probability p±a may not impact the variance of the overall statistical loss but it may lead to a very poor understanding of fairness trade-offs.

heading: 6 EXPERIMENTAL RESULTS
text: In this Section, we investigate on real datasets the validity of the theoretical results that we have derived. Here, we solve (via L-BFGS) for a logistic regression with an additional constraint on fairness. Concretely, the objective function is defined as:
min β∈Rd
1
n n∑ i=1 `(yi,xi;β) + λ  1 n0 n0∑ j=1 `(yj ,xj ;β)− 1 n1 n1∑ j′=1 `(yj′ ,xj′ ;β) 2 , (14) where ` is the logistic loss function and the groups 0 and 1 correspond to two different classes of a protected attribute. We have considered three datasets with binary protected attributes and binary outcomes, shown in Table 2, and applied a standard 80–20 train-test split.
Figures 1 and 2 illustrate the trade off between average loss and disparity for a range of λ values. 3
On the train test (Figure 1, there is a clear dependence between the value of λ and the respective average loss and disparity between groups. As expected, an increase in λ tends to decrease disparity, while increasing the average loss, and vice versa. However, this is not always the case on the test set, as some intermediate values of λ achieve both lower average loss and lower disparity, whereas more (or totally) debiased models clearly overfit.

heading: 6.1 IN-SAMPLE RESULTS
text: 3Specifically {0.01, 0.05, 0.1, 0.5, 1, 5, 10, 50, 100, 500}. Each distinct color represents a different initialization, while the size of the point is a monotonically increasing function of the respective λ.

heading: 6.2 OUT-OF-SAMPLE RESULTS

heading: 6.3 STANDARD DEVIATION SCALING
text: We experiment with class imbalance to see how the solution to the original problem changes as imbalance grows, in line with Theorem 2. To do so, we downsample observations from one class, while keeping the original number of observations in the other class. As predicted, on the test set, the loss variance increases with class imbalance, as shown in Figure 34.

heading: 7 CONCLUSION
text: The analysis that we have conducted from two different angles, namely learning with uniform convergence and asymptotics, leads to the same overall qualitative assessment. While we have derived probabilistic upper bounds to prove learning guarantees on the one hand and convergence to a limiting distribution on the other, a striking feature of learning fairness trade-offs is the fundamental difference of regimes between the usual statistical performance criterion measured on the whole sample and the fairness penalty that examines relationships between sub-samples.
Indeed, fairness is not about learning an average distribution, quite the contrary, in the sense that it requires a fine understanding of differences across conditional distributions. Intuitively, in the usual case of an overall statistical loss function, if a category only represents a small portion of the sample, then it also only constitutes a small fraction of the overall loss. On the opposite, from a fairness viewpoint, this implies that it is difficult to make any type of statements regarding the relationship between this particular category and other categories, hence a high risk for a given fairness objective. We have also shown with an empirical investigation that our results translate to practical cases and that small sample sizes or class imbalance can lead to spurious empirical results.
4Here, points of the same color correspond to the same random seed. Different random seeds are needed to obtain several variants of the downsampled data. The dotted color lines are the plain linear least square estimate through the points of the same color, while the bold black line is least square estimate using data points from all seeds. λ is fixed at 50.

heading: A SOME APPLICATIONS OF FAIR LEARNING
text: In this Section, we apply our results to two particular loss functions, namely the Calders-Verwer gap and the Bayes gap.
A.1 EXAMPLE 1: LEARNING DISPARITY
Of particular interest when measuring fairness is the discrepancy that can be observed amongst different groups, for example in terms of a loss L that captures some properties we wish to ascertain. This could be the difference in false negative rates between categories a and a′, where a is usually chosen to be a reference group. This concept holds for both the true distribution and the sample distribution.
Definition 4. The (demographic) disparity, or Calders-Verwer gap Calders & Verwer (2010); Chen et al. (2019), between groups a and a′ with respect to loss L can be defined as
∆LT,a,a′(h) = LT,a(h)− LT,a′(h), (15)
for T ∈ {D,S}.
Note that it is also quite usual to consider the absolute value of disparity, ∣∣∆LT,a,a′(h)∣∣ indicating whether there is equality or not (and magnitude thereof), rather than giving a sign (which relies more on how the baseline category has been chosen). Indeed, trivially, disparity is asymmetric whereas the absolute disparity is symmetric.
It is therefore important to be able to establish the learnability of this widely used metric, which we do in the following proposition. Proposition 7. With probability at least 1− δ, it holds
sup h∈H ∣∣∆LD,a,a′(h)−∆LS,a,a′(h)∣∣ ≤ 2 {R(` ◦ H ◦ Na) +R(` ◦ H ◦ Na′)} +B √ 2 log ( 4 δ ) na + na′ [√ na + na′ na + √ na + na′ na′ ] .
Proof. We start by observing that by sub-additivity of the sup, we have
sup h∈H ∣∣∆LD,a,a′(h)−∆LS,a,a′(h)∣∣ ≤ sup h∈H |LD,a(h)− LS,a(h)|+ sup h∈H |LD,a′(h)− LS,a′(h)| .
We can then conlude thanks to Proposition 1 and the union bound.
What this upper bound suggests is that in order to learn about disparity, one has to learn the two categories a and a′. If one category has either a large Rademacher complexity or a low count, the upper bound will increase. This result enables us to derive bounds on quantities of interest such as∣∣∆LD,a,a′(h∗S)−∆LS,a,a′(h∗S)∣∣ that follows directly from Proposition 7. A.2 EXAMPLE 2: LEARNING BIAS
In this Section, we understand bias in a very specific (and non-fairness related) way, as in Chen et al. (2018). In short, one can consider bias –in this context– as the difference between the loss incurred by category a when the classifier is determined by minimising the loss function over the entire sample and the loss in category a when the optimal classifier is derived on a standalone basis (i.e., the classifier explicitly takes into the account the attribute a).
If it is possible to use the characteristics s directly in the model, then one can calibrate an optimal classifier on each category:
h∗D(x, s) = C∑ a=1 1{s=a}h ∗ D,a(x). (16)
However, we usually do not have access to the characteristic s or cannot include it as a feature (for instance to avoid disparate treatment), so that –in general– hD(x, s) = h∗D(x) for all s = 1, · · · , C. Consequently, we can define the Bayes gap as the difference between the loss obtained between the Definition 5. The Bayes gap for category a is given by
ΓT,a = LT,a(h ∗ S)− LT,a(h∗S,a), (17)
for T ∈ {D,S}.
In particular, ΓS,a ≥ 0. Γ·,a represents the added loss incurred by category a due to the consideration of other categories while selecting the classifier h. Proposition 8. The true Bayes gap, ΓD,a = LD,a(h∗S)− LD,a(h∗S,a) can be learnt as
|ΓD,a − ΓS,a| ≤ 4R(` ◦ H ◦ Na) + 2B
√ 2 log(2/δ)
2na , (18)
with probability at least 1− δ.
Proof. The proof is fairly straightforward and simply decomposes the Bayes gap in terms of easier building blocks:
LD,a(h ∗ S)− LD,a(h∗S,a) = LD,a(h∗S)− LS,a(h∗S) + LS,a(h∗S)− LS,a(h∗S,a)
+LS,a(h ∗ S,a)− LD,a(h∗S,a),
leading to ΓD,a − ΓS,a = LD,a(h∗S)− LS,a(h∗S) + LS,a(h∗S,a)− LD,a(h∗S,a).
We thus obtain that
|ΓD,a − ΓS,a| ≤ 2 sup h∈H |LD,a(h)− LS,a(h)|
≤ 4R(` ◦ H ◦ Na) + 2B
√ 2 log(2/δ)
2na ,
where the second inequality holds with probability at least 1− δ by Proposition 1.

heading: B OUT-OF-SAMPLE VARIANCE SCALING
text: In this Section, we consider a surrogate example to illustrate some real-world consequences of Theorem 2. The behaviour of a number of debiasing methods, both in- and out-of-sample, has been studied on real and surrogate data in the literature (Zafar et al. (2017); Agrawal et al. (2020); Oneto et al. (2020) for instance), we thus only provide an illustration of our result on a simple test case, to highlight the role played by sampling variance in dealing with fairness metrics. In keeping with the previous section, we suppose that we have chosen a given classifier ŷ = h(x, s) and are now considering its statistical properties on a (large) out-of-sample dataset.
B.1 PREDICTIVE PARITY AND ITS LIMITING VARIANCE
In our simplified experimental setup, we consider C = 2, and set `0 = 0 with λ = 1, i.e., we only look at a fairness criterion, and choose a ratio τPP linked to predictive parity (see Table 1):
φD(h) = τD,PP := P(ŷ = 1|y = 1, s = 1) P(ŷ = 1|y = 1, s = 2) . (19)
The perfectly fair case corresponds to τD,PP = 1. We also define the corresponding sample version of this criterion, using the samples N+a , a = 1, 2:
φS(h) = τS,PP =
1 n+1 ∑ i∈N+1
1{ŷi=1} 1 n+2 ∑ i∈N+2 1{ŷi=1} . (20)
In this case, one can compute Vlim(h) directly as
Vlim(h) = 1− P(ŷ = 1|y = 1, s = 1) P(ŷ = 1|y = 1, s = 1) 1 π1 + 1− P(ŷ = 1|y = 1, s = 2) P(ŷ = 1|y = 1, s = 2) 1 π2 , (21)
where π1 = p+1
p+1 +p + 2
and π2 = 1− π1 = p + 2
p+1 +p + 2
.
B.2 SIMULATION SET-UP AND RESULTS
In our simulations, we use the fixed values P(ŷ = 1|y = 1, s = 1) = 0.95 and P(ŷ = 1|y = 1, s = 2) = 0.99, leading to τD,PP = 0.96. We vary the parameters m = n+1 + n + 2 , which represents the overall sample size available to us to compute τS,PP, and π1, which is the effective proportion of class 1 versus class 2. Throughout this exercise, we simulate N = 1000 times the experiment. Our baseline case is m = 1, 000 and π1 = 10%.
From Figure 4 (a), one recovers the usual behaviour due to sample size: asm increases, the empirical distribution of τS,PP becomes more peaked. A small sample size (such as m = 100) would yield poor accuracy and one can observe that the density is actually bi-modal.
The behaviour with respect to sample size can also be checked by comparing the empirical distribution of τ (k) S,PP−τD,PP√
Vlim(h) , where k = 1, · · · , N is the experiment run, with a standard Gaussian distribution,
as predicted by Proposition 2. It can be seen in Figure 5 that there is a good adequacy between both distributions.
The most salient feature, however, is the behaviour of τS,PP’s distribution with respect to category probability, as described in Figure 4 (b), where one can see that as the sample becomes balanced, the variance of the estimator τS,PP decreases. When π1 is very small, say 1%, one recovers the bi-modal distribution that comes with a small sample.
B.3 KEY OBSERVATION
In a nutshell, low sample sizes and class imbalance can lead to poor generalisation. Indeed, by considering the cases m = 100, π1 = 10% and m = 1000, π1 = 1%, it is clear that one cannot draw any conclusion regarding the presence of bias nor in terms of which group is the advantaged group. Bi-modality is a particularly interesting characteristic of the empirical distribution: there is a mode strictly below 1 and a mode strictly above 1.

heading: C PROOFS
text: C.1 PROOF OF PROPOSITION 3
Proposition 3 Under the assumption that φ isKφ-Lipschitz, it holds, with probability at least 1−δ, that
sup h∈H |φD(h)− φS(h)| ≤ 2Kφ C∑ a=1 R(`+ ◦ H ◦ N+a ) +R(`− ◦ H ◦ N−a )
+KφBZS
√ 2 log 4Cδ
n .
with ZS := ∑C a=1 √ n n+a + √ n n−a .
Proof. Using the hypothesis that φ is Kφ-Lipschitz, it comes
|φD(h)− φS(h)| ≤ Kφ C∑ a=1 ∣∣∣L+D,a(h)− L+S,a(h)∣∣∣+ ∣∣∣L−D,a(h)− L−S,a(h)∣∣∣ For any δ′ ∈ (0, 1) and any a = 1, · · · , C it holds
sup h∈H
∣∣∣L±D,a(h)− L±S,a(h)∣∣∣ ≤ 2R(`± ◦ H ◦ N±a ) +B √ 2 log 2δ′
n±a ,
whereby
sup h∈H |φD(h)− φS(h)| ≤ 2Kφ C∑ a=1 R(`+ ◦ H ◦ N+a ) +R(`− ◦ H ◦ N−a )
+KφB C∑ a=1
√ 2 log 2δ′
n+a +
√ 2 log 2δ′
n−a ,
with probability at least 1 − 2Cδ′, thanks to the union bound. To have 1 − δ = 1 − 2Cδ′, one can simply pick δ′ = δ/(2C). Now, we can write the last term as
C∑ a=1
√ 2 log 2δ′
n+a +
√ 2 log 2δ′
n−a =
√ 2 log 2δ′
n C∑ a=1 √ n n+a + √ n n−a
= ZS
√ 2 log 2δ′
n ,
hence the final result.
C.2 PROOF OF THEOREM 1
Theorem 1 With probability at least 1− δ, it holds
0 ≤ LD(h∗S)− LD(h∗D) ≤ UBS +B ( 1 + λZSK φ ) 3√
2
√ log(16C/δ)
n , (22)
Proof. For the sake of clarity, we divide the proof into different steps.
Step 1. We can start by rewriting
LD(h∗S)− LD(h∗D) = LD(h∗S)− LS(h∗S) + LS(h∗S)− LS(h∗D) + LS(h∗D)− LD(h∗D) ≤ LD(h∗S)− LS(h∗S) + LS(h∗D)− LD(h∗D),
since, by definition, LS(h∗S)− LS(h∗D) ≤ 0. Step 2. Now, LD(h∗S) − LS(h∗S) ≤ suph∈H |LD(h)− LS(h)| on the one hand, and, on the other hand, we have
|LS(h∗D)− LD(h∗D)| ≤ ∣∣L0S(h∗D)− L0D(h∗D)∣∣ +λKφ
C∑ a=1 {∣∣∣L+D,a(h∗D)− L+S,a(h∗D)∣∣∣+ ∣∣∣L−D,a(h∗D)− L−S,a(h∗D)∣∣∣} . Step 3. The key insight is to notice that the right-hand side only involves h∗D, which does not depend on the sample S, hence one can apply the Hoeffding inequality directly. Thus, by Hoeffding’s inequality, for each a, with probability at least 1− δ′′,
∣∣∣L±D,a(h∗D)− L±S,a(h∗D)∣∣∣ ≤ B √ log(2/δ′′)
2n±a .
Similarly, with probability at least 1− δ′′,
∣∣L0S(h∗D)− L0D(h∗D)∣∣ ≤ B √ log(2/δ′′)
2n .
We can then infer that with probability at least 1− (2C + 1)δ′′
|LS(h∗D)− LD(h∗D)| ≤ B √ log(2/δ′)
2n +λBKφ C∑ a=1
√ log(2/δ′′)
2n+a +
√ log(2/δ′′)
2n−a
≤ B ( 1 + λZSK φ )√ log(2/δ′′)
2n .
Step 4. From the previous proposition, it comes that with probability at least 1− δ′
sup h∈H |LD(h)− LS(h)| ≤ UBS +B
( 1 + λZSK φ )√2 log(8C/δ′)
n .
Finally, by choosing δ′ = δ/2 and δ′′ = δ/(2(2C + 1)),
LD(h∗S)− LD(h∗D) ≤ UBS +B ( 1 + λZSK
φ ) [√2 log(16C/δ)
n +
√ log(4(2C + 1)/δ)
2n
]
≤ UBS +B ( 1 + λZSK φ ) 3√
2
√ log(16C/δ)
n ,
with probability at least 1− δ.
C.3 PROOF OF THEOREM 2
Theorem 2 Let h ∈ H, under the assumption that p±a > 0 for all a, and that ∇φD(h) exists and is non-zero, we have the following convergence in distribution
√ n (LS(h)− LD(h))
d−−−−−→ n→+∞ N (0,Vlim(h)) , (23)
where Vlim(h) = C∑ a=1 p+a ( σ0,+a )2 + λ2 (K+a ) 2 p+a ( σ+a )2 + 2λK+a cov + a ( `0(h, z), `+(h, z) ) +
C∑ a=1 p−a ( σ0,−a )2 + λ2 (K−a ) 2 p−a ( σ−a )2 + 2λK−a cov − a ( `0(h, z), `−(h, z) ) +
C∑ a=1 p+a (1− p+a ) ( L0,+D,a )2 + p−a (1− p−a ) ( L0,−D,a )2 − 2p+a p−a L 0,+ D,aL 0,− D,a
− ∑ a6=a′ ( p+a p + a′L 0,+ D,aL 0,+ D,a′ + p − a p − a′L 0,− D,aL 0,− D,a′
+p+a p − a′L 0,+ D,aL 0,− D,a′ + p − a p + a′L 0,− D,aL 0,+ D,a′
)
Proof. For the sake of clarity, we divide this simple (but slightly tedious) proof into multiple steps. In this proof, we make the assumption that φ is differentiable with continuous gradient; this is not necessary but simplifies the exposition. The reader is referred to DasGupta (2008) for details regarding the delta method, the central limit theorem and different types of convergence.
Step 1. We start by rewriting the difference between both true and empirical trade-offs LS and LD for a given h ∈ H. Thanks to the Taylor formula, there exists ξ ∈ [0, 1] such that
φS(h)− φD(h) = φ(L±S (h))− φ(L ± D(h))
= ∇φ(ξL±D(h) + (1− ξ)L ± S (h)) T ( L±S (h)− L ± D(h) ) We denote K±S,a the partial differential of φ with respect to x ± a , i.e., K ± S,a = ∂x±a φ(ξL ± D(h) + (1−
ξ)L±S (h)) T ( L±S (h)− L ± D(h) ) . Some algebra then yields
√ n (LS(h)− LD(h))
= C∑ a=1 √ n n+a √ n+a ( p+a [ L0,+S,a (h)− L 0,+ D,a(h) ] + λK+S,a [ L+S,a(h)− L + D,a(h) ]) +
C∑ a=1 √ n n−a √ n−a ( p−a [ L0,−S,a (h)− L 0,− D,a(h) ] + λK−S,a [ L−S,a(h)− L − D,a(h) ]) +
C∑ a=1 √ n ( n+a n − p+a ) L0,+S,a (h) + C∑ a=1 √ n ( n−a n − p−a ) L0,−S,a (h).
Step 2. Since limn→+∞ n±a n = p ± a > 0 almost surely, this implies trivially that limn→+∞ n ± a = +∞ almost surely, for any a. We now recall that, thanks to the continuous mapping theorem, it holds that for any n±a , limn→+∞ √ n/n±a = 1/ √ p±a almost surely. Finally, limn→+∞K±S,a = K ± D,a almost surely, since∇φ is continuous and limn→+∞ L±S (h) = L ± D(h) almost surely. Step 3. Let us now consider each term a± separately.√ n±a ( p±a [ L0,±S,a (h)− L 0,± D,a(h) ] + λK±S,a [ L±S,a(h)− L ± D,a(h)
]) = √ n±a ([ p±a L 0,± S,a (h) + λK ± D,aL ± S,a(h) ] − [ p±a L 0,± D,a(h) + λK ± D,aL ± D,a(h)
]) + λ ( K±S,a −K ± D,a )√ n±a [ L±S,a(h)− L ± D,a(h) ] .
By the Central Limit Theorem (CLT), √ n±a [ L±S,a(h)− L ± D,a(h) ] d−−−−−→
n→+∞ N(0, [σ±a ] 2), but since( K±S,a −K ± D,a ) a.s.−−−−−→
n→+∞ 0, the whole term
( K±S,a −K ± D,a )√ n±a [ L±S,a(h)− L ± D,a(h) ] goes to 0
almost surely.
All that remains is to apply the CLT to√ n±a ([ p±a L 0,± S,a (h) + λK ± D,aL ± S,a(h) ] − [ p±a L 0,± D,a(h) + λK ± D,aL ± D,a(h) ]) ,
and notice that Vs=a,y=±1 [ p±a ` 0,±(h, z) + λK±D,a` ±(h, z) ] = [p±a ] 2[σ0,±a ] 2 + λ2[K±D,a] 2[σ±a ] 2 + 2p±a λK ± D,acov ± a ( `0(h, z), `±(h, z) ) .
Note that since each data point in the sample is independent, the CLT can be applied term by term (i.e., all a±’s have independent limiting distributions).
Step 4. To finish the proof, it simply remains to consider the adjustments due to observing empirical proportions rather than the true class probabilities. We thus need to consider the limiting distribution of the vector √ n ( n±a n − p ± a ) ±,a=1,··· ,C . But this is simply the limiting distribution of empirical proportions in repeated trials of a multinoulli distribution, hence the result.
Let us point out that the non-vanishing assumption on the gradient of the fairness loss function φ can be relaxed, but leads to the need for a higher-order delta method (see DasGupta (2008)).

Review summaries:
This paper establishes the guarantee for the generalization of fairness-aware learning in binary classification under PAC-learning and a more practical asymptotic framework. Through the derived theorem, authors conclude that low sample size and class balance lead to the poor generalization of fairness-aware learning, and the need for a sample-efficient method is also argued. The experimental results using real data are aligned with the theorem, emphasizing the validity of theorem.

The paper provides an analysis of fairness via regularizing a loss function with a suitably selected fairness measure / metric. In particular, the paper analysis this under a PAC learning setting and a sample limit (asymptotic) setting. A majority of the paper focuses on the PAC setting, where Rademacher complexity bounds are made and analysed. Some experiments are included.