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.

§ INTRODUCTION

As machine learning is increasingly being used in scenarios that can negatively affect humans [Brennan et al., 2009, Khandani et 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 (race) cannot be recovered from the representations.
Perhaps the most prominent approach for learning fair representations is adversarial training [Edwards & Storkey, 2016, Madras et al., 2018, Xie et al., 2017, Song et al., 2019, Roy & Boddeti, 2019], which jointly trains an encoder trying to transform data into a fair representation with an adversary attempting to recover sensitive attributes from the representation.
However, several recent lines of work [Feng et al., 2019, Moyer et al., 2018, Elazar & Goldberg, 2018, Xu et al., 2020, Gupta et al., 2021, Song & 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, 2021] on the fair usage of AI, stating that any entity that cannot guarantee non-discrimination would be held accountable for the produced data.
This raises the question: Can we learn representations which provably guarantee that sensitive attributes cannot be recovered?

This work

Following prior work, we focus on tabular datasets used for tasks such as loan or insurance assessment where fairness is of high relevance.
We assume that the original input data $\vx$ comes from two probability distributions $p_0$ and $p_1$, representing groups with sensitive attributes $a=0$ and $a=1$, respectively.
In the cases where distributions $p_0$ and $p_1$ are known, we will obtain provable fairness guarantees, and otherwise we perform density estimation and obtain guarantees with respect to the estimated distribution.
In our experimental evaluation we confirm that the bounds computed on the estimated distribution in practice also bound adversarial accuracy on the true distribution, meaning that density estimation works well for the setting we consider.

To address the above challenges, we propose Fair Normalizing Flows (FNF), a new method for learning fair representations with guarantees.
In contrast to other approaches where encoders are standard feed-forward neural networks, we instead model the encoder as a normalizing flow [Rezende & Mohamed, 2015].
<ref> provides a high-level overview of FNF.
As shown on the left in <ref>, using raw inputs $\vx$ allows us to train high-utility classifiers $h$, but at the same time does not protect against the existence of a malicious adversary $g$ that can predict a sensitive attribute $a$ from the features in $\vx$.
Our architecture consists of two flow-based encoders $f_0$ and $f_1$, where flow $f_a$ transforms probability distribution $p_a(\vx)$ into $p_{Z_a}(\vz)$ by mapping $\vx$ into $\vz = f_a(\vx)$.
The goal of the training procedure is to minimize the distance $\Delta$ between the resulting distributions $p_{Z_0}(\vz)$ and $p_{Z_1}(\vz)$ so that an adversary cannot distinguish between them.
Intuitively, after training our encoder, each latent representation $\vz$ can be inverted into original inputs $x_0 = f^{-1}_0(\vz)$ and $x_1 = f^{-1}_1(\vz)$ that should ideally have similar probability $p_0$ and $p_1$, meaning that even the optimal adversary cannot distinguish which of them actually produced latent $\vz$.
Crucially, as normalizing flows enable us to compute the exact likelihood in the latent space, for trained encoders we can upper bound the accuracy of any adversary with $\frac{1 + \Delta}{2}$, which should be small if training was successful.
Furthermore, the distance $\Delta$ provides a tight upper bound [Madras et al., 2018] on common fairness notions such as demographic parity [Dwork et al., 2012] and equalized odds [Hardt et al., 2016].
As shown on the right in <ref>, we can still train high-utility classifiers $h$ using our representations, but now we can 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 us to examine how to reverse a negative decision outcome.

Main contributions

Our key contributions are:

* 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 to transfer learning.

Overview of Fair Normalizing Flows (FNF).
There are two encoders, $f_0$ and $f_1$, that transform the two input distributions $p_0$ and $p_1$ into latent distributions $p_{Z_0}$ and $p_{Z_1}$ with a small statistical distance $\Delta \approx 0$.
Without FNF, a strong adversary $g$ can easily recover sensitive attribute $a$ from the original input $\vx$, but once inputs are passed through FNF, we are guaranteed that $\emph{any}$ adversary that tries to guess sensitive attributes from latent $\vz$ cannot be significantly better than random chance.
At the same time, we can ensure that any benevolent user $h$ maintains high utility.

§ 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., 2016], and equality of opportunity [Hardt et al., 2016], which are widely studied in the literature [Edwards & Storkey, 2016, Madras et al., 2018, Zemel et 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 et al., 2013, McNamara et al., 2019], in-processing methods modify training by incorporating fairness constraints [Kamishima et al., 2011, Zafar et al., 2017], and post-processing methods change the predictions of a 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 approaches, including variational autoencoders [Moyer et al., 2018, Louizos et al., 2016], adversarial training [Edwards & Storkey, 2016, Madras et al., 2018, Xie et al., 2017, Song et al., 2019, Roy & Boddeti, 2019, Liao et al., 2019, Jaiswal et al., 2020, Feng et al., 2019], and disentanglement [Creager 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 unfairness, 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 et al., 2020, Gupta et al., 2021, 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 is precisely the goal of our work.
Prior work makes first steps in this direction: Gupta et al., 2021 upper bound a 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 an 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 et 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 [Whittaker et al., 2018, EU, 2021, FTC, 2021] has spurred interest in provably fair algorithms.
Unlike this work, the majority of these efforts [McNamara et al., 2019, John et al., 2020, Urban et al., 2020, Ruoss et al., 2020] focus on individual fairness.
Individual fairness is also tightly linked to differential privacy [Dwork et al., 2012, Dwork et al., 2006], which guarantees that an attacker cannot infer whether a given individual was present in the dataset or 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 $(\vx, a) \in \R^d \times \mathcal{A}$ comes from a probability distribution $p$, where $\vx$ represents the features and $a$ represents a sensitive attribute.
In this work, we focus on the case where the sensitive attribute is binary, meaning $\mathcal{A} = \{0, 1\}$.
Given $p$, we can define the conditional probabilities as $p_0(\vx) = P(\vx \mid a=0)$ and $p_1(\vx) = P(\vx \mid a=1)$.
We are interested in classifying each sample $(\vx, a)$ to a label $y \in \{0, 1\}$, which may or may not be correlated with the sensitive attribute $a$.
Our goal is to build a classifier $\hat{y} = h(\vx)$ that tries to predict $y$ from the features $\vx$, while satisfying certain notions of fairness.
Next, we present several definitions of fairness relevant for this work.

Fairness criteria

A classifier $h$ satisfies demographic parity if it assigns positive outcomes to both sensitive groups equally likely, $P(h(\vx) = 1 \mid a = 0) = P(h(\vx) = 1 \mid a = 1)$.
If demographic parity cannot be satisfied, we consider demographic parity distance, defined as $ \lvert \E \left[ h(\vx) \mid a = 0 \right] - \E \left[ h(\vx) \mid a = 1 \right] \rvert$.
An issue with demographic parity occurs if the base rates differ among the attributes, $P(y = 1 \mid a = 0) \neq P(y = 1 \mid a = 1)$.
In that case, even the ground truth label $y$ does not satisfy demographic parity.
Thus, Hardt et al., 2016 introduced equalized odds, which requires that $P(h(\vx) = 1 \mid y=y_0, a=0) = P(h(\vx) = 1 \mid y=y_0, a=1)$ for $y_0 \in \{0, 1\}$.

Fair representations

Instead of directly predicting $y$ from $\vx$, Zemel et al., 2013 introduced the idea of learning fair representations of data.
The idea is that a data producer preprocesses the original data $\vx$ to obtain a new representation $\vz = f(\vx, a)$.
Then, any data consumer, who is using this data to solve a downstream task, can use $\vz$ as an input to the classifier instead of the original data $\vx$.
Thus, if the data producer can ensure that data representation is fair (some fairness notion), then all classifiers employing this representation will automatically inherit the fairness property.
However, due to inherent biases of the dataset, this fairness increase generally results in a small accuracy decrease (see <ref> 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, Dinh et al., 2016, Kingma & Dhariwal, 2018] provide an attractive framework for transforming any probability distribution $q$ into another distribution $\bar{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, 2015].
In this work, however, we mainly leverage the fact that flow models sample a latent variable $\vz$ from a density $\bar{q}(\vz)$ and apply an invertible function $f_\vtheta$, parametrized by $\vtheta$, to obtain datapoint $\vx = f^{-1}_\vtheta(\vz)$.
Given a density $q(\vx)$, the exact log-likelihood is then obtained by applying the change of variables formula $\log q(\vx) = \log \bar{q}(\vz) + \log \lvert \det (d\vz/d\vx) \rvert$.
Thus, for $f_\vtheta = f_1 \circ f_2 \circ \ldots \circ f_K$ with $\vr_0 = \vx$, $f_i(\vr_{i-1}) = \vr_i$, and $\vr_K = \vz$, we have

\begin{equation}
\log q(\vx) = \log \bar{q}(\vz) + \sum_{i = 1}^K \log \lvert \det (d\vr_i/d\vr_{i-1}) \rvert.
\end{equation}

A clever choice of transformations $f_i$ [Rezende & Mohamed, 2015, Dinh et al., 2015, Dinh et al., 2016] makes the computation of the log-determinant tractable, resulting in efficient training and sampling.
Alternative generative models cannot compute the exact log-likelihood (VAEs [Kingma & Welling, 2014], GANs [Goodfellow et al., 2014]) or have inefficient sampling (autoregressive models).
Our approach is also related to discrete flows [Tran et al., 2019, Hoogeboom et al., 2019] and alignment flows [Grover et al., 2020, Usman et al., 2020].
However, alignment flows jointly learn the density and the transformation, unlike the fairness setting where these are computed by different entities.

§ MOTIVATION

In this section, we motivate our approach by highlighting some key issues with fair representation learning based on adversarial training.
Consider a distribution of samples $\vx = (x_1, x_2) \in \sR^2$ divided into two groups, shown as blue and orange in <ref>.
The first group with a sensitive attribute $a = 0$ has a distribution $(x_1, x_2) \sim p_0$, where $p_0$ is a mixture of two Gaussians $\mathcal{N}([-3, 3], I)$ and $\mathcal{N}([3, 3], I)$.
The second group with a sensitive attribute $a = 1$ has a distribution $(x_1, x_2) \sim p_1$, where $p_1$ is a mixture of two Gaussians $\mathcal{N}([-3, -3], I)$ and $\mathcal{N}([3, -3], I)$.
The label of a point $(x_1, x_2)$ is defined by $y = 1$ if $\sign(x_1) = \sign(x_2)$ and $y = 0$ otherwise.
Our goal is to learn a data representation $\vz = f(\vx, a)$ such that it is impossible to recover $a$ from $\vz$, but still possible to predict target $y$ from $\vz$.
Note that such a representation exists for our task: simply setting $\vz = f(\vx, a) = (-1)^a\vx$ makes it impossible to predict whether a particular $\vz$ corresponds to $a = 0$ or $a = 1$, while still allowing us to train a classifier $h$ with essentially perfect accuracy ($h(\vz) = \mathds{1}_{\{z_1 > 0\}}$).

Adversarial training for fair representations

Samples from our example distribution.
The blue group ($a = 0$) is sampled from $p_0$ and the orange group ($a = 1$) is sampled from $p_1$.

Sensitive attribute recovery rates for adversarial training and fair normalizing flows (FNF) with 100 different random seeds.

Adversarial training [Edwards & Storkey, 2016, Madras et al., 2018] is an approach that trains encoder $f$ and classifier $h$ jointly with an adversary $g$ trying to predict the sensitive attribute $a$.
While the adversary tries to minimize its loss $\mathcal{L}_{adv}$, the encoder $f$ and classifier $h$ are trying to maximize $\mathcal{L}_{adv}$ and minimize the classification loss $\mathcal{L}_{clf}$ as

\begin{equation}
\min_{f, h} \max_{g \in \mathcal{G}} \E_{(\vx, a) \sim D} \left[
\mathcal{L}_{clf}(f(\vx, a), h) - \gamma \mathcal{L}_{adv}(f(\vx, a), g)
\right],
\end{equation}

where $\mathcal{G}$ denotes the model family of adversaries, neural networks, considered during training.
Unfortunately, there are two key issues with adversarial training.
First, it yields a non-convex optimization problem, which usually cannot be solved to optimality because of saddle points.
Second, it assumes that the adversary $g$ comes from a fixed model family $\mathcal{G}$, which means that even if the optimal $g \in \mathcal{G}$ cannot recover the sensitive attribute $a$, adversaries from other model families can still do so as demonstrated in recent work [Feng et al., 2019, Moyer et al., 2018, Elazar & Goldberg, 2018, Xu et al., 2020, Gupta et al., 2021].
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 <ref>, 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 <ref> 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 (larger networks).
In <ref> 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 $p_0(\vx)$ and $p_1(\vx)$. At the end of the section, we discuss the required changes if we only work with estimates.
Let $\mathcal{Z}_0$ and $\mathcal{Z}_1$ denote conditional distributions of $z = f(\vx, a)$ for $a \in \{0, 1\}$, and let $p_{Z_0}$ and $p_{Z_1}$ denote their respective densities.
Madras et al., 2018 have shown that bounding the statistical distance $\Delta(p_{Z_0}, p_{Z_1})$ between $\mathcal{Z}_0$ and $\mathcal{Z}_1$ provides an upper bound on the unfairness of any classifier $h$ built on top of the representation encoded by $f$.
The statistical distance between $\mathcal{Z}_0$ and $\mathcal{Z}_1$ is defined similarly to maximum mean discrepancy (MMD) [Gretton et al., 2006] between the two distributions:

\begin{equation} \label{eq:statdist}
\Delta(p_{Z_0}, p_{Z_1}) \triangleq \sup_{\mu \in \mathcal{B}}  \lvert \E_{\vz \sim \mathcal{Z}_0} [\mu(\vz)] - \E_{\vz \sim \mathcal{Z}_1} [\mu(\vz)] \rvert,
\end{equation}

where $\mu\colon \R^d \rightarrow \{0, 1\}$ is a function in a set of all binary classifiers $\mathcal{B}$ trying to discriminate between $\mathcal{Z}_0$ and $\mathcal{Z}_1$.
If we can train an encoder to induce latent distributions $\mathcal{Z}_0$ and $\mathcal{Z}_1$ with statistical distance below some threshold, then we can both upper bound the maximum adversarial accuracy by $(1 + \Delta(p_{Z_0}, p_{Z_1})) / 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 a lower bound of $\Delta(p_{Z_0}, p_{Z_1})$.
In contrast, we learn fair representations that allow computing the optimal adversary $\mu^*$ attaining the supremum in <ref> and thus enable exact evaluation of $\Delta(p_{Z_0}, p_{Z_1})$.

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 <ref>. We show the proof in <ref>.

The adversary $\mu^*$ attaining the supremum in the definition of $\Delta(p_{Z_0}, p_{Z_1})$ can be defined as $\mu^*(\vz) = \mathds{1}_{\{p_{Z_0}(\vz) \leq p_{Z_1}(\vz)\}}$, namely it evaluates to $1$ if and only if $p_{Z_0}(\vz) \leq p_{Z_1}(\vz)$.

This intuitively makes sense – given some representation $\vz$, the adversary computes likelihood under both distributions $\mathcal{Z}_0$ and $\mathcal{Z}_1$, and predicts the attribute with higher likelihood for that $\vz$. Liao et al., 2019 also observed that the optimal adversary can be phrased as $\argmax_{a} p(a | \bm{z})$.
So far, prior work mostly focused on mapping input $\vx$ to the latent representation $\vz = f_\theta(\vx, a)$ via standard neural networks.
However, for such models, given densities $p_0(\vx)$ and $p_1(\vx)$ over the input space, it is intractable to compute the densities $p_{Z_0}(\vz)$ and $p_{Z_1}(\vz)$ in the latent space as many inputs $\vx$ can be mapped to the same latent $\vz$ 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, $f_0$ and $f_1$, that encode inputs from the groups with sensitive attributes $a=0$ and $a=1$, respectively.
We show a high-level overview of FNF in <ref>.
Note that models $f_0$ and $f_1$ are parameterized by $\theta_0$ and $\theta_1$, but we do not write this explicitly to ease the notation.
Given some input $\vx_0 \sim p_0$, it is encoded to $\vz_0 = f_0(\vx_0)$, inducing a probability distribution $\mathcal{Z}_0$ with density $p_{Z_0}(\vz)$ over all possible latent representations $\vz$.
Similarly, inputs $\vx_1 \sim p_1$ are encoded to $\vz_1 = f_1(\vx_1)$, inducing the probability distribution $\mathcal{Z}_1$ with density $p_{Z_1}(\vz)$.
Clearly, if we can train $f_0$ and $f_1$ so that the resulting distributions $\mathcal{Z}_0$ and $\mathcal{Z}_1$ 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 $f_0$ and $f_1$ based on normalizing flows [Rezende & Mohamed, 2015] which allow us to compute the densities at $\vz$ using the change of variables formula

\begin{equation}
\label{eq:changevar}
\log p_{Z_a}(\vz) = \log p_a(f^{-1}_a(\vz)) + \log \bigg | \det \frac{\partial f^{-1}_a(\vz)}{\partial \vz} \bigg |
\end{equation}

for $a \in \{0, 1\}$.
Recall that <ref> provides a form of the optimal adversary.
To compute the statistical distance it remains to evaluate the expectations $\E_{\vz \sim \mathcal{Z}_0} [\mu^*(\vz)]$ and $\E_{\vz \sim \mathcal{Z}_1} [\mu^*(\vz)]$.
Sampling from $\mathcal{Z}_0$ and $\mathcal{Z}_1$ is straightforward – we can sample $\vx_0 \sim p_0$ and $\vx_1 \sim p_1$, and then pass the samples $\vx_0$ and $\vx_1$ through the respective encoders $f_0$ and $f_1$ to obtain $\vz_0 \sim \mathcal{Z}_0$ and $\vz_1 \sim \mathcal{Z}_1$.
Given that the outputs of $\mu^*$ are bounded between 0 and 1, we can then use Hoeffding inequality to compute the confidence intervals for our estimate using a finite number of samples.

Given a finite number of samples ${\vx}_0^1, {\vx}_0^2, ..., {\vx}_0^n \sim p_0$ and ${\vx}_1^1, {\vx}_1^2, ..., {\vx}_1^n \sim p_1$, denote as ${\vz}_0^i = f_0({\vx}_0^i)$ and ${\vz}_1^i = f_1({\vx}_1^i)$ and let $\hat{\Delta}(p_{Z_0}, p_{Z_1}) := |\frac{1}{n} \sum_{i=1}^n \mu^*({\vz}_0^i) - \frac{1}{n} \sum_{i=1}^n \mu^*({\vz}_1^i)|$ be an empirical estimate of the statistical distance $\Delta(p_{Z_0}, p_{Z_1})$.
Then, for $n \geq -2\log\left(\frac{1 - \sqrt{1 - \delta}}{2}\right)/\epsilon^2$ we are guaranteed that $\Delta(p_{Z_0}, p_{Z_1}) \leq \hat{\Delta}(p_{Z_0}, p_{Z_1}) + \epsilon$ with probability at least $1 - \delta$.

Learning Fair Normalizing Flows

Input: $N, B, \gamma, p_0, p_1$
Initialize $h, f_0, f_1$ with parameters $\theta_h, \theta_0, \theta_1$
$i=1$ to $N$
$j=1$ to $B$
Sample $\vx^j_0 \sim p_0, \vx^j_1 \sim p_1$
$\vz^j_0 = f_0(\vx^j_0)$
$\vz^j_1 = f_1(\vx^j_1)$
$\mathcal{L}_0 = \frac{1}{B} \sum_{j=1}^B (\log p_{Z_0}(\vz^j_0) - \log p_{Z_1}(\vz^j_0))$
$\mathcal{L}_1 = \frac{1}{B} \sum_{j=1}^B (\log p_{Z_1}(\vz^j_1) - \log p_{Z_0}(\vz^j_1))$
$\mathcal{L} = \gamma(\mathcal{L}_0 + \mathcal{L}_1) + (1 - \gamma)\mathcal{L}_{clf}$
Update $\theta_a \leftarrow \theta_a - \alpha \nabla_{\theta_a}\mathcal{L}$, for $a \in \{0, 1\}$
Update $\theta_h \leftarrow \theta_h - \alpha \nabla_{\theta_h}\mathcal{L}$

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 is not differentiable (as the classifier $\mu^*$ is binary), so we replace it with a differentiable proxy based on the symmetrized KL divergence, shown in <ref> below (proof provided in <ref>).
We show a high-level description of our training procedure in <ref>.
In each step, we sample a batch of $\vx_0$ and $\vx_1$ from the respective distributions and encode them to the representations $\vz_0$ and $\vz_1$.
We then estimate the symmetrized KL divergence between distributions $\mathcal{Z}_0$ and $\mathcal{Z}_1$, denoted as $\mathcal{L}_0 + \mathcal{L}_1$, and combine it with a classification loss $\mathcal{L}_{clf}$ using tradeoff parameter $\gamma$, and perform a gradient descent step to minimize the joint loss.
While we use a convex scalarization scheme to obtain the joint loss in <ref>, our approach is independent of the concrete multi-objective optimization objective (see <ref>).

We can bound
$\Delta(p_{Z_0}, p_{Z_1})^2 \leq \frac{1}{4}(KL(p_{Z_0}, p_{Z_1}) + KL(p_{Z_1}, p_{Z_0})).$

Bijective encoders for categorical data

Many fairness datasets consist of categorical data, and often even continuous data is discretized before training.
In this case, we will show that the optimal bijective representation can be easily computed.
Consider the case of discrete samples $\vx$ coming from a probability distribution $p(\vx)$ where each component $x_i$ takes a value from a finite set $\{1, 2, \dots, d_i\}$.
Similar to the continuous case, our goal is to find bijections $f_0$ and $f_1$ that minimize the statistical distance of the latent distributions.
Intuitively, we want to pair together inputs that have similar probabilities in both $p_0$ and $p_1$.
In <ref> we show that the solution that minimizes the statistical distance is obtained by sorting the inputs according to their probabilities in $p_0$ and $p_1$, and then matching inputs at 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 <ref>.
We can trade off accuracy and fairness by randomly selecting one of the two mappings based on a parameter $\gamma$.

Let $\mathcal{X} = \{\vx_1, ..., \vx_m\}$ and bijections $f_0, f_1: \mathcal{X} \rightarrow \mathcal{X}$.
Denote $i_1, i_2, ..., i_m$ and $j_1, ..., j_m$ permutations of $\{1, 2, ..., m\}$ such that $p_0(\vx_{i_1}) \leq p_0(\vx_{i_2}) \leq ... \leq p_0(\vx_{i_m})$ and $p_1(\vx_{j_1}) \leq p_1(\vx_{j_2}) \leq ... \leq p_1(\vx_{j_m})$.
The encoders defined by mapping $f_0(\vx_k) = \vx_k$ and $f_1(\vx_{j_k}) = \vx_{i_k}$ are bijective representations with the smallest possible statistical distance.

Statistical distance of true estimated density

In this work we assume access to a 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 (if it was provided by a regulatory agency), in many practical scenarios, and our experiments in <ref>, we only have an estimate $\hat{p}_0$ and $\hat{p}_1$ of the true densities $p_0$ and $p_1$.
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 $p_{Z_0}$ and $p_{Z_1}$ using the statistical distance between $\hat{p}_{Z_0}$ and $\hat{p}_{Z_1}$.

Let $\hat{p}_0$ and $\hat{p}_1$ be density estimates such that $TV(\hat{p}_0, p_0) < \epsilon/2$ and $TV(\hat{p}_1, p_1) < \epsilon/2$, where $TV$ stands for the total variation between two distributions.
If we denote the latent distributions $f_0(\hat{p}_0)$ and $f_1(\hat{p}_1)$ as $\hat{p}_{Z_0}$ and $\hat{p}_{Z_1}$ then $\Delta(p_{Z_0}, p_{Z_1}) \leq \Delta(\hat{p}_{Z_0}, \hat{p}_{Z_1}) + \epsilon$.

This theorem can be combined with <ref> to obtain a 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 low-dimensional 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, 2017].
We can thus leverage the rich literature on density estimation [Rezende & Mohamed, 2015, Dinh et al., 2016, van den Oord et al., 2016, van den Oord et al., 2016, van den Oord et al., 2016] to estimate $\hat{p}_0$ and $\hat{p}_1$.
Importantly, FNF is agnostic to the density estimation method (as we show in <ref>), 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 et 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, 2017], 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 a good density estimate, while keeping accuracy high (details shown in <ref>).
We make all of our code publicly available at <https://github.com/eth-sri/fnf>.

Evaluating Fair Normalizing Flows

We first evaluate FNF's effectiveness in learning fair representations by training different FNF models with different values for the utility fairness tradeoff parameter $\gamma$.
We estimate input densities using RealNVP [Dinh et al., 2016] for Health, MADE [Germain et al., 2015] for Adult and Compas, and Gaussian Mixture Models (GMMs) for the rest (we experiment with other density estimation methods in <ref>).
For continuous datasets we use RealNVP as encoder, while for categorical datasets we compute the optimal bijective representations using <ref>.
<ref> shows our results, each point representing a single model, with models on the right focusing on classification accuracy, and models on the left gradually increasing their fairness focus.
The results in <ref>, 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 (Law School) enforcing fairness only slightly degrades accuracy, while for others there is a substantial drop (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, as mentioned earlier, 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 a
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 <ref>).

Continuous datasets

Categorical datasets

Fair Normalizing Flows (FNF) on continuous and categorical data.
The points show different accuracy statistical distance tradeoffs (with 95% confidence intervals from varied random seeds), demonstrating that FNF significantly reduces statistical distance while retaining high accuracy.

Bounding adversarial accuracy

Bounding adversarial accuracy.

Recall that the guarantees provided by FNF hold for estimated densities $\hat{p}_0$ and $\hat{p}_1$.
Namely, the maximum adversarial accuracy for predicting whether the latent representation $\vz$ originates from distribution $\hat{\mathcal{Z}}_0$ or $\hat{\mathcal{Z}}_1$ is bounded by $(1 + \Delta(\hat{p}_{Z_0}, \hat{p}_{Z_1})) / 2$.
In this experiment, we investigate how well these guarantees transfer to the underlying distributions $\mathcal{Z}_0$ and $\mathcal{Z}_1$.
In <ref> we show our upper bound on the adversarial accuracy computed from the statistical distance using the estimated densities (diagonal dashed line), together with adversarial accuracies obtained by training an adversary, a multilayer perceptron (MLP) with two hidden layers of 50 neurons, for each model from <ref>.
We also show 95% confidence intervals obtained using the Hoeffding bound from <ref>.
We observe that our upper bound from the estimated densities $\hat{p}_0$ and $\hat{p}_1$ provides a tight upper bound on the adversarial accuracy for the true distributions $\mathcal{Z}_0$ and $\mathcal{Z}_1$.
This demonstrates that, even though the exact constants from <ref> are intractable, our density estimate is good enough in practice, and our bounds hold for adversaries on the true distribution.

Adversarial fair representation learning methods are only fair adversaries from a training family $\mathcal{G}$
while FNF provides a provable upper bound on the maximum accuracy of any adversary.

Comparison with adversarial training

We now compare FNF with adversarial fair representation learning methods on Adult dataset: LAFTR-DP ($\gamma = 2$) [Madras et al., 2018], MaxEnt-ARL ($\alpha = 10$) [Roy & Boddeti, 2019], and Adversarial Forgetting ($\rho = 0.001, \delta = 1, \lambda = 0.1$) [Jaiswal et al., 2020].
We train with a family of adversaries $\mathcal{G}$ trying to predict the sensitive attribute from the latent representation.
Here, the families $\mathcal{G}$ are MLPs with 1 hidden layer of 8 neurons for LAFTR-DP, and 2 hidden layers with 64 neurons and 50 neurons for MaxEnt-ARL and Adversarial Forgetting, respectively.
In <ref> we show that these methods generally prevent adversaries from $\mathcal{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., 2021]: adversarial training provides no guarantees against adversaries outside $\mathcal{G}$.
In contrast, FNF computes a provable upper bound on the accuracy of any adversary for the estimated input distribution, and <ref> 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, reverse an unfavorable outcome, which is considered to be fundamental to explainable algorithmic decision-making [Venkatasubramanian & Alfano, 2020].
To that end, we apply FNF with $\gamma = 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, $\vx$ such that $h(f_a(\vx)) = h(\vz) = 0$, we compute the closest $\tilde{\vz}$ (corresponding to a point $\tilde{\vx}$ from the dataset) the $\ell_2$-distance in latent space such that $h(\tilde{\vz}) = 1$.
We then linearly interpolate between $\vz$ and $\tilde{\vz}$ to find a (potentially crude) approximation of the closest point to $\vz$ 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 <ref>, we also show that, unlike prior work, FNF enables practical interpretability analyses.

Flow architectures

FNF performance with different flow encoder architectures.

In the next experiment we compare the RealNVP encoder with an alternative encoder based on the Neural Spline Flows architecture [Durkan et al., 2019] for the Crime dataset.
In <ref> we show the statistical distance and accuracy for models obtained using different values for the tradeoff parameter $\gamma$.
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.

Transfer learning

Unlike prior work, transfer learning with FNF requires no additional reconstruction 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 is independent of the label).
For the primary condition group MSC2a3 we retain the accuracy at 73.8%, while for METAB3 it slightly decreases from 75.4% to 73.1%.

§ CONCLUSION

We introduced Fair Normalizing Flows (FNF), a 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 a 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 fairness without significantly sacrificing utility, while simultaneously allowing interpretation of the representations and transferring to unseen tasks.

§ 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 to be non-discriminatory regardless of the concrete downstream use case.
Since our method relies on accurate density estimates, we envision that the data regulators, whose tasks already include determining fairness criteria, data sources, and auditing results, would create a regulatory framework for density estimation that can then be realized by, 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 in the context of our work and in the broader field (particularly for high-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.

[Albarghouthi et al., 2017]
Aws Albarghouthi, Loris D'Antoni, Samuel Drews, and Aditya V. Nori.
Fairsquare: probabilistic verification of program fairness.
Proc. ACM Program. Lang., 2017.

[Angwin et al., 2016]
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner.
Machine bias, 2016.

[Barocas & Selbst, 2016]
Solon Barocas and Andrew D. Selbst.
Big data's disparate impact.
California Law Review, 2016.

[Bastani et al., 2019]
Osbert Bastani, Xin Zhang, and Armando Solar-Lezama.
Probabilistic verification of fairness properties via concentration.
Proc. ACM Program. Lang., 2019.

[Brennan et al., 2009]
Tim Brennan, William Dieterich, and Beate Ehret.
Evaluating the predictive validity of the compas risk and needs
assessment system.
Criminal Justice and Behavior, 2009.

[Cerrato et al., 2022]
Mattia Cerrato, Marius Köppel, Alexander Segner, and Stefan Kramer.
Fair group-shared representations with normalizing flows.
arXiv preprint arXiv:2201.06336, 2022.

[Creager et al., 2019]
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.

[Dinh et al., 2015]
Laurent Dinh, David Krueger, and Yoshua Bengio.
NICE: non-linear independent components estimation.
In 3rd International Conference on Learning Representations,

[Dinh et al., 2016]
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio.
Density estimation using real NVP.
CoRR, 2016.

[Dua & Graff, 2017]
Dheeru Dua and Casey Graff.
UCI machine learning repository, 2017.

[Durkan et al., 2019]
Conor Durkan, Artur Bekasov, Iain Murray, and George Papamakarios.
Neural spline flows.
Advances in Neural Information Processing Systems, 2019.

[Dwork et al., 2006]
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.

[Dwork et al., 2012]
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard S.
Fairness through awareness.
In Innovations in Theoretical Computer Science 2012, 2012.

[Edwards & Storkey, 2016]
Harrison Edwards and Amos J. Storkey.
Censoring representations with an adversary.
In 4th International Conference on Learning Representations,

[Elazar & Goldberg, 2018]
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, 2021]
Proposal for a regulation laying down harmonised rules on artificial
intelligence, 2021.

[Feng et al., 2019]
Rui Feng, Yang Yang, Yuehan Lyu, Chenhao Tan, Yizhou Sun, and Chunping Wang.
Learning fair representations via an adversarial framework.
CoRR, abs/1904.13341, 2019.

[Flaticon.com, 2021]
Image, 2021.

[FTC, 2021]
Aiming for truth, fairness, and equity in your company’s use of ai,

[Germain et al., 2015]
Mathieu Germain, Karol Gregor, Iain Murray, and Hugo Larochelle.
MADE: masked autoencoder for distribution estimation.
In Proceedings of the 32nd International Conference on Machine
Learning, 2015.

[Goodfellow et al., 2014]
Ian 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.

[Gretton et al., 2006]
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf,
and Alexander J. Smola.
A kernel method for the two-sample-problem.
In Advances in Neural Information Processing Systems 19, 2006.

[Grover et al., 2020]
Aditya Grover, Christopher Chute, Rui Shu, Zhangjie Cao, and Stefano Ermon.
Alignflow: Cycle consistent learning from multiple domains via
normalizing flows.
In AAAI, pp.  4028–4035. AAAI Press, 2020.

[Gupta et al., 2021]
Umang Gupta, Aaron Ferber, Bistra Dilkina, and Greg Ver Steeg.
Controllable guarantees for fair outcomes via contrastive information
CoRR, abs/2101.04108, 2021.

[Hardt & Price, 2015]
Moritz Hardt and Eric Price.
Tight bounds for learning a mixture of two gaussians.
In Rocco A. Servedio and Ronitt Rubinfeld (eds.), Proceedings
of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015.

[Hardt et al., 2016]
Moritz Hardt, Eric Price, and Nati Srebro.
Equality of opportunity in supervised learning.
In Advances in Neural Information Processing Systems 29, 2016.

[He et al., 2019]
Yuzi He, Keith Burghardt, and Kristina Lerman.
Learning fair and interpretable representations via linear
CoRR, abs/1910.12854, 2019.

[Hoogeboom et al., 2019]
Emiel Hoogeboom, Jorn W. T. Peters, Rianne van den Berg, and Max Welling.
Integer discrete flows and lossless compression.
In NeurIPS, pp.  12134–12144, 2019.

[Jagielski et al., 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.

[Jaiswal et al., 2020]
Ayush Jaiswal, Daniel Moyer, Greg Ver Steeg, Wael AbdAlmageed, and Premkumar
Invariant representations through adversarial forgetting.
In The Thirty-Fourth AAAI Conference on Artificial
Intelligence, 2020.

[Jiang, 2017]
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.

[John et al., 2020]
Philips George John, Deepak Vijaykeerthy, and Diptikalyan Saha.
Verifying individual fairness in machine learning models.
In Proceedings of the Thirty-Sixth Conference on Uncertainty in
Artificial Intelligence, 2020.

[Kaggle, 2012]
Health heritage prize, 2012.
URL <https://www.kaggle.com/c/hhp>.

[Kamishima et al., 2011]
Toshihiro Kamishima, Shotaro Akaho, and Jun Sakuma.
Fairness-aware learning through regularization approach.
In Data Mining Workshops (ICDMW), 2011.

[Kehrenberg et al., 2020]
Thomas Kehrenberg, Myles Bartlett, Oliver Thomas, and Novi Quadrianto.
Null-sampling for interpretable and fair representations.
In Computer Vision - ECCV 2020 - 16th European Conference,

[Khandani et al., 2010]
Amir E Khandani, Adlar J Kim, and Andrew W Lo.
Consumer credit-risk models via machine-learning algorithms.
Journal of Banking & Finance, 2010.

[Kingma & Ba, 2015]
Diederik P. Kingma and Jimmy Ba.
Adam: A method for stochastic optimization.
In 3rd International Conference on Learning Representations,

[Kingma & Dhariwal, 2018]
Diederik P. Kingma and Prafulla Dhariwal.
Glow: Generative flow with invertible 1x1 convolutions.
In Advances in Neural Information Processing Systems 31, 2018.

[Kingma & Welling, 2014]
Diederik P. Kingma and Max Welling.
Auto-encoding variational bayes.
In 2nd International Conference on Learning Representations,

[Liao et al., 2019]
Jiachun Liao, Chong Huang, Peter Kairouz, and Lalitha Sankar.
Learning generative adversarial representations (GAP) under
fairness and censoring constraints.
CoRR, abs/1910.00411, 2019.

[Lin et al., 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.

[Lloyd, 1982]
Stuart P. Lloyd.
Least squares quantization in PCM.
IEEE Trans. Inf. Theory, 1982.

[Locatello et al., 2019]
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.

[Louizos et al., 2016]
Christos Louizos, Kevin Swersky, Yujia Li, Max Welling, and Richard S. Zemel.
The variational fair autoencoder.
In 4th International Conference on Learning Representations,

[MacQueen, 1967]
James MacQueen.
Some methods for classification and analysis of multivariate
In Proceedings of the fifth Berkeley symposium on mathematical
statistics and probability, 1967.

[Madras et al., 2018]
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.

[Martínez et al., 2020]
Natalia Martínez, Martín Bertrán, and Guillermo Sapiro.
Minimax pareto fairness: A multi objective perspective.
In Proceedings of the 37th International Conference on Machine
Learning, 2020.

[McNamara et al., 2019]
Daniel McNamara, Cheng Soon Ong, and Robert C. Williamson.
Costs and benefits of fair representation learning.
In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics,
and Society, 2019.

[Menon & Williamson, 2018]
Aditya Krishna Menon and Robert C. Williamson.
The cost of fairness in binary classification.
In Conference on Fairness, Accountability and Transparency,

[Moyer et al., 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.

[Paszke et al., 2019]
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-performance deep learning library.
In Advances in Neural Information Processing Systems 32, 2019.

[Pidhorskyi et al., 2018]
Stanislav Pidhorskyi, Ranya Almohsen, and Gianfranco Doretto.
Generative probabilistic novelty detection with adversarial
In Advances in Neural Information Processing Systems 31, 2018.

[Poyiadzi et al., 2020]
Rafael Poyiadzi, Kacper Sokol, Raúl Santos-Rodríguez, Tijl De
Bie, and Peter A. Flach.
FACE: feasible and actionable counterfactual explanations.
In AAAI/ACM Conference on AI, Ethics, and Society, 2020.

[Rezende & Mohamed, 2015]
Danilo Jimenez Rezende and Shakir Mohamed.
Variational inference with normalizing flows.
In Proceedings of the 32nd International Conference on Machine
Learning, 2015.

[Roy & Boddeti, 2019]
Proteek Chandan Roy and Vishnu Naresh Boddeti.
Mitigating information leakage in image representations: A maximum
entropy approach.
In IEEE Conference on Computer Vision and Pattern
Recognition, 2019.

[Ruoss et al., 2020]
Anian Ruoss, Mislav Balunovic, Marc Fischer, and Martin T. Vechev.
Learning certified individually fair representations.
In Advances in Neural Information Processing Systems 33, 2020.

[Segal et al., 2020]
Shahar Segal, Yossi Adi, Benny Pinkas, Carsten Baum, Chaya Ganesh, and Joseph
Fairness in the eyes of the data: Certifying machine-learning models.
CoRR, abs/2009.01534, 2020.

[Song & Shmatikov, 2020]
Congzheng Song and Vitaly Shmatikov.
Overlearning reveals sensitive attributes.
In 8th International Conference on Learning Representations,

[Song et al., 2019]
Jiaming Song, Pratyusha Kalluri, Aditya Grover, Shengjia Zhao, and Stefano
Learning controllable fair representations.
In The 22nd International Conference on Artificial Intelligence
and Statistics, 2019.

[Tran et al., 2019]
Dustin Tran, Keyon Vafa, Kumar Krishna Agrawal, Laurent Dinh, and Ben Poole.
Discrete flows: Invertible generative models of discrete data.
In NeurIPS, pp.  14692–14701, 2019.

[Urban et al., 2020]
Caterina Urban, Maria Christakis, Valentin Wüstholz, and Fuyuan Zhang.
Perfectly parallel fairness certification of neural networks.
Proc. ACM Program. Lang., 2020.

[Usman et al., 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.

[Ustun et al., 2019]
Berk Ustun, Alexander Spangher, and Yang Liu.
Actionable recourse in linear classification.
In Proceedings of the Conference on Fairness, Accountability,
and Transparency, 2019.

[van den Oord et al., 2016]
Aäron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol
Vinyals, Alex Graves, Nal Kalchbrenner, Andrew W. Senior, and Koray
Wavenet: A generative model for raw audio.
In The 9th ISCA Speech Synthesis Workshop,

[van den Oord et al., 2016]
Aäron van den Oord, Nal Kalchbrenner, Lasse Espeholt, Koray Kavukcuoglu,
Oriol Vinyals, and Alex Graves.
Conditional image generation with pixelcnn decoders.
In Advances in Neural Information Processing Systems 29,

[van den Oord et al., 2016]
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.

[van der Maaten & Hinton, 2008]
Laurens van der Maaten and Geoffrey Hinton.
Visualizing data using t-sne.
Journal of Machine Learning Research, 2008.

[Venkatasubramanian & Alfano, 2020]
Suresh Venkatasubramanian and Mark Alfano.
The philosophical basis of algorithmic recourse.
In Conference on Fairness, Accountability, and Transparency,

[Wang et al., 2021]
Tianhao Wang, Zana Buçinca, and Zilin Ma.
Learning interpretable fair representations.
Technical report, Harvard University, 2021.

[Wei & Niethammer, 2020]
Susan Wei and Marc Niethammer.
The fairness-accuracy pareto front.
CoRR, 2020.

[Whittaker et al., 2018]
Meredith Whittaker, Kate Crawford, Roel Dobbe, Genevieve Fried, Elizabeth
Kaziunas, Varoon Mathur, Sarah Mysers West, Rashida Richardson, Jason
Schultz, and Oscar Schwartz.
AI now report 2018.
AI Now Institute at New York University New York, 2018.

[Wightman, 2017]
F. Linda Wightman.
LSAC national longitudinal bar passage study, 2017.

[Wong & Kolter, 2020]
Eric Wong and J. Zico Kolter.
Learning perturbation sets for robust machine learning.
CoRR, abs/2007.08450, 2020.

[Xie et al., 2017]
Qizhe Xie, Zihang Dai, Yulun Du, Eduard H. Hovy, and Graham Neubig.
Controllable invariance through adversarial feature learning.
In Advances in Neural Information Processing Systems 30, 2017.

[Xu et al., 2020]
Yilun Xu, Shengjia Zhao, Jiaming Song, Russell Stewart, and Stefano Ermon.
A theory of usable information under computational constraints.
In 8th International Conference on Learning Representations,

[Zafar et al., 2017]
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez, and Krishna P.
Fairness constraints: Mechanisms for fair classification.
In Proceedings of the 20th International Conference on
Artificial Intelligence and Statistics, 2017.

[Zemel et al., 2013]
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.

[Zhang et al., 2018]
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.

[Zhao & Gordon, 2019]
Han Zhao and Geoffrey J. Gordon.
Inherent tradeoffs in learning fair representations.
In Advances in Neural Information Processing Systems 32, 2019.

§ APPENDIX

§.§ Proofs

Here we present the proofs of the theorems used in the paper.

Proof of <ref> (Optimal adversary)

Here we prove <ref>, which states the form of an adversary $\mu\colon \R^d \rightarrow \{0, 1\}$ that can achieve the highest discrimination between $\mathcal{Z}_0$ and $\mathcal{Z}_1$.
We start by rewriting the equation for statistical distance $\Delta(p_{Z_0}, p_{Z_1})$ as follows:

\begin{equation}
\Delta(p_{Z_0}, p_{Z_1}) = \sup_{\mu}  \big | \E_{\vz \sim \mathcal{Z}_0} [\mu(\vz)] - \E_{\vz \sim \mathcal{Z}_1} [\mu(\vz)] \big |
= \sup_{\mu}  \bigg | \int_{\vz} (p_{Z_0}(\vz) - p_{Z_1}(\vz))\mu(\vz) \,dz \bigg |.
\end{equation}

To maximize the absolute value of the integral, we either have to maximize or minimize the integral $\int_{\vz} (p_{Z_0}(\vz) - p_{Z_1}(\vz))\mu(\vz) \,dz$.
Clearly, to maximize the integral we should choose the function $\mu = \mathds{1}_{\{p_{Z_0}(\vz) \geq p_{Z_1}(\vz)\}}$, for which $\mu(\vz) = 1$ if and only if $p_{Z_0}(\vz) \geq p_{Z_1}(\vz)$, and 0 otherwise.
Similarly, to minimize the integral we should choose the function $\mu = \mathds{1}_{\{p_{Z_0}(\vz) \leq p_{Z_1}(\vz)\}}$ for which $\mu(\vz) = 1$ if and only if $p_{Z_0}(\vz) \leq p_{Z_1}(\vz)$, 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 $\mu^*(\vz) = \mathds{1}_{\{p_{Z_0}(\vz) \leq p_{Z_1}(\vz)\}}$.
This subsequently yields $\Delta(p_{Z_0}, p_{Z_1}) = \big | \E_{\vz \sim \mathcal{Z}_0} [\mu^*(\vz)] - \E_{\vz \sim \mathcal{Z}_1} [\mu^*(\vz)] \big |$.
Moreover, we can also write $\Delta(p_{Z_0}, p_{Z_1}) = \left| \int_{\vz} (p_{Z_1}(\vz) - p_{Z_0}(\vz))\mu^*(\vz) \,dz \right| = \left| \int_{\vz} \max(0, p_{Z_1}(\vz) - p_{Z_0}(\vz)) \,dz \right|$ (this will be used to prove <ref>).

Proof of <ref> (Finite sample estimate)

We start by plugging in the optimal adversary $\mu^*$ from <ref> into the definition of the statistical distance.
Let $\mu^*$ be the optimal adversary defined in <ref>, namely $\mu^*(\vz) = 1$ if and only if $p_{Z_0}(\vz) < p_{Z_1}(\vz)$.
We first write the statistical distance in terms of the optimal adversary $\mu^*$,
then bound the statistical distance using triangle inequality and finally apply Hoeffding's inequality on the individual terms:

\begin{align*}
\Delta(\mathcal{Z}_0, \mathcal{Z}_1) &= \sup_{\mu} \big | \E_{\vz \sim \mathcal{Z}_0} [\mu(\vz)] - \E_{\vz \sim \mathcal{Z}_1} [\mu(\vz)] \big | \\
&= \big | \E_{\vz \sim \mathcal{Z}_0} [\mu^*(\vz)] - \E_{\vz \sim \mathcal{Z}_1} [\mu^*(\vz)] \big | \\
&= \big | \E_{\vz \sim \mathcal{Z}_0} [\mu^*(\vz)] - \frac{1}{n} \sum_{i=1}^n \mu^*({\vz}_0^i) + \frac{1}{n} \sum_{i=1}^n \mu^*({\vz}_0^i) -  \frac{1}{n} \sum_{i=1}^n \mu^*({\vz}_1^i) + \frac{1}{n} \sum_{i=1}^n \mu^*({\vz}_1^i) -  \E_{\vz \sim \mathcal{Z}_1} [\mu^*(\vz)] \big | \\
&\leq \big | \E_{\vz \sim \mathcal{Z}_0} [\mu^*(\vz)] - \frac{1}{n} \sum_{i=1}^n \mu^*({\vz}_0^i) \big | + \hat{\Delta}(\mathcal{Z}_0, \mathcal{Z}_1) + \big | \frac{1}{n} \sum_{i=1}^n \mu^*({\vz}_1^i) - \E_{\vz \sim \mathcal{Z}_1} [\mu^*(\vz)] \big | \\
&\leq \hat{\Delta}(\mathcal{Z}_0, \mathcal{Z}_1) + \epsilon
\end{align*}

where Hoeffding's inequality guarantees that with probability at least $(1 - 2\exp(-n\epsilon^2/2))^2 \geq 1 - \delta$ the first and last summand are at most $\epsilon/2$.

Proof of <ref> (Bounding the statistical distance with symmetrized KL)

We can bound the statistical distance $\Delta(p_{Z_0}, p_{Z_1})$ by noticing that $|\mu(\vz)| \leq 1$ because $\mu$ is a binary classifier and thus

\begin{equation*}
\Delta(p_{Z_0}, p_{Z_1}) = \sup_{\mu}  \bigg | \int_{\vz} (p_{Z_0}(\vz) - p_{Z_1}(\vz))\mu(\vz) \,dz \bigg | \leq \int_{\vz} |p_{Z_0}(\vz) - p_{Z_1}(\vz)| \,dz = TV(p_{Z_0}, p_{Z_1}).
\end{equation*}

Pinsker's inequality guarantees that $TV(p_{Z_0}, p_{Z_1})^2 \leq \frac{1}{2} KL(p_{Z_0}, p_{Z_1})$.
Given that $TV(p_{Z_0}, p_{Z_1}) = TV(p_{Z_1}, p_{Z_0})$ we also have that $TV(p_{Z_0}, p_{Z_1})^2 \leq \frac{1}{2} KL(p_{Z_1}, p_{Z_0})$.
Thus, in order to bound the statistical distance we can use
$2\Delta(p_{Z_0}, p_{Z_1})^2 \leq 2TV(p_{Z_0}, p_{Z_1})^2 \leq \frac{1}{2} KL(p_{Z_0}, p_{Z_1}) + \frac{1}{2} KL(p_{Z_1}, p_{Z_0})$, which corresponds to our objective with symmetrized KL divergence used in <ref>.

Proof of <ref> (Encoding for discrete distributions)

Without loss of generality we can assume that $f_0(\vx_k) = \vx_k$.
Assume that $f_1(\vx) = \vy$ and $f_1(\vx') = \vy'$ where $p_0(\vx) < p_0(\vx')$ and $p_1(\vy) > p_1(\vy')$.
Let $d_1 = |p_0(\vx) - p_1(\vy)| + |p_0(\vx') - p_1(\vy')|$ and $d_2 = |p_0(\vx) - p_1(\vy')| + |p_0(\vx') - p_1(\vy)|$.
In the case when $p_1(\vy) \leq p_0(\vx)$ or $p_1(\vy') \geq p_0(\vx')$ it is easy to show that $d_1 = d_2$.
Now, in the case when $p_0(\vx) < p_1(\vy') < p_0(\vx') < p_1(\vy)$, we can see that $d_2 \leq d_1 - (p_0(\vx) - p_1(\vy')) < d_1$.
Similarly, when $p_0(\vx) < p_1(\vy') < p_1(\vy) < p_0(\vx')$, we can see that $d_2 \leq d_1 - (p_1(\vy) - p_1(\vy')) < d_1$.
In all cases, $d_2 \leq d_1$, which means that if we swap $f_1(\vx)$ and $f_1(\vx')$ the total variation either decreases or 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 the two arrays are sorted the same way.

Proof of <ref> (True and approximate distributions)

Let $a \in \{0, 1\}$ be a sensitive attribute, and assume that $TV(\hat{p}_a, p_a) < \epsilon/2$.
Recall that the change of variables for probability densities gives us that for the representation $\vz = f_a(\vx)$ we have, similar as in <ref>, $p_{Z_a}(\vz) = p_a(\vx) \left| \det \frac{\partial f_a(\vx)}{\partial \vx} \right|^{-1}$ and $\hat{p}_{Z_a}(\vz) = \hat{p}_a(\vx) \left| \det \frac{\partial f_a(\vx)}{\partial \vx} \right|^{-1}$.
Then, using those formulas together with the change of variables rule for multivariate integrals we derive:

\begin{align*}
TV(\hat{p}_{Z_a}, p_{Z_a}) &= \int_{\vz} \left| \hat{p}_{Z_a}(\vz) - p_{Z_a}(\vz) \right| \,dz \\
&= \int_{\vx} \left| \hat{p}_{Z_a}(f_a(\vx)) - p_{Z_a}(f_a(\vx)) \right| \left| \det \frac{\partial f_a(\vx)}{\partial \vx} \right| \,dx \\
&= \int_{\vx} \left| \hat{p}_a(\vx) \left| \det \frac{\partial f_a(\vx)}{\partial \vx} \right|^{-1}  - p_a(\vx) \left| \det \frac{\partial f_a(\vx)}{\partial \vx} \right|^{-1} \right| \left| \det \frac{\partial f_a(\vx)}{\partial \vx} \right| \,dx \\
&= \int_{\vx} \left| \hat{p}_a(\vx) - p_a(\vx) \right| \,dx \\
&= TV(\hat{p}_a, p_a) \\
&< \epsilon/2.
\end{align*}

We will also use the observation from the proof of <ref> which states that
\[ \Delta(p_{Z_0}, p_{Z_1}) = \left| \int_{\vz} \max(0, p_{Z_1}(\vz) - p_{Z_0}(\vz)) \,dz \right|. \]

We can now observe that the following inequality holds:

\begin{equation*}
\max(0, p_{Z_0}(\vz) - p_{Z_1}(\vz)) \leq |p_{Z_0}(\vz) - \hat{p}_{Z_0}(\vz)| + \max(0, \hat{p}_{Z_0}(\vz) - \hat{p}_{Z_1}(\vz)) + |\hat{p}_{Z_1}(\vz) - p_{Z_1}(\vz)|
\end{equation*}

Integrating both sides yields:

\begin{align*}
\Delta(p_{Z_0}, p_{Z_1}) &\leq TV(p_{Z_0}(\vz), \hat{p}_{Z_0}(\vz)) + \Delta(\hat{p}_{Z_0}, \hat{p}_{Z_1}) + TV(p_{Z_1}(\vz), \hat{p}_{Z_1}(\vz)) \\
&\leq \Delta(\hat{p}_{Z_0}, \hat{p}_{Z_1}) + \epsilon
\end{align*}

Here, the last inequality follows from the previously proved inequality $TV(\hat{p}_{Z_a}, p_{Z_a}) < \epsilon/2$, applied for both $a = 0$ and $a = 1$.

§ 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 <ref>.

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.

§.§ Datasets

We consider five commonly studied datasets from the fairness literature: Adult and Crime from the UCI machine learning repository [Dua & Graff, 2017], 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 be used as validation set.
<ref> displays the dataset statistics for each of these splits.
Finally, we drop uninformative features to facilitate density estimation.
We show that the removal of these features does not significantly affect the predictive utility of the data in <ref>.

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 a person makes over 50000 US dollars per year.
We consider sex as the protected attribute, and we discretize the dataset by keeping only the categorical columns relationship, workclass, marital-status, race, occupation, education-num, and education.

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 a public records request, ProPublica obtained two years worth of COMPAS scores (18610 people) from the Broward County Sheriff's Office in Florida.
This data was then augmented with public criminal records from the Broward County Clerk's Office website.
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 as 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-degree, and v-score-text.

Classification accuracy before and after removing uninformative features during preprocessing.
For each dataset we train a multi-layer perceptron (MLP) with the same architecture on the original and preprocessed data and report the average accuracy with standard deviation for five different random seeds.
We can observe that the accuracy only decreases slightly after preprocessing.

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.
It 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 is above or below the median.
We consider race as the protected attribute, which we set to 1 if the percentage of white people divided by 5 is smaller than the percentage of black, asian, and hispanic individuals, and to 0 otherwise.
We keep the following 6 features: racePctWhite, pctWInvInc, PctFam2Par, PctKids2Par, PctYoungKids2Par, PctKidsBornNeverMar.

The Health dataset was created for the Heritage Health Prize [Kaggle, 2012] competition on Kaggle and contains medical records of over 55000 patients.
We consider the merged claims, drug count, lab count, and members sheets, which have a 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 to 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-total, DrugCount-months, no-Claims, no-Providers, PayDelay-total, PrimaryConditionGroup, Specialty, ProcedureGroup, and PlaceSvc.
For the transfer learning experiments we follow Madras et al., 2018 and omit the primary condition group labels from the set of features and try to predict them from the latent representation without explicitly optimizing for the task.

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 on over 100000 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, 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).

§.§ Training details

Our code is implemented in PyTorch [Paszke et al., 2019].

Computing resources

We run all experiments on a desktop PC using a single GeForce RTX 2080 Ti GPU and 16-core Intel(R) Core(TM) i9-9900K CPU @ 3.60GHz.

Hyperparameters for main experiments

For Crime we estimate input density using Gaussian Mixture Model (GMM) with 4 components for $a = 0$ and 2 components for $a = 1$.
For Law we use GMM with 8 components for both groups.
The Health dataset requires more complex density estimation so we use RealNVP [Dinh et al., 2016] with 4 blocks of 20 neurons each.
For categorical datasets, Adult and Compas, we perform density estimation using MADE [Germain et 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 0.
Training is 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 <ref>, we trained with the following 5 values for $\gamma$ for respective datasets: 0, 0.02, 0.1, 0.2, 0.9 for Crime, Adult and Compas, 0, 0.001, 0.02, 0.1, 0.9 for Law, 0, 0.05, 0.1, 0.5, 0.95 for Health.
Training for 1 epoch takes around 1 second for Crime, 5 seconds for Law, and 30 seconds for Health.

§ ADDITIONAL EXPERIMENTS

In this section we present additional experimental results.

Compatibility with other fairness metrics

In <ref> we focused on presenting results on statistical distance, as it can bound various fairness metrics [Madras et al., 2018].
In 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 <ref>.
We observe that FNF achieves high rates of demographic parity, equalized odds, and equality of opportunity with only small decreases in classification accuracy (similar to the results for the statistical distance showed in <ref>).

Demographic parity

Equalized odds

Equal opportunity

Tradeoff between accuracy and various fairness metrics (demographic parity, equalized odds, equal opportunity) when using Fair Normalizing Flows (FNF).

Compatibility with different scalarization schemes

Since fairness and accuracy are often competing objectives, they merit a treatment from multi-objective optimization.
Here, we investigate the scalarization scheme proposed by Wei & Niethammer, 2020 and replace our objective $\gamma(\mathcal{L}_0 + \mathcal{L}_1) + (1 - \gamma)\mathcal{L}_{clf}$, obtained via convex scalarization, with the Chebyshev scalarization scheme $\max\{\gamma(\mathcal{L}_0 + \mathcal{L}_1), (1 - \gamma)\mathcal{L}_{clf}\}$, where we use the same normalization for $\mathcal{L}_0$, $\mathcal{L}_1$, and $\mathcal{L}_{clf}$ as [Wei & Niethammer, 2020].

Different scalarization schemes.

We evaluate the schemes for a large range of $\gamma$ values on the Crime dataset and compute the Area Under the Curve (AUC) with the trapezoidal rule.
The convex scalarization yields an AUC of 0.6036, whereas the Chebyshev scalarization attains an AUC of 0.6051.
Moreover, we aggregate the results in <ref>.
In general, we observe that the convex scalarization slightly outperforms the Chebyshev 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-based optimization.
We consider more advanced multi-objective optimization methods [Lin et al., 2019, Martínez et al., 2020] an interesting direction for future work.

Different priors used with FNF.

Compatibility with different priors

In the following experiment, we demonstrate that FNF is compatible with any differentiable estimate of $p_0$ and $p_1$.
We consider Crime with the same setup as before, but with 3 different priors: a GMM with $k=3$ components, an autoregressive 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.
<ref> 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.

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, we consider the Crime dataset where for a community $\vx$: (i) race (non-white 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 $y$ strongly correlates with the sensitive attribute.
We encode every community $\vx \sim p_a$ as $\vz = f_a(\vx)$ and compute the corresponding community with opposite sensitive attribute that is also mapped to $\vz$, $\tilde{\vx} = f_{(1 - a)}^{-1} (\vz)$ (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 $\gamma \in \{0, 1\}$ in <ref>, where the dots are communities $\vx$ and the crosses are the corresponding $\tilde{\vx}$.
We run k-means [MacQueen, 1967, Lloyd, 1982] on all points with $a = 1$ and show the matched clusters for points with $a = 0$ (red clusters are matched).
For $\gamma = 0$, where FNF only minimizes the classification loss $\mathcal{L}_{clf}$, we observe a dichotomy between $\vx$ and $\tilde{\vx}$, since the encoder learns to match real points $\vx$ with high likelihood to points $\tilde{\vx}$ 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 $\vx$ and $-130.1$ for $\tilde{\vx}$.
In contrast, for $\gamma = 1$ FNF minimizes only the KL-divergence losses $\mathcal{L}_0$ + $\mathcal{L}_1$, 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 $-2.8$ for $\vx$ and $-3.0$ for $\tilde{\vx}$.

$\gamma = 0$

$\gamma = 1$

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.

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 tradeoff 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 <ref>).

Statistics for the Crime train set (reproduced from <ref>).

$y = 0$     $y = 1$

$a = 0$     0.29     0.71

$a = 1$     0.82     0.18

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 <ref> (the probabilities for the other datasets can be found in <ref>).
Clearly, <ref> shows 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, a consequence of bias in the data (some neighborhoods tend to be policed more often so more crimes will be reported), as has been documented in various studies, see [Brennan et al., 2009] for a study of the Compas dataset.
Thus, in accordance with the result from [Zhao & Gordon, 2019], we need to sacrifice a lot of accuracy to achieve a small statistical distance on the Crime dataset.


# A Note on John Simplex with Positive Dilation

Zhou Lu111This work is done during the author’s visit at SQZ institution.
Princeton University
<EMAIL_ADDRESS>
(December 2020)

###### Abstract

We prove a John’s theorem for simplices in $R^{d}$ with positive dilation
factor $d+2$, which improves the previously known $d^{2}$ upper bound. This
bound is tight in view of the $d$ lower bound. Furthermore, we give an example
that $d$ isn’t the optimal lower bound when $d=2$. Our results answered both
questions regarding John’s theorem for simplices with positive dilation raised
by Leme and Schneider (2020).

##  1 Introduction

In the problem of linear function reconstruction (Khachiyan (1995), Summa et
al. (2014), Nikolov (2015)), one needs to efficiently reconstruct a linear
function $f$ defined on a set $X$ by using a zeroth order oracle. When the
cost of oracle querying grows along with accuracy, a John like simplex serves
as a good basis as in Leme and Schneider (2020).

A crucial step of their method is to find a simplex $T$ with vertices in $X$,
such that $X$ can be contained in some translate of $T$ with dilation, where a
smaller (absolute value) dilation factor indicates higher efficiency. When
considering negative dilation, a translate $-dT$ is able contain $X$ so the
upper bound is $O(d)$ which matches its lower bound.

However, if we look at positive dilation, it seems to be less efficient than
negative dilation because only a worse $d^{2}$ upper bound was given in Leme
and Schneider (2020). Though a better bound for positive dilation does not
immediately help design better algorithms for the reconstruction problem, it
is natural to ask if we can improve it.

We prove a John’s theorem for simplices with positive dilation factor $d+2$
which answers the question affirmatively. Furthermore, we give a counter-
example that the $d$ lower bound given in Leme and Schneider (2020) isn’t
tight when $d=2$.

##  2 Background

In the seminal work John (2014), it’s proven that any convex $X\subset R^{d}$
can be sandwiched between two concentric ellipsoids of ratio $d$.
Specifically, the following theorem was given in John (2014):

######  Theorem 2.1.

Given any convex body $X\subset R^{d}$, let $x+TB_{d}$ denote the minimal
volume ellipsoid containing $X$, then it holds

$x+\frac{1}{d}TB_{d}\subset X\subset x+TB_{d}$ (1)

The ellipsoid $x+TB_{d}$ is called ’John ellipsoid’. For a more comprehensive
review we refer the readers to Henk (2012). In this paper we consider general
$X$ which is potentially non-convex, and we aim to find a John like simplex
with positive dilation factor $O(d)$ so that it can be seen as an analogue to
John ellipsoid.

######  Definition 2.2.

Given $d+1$ points $v_{1},...,v_{d+1}$ in $R^{d}$, we call their convex hull a
simplex with vertices $v_{1},...,v_{d+1}$.

We consider the following: given a compact set $X\subset R^{d}$ which is not
necessarily convex or connected, we want to find $d+1$ points in $X$ forming a
simplex $T$ such that $X$ is contained in some translate of $T$ with positive
dilation.

A simple method to do so is by considering the maximum volume simplex (MVS) of
$X$ as in Leme and Schneider (2020).

######  Definition 2.3.

A maximum volume simplex $T$ with vertices in a bounded set $X\subset R^{d}$
is one of the simplices whose euclidean measure is no less than any other
simplex of $X$.

######  Proposition 2.4.

There always exists a MVS as long as $X$ is compact.

###### Proof.

Because $X$ is bounded, the volume of its simplex has a least upper bound
$c\geq 0$, therefore we can find a sequence of simplices $T_{j}$ with vertices
$v_{1}^{(j)},...,v_{d+1}^{(j)}$, whose volumes converge to $c$. Due to the
compactness of $X$, any sequence in $X$ has a converging sub-sequence which
converges to a point in $X$, thus we can find indexes $a_{j}$ such that
$v_{1}^{(a_{j})}$ converges to a point $\tilde{v}_{1}\in X$.

We consider a new sequence of simplices $T_{a_{j}}$ whose first vertex is
replaced by $\tilde{v}_{1}$ while others keep unchanged. It’s easy to see that
their volumes still converge to $c$. Again we find a converging sub-sequence
of $v_{2}^{(a_{j})}$ which converges to a point $\tilde{v}_{2}\in X$, and
repeat this procedure until we have all $\tilde{v}_{i}$. Then the simplex with
vertices $\tilde{v}_{i}$ is the desired MVS. ∎

Leme and Schneider (2020) prove the following lemma by using the ’maximum
volume’ property:

######  Lemma 2.5.

Let $T$ be the MVS with vertices in $X$, then $X$ is contained in a translate
of $-dT$.

Using lemma 2.5 twice we get a $d^{2}$ upper bound for positive dilation. We
are interested in proving tighter bounds for the positive dilation factor.
Existing upper and lower bounds are $d^{2}$ and $d$ respectively as in Leme
and Schneider (2020), in their paper two questions regarding John’s theorem
for simplices with positive dilation were raised

Question 1: Can we get a John’s theorem for simplices with positive dilation
factor $O(d)$?

Question 2: Given compact $X\subset R$, can we always find a triangle $T$ with
vertices in $X$ so that $X$ is contained in some translate of $2T$?

We give an affirmative answer to question 1 by proving a $d+2$ upper bound,
and provide a counter-example to question 2.

##  3 $d+2$ upper bound

In this section we prove a $d+2$ upper bound based on a simple observation: by
fully exploiting the ’maximum volume’ property, we can squeeze $-dT$ to a much
smaller set which still contains $X$.

We already know that a simplex $T\in R^{d}$ can be covered by a translate of
$-dT$, therefore a naive method (choose $T$ to be MVS and use $-d$ dilation
twice) directly leads to a $d^{2}$ upper bound for positive dilation.

However, the first step of this method is extravagant in that we can finder a
smaller set covering $X$ when $d>2$. Think about the following example in
$R^{3}$: assume $T$ (the MVS of $X$) is the regular simplex with vertices
$v_{1},...,v_{4}$ and 0 as its center, then $-3T$ has $-3v_{1},...,-3v_{4}$ as
its vertices. We denote $S_{v,i}$ to be the hyperplane parallel to hyperplane
$v_{1},...,v_{i-1},v_{i+1},...,v_{4}$, with $v$ lying on it. By the definition
of $T$, $X$ lies between $S_{v_{i},i},S_{-\frac{5}{3}v_{i},i}$ for any
$i=1,...,4$, therefore much space is wasted in the ’cones’ of $-3T$.

Figure 1: Example in $R^{3}$. The red pyramid is $T$, the blue one is $-3T$
and the yellow ones are the wasted space.

The $d^{2}$ bound can be decomposed as $1+(d+1)(d-1)$ where for each $v_{i}$,
$T$ extends $d-1$ times along its direction. However, we only need to extend
once which yields a $1+(d+1)=d+2$ upper bound.

######  Theorem 3.1.

For any compact set $X\in R^{d}$, there exists $d+1$ points in $X$ forming a
simplex $T$ as its vertices, such that $X$ can be covered in a translate of
$(d+2)T$.

###### Proof.

We choose the MVS of $X$ to be $T$ with vertices $v_{1},...,v_{d+1}$ and we
assume 0 is its center (of gravity) without loss of generality. We denote
$\hat{v}_{i}$ to be the symmetric point of $v_{i}$ with respect to hyperplane
$v_{1},...,v_{i-1},v_{i+1},...,v_{d+1}$ along direction $v_{i}$, and $S_{v,i}$
to be the hyperplane parallel to hyperplane
$v_{1},...,v_{i-1},v_{i+1},...,v_{d+1}$, with $v$ lying on it. By the
definition of $T$, $X$ lies between $S_{v_{i},i},S_{\hat{v}_{i},i}$ for any
$i=1,...,d+1$, otherwise the ’maximum volume’ property will be contradicted.

We take a close look at the simplex $T^{\prime}$ made up of
$S_{\hat{v}_{i},i}$. Obviously $T^{\prime}$ is a translate of $T$ with
positive dilation and center (of gravity) 0 unchanged. Define the intersection
point between line $v_{i}\hat{v}_{i}$ (we overload the notation of vectors to
denote endpoints of a segment when the context is clear) and hyperplane
$v_{1},...,v_{i-1},v_{i+1},...,v_{d+1}$ as $w_{i}$, we have that
$v_{i}=\frac{d}{d+1}w_{i}v_{i}$ by the definition of center (of gravity).
Combing with the fact that $w_{i}v_{i}=\hat{v}_{i}w_{i}$, the dilation factor
is $(1+\frac{1}{d+1})/\frac{1}{d+1}=d+2$.

Denote the simplex made up of $S_{v_{i},i}$ as $\tilde{T}$ and the region
enclosed by $S_{v_{i},i},S_{\hat{v}_{i},i}$ as $\hat{T}$, we have the
following inclusion:

$X\subset\hat{T}=T^{\prime}\cap\tilde{T}\subset T^{\prime}$ (2)

which finishes our proof. ∎

##  4 Lower Bound $>d$ when $d=2$

We give a counter-example to question 2 in this section. The idea behind is
intuitive: we construct several discrete points as a hard case, so that these
discrete points won’t help much when we construct the covering triangle, but
hurts a lot when we consider covering them since the whole convex hull needs
to be covered implicitly.

######  Theorem 4.1.

There exists a compact set $X\in R^{2}$, such that for any triangle $T$ with
vertices in $X$, $X$ can’t be contained in any translate of $2T$.

###### Proof.

We pick 5 points:

$A=(-1,0),B=(1,0),C=(-\epsilon-\delta,1),D=(\epsilon+\delta,1),E=(0,\epsilon-1)$

to construct $X=\\{A,B,C,D,E\\}$, where constants (TBD) satisfy
$\epsilon,\delta\in(0,1)$. Due to symmetry, we discuss different choices of
$T$ by 6 cases and how they lead to contradiction.

Case 1: $T=\triangle CDE$

The intercept along $y=0$ of any translate of $2T$ has length at most
$4(\epsilon+\delta)<2$, thus $AB$ can’t be covered by any translate of $2T$.

Case 2: $T=\triangle ABE$

The intercept along $x=0$ of any translate of $2T$ has length at most
$2-2\epsilon<2-\epsilon$, thus $C,E$ can’t be simultaneously covered by any
translate of $2T$.

Case 3: $T=\triangle ACD$

The intercept along $y=0$ of any translate of $2T$ has length at most
$4(\epsilon+\delta)<2$, thus $AB$ can’t be covered by any translate of $2T$.

Case 4: $T=\triangle ABC$

The intercept along $y=1$ of any translate of $2T$ has length at most
$2\epsilon<2\epsilon+2\delta$ when its ’bottom’ is below $y=\epsilon-1$, thus
$CD$ and $E$ can’t be simultaneously covered by any translate of $2T$.

Case 5: $T=\triangle ACE$

The intercept along $y=0$ of any translate of $2T$ has length at most
$2-2\frac{(\epsilon+\delta)(1-\epsilon)}{2-\epsilon}<2$, thus $AB$ can’t be
covered by any translate of $2T$.

Case 6: $T=\triangle ADE$

We would like to prove that any translate of $2T$ can’t cover $\triangle ABC$.
We extend $\overrightarrow{AD}$ by twice to
$D^{\prime}=(1+2\epsilon+2\delta,1)$ and $\overrightarrow{AE}$ by twice to
$E^{\prime}=(1,2\epsilon-2)$, then try to move $\triangle ABC$ to fit in
$\triangle A^{\prime}D^{\prime}E^{\prime}$ where $A^{\prime}=A$.

Because $A^{\prime}+\overrightarrow{CB}=(\epsilon+\delta,-1)$, in order for
$C$ to be contained in $\triangle A^{\prime}D^{\prime}E^{\prime}$, $B$ must
lie below line

$y=\frac{1}{1+\epsilon+\delta}(x-\epsilon-\delta)-1$ (3)

Therefore the largest possible $y$-coordinate of $B$ is that of the
intersection point between line 3 and

$y=\frac{2-\epsilon}{\epsilon+\delta}(x-1-\frac{2(\epsilon+\delta)(1-\epsilon)}{2-\epsilon})$
(4)

By straightforward computation, we have that

$y=-\frac{2}{\frac{2-\epsilon}{\epsilon+\delta}+1-\epsilon}$ (5)

is the largest possible $y$-coordinate of $B$. However, the intercept along
line 5 of $\triangle A^{\prime}D^{\prime}E^{\prime}$ equals

$\displaystyle\quad(2-2\epsilon-\frac{2}{\frac{2-\epsilon}{\epsilon+\delta}+1-\epsilon})\times\frac{1+\frac{(\epsilon+\delta)(1-\epsilon)}{2-\epsilon}}{1-\epsilon}$
$\displaystyle=2+\frac{(\epsilon+\delta)(1-\epsilon)}{2-\epsilon}-\frac{2(\epsilon+\delta)}{(1-\epsilon)(2-\epsilon)}$
$\displaystyle=2-\frac{(\epsilon+\delta)(1+2\epsilon-\epsilon^{2})}{(1-\epsilon)(2-\epsilon)}<2$

thus $C,A,B$ can’t be simultaneously covered by any translate of $2T$.

For the choice of constants, any constant pair additionally satisfying
$\epsilon+\delta<\frac{1}{2}$ is feasible.

∎

##  5 Conclusion

In this note, we analyze John’s theorem for simplices with positive dilation
and answer related open questions raised by Leme and Schneider (2020). We
prove a tight $d+2$ upper bound which matches the $d$ lower bound, improving
the previously known $d^{2}$ bound. We also give a simple counter-example
showing that the $d$ lower bound isn’t optimal.

## References

  * Henk (2012) Martin Henk.  löwner-john ellipsoids.  _Documenta Math_ , pages 95–106, 2012.
  * John (2014) Fritz John.  Extremum problems with inequalities as subsidiary conditions.  In _Traces and emergence of nonlinear programming_ , pages 197–215. Springer, 2014.
  * Khachiyan (1995) Leonid Khachiyan.  On the complexity of approximating extremal determinants in matrices.  _Journal of Complexity_ , 11(1):138–153, 1995\.
  * Leme and Schneider (2020) Renato Paes Leme and Jon Schneider.  Costly zero order oracles.  In _Conference on Learning Theory_ , pages 3120–3132. PMLR, 2020\.
  * Nikolov (2015) Aleksandar Nikolov.  Randomized rounding for the largest simplex problem.  In _Proceedings of the forty-seventh annual ACM symposium on Theory of computing_ , pages 861–870, 2015.
  * Summa et al. (2014) Marco Di Summa, Friedrich Eisenbrand, Yuri Faenza, and Carsten Moldenhauer.  On largest volume simplices and sub-determinants.  In _Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms_ , pages 315–323. SIAM, 2014.