Fair Normalizing Flows
Authors: Mislav Balunovic
Anian Ruoss
Martin Vechev
Venue: ICLR 2022 Poster (2022)
Keywords: fairness
fair representation learning
adversarial fairness
trustworthy machine learning

Abstract: Fair representation learning is an attractive approach that promises fairness of downstream predictors by encoding sensitive data. Unfortunately, recent work has shown that strong adversarial predictors can still exhibit unfairness by recovering sensitive attributes from these representations. In this work, we present Fair Normalizing Flows (FNF), a new approach offering more rigorous fairness guarantees for learned representations. Specifically, we consider a practical setting where we can estimate the probability density for sensitive groups. The key idea is to model the encoder as a normalizing flow trained to minimize the statistical distance between the latent representations of different groups. The main advantage of FNF is that its exact likelihood computation allows us to obtain guarantees on the maximum unfairness of any potentially adversarial downstream predictor. We experimentally demonstrate the effectiveness of FNF in enforcing various group fairness notions, as well as other attractive properties such as interpretability and transfer learning, on a variety of challenging real-world datasets.

Published as a conference paper at ICLR 2022
FAIR NORMALIZING FLOws
Mislay Balunovié
Anian Ruoss*
ETH Zurich
ETH Zurich, DeepMind an rrnianrseen @ com
mi s sav. ba www.uuvii@ii.feetii..
Martin Vechev
ETH Zurich
martin. wwwweveinc.eeeeeeeeeeeeeeeee wwt.f.ehh.ccc ch
ABSTRACT
Fair representation learning is an attractive approach that promises fairesss downstream predictors by encoding sensitive data. Unfortunately, recent work has shown that strong adversarial predictors can still exhibit unfairness by recovering sensitive attributes from these representations. malizing Flows (FNF), new approach offering more rigorous fairness guarantees for learned representations. Specifically, we consider a practical setting where we can estimate the probability density for sensitive groups. The key idea is to model the encoder as a normalizing flow trained to minimize the statistical distance between the latent representations of different groups. The main advantage of FNF is that its exact likelihood computation allows us to obtain guarantees on the maximum unfairness of any potentially adversarial downstream predictor. We experimentally demonstrate the effectiveness of FNF in enforcing various group fairness notions, well other attractive properties such interpretability and transfer learning, on a variety of challenging real-world datasets.
this work, we present Fair Nor-
INTRODUCTION
As machine learning is increasingly being used in scenarios that can negatively affect humans (Bren nan al.] [209]] Khandani al. 2010) Barocas & Selbst 2016), fair representation learning has become one of the most promising ways to encode data into new, unbiased representations with high utility. Concretely, the goal is to ensure that representations have two properties: (i) they are informative for various prediction tasks of interest, (ii) sensitive attributes of the original data (e.g., race) cannot be recovered from the representations. Perhaps the most prominent approach for learning fair representations is adversarial training (Edwards & Storkey 2016 Madras al. 2018 Xie et al.
2017 Song et al. 2019; Roy & Boddeti 2019). which jointly trains an encoder trying to transform data into fair representation with adversary attempting recover sensitive attributes from the representation. However, several recent lines of work (Feng et al. 2019 Moyer et al. 2018 Blazar & Goldberg 2018 Xu al. 2020: Gupta al. 2021 [Sng Shmatikov 2020) have noticed that these approaches do not produce truly fair representations: stronger adversaries can in fact recover sensitive attributes. Clearly, this could allow malicious or ignorant users to use the provided representations to discriminate. This problem emerges at a time when regulators are crafting rules (Whittaker et al. 2018 EU 2021 FTC, 202T) on the fair usage of AI, stating that any entity that cannot guarantee non non-discrimnnation would be held accountable for the produced data. This raises the question: Can we learn representations which provably guarantee that sensitive altributes cannot be recovered?
This work Following prior work, we focus tabular datasets used for tasks such as loan or insurance assessment where fairness of high relevance. We assume that the original input data comes from two probability distributions po and Pl. representing groups with sensitive attributes a = 0 and a = 1, respectively. In the cases where distributions Pu and P1 are known, we will obtain provable faimess guarantees, and otherwise perform density estimation and obtain guarantees with respect to the estimated distribution. In our experimental evaluation we confirm that the bounds
Work performed while ETH Zurich.

---

Published as a conference paper at ICLR 2022
Pzu (+)
2g fo(m)
21 (1(()
P0t, (2)
(o(a)
FNF
3h: Ply h(xr)) s
(2) 28p = fo
3h Ply ((a))
Pa
By Pla o(x))) =
Vy P(a o(t)) 11 se
Figure 1: Overview of Fair Normalizing Flows (FNF). There are two encoders, fo and fi, that transform the two input distributions po and p1 into latent distributions p%, and pz, with a small statistical distance A 2 O. Without FNF, a strong adversary y can easily recover sensitive attribute from the original input æ, but once inputs are passed through FNF, we are guaranteed that any adversary that tries to guess sensitive attributes from latent z cannot be significantly better than random chance. At the same time, we can ensure that any benevolent user h maintains high utility.
computed on the estimated distribution in practice also bound adversarial accuracy on the true distribution, meaning that density estimation works well for the setting consider.
To address the above challenges, we propose Fair Normalizing Flows (FNF), new method for learning fair representations with guarantees. In contrast other approaches where encoders standard forward neural networks, we instead model the encoder as a normalizing flow (Rezende) & Mohamed| 2015). Fig. [ provides high-level overview of FNF. As shown the left in Fig. [ using raw inputs æ allows us to train high-utility classifiers h, but at the same time does not protect against the existence of malicious adversary g that can predict a sensitive attribute a from the features in æ. Our architecture consists of two flow-based encoders fo and fi. where flow fa transforms probability distribution Pa (x) into pz. (z) )) by mapping æ into z = (x). The goal of the training procedure is to minimize the distance A between the resulting distributions pz, (z) and Pz, (z) ) so that an adversary cannot distinguish between them. Intuitively, after training our encoder, each latent representation z can be inverted into original inputs xg (z) and 2 = ( that should ideally have similar probability w.r.t. Po and pl. meaning that even the optimal adversary cannot distinguish which of them actually produced latent z. Crucially, as normalizing flows enable us compute the exact likelihood in the latent space, for trained encoders
upper bound the accuracy of any adversary with 1+ which should be small if training was successful. Furthermore, 2
the distance A provides tight upper bound (Madras al. 2018) on common fairness notions such as demographic parity (Dwork et al.) (012) and equalized odds (Hardt et al.. 2016). As shown on the still train high-utility classifiers h using our representations, but now can
right in Fig. [ actually guarantee that no adversary g can recover sensitive attributes better than chance.
We empirically demonstrate that FNF can substantially increase provable fairness without significantly sacrificing accuracy on several common datasets. Additionally, we show that the invertibility of FNF enables algorithmic recourse, allowing to examine how reverse a negative decision outcome.
Main contributions Our key contributions
A novel fair representation learning method, called Fair Normalizing Flows (FNF), which guarantees that the sensitive attributes cannot be recovered from the learned representations at the cost of a small decrease in classification accuracy.
Experimental evaluation demonstrating that FNF can provably remove sensitive attributes from the representations, while keeping accuracy for the prediction task sufficiently high.
Extensive investigation of algorithmic recourse and applications of FNF transfer learning.
2

---

Published as a conference paper at ICLR 2022
2 RELATED WORK
In this work, we focus on group fairness, which requires certain classification statistics to be equal across different groups of the population. Concretely, we consider demographic parity (Dwork et al.
2012), equalized odds (Hardt et al. (016), and equality of opportunity (Hardt et al. (016). which
widely studied in the literature (Edwards & Storkey| 2016 Madras al.) 2018 Zemel al.)
2013). Algorithms enforcing such fairness notions target various stages of the machine learning
pipeline: Pre-processing methods transform sensitive data into an unbiased representation Zemel ct al. 2013 McNamara et al. 2019)), in- proccsssssnng methods modify training by incorporating faimess constraints (Kamishima et al. 2011 Zatar al., 2017). and post-processing methods change the predictions of pre-trained classifier (Hardt et al. 2016). Here, we consider fair representation learning (Zemel et al. 2013). which computes data representations that hide sensitive information, e.g. group membership, while maintaining utility for downstream tasks and allowing transfer learning.
Fair representation learning Fair representations can be learned with a variety of different ap-
proaches, including variational autoencoders (Moyer et al. [0188] Louizos et al. 2016). adversarial
training (Edwards& & Storkey, [2016] Madras et al. 2018|] Xie et al. [017]] [Sng et al. 2019 Roy &
Boddeti 2019 Liao et al.] 2019 Jaiswal al. 2020 Feng al. 2019), and disentanglement (Crea- ger et al. 2019 Locatello et al., 2019). Adversarial training methods minimize a lower bound on
demographic parity, namely an adversary's accuracy for predicting the sensitive attributes from the latent representation. However, since these methods only empirically evaluate worst-case unfair- ness, adversaries that are not considered during training can still recover sensitive attributes from the learned representations (Feng et al., 2019; Moyer et al., 2018, Elazar & Goldberg, 2018 Xu al. 2020) Gupta et al.) [022]]Song & Shmatikov 2020). These findings illustrate the necessity of learning representations with provable guarantees on the maximum recovery of sensitive information regardless of the adversary. which precisely the goal of our work. Prior work makes first steps in this direction: Gupta et al. (2021) upper bound monotonically increasing function of demographic parity with the mutual information between the latent representation and sensitive attributes. However, the monotonic nature of this bound prevents computing guarantees on the reconstruction power of the optimal adversary. Feng et al. (2019) minimize the Wasserstein distance between latent distributions of different protected groups, but only provide upper bound on the performance of any Lipschitz continuous adversary. However, as we will show, the optimal adversary is generally discontinuous. A concurrent work (Cerrato al. 2022) also learns fair representations using normalizing flows, but different to us, they do not use exact likelihood computation to provide theoretical fairness guarantees.
Provable fairness guarantees The ongoing development of guidelines on the fair usage of AI [Whttakerr et al., 2018 EU 2021: FTC (021) has spurred interest in provably fair algorithms. Unlike this work, the majonty of these efforts (McNamara et al. 2019 John al., 2020 UUban et al.) 2020: Ruoss et al. 2020) focus on individual fairness. Individual fairness is also tightly linked to differential privacy (Dwork et al., 2012 2006), which guarantees that an attacker cannot infer whether given individual was present in the dataset not, but these models can still admit reconstruction of sensitive attributes by leveraging population- level correlations (Jagielski et al. 2019). Group fairness certification methods (Albarghouthi et al. 2017 Bastani et al. 2019 Segal et al. 2020) generally only focus on certification and, unlike our work, do not learn representations that are provably fair.
BACKGROUND
We assume that the data (zz, a) E Rd comes from a probability distribution p. where æ represents the features and represents sensitive attribute. In this work, we focus on the case where the sensitive attribute is binary, meaning A = {0, 1). Given p, we can define the conditional probabilities as pa())) = P(æ: (ar, a) to a label y E 10, which may or may not be correlated with the sensitive attribute a. Our goal is to build classifier
0) and pi (æ) P(æ: a 1). We are interested in classifying each sample
h(x)) that tries to predict y from the features æ. while satisfying certain notions of fairness. Next, we present several definitions of faimess relevant for this work.
Fairness criteria A classifier h satisfies demographic parity if it assigns positive outcomes to both sensitive groups equally likely, ie.. P(h(x) = 1 a = 0) = P(h(z) = a = 1). If demographic parity cannot be satisfied, we consider demographic parity distance, defined as
3

---

Published as a conference paper at ICLR 2022
EE [h(z) a= E [h(x)) 1]1. An issue with demographic parity occurs if the base rates differ among the attributes, Le., P(y = 1| a = 0) * p(y=1 a = 1). In that case, even the ground truth label y does not satisfy demographic parity. Thus, Hardt et al. (016)) introduced equalized odds, which requires that P(h(ar) =
yo: a = 0) = P(h(m)) = y yo, a = 1) for yo E {0. 1}.
Fair representations Instead of directly predicting y from æ. Zemel et al. 2013 introduced the idea of learning, fair representations of data. The idea is that data producer preprocesses the original data x to obtain new representation = = f(x,,) a). Then, any data consumer, who is using this data to solve a downstream task, can use as an input to the classifier instead of the original data æ. Thus, the data producer can ensure that data representation fair (w.r.t. some faimess notion), then all classifiers employing this representation will automatically inherit the faimess property. However, due to inherent biases of the dataset, this fairness increase generally results in a small accuracy decrease (see Appendix for an investigation of this tradeoff in the context of our method).
Normalizing flows Flow-based generative models (Rezende & Mohamed, 2015 Dinh et al. 2015 2016 Kingma & Dhariwal (2188) provide an attractive framework for transforming any probability distribution into another distribution q. Accordingly, they are often used to estimate densities from data using the change of variables formula on a sequence of invertible transformations, so-called normalizing flows (Rezende & Mohamed] (015). In this work, however, we mainly leverage the fact that flow models sample a latent variable z from density g(z) and apply an invertible function fa- parametrized by 0. to obtain datapoint æ = =fo (z). Given density (xx,, the exact log-liilldooo is then obtained by applying the change of variables formula log ((x) log 7(z) (dz/
Thus, for fo f1 o f2 o .... o fK with ro = x: (r( = Tú and rk = z, we have
K
log g(x) = log ((z) + Σ
log det (edr///dr/ddr
(1)
clever choice of transformations Sa (Rezende Mohamed 2015; Dinh et al. 2015 2016) makes the
computation of the log-determinant tractable, resulting in efficient training and sampling. Alternative generative models cannot compute the exact log- liceliidl (c.g., VAEs (Kingma & Welling 2014), GANs (Goodfellow et al. 2014)) or have inefficient sampling (e.g.. autoregressive models). Our approach is also related to discrete flows (Tran et al.) 2019 Hoogeboom et al., 2019) and alignment
flows (Grover al., 2020 Usman al. (020). However, alignment flows jointly learn the density
and the transformation, unlike the fairness setting where these are computed by different entities.
4 MOTIVATION
In this section, we motivate our approach by highlighting some key issues with fair representation learning based on adversarial training. Consider distribution of samples x = (x2) R² divided
into two groups, shown as blue and orange in Fig. 2 The first group with a sensitive attribute a = 0 has a distribution (2) ~ Po. where po is a mixture of two Gaussians ([[-3, 3) and ([3, 3). f). The second group with sensitive attribute a = 1 has a distribution (21) ~ p1. where p1 is mixture of two Gaussians W([33, -3], I) and ( 33,, The label of a point (æ1, 22) is defined sign( and 0 otherwise. Our goal is to learn data representation = f(x a) such that is impossible to recover a from z, but still possible to predict target from z. Note that such representation exists for our task: simply setting = = s(x a) = (-1 1) makes
by 1 if 1
it impossible to predict whether a particular z corresponds to a = 0 or a = 1, while still allowing us to train classifier h with essentially perfect accuracy (c.g., h(2) = (=120)).
Adversarial training for fair representations Adversarial training (Edwards & Storkey 2016 Madras et al. 2018)) is an approach that trains encoder and classifier h jointly with an adversary g trying to predict the sensitive attribute a. While the adversary tries to minimize its loss Lade, the encoder and classifier h are trying to maximize Lade and minimize the classification loss Las as
min max B( [aa a), (faae((x g). f.h gEg
where G denotes the model family of adversaries, e.g., neural networks, considered during training. Unfortunately, there two key issues with adversarial training. First, it yields non-convex
4

---

Published as a conference paper at ICLR 2022
30
20
10
0.5
0.6
0.7
0.8
0.9
1.0
Recovered sensitive
Figure 2: Samples from our example distribu- is sampled from
Figure 3: Sensitive attribute recovery rates for adversarial training and fair normalizing flows (FNF) with 100 different random seeds.
tion. The blue group Po and the orange group (a = 1) is sampled from p1-
optimization problem, which usually cannot be solved to optimality because of saddle points. Second, it assumes that the adversary 9 comes from fixed model family G, which means that even if the optimal g E G cannot recover the sensitive attribute o, adversaries from other model families can still do as demonstrated in recent work (Feng et al., 2019 Moyer et al. 2018 Elazar & Goldberg 2018 Xu et al. 2020 Gupta et al.] (021). To investigate these issues, we apply adversarial training to learn representations for our synthetic example, and measure how often the sensitive attributes can be recovered from learned representations. Our results, shown in Fig. 3 repeated 100 times with different seeds, demonstrate that adversarial training is unstable and rarely results in truly fair representations (where only 50% can be recovered). In Section 6 we follow up on recent work and show that several adversarial fair representation learning approaches do not work against adversaries from a different model familiy (e.g.. larger networks). In Fig, we show that our approach, introduced next, can reliably produce fair representations without affecting the utility.
FAIR NORMALIZING FLOWS
Throughout this section we will assume knowledge of prior distributions po(#)) and pi (æ)). At the end of the section, we discuss the required changes if we only work with estimates. Let Zo and 2, denote conditional distributions of z f(x a) for a (0, 1}, and let Pz. and pz, denote their respective densities. Madras et al. (018)) 1) have shown that bounding the statistical distance Apz.. pz,) between Zo and Z1 provides an upper bound on the unfairness of any classifier h built on top of the representation encoded by f. The statistical distance between Zo and Z1 is defined similarly to maximum mean discrepancy (MMD) (Gretton et al. 2006) between the two distributions:
A (p PZ,)
sup Ez - E2w2, Fe<2)]u(=)], [u(2)]] MEB
where μ:: IRd + {0, 13 is a function in of all binary classifiers B trying discriminate between Zn and 2, If we can train an encoder to induce latent distributions Zn and 21 with statistical distance below some threshold, then we can both upper bound the maximum adversarial accuracy by (1+ Appz, ..,...z,)))) P2,))/2 and, using the bounds from Madras et al. (2018), obtain guarantees for demographic parity and equalized odds of any downstream classifier h. Such guarantees are unattainble for adversarial training, which minimizes lower bound of Apzz, pz, In contrast, learn fair representations that allow computing the optimal adversary jr" attaining the supremum in Eq. (3 and thus enable exact evaluation of A (p2. Pz, )-
Optimal adversary In the following lemma we state the form of an optimal adversary which attains the supremum in the definition of statistical distance in Eq. (3). We show the proof in Appendix A.
Lemma 5.1. The adversary μ² attaining the supremum in the definition of ((p P2,) can be defined as 4 (z) = (rzo (z) (z)). namely it evaluates to 1 if and only if pz, (z) S Pz, (z).
This intuitively makes sense given some representation x, the adversary computes likelihood under both distributions 2n and 2,, and predicts the attribute with higher likelihood for that Liao et al.
5

---

Published as a conference paper at ICLR 2022
(011 also observed that the optimal adversary be phrased arg argmax, p(a[z) So far, prior work mostly focused on mapping imput æ to the latent representation x = fo (z a) via standard neural networks. However, for such models, given densities (o( and pi (zx) over the imput space, it is intractable to compute the densities pzo (z) and p2, (z) in the latent space as many inputs x can he mapped to the same latent and we cannot use inverse function theorem. Consequently, adversarial training methods cannot compute the optimal adversary and thus resort to a lower bound.
Encoding with normalizing flows Our approach, named Fair Normalizing Flows (FNF), consists of two models, fo and fi, that encode inputs from the groups with sensitive attributes a = 0 and 1, respectively. We show high-level overview of FNF in Fig. D Note that models fo and fi are parameterized by dg and 01. but we do not write this explicitly to ease the notation. Given some imput 2o ~ po. it is encoded to z fo( inducing a probability distribution Zo with density pz. (z) over all possible latent representations 2. Similarly, inputs I1 P1 are encoded to
fi (21). inducing the probability distribution 21 with density pz; (z). Clearly, if we can train fo and fi so that the resulting distributions Zo and Z have small distance, then we can guarantee fairness of the representations using the bounds from [Madras et al. (2018). As evaluating the statistical distance is intractable for most neural networks, we need a model family that allows us to compute this quantity.
We propose to use bijective encoders So and S1 based on normalizing flows (Rezende & Mohamed 2015) which allow us to compute the densities at z using the change of variables formula
a.
log
pz. Pz.
(z) (fa (z)) + log det
(4)
provides a form of the optimal adversary. To compute the statistical distance it remains to evaluate the expectations Bz~zo Jue (z)] and Eg [u* (z)]. Sampling from Zo and 21 is straightforward - we can sample Ty ~ Po and Φ1 ~ pr. and then pass the samples zp and 21 through the respective encoders fo and f1 to obtain zu Zo and 21 Z1. Given that the outputs of μr" are bounded between and I, we can then use Hoeffding inequality to compute the confidence intervals for our estimate using finite number of samples.
for a E 13. Recall that Lemma 5.1
Lemma 5.2. Given a finite number of samples why zy D ~ Po and æt xq x" ~ PL, denote as =0 = fo(at) and z = (xx) and let Áppz. A(zz.P2,) = 1/ E. 1 (2))
Ei= 10 (=1)) be
an empirical estimate of the statistical distance Appz. (P,).PZ,). Then, for n 2 2 log
I-VI-A /e2
2
we are guaranteed that A(pz. pZ,) S Á(pz.) + with probability at least 1 8.
Training flow-based encoders The next challenge is to design a training procedure for our newly proposed architecture. The main issue is that the statistical distance not dif- ferentiable (as the classifier μe" is binary), so we replace it with a differentiable proxy based on the symmetrized KL. divergence, shown in Lemma 5.3 below (proof provided in Ap- pendix A.I We show high-level description of our training procedure in Algorithm [T] In each step. sample a batch of œn and 21 from the respective distributions and encode them to the representations 2n and 21. We then esti- mate the symmetrized KL divergence between distributions Zo and Z,, denoted as Lo + L1. and combine it with classification loss Lelf using tradeoff parameter 7 and perform a gra- dient descent step to minimize the joint loss.
Algorithm 1 Learning Fair Normalizing Flows
Input: N, BB, po: P1 Initialize h, for fi with parameters On Po. 01 for i to N do
for j = 1 to B do
Sample x/ ~ Po: x/ ~ P1
z/ fo(xz)
z fi fxxz) end for
Lo B Σ 1=1 (log (z log Pz, (z())
L B Σ 1= (log p2, (z)) log Pz, (z1))
L= (Cn + L1)+ +
L)
Update 02 - 0. - -aa aV C. for E (0, 1}
Update 02 0₂ a
end for
While we use convex scalarization scheme to obtain the joint loss in Algorithm I our approach is independent of the concrete multi-objective optimization objective (see Appendix
Lemma 5.3. We can bound Alpz. pz, )2 < (K p2,) + KL(p,,
Bijective encoders for categorical data Many fairness datasets consist of categorical data, and often even continuous data is discretized before training. In this case, will show that the optimal

---

Published as a conference paper at ICLR 2022
bijective representation can be easily computed. Consider the case of discrete samples x coming from a probability distribution p(æ) where each component Fj takes a value from a finite set {1, 2,...... d.). Similar to the continuous case, our goal is to find bijections fo and fi that minimize the statistical distance of the latent distributions. Intuitively, we want to pair together inputs that have similar probabilities in both Po and p1. In Lemma 5.4 we show that the solution that minimizes the statistical distance is obtained by sorting the inputs according to their probabilities in po and Pl. and then matching inputs the corresponding indices in these two sorted arrays. As this can result in a bad classification accuracy when inputs with different target labels get matched together, we can obtain another representation by splitting inputs in two groups according to the predicted classification label and then matching inputs in each group using Lemma 5.4 We can trade off accuracy and fairness by randomly selecting one of the two mappings based on a parameter 7.
X - X. Denote ,,,12, i2, bm and -i Im permutations of 21. ...., m) such that po po(;;; S po( S... S pr(aas... and pi (z S pi(a),)) S ... S p ). The encoders defined by mapping fo(xx) = Ik and f((x))) = Dig are bijective representations with the smallest possible statistical distance.
Lemma 5.4. Let = [21,.... Lm and bijections Jo,
Statistical distance of true vs. estimated density In this work we assume access to density of the inputs for both groups and we provably guarantee fairness with respect to this density. While it is sensible in the cases where the density estimate can be trusted (e.g.. if it was provided by regulatory agency), in many practical scenarios, and our experiments in Section o we only have an estimate po and pi of the true densities po and pl- We now want to know how far off our guarantees are compared to the ones for the true density. The following theorem provides a way to theoretically bound the statistical distance between Pz. and pz, using the statistical distance between Pz. and pz.-
Theorem 5.5. Let po and ii be density estimates such that TV (şo, po) < < and TV (fi, < </22. where TV stands the total variation between two distributions. we denote the latent distributions fo(po) and f1()1) as pz. and pz, then (pZ. (pzo:PZ,) P2,) S A(pz. d2,) + c.
This theorem can be combined with Lemma 5.2 obtain high probability upper bound on the statistical distance of the underlying true densities using estimated densities and a finite number of samples. Computing exact constants for the theorem is often not tractable, but as we will show experimentally, in practice the bounds computed on the estimated distribution in fact bound adversarial accuracy on the true distribution. Moreover, for -i-diimnsional data relevant to fairness, obtaining good estimates can be provably done for models such as Gaussian Mixture Models (Hardt & Price 2015) and Kernel Density Estimation (Jiang 2017p. We can thus leverage the rich literature on density estimation (Rezende& & Mobamed 22055) Dinh et al. 2016 van den Oord et al. 2016a c to estimate Po and fr. Importantly, FNF is agnostic to the density estimation method (as we show in Appendix C and can benefit from future advances in the field. Finally, we note that density estimation has already been applied in a variety of security-critical areas such as fairness (Song et al. 2019), adversarial robustness (Wong& & Kolter 2020), and anomaly detection (Pidhorskyi al. 2018).
EXPERIMENTAL EVALUATION
In this section, we evaluate Fair Normalizing Flows (FNF) on several standard datasets from the fairness literature. We consider UCI Adult and Crime (Dua & Graff] (017), Compas (Angwin et al. 2016), Law School (Wightman) 2017). and the Health Heritage dataset. We preprocess Compas and Adult into categorical datasets by discretizing continuous features, and we keep the other datasets as continuous. Moreover, we preprocess the datasets by dropping uninformative features, facilitating the learning of good density estimate, while keeping accuracy high (details shown in Appendix (B) We make all of our code publicly available at httttss: gi thub.
sri/fnff
Evaluating Fair Normalizing Flows We first evaluate FNF's effectiveness in learning fair repre- sentations by training different FNF models with different values for the utility vs. fairness tradeoff parameter 7, We estimate input densities using RealNVP (Dinh et al. 2016) for Health, MADE (Ger) main et al. 2015) for Adult and Compas, and Gaussian Mixture Models (GMMs) for the rest (we experiment with other density estimation methods in Appendix C). For continuous datasets RealNVP as encoder, while for categorical datasets we compute the optimal bijective representations
using Lemma 5.4 Fig. 4 shows our results, each point representing single model, with models on
7

---

Published as a conference paper at ICLR 2022
0.435
0.81
0.83
0.75
0.755
0.750
0.725
0,700
0.63
0.435
0.2
5.4
8.6
0.0
1.
0.30
0.12
0.34
0.36
3.38
0.00
6.22
5.24
Statis distance
Stotisicaal distonce
(a) Continuous datasets
(b) Categorical datasets
Figure 4: Fair Normalizing Flows (FNF) continuous and categorical data. The points show different accuracy vs. statistical distance tradcoffs (with 95% confidence intervals from varied random seeds), demonstrating that FNF significantly reduces statistical distance while retaining high accuracy.
Table I: Adversarial fair representation learning methods are only fair w.r.t adversaries from training family G while FNF provides provable upper bound on the maximum accuracy of any adversary.
Adv Ace
9 9
9 g
Max Adv
ADV FORGETTING Jaiswal et al. 2020 MAXENT-AR ARI (Roy & Bodien 2019
85,99
66.68
74.50
85.90
50.00
85.18
LAFTR (Madras et 2018 PNF (our work)
86.09
72.05
84,58
84.43
N/A
59.56
61.12
the right focusing on classification accuracy, and models on the left gradually increasing their fairness focus. The results in Fig. averaged over 5 random seeds, indicate that FNF successfully reduces the statistical distance between representations of sensitive groups while maintaining high accuracy. We observe that for some datasets (e.g., Law School) enforcing fairness only slightly degrades accuracy. while for others there is substantial drop (e.g.. Crime). In such datasets where the label and sensitive attribute are highly correlated we cannot achieve fairness and high accuracy simultaneously (Menon & Williamson] 2018 Zhao & Gordon 2019). Overall, we see that FNF is generally insensitive to the random seed and can reliably enforce fairness. Recall that we have focused on minimizing statistical distance of learned representations because, mentioned carlier, Madras et al. (2018) have shown that fairness metrics such as demographic parity. equalized odds and equal opportunity can all be bounded by statistical distance. For example, FNF reduces the demographic parity distance of classifier on Health from 0.39 to 0.08 with an accuracy drop of 3.9% (we provide similar results showing FNF's good performance for equalized odds and equality of opportunity in Appendix C
Bounding adversarial accuracy Recall that the guarantees provided by FNF hold for estimated densi- ties po and f1. Namely, the maximum adversarial ac- curacy for predicting whether the latent representation originates from distribution 2, 2, is bounded by (1+A(pz, -0, /2. In this experiment, we investigate how well these guarantees transfer the underlying distributions Z, and Z,. In Fig. 5 we show our upper bound on the adversarial accuracy computed from the statistical distance using the estimated densities (diag- onal dashed line), together with adversarial accuracies obtained by training an adversary, multilayer percep- tron (MLP) with two hidden layers of 50 neurons, for
Law
Cr
accuraey
0.9
Health
Compas
Addt
0.5
0.2
0.6 Statistical distance
Figure 5: Bounding adversarial accuracy.
each model from Fig. 4 We also show 95% confidence intervals obtained using the Hoeffding bound from Lemma 5.2 We observe that our upper bound from the estimated densities fa and P1 provides a tight upper bound the adversarial accuracy for the true distributions Zq and Z1. This demonstrates that, even though the exact constants from Theorem 5.3 are intractable, our density estimate is good enough in practice, and our bounds hold for adversaries the true distribution.
8

---

Published as a conference paper at ICLR 2022
Comparison with adversarial training We now compare FNF with adversarial fair representation
learning methods on Adult dataset: LAFTR-DP (y = 2) (Madras et al.] 2018). MaxEnt-ARL
(a 10) (Roy& & Boddeti 2019), and Adversarial Forgetting (p = 0.001, ò 1, 0.1) (Jissaal et al. 2020). We train with a family of adversaries g trying to predict the sensitive attribute from the latent representation. Here, the families G are ML.Ps with hidden layer of 8 neurons for LAFTR-DP, and 2 hidden layers with 64 neurons and 50 neurons for MaxEnt-ARI and Adversarial Forgetting, respectively, In Table we show that these methods generally prevent adversaries from G to predict the sensitive attributes. However, we can still attack these representations using either larger MLPs (3 layers of 200 neurons for LAFTR-DP) or simple preprocessing steps (for MaxEnt- ARL and Adversarial Forgetting) as proposed by Gupta et al. (2021) (essentially reproducing their results). Our results confirm findings from prior work (Feng et al. 2019 Xu et al. 2020 Gupta et al. 202T): adversarial training provides no guarantees against adversaries outside G. In contrast, FNF computes a provable upper bound on the accuracy of any adversary for the estimated input distribution, and Table T shows that this extends to the true distribution. FNF thus learns representations with significantly lower adversarial accuracy with only minor decrease in task accuracy.
Algorithmic recourse with FNF We next experiment with FNF's bijectivity to perform recourse, i... reverse an unfavorable outcome, which is considered to be fundamental to explainable algorithmic recision-making VVenkatasubramaniaan & Alfano 2020). To that end, we apply FNF with y 1 to the Law School dataset with three features: LSAT score, GPA, and the college to which the student applied (ordered decreasingly in admission rate). For all rejected applicants, i.e., E such that f (x)) h=z) = O, we compute the closest 2 (corresponding to point E from the dataset) w.r.t. the fz-distance latent space such that l())) 1. We then linearly interpolate between z and E to find (potentially crude) approximation of the closest point to in latent space with positive prediction. Using the bijectivity of our encoders, we can compute the corresponding average feature change in the original space that would have caused a positive decision: increasing LSAT by 4.2 (non-whites) and 7.7 (whites), and increasing GPA by 0.7 (non-whites) and 0.6 (whites), where we only report recourse in the cases where the college does not change since this may not be actionable advice for certain applicants (Zhang et al.) 2018 Ustun et al.) 2019 Poyiadzi et al., 2020). In
Appendix C
we also show that, unlike prior work, FNF enables practical interpretability analyses.
Flow architectures In the next experiment we compare the RealNVP encoder with an alternative encoder based on the Neural Spline Flows architecture (Durkan et al., (019) for the Crime dataset. In Table we show the statistical distance and accuracy for models obtained using different values for the tradeoff parameter 7. We can observe that both flows offer similar performance. Note that FNF will benefit from future advances in normalizing flows research, as it is orthogonal to the concrete flow architecture that is used for training.
Table 2: FNF performance with dif- ferent flow encoder architectures.
ReaINVP
NSF
7
A
Acc
A
Acc
0.00
1.00
0.85
1.00
0.84
0.70
0.85
0.71
0.85
0.10
0.53
0.83
0.54
0.83
0.23
0.69
0.69
Transfer learning Unlike prior work, transfer learning with FNF requires no additional reconstruc- tion loss since both encoders are invertible and thus preserve all information about the input data. To demonstrate this, we follow the setup from Madras et al.] (2018) and train a model to predict the Charlson Index for the Health Heritage Prize dataset. We then transfer the learned encoder and train a classifier for the task of predicting the primary condition group. Our encoder reduces the statistical distance from 0.99 to 0.31 (this independent of the label). For the primary condition group MSC2a3 retain the accuracy at 73.8%, while for METAB3 it slightly decreases from 75.4% to 73.1%.
7 CONCLUSION
We introduced Fair Normalizing Flows (FNF), new method for learning representations ensuring that no adversary can predict sensitive attributes at the cost of a small accuracy decrease. This guarantee is stronger than prior work which only considers adversaries from restricted model family, The key idea is to use an encoder based on normalizing flows which allows computing the exact likelihood in the latent space, given an estimate of the input density. Our experimental evaluation on several datasets showed that FNF effectively enforces faimess without significantly sacrificing utility, while simultaneously allowing interpretation of the representations and transferring to unseen tasks.

---

Published as a conference paper at ICLR 2022
ETHICS STATEMENT
Since machine learning models have been shown to reinforce the human biases that are embedded in the training data, regulators and scientists alike are striving to propose novel regulations and algorithms to ensure the fairness of such models. Our method enables data producers to learn fair data representations that are guaranteed be non din--criminntoryy regardless of the concrete downstream use case. Since our method relies accurate density estimates, we envision that the data regulators, whose tasks already include determining fairness criteria, data sources, and auditing results, would create regulatory framework for density estimation that can then be realized by, c.g.. industrial partners. Importantly, this would not require regulators to estimate the densities themselves. Nevertheless, data regulators would need to take great care when formulating such legislation since the potential negative effects of poor density estimates are still largely unexplored, both the context of our work and in the broader field (particularly for nigh-dimensional data). In this setting, any data producer using our method would then be able to guarantee the fairness of all potential downstream consumer models.
REFERENCES
Aws Albarghouthi, Loris Antoni, Samuel Drews, and Aditya V. Nori. Fairsquare: probabilistic verification of program fairness. Proc. ACM Program. Lang., 2017.
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias, 2016.
Solon Barocas and Andrew D. Selbst. Big data's disparate impact. California Law Review, 2016.
Osbert Bastani, Xin Zhang, and Armando Solar-Lezama. Probabilistic verification of fairness properties via concentration. Proc. ACM Program. Lang., 2019. 2019.
Tim Brennan, William Dieterich, and Beate Ehret. Evaluating the predictive validity of the compas risk and needs assessment system. Criminal Justice and Behavior, 2009.
Mattia Cerrato, Marius Köppel, Alexander Segner, and Stefan Kramer. Fair group-shared representa- tions with normalizing flows. arXiv preprint arXiv:2201.06336 2022.
Elliot Creager, David Madras, Jörn-Henrik Jacobsen, Marissa A. Weis, Kevin Swersky, Toniann Pitassi, and Richard S. Zemel. Flexibly fair representation learning by disentanglement. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Laurent Dinh, David Krueger, and Yoshua Bengio. NICE: non-linear independent components estimation. 3rd International Conference on Learning Representations, 2015.
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using real NVP. CoRR, 2016.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
Conor Durkan, Artur Bekasov, lain Murray, and George Papamakarios. Neural spline flows. Advances in Neural Information Processing Systems, 2019.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Third Theory of Cryptography Conference, 2006.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard S. Zemel. Fairness through awareness. In Innovations in Theoretical Computer Science 2012, 2012.
Harrison Edwards and Amos J. Storkey. Censoring representations with an adversary. 4th International Conference Learning Representations, 2016.
Yanai Elazar and Yoav Goldberg, Adversarial removal of demographic attributes from text data. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, 2018.
EU. Proposal for regulation laying down harmonised rules artificial intelligence, 2021.
10

---

Published as a conference paper at ICLR 2022
Rui Feng. Yang Yang, Yuehan Lyu, Chenhao Tan, Yizhou Sun, and Chumping Wang. Learning fair representations via an adversarial framework. CoRR, abs/ 0as//194.1100 903,1334,, 2019.
Flaticon.com. Image, 2021.
FTC. Aiming for truth, fairness, and equity in your company's use of ai, 2021. URL ftc. http:://www......ooo/essssssssss
truth aiming-truth- fairness orw.aathwa..aaaaaaeeetooooorooaa
Mathieu Germain, Karol Gregor, lain Murray, and Hugo Larochelle. MADE: masked autoencoder for distribution estimation. In Proceedings of the 32nd International Conference Machine Learning, 2015.
lan J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems 27, 2014.
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander J. Smola. A kernel method for the wvo-sample-problene In Advances in Neural Information Processing Systems 19, 2006.
Aditya Grover, Christopher Chute, Rui Shu, Zhangjic Cao, and Stefano Ermon. Alignflow: Cycle consistent learning from multiple domains via normalizing flows. In AAAI, pp. 4028 4028-4035. AAAI Press, 2020.
Umang Gupta, Aaron Ferber, Bistra Dilkina, and Greg Ver Steeg. Controllable guarantees for fair outcomes via contrastive information estimation. CoRR, abs/2101.0410 004108, 2021.
Moritz Hardt and Eric Price. Tight bounds for learning mixture of two gaussians. In Rocco A. Servedio and Ronitt Rubinfeld (eds.), Proceedings of the Forty-Seventh Anmual ACM on Symposium on Theory of Computing, 2015.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems 29, 2016.
Yuzi Hc, Keith Burghardt, and Kristina Lerman. Learning fair and interpretable representations via linear orthogonalization. CoRR, abs/1910. 12854, 2019.
Emiel Hoogeboom, Jorn W. T. Peters, Rianne den Berg, and Max Welling. Integer discrete flows and lossless compression. In NeurlPS, pp. 12134-1211 12144, 2019.
Matthew Jagielski, Michael J. Kearns, Jieming Mao, Alina Oprea, Aaron Roth, Saeed Sharifi- Malvajerdi, and Jonathan R. Ullman. Differentially private fair learning. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Ayush Jaiswal, Daniel Moyer, Greg Ver Steeg, Wael AbdAlmageed, and Premkumar Natarajan. Invariant representations through adversarial forgetting. In The Thhitt-Fourdh AAAI Conference Artificial Intelligence, 2020.
Heinrich Jiang. Uniform convergence rates for kernel density estimation. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, 2017.
Philips George John, Deepak Vijaykeerthy, and Diptikalyan Saha. Verifying individual faimness in machine learning models. In Proceedings of the Thirty-Sixhh Conference Uncertainty in Artificial Intelligence, 2020.
Kaggle. Health heritage prize, 2012. URL
Toshihiro Kamishima, Shotaro Akaho, and Jun Sakuma. Faimess-aware learning through regulariza- tion approach. In Data Mining Workshops (ICDMW), 2011.
Thomas Kehrenberg, Myles Bartlett, Oliver Thomas, and Novi Quadrianto. Null-sampling for inter- pretable and fair representations. Computer Vision ECCV 2020 16th European Conference, 2020.
11

---

Published as a conference paper at ICLR 2022
Amir E Khandani, Adlar J Kim, and Andrew W Lo. Consumer credit-risk models via machine- learning algorithms. Journal of Banking & Finance, 2010.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International
Conference on Learning Representations, 2015.
Diederik Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible 1x1 convolutions. In Advances in Neural Information P Processing Systems 31, 2018.
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In 2nd International
Conference on Learning Representations, 2014.
Jiachun Liao, Chong Huang, Peter Kairouz, and Lalitha Sankar. Learning generative adversarial representations (GAP) under fairness and censoring constraints. CoRR, abs/19100004// 2019.
Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qingfu Zhang, and Sam Kwong. Pareto multi-task learning. In Advances in Neural Information Processing Systems 32, 2019.
Stuart P. Lloyd. Least squares quantization in PCM. IEEE Trans. Inf. Theory, 1982.
Francesco Locatello. Gabriele Abbati, Thomas Rainforth, Stefan Bauer, Bernhard Schölkopf. and Olivier Bachem. On the fairness of disentangled representations. In Advances in Neural Information Processing Systems 32, 2019.
Christos Louizos, Kevin Swersky, Yujia Li, Max Welling, and Richard S. Zemel. The variational fair autoencoder. In 4th International Conference Learning Representations, 2016.
James MacQueen. Some methods for classification and analysis of multivariate observations. In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, 1967.
David Madras, Elliot Creager, Toniann Pitassi, and Richard S. Zemel. Learning adversarially fair and transferable representations. In Proceedings of the 35th International Conference on Machine Learning, 2018
Natalia Martínez, Martín Bertrán, and Guillermo Sapiro. Minimax pareto fairness: A multi objective perspective. Proceedings of the 37th International Conference on Machine Learning. 2020.
Daniel McNamara, Cheng Soon Ong, and Robert C. Williamson. Costs and benefits of fair repre- sentation learning. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, 2019.
Aditya Krishna Menon and Robert C. Williamson. The cost of fairness in binary classification. In Conference on Fairness, Accountability and Transparency, 2018.
Daniel Moyer, Shuyang Gao, Rob Brekelmans, Aram Galstyan, and Greg Ver Steeg. Invariant representations without adversarial training. In Advances in Neural Information Processing Systems 31, 2018.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performanne deep learning library. In Advances in Neural Information Processing Systems 32, 2019.
Stanislav Pidhorskyi, Ranya Almohsen, and Gianfranco Doretto. Generative probabilistic novelty detection with adversarial autoencoders. In Advances in Neural Information Processing Systems 31, 2018.
Rafael Poyiadzi, Kacper Sokol, Raúl Santos- Rodríguz, Tijl De Bie, and Peter Flach. FACE: feasible and actionable counterfactual explanations. In AAAI/ACM Conference on AI, Ethics, and Society, 2020.
Danilo Jimenez Rezende and Shakir Mohamed. Variational inference with normalizing flows. In Proceedings of the 32nd International Conference Machine Learning, 2015.
12

---

Published as a conference paper at ICLR 2022
Proteek Chandan Roy and Vishnu Naresh Boddeti. Mitigating information leakage in image repre- sentations: maximum entropy approach. In JEEE Conference on Computer Vision and Pattern Recognition, 2019.
Anian Ruoss, Mislav Balunovic, Mare Fischer, and Martin T. Vechev. Learning certified individually fair representations. In Advances in Neural Information Processing Systems 33, 2020.
Shahar Segal, Yossi Adi, Benny Pinkas, Carsten Baum, Chaya Ganesh, and Joseph Keshet. Fairness in the eyes of the data: Certifying machine-learning models. CoRR, abs/2009.01 2020.
Congzheng Song and Vitaly Shmatikov. Overlearning reveals sensitive attributes. In 8th International Conference on Learning Representations, 2020.
Jiaming Song, Pratyusha Kalluri, Aditya Grover, Shengjia Zhao, and Stefano Ermon. Learning controllable fair representations. In The 22nd International Conference on Artificial Intelligence and Statistics, 2019.
Dustin Tran, Keyon Vafa, Kumar Krishna Agrawal, Laurent Dinh, and Ben Poole. Discrete flows: Invertible generative models of discrete data. In NeurlPS, pp. 14692-14701, 2019.
Caterina Urban, Maria Christakis, Valentin Wüstholz, and Fuyuan Zhang. Perfectly parallel fairness certification of neural networks. Proc. ACM Program. Lang., 2020.
Ben Usman, Avneesh Sud, Nick Dufour, and Kate Saenko. Log-likelihood ratio minimizing flows: Towards robust and quantifiable neural distribution alignment. In NeurIPS, 2020.
Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In Proceedings of the Conference Fairness, Accountability, and Transparency, 2019.
Aäron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew W. Senior, and Koray Kavukcuoglu. Wavenet: A generative model for raw audio. The 9th ISCA Speech Syuthesis Workshop, 2016a.
Aäron van den Oord, Nal Kalchbrenner, Lasse Espeholt, Koray Kavukcuoglu, Oriol Vinyals, and Alex Graves. Conditional image generation with pixelenn decoders. Advances in Neural Information Processing Systems 29, 2016b.
Aäron van den Oord, Nal Kalchbrenner, and Koray Kavukcuoglu. Pixel recurrent neural networks. In Proceedings of the 33nd International Conference on Machine Learning, 2016c.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 2008.
Suresh Venkatasubramannin and Mark Alfano. The philosophical basis of algorithmic recourse. In Conference on Fairness, Accountability, and Transparency, 2020.
Tianhao Wang, Zana Buçinca, and Zilin Ma. Learning interpretable fair representations. Technical report, Harvard University, 2021.
Susan Wei and Mare Niethammer. The faimess-accuracy pareto front. CoRR, 2020.
Meredith Whittaker, Kate Crawford, Roel Dobbe, Genevieve Fried, Elizabeth Kaziunas, Varoon Mathur, Sarah Mysers West, Rashida Richardson, Jason Schultz, and Oscar Schwartz. Al now report 2018. AT Now Institute New York University New York, 2018
F. Linda Wightman. LSAC national longitudinal bar passage study, 2017.
Eric Wong and J. Zico Kolter. Learning perturbation sets for robust machine learning. CoRR, abs/2007.08450, 2020.
Qizhe Xie, Zihang Dai, Yulun Du, Eduard H. Hovy, and Graham Neubig. Controllable invariance through adversarial feature learning. Advances in Neural Information Processing Systems 30, 2017.
13

---

Published as a conference paper at ICLR 2022
Yilun Xu, Shengjia Zhao, Jiaming Song, Russell Stewart, and Stefano Ermon. A theory of us- able information under computational constraints. 8th International Conference on Learning Representations, 2020.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez, and Krishna Gummadi, Fairness constraints: Mechanisms for fair classification. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017.
Richard S. Zemel, Yu Wu, Kevin Swersky, Toniann Pitassi, and Cynthia Dwork. Learning fair representations. In Proceedings of the 30th International Conference on Machine Learning, 2013.
Xin Zhang, Armando Solar-Lezama, and Rishabh Singh. Interpreting neural network judgments via minimal, stable, and symbolic corrections. In Advances in Neural Information Processing Systems 31, 2018.
Han Zhao and Geoffrey J. Gordon. Inherent tradeoffs in learning fair representations. In Advances in Neural Information Processing Systems 32, 2019.
14

---

Published as a conference paper at ICLR 2022
A APPENDIX
A.1
PROOFS
Here present the proofs of the theorems used in the paper.
Proof of Lemma 5.1 (Optimal adversary)
Proof. Here prove Lemma 5.1 which states the form of adversary μr: R {0, 1} that can achieve the highest discriminttion between 2g and 21. We start by rewriting the equation for statistical distance ((pz, pz,) as follows:
- PZ, (2) -p
(P2
oP = sup Ez~ [x()]] -Bs:) ( = sup 1
dz
(5)
To maximize the absolute value of the integral, we either have to maximize or minimize the integral S2 (P2, Pz, (z))u(z) dz. Clearly, to maximize the integral we should choose the function
(x)22,, (x)), for which μuz) = 1 if and only if p%, (=) 2 pz, (z), and otherwise. Similarly, to minimize the integral we should choose the function = (pz, (=) (*)} for which u=z)= = 1 if and only if (2,(2))) S pz, (z), and 0 otherwise. In fact, it can be easily observed that both options result in the same absolute value of the integral so we can, without loss of generality, choose
the option μ² (z) = 1 (pzo (z) (=))- This subsequently yields A(P2, P2,) = Eg (arn2,(p(( [x)(
Ex~z, IM* (z)] Moreover, we can also write A(pz, PZ,) [fz (z) pz. (z)) (2)
[s_ max(0, pz, (=) (zz dz| (this will be used to prove Theorem 5.5
Proof of Lemma 5.2 (Finite sample estimate)
Proof. We start by plugging in the optimal adversary μ* from Lemma 5.1 into the definition of the statistical distance. Let μ² be the optimal adversary defined in Lemma 5.1 namely μ=" (=(=)) if and only if pz, (z) < pz, (z). We first write the statistical distance in terms of the optimal adversary μ², then bound the statistical distance using triangle inequality and finally apply Hoeffding's ' inequality on the individual terms:
A (Zo. 21)=
sup E [m[2)] E [u(z)]
BawZo 11* (2)]
RENz (=)]
Benzo |1" (z)]
1
1 (zf) + M
(2f)
1 Σ
nr (xf) + Σ (x))) (M²())]
i=1
i=1
i=1
< 1B-ZO |1" (z)]
1 (=6) + A 21) + 21)+
n (z1) - Egnz [n (z)]
< Á(Zo, Z1) te
where Hoeffding's 's inequality guarantees that with probability at least (1 - 2 exxp(_nc2/p0 2 the first and last summand are at most c/2.
Proof of Lemma 5.3 (Bounding the statistical distance with symmetrized KI.)
Proof. We can bound the statistical distance A(pza P2.) by noticing that |x(2] < because μ is binary classifier and thus
A(pZ. P2,) sup / (p). pz, (z))) dz < / |pz, (z) pz, (2)) TV Pp.,,PZ,))
Pinsker's inequality guarantees that TV (V pz, )2 < LL P2,). Given that TV .2,) TV (pz,,PZ., we also have that TV (Pz. . pz, < KK(pzz,Pza) Thus, in order to bound the sta- tistical distance we can use 2A(p%) )2,) < which corresponds our objective with symmetrized KI. divergence used in Algorithm
(P ,2, KL pz, JL Pz, ):
15

---

Published as a conference paper at ICLR 2022
Proof of Lemma 5.4 (Encoding for discrete distributions)
Proof. Without loss of generality we can assume that fo(2x) = Assume that fi and
fi(x') y where pa pn(#)) () po(a') and p. (y) > pi piy''. Let di = ppo()) - pi (y) + po (
pi (i(")) and d2 - [po(#) pi (y')) + [vo(#") p (y)). In the case when (y) (o pi
pi
Po(a') is easy to show that d1 = d2. Now, in the case when Pu(a) < P1 (y') < po( < (1 we
p1 (3/)) < d1. Similarly, when (o Pi Pily) po(x'). we can see that d2 Σ d1 (pI (y) Pi (g")) < d1. In all cases, d2 S d1, which means that if we swap fi (2z) and fi (ar') the total variation either decreases stays the same. We can repeatedly swap such pairs, and once there are no more swaps to do, we arrive at the condition of the lemma where
can that d2 S d1 (po(z)
the arrays sorted the same way.
Proof of Theorem 5.5 (True and approximate distributions)
Proof. Let a E (0,1) 1) be sensitive attribute, and assume that (V Pa) < e/2. Recall that the
change of variables for probability densities gives us that for the representation
[a) we have,
similar as Eq. (4), pz. (=) = Po (2)) det (f.(w)) and Ộz. (z) = Pa (z) det (f.(z) Then, 8e
using those formulas together with the change of variables rule for multivariate integrals derive:
(P(2.. P2.) =
(z) P2. (z) (2.
da
afa(z) dx dr
(2. - Pz. (fa (x))) det
Pa (xx) det afa(z))
(f((z))
ffa(x) Óx
Pa()))
det
det
dx
Ox
Ox
m
[pa())) - Paa -a((a)) de
TV (P < c/2.
We will also use the observation from the proof of Lemma 5.1 which states that
A (p P2,) = max(0, O, pz, (z) Pz. (z)) dz
We can now observe that the following inequality holds: max (=) - pz, (=)) S pz, (=) (z)) max(0. -zz + 19 (z) pz, (z)1
Integrating both sides yields:
A pz, < (z), (z)) A APZ,, + (VV < A(22, P2,) +
Here, the last inequality follows from the previously proved inequality TV (pz,, < e/2, applied for both and
B EXPERIMENTAL SETUP
In this section, we provide the full specification of our experimental setup. We first discuss the datasets considered and the corresponding preprocessing methods employed. We empirically validate that our preprocessing maintains high accuracy on the respective prediction tasks. Finally, we specify the hyperparameters and computing resources for the experiments in Section
16

---

Published as a conference paper at ICLR 2022
Table 3: Statistics for train, validation, and test datasets. In general, the label (y) and sensitive attribute (a) distributions are highly skewed, which is why we report balanced accuracy.
SIZE
y
0
1 |
TRAIN
24 129
32.6%
28.5%
21.6%
24.9%
ADULT
VALIDATION
6033
31.9%
28.3%
19.9%
24.9%
TEST
15000
32.6%
27.9%
19.1%
24.6%
TRAIN
3377
60.6%
60.9%
46.8%
52.3%
COMPAS
VALIDATION
845
60.0%
60.1% %
46.9%
52.2%
TEST
1056
58.9%
61.8%
51.3%
55.6%
TRAIN
1276
42.3%
71.3%
17.8%
48.7%
CRIME
VALIDATION
319
40.8%
78.8%
21.5%
55.5%
TEST
399
43.1% 1%
74.9%
16.3%
49.6%
TRAIN
139 785
35.7%
79.0%
48.3%
68.0%
HEALTH
VALIDATION
31917
35.6%
79.3%
49.2%
68.6%
TEST
43 683
35.4%
78.8%
48.3%
68.0%
TRAIN
35 053
18.0%
28.5%
21.6%
27.3%
LAW
VALIDATION
13 764
17.5%
28.3%
19.9%
26.8%
TEST
17205
17.5%
27.9%
19.1%
26.3%
B. DATASETS
We consider five commonly studied datasets from the fairness literature: Adult and Crime from the UCI machine learning repository (Dua & Graff) (017), Compas (Brennan et al.) 2009). Law School (Wightman) 2017). and the Health Heritage Prize (Kaggle 2012) dataset. Below, we briefly introduce each of these datasets and discuss whether they contain personally identifiable information, if applicable. We preprocess Adult and Compas into categorical datasets by discretizing continuous features, keeping the other datasets as continuous. We drop rows and columns with missing values. For each dataset, we first split the data into training and test set, using the original splits wherever possible and a 80% 20% split of the original dataset otherwise. We then further sample 20% of the training set to used as validation set. Table 3 displays the dataset statistics for each of these splits. Finally, drop uninformative features to facilitate density estimation. We show that the removal of these features does not significantly affect the predictive utility the data Table 4
Adult
The Adult dataset, also known as Census Income dataset, was extracted from the 1994 Census database by Barry Becker and is provided by the UCI machine learning repository (Dua & Graff 2017). It contains 14 attributes: age, workclass, fnlwgt, education, education-num, marital-status, occupation, relationship, race, sex, capital-gain, capital-loss, hours-per-week. and native-country. The prediction task is to determine whether person makes over 50 000 US dollars per year. We consider sex the protected attribute, and we discretize the dataset by keeping only the categorical columns relationship, workclass, sarrita-stttuu race, occupation, education-nin numm, and education.
Compas
The Compas (Brennan et al., 2009) dataset was procured by ProPublica, and contains the criminal history, jail and prison time, demographics. and COMPAS risk scores for defendants from Broward County from 2012 and 2013. Through public records request, ProPublica obtained of COMPAS scores (18 610 people) from the Broward County Sheriff's s Office in Florida. This data was then augmented with public criminal records from the Broward County Clerk's Office website.
years worth
17

---

Published as a conference paper at ICLR 2022
Table 4: Classification accuracy before and after removing uninformative features during prepro- cessing. For each dataset we train multi-layer perceptron (MLP) with the same architecture on the original and preprocessed data and report the average aceuracy with standard deviation for five different random seeds. We can observe that the accuracy only decreases slightly after preprocessing.
ACCURACY (%)
ORIGINAL
PREPROCESSED
ADULT
85.0 (# 0.001)
84.4 (# (1.4+0000) 0.001)
COMPAS
65.3 (+ 0.003)
65.0 (+ 0.003)
CRIME
85.5 (# 0.003)
85.2 (# 0.0004)) 0.004)
HEALTH
80.1 (+ 0.002)
76.1 (+ 0.001)
LAW
88.2 (# 0.006)
86.4 (# 0.001)
Furthermore, jail records were obtained from the Browards County Sheriff's Office, and public incarceration records were downloaded from the Florida Department of Corrections website. The task consists of predicting recidivsm within two years for all individuals. We only consider Caucasian and African-American individuals and use race the protected attribute. We discretize the continuous features age, diff-custody, diff-jail, and priors-count, and we remove all other features except for sex, c-charge-degres and v-score-text.
Crime
The Communities and Crime dataset combines socio-economic data from the 1990 US Census, law enforcement data from the 1990 US LEMAS survey, and crime data from the 1995 FBI UCR. was created by Michael Redmond and is provided by the UCI machine learning repository (Dua & Graff) 2017). The dataset contains 128 attributes such as county, population, per capita income, and number of immigrants. The task consists of predicting whether the number of violent crimes per population for a given community above or below the median. We consider race as the protected attribute, which set to if the percentage of white people divided by is smaller than the percentage of black, asian, and hispanic individuals, and to otherwise. We keep the following 6 features: racePetWhite, PetWInvIne, PetFam2Par, PetKids2Par, PctYoungKids2Par, PorKidsBornNeverMaa
Health
The Health dataset was created for the Heritage Health Prize (Kaggic 2012) competition on Kaggle and contains medical records of over 55 000 patients. We consider the merged claims, drug count, lab count, and members sheets, which have total of 18 attributes. The identity of individual patients and health care providers, as well as other individual identifiable information, has been removed from the datasets to protect the privacy of those involved and comply with applicable law. We consider age as the protected attribute, which we binarize to patients above and below 60 years. The task is to predict the maximum Charlson Comordbidity Index, which predicts 10-year survival in patients with multiple comorbities. We drop all but the following features: DrugCount-tow total, DrugCount- months, no-Claims, no- no-Providers, PayDelay-tote PlaceSvc. For the transfer learning experiments we follow MMdras et al. (2018) and omit the primary condition group labels from the of features and try predict them from the latent representation without explicitly optimizing for the task.
PrimaryConditionCee
Specialty, ProcedureGroup. and
Law School
The Law School (Wightman) 2017) dataset contains admissions data from 25 law schools over the 2005, 2006, and in some cases 2007 admission cycles, providing information over 100 000 individual applications. The data was procured by Project SEAPHE and was cleaned to adhere to high standards of data privacy. Concretely, when the school, race, year, and gender information for enrolled students produced cells of fewer than five subjects, the cells were combined to minimize reidentification risk. The attributes are law school, year of fall term, LSAT score, undergraduate GPA,
18

---

Published as a conference paper at ICLR 2022
6393
6393
679
6393
lon Heee
606
lon Heep
Un
631
22
E-4
02
Equalbed
020 6m
025
0.30
(a) Demographic parity
(b) Equalized odds
(c) Equal opportunity
Figure 6: Tradeoff between accuracy and various fairness metrics (demographic parity, equalized odds, equal opportunity) when using Fair Normalizing Flows (FNF).
race, gender, and in-state residency. We consider race as the protected attribute, which we binarize to white and non-white. We remove all features but the LSAT score, undergraduate GPA, and the college to which the student applied (ordered by decreasing admission rate).
B.2 TRAINING DETAILS
Our code is implemented in PyTorch (Paszke et al. 2019)
Computing resources We run all experiments on a desktop PC using single GeForce RTX 2080 Ti GPU and 16-core Intel(R) Core(TM) 19-9900K CPU @ 3.60GHz.
Hyperparameters for main experiments For Crime estimate input density using Gaussian Mixture Model (GMM) with 4 components for = O and 2 components for a = 1. For Law we GMM with 8 components for both groups. The Health dataset requires more complex density estimation so we use RealNVP (Dinh et al. (0166) with 4 blocks of 20 neurons each. For categorical datasets, Adult and Compas, we perform density estimation using MADE (Germain al., 2015). which is represented using network of 2 hidden layers with 50 neurons.
We represent flow encoders using RealNVP with 4 blocks for Crime and Law, and 6 blocks for Health. Crime and Law use batch size 128, initial learning rate 0.01 and weight decay 0,0001, while Health uses batch size 256, initial learning rate 0.001 and weight decay Training performed using Adam (Kingma & Ba, 2015) optimizer. We use 60, 100, and 80 epochs for Crime, Law and Health, respectively. These parameters were chosen based on the performance on validation set.
For experiments in Fig. 4 we trained with the following 5 values for for respective datasets: 0, 0.02, 1, 0.2, 0.9 for Crime, Adult and Compas, O, 0.001, 0.02, 0.1, 0.9 for Law, 0.05, 0.1, 0.5, 0.95 for Health. Training for epoch takes around second for Crime, 5 seconds for Law, and 30 seconds for Health.
C ADDITIONAL EXPERIMENTS
In this section we present additional experimental results.
Compatibility with other fairness metrics In Section we focused on presenting results on statistical distance, as it can bound various fairness metrics Madras al. 2018). constrast, here we provide more detailed experiments with three common group fairness metrics: demographic parity, equalized odds, and equality of opportunity. We demonstrate the tradeoff between these metrics and downstream accuracy in Fig. We observe that FNF achieves high rates of demographic parity, equalized odds, and equality of opportunity with only small decreases in classification accuracy (similar the results for the statistical distance showed in Fig. 4
Compatibility with different scalarization schemes Since faimess and accuracy are of- ten competing objectives, they merit a treatment from multi-objective optimization. Here, investigate the scalarization scheme proposed by Wei & Niethammer (2020) and
19

---

Published as a conference paper at ICLR 2022
replace our objective r(oo + L1) + (1 Day obtained via convex scalarization, with the Chebyshev scalarization scheme (ax + L1) r)yr,, where we
use the same normalization for Lo. Li, and Las as Wei & Niethammer (020))
We evaluate the schemes for a large range of values on the Crime dataset and compute the Area Under the Curve (AUC) with the trapezoidal rule. The convex scalariza- tion yields an AUC of 0. 0.6036, whereas the Chebyshev scalarization attains an AUC of 0.6051. Moreover, we aggregate the results in Fig. 7 In general, we observe that the convex scalarization slightly outperforms the Cheby- shev scalarization scheme. We believe that this is due to two reasons, (i) the Pareto curve is almost convex, which is why the convex scalarization performs well, and (ii) the stochasticity of gradient-bast based optimization. We consider more advanced -ulti--bjecttive optimization methods Lin et al. 2019); Martínez et al. (2020) an interesting direc- tion for future work.
0221
Chetyshee
0754
0.75
3623
02
03
34
0.5
0.6
0.7
95
60
1.8
Figure 7: Different scalarization schemes.
Compatibility with different priors In the following experiment, we demonstrate that FNF is compatible with any differentiable estimate of po and pl. We consider Crime with the same setup as before, but with 3 different priors: a GMM with k = 3 components, an autoregres- sive prior, and a RealNVP flow (Dinh et al., 2016). For each of these priors, we train an encoder using FNF and a classifier on top of the learned representations. Fig. g shows the tradeoff between the statistical distance and accuracy for each of the priors. Based on these results, we can conclude that FNF achieves similar results for each of the priors, empirically demonstrating the flexibility of our approach.
0.775
0.750
0.725
0.700
0.2
0.4
0.5
0.6
5.9
1.0
Statistical distance
Figure 8: Different priors used with FNF.
Interpreting the representations We now show that the bijectivity of FNF enables interpretability analyses, an active area of research in fair representation learning (He et al. 2019 Kehrenberg et al.) 2020 [Wang et al.) 2021). To that end, consider the Crime dataset where for community x: (i) race (non-white vs. white majority) is the sensitive attribute a, (ii) the percentage of whites (highly correlated with, but not entirely predictive of the sensitive attribute) is in the feature set, and (iii) the label strongly correlates with the sensitive attribute. We encode every community x Pa as = fa (x) and compute the corresponding community with opposite sensitive attribute that is also mapped to z, i.e., æ = S (z) (usually not in the dataset), yielding a matching between both distributions. We visualize the t-SNE (van der Maaten Hinton, 2008) embeddings of this mapping for E {0, 1} in Fig. 99. where the dots are communities z and the crosses are the corresponding ă. We run k-means (MaQQueen) 1967 Lloyd 1982) on all points with a = and show the matched clusters for points with a = 0 (c.g., red clusters are matched). For the classification loss Larr, we observe a dichotomy between x and æ, since the encoder learns to match real points x with high likelihood to points 전ेt with low likelihood, yielding both high task utility (due to (iii), but also high statistical distance (due to (ii).. For example, the red cluster has an average log-likelihood of -4.3 for x and 1330 for ã. In contrast, for 7 1 FNF minimizes only the KL-divergence losses Lo + L1. and thus learns to match points of roughly equal likelihood to the same latent point z such that the optimal adversary can no longer recover the sensitive attribute. Accordingly, the red cluster has an average log-likelihood of 2288 for æ and -3.0 for æ.
0, where FNF only minimizes
Tradeoff' between accuracy and fairness Zhao & Gordon 2019) proved that any classifier with perfect statistical distance necessarily has to sacrifice classification accuracy, where the exact tradcoff depends on the difference in base rates between the different sensitive groups We confirm this statement, with an investigation of the tradeoff between accuracy and fairness for the Crime dataset, where we need to sacrifice a significant amount of accuracy in order to decrease the statistical distance (as can be observed in Fig.
20

---

Published as a conference paper at ICLR 2022
Non-Wihite (a 11
White
Non-White
(o 0)
real matched
real matched
real matched
real
matched
FNF
(a) y 0
(b)
Figure 9: Visualizing k-means clusters on t-SNE embeddings of mappings between real points from the Crime dataset and their corresponding matches from the opposite attribute distribution.
For each pair of sensitive attribute a (racial group) and label y (whether the number of violent crimes is above the median) we report the probability P(Y = y A = a) in Table 5 (the probabilities for the other datasets Clearly, Thole that the sensitive attribute a and the task label y of the Crime dataset are highly correlated: one racial group was much more likely to be reported for violent crimes than the other. This is, of course, consequence of bias in the data (e.g., some neighborhoods tend to be policed more often so more crimes will be reported), as has been documented in various studies, e-g., see Brennan et al. (2009) for a study of the Compas dataset. Thus, in accordance with the result from Zhao & Gordon| (019). we need to sacrifice a lot of accuracy to achieve a small statistical distance on the Crime dataset.
Table 5: Statistics for the Crime
train set (reproduced from Table
be found in Table 3)
y = 0
0.29
0.71
0.82
0.18
21


Reviews:
[{"review_id": "fxCsFLzDPho", "reviewer": "Reviewer_yCUe", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "\nGeneral Suggestion:\n\nIt feels like the type of estimation results you are trying to obtain are very similar to prior works in non-vacuous generalisation bounds for DL. I think the authors work would benefit a lot from reading prior works done for DL/Generalisation such as [1,2] and use these to obtain a correct and computable alternative to that of theorem 5.1. Which as it stands is incorrect. I would be happy to modify my score subject to obtaining a valid result here and recomputing the estimate of the statistical distance across all experiments. \n\nQuestions to the Authors:\n1. Where do you use $p(z)$ explicitly in your proofs/ algorithms ? There seems to be a big selling point on this; however besides theorem 5.3 I don't see a need for explicitly needing $p(z)$ , most of the other two claims 5.1 and 5.2 just require its existence but not its closed form.\n2. As I mentioned the theory seems to be mostly estimation guarantees, you don't seem to be making a theoretical claim on bounding the fairness metrics themselves. Please clarify this.\n\nDetailed Comments/Corrections: \n\n1. Aesthetic: Maybe it's common in this community but using mathcal on a capital letter typically denotes a set\\space (for example a set of functions) it's distracting\\unhelpful to see it being used for a distribution.\n2. Missing a $dz$ in Eq 4, \\mu is a function not a measure. I would also suggest using f or g rather than \\mu as in [3], since mu is incredibly commonly used for mesures, again this makes Eq 4 distracting/confusing at a glance.\n3. Page 5: “However, for such models, given densities $p_0(x)$ and $p_1(x)$ over the input space, it is intractable to compute the densities $p_{Z0} (z)$ and $p_{Z1} (z)$ in the latent space as many inputs $x$ can be mapped to the same latent $z$”  . It could help the reader if you could be more explicit here, it seems the claim is that you can't carry out a change of variables to compute $p(z)$ because the inverse function theorem does not hold for most NN encoders and the Jacobian is not defined. \n4. The Pinsker inequality bounds total variation not MMD. Please revisit MMD literature and use the appropriate bound / connections to KL/OT etc. If you can correct this (or correct me) I am happy to take this point back. Atm it really questions the KL motivation in Algorithm 1, you yet haven't shown that you are minimising a surrogate of the statistical distance. Additionally please translate this into a remark or a lemma so it stands out, as you can see from some of the reviews its easy to miss.\n5. Why train a symmetrised KL while Pinsker's inequality is regarding KL ? there's no explanation for this when it is introduced. This needs justification why a symmetrised KL?.\n6. Second instance of $\\mu=1$ is a typo on the discussion of optimal adversary at the end of page 1 should be mu=0.\n7. Lemma 5.1 : If we assumed the claim was right it would be a very vanilla concentration / CLT like type argument simply arguing that your empirical estimator of the statistical distance has nice convergence properties. This does not rely on flows and it doesn't give any theoretical arguments on how the authors approach results in a small adversarial accuracy. It does allow for empirical arguments of the adversarial accuracy to be made in probability but the authors would have to provide a delta column in all their experiments + estimated confidence bounds on their delta error too, which they haven't, this would give theoretically backed empirical estimators of the adversarial accuracy which would be a good contribution on its own , however this is currently lacking..\n8. Lemma 5.1 should be written in a form similar to this for all  $\\delta>0, P\\left(\\mathrm{err } < \\frac{1}{\\sqrt{n}} * \\sqrt{\\ln(2/\\delta)} \\right) \\geq 1 - \\delta$ so that it is clear to the reader what type of convergence rate you are showing. See theorem 1.1 in [2] for example.\n9. Proof of Lemma 5.1 is abusing notation interchanging densities and measures (distributions). Again I would like to highlight that I am not sure what purpose the calligraphic Z notation has.\n10. The proof for 5.1 has a misstep. Detail on the misstep : After applying the triangle inequality you distribute the sup over the 3 terms. You then use the definition of MMD and substitute the sup/expression in the middle term. However you also remove the sups from the 2 other terms leaving $\\mu$ completely undefined. This does not even compile / type check as a proof. To apply a Hoeffding type bound on a sup you need to have the size of the hypothesis space and apply it via a union bound, as your inputs are real and your hypothesis space infinite this does not work so you go into VC-dimension type of bounds which are vacuous for neural nets. In the end what you need here is a PAC Bayes (e.g. [1,2] ) style of bound which has significant interpretation. In short you cannot apply Hoeffding's inequality over a sup like this. You could rectify this but it will be a different theorem. I think this could be done within a week so I would be happy to rectify my score if this + points 4 and 7 are rectified.\n11. Looking at the proofs for Lemmas 5.1 and 5.3 I am really unconvinced that the flows are a necessary part of the proof ? All you require for these is to assume that the p(z) densities exist but at no point are flow properties used. In short the two provable guarantees you have provided apply to normal NN encoders too, the difference being that using flows will allow computing these statistical distances ?\n12. The notation  $(..)dx = (..)dz$ is a bad heuristic and prone to errors please rectify this by carrying out the change of variables on $\\int |p(x) - \\hat{p}(x) | dx$ explicitly  pushing the jacobian determinant into the abs and applying the definition of p(z). Whilst the step/result is correct its very prone to mistake using heuristics with infinitesimals (imagine if we were looking at TV between $p_{N_1}(z)$ and $p_{N_0}(z)$ we wouldn't be able to apply the same heuristic here). Please correct this.    \n13. Lemma 5.2 seems to be used to motivate the weighting with gamma in Algorithm 1. That is: minimising the statistical distance (which is minimised surrogately so by minimising sym-KL) can lead to this “shuffling” which in turn will decrease classification accuracy and thus we have this gamma-tradeoff heuristic. I feel this lacks clarity. It's important to emphasize that this has nothing to do with the “provable guarantees” . I would argue it's more of a remark/observation that informs/motivates a sound heuristic. Please clarify.\n\n\n\n[1] Dziugaite, G.K. and Roy, D.M., 2017. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703.11008.\n\n[2] Dziugaite, G.K. and Roy, D.M., 2018. Data-dependent PAC-Bayes priors via differential privacy. arXiv preprint arXiv:1802.09583.\n\n[3] Gretton, A., Borgwardt, K., Rasch, M., Schölkopf, B. and Smola, A., 2006. A kernel method for the two-sample-problem. Advances in neural information processing systems, 19, pp.513-520.\n\n", "summary_of_the_paper": "This work proposes using normalising flows to obtain a latent representation of the data that is trained to minimise a surrogate of an MMD [3] based statistical distance used to measure adversarial accuracy when classifying protected features. All this whilst preserving the desired properties of the original features. The authors motivate using normalising flows arguing it allows to compute an empirical estimate of the aforementioned statistical distance which they claim has strong convergence guarantees. ", "summary_of_the_review": "Pros:\n1. The goal of this work is very well motivated and much needed.\n2. The authors provide a very nice illustrative example clarifying and motivating the need for these methods.\n3. In general the authors do aim to motivate every algorithmic choice with some backing from theory which is a very nice structure/writing style.\n4. Overall I do think the general direction the authors aimed to go in is very exciting and has a lot of promise. However in this current iteration it is lacking technical strength (both experimentally and theoretically).\n\nCons:\n\n1.Unfortunately much of the theory the authors use to motivate design choices seem to have mistakes (Proof of Theorem 5.1 is incorrect, the usage of Pinsker’s inequality also seems wrong)\n\n2. Because of the aforementioned error with Pinsker’s inequality  (it bounds TV not MMD) it's not clear if the KL based objective (as a surrogate to the statistical distance) is well motivated.\n\n3. Not very safe heuristics are used in proofs (e.g. equating infinitesimals) ; this is prone to mistakes.\n\n4. The use of normalising flows seems to be only used in theorem 5.3 ? \n\n5. Finally the claimed theoretical results are “estimation guarantees” the way the introduction and abstract are worded seem to indicate that the theoretical results guarantee fairness for a given family of models, that is the way this work is selling itself seems to claim a bound on the true statistical distance. However that is far from the case, instead this work tries to prove that said distance can be estimated “very well” empirically. Thus all experiments in this work should be estimating this quantity as any success statements regarding fairness rely on such empirical estimates and there are really no theoretical guarantees on the fairness aspect of the method itself, it's more like there are theoretical guarantees on the evaluation of the method.\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_C0dId2yu3m", "reviewer": "Reviewer_My3D", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 general, I think the paper is well presented and the organization is good. My major concern is the motivation of this paper, I would like to see why normalization flow is the necessary technique to be the solution to the drawbacks mentioned in existing fair representation learning methods. In addition, the theory seems to be quite straightforward based on PAC learning. If more tailored theoretical analysis can be provided, I think the paper can be more interesting. While I have the above concerns, the technique part in this paper is sound, and I cannot find large mistakes, thus I vote for a weak acceptance.", "summary_of_the_paper": "This paper aims to design a fair representation learning method. To achieve this goal, the authors have proposed a normalization flow-based method, where an adversarial-based strategy is leveraged to train the model. In the experiments, the authors conducted extensive experiments to demonstrate the effectiveness of the proposed methods. ", "summary_of_the_review": "Interesting paper, which however can be further improved.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Qx51kl2W21q", "reviewer": "Reviewer_BBgE", "summary": "", "questions": "", "limitations": "", "rating": 6, "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\n* Fair representation learning with theoretical guarantees for fairness is a significant contribution.\n* The algorithm for training the encoders and minimizing the KL divergence is straightforward and practical.\n* Even if the probability distribution of the input data is not known, density estimation can be used.\n* The invertible encoders can be used for interpretation and transfer learning purposes.\n* Experiments are extensive and show how FNF outperforms adversarial training baselines and suggests upper-bound performances of any adversary.\n\nWeaknesses\n\n* Most of the analyses focus on the fairness guarantee, but there is not much explanation on why the accuracy does not degrade much. The experiments are extensive enough (including the ones in the supplementary), but it is still not clear why FNF should have less accuracy tradeoffs than adversarial training baselines in general. I suggest the authors also show the Figure 4 results for adversarial training.\n* In Section 2, Gupta et al. (2021) is mentioned as a relevant work, but is considered inferior due to its monotonic nature of bounds. However, it would be interesting to also see any experiments whether FNF actually outperforms this approach.\n* In Page 6, how tight is the bound of the square root of KL divergence for statistical distance? FNF's performance seems to largely rely on this tightness. \n* In Algorithm 1, there should be some discussion on when to stop the learning. That is, how can one set $N$?\n* Minor comments\n   * In Page 7, Figure 4 seems to appear too early. The description is in the next Page 8, which is confusing. In Page 8, Table 1 also appears a bit too early.\n   * The experimental setting for Table 1 is not clear. Which datasets were used and were the results averaged?\n\n", "summary_of_the_paper": "This paper proposes a representation learning technique for fairness called Fair Normalization Flows (FNF) with theoretical guarantees on the maximum-possible unfairness. The key idea is to train encoders that map input samples of two sensitive groups into a space where the two groups become indistinguishable in terms of statistic distance (=maximum mean discrepancy) without significantly sacrificing accuracy. FNF minimizes the KL divergence between the converted distributions of the groups, which is an upper bound of statistic distance. In comparison to previous approaches that use adversarial training, FNF does not have instability issues when solving a non-convex problem. In addition, FNF has interpretability and transfer learning functionalities, which other fair representation learning techniques lack. Experiments show that FNF ensures fairness while retaining high accuracy for various real datasets and outperforms other adversarial training baselines.", "summary_of_the_review": "The paper makes significant contributions by proposing a fair representation learning technique with theoretical bounds. The paper can also be improved by better explaining the accuracy results and adding some more details of its techniques and experiments.", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "A6-8ZYVtX2g", "reviewer": "Reviewer_Vaqy", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 of the paper\n+ The paper considers the relevant task of learning fair representations\n+ The issues with learning fair representation via adversarial training are explained well\n\nWeaknesses of the paper\n+ Algorithm 1 is incomplete. No details are given about $\\mathcal L_{clf}$. Shouldn't we be updating the parameters of the classifier $h$ in Algorithm 1? \n+ There is no connection between Algorithm 1 and the various theoretical results given in the paper. You must show that minimizing $\\mathcal L$ in Algorithm 1 ensures that $\\Delta(p_{Z_0}, p_{Z_1})$ is small so that in turn the maximum adversarial accuracy is small. This is not obvious since $\\mathcal L$ in Algorithm 1 also contains $\\mathcal L_{clf}$.\n+ The scalarization scheme employed in Algorithm 1's loss function $\\mathcal L = \\gamma (L_0 + L_1) + (1-\\gamma) L_{clf}$ is well known to be the most naive, and ineffective scalarization technique in multi-objective optimization. A proper application of multi-objective optimization techniques will produce far more interesting trade-off curves than what's seen in Figure 4. Good references are \"The Fairness-Accuracy Pareto Front\" by Wei and Niethammer and \"Pareto Multi-Task Learning\" by Xin et al.\n+I won't be the only one pointing this out, but here goes: a big weakness of the paper is the assumption that $p_0$ and $p_1$ are known. I do note that you reference several fairness papers at the end of Section 5 that have apparently \"successfully\" employed density estimation. But this isn't even my biggest concern. Again, I am afraid that too many uncontrolled approximations are made along the way. It is worth highlighting that $\\mathcal L$ in Algorithm 1 does not even contain $\\Delta(p_{Z_0}, p_{Z_1})$, but rather the symmetrized KL-Divergence between $Z_0$ and $Z_1$ which is simply not the same as the statistical distance between $Z_0$ and $Z_1$. \n\nMinor questions\n+ Why use the term statistical distance and not MMD?\n+ According to the Background (Section 3), $y$ is binary. Consider replacing throughout the expression $E(y=h(x))$ with simply $P(y=h(x))$. \n+ In the left panel of Figure 2, consider adding different symbols to illustrate the two classes $y=0$ and $y=1$. Also consider coloring the $(x_1,x_2)$ region according to the classifier $h(z)$ where $z$ is as given in Section 4. \n+ In figures such as Fig 4a and 4b, consider adding the value of $\\gamma$ above each point.", "summary_of_the_paper": "Given input data $x$, target $y$, and a binary sensitive attribute $a$, this work undertakes the task of learning a representation of $x$, call it $z$, such that a classifier $h$ can perform well using $z$ while at the same time no adversary $g$ can predict $a$ well from $z$. \n\nThis is accomplished by minimizing, see Algorithm 1,  \n$$\n\\gamma \\frac{1}{2} D_{KL}(p_{Z_0} || p_{Z_1}) + (1-\\gamma) \\mathcal L_{clf}.\n$$\nThis operation is possible because 1) $p_0$ and $p_1$, the distributions of $x$ for $a=0$ and $a=1$, respectively, are presumed to be given or readily estimable, and 2) the latent $z$ is obtained by normalizing flows $f_0$ and $f_1$ applied to $p_0$ and $p_1$, respectively. \n\nSupposedly this optimization problem results in latent representations $z$ that ensures the statistical distance/MMD $\\Delta(p_{Z_0}, p_{Z_1})$ is small so that in turn the maximum adversarial accuracy is small.", "summary_of_the_review": "Much fuss is made about controlling the statistical distance between the latent representations $z_0$ and $z_1$. This is justified because controlling the statistical distance amounts to controlling the maximum adversarial accuracy and additionally gives guarantees on demographic parity and equalised odds for any downstream classifier $h$ that uses $z$. \n\nHowever what is actually implemented in Algorithm 1 has no clear connection to controlling the statistical distance between $z_0$ and $z_1$. This feels like a sleight of hand to me. Certainly none of the theory supports Algorithm 1's ability to control the statistical distance. Furthermore no careful thinking is given to the tradeoff value of $\\gamma$ in Algorithm 1. ", "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": "8W-MzvRSbFX", "reviewer": "Reviewer_xsbe", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "[Strengths]\n- Normalizing flows are a flexible tool to disentangle the predictive information and sensitive attributes from the data.\n- The idea of using normalizing flows for fair representation learning is interesting. The formulation of the learning problem is natural and practical.\n- The presentation of the paper is clear.\n\n[Weaknesses]\n- The proposed method applies to only a binary protected attribute. To generalize to a discrete protected attribute, we would need to learn a separate flow for each value. However, equalizing all these distributions is not straightforward as the symmetric KL can no longer be used.\n- I think the proposed method can sacrifice accuracy for fairness. Suppose that the label is a function of the input distribution, normalizing the input distribution could also remove the predictive information. The authors use a parameter \\gamma in the loss function to balance fairness and classifier utility; however, this is not sufficient to attain a good tradeoff in terms of Pareto optimality.\n- In the empirical evaluation, the authors used different density functions, i.e., RealNVP, MADE, and GMMs, for different datasets. This led me wonder if some of the densities do not perform well on certain datasets. For a fair comparison, it could be helpful to provide results for all the densities.\n", "summary_of_the_paper": "In this paper, the authors propose fair representation learning using normalizing flows. The basic idea is to learn a separate normalizing flow for each protected group. These flow distributions are equalized and hence cannot be used to determine the protected group. The authors argue that improved fairness guarantees can be achieved compared to adversarially fair learning.", "summary_of_the_review": "The idea of the paper is clear and interesting. It appears that the proposed approach only supports a binary protected attribute. The empirical evaluation could be strengthened by providing results for all the density functions.\n", "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": "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:

Meta-review: This paper addresses fair representation learning, with the aim of obstructing the recovery of sensitive features from the learned representation, hence enforcing the fairness of subsequent prediction tasks.  In the setting where probability density can be estimated for sensitive groups, Fair Normalizing Flows (FNF) tries to minimize the statistical distance between group-wise latent representations, thereby providing theoretical fairness guarantees.  Experimental confirm the effectiveness of FNF in fairness, transferrability, and interpretability.

The paper received extensive and in-depth discussion.  The rebuttal did an excellent job in clarification.  Although there are still some concerns on the theoretical properties of the optimal solution, overall the reviewers and myself find this paper interesting and worth publishing.
Decision: Accept (Poster)