On Learning with Fairness Trade-Offs
Authors: Francois Buet-Golfouse
Venue: ICLR 2022 Submitted (2022)
Keywords: fairness
statistical learning
PAC
social welfare

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. 

Under review as a conference paper at ICLR 2022
ON LEARNING WITH FAIRNESS TRADE-OFFS
Anonymous authors Paper under double-blind review
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 mathematical framework 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 at- tributes), encompassing partial de-biasing. We do so by adopting two different but complementary viewpoints: first, consider PAC-type setup and derive proba- bilistic upper bounds involving sample-only information; second, we leverage an asymptotic framework to derive closed-form limiting distribution for the differ- ence between the empirical trade-off and the true trade-off. While these results provide guarantees for learning fairness metries 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- samples is hard, and a simple numerical experiment shows that it can lead to spurious results.
tackle
INTRODUCTION
Reducing bias an algorithm requires a number of steps; first, specify the fairness definitions (and thus fairness metries) that apply, second, encode them with penalty discrepancy between outcomes and the perfect fairness scenario. third, choose the trade-off between the original statistical goal and fairness constraints, and, fourth, pick method 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 a series of impossibility theorems (Kleinberg et al. (2017): Pleiss al. 2017); Chouldechoval (2017); Kim et al. (2020)). Note that these results apply not only to fairness- trade-offs.
to measure the
performance but also fairness-fairee
Research has recently been undertaken to tackle specifically Icarnability and generalisation in fairnes--related problems. particular, Oneto al. (2020p; Oneto et al. (2020) derive provable probabilistic upper bounds in fairness setting where one estimates an overall statistical loss and monitors disparities across categories. In In|Chen et al. (2018), the authors have applied bias- variana decomposition techniques to disentangle the sources of unfairness in classifier. While this is not directly related to this present work, the principle risk decomposability turns out to be fruitful in both setups. Finally, in Agrawal et al. (2020), limiting distribution is established in the simple case where there a partial requirement involving a fairness metric with two categories.
Our contributions. as PAC inequalities and the central limit theorem to the problem of learning under faimess con- straints:
The novelty of our work consists of the application of known techniques such
First, develop PAC framework for faimess trade-offs, generalising results from Donini
et al. (0188); Oneto et al. 22020) and tackling explicitly partial debiasing (see Kim et al.
(2020): Agrawal al. (0200).
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 erucial role. We

---

Under review as a conference paper at ICLR 2022
also build on Agrawal al. (2020) and develop asymptotic framework with 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, ex- pressed 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 indeed diffi- cult.
2 FAIRNESS METRICS AND LOSS FUNCTIONS
2.1 SET-UP AND DEFINITIONS
In this article, we define 1....., C be categorical (protected) attribute, x X IR to be set of non- non-proterd proteecotedd features excluding y E 1, +11 is binary outcome variable and y { 1, +1} is an estimator for y. Finally, 2 (x, y.. Note that is derived from a learner h E H. where H 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 a statistical performance objective, L plus fairness loss function d. The trade-off is tuned by a hyper-parameter À 2 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 fairness trade-off is defined
LD(h) (h) + No (b.,(() -.D.o(().LD..o())
(b) (n)))))
where we have used the standard notations (see Shalev-Shwartz Ben-David 2014
(h) E 2))
(h) E (h, 2)|s a, =1
(h) = [ 2)) a. a,y= --1 -1]
and the vector notation (h) (t), (
for some func-
tions E", f and e-
Remark 1. In the whole paper, we assume that there exists uniform bound B > 0 on all functions i.e., |((h,2)) S B for all h and z. l refers to any such function in what follows.
Let us detail two particular cases. If minimisation problem. If 0 = 0 or À + +oc, then the trade-off becomes a faimess constraint.
O, then the overall objective boils down to the usual risk
We are now in a position define the empirical counterpart by considering the empirical distribution rather than the true distribution. With the additional notations V== = {i E (1.... : :s; =
+1}, W = n the corresponding sample versions can be deñned as (g L5 (h) no
E (h, 22),
ΣiENs e+ (h, 24) and L (h) = 1 ELEN= l (h, 2), where n. = nt + n n.
E Na. leading to
Cs(h) (b))) + X (L)
For the sake of simplicity, we will generally refer to oi o(L (h)) (T for T = D,S.
2.2 FAIRNESS DEFINITIONS AND METRICS
One can find multiple technical definitions 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
We note that all faimess metrics considered here can be expressed probabilities, hence on the expectation indicator variables. These fall within our framework. However, this framework can also handle other types of functions.
equality requirement
2

---

Under review as a conference paper at ICLR 2022
Fairness metric
Reference
Equality requirement
Equalized false omission rate
[Berk al. 2018
Ply 1
1,
PPy
10
Predictive parity
Chouldechova
2017
Ply 1
1,8 ④)
PPy
11
Demographic parity
(Calders & Verwer
2010
18 a)
Equalized false negative rate
(Chouldcchova
2017
P(y -yy
1,8
=F -l
Predictive equality
Chouldechova
2017
Ply = 1y
1,s a)
-M(
1y
Equality of opportunity
Hardt ct al.
2016
P(j 1ly 1 1,5 a P(
= 1y 1)
Equalized odds
(Hardi et al.
2016
P(ù 11y
P( 1y =w
Table I: Frequent fairness definitions.
2.3 FAIRNESS LOSS FUNCTIONS
In addition to picking one or multiple fairness definitions, we need to specify & to measure the discrepancy from perfect fairness, the ideal case.
first approach, similar the Calders-Verre gap (Calders & Verwer 2010). consists of looking at the discrepancy between two categories and a':
Ta (h) = (h) a
for T E 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. 22020), and define & as the sum of all absolute discrepancies across categories:
(L) - {11
Litar
LT.a
azia
for T S. Notice that, thanks to the reverse triangle inequality, the function & is Lipschitz continuous. One could naturally weigh the various contributions this fairness function and use another norm than L'. Other functions involving ratios relative differences, are also possible.
Finally, in Kim et al. 2020), the authors consider a convex combination multiple loss functions M):
(L*
Agoli (L(
Note that if the 600's Lipschitz-continuon (with respect to the loss vector (h)), with spective Lipschitz constant K(J), then the overall loss & is itself Lipschitz-continuous with constant K - Xy
LEARNING FAIRNESS TRADE-OFFS
In this section, consider the learning problem from different angles. We start by considering the statistical loss T 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 fairnsss part per se, namely study the generalisation properties of (s)... Finally, bring the together and derive probabilistic upper bounds on fairness trade-off generalisation.
3.1 LEARNING THE STATISTICAL LOSS
Let us first focus on the statistical component of the loss, i.c., L for T DS. Much this paper is based theory of bounds derived from Rademacher complexities, introduced in Bartlett & Mendelson 2003)) and surveyed in Boucheron, Stéphane et al. (200)). Recent textbooks such Shalee-Shward & Ben-Den 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,
SStéhhane al. (2005):
3

---

Under review as a conference paper at ICLR 2022
Definition 2. The Rademacher complexity (or average) of function e is given by
R(e o H o S) = E
sup NEW
Σ 1=1
ore (h, zi)
(3)
Note that definitions can slightly vary (depending for instance on the presence or absence of the absolute value the definition), but all downstream results are qualitatively similar, up to some multiplicative constants.
To make this more concrete, we can consider simple (but usual) case (as describe in Shalev- Shwartz & Ben-David (2014). We suppose that almost surely ||x||2 I R. In addition, if we let H {w; w I Ht') } and assume that the loss function of the type E(w, (x, (w" v), where |p| bounded by and is L'ipsshhi,,,, then, almost surely.
LARR' nn
Rademacher complexities are key to establishing learnability bounds and lead fundamental results in statistical learning theory. In particular, we will make use of standard result (see BBoucheonn Stéphane et al. (2005)..
Proposition 1. With probability at least 1 holds
2 log
sup (D(hh) Ls(h)) 28(6 H HoS) 2 + BB 7
kEH
It will also be useful introduce conditional Rademacher complexities that will be used throughout this paper. In particular, since have partition of the sample in terms of categories S U Na. we can consider the Rademacher complexity of that particular sample:
R(e H. o N.) = E sup NEW
Σ oil (h, zi)
(5)
REN
Lemma 1. The sample Rademacher complexity can be bounded from above by the weighted sum of conditional Rademacher complexities:
Th R(l H No).
R(E o H <
(6)
- where R(Eo Ho. N.) suptER n.
EiEN, o, oh, 2:)]]
Proof.
This comes directly from the sub-additivity of the absolute value and the supremum.
One can further interpret the non-negative gap Ee as R(L o H N..) R(e S) as diver- sification benefit amongst categories. Finally, this leads us to a proposition leveraging our results so far:
Proposition 2. With probability at least 1
(b( (h)) < hER
nh R(C No -B 71
log 2
sup
n
3.2 LEARNING FAIRNESS REQUIREMENTS
Let the fairness learning part; before, would like to find bound the distribution fairness loss given the sample faimess loss, i.e., a probabilistic bound on the difference @D (b)).
4

---

Under review as a conference paper at ICLR 2022
Proposition 3. Under the assumption that ó is -ipsschh,,,, holds, with probability at least 1 1-6,
and where Zs = Da=1 v
that
sup (bb(1)) -ss(1)) NEW
s 2k
R(Ct H HoNa) + R o HoN
2 log 4C d
+K
The proof can be found in Appendix C.I and the role played by Zs is investigated in Section
3.3
SIMULTANEOUS LEARNING OF STATISTICAL PERFORMANCE AND FAIRNESS
We have established probabilistic bounds on both the statistical performance criterion and the fair- ness penalty. However, we wish 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.
3.3. BOUNDING LOSS AND FAIRNESS
First, we may wish to determine a probabilistic upper bound on (h) (h) and ΦD (s())) jointly. By simple application of the union bound, we obtain the following result: Proposition 4. With probability at least - 6, it holds jointly that
2 log
sup (h) (h)l
2R( H) B
n
sup (kD(h) - ds(h) keh
$ 2k Σ
Riet o H N + R(E ooo
6=1
2 log
+K BZs
71
3.3.2 BOUNDING THE TRADE-OFF
As mentioned above, the existence of various impossibility results and the empirical findings show- ing 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 gen- eralisation properties that such objectives can lead to. We can perform a similar analysis on the trade-off objective (h(h) by using the same arguments to get upper bound on this objective. Proposition 5. With probability at least
holds
log
sup [hp(h) Ls(h) s 2R( H. + BV kEH
+2ΛK
RiEt Ho R(E oHoNa
2 2log sC 8
+\K +AK*BZs1
n
n R(C - cHoNt nhe Te HoNo)
n
+ HoN* + RK
oHo oK
2 2lg((80/8)
+B (1+ (1+*K*Zs)
n
5

---

Under review as a conference paper at ICLR 2022
The upper bound be understood the sum of individual contributions plus the usual O Vlo((1/0/// 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 hy FkEH (h) for T E {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 fairness as it provides some guarantees on how far the actual optimal trade-off is from the one we would ob- tain by picking the optimum computed on the sample S. This result provides a faimess pendant to the usual in statistical learning (see for instance Theorem 26.5 in Shalev-Shwartz & Ben- David (2014))
Theorem 1, With probability at least 6, it holds
log
-n 0 S CD S UBs + B (1+ x1+s)
(8)
where hi FEen (h) for T (D, and UBs -2 o o R(E {
( nd R(C HoNN
R(C
H o NoN RK+ e H NoN+)
The proof is given Appendix What particularly interesting about this result is the fact that the upper bound remains the same as in Proposition and only the O (Vlog(1/)//r) factor changes. Let us point out that this result is practical in nature in the sense that one would use hi in practice but would still look for out-of sample generalisation, hence the importance of the term CD(hs).
4 (SOME) PRACTICAL CONSEQUENCES OF PAC FOR FAIRNESS TRADE-OFFS
4.1 DECOMPOSING UPPER BOUNDS ON GENERALISATION
One is led to decompose the overall loss in terms of each category's contributions to the overall learning upper bound.
Definition The (half-) Jcontribution denoted by Ry.- of each category 1,.., C, to the fairnsss trade-off learning upper bound is
R(C HoN The RC HoNT) RAK*R( HoN AK a HoNN.).
n n
RN.
This structure is quite interesting as it shows that the first two terms representing contri- butions 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 will not affect the overall average loss. On the other hand, the contributions coming from the fairness part are unweighted. In this case, low sample size would usually lead to higher Rademacher complexity.
Remark 2.
Now, RN, can be decomposed into finer components:
RN, RN. + RN + -RY. + Ry..
with obvious notations. One then determine the contributions coming from the union of certain categories or of positives or negatives.
4.2 Zs AS SAMPLE CONCENTRATION
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 initial minimisation exercise by including the upper bound to the sample component, i.c., optimise (D) (h).
practical check, but also suggests way of amending the

---

Under review as a conference paper at ICLR 2022
Second, a quantity that is ubiquitous in our analysis (see, for instance, Theorem D. is Zs n. As noticed previously, this measure of concentration within the sam- E. + nia ple 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 Zg can be expressed in terms of the empirical class sample propor- tions:
Zs Σ (Pa) (P.) (P.)
2C
(10)
VM-1/2(D)
I of the vector P ( In addition, under the assump- tion that n 2 for all 1, ,C and a 20 1, the following inequality holds:
where Ma (p) is the a-gennralised mean
8/2))/222 & Zs - (2C 11V=+ V (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 function of the number of categories, which is problematic especially tackle intersectionality. Second, the upper bound on Zs/ (nn) converges to 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 given dataset.
ASYMPTOTIC REGIME
One of the possible issues using PAC learning in practice is the fact that tends to consider worst- case scenarios (e.g., by deriving probabilistic inequalities over whole space of possible classifiers). To mitigate this possible drawback, we adopt a very different viewpoint and set ourselves work which generalises Proposition 1 in AArawal et al. (2020). Our objective is to derive limiting distribution for the rescaled fairness trade-off after having trained one particular classifier, which 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- modelling, this also has the benefit of allowing for closed-form results (as opposed upper bounds in PAC learning). Both approaches are -as will be shown- very complementary.
frame-
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 indepen- dently and identically distributed datapoints, according to mixture distribution with probability weights p Conditional
and y = +1, we can then draw All draws are independent. Let us introduce some additional notation: the intra-category variances are given by (o V,=a.y=11 (h, ) V (h, Furthermore, K (h), i.e.,
D.a is the entry corresponding to a in the gradient (h) We can now introduce our main result, which extends Agrawal et al. (2020) to a multi-category and multi-dimensie dimensiionl setting.
Theorem 2. Let E H. under mild assumptions, we have the following convergence distribution
(Cs(h) - Ln(h))
m+- مه N (0, Vim (h)),
(12)
where
) (o covariance terms
Vimll [h]
Σ
Pa (oa )
(13)
pā
The exact assumptions and the proof can found in Appendix B. In a nutshell, the variance of the limiting trade-off distribution is the addition of
'The a-generalised mean of K numbers 21,-." FK is given by ( EK x%) "
1/a

---

Under review as a conference paper at ICLR 2022
The sum of intra-category 2 losses weighted by their true probabilities po:
The sum of intra-category faimess & losses weighted by their inverse probabilities p as in the uniform convergence framework. addition, the constant )² represents the sensitivity of the fairness loss function & and is bounded from above by [ in these case where K -iisschhi 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 prob- ability Pa may not impact the variance of the overall statistical loss but may lead to a very poor understanding of fairness trade-offs.
6 EXPERIMENTAL RESULTS
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:
1 1i0
min BER TE
Σ E(v, xx; B) +
E Xzi B)
(ug xx:
(14)
where é is the logistic loss function and the groups 0 and correspond to two different classes of protected attribute. We have considered three datasets with binary protected attributes and binary outcomes, shown in Table and applied standard 80-20 train-test split.
Dataset Adult
Reference
Protected attribute
Binary outcome
Dua & Graff 2017
sex
income exceeds 50SK/year default payment next month
Loan defaults
T-Cheng Ych 2009
sex
German eredit
Dua & Graff 20117
sex
creditability
Table 2: Data sets description
Figures 1 and 2
illustrate the trade off between average loss and disparity for range of values.
On the train test (Figure D there is clear dependence between the value of X and the respective average loss and disparity between groups. As expected, 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.
6.1 IN-SAMPLE RESULTS
Adsi Tain
0.5
0325
011
2.000
0.0
004
0000
842
2300
Average Co
Figure 1: Trade off between disparity and average loss on adult, german credit, and loan defaults data sets. Each colour corresponds to different initialisation, while the symbol's 's size corresponds to the weight À on disparity in the overall loss function. Results are measures on the train set.
SSpccifically (0.01, 0.05, 0.1, 0.5, 1,5, 10. 50. 500). Each distinct color represents different initial- ization, while the size of the point monotonically increasing function of the respective X.
8

---

Under review as a conference paper at ICLR 2022
6.2
OUT-OF-SAMPLE RESULTS
German crudit cate.
0422
0.241
698
0432
038
638
04p
8440
Nernay Ice
Garaace bys
Figure 2: Trade-off' between disparity and average loss Adult, German credit, and Loan defaults datasets. Each colour corresponds to a different initialisation, while the symbol's size corresponds to the weight À disparity in the overall loss function. Results are measured on the test set.
6.3 STANDARD DEVIATION SCALING
We experiment with class imbalance see how the solution 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
0.07
ABLFt doto lost st
Garman, credit data Text eet
Lass ti catz. lost set
68225
0m
depeety
0.55
000
0.99
63000
001
020
6305
3.5
12.
23.5
13.5
100 12%
Figure 3: Fairness uncertainty versus class imbalance ratio in protected characteristic on Adult, German credit, and Loan defaults datasets. Results are measured on the test set.
7 CONCLUSION
The analysis that we have conducted from two different angles, namely learning with uniform con- vergence and asymptotics, leads to the same overall qualitative assessment. While have derived probabilistic upper bounds to prove learning guarantees on the one hand and convergence to lim- iting distribution the other, striking feature of learning faimeess trade-offs is the fundamental difference of regimes between the usual statistical performance criterion measured on the whole sample and the faimess 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 fine understanding of differences across conditional distributions. Intuitively, in the usual case of an overall statistical loss function, a category only represents a small portion of the sample, then it also only constitutes 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 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.
'Here, 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 hold black line is least square estimate using data points from all sceds. X fixed 50.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Ashrya Agrawal, Florian Pfisterer, Bernd Bischl, Jiahao Chen, Srijan Sood, Sameena Shah, Francois Buet-Golfouse, Bilal A Mateen, and Sebastian Vollmer. Debiasing classifiers: is reality at variance with expectation?, 2020.
Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 3(mull):463-4822 March 2003. ISSN 1532-4435.
Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth. Fairness in criminal justice risk assessments: The state of the art. Sociological Methods & Research, August 2018. doi: 10.177700491241188855555
Boucheron, Stéphane, Bousquet, Olivier, and Lugosi, Gábor. Theory of classification: survey of some recent advances. ESAIM: PS, 9:323-374 2005, doi: 10. 10.1051/ps:20050188 URL https:
7/doi.org/Ii 1ttp://10..00111s:::0000000
Toon Calders and Sicco Verwer. Three naive bayes approaches for discrimination classification. Data Mining and Knowledge Discovery, 21(2):277-29) 2010. doi: 00007//10111-000-1111
Irene Y. Chen, Fredrik D. Johansson, and David Sontag. Why is my classifier discriminatory? In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS'18, 18, pp. 3543-3554 Red Hook, NY, USA, 2018. Curran Associates Inc.
Jiahao Chen, Nathan Kallus, Xiaojie Mao. Geoffry Svacha, and Madeleine Udell. Fairness under unawareness: Assessing disparity when protected class unobserved. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* '19, pp. 339-348. New York, NY. USA, 2019. Association for Computing Machinery. ISBN 978 9781450361255. doi: 10.1145/ 3287560.3287594.
Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big Data, 5(2):153-163, June 2017. doi: 00.1089/bi.22116.044
Anirban DasGupta. Asymptotic Theory of Statistics and Probability. Springer Texts in Statistics. Springer, 1st edition, March 2008. ISBN 0387759700.
Michele Donini, Luca Oneto, Shai Ben-David, John S Shawe-Taylor, and Massimil- iano Pontil. Empirical risk minimization under fairness constraints. In S. Ben- gio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Asso- ciates, Inc., 2018. URL httpss//pproceeedngg... neurips......................... wttp:uuipss..ppppppree/e/e cctpppapeer/21///illee//// 3Sccecoofe5033TTTtE59aa533333333
pdf
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL httt:://rcciiee.
ics. www.ueu/.mmm
Moritz Hardt, Eric Price, and Nathan Srebro. Equality of opportunity in supervised leam- ing. Advances in Neural Information Processing Systems, 29:3323-3331, December doi: 10.5555211533223555499. URL httpss:/paperss nips cc/paper/ 6374
2016.
Che-hui Lien I-Cheng Yeh. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert Systems with Applications, (36), 2009. doi:
Joon Sik Kim, Jiahao Chen, and Ameet Talwalkar. Model-agnostic characterization of fairness trade-offs. Proceedings of the International Conference on Machine Learning, volume 37, pp. 2020.
Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-off' in the fair deter- mination risk scores. In Christos H. Papadimitriou (ed.). Proceedings of the Sth Innovations in Theoretical Computer Science Conference, volume 67 of Leibniz International Proceedings in Informatics (LIPIcs). Dagstubl, Germany, 2017. Schloss Dagstubl-Leibnizz Zentrum fuer Infor-
matik. doi:
10

---

Under review as a conference paper at ICLR 2022
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning- The MIT Press, 2012. ISBN 026201825X.
Arvind Narayanan. Translation tutorial: 21 faimess definitions and their politics. In Proceedings of the Conference Fairness, Accountability and Transparency, FAT 18, New York, USA, 2018.
L. Oneto, M. Donini, M. Pontil, and A. Maurer. learning fair and transferable representations with theoretical guarantees. In 2020 IEEE 7th International Conference Data Science and Advanced Analytics (DSAA), 30-39, 2020. doi: 10.1 10.1099/SSA4499112200.00000
Luca Oneto, Michele Donini, Massimiliano Pontil, and John Shawe- Taylor Randomized learning and generalization of fair and private classifiers: From pac-bayes to stability and differential privacy. Neurocoonputiing. 416:231-249) 243, 2020. ISSN 0925-2312. doi: http:://do..or//1..mm 1016/.. neucom.2019.12.137. 22...................... p11/80925231220300
www. sci sciencedi rect com wwwascccieeeccciieee....
Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. On fair- ness and calibration. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vish- wanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30, Curran Associates, Inc., 2017. URL http:: oon. pdf
pp.
ccppperrr/pprr
#151-on-a
Kit Rodolfa, Erika Salomon, Lauren Haynes, Iván Higuera Mendieta, Jamie Larson, and Rayid Ghani. Case study: predictive fairness to reduce misdemeanor recidivism through social service interventions. Proceedings of the 2020 Conference on Fairness, Accountability, and Trans- parency, FAT* '20, pp. 142-153, New York, NY, USA, January 2020. Association for Computing Machinery.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, USA, 2014. ISBN 1107057132.
Sahil Verma and Julia Rubin. Faimess definitions explained. In Proceedings of the International Conference on Saftware Engineering, pp. 1-7, New York, NY, USA, 2018. ACM. doi: 10.1145/ 3194770.3194776.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi. Fair- ness Constraints: Mechanisms for Fair Classification. volume 54 of Proceedings of Machine Learning Research, pp. 962-970, Fort Lauderdale, FL, USA, 2017. PMLR.
In the appendix, we indicate the proofs of the two theorems in the main text, Thm and Thm
A SOME APPLICATIONS OF FAIR LEARNING
In this Section, we apply our results to two particular loss functions, namely the Calders- gap and the Bayes gap.
A.1 EXAMPLE 1: LEARNING DISPARITY
Of particular interest when measuring fairness the discrepancy that can be observed amongst different groups, for example in terms of 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 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
al. 2019), between groups and a' with respect to loss L can be defined
4t. (h) = Tor,a - LoT
(15)
for T (D,S).

---

Under review as a conference paper at ICLR 2022
Note that it is also quite usual consider the absolute value of disparity, | (h)l 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 establish the learnaillity of this widely used metric, which do in the following proposition.
Proposition 7. With probability at least 1 8, it holds
sup A (h) A (h)) hcH
I 2 2 H No) + R(e H HoN)
2 log (*) na Daa
The + nl
+ Ba!
+By
+
na
Proof. We start by observing that by sub-additivity of the sup, we have sup
sup A (h) A (h) I sup [h),a(h) - Ls,a
LD (h) - Ls,a (h)).
keH
We then conlude thanks Proposition 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 large Rademacher complexity or a low count, the upper bound will increase. This result enables us derive bounds on quantities of interest such as | b... (hīs)
(h))) that follows directly from Proposition
A.2 EXAMPLE LEARNING BIAS
In this Section, understand bias in very specific (and non-fairness related) way, in Chen jet al. (2018). short, one can consider bias -in this context- as the difference between the loss incurred by category 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).
is possible to use the characteristics directly in the model, then one can calibrate an optimal classifier each category:
h (x, (
(16)
However, we usually do not have access to the characteristic & or cannot include it as a feature (for instance to avoid disparate treatment), so that -in general- (xn = hi (x) for all = 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
Tr (h.) - Lr.a (h
(17)
for T (D,S).
In particular, s' 2 O. T.,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' = LD,(h's) LDDa(his,) can be learnt as
220g(2/8)
DD. - Ts.al= < 4RR(e H Ho + 2B
(18)
2na
with probability at least 1 1-6 5.
Proof. The proof is fairly straightforward and simply decomposes the Bayes gap in terms of easier building blocks:
(h)) (.D,a(
(hz) (s.a(h²) + (s,(()))) (hs.a L.D.alis.a)
I, (h3,a)
12

---

Under review as a conference paper at ICLR 2022
leading to
TD - Ts = LD.a(hi)) - Lsga(his) + Lssahis,a) LD.a(hisd)
We thus obtain that
TD,a - -ss
1
2 sup LD,a(h) Ls))(h)]
NCH
1log(2/0)
< 4R(E + 2B
2n
where the second inequality holds with probability least 1 8 by Proposition)
B OUT-OF-SAMPLA VARIANCE SCALING
In this Section, consider surrogate example illustrate some real-world consequences of The- orem 2 The behaviour of a number of debiasing methods, both in- and out-of- sattof-ssaple, has been studied real and surrogate data in the literature (Zafar et al. (2017): Agrawal al. (2020); Oneto eet al. (2020) for instance), we thus only provide an illustration
our result on a simple test case, highlight the role played by sampling variance in dealing with fairness metries. In keeping with the previous section, we suppose that we have chosen a given classifier y l(x, 8) and are now considering its statistical properties on (large) out-of-sample dataset.
B. PREDICTIVE PARITY AND LIMITING VARIANCE
In our simplified experimental setup, we consider C = 2, and set e = O with À = 1, i.e., we only look at a fairness criterion, and choose ratio Tpp linked to predictive parity (see Table T):
P 1/y 1, 1,
(h) = TD,PP
(19)
PP V 1ly 1,
The perfectly fair case corresponds to TD.PP 1. We also define the corresponding sample version of this criterion, using the samples N a= 1,2:
EiENt (8==1)
hs (h) TSPPP
(20)
EiENy 11h=1
In this case, one can compute Vim (h) directly
( 1ly = 1, 1)
P(ÿ = 1 1,8
(h)
(21)
[" yy = 1,3 1)
m
P(ğ = 11y = 1, 2)
where M1
and π2 - Ti P2
Pi +
p +2
B.2 SIMULATION SET-UP AND RESULTS
In our simulations, use the fixed values PP = 1ly = 1, = 1) 0.95 and P 1ly 1, nf + n which represents the
2) 0.99, leading to TD.PP 0.96. We vary the parameters overall sample size available to us to compute Ts.p,, and which is the effective proportion of class versus class 2. Throughout this exercise, we simulate N 1000 times the experiment. Our baseline case is m = 1, 000 and π 10%.
From Figure (a), one recovers the usual behaviour due to sample size: as m increases, the empirical distribution of Ts,PP becomes more peaked. A small sample size (such as 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 distribu-
tion of TD.. where k 1,... .N is the experiment run, with standard Gaussian distribution, (h)(())
as predicted by Proposition] 2 It can be seen in Figure 5 that there is good adequacy between both distributions.
13

---

Under review as a conference paper at ICLR 2022
densey
0.7
0.8
0.9
07
0.8 0.9
10U
tau
Figure 4: (a) Empirical densities TS.PP for m 100 (dotted), 1000 (black) and 10000 (dashed) at Ti 10%. (b) Empirical densities of TS,pP for т1 = 1% (red), 10% (black) and 50% (blue) at m 1000.
The most salient feature, however, is the behaviour of Ts.PP's distribution with respect to category probability, as described Figure where one can that as the sample becomes balanced, the variance of the estimator Ts,PP decreases. When πi 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 100, ক 10% and m 1000, क 1%. it is clear that cannot draw any conclusion regarding the presence of bias nor in terms of which group is the advantaged group. Bi- Bi-modality is particularly interesting characteristic of the empirical distribution: there is mode strictly below and a mode strictly above
2
Renormalsod Iau.
Figure 5: Normalised density of TD.PP (in black) and theoretical limiting distribution (in green) for m 1, 000 and ग. = 10%.
14

---

Under review as a conference paper at ICLR 2022
C PROOFS
C.1 PROOF OF PROPOSITION 3
Proposition
Under the assumption that & - -Lipschitz, it holds, with probability least 1- 6,
that
sup (dD(h) (s(h)) s 2 NEW
Σ
R(E H HoN + RiC No)
a=1
2lo 1C
+koBZs| BZs
K
with Zs = EE
n2 no
Proof. Using the hypothesis that Φ is K -Lipschitz, comes
(ĀD(h) - os(h)] S K
L.. (h) - (h) + (baa()) - -5 (h)
For any 8' (0,1) and any a =, 1..... C it holds
2 log 2
sup he#
- (h) - L (h)
$2R(E= H +B
BV
na
whereby
C
sup (bb(()) 0s(()) hEW
2k Σ
R(Et HoN + R(E o H HoN
a=1
2 2
2 log
+K B
na
na
with probability at least 20'8' thanks the union bound. To have 8 8- = 1- 208', one can simply pick = 6/(2C). Now, we can write the last term as
c
log 2
2 llog 2
2 2log
C
π
na
n
7n
2oo
Zst
71
hence the final result.
C.2 PROOF THEOREM
I
Theorem I With probubility at least 6, it holds
log(16C//))
0 S Ln(h))= - (D(())) < UBs B (1 \2g
(22)
/2
Proof. For the sake of clarity, we divide the proof into different steps.
Step 1. We can start by rewriting
(p())) - (D(s)) = LD(hi) - Ls(hs) + Ls(h)) Ls(h)) + Ls(h)) (D(1D)
Lo(lis) Ls(hT) + Ls(h)) Ln(lip),
15

---

Under review as a conference paper at ICLR 2022
since, by definition, Ls(h3) - (s(h)) S.
Step 2. Now, LD(h3) - (ht) & supnem [CD(h) (h))) on the one hand, and, on the other hand, we have
(Cs(h)) Co(h))) I
[gg(h)) Lb(bb)
C
+AK Σ
{
(b))
-3 ( +
- - }
Step 3. The key insight is to notice that the right-hand side only involves hb. which does not depend on the sample S, hence one can apply the Hoeffding inequality directly. Thus, by Hoeffding's inequality, for each with probability at least 1 - 8
log(2/0")
D (hb)) L (1i)) S BV
2n
Similarly, with probability at least 1 1 8"
(2/8"/
-Lb(h))) S BV
(bb)) - (b(b))
2n
We can then infer that with probability at least 1 -2C + 1)8"
log(2/8")
Lob(bb))
B
2n
log(2/8")
log(2/8")
+ARK
2na
2na
log(2/0")
B (1+
2n
Step 4. From the previous proposition, it comes that with probability at least 1 8'
(h(h) - Ls(h)) UBs + B \ZgKg) /
2 2log(8C/8))
sup NEH
Finally, by choosing 8' 5/2 and 8" = 6/(2(2C + 1)),
2 log(16C/8)
log (4(2C + 1)/8)
LD(hT) LD(h)) <
UBs + B + \Z
n
2n
3
log (og(16C/0)
< UBs + B (1 + \Zsk3)
V2
with probability at least 8.
C.3 PROOF OF THEOREM
2
Theorem Let h H. under the assumption that p for all a, and that (op exists and is non-zero, we have the following convergence in distribution
(Cs(() CD(h)) 2-+000
N (0, Vian (h)),
(23)
16

---

Under review as a conference paper at ICLR 2022
where
C
(kt)
Vim(()
Σ Pa (o (0 + x22
(o:)² + +22K2 cov (f) E ((,,)) (h,
c
+ X2 ( (5o)² + +2XK cov (1,, 2), E 2))
Σ
Po (oa (0a))²
Pe
a=1
C
+
Σ
Po (1( Paa)
(Littt)
2
+ -Pa) (LDo..) 2
+
2p Pa L 1 D.o
a=1
Σ
Pa + 0,+ 0.+
PaPa' L D.a D.a'
L + PaP L 0,- D.-
D.
D D'a
axal
+P D. D. + Pa Pa L - D.D''
Proof. For the sake of clarity, we divide this simple (but slightly tedious) proof into multiple steps. In this proof, 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 Lo for given h E H. Thanks to the Taylor formula, there exists & [0, such that
@s(h) (h)
(l) - (1)
+ (1- (h))² (bt())
We denote K the partial differential of Φ with respect to x i.c., K 0ut ((L (1 ) (L5 (h) - L (h)). Some algebra then yields
(Ls( (h))
C
+ Pa
(h)
+ +AK (bt((h)
(h) - ( (h))
na
L
Tha
S (h) -b)
+ +AK5a (5,(())
LL (t))
nu
Pa
na
C
Σ
n - Po Vn
L + Σ Vn nne - Pa L (h).
a=1
Step 2. Since lim
p > 0 almost surely, this implies trivially that lim n +00 almost surely, for any a. We now recall that, thanks to the continuous mapping theorem, it holds
KD.a almost surely, since VΦ is continuous and + (h) (h) almost surely.
that for any n lim / 1/V po almost surely. Finally, lim,-++0 K
Step 3. Let us now consider each term a separately.
+ nie P
- (h) -b
AK S.a (T. 11 I. (1))
= Vn
no
I S.0 (h) + t N..0
- (h((h))
p/ L (hi) + dK t5.0 1. (1))
+ ( - kT.a)
Vnn [ (h) - (1) d
S.a
By the Central Limit Theorem (CLT), na
L (h) - - (h)
وه N(0, [0 but since
kD,a) almost surely.
(K5,
a.s. n-+oc O. the whole term
(K k D.a) )
na
_ [. I (h) goes to
17

---

Under review as a conference paper at ICLR 2022
All that remains is to apply the CLT to
nhe Pe Lg (h) + AK L S.a (h)
- 0.
-
Pa
and notice that sma.g=i1 Pa (h, AK 8 (h,
- + 1 22 +
2p cov cov a (h 2), e (h,
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. finish the proof, 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 vn ts
L.e=1,..,,. C But this is simply the limiting distribution of empirical proportions in repeated trials of multinoulli distribution, hence the result.
P
Let us point out that the non-vanishing assumption on the gradient of the faimess loss function Ø can be relaxed, but leads to the need for a higher-order delta method (see DasGupta (2000)
18


Reviews:
[{"review_id": "sbJ5qopOntw", "reviewer": "Reviewer_bVZW", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\n- Understanding the generalization properties of popular fairness measures, as well as their interplay with accuracy, is certainly an interesting problem.\n\n- Sections 2 and 3 are quite well-written, easy to follow and provide some intuitive results.\n\nCons:\n\nUnfortunately, I find the rest of the paper very hard to follow. This is especially due to two reasons:\n\n- It is not clearly stated what the purpose/goal of the paper is. In particular, results follow one after the other, without much connection between them. I would suggest that the introduction is thoroughly rewritten, to clarify what the goal of this work is and how the results that follow address the problem at hand.\n\n- The comparison to related work is kept very vague. As the author acknowledge, there are multiple previous studies on the generalization properties of fairness notions. It is claimed in the text that the present work generalizes these previous results, but it is not clarified in what way.\n\n", "summary_of_the_paper": "The paper studies the generalization properties of PAC learning with fairness constraints.", "summary_of_the_review": "While the topic of the paper is interesting and some of the results look promising, I do not recommend acceptance due to the lack of clarity about the objectives of this work and the insufficient comparison to prior work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "PMZQ0b_6WrB", "reviewer": "Reviewer_9tuc", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n  - These bounds, although perhaps not surprising, are useful theoretical upper bounds for generalization under fairness.\n\nWeakness:\n  - The proof ideas are not very novel. Majority of the proofs are application of Rademacher inequalities and union bounds.\n  - The \"asymptotic regime\" is quite limited in its discussion and analysis.\n  - Theorem 2's improvement of Agrawal et al. (2020)'s result does not seem significant. The only change I can see is accounting for extra dimensions is derivatives and added summations. (Note: The proof of the citation is accessible through the arxiv tar.gz download). A side note: the reference to Proposition 1 does not match the latest arxiv release of Agrawal et al. (2020).\n  - Proof of Proposition 6 would be appreciated in the appendix (particularly the upper bound). Also it seems you can trivially get a tighter upper bound of $ 2C\\sqrt{n} $ (setting denominators to 1).\n  - The experimentation's stated claim is to investigate the validity of the theoretical claims, however, 6.1 & 6.2 appear to only test the trade-off in regularization. A better direction would be perhaps to test out-of-distribution generalization bounds experimentally.\n  - The class imbalance of 6.3 is never explained; and factor of just having less data in the experiment is not explored.\n  - There are many notation choice, typos, and missing definitions which have made navigating the paper difficult. One especially prohibitive choice is the use of the $ \\pm $ subscript, where it is unclear in many places if this is used to denote a specific equation; or is being used to define a $ + $ and $ - $ variant of the equation.\n\nOther:\n  - Just a note that the losses with subscript $ S $ is sometimes used as notation for subgroup loss in other work.\n  - Definition 2 should clarify $ \\sigma_{i} $.\n  - Type facing of Rademacher complexity verses constants $ R $ should be clarified.\n  - Missing $ \\min $ at the top of page 6. Seems to be consistent with definition of $ h^{*} $.\n  - The double superscript of $ \\pm $ of $ \\mathbf p $ in Prop 6 is confusing\n  - Overload on the symbol $ \\sigma $ for std.\n  - Text of footnote 2 is missing. I assume this is to do with choosing sex instead of age for German Credit?\n  - The stated generalized $ \\alpha $-mean seems to actually be just the $ L_p $-norm. A citation of where the definition of \"generalized $ \\alpha $-mean\" comes from would be useful as there seems to be other definitions which give different definitions (i.e., see \"Amari, Shun-ichi. Information geometry and its applications\" where its definitions gives $ \\alpha = 2 $)", "summary_of_the_paper": "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.", "summary_of_the_review": "Although the paper explores an important gap in looking at fairness in the PAC setting (with generalization), I recommend a reject given my listed concerns about novelty. In particular, the proof techniques are not novel and the results of Theorem 2 does not seem to extend the prior work of Agrawal et al. (2020). Furthermore, the experiments do not seem well connected to the theoretical results explored [1]. The  notation choices, typos, and missing definitions further cements that the paper needs major revisions.\n\n[1] Personally, I would even recommend excluding the experiments in the main text for further analysis, i.e., how Rademacher complexity terms might change when considering different fairness criteria; or connections of $ Z_{S} $ to known fairness quantities like data representation rate.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BOmW4GtHu1j", "reviewer": "Reviewer_myf3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In this paper, intuitive notations are used so that readers can easily follow, and theorems and proofs are well organized. The authors derive theoretical results by combining the generalization bound for standard statistical loss and the bound for fairness constraints. In the proofs of theoretical results, the process seems quite standard. It is interesting to observe that the portion of the sample for each group has a different way of affecting the standard loss term and the fairness term. And the two take-aways from proposition 6 are also interesting.\n\nSome suggestions : \n* Below equations (1) and (2), it is written as $T=D, S$, which would be nice to write as $T\\in\\{D,S\\}$ for consistency.\n* Missing part in two $h_{T}^{*}={ }_{h \\in \\mathcal{H}} \\mathcal{L}_{T}(h)$.\n* Section 4.2 mentioned that probabilistic upper bound is useful as a practical check, but it does not seem to reach me practically yet. To emphasize this more, it would be nice to mention the tightness of the upper bound of eq (8), or to add simple experimental results checking it.\n* I think it would be nice to show something more experimentally. Analysis on binary classification was performed, but non-binary classification results can also be included in experiments. And, analysis is with non-binary groups, so experiments can be performed on that setting. Also, you can consider showing some experimental results aligning with proposition 6.", "summary_of_the_paper": "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.", "summary_of_the_review": "It is meaningful to establish a guarantee for generalization in fairness-aware learning, but theorem and proof processes are too standard, so novelty seems to be insufficient. Considering practice, additional theoretical results or more diverse experiments expected to be added.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8DdzpcmJFjb", "reviewer": "Reviewer_CZ3f", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is hard to parse from time to time, and the organization of material is more or less confusing.\n\n### q1: \"this paper is first and foremost concerned with ... [tackling] issue of generalization\"\n\nTo the best of my knowledge, previous literature contains (at least some) results regarding the generalization bound (for example, Woodworth et al. (2017) (c.f., Theorem 7)). If there is any misunderstanding please kindly let me know.\n\n### q2: \"the derivation of PAC framework for fairness trade-offs\"\n\n- In Table 1 the authors list several fairness notions, I am just wondering if the proposed bounds apply to all notions? If so, there is a worry of the tightness and the practical significance of the bound; if not, which notions could fit in the proposed framework?\n\n- In Proposition 3, how strong is the assumption on $\\phi$? It would be very helpful if the author can connect the technical detail with the fairness notion of interest, or provide some insights regarding how to efficiently check if one can directly apply the presented result.\n\n### q3: the derivation of the asymptotic regime\n\nIn Section 5, Theorem 2 presented a convergence in distribution. While I can understand the composition of the variance term (as noted in the paper), I am not sure how to parse the result. What is the purpose of deriving this convergence in distribution?", "summary_of_the_paper": "The paper claims to study out-of-sample generalization w/ both (unconstrained) loss and the fairness consideration. While there are multiple theoretical results presented, the connection between them could be further elaborated, so that the takeaway messages can be clearly conveyed.", "summary_of_the_review": "Overall, the paper is relatively hard to follow, and it would be greatly appreciated if the authors can kindly clarify the questions/concerns as detailed in `Main Review`.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper establishes the guarantee for the generalization of fairness-aware learning in binary classification under PAC-learning and a more practical asymptotic framework. The paper is nicely written, and theorems and proofs are well organized. However, novelty of the contribution seems to be insufficient. A future version of the paper may benefit from additional theoretical results or more diverse experiments.
Decision: Reject