FARE: Provably Fair Representation Learning
Authors: Nikola Jovanović
Mislav Balunovic
Dimitar Iliev Dimitrov
Martin Vechev
Venue: Submitted to ICLR 2023 (2023)
Keywords: fairness
fair representation learning

Abstract: Fair representation learning (FRL) is a popular class of methods aiming to produce fair classifiers via data preprocessing. However, recent work has shown that prior methods achieve worse accuracy-fairness tradeoffs than originally suggested by their results. This dictates the need for FRL methods that provide provable upper bounds on unfairness of any downstream classifier, a challenge yet unsolved. In this work we address this challenge and propose Fairness with Restricted Encoders (FARE), the first FRL method with provable fairness guarantees. Our key insight is that restricting the representation space of the encoder enables us to derive suitable fairness guarantees, while allowing empirical accuracy-fairness tradeoffs comparable to prior work. FARE instantiates this idea with a tree-based encoder, a choice motivated by inherent advantages of decision trees when applied in our setting. Crucially, we develop and apply a practical statistical procedure that computes a high-confidence upper bound on the unfairness of any downstream classifier. In our experimental evaluation on several datasets and settings we demonstrate that FARE produces tight upper bounds, often comparable with empirical results of prior methods, which establishes the practical value of our approach. 


Under review as a conference paper at ICLR 2023
FARE: PROVABLY FAIR REPRESENTATION LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
Fair representation learning (FRL) is a popular class of methods aiming produce fair classifiers via data preprocessing. However, recent work has shown that prior methods achieve worse accuracy-fairnes their results. This dictates the need for FRL methods that provide provable upper bounds on unfairness of any downstream classifier, a challenge yet unsolved. this work we address this challenge and propose Fairness with Restricted Encoders (FARE), the first FRL method with provable fairness guarantees. Our key in- sight is that restricting the representation space of the encoder enables to derive suitable fairness guarantees, while allowing empirical accuracy-fairness tradeoff's comparable to prior work. FARE instantiates this idea with tree-based encoder, a choice motivated by inherent advantages of decision trees when applied in our setting. Crucially, we develop and apply practical statistical procedure that com- putes a high-confidence upper bound on the unfairness of any downstream clas- sifier. In our experimental evaluation several datasets and settings we demon- strate that FARE produces tight upper bounds, often comparable with empirical results of prior methods, which establishes the practical value of our approach.
tradeoffs than originally suggested by
INTRODUCTION
has been repeatedly shown that machine learning systems deployed in real-world applications propagate training data biases, producing discriminatory predictions (Buolamwini & Gebru, 2018: Corbett-Davies et al., 2017; Kleinberg et al., 2017; Tatman & Kasten, 2017). This is especially con- cerning in docision-makinn applications on data that represents humans (e.g., financial or medical), and can lead to unfavorable treatment that negatively affects certain subgroups of the population (Brennan al., 2009; Khandani et al., 2010; Barocas & Selbst, 2016). For instance, a loan predic- tion system deployed by financial institution might recommend loan rejection based on a sensitive attribte of a client, such as race or gender. These observations have forced regulators into action, leading to directives (FTC, 2021; EU, 2021) which demand parties aiming to deploy such systems to ensure fairness (Dwork et al., 2012) of their predictions. Mitigation of unfairness has become key concern for organizations, with the highest increase in perceived relevance over the previous year, out of all potential risks of artificial intelligence (Chui et al., 2021; ; Benaich & Hogarth, 2021).
Fair representation learning A promising approach that attempts address this issue is fair representation learning (FRL) (Zemel et al., 2013; Moyer et al., 2018; Madras et al., 2018; Gupta al., 2021; Kim et al., 2022: Shui et al., 2022; Balunović al., 2022) a long line of work that preprocesses the data using an encoder f. transforming each datapoint x E X' into debiased rep- resentation z. The key promise of FRL that these debiased representations can be given to other parties, who want to solve prediction task without being aware of fairness (or potentially even being fine with discriminating). while ensuring that any downstream classifier they train on these representations has favorable fairness. However, recent work (Xu et al., 2020; Song & Shmatikov, 2020; Gupta et al., 2021) has demonstrated that for some FRL methods is possible to train sig- nificantly more unfair classifiers than originally claimed. This illuminates major drawback of all existing work- their claim about fairness of the downstream classifiers holds only for the models they considered during the evaluation, and does not guarantee favorable faimess of other down- stream classifiers trained on z. This is insufficient for critical applications where fairness must be guaranteed or is enforced by regulations, leading
key question:
Can we create FRL method that provably bounds the unfairness of any downstream classifier?

---

Under review as a conference paper at ICLR 2023
Ieput datasot
Representations
Restricted encoder
2030
21
32
22
92
Is
D1
g
2 (9) $1
4% 2, (9) s (
Figure 1: Overview of our provably fair representation learning method, FARE. The input dataset is transformed into fair representations using restricted encoder. Our method can compute provable upper bound I' on unfairness of any classifier E G trained on these representations.
The most prominent prior attempt to tackle this question, and the work most closely related to ours, is FNF (Balunović al., 2022); discuss other related work in Section 2. Assuming two groups based on the sensitive attribute s, FNF shows that knowing the input distribution for each group can lead an important step towards provable fairness, the required assumption is unrealistic for most machine learning settings, and represents an obstacle to applying the approach in practice. Thus, the original problem of creating FRL methods that provide fairness guarantees remains largely unsolved.
s = 0 and
upper bound unfairness of any downstream classifier. While this work is
This work: provably fair representation learning We propose FARE (Fairness with Restricted Encoders. Fig. 1)-the the first FRL method that offers provable upper bounds on the unfairness of any downstream classifier g trained on its representations, without unrealistic prior assumptions. Our key insight is that using encoder with restricted representations, i.e., limiting possible representations to a finite set [21..... zx} ). allows us to derive a practical statistical procedure that computes a high- confidence upper bound the unfairness of any g, detailed in Section 4. FARE instantiates this idea with a suitable encoder based on fair decision trees (see Section 5), leading to a practical end-to-end FRI. method which produces debiased representations augmented with strong fairness guarantees.
More concretely, FARE takes as input the set of samples (x( ..... (())) from the input distribution X' (left of Fig. 1), and partitions the input space into cells (middle plane, = 3 in this example) using the decision tree encoder. Finally, all samples from the same cell are transformed into the same representation z; (right). As usual in FRL, training a downstream classifier on representations leads to lower empirical unfairness, while slightly sacrificing accuracy the prediction task.
However, the main advantage of FARE comes from the fact that using a restricted set of repre- sentations allows us to, using the given samples, estimate the distribution of two sensitive groups in each cell, i.e., compute an empirical estimate of the conditional probabilities P(s 0/2,) and P(s = 1|2;) (solid color orange bars) for all z;. Further, we can use confidence intervals to obtain upper bounds on these values that hold with high probability (transparent bars), As noted above, this turn leads to the key feature of our method: tight upper bound T on the unfairness of any g G, where G is the set of all downstream classifiers that can be trained on the resulting representations. As we later elaborate on, increasing the number of samples n makes the bounds tighter. Given the current trend of rapidly growing datasets, this further illustrates the practical value of FARE.
In our experimental evaluation in Section we empirically demonstrate that on real datasets FARE produces tight upper bounds, i.c., the unfairness of any downstream classifier trained FARE representations is tightly upper-bounded, which was not possible for any of the previously proposed FRL methods. Moreover, these downstream classifiers are able to achieve comparable empirical eecuracy-fairness tradeoffs to methods from prior work. We believe this work represents a major step towards solving the important problem of preventing discriminatory machine learning models.
2

---

Under review as a conference paper at ICLR 2023
Main contributions The key contributions of our work are:
A practical statistical procedure that, for restricted encoders, upper-bounds the unfairness of any downstream classifier trained on their representations (Section 4).
An end-to-end FRL method FARE, that instantiates this approach with fair decision tree encoder (Section 5), and applies the said statistical procedure to augment the representa- tions with tight provable upper bound on unfairness of any downstream classifier.
An extensive experimental evaluation in several settings, demonstrating favorable empirical faireess results, as well as tight upper bounds on unfairness (which were out of reach for prior work), often comparable to empirical results of existing FRL methods (Section 6).
RELATED WORK
We discuss related work on FRL. prior attempts to obtain fairness guarantees, and fair decision trees.
FRL for group fairness Following Zemel et al. (2013) which originally introduced FRL,
plethora of different methods have been proposed based on optimization (Calmon et al., 2017; Shui et al., 2022), adversarial training (Edwards & Storkey, 2016; Xie et al., 2017; Madras et al., 2018; Song et al., 2019; Feng et al., 2019; Roy & Boddeti, 2019; Jaiswal et al., 2020; Kairouz et al., 2022;
Kim et al., 2022), variational approaches (Louizos al., 2016; Moyer et al., 2018; Oh et al., 2022;
Liu et al., 2022), disentanglement (Sarhan et al., 2020), mutual information (Gupta et al., 2021; Gitiaux Rangwala, 2022), and normalizing flows (Balunović al., 2022: Cerrato et al., 2022). Notably, no prior method restricts representations as defined in Section 4, which is a key step in our work. While Zemel et al. (2013) map data to set of prototypes, this mapping is probabilistic, and thus fundamentally incompatible with our bounding procedure (see Section 4 for further details).
Towards fairness guarantees The key issue is that most of these methods produce representations that have no provable guarantees of fairness, meaning model trained on their representations could have arbitrarily bad fairness. In fact, prior work (Elazar & Goldberg, 2018; Xu et al., 2020; Gupta al., 2021) has shown that methods based on adversarial training often significantly overestimate the fairness of their representations. Some of these works (McNamara et al., 2017; Zhao et al., 2020; Gupta et al., 2021; Shen et al., 2021; Kairouz et al., 2022) propose aheoretically-prinipphe do not provide provable fairness guarantees with finite samples (we discuss the difference in Ap- pendix E). Closest to our work is FNF (Balunovic et al., 2022) that can compute high-confidence bounds, but critically, assumes knowledge of the input probability distribution, which is rarely the case in practice. Our work makes no such assumption, which makes it significantly more practical.
FRI., but
Provable faarness in other settings Numerous related works on provable fairness provide a dif- ferent kind of guarantee or assume a different setting than ours. First, several FRL methods have proposed approaches for learning individually fair representations (Lahoti et al., 2019; Ruoss al., 2020: Peychev et al., 2021), a different notion of faimess than group faimess which we focus on. Prior work has also examined provable fairness guarantees in various problem settings such as rank- ing (Konstantinov & Lampert, 2021), distribution shifting (Kang et al., 2022; Jin et al., 2022), fair classification with in-processing (Feldman et al., 2015; Donini et al., 2018: Celis et al., 2019), indi- vidually fair classification with post-processing (Petersen et al., 2021), and fair meta-lcarning (Oneto et al., 2020). These are all different from our setting, which is FRL for group fairness.
Fair decision trees The line of work focusing on adapting decision trees to fairness concerns includes a wide range of methods which differ mainly in the branching criterion. Common choices include variations of Gini impurity (Kamiran et al., 2010; Raff et al., 2018; Zhang & Ntoutsi, 2019), mixed-integer programming (Aghaei et al., 2019; Wang et al., 2022) or AUC (Barata & Veenman, 2021), while some apply adversarial training (Grari et al., 2020; Ranzato et al., 2021). Further, some works operate in different setting such online learning (Zhang & Ntoutsi, 2019) or post- processing (Abebe et al., 2022). The only works in this area that offer provable fairness guarantees are Ranzato et al. (2021), which certifies individual faimess for post-procsssing and Meyer et al. (2021), which certifies that predictions will not be affected by data changes. This fundamentally differs from our FRI setting where the goal is to certify faimeess of any downstream classifier.
3

---

Under review as a conference paper at ICLR 2023
3 PRELIMINARIES
We now set up the notation and provide the background necessary to understand our contributions.
Fair representation learning Assume data (z, s) E R' x {0, 1) from joint probability distribu- tion X, where each datapoint belongs to group with respect to a sensitive attribute s. While in this work we focus the case of binary 8, our results can be directly extended other settings. Further, we focus on binary classification, i.e., given a label y E {0. } associated with each datapoint, the goal is to build model g: Rd {0, 1} that predicts y from a. Besides maximizing accuracy of we aim to maximize its fairness with respect to sensitive groups, according to some fairness definition, which often implies slight loss in accuracy as these two goals are generally at odds.
A large class of methods aims to directly produce with satisfactory fairness properties. A different group of methods, our focus here, preprocesses data by applying an encoder f: Rd + Rd to obtain a new representation z = f(z, s) of each datapoint. This induces a joint distribution 2 of (z, 8). The downstream classifier g is now trained to predict from z, i.e., now we have g: Rd' - 10. The main advantage of these methods is that by ensuring faimess properties of representations 2, we can limit the unfairness of any trained on data from Z.
Let Zo and 21 denote conditional distributions of z where 0 and s 1, respectively. In this work, we aim to minimize the demographic parity distance of g. reflecting the goal of equally likely assigning positive outcomes to inputs from both sensitive groups:
Fairness metric
DP A Z, 2 (g) == [2 [2
Ez=2219(<)))
Our choice of metric is primarily motivated by consistency with prior work other definitions (c.g., equalized odds) may be more suitable for particular use-case (Hardt et al., 2016), and our method can be easily adapted to support them, following the corresponding results of Madras et al. (2018).
In the remainder of this work, we will Po and P1 to denote the PDFs of Zo and Z1 respectively, i.e., Pz.) = P(z.[s = 0) and pı (2;) = P(z
2 is 1) and to denote the PDF of the marginal distribution of z. Similarly, we will use q for the marginal distribution of and qi for the conditional
distribution of for z 25, i.e. (0) = P(s = 0/z 24) and (1) = P(s = 1|2 = =2)).
Classification trees Starting from the training set Droot of examples (x. y) E Rd x 10, binary classification tree f repeatedly splits some leaf node P with assigned Dp, i.e., picks split feature j E f1,.................. d} and a split threshold v. and adds two nodes L and R as children of P. such that D,, = (xx y) E Dp 2j I r} and DR Dp \ Dr. j and v are picked to minimize a chosen criterion, weighted by |Dr.] and DR.. aiming to produce y-homogeneous leaves. We focus on Gini impurity, computed as Giniy, (D) = 2p, (1 pv) [0, 0.5) where Py LeeW)D 1y = 1}/ID/- At inference, test example x is propagated to leaf I, and we predict the majority class of Dr.
4 PROVABLE FAIRNESS BOUNDS FOR RESTRICTED ENCODERS
In the following we describe our primary contribution, the derivation of provable fairness bounds on unfairness of downstream classifiers, under the assumption of restricted encoders (i.e., encoders with restricted representations, explained in more detail shortly). In Section 5 we demonstrate the feasibility of our approach, by instantiating it with a particular encoder based on decision trees.
Optimal adversary Consider the adversary h: Rd + {0, predicting group membership s, which aims to maximize the following balanced accuracy objective:
2 (h) = (EE~zz E [+(2]])
Ez-z,
(1)
Let h such that for all h, BAz,, (h*) 2 (h), denote the optimal adversary. Intuitively,
the optimal adversary predicts the group for which the likelihood of z under the corresponding
distribution (Zo or Z1) is larger. More formally, 1 1+*22) = (z) 2 po(z)), where [( = 1 if ø
holds, and O otherwise (see Balunović et al. (2022) for a proof). As shown in Madras et al. (2018),
A AP (g) < 2 B.A B.A.,. (h²)
(2)
4

---

Under review as a conference paper at ICLR 2023
holds for any g. i.., upper-bound the unfairness of any downstream classifier trained on data from 2 by computing the balanced accuracy of the optimal adversary h". Shen et al. (2021) also discuss connection between the balanced accuracy and total variation.
Restricted encoders Prior work is unable to utilize Eq. (2) to ob-
tain a faimess guarantee, as using unconstrained neural network en- coders generally makes it intractable to compute the densities po(z) and p1 (z) that define the optimal adversary h". Notably, Balunović et al. (2022) use normalizing flows, allowing computation of po(z) and p1 (z) under the assumption of knowing corresponding densities in the original distribution X. In contrast, we propose a class of en- coders for which we can derive a procedure that can upper-bound the
B
S
CI
h² h2
h7
RHS of Eq. (2), and thus the unfairness of g. without imposing any assumption terms of knowledge of X. We rely only on a set of samples (z, s) 2, obtained by applying ff to samples (x, s) X, which are readily available in the form of a given dataset.
h12
hg
Namely, hypothesize that restricting the space of representations can still lead to favorable fairness-accuracy tradeoffs. Based on this, we propose restricted encoders f: Rd + {=1,.... }. i.e., encoders that map each æ to one of k possible values (cells) 2; E IR'" As now there is a finite number of possible values for representation, we can use samples from to analyze the optimal adversary h² on each possible z. Morcover, we can upper-bound its balanced accuracy some value S with high probability, using confidence intervals (CI) (as illustrated in Fig. 2). Finally, can apply Eq. (2) to obtain the bound A 20. (9) < 25 1 T.
Figure 2: Restricted rep- resentations enable upper- bounding of 2,, (h").
the whole distribution Z with
detailed presentation of our upper- bounding procedure follows. In Sections 5 and 6 we demon- strate how design practical and efficient restricted encoders, by describing and evaluating instantiation based on decision trees, which, as we later discuss, are naturally suited to this problem.
Opper-bounding the balanced accuracy curacy of the optimal adversary as follows: Starting from Eq. (1), we reformulate the balanced ac-
BA 2, (11*)
(z:) (z)) + Σ pı(z.) (1(
(E of discrete RV)
2
1=1
1
max (po(2z),
(Optimal adversary)
2
p(z)) max (1/2g(0)) (0),,, (1/2g(1)) (.())
(Bayes' rule)
0g
where applications of Bayes' rule are po(2:) q: (0)p(z))/((0) and (1.)) = ()))(()))/(() As do not know 2, but instead have access to n samples (2(6), s(i) 2, will aim to upper- bound BAz,22, (h*) with high probability. In particular, we focus on the final expression above, the prightee (i.e., weighted by p(2;)) per-cell balanced accuracy (i.e., max(ooq: (1)))))(1)) for each cell i), where we define au = (0) and
(1).
Next, we introduce 3 lemmas, and later combine them to obtain the desired upper bound. We use Bp; w) to denote the p-th quantile of a beta distribution with parameters v and w. Note that for Lemma 1 we do not use the values 201) in the proof, but still introduce them for consistency.
Lemma 1 (Bounding base rates), Given n independent samples ((z(1), s(D), (2(1), s(n)]] Z and a parameter Chp for ag and aj as defined above, holds that
ao 2B( m 11) and 0n < 2(1 B(1
2 m + 1,n mm))
with confidence 1 eb. where m Σラ= ((80) = 0}.
5

---

Under review as a conference paper at ICLR 2023
Proof. We define independent Bernoulii random variables X : 1(s(7) 0} with same un- known success probability ((). Using the Clopper-Pearson Parser-eerssonne binomial CI (Clopper & Pearson, 1934) (Appendix A) to estimate the probability (()) we get P(g(0) < ( m, n2 + 1)) S c,/2 2 and P(q(O) 2 B(1 - 2 m + 1, - m)) S 6t/2. Substituting ((0) = g(1) in the latter, as well as the definitions of (rg and (r in both inequalities, produces the inequalities from the lemma statement, which per union bound simultaneously hold with confidence 1 - Eb.
Lemma 2 (Bounding balanced accuracy for each cell). Given n independent samples {(z(), )())..... (2(x), s())) 2, parameter cor and constants dgg and di such that og < do and 0n < ai, it holds for each cell i E ( with total confidence 1 - co that
max(a0 9: (0))), 0 q({1) S t,,
(3)
where t = max (ag 26 Ma 72 m, + 1), (1 (1- - B(1 z m, + 1, 10--100 -m))). In this ex- pression, n2 Zii. and m, Σjez, (() 0}, where denote Z; Ki]z 2.
Proof. As in Lemma for each cell we use the Clopper- Pearson CI estimate (0) with samples indexed by Z; and confidence 1 - se/k. As before. we apply (,))) = 1 - qi (1) to arrive at a set of inequalities of the form Eq. (3), which per union bound jointly hold with confidence 1 Cc. D
Lemma (Bounding the sum). Given n independent samples ((z(), s())))))))......... ss.)...... (z s(()) ~ Z, where for each j E [n,...,n} we define a function id)() such that 206) 2s (cell index), parameter Cs and set of real- vallvallud constants (t1....,4e} 1, it holds that
k
loges 2n
Σ p(2)) SS) 2 cs, where S
(ndo(ztin + (b -0- ==1
(4)
and we denote = min(t1...... } and b = max tx}.
Proof. For each j let x := (dd(((())) denote random variable. As for all j. X(i) E [a, b] with probability 1 and ( are independent, we can apply Hoeffding's inequality (Hoeffding, 1963) (re- stated in Appendix A) to upper-bound the difference between the population mean Σ P(2:)4 = Egwz(ide(x) and its empirical estimate Σド= XO), Setting the upper bound such that the error is below 6g directly recovers S and the statement of the lemma.
Applying the lemmas Finally, describe how we apply the lemmas in practice to upper-bound B, (h*), and in turn upper-bound A DP Lo (g) for any downstream classifier trained on repre- sentations learned by a restricted encoder. We assume standard setting, where a set D of datapoints {(xx)) ز from X' is split into training set Dtrain, used to train f. validation set D held-out for the upper-bounding procedure (and not used in training of I in any capacity), and a test set Drest- used evaluate the empirical accuracy and fairness of downstream classifiers.
After training the encoder and applying it to produce representations (2/5), (())) Z for all three data subsets, we aim to derive an upper bound on DP 2, (g) for any g, that holds with confidence at least - where e is the hyperparameter of the procedure (we use 0.05). To this end, heuristically choose some decomposition e = c + E. + c,, and apply Lemma 1 on Dtrain to obtain upper bounds on < cig and α di with error probability eg. As mentioned above, using Dtrain in this step is sound as estimated probabilities q(0) and q(1) are independent of the encoder f. Next, we use dg. āi and Deat in Lemma 2, to obtain upper bounds f,...., ty on per-cell accuracy that jointly hold with error probability e,. Finally, we upper-bound the sum D p( (4 S S with error probability e, using Lemma 3 on Drest with previously computed 4, ...... Ln Combining this with Eq. (2) finally gives the desired upper bound
A DP 2, (g) < 2 BA2,, (1""),,(h") (h") 1 < 28 1
(5)
which per union bound holds with desired error probability e, with respect to the sampling process.
This completes the upper-bounding procedure, enabling provable fair representation learning with no restrictive assumptions, which addresses a major limitation of prior work. Our procedure can be applied to representations produced by any restricted encoder. In the following sections, will describe a particular instantiation based on decision trees, and experimentally demonstrate that applying the above procedure produces tight unfairness upper bounds real datasets.

---

Under review as a conference paper at ICLR 2023
5 RESTRICTED REPRESENTATIONS WITH FAIR DECISION TREES
Next, we describe practical restricted encoder, enabling favorable accuracy-faimess tradeoff (similar to prior work), while allowing application of our results from Section 4 to provably bound the fairness of downstream classifiers trained on the representations (unique to our work).
Our encoder is based on decision trees, a choice motivated by strong results of tree-based models on tabular data (Borisov al., 2021), as well as their feature space splitting procedure, whose discrete behavior is inherently suitable for our requirement of restricted representations. In particular, we train a classification tree f with i leaves, and encode all examples that end up in leaf i to the same representation z₁. We construct 2; based on the set of training examples in leaf i, taking the median value for continuous, and the most common value for categorical features (thus in our case, d' = d).
Fairness-aware criterion Common splitting criteria are aimed at maximizing accuracy by making
the distribution of y in each leaf highly unbalanced, e.g., Ginii (D) = 2p, Py) E [0, 0.5) where Fy ElawED 1 = PI Aiming to use such tree as encoder generally leads to high unfairness, making it necessary to introduce direct way to prioritize more fair tree structures.
To this end, similar to Kamiran et al. (2010) and others (see discussion related work in Section 2), use the criterion FoirGini(D) (1 G)nin, + 70.55 Ginii Gini, is defined analogously to Giniy- The second term aims to maximize (Dni make the distribution of in each leaf close uniform (making it challenging for the adversary to infer the value of 8 based on z;), while the hyperparameter y controls the accuracy-fairnes. tradeoff.
0.5), where
Fairness-aware categorical splits While usual splits of the form 2j S (see Section 3) are suit- able for continuous, they are inefficient for categorical (usually one-hot) variables, as only 1 category can be isolated. Consequently, this increases the number of cells and makes our fairness bounds loose. Instead, we represent ny categories for feature j as integers E {1, .... nz}. To avoid evaluating all 2n: possible partitions, we sort the values by Py ElewEED 1
where D. = xx E D x = c}. and consider all prefix- suffix partitions (Breiman shortcus).
This ordering focuses on accuracy and is provably optimal for FairGúni(D) with y 0 (Breiman et al., 1984). However, as it ignores fairness, it is inefficient for y > 0. To alleviate this, we gener- alize the Breiman shortcut, and explore all prefix-suffix partitions under several orderings. Namely, for several values of the parameter we split the set of categories {1, .,.... .......... in q-quantiles with respect p. (c) (defined analogous to Py (c)), and sort each quantile by (c) as before, interspersing obtained arrays to obtain the final ordering. Note that while this offers no optimality guarantees, it an efficient way to consider both objectives, complementing our fairness-aware criterion.
We defer the discussion of the hyperparameters of our encoder to Appendix B.
EXPERIMENTAL EVALUATION
We evaluate our method, FARE, on several common fairness datasets, demonstrating that it pro- duces representations with faimess- tradeoffs comparable to prior work, while for the first time offering provable faimess bounds. We further provide more insights into FARE, discuss the interpretability of the representations, and provide additional experiments on transfer learning.
Experimental setup We consider common fairness datasets: Health (Kaggle, 2012) and two vari- ants of ACSIncome (Ding et al., 2021), ACSIncome-CA (only California), and ACSIncome-US (US-wide, larger but more difficult due distribution shift). The sensitive attributes are age and sex, respectively. We compare our method with the following recent FRL baselines (described in Section 2): LAFTR (Madras al., 2018), CVIB (Moyer et al., 2018), FCRL (Gupta al., 2021), FNF (Balunović et al., 2022), sIPM-LFR (Kim et al., 2022), and FairPath (Shui et al., 2022). We provide all omitted details regarding datasets, baselines, and our experimental setup, in Appendix B.
Main experiments We explore the various hyperparameters. Each run produces representations, used to train a 1-hidden-layer neural
tradeoff of each method by running it with
7

---

Under review as a conference paper at ICLR 2023
Unrai Baseline
Unbir Baseline
FCRL
0.21
[1.00
PNF
Demograshi Parly Dietance
JPMA-FFR
Demograshi Party Distance
FARE (Mpper Bound)
FARE (Jsper Bound)
FARE (Emplrcaa)
FORE (Emp
R.15
0.10
0.00
0000
Accuracy
Figure 3: Evaluation of FRL methods on ACSIncome-CA (left) and ACSIncome-US (right).
Urbar Basciite
network (1-NN) for the prediction task using standard training procedure (same for each method), and plot its de- mographic parity (DP) distance and prediction accuracy.
Party Delurnee
SPMM LFR
FARE (Upper Bound)
PARE (Rmppiici)
Following Kim et al. (2022), we show test set Pareto front for each method. Further, for FARE independently show a Pareto front of a 95% confidence provable upper bound DP distance (following Section 4), which is key fea- ture of our approach and cannot be produced by any other method. Finally, we include Unfair Baseline, which uses an identity encoder. The results are shown in Figs. 3 and 4. We omit FairPath and LAFTR from the main plots (see tended results in Appendix C), as LAFTR has stability and convergence issues (Gupta al., 2021; Kim et al., 2022). and FairPath uses different metric to us (Shui et al., 2022).
6.1
0.74
0.70
0.75
0.80
0.30
Accuracy
Figure 4: Evaluation Health.
We observe that FARE can achieve better (Fig. 3) or comparable (Fig. 4) accuracy- compared to baselines. Crucially, other methods cannot guarantee that there is no classifier with worse DP distance when trained on their representations. This cannot happen for our method-we produce provable upper bound on DP distance of any classifier trained on representations. The results indicate that our provable upper bound often comparable to empirical values of baselines. Note that there small gap (up to 1.5%) between the maximum accuracy of FARE and the unfair baseline, indicating a tradeoff of restricted encoders FARE obtains provable bounds, but loses some information, limiting the predictive power of downstream classifiers. This is rarely issue in practice, as obtaining meaningful fairness improvements generally requires a non-trivial accuracy loss, especially when s correlated with the task label. Finally, another advantage of FARE is its efficiency, with runtime of several seconds, as opposed to minutes or hours for basclines.
tradeoff
Exploring downstream classifiers Fig. (left), we show a representative point from Fig. 4, its fairness guarantee, and 24 diverse downstream classifiers (see Appendix B) trained on same repre- sentations, where half trained to maximize accuracy, and half maximize unfairness. The latter (left cluster) can reach higher unfairness than initially suggested, reaffirming a known limitation of prior work (Xu al., 2020; Gupta al., 2021): evaluating representations with some model class (here, I I-NN) does not reliably estimate unfairness, as other classifiers (perhaps intentionally cre- ated by malicious actor) might more unfair. This highlights the value of FARE which provides provable unfaimess upper bound-al all unfairness values still remain below known upper bound.
we explore a point from Fig. (right), with accuracy 75.1% and DP distance of 0.005. As here A 6, i.e., the possible representations are {= #6 }. the previous investigation of downstream classifiers simplifies. Instead of choosing model class, we can enumerate all 2 = 64 possible classifiers, and directly confirm that each DP distance is below the upper bound, shown in Fig. 5 (middle). Note that in the original experiment, all bascline methods have DP distance > 0.04 similar accuracy of as 75%, implying that the FARE bound is this very tight.
Similarly,
8

---

Under review as a conference paper at ICLR 2023
FARE (Upper Bound)
Upper Bound M-2
Upper Bound with M:44
Demograghic Parity Distance
0.10-
Downstream Ciassiiers
Demographic Parily Distance
0.32
Downsteart Clasiiess
HUpper
Basance
Upper Bound with M-16
Upper Bound with M-8
0.15
Upper Bound with M-32
0.355
FARE (Empiriaal)
Damographs
1010
0.31
0.30-
0
0.66
0.25-
0.301
0.500
0.50
0.70
0.20
0.75
0.52
Accuracy
Accuracy
Acouraay
Figure 5: Comparing trained downstream classifiers with the FARE upper bound (left and middle).
The impact of increasing the dataset size M times on the fairness upper bound tightness (right).
Data improves bounds In Fig. we see that the FARE bounds are tighter for ACSIncome- as using more samples improves the bounding procedure. To investigate this further, we choose representative set of FARE points from Fig. (left), and repeat the upper-bounding procedure with the dataset repeated M times, showing the resulting upper bounds for M E {2, 4, 8, 16, 32) in Fig. (right). We can observe a significant improvement in the provable upper bound for larger dataset sizes, indicating that FARE is well-suited for large datasets and will benefit from ever-increasing amounts data used in real-world machine learning deployments (Villalobos & Ho, 2022).
Interpretability Another advantage of FARE is that its tree-based encoder enables direct inter- pretation of representations. To illustrate this, for representations with = 6 analyzed in Fig. (middle) we can easily find that, for example, the representation 26 assigned each person older that 24, with at least a Bachelor's degree, and an occupation in management, business or science.
Transfer learning Finally, we analyze the transfer- ability of learned representations across tasks. We pro- duce a diverse set of representations on the Health dataset with each method, and following the procedure from prior work (Madras et al., 2018; Balunović et al., 2022; Kim al., 2022) evaluate them five unseen tasks y (see Appendix B for details), where for each the goal is predict certain primary condition group. For each task and each method, we identify the high- est accuracy obtained while keeping A DP 22 not above 0.20 (or 0.05). Moreover, we show T, the provable DP distance upper bound of FARE.
DP
FARE
FCRL
FNF
sIPM
MIS
$ 0.05
0.54
78.7
78.6
78.7
78.6
NRU
S
< 0.05
0:42
72.1
71.4
71.7
ART
S
2 0.05
0.23
69.5
70.7
69.5
68.5
MET
$ 0.20
69.2
75.0
5 0.05
0.12
66.1
65.3
MSC
S 0.20
0.53
67.2
70.5
73.0
0.05
0.12
63.0
Table 1: Transfer learning on Health.
The results are shown in Table 1. First, we observe that some methods are unable to reduce A Za.2, below the given threshold. Our method always reduce the DP 2, sufficiently, but due our restriction on representations which enables provable upper bounds, we often lose more accuracy than other methods for high A 20,z, thresholds. Future work could focus investigating alternative restricted encoders with better fairness-accuracy tradeoffs in the transfer learning setting.
DP
7 CONCLUSION
We introduced FARE, method for provably fair representation learning. The key idea was that using restricted encoders enables practical statistical procedure for computing a provable upper bound on unfairness of downstream classifiers trained on these representations. We instantiated this idea with a tree-based encoder, and experimentally demonstrated that FARE can for the first time obtain tight fairness bounds several datasets, while simultaneously producing empirical fairness- accuracy tradeoffs similar to prior work which offers no guarantees.

---

Eifffel: enforcing fairness in Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
To foster reproducibility, all our code, datasets and scripts are provided in the Openreview dis- cussion. All of our experiments presented in Section 6 be using the instructions we provide in the Readme file that accompanies our code. The hyperparameters used for our runs are described in Appendix B and further detailed in the Readme.
REFERENCES
Seyum Assefa Abebe, Claudio Lucchese, and Salvatore Orlando. forests by flipping leaves. In SAC, 2022.
Sina Aghaei, Mohammad Javad Azizi, and Phebe Vayanos. Learning optimal and fair decision trees for non-diseriminative decision-making. In AAAI, 2019.
Mislav Balunović, Anian Ruoss, and Martin T. Vechev. Fair normalizing flows. In ICLR, 2022.
António Pereira Barata and Cor J. Veenman. Fair tree learning. CoRR, 2021.
Solon Barocas and Andrew D. Selbst. Big data's disparate impact. California Law Review, 2016.
Nathan Benaich and Ian Hogarth. State ai report 2021. 2021. https: /ttp:://wwwww. www.wst..of....mmmmmmmm.m .ai/ 2021, accessed: 2022-09-26.
Vadim Borisov, Tobias Leemann, Kathrin SeBler, Johannes Haug, Martin Pawelezyk, and Gjergji Kasneci. Deep neural networks and tabular data: A survey. arXiv, 2021.
Leo Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth, 1984.
Tim Brennan, William Dieterich, and Beate Ehret. Evaluating the predictive validity of the compas risk and needs assessment system. Criminal Justice and Behavior, 2009.
Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in commer- cial gender classification. In FAccT, 2018.
Flávio P. Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and
Kush R. Varshney. Optimized pre-processing for discrimination prevention. In NeurIPS, 2017.
L. Elisa Celis, Lingxiao Huang, Vijay Keswani, and Nisheeth K. Vishnoi. Classification with fair- ness constraints: A meta-algorithm with provable guarantees. In FAT, 2019.
Mattia Cerrato, Marius Köppel, Alexander Segner, and Stefan Kramer. Fair group-shared represen-
tations with normalizing flows. CoRR, 2022.
Michael Chui, Bryce Hall, Alex Singla, and Alex Sukharevsky. 2021. 2021. attps://wwet wwwp://cciiisy.c.oo.om wow/ www/caapbbliieieeeseeeeeeoeeeeee qquatt umblack/ ouu--nnsii pur-insiight//lloll whw.ooaa--suuuueeeee-eeeeeee thsrrrey-te--ssttt-----a-------- 26.
The state of ai in
accessed: 2022-09-
C. Clopper and E. Pearson. The use of confidence fiducial limits illustrated in the of the binomial. Biometrika, 1934.
Sam Corbett-Davies Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algorithmic decision making and the cost of faireess. In ACM SIGKDD, 2017.
Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning, Advances in Neural Information Processing Systems, 34, 2021.
Michele Donini, Luca Oneto, Shai Ben-David, John Shawe-Taylor, and Massimiliano Pontil. Em- pirical risk minimization under fairness constraints. NeurIPS, pp. 2796-2806, 2018
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard S. Zemel. Fairness through awareness. In ITCS, 2012.
10

---

Under review as a conference paper at ICLR 2023
Harrison Edwards and Amos J. Storkey. Censoring representations with an adversary. In ICLR, 2016.
Yanai Elazar and Yoav Goldberg, Adversarial removal of demographic attributes from text data. In EMNLP, 2018.
EU. Proposal for a regulation laying down harmonised rules on artificial intelligence, 2021.
Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubra- manian. Certifying and removing disparate impact. In KDD, 2015.
Rui Feng. Yang Yang. Yuehan Lyu, Chenhao Tan, Yizhou Sun, and Chunping Wang. Learning fair representations via an adversarial framework. CoRR, 2019.
FTC. Aiming for truth, fairness, and equity in your companys use of ai, 2021. https:/ /tt:://wwwwwwo ftc. gov/news www.ts//bloss//ussssisieee blog /0og/222111 /04/ aai, accessed: 2022-09-
26.
Xavier Gitiaux and Huzefa Rangwala. Sofair: Single shot fair representation learning. IJCAI, 2022.
Vincent Grari, Boris Ruf, Sylvain Lamprier, and Marcin Detyniecki. Achieving fairness with deci- sion trees: An adversarial approach. Data Sci. Eng., 2020.
Steffen Grünewälder and Azadeh Khaleghi. Oblivious data for fairness with kernels. J. Mach. Learn. Res., 12:208:1-208:38 2021.
Umang Gupta, Aaron Ferber, Bistra Dilkina, and Greg Ver Steeg. Controllable guarantees for fair outcomes via contrastive information estimation. In AAAI, 2021.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning, In NewrIPS, 2016.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. JSTOR, (301), 1963.
Ayush Jaiswal, Daniel Moyer, Greg Ver Steeg, Wael AbdAlmageed, and Premkumar Natarajan. Invariant representations through adversarial forgetting. In AAAI, 2020.
Jiayin Jin, Zeru Zhang, Yang Zhou, and Lingfei Wu. Input-agnostic certified group fairness via gaussian parameter smoothing. In ICML, 2022.
Kaggle. Health heritage prize, 2012. URL https: //ww www.le.coo//aacca.....oooo.ooo.a / c/hhp.
Peter Kairouz, Jiachun Liao, Chong Huang, Maunil Vyas, Monica Welfert, and Lalitha Sankar. Generating fair universal representations using adversarial models. IEEE TIFS, 2022.
Faisal Kamiran, Toon Calders, and Mykola Pechenizkiy. Discrimination aware decision tree learn- ing. In ICDM, 2010.
Mintong Kang. Linyi Li, Maurice Weber, Yang Liu, Ce Zhang, and Bo Li. Certifying distri- butional fairnsss with subpopulation decomposition. CoRR, 2022.
Amir E Khandani, Adlar J Kim, and Andrew W Lo. Consumer credit-risk models via machine- learning algorithms. Journal of Banking Finance, 2010.
Dongha Kim, Kunwoong Kim, Insung Kong, Ilsang Ohn, and Yongdai Kim. Learning fair repre- sentation with parametric integral probability metric. In ICML, 2022.
Jon Kleinberg. Sendhil Mullainathan, and Manish Raghavan. Inherent trade-off's in the fair determi- nation of risk scores. In /TCS, 2017.
Nikola Konstantinov and Christoph H. Lampert. Fairness through regularizaiion for learning to rank. CoRR, 2021.
11

---

Under review as a conference paper at ICLR 2023
Preethi Lahoti, Krishna P. Gummadi, and Gerhard Weikum. ifair: Learning individually fair data representations for algorithmic decision making. In ICDE, 2019.
Ji Liu, Zenan Li, Yuan Yao, Feng Xu, Xiaoxing Ma, Miao Xu, and Hanghang Tong. Fair represen- tation learning: An alternative mutual information. In KDD, 2022.
Christos Louizos, Kevin Swersky, Yujia Li, Max Welling, and Richard Zemel. The variational fair autoencoder. In ICLR, 2016.
David Madras, Elliot Creager, Toniann Pitassi, and Richard S. Zemel. Learning adversarially fair and transferable representations. In ICML,, 2018.
Daniel McNamara, Cheng Soon Ong, and Robert C. Williamson. Provably fair representations. CoRR, abs/1710.04394, 2017.
Anna Meyer, Aws Albarghouthi, and Loris D'Antoni. Certifying robustness programmable data bias in decision trees. In NeurlPS, 2021.
Daniel Moyer, Shuyang Gao, Rob Brekelmans, Aram Galstyan, and Greg Ver Steeg. Invariant representations without adversarial training. In NeurIPS, 2018.
Changdac Oh, Heeji Won, Junhyuk So, Taero Kim, Yewon Kim, Hosik Choi, and Kyungwoo Song.
Learning fair representation via distributional contrastive disentanglement. In KDD, 2022.
Luca Oneto, Michele Donini, Massimiliano Pontil, and Andreas Maurer. Learning fair and transfer-
able representations with theoretical guarantees. In DSAA, 2020.
Felix Petersen, Debarghya Mukherjee, Yuekai Sun, and Mikhail Yurochkin. Post- Post-processing for individual fairness. In NeurlPS, 2021.
Momchil Peychev, Anian Ruoss, Mislav Balunovic, Maximilian Baader, and Martin T. Vechev. Latent space smoothing for individually fair representations. CoRR, 2021.
Edward Raff, Jared Sylvester, and Steven Mills. Fair forests: Regularized tree induction minimize model bias. In A/ES, 2018.
Francesco Ranzato, Caterina Urban, and Marco Zanella. Fair training of decision tree classifiers. CoRR, 2021.
Proteek Chandan Roy and Vishnu Naresh Boddeti. Mitigating information leakage in image repre- sentations: A maximum entropy approach. In CVPR, 2019.
Anian Ruoss, Mislav Balunovic, Mare Fischer, and Martin T. Vechev. Learning certified individually fair representations. In NeurlPS, 2020.
Mhd Hasan Sarhan, Nassir Navab, Abouzar Eslami, and Shadi Albarqouni. Faireess by learning orthogonal disentangled representations. In ECCV, 2020.
Xudong Shen, Yongkang Wong, and Mohan S. Kankanhalli. Fair representation: Guaranteeing
approximate multiple group fairness for unknown tasks. CoRR, abs/2109.00 2021.
Changjian Shui, Qi Chen, Jiaqi Li, Boyu Wang, and Christian Gagné. Fair representation learning through implicit path alignment. In ICML, 2022.
Congzheng Song and Vitaly Shmatikov. Overlearning reveals sensitive attributes. In ICLR, 2020.
Jiaming Song, Pratyusha Kalluri, Aditya Grover, Shengjia Zhao, and Stefano Ermon. Learning controllable fair representations. In AISTATS, 2019.
Zilong Tan, Samuel Yeom, Matt Fredrikson, and Ameet Talwalkar. Learning fair representations for kernel models. In AISTATS, volume 108 of Proceedings of Machine Learning Research, pp. 155-166. PMLR, 2020.
Rachael Tatman and Conner Kasten. Effects of talker dialect, gender & race on accuracy of bing speech and youtube automatic captions. In INTERSPEECH, 2017.
12

---

Under review as a conference paper at ICLR 2023
Pablo Villalobos and Anson Ho. Trends in training dataset sizes. https: http///pcch...... org/ blog/tzends- in- in-traainin--dttsetttt-
2022. Accessed: 2022-09-28.
Jingbo Wang, Yannan Li, and Chao Wang. Synthesizing fair decision trees via iterative constraint solving. In CAV, 2022.
Qizhe Xie, Zihang Dai, Yulun Du, Eduard H. Hovy, and Graham Neubig. Controllable invariance through adversarial feature learning. In NIPS, pp. 585-596, 2017.
Yilun Xu, Shengjia Zhao, Jiaming Song, Russell Stewart, and Stefano Ermon. A theory of usable information under computational constraints. In ICLR, 2020.
Richard S. Zemel, Yu Wu, Kevin Swersky, Toniann Pitassi, and Cynthia Dwork. Learning fair representations. In ICML, 2013.
Wenbin Zhang and Eirini Ntoutsi, FAHT: an adaptive aaire decision tree classifier. In IJCAI, 2019.
Han Zhao, Amanda Coston, Tameem Adel, and Geoffrey J. Gordon. Conditional learning of fair representations. ICLR. OpenReview.net, 2020.
13

---

Under review as a conference paper at ICLR 2023
Dataset
Training size
Test size
Base rate (8)
Base rate (y)
ACSIncome- CA
165 546
18 395
0.46
0.64
ACSIncome-US
429 070
158 786
0.48
0.68
Health
174 732
43 683
0.35
0.68
Table 2: Statistics of evaluated datasets.
A MATHEMATICAL TOOLS
We first derive Eq. (2). More details can be found in Madras al. (2018), and here we provide overview:
A DP Z..2, (g) = E [g(2)] - 2 [9(2)]
( E, [g(2]]
E [1 g(=)] E [g(2]]
(2BAz,22 1
From this, we can argue that we can drop the absolute value and bound the balanced accuracy of with the balanced accuracy h², finally arriving Equation 2.
Then, we formally state the Hoeffding's inequality and the Clopper-Pearson binomial confidence intervals, used in our upper-bounding procedure Section 4.
Hoeffding's inequality (Hoeffding, 1963): Let (1)),
( be independent random variables such
that P(X (1) E E(a(5) (00) = 1. Let ú x() 46. and [[ holds that:
-2n2t²
P(u P 2 S exp
(b()) (z
Clopper-Pearsee binomial proportion confidence intervals (Clopper Pearson, 1934): Assume binomial distribution with an unknown success probability 0. Given m successes out of n experi- ments, holds that:
a B 5 m, - m +
B 2" m + 1,n-m)
(6)
with confidence least 1 a over the sampling process, where Bp; v, w) denotes the p-th quantile of beta distribution with parameters v and w.
B DETAILS OF EXPERIMENTAL EVALUATION
In this section we provide details of our experimental evaluation omitted from the main text.
Datasets As mentioned in Section 6, we perform our experiments on ACSIncome (Ding et al., 2021) and Health (Kaggle, 2012) datasets. Table 2 we show some general statistics about the datasets: size of the training and test set, base rate for the sensitive attribute s (percentage of the majority group out of the total population), and base for the label y (accuracy of the majority class predictor).
ACSIncome dataset recently proposed by Ding et al. (2021) as an improved version of UCI Adult, with comprehensive data from US Census collected across all states and several years (we use 2014). The task is to predict whether an individual's 's income is above $50,000, and we consider sex as sensitive attribute. We evaluate our method on two variants of the dataset: ACSIncome-CA. which contains only data from California, and ACSIncome-US, which merges data from all states and is thus significantly larger but also more difficult, due to distribution shift. 10% of the total dataset is used as the test set. We also use the Health dataset (Kaggle, 2012), where the goal is to predict the Charlson Comorbidity Index, and consider age sensitive attribute (binarized by thresholding at 60 years). For this dataset perform the same preprocessing as Balunović et al. (2022), and use 20% of the total dataset the test set.
14

---

Under review as a conference paper at ICLR 2023
Unner Diaiiine
Jiit Seaeine
0.21
(1:00
PaP
Demograshi Parity Dietance
Demograhhe Party Distance
LAFTA
LAFTS
PARS sippre Roand)
ENCE Moper Round)
(Engricaa)
R.15-
0.10
0.10
0.00
[000
Accuracy
Figure 6: Extended evaluation on ACSIncome-CA (left) and ACSIncome- (right).
Evaluation procedure For our main experiments, as a downstream classifier we use a I-hidden- layer neural network with hidden layer size 50, trained until convergence on representations normal- ized such that their mean is approximately 0 and standard deviation approximately 1. We train the classifier times and in our main figures report the average test set accuracy, and the maximal DP distance obtained, following the procedure of Gupta al. (2021).
Hyperparameters For baselines, we follow the instructions in respective writeups, as well as Gupta al. (2021) to densely explore appropriate parameter range for cach value (linearly, or exponentially where appropriate), aiming to obtain different points on the accuracy-faimess curve. For CVIB, explore À E [0.01, 1] and B E [0.001, 0.1). For FCRL ACSIncome explore = E [0.01, 2]. and for Health E [0.01,2] and 8 = 0.5A. For FNF, we explore E [0, 1]. For SIPM-LFR, we
[0.0001, 1.0] and X [0.0001, 100.0], extending the suggested ranges. For FairPath we set the parameter Λ E [0, 100). Finally, for LAFTR we use E [0.1, 1, 50). extending the range of [0, 4] suggested by (Gupta al., 2021). We adjust the parameters for transfer learning whenever supported by the method.
For FARE, there are four hyperparameters: y (used for the criterion, where larger 7 puts more focus on fairness), & (upper bound for the number of leaves), n. (lower bound for the number of examples leaf), and v (the ratio the training set to used as validation set). Note that all parameters affect accuracy, empirical fairness, and the tightness of the fairness bound. For example, larger n,, is likely to improve the bound by making Lemma tighter, as more samples can be used for estimation. For the same reason, increasing improves the tightness of the bound, but may slightly reduce the accuracy as fewer samples remain in the training set used to train the tree. In our experiments we investigate y [0, 1), [2, 200), n4 [50, 1000]. {0.1, 0.2, 0.3, 0.5). For the bopuribbundiig procedure, we always set e = 0.05, 6 6, = 0.005, and thus 6 = 0.04. Finally, when sorting categorical features described in Section 5, g E { 2, 4} in all cases.
Omitted details of additional experiments For the exper- iment with alternative classifiers (Fig. left) we explore the following classifiers: (i) I-hidden-layer neural network (I- NN) with hidden layer sizes 50 and 200. (ii) 2-NN with hid- den layers of size (50, 50). as well as (200, 100). (iii) logistic regression, (iv) random forest classifier with 100 and 1000 es- timators, (v) decision tree with 100 and an unlimited number of leaf nodes. We train all these classifiers with standard- ization preprocessing step described above. We further train one variant of I-NN, 2-NN, random forest, and logis- tic regression, unnormalized data. All described models are trained both to predict the task label y, and to maximize unfairness, i.e., predict 8, leading to 24 evaluated models.
Lital Now
CVB
PoB LETAUIII
LATTI
FARL lape
0.1
6.4
0.76
0.75
0.80
0.22
Accuracy
Figure 7: Extended evaluation of FRL methods on Health.
15

---

Under review as a conference paper at ICLR 2023
DP 24.21
FARE
PCRL
FNF
sIPM
S 00.00
0.64
79.3
78.6
79.2
79.8
MIS
0.20
0.64
79.3
78.6
78,9
79.8
0.15
0.64
79.3
78.6
78.9
79.6
0,48
78.6
78.9
79.0
0.05
0.54
78.7
78.6
78.7
78.6
0.30
72.4
71.9
78.8
NEU
0.20
0.64
73.2
72.4
71.9
76.6
0.15
0.64
73.2
72.4
71.8
73.2
< 0.10
0.64
73.2
72.2
71.8
S 0.05
0.42
72.1
71,4
71.7
< 0.30
0.41
74,4
70.7
68.9
78.3
ART
S 0.20
0.41
74.4
70.7
68.9
78.3
0.15
0.46
74.2
70.1
68.9
S 0.10
0,23
69.5
69.6
68.7
0.23
69.5
69.5
68.5
S 0.30
0.47
74.0
72.5
76.2
MET
0,46
69.2
75.0
S
0..5
67.9
73.2
S 0.10
0.12
66.1
66.7
73.2
0,05
0.12
66.1
65.3
0.30
0.56
71.3
70.5
73.5
77.6
MSC
0.20
0.53
67.2
70.5
73.0
X 0.15
0.12
63.0
69.7
0.10
0.12
63.0
69.0
X 0.05
0.12
63.0
Table 3: Extended results of transfer learning experiments on Health.
For transfer learning (Table 1), the five transfer tasks repre- sent prediction of the following attributes from the Health dataset: MISCHRT (MIS), NEUMENT (NEU), ARTH- SPIN (ART), METAB3 (MET), MSC2A3 (MSC).
C EXTENDED RESULTS
We provide the extended results of our main experiments, including two originally excluded meth- ods, LAFTR and FairPath in Fig. and Fig. 7, corresponding to Fig. 3 and Fig. 4.
Additionally, in Table we provide extended results of our transfer learning experiments, showing the accuracy values for thresholds A DP 2, E {0.30, 0.20, 0.15, 0.10, 0.053. can observe similar trends shown in Table in the main paper.
D ADDITIONAL EXPERIMENTS
In this section, we provide additional experimental results showing the effects which imbalance in sensitive attribute, different downstream classifiers, and dataset size have on FARE.
D.1 EFFECT OF SENSITIVE ATTRIBUTE IMBALANCE
In this section, we demonstrate empirically what effect an imbalance in the sensitive attribute has on the resulting fairness and accuracy of our proposed method. Let denote the level of imbalance of each training set (i.e., the number data points in the larger the two sensitive classes divided by the total number of data points in the set). For each value of we are interested in, sample a random subset of size 49 053 from the original ACSIncome CA training dataset (out 165 546 data points in total) and ensuring that the level of imbalance is exactly c. We use 49 053 samples, as this is the largest number for which we can have same dataset size for each c, thus ensuring the fair comparison.
16

---

Under review as a conference paper at ICLR 2023
0.40
FARE C-0.9 (Upper Bound)
FARE C-0.9 (Empirical)
0.35
FARE C-0.8 (Upper Bound)
FARE (Empirica))
FARE 0-0.7 (Upper Bound)
Demographic Parity Distance
FARE C-0.7 7.7 (Emprrica)
0.30
FARE 0=0.8 (Upper Bound)
FARE (Empirial)
0.25
FARE C-0.5 (Upper Bound)
FARE 0=0.5 (Empirica))
0.20
0.05
0.00
0.72
0.75
0.78
0.81
Accuracy
Figure 8: Evaluation of FARE at different levels of imbalance in the sensitive attribute (denoted by c) on randomly sampled subsets of ACSIncome-Ca of the same size.
We train FARE each subset separately and show Pareto plots, similar to those in Fig. 3, in Fig. 8. We observe that FARE is very robust to the level of imbalance, even for very high levels, such as 0.9, we only see small difference our Pareto curves (only the low-accuracy regime).
D.2 EXPERIMENTS WITH DIFFERENT DOWNSTREAM CLASSIFIERS
In this section, we compare different FRL methods on ACSIncome- CAC, similarly to Fig. 3 (left), the case when different downstream classifiers are used. In Fig. 9, we show the results on additional downstream classifiers:
Decision Tree with maximum 2500 leaves
Random Forest using 100 trees
Logistic Regression
Two-layer neural network with 50 neurons per layer
We observe that the general trends observed in Fig. 3 (left) for the different FRL methods hold re- gardless of the downstream classifier choice. We also see that the gap of method to the maximum achievable accuracy the smallest when the downstream classifier a tree. This is unsurprising given that FARE's own representations are based on trees. Further, we see that the more complex feature extraction of FCRL and sIPM-LFR allow them to gain better accuracy over the unfair base- line when using more simple classifier such as decision tree.
D.3 PERFORMANCE GAP ON LARGER DATASETS
In this section, we explore whether the small performance gap we observed in Fig. between FARE's most accurate model and the unfair baseline widens for larger datasets. To this end, we merge two ACSIncome-US datasets from two consecutive years (2014 and 2015) and compare the results to the single year dataset from 2014, shown in Fig. (right). We note that the merged dataset has roughly 2x the number of data points. The comparison between the merged and single- year datasets is shown Fig. 10. We observe almost no difference between the results on the two datasets for the unfair baseline well as the empirical and provable faimess of method. This suggests that the complexity of the dataset is more important factor than the data volume for the observed performance gap.
17

---

Under review as a conference paper at ICLR 2023
Bosefire
Untai Baseline
FORL
Demographio Parity Distance
(Upper (Empricaf)
Demographic Parity Distance
(Apprr
0.15
0.15
0.10
0.10
0.05
0.05
0.00
0.00
0.75
Accuracy
Accuracy
(a) Decision Tree
(b) Random Forest
Baseline
Undai Baseline
CVB
CviB
0.35
PCR
FCRI
PNF
SPM
Demagrapho Parity Distance
0.30
(Lupper
Demagraphio Parity Distance
(Empricaf)
0.25
0.20
0.15
0.05
0.05
0.00
0.00
Accuracy
Accuracy
(c) Logistic Regression
(d) Two-Layer NN
Figure Comparison between different downstream classifiers on different FRL methods on ACSIncome-CA.
E DIFFERENCES BETWEEN THEORETICALLLYPPIICCPPP FRL AND PROVABLY FAIR REPRESENTATION LEARNING
In this section discuss the differences between poarettcalll-principlee fair representation learn- ing, which is most of the prior work, and provably fair representation learning, which is our method.
Provably fair representation learning Here, first restate what kind of provable guarantee want to obtain for our learned representations.
use a finite set of n datapoints ((ar5), sU1) to learn representations 20) = f(x()) ,()) such that the DP distance of any classifier trained on these representations is bounded by some value with confidence 1 We consider practical scenarios, requiring 95% confidence, and n ranging from 100 000 roughly 000 000.
Note that this is the only type of guarantee that can provide an assurance to practitioner that their representations guarantee that is obtained using finite number samples, and bounds that are obtained under stronger assumptions such perfect convergence of the training procedure are less useful.
indeed fair. The practitioner only benefit from provable fairness
18

---

Under review as a conference paper at ICLR 2023
Unfair Baseline ACSincome 2014
Untair Baseline ACSincome_2014440 20144+055
0.25
ACSIncome (Uppor Bound)
FARE ACSIncome,201 (Empirical)
FARE ACSIncome 201422214220 4-2015 (Uoper Bound)
Demographic Parity Distance
FARE ACSIncome_201 4-2015 (Empirica))
0.20
0.15
0.10
0.05
0.00
0.74
0.76
0.78
0.80
0.82
Accuracy
Figure 10: Comparison of the performance gap between FARE and the Unfair Baseline on ACSIncome-US for single year and two years.
pntorretiaallyprnnipppte FRL We now discuss pooretically-princpphe FRL methods from prior work and, argued in Section 2, explain why they cannot achieve the guarantee of provable fairness using a finite number of samples, described above. These are the methods which use sound theory as basis for their representation learning algorithms. There several works that compute bounds DP distance using total variation, mutual information, and other techniques. However, to make the training practical they replace these bounds with approximations that cannot yield high-probability certificates with finite number of samples, which is what we call provably fair representation learning above.
For example, Madras et al. (2018) bound demographic parity using the accuracy of the optimal ad- versary for predicting sensitive attribute from the learned representations (which is also elosely connected to the TV distance between the representations). However, even in the case of known input distribution it is not possible to compute the optimal adversary for the learned representa- tions when using standard feedforward neural network encoders (this is discussed in more detail Balunović et al. (2022)). this direction, Feng et al. (2019) bound the accuracy the optimal Lipschitz continuous adversary (though the general optimal adversary does not have be Lipschitz continuous) using Wasserstein distance, which again cannot be provably bounded for finite number of samples. Kairouz et al. (2022) formulate the optimal adversary for each type of the reconstruction loss, but then explain that is not possible to compute those in practice (except for the restricted case when input distribution is e.g., a mixture of Gaussians), and they simply use it as motivation for min-max optimization in training. Perhaps the most advanced work in this direction is Balunović al. (2022) which proposes new architecture based on normalizing flows that essentially allows pushing the input distribution through the encoder to obtain the distribution of the latent represen- tations which can then be used estimate TV distance. However, in practice the input distribution is unknown and their certificate only holds for the estimated input distribution. Zhao et al. (2020) also show that the TV distance can bound the DP distance, but they provide no finite sample certifi- cate. They rely solving the min-max optimization problem where the objective is approximated and then approximately optimized using SGD. Thus, it is impossible to know whether the resulting representations indeed fair for any downstream classifier.
Another idea is based on the fact that the DP distance can be bounded with an expression involving mutual information between the representations and sensitive attribute. For example, Gupta et al. (2021) provide one such bound, but they use it as a motivation for their training algorithm and do not provide way to compute this bound finite sample dataset. Kim et al. (2022) bound the
19

---

Under review as a conference paper at ICLR 2023
DP distance using IPM (integral probability metric), which again cannot be computed with high probability using finite sample dataset. Tan et al. (2020) use classical sufficient dimension reduction framework to construct representations subspaces of reproducing kernel Hilbert space (RKHS), and apply this to obtain fair Gaussian processes, but they assume existence of fair subspace which might not generally hold. Similarly, Grünewääler & Khaleghi (2021) generate features oblivious to sensitive attributes using Hilbert-space--aluee conditional expectation and relaxed optimization of MMD criterion, which cannot provably guarantee fairness. All of these works fall into the category of peareticall--rinccpphe FRL, and they cannot provide a high-probability certificate of fairness using a finite number of samples.
20


Reviews:
[{"review_id": "yUow4RDRKG", "reviewer": "Reviewer_8jvQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "Fair representation learning (FRL) is a popular class of methods aiming to produce\nfair classifiers via data preprocessing, but accuracy-fairness tradeoffs are challenging to achieve using the current toolbox.  To this end, the authors develop\n\n- a practical statistical procedure that, for restricted encoders, upper bounds the unfairness of any downstream classifier trained on their representations.\n- an end-to-end FRL method, FARE, that instantiates this approach with a fair decision tree\nencoder and applies it to augment the representations with a tight provable upper bound on the unfairness of any downstream classifier.\n\nThe theoretical results are validated using many comparative experiments.", "summary_of_the_review": "The authors have developed a practical procedure for FRL, called FARE, with strong theoretical guarantees.  The numerical experiments confirm its promise relative to the alternatives. ", "strength_and_weaknesses": "This paper provides an excellent overview of the prior work on FRL, highlighting their strength and weakness.  The FARE procedure is practical and is backed by theoretical guarantees. The numerical experiments confirm its superiority over the competitors.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "t5RyU2YDpy", "reviewer": "Reviewer_2duo", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "", "summary_of_the_paper": "This paper proposes a method to learn fair representations, where the main focus of fairness is the classic demographic parity condition. Compared with existing methods to achieve this goal, algorithmically, the main difference is that, instead of using rich neural networks as the feature encoders, the authors proposed to use decision trees instead. The features are then encoded as the indices of leaf nodes in the decision tree. Theoretically, the main contribution is to provide a finite sample bound on the probability mass function over the feature space, which is estimated from finite samples. \n", "summary_of_the_review": "As mentioned in my detailed comments above, due to the limited technical contribution and the missing discussion with closely related works, I would recommend rejection.\n", "strength_and_weaknesses": "Strength:\nI didn't check the most recent literature extensively, but the idea of using decision trees as the feature encoders in learning fair representations appears new to me. \n\nWeakness:\nAlthough the application of decision trees as feature encoders in learning fair representations is new, this contribution alone is too incremental to grant acceptance into a major conference like ICLR. Perhaps more importantly, there are quite a few statements in the paper are too strong to be accurate. The authors overclaimed the contributions of this work while missing a lot of closely related works that have already provided fairness guarantees for downstream tasks. Let me elaborate.\n\n-   First of all, apparently, the authors appeared to think that the fairness guarantee of downstream tasks from the learned fair representations could only be obtained using the proposed method, but not from existing encoders with neural networks. This is false. No matter what the encoders are, one can always certify a DP gap for any downstream classifiers based on the learned fair representations. To be more specific, the DP gap for any downstream classifiers is given by the TV distance between Z_0 and Z_1. This is a simple consequence of the data-processing inequality for the TV-distance and the fact that the DP gap is nothing but the TV-distance of the predictions over two groups. See [1] Proposition 3.1 for more details. [1] also discusses the relationship between the TV-distance and the optimal balanced error rate, but is missing from the discussion. \n\n-   In light of the above argument, the real contribution of this work is Lemma 3 which provides a finite sample analysis for discrete distributions using Hoeffding's inequality. However, it still does not justify the \"inherent advantages of decision trees as feature encoders\". In fact, for any fixed neural network, one can also obtain such high-probability bounds as well by using non-parametric kernel density estimation. The only difficulty here is instead of estimating the probability mass function, which is easier to do because of the finite support, one needs to work with probability density. But in principle it is still doable, and one can then proceed to compute the TV-distance between the estimated density functions from the two groups, which will provide a DP gap for any downstream classifiers over the learned representations. \n\n-   A lot of the important and closely related works in theoretical understanding of learning fair representations are missing. I would suggest the authors to check the Related Work section of [2] for more reference. \n\nMore detailed comments:\n-   In the abstract, the authors mentioned that \"motivated by inherent advantages of decision trees\". What are the inherent advantages of decision trees here? Wouldn't any encoder that can provide discrete codes work? For example, consider the approach of Zemel et al.'13, couldn't we just use the deterministic cluster assignment (instead of a probabilistic one) as the codes? \n\n-   In Section 1, \"their claim about fairness of the downstream classifiers holds only for the models they considered during the evaluation, and does not guarantee ...\". This statement is false. As I explained above, the fairness guarantee on any downstream tasks is guaranteed, and this is just a simple application of the celebrated data-processing inequality. \n\n-   In Section 2, Paragraph \"Towards fairness guarantees\", \"...trained on the representations produced by these methods could have arbitrarily bad fairness\". Again, this is simply false. See [1] and [2]. \n\n-   Section 4, the discussion of the optimal balanced accuracy is not very deep. At least, one should point out its connection to the TV distance between the two feature distributions (Z_0 & Z_1). See [2] for more details.\n\n\n[1].    Conditional Learning of Fair Representations\n[2].    Fair Representation: Guaranteeing Approximate Multiple Group Fairness for Unknown Tasks\n", "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": {}}, {"review_id": "jU--hILKfiC", "reviewer": "Reviewer_bbjC", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "", "summary_of_the_paper": "This paper proposes a tree-based encoder for fair representation learning (FRL). The encoder transforms the input data such that downstream classifiers using the transformed data achieve some fairness guarantees. The authors focus on demographic parity as the fairness criterion in binary classification settings.\n\n\n", "summary_of_the_review": "I have some doubts regarding the novelty and soundness of the proposed approach (see the comments above).\n\nQuestions:\n- The related work [1] provides provable guarantees on the demographic parity. How does the result presented in the paper differ from those?\n- The restricted encoder is similar to the SDR approach (or sliced inverse regression) described in [2]. What are the advantages of the tree encoder?\n", "strength_and_weaknesses": "[Strengthes]\n1. The proposed restricted encoder is conceptually flexible and could potentially generalize to a large family of models.\n2. The objective based on optimal adversary could be useful for several other fair learning problems.\n3. Empirical results show that the proposed method attains improved fairness-accuracy tradeoffs than several popular approaches.\n\n[Weaknesses]\n- Novelty: the authors claim to provide the first provable FRL upper bound; however, provable FRL has been widely studied in literature:\n\n[1] Donini et al.,  Empirical risk minimization under fairness constraints, NeurIPS 2018\n\n[2] Tan et al., Learning Fair Representations for Kernel Models, AISTATS 2020\n\n[3] Grünewälder et al., Oblivious Data for Fairness with Kernels, JMLR 2021.\n\nThe problem setup of the paper is very similar to those considered in the above papers. Thus, novelty of the paper may not be justified without a comparison with the above related work.\n\n- Soundness: the proposed approach makes implicit  i.i.d. assumption for the data and sensitive attributes, and the results rely on the specific choice of the encoder. While the approach conceptually makes sense, the function class of the encoder is typically unknown for deep architectures. Thus, the results, which rely on a perfect encoder, may not hold in general. \n", "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": "PtYjA_kk1FL", "reviewer": "Reviewer_qvc4", "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": "", "summary_of_the_paper": "1. The motivation is to tackle the accuracy-fairness tradeoffs of fair representation learning (FRL), indicating the need of providing provable upper bounds on unfairness of downstream classifiers.\n2. They propose Fairness with Restricted Encoders (FARE), the first FRL method with provable fairness guarantees. They restrict the representation space ( i.e., limiting possible representations to a finite set {z 1 , . . . , z k } ) of the (upstream) decision-tree-based encoder.\n3. Experiment results on various datasets demonstrate FARE can produce tight upper bounds.\n", "summary_of_the_review": "Updated response after the second round discussion: the concern is the likelihood of missing literature of provable FRL and evaluation against such work. I am convinced after the discussion that the paper could be improved with the revision addressing this concern.", "strength_and_weaknesses": "1. Providing provably fairness is significant and useful.\n2. The evaluation part is sound.\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "N00_emCVUo", "reviewer": "Reviewer_1zmn", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "In this paper authors exploit the use of a restricted encoder to derive a provably fair (group fairness) representation which has the ability to upper bound the unfairness of any down stream classifier. They demonstrate this ability through the use of an optimal adversary, i.e., a classifier which tries to predict the sensitive variable given the representation. Such a bound is computable as the restriction in the encoder leads to a finite set of representations.", "summary_of_the_review": "This paper contributes to the very critical area of fair representation learning. The extensive literature survey and the clear description of the contributions of proposed technique in contrast with existing literature can make it a very good introduction paper for readers delving into this topic.\n\nThe experimental validation could be strengthened by focussing on tasks (at least simulated tasks) where the data sizes are larger. This can allow for the development of more powerful downstream classifiers which might help provide a stronger estimate of accuracy of an unfair classifier and thus the loss in accuracy due to the fair representation.\n\nIt would be also helpful if the authors discuss the impact of balance in the training data on the granularity of the restricted representations. It is not uncommon in many domains to be presented with datasets which are highly imbalanced w.r.t. sensitive variables. In such cases Fairness-aware categorical splits could possibly lead to uninformative representations for classification purposes. Adding a discussion on balance of training data would be helpful to readers dealing with such datasets.", "strength_and_weaknesses": "Strengths\n-----------\nClear derivations.\nSufficient experimental validation.\nVery clear demonstration of the core concepts even for a casual reader.\n\n\nWeaknesses\n---------------\nThe classifiers used for empirical validation are fairly simple, which might be suitable for the relatively small datasets being used. However using a diverse set of classifiers for empirical validation might be preferable.\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject