Efficient Fairness-Performance Pareto Front Computation

## Abstract

Abstract There is a well known intrinsic trade-off between the fairness of a representation and the performance of classifiers derived from the representation.
Due to the complexity of optimisation algorithms in most modern representation learning approaches, for a given method it may be non-trivial to decide whether the obtained fairness-performance curve of the method is optimal, i.e., whether it is close to the true Pareto front for these quantities for the underlying data distribution. In this paper we propose a new method to compute the optimal Pareto front,
which does not require the training of complex representation models. We show that optimal fair representations possess several useful structural properties, and that these properties enable a reduction of the computation of the Pareto Front to a compact discrete problem. We then also show that these compact approximating problems can be efficiently solved via off-the shelf concave-convex programming methods. Since our approach is independent of the specific model of representations, it may be used as the benchmark to which representation learning algorithms may be compared. We experimentally evaluate the approach on a number of real world benchmark datasets.

## 1 Introduction

Fair representations are a central topic in the field of Fair Machine Learning, Mehrabi et al., (), Pessach and Shmueli, (),Chouldechova and Roth, (). Since their introduction in Zemel et al., (), Fair representations have been extensively studied, giving rise to a variety of approaches based on a wide range of modern machine learning methods, such GANs, variational auto encoders, numerous variants of Optimal Transport methods, and direct variational formulations. See the papers Feldman et al., (), Edwards and Storkey, (),Louizos et al., (),Madras et al., (), Gordaliza et al., (); Zehlike et al., (), Song et al., (), Du et al., (), for a sample of existing methods.

For a given a representation learning problem and a target classification problem, since the fairness constraints reduce the space of feasible classifiers, the best possible classification performance will usually be lower as the fairness constraint becomes stronger. This phenomenon is known as the Fairness-Performance trade-off.
Assume that we have fixed a way to measure fairness. Then for a given representation learning method, one is often interested in the fairness-performance curve $(\gamma,E(\gamma))$. Here, $\gamma$ is the fairness level, and $E(\gamma)$ is the classification performance of the method at that level.
The curve $(\gamma,E(\gamma))$ where $E(\gamma)$ is the best possible performance over all representations and classifiers under the constraint is known as the Fairness-Performance Pareto Front.

As indicated by the above discussion, representation learning methods typically involve models with high dimensional parameter spaces, and complex, possibly constrained non-convex optimisation algorithms.
As such, these methods may be prone to local minima, and may be sensitive to a variety of hyper-parameters, such as architecture details, learning rates, and even initializations. While the representations produced by such methods may often be useful, it nevertheless may be difficult to decide whether
their associated Fairness-Performance curve is close to the true Pareto Front.

In this paper we propose a new method to compute the optimal Pareto front,
which does not require the training of complex fair representation models. In other words, we show that, perhaps somewhat surprisingly, the computation of the Pareto Front can be decoupled from that of the representation, and only relies on learning of much simpler, unconstrained classifiers on the data. To achieve this, we first show that the optimal fair representations satisfy a number of structural properties. While these properties may be of independent interest, here we use them to express the points on the Pareto Front as the solutions of small discrete optimisation problems. The problems fall into the category of *concave minimisation* problems Benson, (), which have been extensively studied, and can be efficiently solved using modern dedicated optimisation frameworks, Shen et al., ().

We now describe the results in more detail. Let $X$ and $A$ denote the data features and the sensitive attribute, respectively. The sensitive attribute is a part of the data, and we assume that $A$ is binary. The features $X$ will be taking values in $\mathbb{R}^{d}$. In addition, we have a *target* variable $Y$, taking values in a finite set $\mathcal{Y}$. That is, we are interested in representations that maximise the performance of prediction of $Y$, under the fairness constraint. The representation is denoted by $Z$, and is typically expressed by constructing the conditional distributions $\mathbb{P}\left(Z|X=x,A=a\right)$, for $a\in\left\{0,1\right\}$. The problem setting is illustrated in Figure 1.

Figure: Figure 1: Fair Representation Problem Setting
Refer to caption: extracted/5881113/figures/fig1a.png

In Section 4 we introduce the invertibility theorem. This result states, informally, that in an *optimal* representation, every point $z$ can be generated from at most two $x$’s, one given $A=0$ and another given $A=1$. That is, there are *unique* $u,v$ such that $\mathbb{P}\left(Z=z|X=u,A=0\right)\neq 0$ and $\mathbb{P}\left(Z=z|X=v,A=1\right)\neq 0$.
This in turn hints at a possibility that in an optimal representation, the space of $z$ may be indexed by the pairs $(u,v)$, where $u,v$ denote $x$’s corresponding to $A=0$ and $A=1$ as above. Indeed, an additional result, the Uniform Approximation Lemma D.1, deferred to Supplementary D due to space constraints, implies that for every pair $(u,v)$, one needs to have only a small number of $z$’s associated with it, in order to approximate all possible representations. Together, these results bound the number of points needed to model *all* optimal representations, if $X$ has finitely many values.

Next, in Section 5.1 we show that instead of discretising $X$ as suggested above, one may in fact discretise a much smaller space, i.e., $\Delta_{\mathcal{Y}}$—the space of all possible distributions of $Y$. As an example, if $Y$ is binary, this space is the interval $[0,1]$.
This reduction is possible due to the *factorisation* property of representations. That is, we show that for the purposes of the computation of the Pareto front, any representation may be represented as a composition (thus the factorisation terminology) of a mapping into $\Delta_{\mathcal{Y}}$, and a representation of $\Delta_{\mathcal{Y}}$.

Based on these results, in Section 5.2 we introduce MIFPO, a discrete optimisation problem for the computation of the Pareto front, and in Section 5.3 we provide details on estimating the problem parameters from the data. The MIFPO problem is a concave minimisation problem with linear constraints, and we solve it using the disciplined convex-concave programming framework, DCCP, Shen et al., (). It is worth noting that for the special case of perfect fairness, i.e., the point $\gamma=0$ on the curve, the MIFPO problem is in fact a *linear* programming problem, solvable by standard means, and closely related to the Optimal Transportation problem.

We illustrate MIFPO by evaluating it on a number of standard real world fairness benchmark datasets. We also compare its fairness-performance curve to that of FNF, , a recent representation learning approach which yields representations with guaranteed fairness constraint satisfaction. As expected, MIFPO produces tighter fairness-performance curves, indicating that FNF still has space for improvement. This suggests that MIFPO may also be used as an analysis method in the construction of full representation learning algorithms.
In a similar fashion, in Supplementary Material Section H, we show that MIFPO may also be used to evaluate the fairness-performance Pareto front of fair *classifiers*, where fairness is measured by statistical parity. We evaluate two widely used fair classification methods and find that their Pareto front is significantly below that of MIFPO.

To summarise, the contributions of this paper are as follows: (a) We derive several new structural properties of optimal fair representations.
(b) We use these properties to construct a model independent problem, MIFPO, which can approximate the Pareto Front of arbitrary high dimensional data distributions, but is much simpler to solve than direct representation learning for such distributions. (c) We illustrate the approach on real world fairness benchmarks.

The rest of this paper is organised as follows: Section 2 discusses the literature. Section 3 introduces the formal problem setting. The Inveribility Theorem is discussed in Section 4, and the details of the MIFPO construction are given in Section 5. Experimental results are presented in Section 6, and we conclude the paper in Section 7. All proofs are provided in the Supplementary Material.

## 2 Literature and Prior Work

As mentioned in the previous Section, there exists a variety of approaches
to the construction of fair representations. We refer to the book Barocas et al., (), and surveys Mehrabi et al., (),Du et al., (), for an overview.
Notably, the work Song et al., () introduces a variational framework that unifies many of the existing methods under a single optimisation procedure. This work also explicitly deals with the difficulty of obtaining useful fairness-performance trade-offs, although such considerations are present in practically all fairness related work.

In a recent paper, , it was observed that if one
knows the density of the source data, $\mathbb{P}\left(X|A=a\right)$, $a\in\left\{0,1\right\}$, and uses models with computable change of variables, such as the normalising flows, Rezende and Mohamed, (), then one can verify the total variation fairness criterion (see (3)), with high probability. This enables one to provide guarantees on the fairness of a representation, which is clearly an important feature in applications. Such guarantees also allow result comparison between different methods. Indeed, if a given constraint is not guaranteed in one of the methods, then the performance comparison may be unfair. Due to this reason, in the experiments Section 6 we compare our own results to those of . It may be worthwhile to note, however, that the assumption of knowing the densities $\mathbb{P}\left(X|A=a\right)$, made in , is quite significant. This is due to the fact that such information is normally not given, and the estimation of densities from data is generally a difficult problem. We remark that our approach does not rely on this assumption.

## 3 Problem Setting

Let $A$ be a binary sensitive variable, and let $X$ be an additional feature random variable, with values in $\mathbb{R}^{d}$. Assume also that there is a target variable $Y$ with finitely many values, jointly distributed with $X,A$.

A representation $Z$ of $(X,A)$ is defined as a random variable taking values in some space $\mathbb{R}^{d^{\prime}}$, with *(i)* distribution given through
$\mathbb{P}_{\theta}\left(Z|X,A\right)$, where $\theta$ are the parameters of the representation, and *(ii)* such that $Z$ is independent of the rest of the variables of the problem conditioned on $(X,A)$. In particular, we have

$$ $Z\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern 2.0mu{ \displaystyle\perp}}}{\mathrel{\hbox to0.0pt{$\textstyle\perp$\hss}\mkern 2.0 mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptstyle\perp$\hss}\mkern 2. 0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptscriptstyle\perp$\hss} \mkern 2.0mu{\scriptscriptstyle\perp}}}Y|(X,A),$ (1) $$

where $\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern 2.0mu{
\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{$\textstyle\perp$\hss}\mkern 2.0
mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptstyle\perp$\hss}\mkern 2.
0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptscriptstyle\perp$\hss}
\mkern 2.0mu{\scriptscriptstyle\perp}}}$ denotes statistical independence.

Fairness in this paper will be measured by the Total Variation distance. For two distributions, $\mu,\nu$ on $\mathbb{R}^{d}$, with densities $f_{\mu},f_{\nu}$, respectively, this distance is defined as

$$ $\left\|\mu-\nu\right\|_{TV}=\frac{1}{2}\sup_{g\text{ s.t. }\left\|g\right\|_{ \infty}\leq 1}\int g(x)\cdot\left[f_{\mu}(x)-f_{\nu}(x)\right]dx=\frac{1}{2} \int\left|f_{\mu}(x)-f_{\nu}(x)\right|dx.$ (2) $$

Note that $\int\left|f_{\mu}(x)-f_{\nu}(x)\right|dx$ is in fact the $L_{1}$ distance, and the equivalence $\left\|\cdot\right\|_{TV}=\frac{1}{2}\left\|\cdot\right\|_{L_{1}}$ is well known, see Cover and Thomas, ().

For $a\in\left\{0,1\right\}$, let $\mu_{a}$ be the distribution of $Z$ given $A=a$, i.e.
$\mu_{a}(\cdot):=\mathbb{P}\left(Z=\cdot|A=a\right)$. For $\gamma\geq 0$, we say that the representation $Z$ is $\gamma$-fair iff

$$ $\left\|\mu_{0}-\mu_{1}\right\|_{TV}\leq\gamma\hskip 5.69054pt\hskip 5.69054pt \hskip 5.69054pt\hskip 5.69054pt\text{(Fairness Condition)}.$ (3) $$

In what follows we will denote the norm of the difference as
$F_{\theta}:=\left\|\mu_{0}-\mu_{1}\right\|_{TV}$.
Note that (3) is a quantitative relaxation of the “perfect fairness” condition in the sense of statistical parity, which requires $Z\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern 2.0mu{
\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{$\textstyle\perp$\hss}\mkern 2.0
mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptstyle\perp$\hss}\mkern 2.
0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptscriptstyle\perp$\hss}
\mkern 2.0mu{\scriptscriptstyle\perp}}}A$. Specifically, observe that by definition, $Z\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern 2.0mu{
\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{$\textstyle\perp$\hss}\mkern 2.0
mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptstyle\perp$\hss}\mkern 2.
0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptscriptstyle\perp$\hss}
\mkern 2.0mu{\scriptscriptstyle\perp}}}A$ iff (3) holds with $\gamma=0$ (i.e. $\mu_{0}=\mu_{1}$). In addition, as shown in Madras et al., (), (3) implies several other common fairness criteria. In particular, (3) implies bounds on demographic parity and equalized odds metrics for any downstream classifier built on top of $Z$.

Next, we describe the measurement of information loss in $Y$ due to the representation. Let $h:\Delta_{\mathcal{Y}}\rightarrow\mathbb{R}$ be a continuous and concave function on the set of probability distributions on $\mathcal{Y}$, $\Delta_{\mathcal{Y}}$.
The quantity $h(\mathbb{P}\left(Y|X=x\right))$ will measure the best possible
prediction accuracy of $Y$ conditioned on $X=x$, for varying $x$.
As an example, consider the case of binary $Y$, $\mathcal{Y}=\left\{0,1\right\}$.
Every point in $\Delta_{\mathcal{Y}}$ can be written as $(p,1-p)$ for $p\in[0,1]$, and we may choose $h$ to be the optimal binary classification error,

$$ $h((1-p,p))=min(p,1-p).$ (4) $$

Another possibility it to use the entropy, $h((1-p,p))=p\log p+(1-p)log(1-p)$. The average uncertainty of $Y$ is given by $\mathbb{E}_{x\sim X}h(\mathbb{P}\left(Y|X=x\right))$. Note that this notion does not depend on a particular classifier, but reflects the performance the *best* classifier can possibly achieve (under appropriate cost).

The goal of fair representation learning is then to find representations $Z$ that for a given $\gamma\geq 0$ satisfy the constraint (3), and under that constraint minimize the objective $E=E_{\theta}$ given by

$$ $E_{\theta}=\mathbb{E}_{z\sim Z}h(\mathbb{P}\left(Y|Z=z\right)).$ (5) $$

That is, the representation should minimise the optimal $Y$ prediction error (using $Z$) under the fairness constraint.

The curve that associates to every $0\leq\gamma\leq 1$ the minimum of (5) over all representations $Z$ which satisfy (3) with $\gamma$ is referred to as the *Pareto Front* of the Fairness-Performance trade-off.

In supplementary material Section A we show that
for any representation, $\mathbb{E}_{z\sim Z}h(\mathbb{P}\left(Y|Z=z\right))\geq\mathbb{E}_{x\sim X}h(
\mathbb{P}\left(Y|X=x\right))$, i.e. representations generally decrease the performance. Technically, this happens due to the concavity of $h$, and this result is an extension of the classical *information processing inequality*, Cover and Thomas, ().
To intuitively see *why* representations decrease performance, note that as illustrated in Figure 1, the distribution $\mathbb{P}\left(Y|Z=z\right)$ is a mixture of various distributions
$\mathbb{P}\left(Y|X=x,A=a\right)$. Thus, for instance, even if all
$\mathbb{P}\left(Y|X=x,A=a\right)$ are deterministic, but not all of the same value,
$\mathbb{P}\left(Y|Z=z\right)$ will not be deterministic.

## 4 The Invertibility Theorem

In this section we define the notion of invertibility for representations, and show that optimal fair representations are invertible.

To this end, let us first introduce an additional notation, which is more convenient when describing representations specifically on finite sets.
Let $S_{0},S_{1}$ be finite disjoint sets, where $S_{a}$ represents the values of $(X,A)$ when $A=a$, for $a\in\left\{0,1\right\}$. Denote $S=S_{0}\cup S_{1}$. We are assuming that there is a probability distribution $\zeta$ on $S$, and $A$ is the random
variable $A=\mathbbm{1}_{\left\{s\in S_{1}\right\}}$.
$X$ is defined as taking the values $s\in S$, with
$\mathbb{P}\left(X=s\right)=\zeta(s)$.
Further, the variable $Y$ is defined to take values in a finite set $\mathcal{Y}$, and for every $s\in S$, its conditional distribution is given by $\rho_{s}\in\Delta_{\mathcal{Y}}$. That is, $\mathbb{P}\left(Y=y|X=s,A=a\right)=\rho_{s}(y)=\rho_{s,a}(y)$. (^2^22Note that there is a slight redundancy in the notation $\mathbb{P}\left(Y=y|X=s,A=a\right)$ here, since $a$ is determined by $s$. However, to retain compatibility with the standard notaion, we specify them both. This is similar to the continuous situation, in which although $A$ is technically part of the features, $X$ and $A$ are specified separately.)
This completes the description of the data model.

For $a\in\left\{0,1\right\}$ we denote $\alpha_{a}=\mathbb{P}\left(A=a\right)=\zeta(S_{a})$, and
$\beta_{a}(s)=\mathbb{P}\left(X=s|A=a\right)$. Observe that $\beta_{a}(s)=0$ if $s\notin S_{a}$, and $\beta_{a}(s)=\zeta(s)/\zeta(S_{a})$ if $s\in S_{a}$.

We now describe the representation.
The representation will take values in a finite set $\mathcal{Z}$.
For every $s\in S$ and $z\in\mathcal{Z}$, let $T_{a}(z,s)=\mathbb{P}\left(Z=z|X=s,A=a\right)$ be the conditional probability of representing $s$ as $z$. Then $T_{a}$’s fully define the distribution of the representation $Z$. We shall refer to the representation as $T$ or $Z$ in interchangeably.
Finally, for $a\in\left\{0,1\right\}$ denote

$$ $\mu_{a}(z)=T_{a}\beta_{a}=\mathbb{P}\left(Z=z|A=a\right)=\sum_{s\in S_{a}} \beta_{a}(s)T_{a}(z,s).$ (6) $$

Similarly to the previous section, our goal is to find representations $T$ that minimise the cost (5) under the constraint (3), for some fixed $\gamma>0$.

A representation $T$ is *invertible* if for every $z\in\mathcal{Z}$ and every $a\in\left\{0,1\right\}$, there is at most one $s\in S_{a}$ such that $T_{a}(z,s)>0$. In words, a representation is invertible, if any given $z$ can be produced by at most two original features $s$, and at most one in each of $S_{0}$ and $S_{1}$.

Given a representation $T$ and $z\in\mathcal{Z}$, we say that an $s\in S$ is a
*parent* of $z$ if $T_{a}(z,s)>0$ for the appropriate $a$.

###### Theorem 4.1 .

Let $T$ be any representation of $(S,A,\zeta,Y)$ on a set $\mathcal{Z}$. Then there exists an invertible representation $T^{\prime}$ of $(S,A,\zeta,Y)$, on some set $\mathcal{Z}^{\prime}$, such that

$$ $\mathbb{E}_{z^{\prime}\sim Z^{\prime}}h(\mathbb{P}\left(Y|Z^{\prime}=z^{\prime }\right))\leq\mathbb{E}_{z\sim Z}h(\mathbb{P}\left(Y|Z=z\right))\text{ and } \left\|\mu^{\prime}_{0}-\mu^{\prime}_{1}\right\|_{TV}=\left\|\mu_{0}-\mu_{1} \right\|_{TV}.$ (7) $$

Here, similarly to $\mu_{a}$, $\mu^{\prime}_{a}$ are the distributions induced by $T^{\prime}$ on $\mathcal{Z}^{\prime}$. In words, for every representation, we can find an invertible representation of the same data which satisfies at least as good a fairness constraint, and has at least as good performance as the original. In particular, this implies that when one searches for optimal performance representations, it suffices to only search among the invertible ones.

The proof proceeds by observing that if an atom $z\in\mathcal{Z}$ has more than one parent on the same side (i.e. $S_{0}$ or $S_{1}$), then one can split this atom into two, with each having less parents. However, the details of this construction are somewhat intricate. The full argument can be found in Section C.

###### Theorem 4.1 .

## 5 The Model Independent Optimization Problem

This Section describes the specific numerical problem, MIFPO, that is used to compute the Fairness-Performance Pareto Front.
Section 5.1 discusses the factorisation of representations, in Section 5.2 the MIFPO problem is defined, and in Section 5.3 we describe how MIFPO is instantiated from data.

To motivate MIFPO, let us write again some of the terms involved in the expressions of the performance cost and the fairness constraints
$E$ and $F$, as defined in Section 3. To simplify the exposition, we use the discrete summation notation, but similar expressions can also be written using integration and densities. We have

$$ $\mathbb{P}\left(z\right)=\sum_{x,a}\mathbb{P}\left(z|x,a\right)\mathbb{P}\left (x,a\right)\text{ and }\mathbb{P}\left(z|a\right)=\sum_{x}\mathbb{P}\left(z|a, x\right)\mathbb{P}\left(x,a\right)/\mathbb{P}\left(a\right).$ (8) $$

Moreover,

$$ $\displaystyle\mathbb{P}\left(Y|z\right)=\sum_{x,a}\mathbb{P}\left(Y|x,a,z \right)\mathbb{P}\left(a,x|z\right)=\sum_{x,a}\mathbb{P}\left(Y|x,a\right) \mathbb{P}\left(z|a,x\right)\mathbb{P}\left(a,x\right)/\mathbb{P}\left(z\right),$ (9) $$

where we have used $\mathbb{P}\left(Y|x,a,z\right)=\mathbb{P}\left(Y|x,a\right)$, which holds due to the independence condition (1) of the representation.
We observe that one can write the performance cost and the fairness constraint, $E$ and $F$, in terms of
$\mathbb{P}\left(a\right),\mathbb{P}\left(x,a\right),\mathbb{P}\left(Y|x,a\right)$, and of the representation $\mathbb{P}\left(z|x,a\right)$. We refer to these quantities as the *basic probabilities*. It follows that *any two problems having the same basic probabilities, will have the same $E$ and $F$*.

One way to view the construction of the MIPFO problem is simply as a discretization, where we model the above basic probabilities in an abstract way, on a finite set, without the need to consider the details of how the representation $\mathbb{P}\left(z|x,a\right)$ is implemented.
However, discretization of the features $x\in\mathbb{R}^{d}$ directly would likely always be too crude. In the following Section we show that in fact one only needs to discretize a much smaller space, namely
$\Delta_{\mathcal{Y}}$ - the set of distributions over $Y$ values, which is typically easy to achieve. In Section 5.3 we show how factorisation is used in practice.

Figure: Figure 2: (a) The MIFPO Setting (b) Factorisation Through $\Delta_{\mathcal{Y}}$
Refer to caption: extracted/5881113/figures/fig2b.png

### 5.1 Factorisation

The general idea behind factorisation is the observation that in a given representation, individual source points $x,x^{\prime}$ may be merged if they have the same $\rho_{x}=\mathbb{P}\left(Y|x\right)$ distribution, without affecting the measurements $E$ and $F$. We now carry out this argument formally, with Figure 2(b) illustrating the construction.
For clarity, we use the notation of Section 4 for finite sets. The extension to the continuous case is discussed in the end of the Section.

Suppose that we have a representation on some, possibly very large source space $S=S_{0}\cup S_{1}$, with representation space $\mathcal{Z}$. Introduce a map $\Psi:S_{0}\rightarrow\Delta_{\mathcal{Y}}$, given by $\Psi(v)=\rho_{v}$. Then we can define a distribution $\bar{\beta}_{0}$ on $\Delta_{\mathcal{Y}}$, and the transition kernel $\bar{T}_{0}:\mathcal{Z}\times\Delta_{\mathcal{Y}}\rightarrow[0,1]$ by

$$ $\bar{\beta}_{0}(\rho)=\sum_{v\in\Psi^{-1}(\left\{\rho\right\})}\beta_{0}(v) \hskip 5.69054pt\text{ and }\bar{T}_{0}(z,\rho)=\sum_{v\in\Psi^{-1}(\left\{ \rho\right\})}\frac{\beta_{0}(v)}{\bar{\beta}_{0}(\rho)}T_{0}(z,v),\text{ for all $\rho\in\Delta_{\mathcal{Y}}$}.$ (10) $$

Similar construction can be made for $a=1$, defining $\bar{\beta}_{1}$,
$\bar{T}_{1}$. Observe that together, $\bar{\beta}_{a}$ and $\bar{T}_{a}$ define a representation on $\Delta_{\mathcal{Y}}$ with values in $\mathcal{Z}$ (technically, the source space is $\Delta_{\mathcal{Y}}^{0}\cup\Delta_{\mathcal{Y}}^{1}$, where $\Delta_{\mathcal{Y}}^{a}$ are two disjoint copies
of $\Delta_{\mathcal{Y}}$). Note that it is understood here that the distribution of $Y$ at point $\rho\in\Delta_{\mathcal{Y}}$ is taken to be $\rho$ itself.
The crucial property of this new representation is that
the induced distributions on $\mathcal{Z}$ coincide with those of the old one. That is,

$$ $\mu_{a}(z)=\bar{\mu_{a}}(z)\text{ and }\mathbb{P}_{T}\left(Y|Z=z\right)= \mathbb{P}_{\bar{T}}\left(Y|Z=z\right)$ (11) $$

for all $z\in\mathcal{Z}$. This property follows simply by substituting the definitions, although the derivation is slightly notationally heavy. The full details may be found in Supplementary Section F.2.

The meaning of (11) is that from $\mathcal{Z}$ one can not distinguish between the representations $T$ and $\bar{T}$, and in particular they have the same $E$ and $F$. We say that $T$ is *factorised* through $\Delta_{\mathcal{Y}}$ since it can be represented as a composition, of first applying $\Psi$ and then applying $\bar{T}$.

When the feature space $S$ is continuous, e.x. $\mathbb{R}^{d}$, the construction of $\bar{T}$ is similar. Indeed, $\Psi$ can be defined in the same way, $\bar{\beta}_{a}$ are defined as push-forwards $\bar{\beta}_{a}=\Psi\beta_{a}$, and $\bar{T}_{a}(z,\rho)$ is defined as conditional expectation, $\bar{T}_{a}(z,\rho)=\mathbb{E}_{v\sim\beta_{0}}T_{a}(z,v)|\left(\Psi(v)=\rho\right)$.

### 5.2 MIFPO Definition

Fix an integer $k\geq 2$. The representation space $\mathcal{Z}$ will
be a finite set which can be written as $\mathcal{Z}=S_{0}\times S_{1}\times[k]$,
where $[k]:=\left\{1,2,\ldots,k\right\}$.
That is, every point $z\in\mathcal{Z}$ corresponds to some triplet $(u,v,j)$, with $u\in S_{0},v\in S_{1},j\in[k]$.
The motivation for this choice of $\mathcal{Z}$ is as follows: First, note the by the invertibility Theorem 4.1, in an optimal representation, every $z\in\mathcal{Z}$ is associated with a pair of parents, $(u,v)$. Moreover, it can be shown that for every pair $(u,v)$, it is sufficient to have at most $k$ points $z$ which have $(u,v)$ as parents, to approximate *all* representations on *all* possible spaces $\mathcal{Z}^{\prime}$, in terms of their $E$ and $F$ quantities, to a given degree $\varepsilon$. Here, $k$ would depend on $\varepsilon$ and on the function $h$, but not on the particular representations, or even the sizes $\left|S_{0}\right|,\left|S_{1}\right|$, etc.
See Section D in Supplementary Material, for additional details. As a result, choosing $\mathcal{Z}=S_{0}\times S_{1}\times[k]$ should be sufficient to model all representations well. We have used $k=10$ in all experiments.

Next, the variables of the problem, modeling the representation itself, will be denoted by $r_{u,v,j}$ and $r_{v,u,j}$, for $(u,v,j)\in\mathcal{Z}$.
These values correspond to the probabilities $r_{u,v,j}=\mathbb{P}\left(Z=(u,v,j)|(X,A)=(u,0)\right)$ and
$r_{v,u,j}=\mathbb{P}\left(Z=(u,v,j)|(X,A)=(v,1)\right)$. Note that the order of $u,v$ in $r_{u,v,j}$ and $r_{v,u,j}$ determines whether the weight is transferred from $S_{0}$ or $S_{1}$.
The values $r$ correspond to the values of $T_{0}(z,u),T_{1}(z,v)$ in Section 4. However, note that due to the special structure of the representation here, many values will be 0 0, such as for instance $T_{0}((u,v,j),u^{\prime})$, whenever $u\neq u^{\prime}$. The $r$ notation accounts for this, and is thus clearer. The whole setup is illustrated in Figure 2(a).

Note that the variables represent probabilities, and thus satisfy the following constraints:

$$ $\displaystyle r_{u,v,j}\geq 0,\hskip 5.69054ptr_{v,u,j}\geq 0\hskip 5.69054pt \forall(u,v,j)\in\mathcal{Z}$ (12) $\displaystyle\sum_{v\in S_{1},j\in[k]}r_{u,v,j}=1\hskip 5.69054pt\forall u\in S _{0}\text{ and }\sum_{u\in S_{0},j\in[k]}r_{v,u,j}=1\hskip 5.69054pt\forall v \in S_{1}.$ (13) $$

Recall from Section 4 that the additional parameters of the problem are the conditional distributions $\beta_{0}(u),\beta_{1}(v)$, on $S_{0}$ and $S_{1}$, modeling $\mathbb{P}\left((X,A)|A=0\right)$ and
$\mathbb{P}\left((X,A)|A=1\right)$ respectively. The quantities $\alpha_{a}=\mathbb{P}\left(A=a\right)$, and the conditional $Y$ distributions,
$\rho_{u},\rho_{v}\in\Delta_{\mathcal{Y}}$, modelling $\rho_{u}=\mathbb{P}\left(Y=\cdot|(X,A)=(u,0)\right)$, $\rho_{v}=\mathbb{P}\left(Y=\cdot|(X,A)=(v,1)\right)$.
Here we assume that these quantities are given, and in Section 5.3 below we describe how one may estimate them from the data.

With these preparations, we are ready to write the performance cost
(5) in the new notation:

$$ $E_{r}=\sum_{z=(u,v,j)}\left(\alpha_{0}\beta_{0}(u)r_{u,v,j}+\alpha_{1}\beta_{1 }(v)r_{v,u,j}\right)h\left(\frac{\rho_{u}\alpha_{0}\beta_{0}(u)r_{u,v,j}+\rho_ {v}\alpha_{1}\beta_{1}(v)r_{v,u,j}}{\alpha_{0}\beta_{0}(u)r_{u,v,j}+\alpha_{1} \beta_{1}(v)r_{v,u,j}}\right).$ (14) $$

Indeed, observe that due to the structure of our representations, every
$z$ has two parents, and we have $\mathbb{P}\left(Z=z\right)=\left(\alpha_{0}\beta_{0}(u)r_{u,v,j}+\alpha_{1}
\beta_{1}(v)r_{v,u,j}\right)$. Similarly, $\mathbb{P}\left(Y|Z=z\right)$ is computed via (9) and substituted inside $h$ to obtain (14). As we show in Supplementary E, the cost (14) is a *concave* function of the parameters $r$.

We now proceed to discuss the fairness constraint $F$. Recall that we define $\mu_{a}(z)=\mathbb{P}\left(Z=z|A=a\right)$, for $a\in\left\{0,1\right\}$. For $z=(u,v,j)$ we have then $\mu_{0}((u,v,j))=\beta_{0}(u)r_{u,v,j}$ and
$\mu_{1}((u,v,j))=\beta_{1}(v)r_{v,u,j}$. We thus can write

$$ $F_{r}=\left\|\mu_{0}-\mu_{1}\right\|_{TV}=\frac{1}{2}\sum_{z}\left|\mu_{0}(z)- \mu_{1}(z)\right|=\frac{1}{2}\sum_{(u,v,j)}\left|\beta_{0}(u)r_{u,v,j}-\beta_{ 1}(v)r_{v,u,j}\right|$ (15) $$

and the Fairness constraint, for a given $\gamma\in[0,1]$ is simply

$$ $F_{r}\leq\gamma.$ (16) $$

Although the constraint (16) is convex in the variables $r$, and can be incorporated directly into most optimisation frameworks, it may be significantly more convenient to work with *equality* constraints. Using the following Lemma, we can find equivalent equality constraints in a particularly simple form.

###### Lemma 5.1 .

Let $\mu_{0},\mu_{1}\in\Delta_{\mathcal{Z}}$ be two probability distributions over $\mathcal{Z}$ and fix some $\gamma\geq 0$. If $\left\|\mu_{0}-\mu_{1}\right\|_{TV}=\gamma$ then there exist $\phi_{0},\phi_{1}\in\Delta_{\mathcal{Z}}$ such that $\mu_{0}+\gamma\phi_{0}=\mu_{1}+\gamma\phi_{1}$. In the other direction, if there exist
$\phi_{0},\phi_{1}\in\Delta_{\mathcal{Z}}$ such that $\mu_{0}+\gamma\phi_{0}=\mu_{1}+\gamma\phi_{1}$, then $\left\|\mu_{0}-\mu_{1}\right\|_{TV}\leq\gamma$.

As consequence, if we find distributions
$\phi_{0},\phi_{1}\in\Delta_{\mathcal{Z}}$ such that $\mu_{0}+\gamma\phi_{0}=\mu_{1}+\gamma\phi_{1}$ holds, then we know that (16) also holds, and conversely, if (16) holds, then distributions as above exist.

Using this observation, we introduce new variables, $\phi_{u,v,j}$ and $\phi_{v,u,z}$, for every $(u,v,j)\in\mathcal{Z}$, which correspond to
$\phi_{0}((u,v,j))$ and $\phi_{1}((u,v,j))$ respectively.
These variables will be required to satisfy the following constraints:

$$ $\displaystyle r_{u,v,j}\geq 0,\hskip 5.69054ptr_{v,u,j}\geq 0\hskip 5.69054pt \forall(u,v,j)\in\mathcal{Z}$ (17) $\displaystyle\sum_{u,v,j}r_{u,v,j}=1\text{ and }\sum_{u,v,j}r_{v,u,j}=1$ (18) $\displaystyle\beta_{0}(u)r_{u,v,j}+\gamma\phi_{u,v,j}=\beta_{1}(v)r_{v,u,j}+ \gamma\phi_{v,u,j}\hskip 5.69054pt\forall(u,v,j)\in\mathcal{Z}.$ (19) $$

Here the first two lines encode the fact that $\phi_{0},\phi_{1}$ are probabilities, while the third line encodes the fairness constraint, as discussed above.

We now summarise the full MIFPO problem.

###### Definition 5.1 (MIFPO) .

For a fixed finite ground set $S=S_{0}\cup S_{1}$,
the problem parameters are the weight $\alpha_{0}$, the distributions
$\beta_{0},\beta_{1}$, on $S_{0}$ and $S_{1}$ respectively, and the distributions
$\rho_{x}\in\Delta_{\mathcal{Y}}$ for every $x\in S$.
The problem variables are
$\left\{r_{u,v,j},r_{v,u,j},\phi_{u,v,j},\phi_{v,u,j}\right\}_{(u,v,j)\in
\mathcal{Z}}$ as defined above. We are interested in minimising the concave function (14), subject to the constraints (12)-(13) and (17)-(19).

The relationship between MIFPO and the Optimal Transport problem is detailed in Section B.

###### Lemma 5.1 .

###### Definition 5.1 (MIFPO) .

### 5.3 Constructing a MIFPO Instance

In this Section we discuss the estimation of the quantities $\alpha$,$\beta$ and $\rho$ from the data, and specify how the data is used to construct the MIFPO problem instance.

For clarity we treat the case of binary $Y$, which is also the case for all datasets in , on which we base our experiments. Note that for binary $Y$, $\Delta_{\mathcal{Y}}$ is simply the interval $[0,1]$, with $p\in[0,1]$ corresponding to the probability $p=\mathbb{P}\left(Y=1|x,a\right)$.

The computation proceeds in 3 steps, schematically shown as Algorithm 1.
The input is a labeled dataset $\left\{(x_{i},a_{i},y_{i})\right\}_{i\leq N}$, with $x_{i}\in\mathbb{R}^{d}$, $a_{i},y_{i}\in\left\{0,1\right\}$, and two integers, $L,k$, which will specify the approximation degrees for the discretisation and for the approximation space, respectively. In Step 1., separately for the parts of the data corresponding to $A=0$ and $A=1$, we learn *calibrated* classifiers $c_{0},c_{1}:\mathbb{R}^{d}\rightarrow[0,1]$, which represent the probabilities $c_{a}(x)=\mathbb{P}\left(Y=1|X=x,A=a\right)=\rho_{a}(x)$. Note the following points: (a) In most applications, the true values of $\mathbb{P}\left(Y=1|X=x,A=a\right)$ are non-binary (i.e. $\neq 0,1$), and thus the $\left\{0,1\right\}$-valued labels are only noisy observations of the actual probabilities. Thus, some sort of estimator must be used to learn the probabilities. (b) Typical classification objectives tend to yield in an imprecise estimation of $\mathbb{P}\left(Y=1|X=x,A=a\right)$. However, this can usually be fixed by the process of calibration in post-processing, see Niculescu-Mizil and Caruana, (), Kumar et al., (),
(Berta et al.,, ).
In Step 2. we define the sets $H_{a}=\left\{c_{a}(x)\hskip 5.69054pt|\hskip 5.69054ptx\in X_{a}\right\}
\subset[0,1]$, and approximate them by histograms with $L$ bins. That is, for each $a$, we find $L$ points $\rho_{a}^{1},\ldots,\rho_{a}^{L}\in[0,1]$, and weights $\beta_{a}^{1},\ldots,\beta_{a}^{L}$, such that the distribution
with centers $\rho_{a}^{i}$ and weights $\beta_{a}^{i}$ approximates $H_{a}$ well.
We typically take uniform bins, i.e. simply $\rho_{a}^{l}=\frac{l-1}{L-1}$, for $l=1,\ldots,L$. See Figure 3(b) for an example
of such histograms on real data. Finally,
in Step 3. we solve the MIFPO problem, as given in
Definition 5.1. The ground set here
is $S=S_{0}\cup S_{1}$, with $S_{0}=\left\{1,\ldots,L\right\}$ and $S_{1}=\left\{1^{\prime},\ldots,L^{\prime}\right\}$, where we have added ^′ in $S_{1}$ to signify that the sets are disjoint copies in $S$, and $\left|S\right|=2L$. The problem parameters are
$\alpha_{a}^{l},\beta_{a}^{l},\rho_{a}^{l}$, as computed in the previous step,
and the parameter $k$ determining the size of $\mathcal{Z}$.

## 6 Experiments

Figure: Figure 3: (a) Fairness-Performance Curves of MIFPO and FNF (b) Histograms $H_{a}$ for the Datasets
Refer to caption: extracted/5881113/figures/Exp_figure.png

This section describes the evaluation of the MIFPO approach on real data.
As indicated in Algorithm 1, two main components are required to apply our methods: building a calibrated classifier necessary for evaluating $c_{a}$ , and solving the discrete optimization problem described in Section 5.2.

For the calibrated classifier, we have used a standard
XGBoost (Chen et al.,, ), with Isotonic Regression calibration, as
implemented in sklearn, Pedregosa et al., (). As discussed in Sections 1, 5.2, MIFPO is a concave minimisation problem, under linear constraints. While such problems do not necessarily posses the favourable properties of concave *maximisation* (or convex minimisation), such as unique minima points, it is nevertheless possible to take advantage of concavity, to improve on general purpose optimisation methods. Here, we have used the DCCP framework and the associated solver, (Shen et al.,, , ). This framework is based in the combination
of convex-concave programming ideas (CCP) Lipp and Boyd, () and disciplined convex programming,
Grant et al., ().
Throughout the experiments, we use the missclassification error loss $h$, given by (4). Additional implementation details may be found in Supplementary Section G.

Figure: Algorithm 1 MIFPO Implementation

We have computed the MIFPO Pareto front for 3 real datasets, the "Health", "Crime" and "Law" datasets. These datasets are standard benchmarks in Fairness related work and were also used in . The results are shown in Figure 3(a), dotted lines. As a point of reference, we have also run FNF, , shown as solid lines.

In Figure 3(b) the histograms $H_{a}$ (see Section 5.3) are presented for the three datasets. Observe that as expected, when the histograms of $A=0$ and $A=1$ classes look similar, as in "Law" (indicating approximately $Y\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern 2.0mu{
\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{$\textstyle\perp$\hss}\mkern 2.0
mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptstyle\perp$\hss}\mkern 2.
0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptscriptstyle\perp$\hss}
\mkern 2.0mu{\scriptscriptstyle\perp}}}A$, fair $Y$), the Pareto front is flat. Otherwise, the front exhibits variability, as in "Health" and "Crime".

As indicated in Figure 3(a), FNF struggles to obtain the full range of values $\gamma$ in its fairness-performance curve, and for the values that are obtained, the errors are higher than the optimum.
This highlights the difficulties with the construction of fair representations, which were circumvented in this paper.

## 7 Conclusion And Future Work

In this paper we have uncovered new fundamental properties of optimal fair representations, and used these properties to develop a model independent procedure for the computation of Fairness-Performance Pareto front from data. We have also demonstrated the procedure on real datasets, and have shown that it may be used as a benchmark for representation learning algorithms.

We now discuss a few possible directions for future work.
Perhaps the most obvious is the extension of the optimisation algorithms used to solve the MIFPO problem.
While DCCP’s performance is satisfactory, it does not guarantee a global minimum, which would be desirable for guaranteeing a Pareto front. As mentioned earlier, methods with global minimum guarantees exist,see Benson, (), but would require problem specific adjustments.

Next, perhaps the biggest limitation of the current approach is the need to discretise the $\Delta_{\mathcal{Y}}$. This means that the $Y$ can only take a small number of values, which, for instance, prevents us from considering multiple target variables, i.e. $Y=(Y_{1},\ldots,Y_{t})$. It is thus of interest to ask whether it is possible to obtain a continuous version of our method, which would not discretise $\Delta_{\mathcal{Y}}$. Note that this would still be different from the current continuous methods, since it would operate in a different space, that of $\Delta_{\mathcal{Y}}$, which could still be significantly smaller than $\mathbb{R}^{d}$.

Finally, as noted earlier, representation learning methods solve an inherently harder problem than MIFPO, since such methods need to supply the actual representation, while MIFPO does not. It then would be of interest to understand whether one can use the partial information provided by MIFPO, to guide and improve a full representation learning algorithm.

## Acknowledgement

This research was supported by European Union’s Horizon Europe
research and innovation programme under grant agreement
No. GA 101070568 (Human-compatible AI with guarantees).

## Supplementary Material

[sections]
\printcontents[sections]l1

## Appendix A Monotonicity of Loss Under Representations

As discussed in Section 3, we observe that representations can not increase the performance of the classifier (i.e decrease the loss).

###### Lemma A.1 .

For every $(Y,X,A)$, every representation $Z$ as above, and concave $h$,

$$ $\mathbb{E}_{z\sim Z}h(\mathbb{P}\left(Y|Z=z\right))\geq\mathbb{E}_{(x,a)\sim(X ,A)}h(\mathbb{P}\left(Y|X=x,A=a\right)).$ (20) $$

Note that the right hand-side above can be considered a “trivial" representation, $Z=(X,A)$.

In what follows, to simplify the notation we use expressions of the
form $\mathbb{P}\left(x,a|z\right)$ to denote the formal expressions $\mathbb{P}\left(X=x,A=a|Z=z\right)$, whenever the precise interpretation is clear from context.

###### Proof.

For every value $y\in\mathcal{Y}$, we have

$$ $\displaystyle\mathbb{P}\left(Y=y|Z=z\right)$ $\displaystyle=\sum_{a}\int dx\hskip 5.69054pt\mathbb{P}\left(Y=y|x,a,z\right) \frac{\partial\mathbb{P}\left(x|a,z\right)}{\partial x}\mathbb{P}\left(a|z\right)$ (21) $\displaystyle=\sum_{a}\int dx\hskip 5.69054pt\mathbb{P}\left(Y=y|x,a\right) \frac{\partial\mathbb{P}\left(x|a,z\right)}{\partial x}\mathbb{P}\left(a|z\right)$ (22) $\displaystyle=\mathbb{E}_{(x,a)\sim(X,A)|Z=z}\mathbb{P}\left(Y=y|x,a\right).$ (23) $$

Here, on line (21), $\frac{\partial\mathbb{P}\left(x|a,z\right)}{\partial x}$ is the density of $\mathbb{P}\left(x|a,z\right)$ with respect to $dx$.
Crucially, the transition from (21) to (22) is using the property (1).
The transition (22) to (23) is a change of notation.
Using (23) and the concavity of $h$, we obtain

$$ $\displaystyle\mathbb{E}_{z\sim Z}h(\mathbb{P}\left(Y|Z=z\right))$ $\displaystyle\geq\mathbb{E}_{z\sim Z}\mathbb{E}_{(x,a)\sim(X,A)|Z=z}h\left( \mathbb{P}\left(Y|x,a\right)\right)$ (24) $\displaystyle=\mathbb{E}_{(x,a)\sim(X,A)}h(\mathbb{P}\left(Y|X=x,A=a\right)).$ (25) $$

∎

###### Lemma A.1 .

###### Proof.

## Appendix B MIFPO and Optimal Transport

In this Section we discuss the relation between the MIFPO minimisation problem, Definition 5.1, and the problem of Optimal Transport (OT). General background on OT may be found in Peyré et al., ().
We discuss the similarity between OT and the minimisation of (14) under the constraint (16) with $\gamma=0$, i.e. the perfectly fair case.
In this case, (16) is equivalent to the condition $\beta_{0}(u)r_{u,v,j}=\beta_{1}(v)r_{v,u,j}$,
for all $(u,v,j)\in\mathcal{Z}$. Next, note that thus in is case the
expression for $\mathbb{P}\left(Y|Z=(u,v,j)\right)$ is

$$ $\frac{\rho_{u}\alpha_{0}\beta_{0}(u)r_{u,v,j}+\rho_{v}\alpha_{1}\beta_{1}(v)r_ {v,u,j}}{\alpha_{0}\beta_{0}(u)r_{u,v,j}+\alpha_{1}\beta_{1}(v)r_{v,u,j}}= \frac{\rho_{u}\alpha_{0}+\rho_{v}\alpha_{1}}{\alpha_{0}+\alpha_{1}},$ (26) $$

and *this is independent* of the variables $r$! Therefore we can write
the cost (14) as

$$ $\sum_{u,v}(\alpha_{0}+\alpha_{1})h\left(\frac{\rho_{u}\alpha_{0}+\rho_{v} \alpha_{1}}{\alpha_{0}+\alpha_{1}}\right)\frac{1}{2}\left[\sum_{j\leq k}\beta_ {0}(u)r_{u,v,j}+\beta_{1}(v)r_{v,u,j}\right].$ (27) $$

Note further that for fixed $u,v$, the different $j$’s in this expression play similar roles and could be effectively merged as a single point.

The cost (27) has several similarities with OT. First, in both problems we have
two sides, $S_{0}$ and $S_{1}$, and we have a certain fixed loss associated with "matching" $u$ and $v$. In case of (27), this loss is $(\alpha_{0}+\alpha_{1})h\left(\frac{\rho_{u}\alpha_{0}+\rho_{v}\alpha_{1}}{
\alpha_{0}+\alpha_{1}}\right)$, which describes the information loss
incurred by colliding $u$ and $v$ in the representation.
And second, similarly to OT, (27) it is *linear* in the variables $r$. Linear programs are conceptually considerably simpler than minimisation of the concave objective (14).

## Appendix C Proof Of Theorem 4.1

###### Proof.

Assume $T$ is not invertible. Then there is a $z\in\mathcal{Z}$ which has at least two parents in either $S_{0}$ or $S_{1}$. Assume without loss of generality that $z$ has two parents in $S_{0}$.
Let

$$ $U=\left\{s\in S_{0}\hskip 5.69054pt|\hskip 5.69054ptT_{0}(z,s)>0\right\}, \hskip 5.69054ptV=\left\{s\in S_{1}\hskip 5.69054pt|\hskip 5.69054ptT_{1}(z,s) >0\right\}$ (28) $$

be the sets of parents of $z$ in $S_{0}$ and $S_{1}$ respectively.
Chose a point $x\in U$, and denote by $U^{r}=U\setminus\left\{x\right\}$ the remainder of $U$. By assumption we have $\left|U^{r}\right|\geq 1$.
We also assume that $\left|V\right|>0$. The easier case $\left|V\right|=0$ will be discussed later.

Now, we construct a new representation, $T^{\prime}$. The range of $T^{\prime}$ will be $\mathcal{Z}^{\prime}=\mathcal{Z}\setminus{z}\cup\left\{z^{\prime},z^{\prime
\prime}\right\}$. That is, we remove $z$ and add two new points.
Denote

$$ $\kappa=\mathbb{P}\left(x|z,a=0\right)=\frac{\beta_{0}(x)T_{0}(z,x)}{\sum_{s\in U }\beta_{0}(s)T_{0}(z,s)}.$ (29) $$

Then $T^{\prime}$ is defined as follows:

$$ $\begin{cases}T^{\prime}_{a}(h,s)=T_{a}(h,s)&\text{for all $a\in\left\{0,1 \right\}$, all $s\in S$ and all $h\in\mathcal{Z}\setminus\left\{z\right\}$ }\\ T^{\prime}_{0}(z^{\prime},x)=T_{0}(z,x)&\\ T^{\prime}_{0}(z^{\prime\prime},u)=T_{0}(z,u)&\text{ for all $u\in U^{r}$}\\ T^{\prime}_{1}(z^{\prime},v)=\kappa T_{1}(z,v)&\text{ for all $v\in V$}\\ T^{\prime}_{1}(z^{\prime\prime},v)=(1-\kappa)T_{1}(z,v)&\text{ for all $v\in V $}.\end{cases}$ (30) $$

All values of $T^{\prime}$ that were not explicitly defined in (30) are set to 0 0. In words, on the side of $S_{0}$, we move all the parents of $z$ except $x$ to be the parents of $z^{\prime\prime}$, while $z^{\prime}$ will have a single parent, $x$. On the $S_{1}$ side, both $z^{\prime}$ and $z^{\prime\prime}$ will have the same parents as $z$, with transitions multiplied by $\kappa$ and $1-\kappa$ respectively. The multiplication by $\kappa$ is crucial for showing both inequlaities in (7).

Note that $T^{\prime}$ can be though of as splitting $z$ into $z^{\prime}$ and $z^{\prime\prime}$, such that $z^{\prime}$ has one parent on the $S_{0}$ side, and $z^{\prime\prime}$ has strictly less parents than $z$ had. Once we show that $T^{\prime}$ satisfies (7), it is clear that by induction we can continue splitting $T^{\prime}$ until we arrive at an invertible representation which can no longer be split, thus proving the Lemma.

In order to show (7) for $T^{\prime}$, we will sequentially show the following claims:

$$ $\displaystyle\mathbb{P}\left(z\right)=\mathbb{P}\left(z^{\prime}\right)+ \mathbb{P}\left(z^{\prime\prime}\right)\text{ and }\mathbb{P}\left(z^{\prime} \right)=\kappa\mathbb{P}\left(z\right)$ (31) $\displaystyle\mathbb{P}\left(a|z\right)=\mathbb{P}\left(a|z^{\prime}\right)= \mathbb{P}\left(a|z^{\prime\prime}\right)\text{ for $a\in\left\{0,1\right\}$}$ (32) $\displaystyle\begin{cases}\text{ for $a=1$}&\mathbb{P}\left(s|z,a\right)= \mathbb{P}\left(s|z^{\prime},a\right)=\mathbb{P}\left(s|z^{\prime\prime},a \right)\hskip 5.69054pt\forall s\in S\\ \text{ for $a=0$, $s\in U^{r}$}&\begin{cases}\mathbb{P}\left(x|z^{\prime},a \right)=1&\mathbb{P}\left(x|z^{\prime\prime},a\right)=0\\ \mathbb{P}\left(s|z^{\prime},a\right)=0&\mathbb{P}\left(s|z^{\prime\prime},a \right)=(1-\kappa)^{-1}\mathbb{P}\left(s|z,a\right)\end{cases}\end{cases}$ (33) $\displaystyle\mathbb{P}\left(Y|z\right)=\kappa\mathbb{P}\left(Y|z^{\prime} \right)+(1-\kappa)\mathbb{P}\left(Y|z^{\prime\prime}\right)$ (34) $\displaystyle\mathbb{P}\left(z\right)h(\mathbb{P}\left(Y|z\right))\geq\mathbb{ P}\left(z^{\prime}\right)h(\mathbb{P}\left(Y|z^{\prime}\right))+\mathbb{P} \left(z^{\prime\prime}\right)h(\mathbb{P}\left(Y|z^{\prime\prime}\right))$ (35) $\displaystyle\left|\mu_{0}(z)-\mu_{1}(z)\right|=\left|\mu^{\prime}_{0}(z^{ \prime})-\mu^{\prime}_{1}(z^{\prime})\right|+\left|\mu^{\prime}_{0}(z^{\prime \prime})-\mu^{\prime}_{1}(z^{\prime\prime})\right|.$ (36) $$

Here the probabilities involving $z^{\prime},z^{\prime\prime}$ refer to the representation $T^{\prime}$.
Observe that the left hand side of (35) is the contribution of $z$ to the performance cost $\mathbb{E}_{t\sim Z}h(\mathbb{P}\left(Y|Z=t\right))$ of $T$, while the right hand side of (35) is the contribution of $z^{\prime},z^{\prime\prime}$ to the performance cost of $T^{\prime}$. Since all other elements $t\in\mathcal{Z}$ have identical contributions, this shows the first inequality in (7).
Similarly,
recall that

$$ $\left\|\mu_{0}-\mu_{1}\right\|_{TV}=\frac{1}{2}\sum_{t\in\mathcal{Z}}\left|\mu _{0}(t)-\mu_{1}(t)\right|,$ (37) $$

and thus the left hand side of (36) is the contribution of $z$ to $\left\|\mu_{0}-\mu_{1}\right\|_{TV}$, with the right hand side being the contribution of $z^{\prime},z^{\prime\prime}$ to $\left\|\mu^{\prime}_{0}-\mu^{\prime}_{1}\right\|_{TV}$, therefore yielding the claim $\left\|\mu^{\prime}_{0}-\mu^{\prime}_{1}\right\|_{TV}=\left\|\mu_{0}-\mu_{1}
\right\|_{TV}$.

Claim (31): By definition,

$$ $\displaystyle\mathbb{P}\left(z^{\prime}\right)$ $\displaystyle=\alpha_{0}\beta_{0}(x)T_{0}^{\prime}(z^{\prime},x)+\alpha_{1} \sum_{s\in V}\beta_{1}(s)T^{\prime}_{1}(z^{\prime},s)$ (38) $\displaystyle=\alpha_{0}\beta_{0}(x)T_{0}(z,x)+\kappa\alpha_{1}\sum_{s\in V} \beta_{1}(s)T_{1}(z,s)$ (39) $\displaystyle=\kappa\alpha_{0}\sum_{s\in U}\beta_{0}(s)T_{0}(z,s)+\kappa\alpha _{1}\sum_{s\in V}\beta_{1}(s)T_{1}(z,s)$ (40) $\displaystyle=\kappa\mathbb{P}\left(z\right).$ (41) $$

Similarly, by definition we have

$$ $\displaystyle\mathbb{P}\left(z^{\prime\prime}\right)$ $\displaystyle=\alpha_{0}\sum_{s\in U^{r}}\beta_{0}(s)T_{0}(z,s)+(1-\kappa) \kappa\alpha_{1}\sum_{s\in V}\beta_{1}(s)T_{1}(z,s),$ (42) $$

and summing this with (39), we obtain
$\mathbb{P}\left(z\right)=\mathbb{P}\left(z^{\prime}\right)+\mathbb{P}\left(z^{
\prime\prime}\right)$.

Claim (32):
Note that it is sufficient to prove the claim for $a=0$ since the probabilities sum to 1. Write

$$ $\displaystyle\mathbb{P}\left(a=0|z\right)$ $\displaystyle=\frac{\mathbb{P}\left(a=0,z\right)}{\mathbb{P}\left(z\right)}$ (43) $\displaystyle=\frac{\alpha_{0}\sum_{s\in U}\beta_{0}(s)T_{0}(z,s)}{\mathbb{P} \left(z\right)}$ (44) $\displaystyle=\frac{\kappa\cdot\alpha_{0}\sum_{s\in U}\beta_{0}(s)T_{0}(z,s)}{ \kappa\cdot\mathbb{P}\left(z\right)}$ (45) $\displaystyle=\frac{\alpha_{0}\beta_{0}(x)T_{0}(z,x)}{\mathbb{P}\left(z^{ \prime}\right)}$ (46) $\displaystyle=\mathbb{P}\left(a=0|z^{\prime}\right).$ (47) $$

Similarly,

$$ $\displaystyle\mathbb{P}\left(a=0|z\right)$ $\displaystyle=\frac{\mathbb{P}\left(a=0,z\right)}{\mathbb{P}\left(z\right)}$ (48) $\displaystyle=\frac{\alpha_{0}\sum_{s\in U}\beta_{0}(s)T_{0}(z,s)}{\mathbb{P} \left(z\right)}$ (49) $\displaystyle=\frac{(1-\kappa)\cdot\alpha_{0}\sum_{s\in U}\beta_{0}(s)T_{0}(z, s)}{(1-\kappa)\cdot\mathbb{P}\left(z\right)}$ (50) $\displaystyle=\frac{\alpha_{0}\sum_{s\in U^{r}}\beta_{0}(s)T_{0}(z,s)}{\mathbb {P}\left(z^{\prime\prime}\right)}$ (51) $\displaystyle=\mathbb{P}\left(a=0|z^{\prime\prime}\right).$ (52) $$

Claim (33):
For $a=1$, let us show $\mathbb{P}\left(s|z,a\right)=\mathbb{P}\left(s|z^{\prime},a\right)$.

$$ $\displaystyle\mathbb{P}\left(s|z,a=1\right)$ $\displaystyle=\frac{\alpha_{1}\beta_{1}(s)T_{1}(z,s)}{\alpha_{1}\sum_{s^{ \prime}\in V}\beta_{1}(s^{\prime})T_{1}(z,s^{\prime})}$ (53) $\displaystyle=\frac{\kappa\alpha_{1}\beta_{1}(s)T_{1}(z,s)}{\kappa\alpha_{1} \sum_{s^{\prime}\in V}\beta_{1}(s^{\prime})T_{1}(z,s^{\prime})}$ (54) $\displaystyle=\frac{\alpha_{1}\beta_{1}(s)T^{\prime}_{1}(z,s)}{\alpha_{1}\sum_ {s^{\prime}\in V}\beta_{1}(s^{\prime})T^{\prime}_{1}(z,s^{\prime})}$ (55) $\displaystyle=\mathbb{P}\left(s|z^{\prime},a=1\right).$ (56) $$

The statement $\mathbb{P}\left(s|z,a\right)=\mathbb{P}\left(s|z^{\prime\prime},a\right)$ is shown similarly. Next, for $a=0$, we have $\mathbb{P}\left(x|z^{\prime},a\right)=1$ and $\mathbb{P}\left(x|z^{\prime\prime},a\right)=0$ by the definition of the coupling $T^{\prime}$.
Moreover, for $s\in U^{r}$, $\mathbb{P}\left(s|z^{\prime},a\right)=0$ also follows by the definition of $T^{\prime}$.
Finally, write

$$ $\displaystyle\mathbb{P}\left(s|z^{\prime\prime},a=0\right)$ $\displaystyle=\frac{\alpha_{0}\beta_{0}(s)T^{\prime}_{0}(z^{\prime\prime},s)}{ \sum_{s\in U^{r}}\alpha_{0}\beta_{0}(s^{\prime})T^{\prime}_{0}(z^{\prime\prime },s^{\prime})}$ (57) $\displaystyle=\frac{\alpha_{0}\beta_{0}(s)T_{0}(z,s)}{\sum_{s\in U^{r}}\alpha_ {0}\beta_{0}(s^{\prime})T_{0}(z,s^{\prime})}$ (58) $\displaystyle=\frac{\alpha_{0}\beta_{0}(s)T_{0}(z,s)}{(1-\kappa)\sum_{s\in U} \alpha_{0}\beta_{0}(s^{\prime})T_{0}(z,s^{\prime})}$ (59) $\displaystyle=(1-\kappa)^{-1}\mathbb{P}\left(s|z,a=0\right).$ (60) $$

Claim (34):
We first observe that for any representation (and any z),

$$ $\displaystyle\mathbb{P}\left(Y=y|Z=z\right)$ $\displaystyle=\frac{\sum_{s,a}\mathbb{P}\left(Y=y,s,a,z\right)}{\mathbb{P} \left(z\right)}$ (61) $\displaystyle=\frac{\sum_{s,a}\mathbb{P}\left(Y=y|s,a\right)\mathbb{P}\left(s, a,z\right)}{\mathbb{P}\left(z\right)}$ (62) $\displaystyle=\sum_{a}\mathbb{P}\left(a|z\right)\left[\sum_{s\in S_{a}}\mathbb {P}\left(Y=y|s,a\right)\mathbb{P}\left(s|a,z\right)\right],$ (63) $$

where we have used the property (1) for the transition (61)-(62).
Now, using (33), for $a=1$ we have

$$ $\sum_{s\in S_{1}}\mathbb{P}\left(Y=y|s,a=1\right)\mathbb{P}\left(s|a=1,z\right )=\sum_{s\in S_{1}}\mathbb{P}\left(Y=y|s,a=1\right)\mathbb{P}\left(s|a=1,z^{ \prime}\right)=\sum_{s\in S_{1}}\mathbb{P}\left(Y=y|s,a=1\right)\mathbb{P} \left(s|a=1,z^{\prime\prime}\right).$ (64) $$

For $a=0$, we have for $z^{\prime}$ using (33):

$$ $\displaystyle\sum_{s\in S_{0}}\mathbb{P}\left(Y=y|s,a=1\right)\mathbb{P}\left( s|a=1,z^{\prime}\right)=\mathbb{P}\left(Y=y|x,a=1\right).$ (65) $$

For $a=0$ and $z^{\prime\prime}$ we have

$$ $\displaystyle\sum_{s\in S_{0}}\mathbb{P}\left(Y=y|s,a=1\right)\mathbb{P}\left( s|a=1,z^{\prime\prime}\right)$ $\displaystyle=\sum_{s\in U^{r}}\mathbb{P}\left(Y=y|s,a=1\right)\mathbb{P}\left (s|a=1,z^{\prime\prime}\right)$ (66) $\displaystyle=(1-\kappa)^{-1}\sum_{s\in U^{r}}\mathbb{P}\left(Y=y|s,a=1\right) \mathbb{P}\left(s|a=1,z\right)$ (67) $$

where we have used (33) again on the last line.

Combining (64),(65),(67), and using (32) and the general expression (63), we obtain the claim (34).

Claim (35): This follows immediately from
(34) by using (31) and the concavity of $h$.

Claim (36):
By definition, for every representation, $\mu_{a}(z)=\mathbb{P}\left(Z=z|a\right)=\frac{\mathbb{P}\left(z|a\right)
\mathbb{P}\left(z\right)}{\mathbb{P}\left(a\right)}$.
Thus, using (31),(32) we have
for $a\in\left\{0,1\right\}$,

$$ $\mu_{a}(z^{\prime})=\kappa\mu_{a}(z)\text{ and }\mu_{a}(z^{\prime\prime})=(1- \kappa)\mu_{a}(z),$ (68) $$

which in turn yields (36).

It remains only to recall that we have derived (35),(36) under the assumption that $\left|V\right|>0$. That is, we assumed that the point $z$ which fails invertability on $S_{0}$ has some parents in $S_{1}$. The case when $\left|V\right|=0$, i.e. there are no parents in $S_{1}$ can be treated using a similar argument, but is much simpler. Indeed, in this case one can simply split $z$ into $z^{\prime}$ and $z^{\prime\prime}$ and splitting the $S_{0}$ weight between them as before, without the need to carefully balance the interaction of probabilities with $S_{1}$ via $\kappa$.

∎

###### Proof.

## Appendix D Uniform Approximation and Two Point Representations

As discussed in Sections 1,5.2, we are interested in showing that all optimal invertible representations, no matter which, and no matter on which set $\mathcal{Z}^{\prime}$, can be approximated using a representation with the following property: For every $u\in S_{0},v\in S_{1}$, there are at most $k$ points
$z\in\mathcal{Z}$ that have $(u,v)$ as parents, see Figure 2(a). Here $k$ would depend only on the desired approximation degree, but not on $\mathcal{Z}^{\prime}$, or on the exact representation we are approximating. We therefore refer to this result as the Uniform Approximation result. Its implications for practical use were discussed in Section 5.2.

To proceed with the analysis, in what follows we introduce the notion of two-point representation. The main result is given as Lemma D.1 below.

This Section uses the notation of Section 4.
Let $T$ be an invertible representation, let $u\in S_{0},v\in S_{1}$ be some points, and denote by $\mathcal{Z}_{uv}=\left\{z^{j}\right\}_{1}^{k}$ the set of all points $z\in\mathcal{Z}$ which have $u$ and $v$ as parents. Denote by

$$ $w_{u}=\sum_{j=1}^{k}\beta_{0}(u)T_{0}(z^{j},u)\text{ and }w_{v}=\sum_{j=1}^{k} \beta_{1}(v)T_{1}(z^{j},v)$ (69) $$

the total weights of $\beta_{0}$ and $\beta_{1}$ transferred by the representation from $u$ and $v$ respectively to $\mathcal{Z}_{uv}$. Recall that $\rho_{u},\rho_{v}$ denote the distributions of $Y$ conditioned on $u,v$.
We call the situation above, i.e. the collection of numbers
$\left(\left\{\beta_{0}(u)T_{0}(z^{j},u)\right\}_{j\leq k},\left\{\beta_{1}(v)T
_{1}(Z^{j},v)\right\}_{j\leq k}\right)$,
a *two point representation*, since it describes how the weight from the points $u,v$ is distributed in the representation, independently of the rest of the representation.
The contribution of $\mathcal{Z}_{uv}$ to the global performance cost is

$$ $\displaystyle E_{uv,T}$ $\displaystyle:=\sum_{j\leq k}\mathbb{P}\left(z^{j}\right)h(\mathbb{P}\left(Y|z ^{j}\right))$ (70) $\displaystyle=\sum_{j\leq k}\left(\alpha_{0}\beta_{0}(u)T_{0}(z^{j},u)+\alpha_ {1}\beta_{1}(v)T_{1}(z^{j},v)\right)h\left(\frac{\alpha_{0}\beta_{0}(u)T_{0}(z ^{j},u)\rho_{u}+\alpha_{1}\beta_{1}(v)T_{1}(z^{j},v)\rho_{v}}{\alpha_{0}\beta_ {0}(u)T_{0}(z^{j},u)+\alpha_{1}\beta_{1}(v)T_{1}(z^{j},v)}\right),$ (71) $$

while its contribution to the fairness condition is

$$ $F_{uv,T}=\frac{1}{2}\sum_{j\leq k}\left|\beta_{0}(u)T_{1}(z^{j},u)-\beta_{1}(v )T_{1}(z^{j},v)\right|.$ (72) $$

Let us now consider two extreme cases of two-point representations.
Assume that the total amounts of weight to be represented, $w_{u},w_{v}$ are fixed. The first case is when $k=1$, and this is the maximum fairness case, since in this case the weights $w_{u},w_{v}$ overlap as much as possible. Indeed, the contributions to the fairness penalty and performance cost in this case are

$$ $\left|w_{u}-w_{v}\right|\text{ and }\left(\alpha_{0}w_{u}+\alpha_{1}w_{v} \right)h\left(\frac{\alpha_{0}w_{u}\rho_{u}+\alpha_{1}w_{v}\rho_{v}}{\alpha_{0 }w_{u}+\alpha_{1}w_{v}}\right)$ (73) $$

respectively. The other extreme case is when $w_{u}$ and $w_{v}$ do not overlap at all. This case be realised with $k=2$, by sending all $w_{u}$ to $z^{1}$ and
all $w_{v}$ to $z^{2}$. The fairness and performance contributions would be

$$ $w_{u}+w_{v}\text{ and }\alpha_{0}w_{u}\cdot h\left(\rho_{u}\right)+\alpha_{1}w _{v}\cdot h\left(\rho_{v}\right),$ (74) $$

respectively. Note that the fairness penalty is the maximum possible, while the performance cost is the minimum possible (indeed, this is the cost before the representation, and any representation can only increase it, by Lemma A.1). We thus observed that each two points
$u,v$, with fixed total weight $w_{u},w_{v}$, can have their own Pareto front of performance-fairness. One could, in principle, fix a threshold
$\gamma_{uv}$, $\left|w_{u}-w_{v}\right|\leq\gamma_{uv}\leq w_{u}+w_{v}$ for the fairness penalty (72), and obtain a performance cost between that in (73) and (74). However, it is not clear how large the number of points $k$ should be in order to realise such intermediate representations.
In the following Lemma we show that one can uniformly approximate all the points on the two-point Pareto front using a fixed number of points, that depends only on the function $h$. This means that in practice one can choose a certain number $n$ of $z$ points, and have guaranteed bounds on the possible amount of loss incurred with respect to all representations of all other sizes.

###### Lemma D.1 .

For every $\varepsilon>0$, there a number $n=n_{\varepsilon}$ depending only on the function $h$, with the following property:
For every two-point representation
$\left(\left\{\beta_{0}(u)T_{0}(z^{j},u)\right\}_{j\leq k},\left\{\beta_{1}(v)T
_{1}(Z^{j},v)\right\}_{j\leq k}\right)$,
with total weights $w_{u},w_{v}$, there is a two point representation $T^{\prime}$ on a set $\mathcal{Z}^{\prime}_{u,v}$, with the same total weights,
such that $\left|\mathcal{Z}^{\prime}_{uv}\right|\leq n$,
and such that

$$ $F_{uv,T^{\prime}}\leq F_{uv,T}\text{ and }\hskip 5.69054ptE_{uv,T^{\prime}} \leq E_{uv,T}+2(w_{u}+w_{v})\varepsilon.$ (75) $$

###### Proof.

To aid with brevity of notation, define
for $j\leq k$

$$ $c_{0}^{j}=\alpha_{0}\beta_{0}(u)T_{0}(z^{j},u),\hskip 5.69054ptc_{1}^{j}= \alpha_{1}\beta_{1}(v)T_{1}(z^{j},v).$ (76) $$

Then we can write

$$ $E_{uv,T}=\sum_{j\leq k}(c^{j}_{0}+c^{j}_{1})\cdot h\left(\frac{c_{0}^{j}\rho_{ u}+c_{1}^{j}\rho_{v}}{c_{0}^{j}+c_{1}^{j}}\right),\hskip 5.69054ptF_{uv,T}= \frac{1}{2}\sum_{j\leq k}\left|\Lambda c^{j}\right|,$ (77) $$

where $\Lambda$ is the vector $\Lambda=(\alpha_{0}^{-1},-\alpha_{1}^{-1})$, $c^{j}=(c_{0}^{j},c_{1}^{j})$, and $\Lambda c^{j}$ is the inner product of the two.

Observe that the cost $E_{uv,T}$ depends on $c^{j}$ mainly through the fractions $\frac{c_{0}^{j}}{c_{0}^{j}+c_{1}^{j}}$. Our strategy thus would be to approximate all $k$ of such fractions by a $\delta$-net of a size independent of $k$. To this end, set

$$ $p^{j}=\frac{c_{0}^{j}}{c_{0}^{j}+c_{1}^{j}}$ (78) $$

and define $h_{uv}:[0,1]\rightarrow\mathbb{R}$ by

$$ $h_{uv}(p)=h(p\rho_{u}+(1-p)\rho_{v}).$ (79) $$

Since $h$ is continuous (by assumption), and defined on a compact set, it is *uniformly* continuous, and so is $h_{uv}$. By definition, this means there is a $\delta>0$ such that for all $p,p^{\prime}$ with $\left|p-p^{\prime}\right|\leq\delta$, it holds that $\left|h_{uv}(p)-h_{uv}(p^{\prime})\right|\leq\varepsilon$. Let us now choose $\left\{x_{i}\right\}_{i=1}^{n}$ to be a $\delta$ net on $[0,1]$.
For every $i\leq n$ set

$$ $\Gamma_{i}=\left\{j\hskip 5.69054pt|\hskip 5.69054pt\left|p^{j}-x_{i}\right| \leq\delta,\text{ and $i$ is minimal with this property}\right\}.$ (80) $$

That is, $\Gamma_{i}$ is the set of indices $j$ such that $p^{j}$ is approximated by $x^{i}$.
Using $x_{i}$ we construct the representation $T^{\prime}$ as follows:
For $a\in\left\{0,1\right\}$ set

$$ $c^{\prime i}_{a}=\sum_{j\in\Gamma_{i}}c_{a}^{j}.$ (81) $$

For $n$ new points, $z^{i}\in\mathcal{Z}^{\prime}_{uv}$,
set $T^{\prime}_{0}(z^{\prime i},u)=c^{\prime i}_{0}/\beta_{0}(u)$,
$T^{\prime}_{1}(z^{\prime i},v)=c^{\prime i}_{1}/\beta_{1}(v)$. Note that the total weights
are preserved, $\sum_{i\leq n}c^{\prime i}_{0}=w_{u}$ and $\sum_{i\leq n}c^{\prime i}_{1}=w_{v}$.

Next, for every $j\in\Gamma_{i}$ we have

$$ $\left|\frac{c^{j}_{0}}{c^{j}_{0}+c^{j}_{1}}-x_{i}\right|\leq\delta.$ (82) $$

Thus

$$ $\displaystyle\left|\frac{c^{\prime i}_{0}}{c^{\prime i}_{0}+c^{\prime i}_{1}}- x_{i}\right|=\left|\frac{\sum_{j\in\Gamma_{j}}\left[c^{j}_{0}-(c^{j}_{0}+c^{j} _{1})x_{i}\right]}{c^{\prime i}_{0}+c^{\prime i}_{1}}\right|\leq\frac{\sum_{j \in\Gamma_{j}}\delta(c^{j}_{0}+c^{j}_{1})}{c^{\prime i}_{0}+c^{\prime i}_{1}}=\delta.$ (83) $$

Next, observe that by the construction of $x_{i}$,

$$ $\displaystyle\left|E_{uv,T}-\sum_{i}(c^{\prime i}_{0}+c^{\prime i}_{1})h_{uv}( x_{i})\right|$ $\displaystyle=\left|\sum_{i}\sum_{j\in\Gamma_{i}}(c^{j}_{0}+c^{j}_{1})h_{uv}(p ^{j})-\sum_{i}(c^{\prime i}_{0}+c^{\prime i}_{1})h_{uv}(x_{i})\right|$ (84) $\displaystyle\leq\sum_{i}\sum_{j\in\Gamma_{i}}(c^{j}_{0}+c^{j}_{1})\varepsilon$ (85) $\displaystyle=(w_{u}+w_{v})\varepsilon.$ (86) $$

In addition,

$$ $\displaystyle\left|E_{uv,T^{\prime}}-\sum_{i}(c^{\prime i}_{0}+c^{\prime i}_{1 })h_{uv}(x_{i})\right|$ $\displaystyle=\left|\sum_{i}(c^{\prime i}_{0}+c^{\prime i}_{1})h_{uv}(\frac{c^ {\prime i}_{0}}{c^{\prime i}_{0}+c^{\prime i}_{1}})-\sum_{i}(c^{\prime i}_{0}+ c^{\prime i}_{1})h_{uv}(x_{i})\right|$ (87) $\displaystyle\leq(w_{u}+w_{v})\varepsilon,$ (88) $$

where we have used (83) in the last transition.

Combining the two inequalities yields the second part of (75),

$$ $\left|E_{uv,T^{\prime}}-E_{uv,T}\right|\leq 2(w_{u}+w_{v})\varepsilon.$ (89) $$

Finally, note that

$$ $\displaystyle\sum_{i}\left|\Lambda c^{\prime i}\right|$ $\displaystyle=\sum_{i}\left|\sum_{j\in\Gamma_{j}}\Lambda c^{j}\right|$ (90) $\displaystyle\leq\sum_{i}\sum_{j\in\Gamma_{j}}\left|\Lambda c^{j}\right|$ (91) $\displaystyle=\sum_{j}\left|\Lambda c^{j}\right|,$ (92) $$

yielding the first part of, and thus completing the proof of, statement (75).

It remains to observe that above we have used a $\delta$ net for $h_{uv}$, which depends on $\rho_{u},\rho_{v}$. However, we can directly build an appropriate $\delta$-net in full range of $h$, the simplex $\Delta_{\mathcal{Y}}$,
which would produce bounds valid for all $u,v$.
Indeed, let $\delta^{\prime}$ be such that $\left|h(\nu)-h(\nu)\right|\leq\varepsilon$ for all $\mu,\nu\in\Delta_{\mathcal{Y}}$ with $\left\|u-v\right\|_{1}\leq\delta^{\prime}$. Observe that the map $p\mapsto p\rho_{v}+(1-p)\rho_{u}$ is 2-Lipschitz from $\mathbb{R}$ to $\Delta_{\mathcal{Y}}$ equipped with the $\left\|\cdot\right\|_{1}$ norm, for any $u,v\in\Delta_{\mathcal{Y}}$. Thus, choosing $\delta=\frac{1}{2}\delta^{\prime}$, we have
$\left|h_{uv}(p)-h_{uv}(p^{\prime})\right|\leq\varepsilon$ if $\left|p-p^{\prime}\right|\leq\delta$.
This completes the proof of the Lemma.
∎

###### Lemma D.1 .

###### Proof.

## Appendix E Concavity Of E r subscript 𝐸 𝑟 E_{r} italic_E start_POSTSUBSCRIPT italic_r end_POSTSUBSCRIPT

Note that the variables $r$ appear in (9) both as coefficients multiplying $h$ and inside the arguments of $h$, in a fairly involved manner. Nevertheless, the cost turns out to still retain an interesting structure, as it is *concave*, if $h$ is. We record this in the following Lemma.

###### Lemma E.1 .

If $h:\Delta_{\mathcal{Y}}\rightarrow\mathbb{R}$ is concave, then of every $\rho_{1},\rho_{2}\in\Delta_{\mathcal{Y}}$ the function $g:\mathbb{R}^{2}\rightarrow\mathbb{R}$, given by $g((c_{1},c_{2}))=(c_{1}+c_{2})h(\frac{c_{1}\rho_{1}+c_{2}\rho_{2}}{c_{1}+c_{2}})$ is concave.

###### Proof.

It is sufficient to show that for every $c,c^{\prime}\in\mathbb{R}^{2}$, we have $g((c+c^{\prime})/2)\geq\frac{1}{2}(g(c)+g(c^{\prime})$. To this end,
define the map $F:\mathbb{R}^{2}\rightarrow\Delta_{\mathcal{Y}}$ by

$$ $F(c)=\frac{c_{1}\rho_{1}+c_{2}\rho_{2}}{c_{1}+c_{2}}$ (93) $$

and note that

$$ $\displaystyle F((c+c^{\prime})/2)=F(c)\frac{c_{1}+c_{2}}{c_{1}+c_{2}+c^{\prime }_{1}+c^{\prime}_{2}}+F(c^{\prime})\frac{c^{\prime}_{1}+c^{\prime}_{2}}{c_{1}+ c_{2}+c^{\prime}_{1}+c^{\prime}_{2}}.$ (94) $$

It then follows that

$$ $\displaystyle g((c+c^{\prime})/2)$ $\displaystyle=\frac{1}{2}(c_{1}+c_{2}+c^{\prime}_{1}+c^{\prime}_{2})h(F((c+c^{ \prime})/2))$ (95) $\displaystyle=\frac{1}{2}(c_{1}+c_{2}+c^{\prime}_{1}+c^{\prime}_{2})h\left(F(c )\frac{c_{1}+c_{2}}{c_{1}+c_{2}+c^{\prime}_{1}+c^{\prime}_{2}}+F(c^{\prime}) \frac{c^{\prime}_{1}+c^{\prime}_{2}}{c_{1}+c_{2}+c^{\prime}_{1}+c^{\prime}_{2} }\right)$ (96) $\displaystyle\geq\frac{1}{2}(c_{1}+c_{2}+c^{\prime}_{1}+c^{\prime}_{2})\left[ \frac{c_{1}+c_{2}}{c_{1}+c_{2}+c^{\prime}_{1}+c^{\prime}_{2}}h(F(c))+\frac{c^{ \prime}_{1}+c^{\prime}_{2}}{c_{1}+c_{2}+c^{\prime}_{1}+c^{\prime}_{2}}h(F(c^{ \prime}))\right]$ (97) $\displaystyle=\frac{1}{2}\left(g(c)+g(c^{\prime})\right).$ (98) $$

∎

###### Lemma E.1 .

###### Proof.

## Appendix F Additional Proofs

### F.1 Proof Of Lemma 5.1

###### Proof.

For this proof it is more convenient to work with the $\ell_{1}$ norm $\left\|\cdot\right\|_{1}$ directly. Recall that $\left\|\mu_{0}-\mu_{1}\right\|_{TV}=\frac{1}{2}\left\|\mu_{0}-\mu_{1}\right\|_
{1}$ and that

$$ $\left\|\mu_{0}-\mu_{1}\right\|_{1}=\sum_{z}\left|\mu_{0}(z)-\mu_{1}(z)\right|.$ (99) $$

Assume that $\left\|\mu_{0}-\mu_{1}\right\|_{1}=2\gamma$. Define the functions
$\bar{\phi}_{0}(z)=\mathbbm{1}_{\left\{\mu_{1}\geq\mu_{0}\right\}}(z)\cdot(\mu_
{1}(z)-\mu_{0}(z))$ and
$\bar{\phi_{1}}(z)=\mathbbm{1}_{\left\{\mu_{0}\geq\mu_{1}\right\}}(z)\cdot(\mu_
{0}(z)-\mu_{1}(z))$. Note that we then have

$$ $\sum_{z}\bar{\phi}_{0}(z)=\sum_{z}\bar{\phi}_{1}(z)=\gamma.$ (100) $$

Indeed, define

$$ $\eta(z)=\mathbbm{1}_{\left\{\mu_{0}\geq\mu_{1}\right\}}(z)\cdot\mu_{1}(z)+ \mathbbm{1}_{\left\{\mu_{1}\geq\mu_{0}\right\}}(z)\cdot\mu_{0}(z).$ (101) $$

Clearly, $\eta+\bar{\phi}_{0}=\mu_{1}$ and thus
$\sum_{z}\eta(z)+\bar{\phi}_{0}(z)=1$.
Similarly,
$\sum_{z}\eta(z)+\bar{\phi}_{1}(z)=1$.
Therefore we have

$$ $\sum_{z}\bar{\phi}_{0}(z)=\sum_{z}\bar{\phi}_{1}(z).$ (102) $$

Note also that we can write

$$ $2\gamma=\left\|\mu_{0}-\mu_{1}\right\|_{1}=\sum_{z}\left|\mu_{0}(z)-\mu_{1}(z) \right|=\sum_{z}\left(\bar{\phi}_{0}(z)+\bar{\phi}_{1}(z)\right),$ (103) $$

which combined with (102) yields (100).

Next, we can also directly verify that

$$ $\mu_{0}+\bar{\phi_{0}}=\mu_{1}+\bar{\phi_{1}},$ (104) $$

and thus setting $\phi_{0}=\gamma^{-1}\bar{\phi_{0}},\phi_{1}=\gamma^{-1}\bar{\phi_{1}}$ completes the proof of this direction.

In the other direction, given $\phi_{0},\phi_{1}\in\Delta_{\mathcal{Z}}$ such that $\mu_{0}+\gamma\phi_{0}=\mu_{1}+\gamma\phi_{1}$, we have

$$ $\sum_{z}\left|\mu_{0}(z)-\mu_{1}(z)\right|=\gamma\sum_{z}\left|\phi_{1}(z)- \phi_{0}(z)\right|\leq 2\gamma,$ (105) $$

thus completing the proof.
∎

###### Proof.

### F.2 The Factor Representation

Fix $z\in\mathcal{Z}$.
To show $\mu_{0}(z)=\bar{\mu_{0}}(z)$ write, by definition,

$$ $\displaystyle\bar{\mu}_{0}(z)$ $\displaystyle=\sum_{\rho}\bar{\beta}_{0}(\rho)\bar{T}_{0}(z,\rho)$ (106) $\displaystyle=\sum_{\rho}\sum_{v\in\Psi^{-1}(\left\{\rho\right\})}\beta_{0}(v) T_{0}(z,v)$ (107) $\displaystyle=\sum_{v\in S_{0}}\beta_{0}(v)T_{0}(z,v)$ (108) $\displaystyle=\mu_{0}(z).$ (109) $$

The case $a=1$ is shown similarly.
Next, the above also implies that

$$ $\mathbb{P}_{\bar{T}}\left(z\right)=\alpha_{0}\bar{\mu_{0}}(z)+\alpha_{1}\bar{ \mu_{1}}(z)=\alpha_{0}\mu_{0}(z)+\alpha_{1}\mu_{1}(z)=\mathbb{P}_{T}\left(z \right).$ (110) $$

Finally, by definition we have

$$ $\displaystyle\mathbb{P}_{\bar{T}}\left(Y|z\right)$ $\displaystyle=\sum_{a\in\left\{0,1\right\}}\sum_{\rho}\mathbb{P}_{\bar{T}} \left(Y|\rho,a\right)\mathbb{P}_{\bar{T}}\left(\rho,a|z\right)$ (111) $\displaystyle=\mathbb{P}_{\bar{T}}\left(z\right)^{-1}\sum_{a\in\left\{0,1 \right\}}\sum_{\rho}\mathbb{P}_{\bar{T}}\left(Y|\rho,a\right)\mathbb{P}_{\bar{ T}}\left(z|\rho,a\right)\bar{\beta}_{a}(\rho)\alpha_{a}$ (112) $$

Taking (110) into account, to show
$\mathbb{P}_{\bar{T}}\left(Y|z\right)=\mathbb{P}_{T}\left(Y|z\right)$ it thus suffices to show that for a fixed $a$,

$$ $\sum_{\rho}\mathbb{P}_{\bar{T}}\left(Y|\rho,a\right)\mathbb{P}_{\bar{T}}\left( z|\rho,a\right)\bar{\beta}_{a}(\rho)\alpha_{a}=\sum_{x}\mathbb{P}_{T}\left(Y|x ,a\right)\mathbb{P}_{T}\left(z|x,a\right)\beta_{a}(\rho)\alpha_{a}.$ (113) $$

Let us consider $a=0$. Then

$$ $\displaystyle\sum_{\rho}\mathbb{P}_{\bar{T}}\left(Y|\rho,a=0\right)\mathbb{P}_ {\bar{T}}\left(z|\rho,a=0\right)\bar{\beta}_{0}(\rho)\alpha_{0}$ $\displaystyle=\alpha_{0}\sum_{\rho}\rho\bar{T}_{0}(z,\rho)\bar{\beta}_{0}(\rho)$ (114) $\displaystyle=\alpha_{0}\sum_{\rho}\rho\sum_{v\in\Psi^{-1}(\left\{\rho\right\} )}\beta_{0}(v)T_{0}(z,v)$ (115) $\displaystyle=\alpha_{0}\sum_{v\in S_{0}}\rho_{v}\beta_{0}(v)T_{0}(z,v).$ (116) $$

where we have use the definitions on line (114), and in particular that $\mathbb{P}_{\bar{T}}\left(Y|\rho,a\right)=\rho$ by construction.
This shows (113) for $a=0$, and the case $a=1$ is shown similarly, thus completing the proof.

## Appendix G Experiments - Additional Details

### G.1 Datasets for evaluations

The FNF data preprocessing, as implemented in ,
was used for both MIFPO and FNF models. In running FNF, we have used
the original code and configuration from ,
with the exception that we have disabled the noise injection into features, and the subsequent logit transformation.
This was disabled since this step was not a part of preprocessing,
and due its particular implementation in , it significantly complicated the comparison with an external model like XGBoost. This step was also performed during both training and *evaluation*, thus producing a less clean experiment, and was not documented anywhere in the paper .
We note that retaining this step would not have changed the FNF related analysis or its conclusions, as presented in Section 6.

### G.2 Minimization of Concave Functions under Convex Constraints

as described in figure 6, we used the disciplined convex concave programming (DCCP) framework and the associated solver, (Shen et al.,, , ) for solving the concave minimization with convex constraints problem.

Minimizing concave functions under convex constraints is a common problem in optimization theory. Unlike convex optimization where global minima can be readily found, in concave minimization problems we only know that the local minimas lie on the boundaries of the feasible region defined by the convex constraints. While techniques such as branch-and-bound algorithms, cutting plane methods, and heuristic approaches are often employed, here we used the framework of DCCP which gain a lot of popularity in recent years.

The DCCP framework extends disciplined convex programming (DCP) to handle nonconvex problems with objective and constraint functions composed of convex and concave terms. The idea behind a "disciplined" methodology for convex optimization is to impose a set of conventions inspired by basic principles of convex analysis and the practices of convex optimization experts. These "disciplined" conventions, while simple and teachable, allow much of the manipulation and transformation required for analyzing and solving convex programs to be automated. DCCP builds upon this idea, providing an organized heuristic approach for solving a broader class of nonconvex problems by combining DCP principles with convex-concave programming (CCP) methods, and is implemented as an extension to the CVXPY package in Python.

While convenient, the use of the disciplined framework bears some limitations. Mainly, generic operations like element-wise multiplication are not under the allowed set of operations (and for obvious reasons), which limits the usability. Notice, that for the prediction accuracy measure $h(p)=\min(p,1-p)$ this is not a problem, but for the entropy classification error $h((1-p,p))=-p\log p-(1-p)\log(1-p)$, this is more challenging. Nevertheless, here we show that the standard DCCP framework allows for entropy classification error.

###### Lemma G.1 .

Let $a=(1-\alpha)\mathcal{V}(v)r_{v,z}$ and $b=\alpha\cdot\mathcal{U}(u)r_{u,z}$, with $p_{v}=p_{a}$ and $p_{u}=p_{b}$.

We can write our cost function under the entropy accuracy error as:

$$ $\displaystyle(a+b)\cdot\mathrm{entropy}$ $\displaystyle\left(\frac{a\cdot p_{a}+b\cdot p_{b}}{a+b}\right)$ $\displaystyle=\mathrm{entropy}(a\cdot(1-p_{a})+b\cdot(1-p_{b}))+\mathrm{ entropy}(a\cdot p_{a}+b\cdot p_{b})-\mathrm{entropy}(a+b)$ $$

###### Proof.

$$ $\displaystyle\mathrm{entropy}(x)$ $\displaystyle=\mathrm{entropy}(x,1-x)=x\left[\log(x)-\log(1-x)\right]+\log(1-x)$ $$

Thus,

$$ $\displaystyle\mathrm{entropy}\left(\frac{a\cdot p_{a}+b\cdot p_{b}}{a+b}\right)$ $\displaystyle=\frac{a\cdot p_{a}+b\cdot p_{b}}{a+b}\left[\log\left(\frac{a \cdot p_{a}+b\cdot p_{b}}{a+b}\right)-\log\left(1-\frac{a\cdot p_{a}+b\cdot p_ {b}}{a+b}\right)\right]$ $\displaystyle\quad+\log\left(1-\frac{a\cdot p_{a}+b\cdot p_{b}}{a+b}\right)$ $\displaystyle=\frac{a\cdot p_{a}+b\cdot p_{b}}{a+b}\left[\log(a\cdot p_{a}+b \cdot p_{b})-\log(a+b-a\cdot p_{a}-b\cdot p_{b})\right]$ $\displaystyle\quad+\log(a+b-a\cdot p_{a}-b\cdot p_{b})-\log(a+b)$ $$

Hence :

$$ $\displaystyle(a+b)\cdot\mathrm{entropy}\left(\frac{a\cdot p_{a}+b\cdot p_{b}}{ a+b}\right)$ $\displaystyle=(a+b)\cdot\left[\frac{a\cdot p_{a}+b\cdot p_{b}}{a+b}\left[\log( a\cdot p_{a}+b\cdot p_{b})-\log(a+b-a\cdot p_{a}-b\cdot p_{b})\right]\right]$ $\displaystyle\quad+(a+b)\cdot\log(a+b-a\cdot p_{a}-b\cdot p_{b})$ $\displaystyle\quad-(a+b)\cdot\log(a+b)$ $$

$$ $\displaystyle=\mathrm{entropy}(a\cdot p_{a}+b\cdot p_{b})-(a\cdot p_{a}+b\cdot p _{b})\cdot\log(a+b-a\cdot p_{a}-b\cdot p_{b})$ $\displaystyle\quad+(a+b)\cdot\log(a+b-a\cdot p_{a}-b\cdot p_{b})-\mathrm{ entropy}(a+b)$ $$

Finally, the expression can be written as:

$$ $=\mathrm{entropy}(a+b-a\cdot p_{a}-b\cdot p_{b})+\mathrm{entropy}(a\cdot p_{a} +b\cdot p_{b})-\mathrm{entropy}(a+b)$ $$

$$ $=\mathrm{entropy}(a\cdot(1-p_{a})+b\cdot(1-p_{b}))+\mathrm{entropy}(a\cdot p_{ a}+b\cdot p_{b})-\mathrm{entropy}(a+b)$ $$

∎

Given the element-wise entropy function $x\cdot(1-x)$ is with known characteristics and under the dccp framework, we can use the entropy error for our cost using :

$$ $\displaystyle=$ $\displaystyle\mathrm{entropy}((1-\alpha)\mathcal{V}(v)r_{v,z}\cdot(1-p_{v})+ \alpha\cdot\mathcal{U}(u)r_{u,z}\cdot(1-p_{u}))$ $\displaystyle-\mathrm{entropy}((1-\alpha)\mathcal{V}(v)r_{v,z}\cdot p_{v}+ \alpha\cdot\mathcal{U}(u)r_{u,z}\cdot p_{u})$ $\displaystyle-\mathrm{entropy}((1-\alpha)\mathcal{V}(v)r_{v,z}+\alpha\cdot \mathcal{U}(u)r_{u,z})$ $$

###### Lemma G.1 .

###### Proof.

### G.3 Implementations and computational details

The Pareto front evaluation requires two main parts - solving the optimization problem described above, and building a calibrated classifier required for evaluating $c_{a}=P(Y|X,A=a)$ (see Algorithm 1).

For a calibrated classifier, we are using standard model calibration. Model calibration is a well-studied problem where we fit a monotonic function to the probabilities of some base model so that the probabilities will reflect real probabilities, that is, $P(Y|X)$. Here, we used Isotonic regression (Berta et al.,, ) for model calibration with XGBoost (Chen et al.,, ) as the base model. For training the XGBoost model, a GridSearchCV approach is employed to find the best hyperparameters from a specified parameter grid, using 3-fold cross-validation.

The experiments were conducted on a system with an Intel Core i9-12900KS CPU (16 cores, 24 threads), 64 GB of RAM, and an NVIDIA GeForce RTX 3090 GPU.

## Appendix H Fair Classifiers As Fair Representations

In this Section we show that the (accuracy, statistical parity) Pareto frontier of binary classifiers can be computed from the Pareto frontier of representations with total variation fairness distance.

We then proceed to evaluate the Pareto front of a few widely used fair classifiers on standard benchmark datasets, and compare it to the Pareto front computed by MIFPO. We find that in all cases, the standard classifiers produce fronts that are significantly weaker than the MIFPO front.

### H.1 The Relation between Representation and Classifier Pareto Fronts

For a binary classifier $\hat{Y}$ of $Y$, its prediction error is defined as usual by $\epsilon(\hat{Y}):=\mathbb{P}\left(\hat{Y}\neq Y\right)$.
The statistical parity *distance* of $\hat{Y}$ is defined as

$$ $\Delta_{SP}(\hat{Y}):=\left|\mathbb{P}\left(\hat{Y}=1|A=1\right)-\mathbb{P} \left(\hat{Y}=1|A=0\right)\right|.$ (117) $$

Let the uncertainy measure $h$ be defined by (4).

###### Lemma H.1 .

Let $\hat{Y}$ be a classifier of $Y$. Then there is a representation
given by a random variable $Z$ on a set $\mathcal{Z}$ with $\left|\mathcal{Z}\right|=2$, such that

$$ $\mathbb{E}_{z\sim Z}h(\mathbb{P}\left(Y|Z=z\right))\leq\epsilon(\hat{Y})\text{ and }\left\|\mu_{0}-\mu_{1}\right\|_{TV}\leq\Delta_{SP}(\hat{Y}).$ (118) $$

Conversely, for any given representation $Z$, there is a classifier
$\hat{Y}$ of $Y$ as a function of $Z$ (and thus of $(X,A)$), such that

$$ $\epsilon(\hat{Y})\leq\mathbb{E}_{z\sim Z}h(\mathbb{P}\left(Y|Z=z\right))\text{ and }\Delta_{SP}(\hat{Y})\leq\left\|\mu_{0}-\mu_{1}\right\|_{TV}.$ (119) $$

###### Proof.

Let us begin with the second part of the Lemma, inequalities (119).
Given a representation $Z$, $\epsilon(\hat{Y})\leq\mathbb{E}_{z\sim Z}h(\mathbb{P}\left(Y|Z=z\right))$ follows since $\mathbb{E}_{z\sim Z}h(\mathbb{P}\left(Y|Z=z\right))$ is the error of the optimal classifier of $Y$ as a function of $Z$. We choose $\hat{Y}$ to be such an optimal classifier and thus satisfy the above inequality, with equality.
Next, the second inequality in (119) holds for
for *any* classifier $\hat{Y}$ derived from $Z$.
The argument below is a slight generalisation of the argument in Madras et al., ().
Define $f(z)=\mathbb{P}\left(\hat{Y}=1|Z=z\right)$.
Note that for $a\in\left\{0,1\right\}$, $\mathbb{P}\left(\hat{Y}=1|A=a\right)=\int f(z)d\mu_{a}(z)$. Thus

$$ $\displaystyle\mathbb{P}\left(\hat{Y}=1|A=0\right)-\mathbb{P}\left(\hat{Y}=1|A= 1\right)$ $\displaystyle=\int f(z)d\mu_{0}(z)-\int f(z)d\mu_{1}(z)$ (120) $\displaystyle=\sup_{g|\left|g\right|\leq 1}\left|\int f(z)d\mu_{0}(z)-\int f(z )d\mu_{1}(z)\right|$ (121) $\displaystyle=\left\|\mu_{0}-\mu_{1}\right\|_{TV},$ (122) $$

where we have used $\left|f\right|\leq 1$ in the second line.
Repeating the argument also for $\mathbb{P}\left(\hat{Y}=1|A=1\right)-\mathbb{P}\left(\hat{Y}=1|A=0\right)$, we obtain the second inequality in (119).

We now turn to the first statement, 118.
Let $\hat{Y}$ be a classifier of $Y$ as a function of $(X,A)$.
Observe that thus by definition $\mathbb{P}\left(\hat{Y}|X,A\right)$ induces a distribution on the set
$\left\{0,1\right\}$, and thus may be considered as a representation $Z:=\hat{Y}$ of $(X,A)$ on that set. We now relate the properties of this $Z$ as a representation to the quantities $\epsilon(\hat{Y})$ and $\Delta_{SP}(\hat{Y})$. Similarly to the argument above, the first part of (118) follows since
$\mathbb{E}_{z\sim Z}h(\mathbb{P}\left(Y|Z=z\right))$ is the best possible error over all classifiers.
For the second part, note that since $\hat{Y}$ is binary, we have

$$ $\mathbb{P}\left(\hat{Y}=1|A=0\right)-\mathbb{P}\left(\hat{Y}=1|A=1\right)=- \mathbb{P}\left(\hat{Y}=0|A=0\right)+\mathbb{P}\left(\hat{Y}=0|A=1\right).$ (123) $$

It follows that

$$ $\displaystyle\left\|\mu_{0}-\mu_{1}\right\|_{TV}$ $\displaystyle=\frac{1}{2}\sum_{v\in\left\{0,1\right\}}\left|\mathbb{P}\left( \hat{Y}=v|A=0\right)-\mathbb{P}\left(\hat{Y}=v|A=1\right)\right|$ (124) $\displaystyle=\left|\mathbb{P}\left(\hat{Y}=1|A=0\right)-\mathbb{P}\left(\hat{ Y}=1|A=1\right)\right|$ (125) $\displaystyle=\Delta_{SP}(\hat{Y}),$ (126) $$

where we have used (123) for the second to third line transition. This completes the proof of the second part of (118).
∎

###### Lemma H.1 .

###### Proof.

### H.2 Comparison to Common Fair Classifiers

Figure: Figure 4: Comparing common fair classification pipelines to the MIFPO Pareto front, for LSAC, COMPAS, and ADULT datasets. For FGBM and LGBM+Post Process methods, each point represents a trade-off obtained at a single hyper-parameter configuration.
Refer to caption: extracted/5881113/figures/download.png

In this Section we evaluated the accuracy-fairness tradeoff for common fair classification algorithms using three datasets - the Adult dataset (income prediction), COMPAS (recidivism prediction), and LSAC (law school admission). These datasets are standard fair classification benchmarks, and have relevance to real-world decision-making processes.

Fairness classifiers are generally categorized into three groups: fair pre-processing, fair in-processing, and fair post-processing. Fair pre-processing and post-processing utilize standard classifiers as part of the fair classification pipeline. In the experiments below we have
evaluated two widely adopted algorithms, representing two different categories: (i) FairGBM Cruz et al., (), an in-processing method where a boosting trees algorithm (LightGBM) is subject to pre-defined fairness constraints, and (ii) Balanced-Group-Threshold, a post-processing method which adjusts the threshold per group to obtain a certain fairness criterion. For FairGBM we have used the original implementation provided by the authors, while for Balanced-Group-Threshold post-processing we have used the implementations available via Aequitas, a popular bias and fairness audit toolkit, Saleiro et al., ().

It is important to note that, as a rule, common fairness classification methods are not designed to control the fairness-accuracy trade-off explicitly. Instead, in most cases, these methods rely on rerunning the algorithm for a wide range of hyperparameter settings, in the hope that different hyperparameters would result in different fairness-accuracy trade-off points. However, there typically is no direct known and controlled relation between hyperpatameters and the obtained fairness-accuracy trade-off.

For FairGBM, we utilized the hyperparameter ranges specified in the original paper, Cruz et al., (). In the case of the balancing post-processing method, we iterated over all possible parameters to ensure a comprehensive analysis.

Figure 4 shows the MIFPO computed Pareto front, and all hyperparameter runs of the two algorithms above, with accuracy evaluated on the test set. These experiments demonstrate the following two points: (a)
The standard classifiers achieve a considerably lower accuracy than what is theoretically possible at a given fairness level. (b) the existing methods are also unable to present solutions for the full range of the statistical parity values. The values from the FGBM and the post-processing algorithms all have statistical parity $\leq 0.2$.

The above results emphasize the limitations of current fair classification algorithms in achieving optimal trade-offs between accuracy and fairness across the full range of fairness values, and suggest that there is room for improvement in developing more flexible and comprehensive fair classification techniques.

## Peer Reviews

confidence: 2
contribution: 2
initial_rating: 6
presentation: 3
questions: I do not have any significant questions.
soundness: 3
strengths: 1.This paper studies an interesting and important problem, as realizing the Pareto front is indeed important for any practical problems.

2. This paper is theoretically rigorous. The main techniques to achieve the goal, such as reduction to focus on invertible representations and solve the optimization problem (17) with restrictions listed below, are sound with formal justifications. Consequently, the method is theoretically credible.
summary: This paper has two main technical contributions: The first is to deeply analyze structural properties of optimal fair representations, and the other contribution is develop a method to compute the Pareto front for data distributions with any dimension. A particular advantage of this new method is its model independence: By using well-established optimization techniques, the computation of such Pareto front does not require an extensive of training of representation models; instead, much simpler data operations shall be sufficient.
weaknesses: The sensitive attributes here are assumed to be binary, but recently there have been some results for more general cases (multi-class, multi-group), and computing Pareto front for those cases are certainly more desirable, yet the setting in this paper is limited.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
questions: As far as I can tell, all non-pareto efficiency in the experiments come from the following factors: 1) Not enough samples 2) suboptimality of the DCCP solvers 3) Not enough expressibility of the chosen (proxy) representation space via choice of $k$ value. I believe that these should be discussed in a self-contained section within the experiments section. In addition, could there be more sources of errors which combine to make the curves not only have “pareto optimal” points in Figure 3?

Other minor comments:

1. Some inconsistent usage of \citet vs. \citep (for example in the first paragraph of the paper). Please see the reference: https://towson.libguides.com/mlastyle/in-text
2. Figure 1 seems to be slightly vertically squashed, which makes it a bit harder to read the equations. I would also recommend using a vector graphic (pdf) figure instead of a png / jpg, as the latter does not allow for highlighting / reduces accessibility. A pdf may also scale up / down better in terms of figure quality.
3. What is figure 1 depicting? Can you provide an explanation in the caption?
4. What is the randomness over in $P(Z|X = x, A=a)$ in line 78? Is there assumed to be an underlying distribution $D$ on $X \times Y$? Note: I believe the randomness is over theta, the parameters of the representation, but it may be helpful clarify this earlier if using the notation $P(Z|X = x, A=a)$ in the introduction.
5. Is $P(Y|X=x)$ the ground truth conditional label distribution (line 174)? If so, is $P(Y|Z=z)$ the same ground truth conditional label distribution in the representation space Z? I guess I am just a bit confused. I thought we defined Y as a random variable of X,A, how can we condition Y on a representation z?
6. To make sure I understand footnote 1, if we consider $\beta_a(s)$ in line 228, this should formally be written as $P(X=s|A=a) = P(X = (x, a) | A = a)$, where in the latter, the two realizations of $a$ are identical?
7. Invertible representation seems to be a key concept, maybe it should be a formal definition in line 240?
8. The choice of $k$ seems quite important for MIFPO. Do you have any ablations of the method performance across $k$ size? I’m assuming the computational complexity scales in $k$?
9. How does the work relate to Impossibility results for fair representations (Tosca Lechner, Shai Ben-David, Sushant Agarwal, Nivasini Anathakrishnan)? Is it that they require perfect statistical parity (i.e., TV distance 0)?
10. Missing citations for “Health”, “Crime”, and “Law” datasets. What are these datasets?
11. Missing citations for Adult, LSAC, and COMPAS datasets.
12. More generally, more details are needed for the experiments, how many train points for the calibrated classifiers? Do you hold out some fixed percent for post-processing? 
13. “Pareto front is flat for Law dataset” (468-473), but the MIFPO curve doesn’t seem very flat in Figure 3a? In fact, the vertical variability looks similar to the health dataset. 
14. Non-monotonicity of pareto curve in Figure 3a: is this only due to sample size issues?
15. Figure 4: inconsistent legends between plots. Could probably remove the legends from COMPAS and ADULT plots, or ensure that all legends are identical. Pareto Front should also maybe be labeled as “Pareto Front as Found by MIFPO (Ours)”, or something similar for clarity.
16. As a reader, I gained very little (if anything) from Figure 1 and 2. Ideally, they should be self-contained, or at least have an explanation somewhere in the text. Neither figure is explained in the main text or the caption.
17. In the appendix align environments, consider using \nonumber in order to hide the equation numbers of unreferenced lines. For example, equation 118 is — to my knowledge — not referenced anywhere.
18. The full concave program should be stated somewhere, instead of for example in Def. 5.1 saying that we minimize equation (17) subject to constraints (15-16) and (20-22) which are spread throughout the paper.
soundness: 3
strengths: I really enjoyed the fact that we can restrict to looking at a small, finite number of “parents” of points in the representation space, and this totally describes the set of pareto efficient transformations (I have a soft spot for such factorizations). The experiments also seem reasonable, and tie in with the theory directly. The fact that the proposed method MIFPO utilizes existing solvers is also a strength, given the power of these existing solvers in practice. Overall, the paper seems to propose a clear improvement over the compared method from previous work (FNF).
summary: The authors work with approximately fair representation learning, where the goal is to learn a fair representation random variable Z in $R^{d’}$. They define a $\gamma$-Fair representation as one which has a small L1 distance between the random variable Z conditioned on either a = 1 or a = 0 (where a is the sensitive attribute realization). Perfectly fair ($\gamma=0$) representation implies demographic parity / equalized odds w.r.t. attribute A for any classifier built on top of Z. The goal is to find a representation Z which minimizes total error (any concave function $h$) of the label random variable $Y$ conditioned on the representation $Z$. That is, we want to be able to reconstruct the ground truth conditional label distribution $Y$ with only the ability to modify the representation $Z$, subject to the constraint that $Z$ is $\gamma$-fair.

The main issue tackled by the paper is the fact that it can be difficult to work in the representation space $R^{d’}$ if the representations are allowed to be arbitrarily complex. Therefore, the authors focus on _invertible_ representations (line 240), which are those with a small basis in the original feature space (X,A). In theorem 4.1, the authors demonstrate that at least w.r.t. the fairness constraint, it suffices to search only in the space of invertible representations, whose total error is guaranteed to be “good enough”. 

Next, in section 5, the authors show how to use the invertibility theorem 4.1 in order to efficiently optimize over the representation space. Finally, in Section 6, the authors experiment with the proposed method, MIFPO, and compare against an existing fair representation learning algorithm FNF. They demonstrate that by estimating the base conditional probabilities with calibrated classifiers, MIFPO allows for construction of fair classifiers which tradeoff fairness and accuracy to a specified degree better than prior methods.
weaknesses: I have not worked in and am not familiar with the area of fair representation learning, and did not check any proofs of the paper. I think a major weakness of the paper --- as someone in algorithmic fairness with some background in theory --- is that it can be difficult to read. In particular, the main body is quite notation heavy, especially as you push into section 5. For example, some of the triple indexing in equation (17) seems a bit unnecessary, given that only two orders ever appear — $r_{u,v,j}$ or $r_{v, u, j}$ — and these two are very difficult to tell apart. Perhaps having a notation guide somewhere (maybe in the appendix) can be useful, since I found myself going back and forth needing to look up the definition of each variable.

I also think that there is some room for improvement in terms of detailing what the sources of randomness are (e.g. via the parameterization $\theta$), or better describing some of the notation (see minor comments for detailed examples). This could be a consequence of my background and being unfamiliar with working with labels and representations as random variables directly.

I am open to raising my score if the readability can be improved for the general theory / fairness audience. Perhaps this will require making parts of the discussion in the main body less formal in order to better give some intuition. It may also require having more statements / sections which describe the contributions and importance of different theorems and parts at a high level (especially for Section 5.2). This can be difficult, given that you would of course like to formally spell out the concave program that you are solving in the main body. I am open to suggestions on how the readability of 5.2 can be improved.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: My main questions concern how the authors view the nonconvexity of the entire optimization problem as a major or minor issue. They point out in the Conclusion section that their optimization problem, as it is concave *minimization*, does not provably converge to global optima, but I wasn't sure after reading the paper why solving the MIFPO program with DCCP is satisfactory. We see that the fairness-performance curve in Section 6 leaves some points that FNF doesn't quite reach, but is there anything we can formally say about how close to true optimal this fairness-performance curve is? I think that would rely on formal guarantees for DCCP, but I am unfamiliar with such guarantees.

Related to this question: how do we evaluate how good this "local" optimal Pareto frontier is? And what modifications to the MIFPO program seem promising to make it provably convex? My intuition suggests that the problem lies in the choice of $h$, but, in that case, it seems there's not much one can do.
soundness: 3
strengths: Overall, I found the main idea of this paper and the technical contribution very nice, and the authors mostly present their results in a well-organized way. I am not an expert in the fair representations literature, so I am not sure how these methods are positioned with respect to other fairness-ensuring methods (i.e. inprocessing methods, postprocessing methods), so I am unclear whether the paper as a whole is well-motivated (it very well may be, I could just be ignorant of how widely adopted fair representation learning is). But, if we take it as given that it is desirable to construct new ways to benchmark fair representations without needing to train them explicitly with complicated nonconvex NNs and such, then this paper presents a worthwhile and interesting contribution.

**Originality.** As far as my knowledge goes, this paper is an original contribution to the fair representation learning literature. It is particularly novel because it presents a way to compute a Pareto frontier for fairness-accuracy tradeoffs without explicitly training a representation itself. The authors come to this computation through analyzing the theoretical properties of a fair representation by first positing an intuitive optimization problem and then breaking down its constituent parts into quantities that are easily estimable from the data. The key step in doing so is interesting and, in my opinion, novel --- the authors reduce the search space of the problem from the input space (which can be any arbitrary subset of $\mathbb{R}^d$) to $\Delta_{\mathcal{Y}}$ through basic properties of representations.

**Quality.** The result itself is interesting and significant, and I particularly believe that the general technique of reducing the search space to $\Delta_{\mathcal{Y}}$ to make the computation feasible is interesting. The experiments seem to be comprehensive, and Algorithm 1, the implementation to solve MIFPO, relies on simple primitives that are easily estimable from the dataset. The derivation in Sections 3, 4, and 5 are sound as far as my reading of the results go, though I did not carefully step through the proofs of the main theorems and lemmas.

**Clarity.** The writing itself is mostly clear, although there are some notation changes I would suggest to make the exposition clearer (see "Weaknesses"). The main suggestion would be to stick with probability notation (e.g. $\mathrm{Pr}(Z = z \mid A = a)$, etc.) throughout the paper or to stick with the defined notation (with $\alpha, \beta, \rho, \mu$, etc.) throughout the paper. Switching between the two obscures some of the results and made reading the results slightly more difficult. Besides that, the paper itself is well-structured and, overall, gives a clear exposition of the main technique. Besides these notational difficulties, I had little trouble following along.

**Significance.** Because I am not an expert or well-versed in the specific fair representation subfield of the fairness literature, I cannot speak to the motivation of this particular method and whether it is a big gap in the literature. However, if it *is* desirable to have methods for computing such Pareto frontiers without explicit training of representations in order to benchmark fair representations well, I believe this is a significant contribution.
summary: This paper presents a method for calculating the Fairness-Accuracy Pareto front for all fair representations for a particular fairness-constrained learning task without needing to explicitly train representation models. As such, this front describes a space of possible trade-offs for fair representations in terms of their fairness vs. accuracy, which might have downstream applications in benchmarking particular trained fair representations and check if their performance still has room for improvement. The authors accomplish this through transforming the fair representation learning problem to a much lower-dimensional problem through observing a mapping from the input space to the simplex of the output space, $\Delta_{\mathcal{Y}}$. In binary classification, this is particularly appealing because $\Delta_{\mathcal{Y}} = [0, 1]$, which is nicely discretizable and much "more compact" than the arbitrary space of inputs. This results in a concave *minimization* program that, although unsolvable through nice black-box methods for convex optimization (it is concave *minimization* not *maximization*), still has easily estimable quantities from data and is experimentally feasible through certain DCCP frameworks. The authors show this in their suite of experiments over various standard fairness datasets.
weaknesses: There are a a couple of weaknesses I found in the paper, but none are significant enough to warrant rejecting the paper, in my view. Most of the weaknesses relate to the clarity of the paper, but the main technical weakness, in my eyes, is that the resulting optimization problem, though simpler, still relies on nonprovable guarantees --- it is a concave minimization problem, so we have no guarantees of global optima.

- **Concave minimization.** The authors themselves acknowledge in the conclusion that this is a weakness of their work, but it would be nice to see some more exposition justifying that computing this optimization problem, though it does not provably converge to global optima, is still a good thing to do in the context of constructing this Pareto front (more in "Questions").
- **Figures are slightly confusing.** I found the figures to be slightly confusing, as the notation in the figures doesn't quite match up with the notation in the paper, and the figures themselves are blurry and don't quite give a clear picture to what's going on, in my opinion. I would suggest going a bit lighter on the notation in the figures to make them a bit more comprehensible; for example, I don't think that Figure 2(b) needs the $\overline{T}$ full definition in it, and I don't think that Figure 2(a) needs a presentation of the probability distribution on $v, u, u'$ in the form of the squiggly red line and the accompanying $\beta$ labels. Cleaning up the figures to be more presentable would help in the clarity of presentation.
- **Notational issues.** My main issue with the clarity of the paper is that there is much switching back and forth between established notation and introducing of new notation. I think the paper would be clearer if the authors either stuck to just using the probability notation through, so it is clear what probabilities factorize into what (i.e. sticking to just presenting $T_a(z, s)$ instead as just $P(Z = z \mid X = s, A = a)$), or at least introducing notation that is a bit more evocative of what each quantity is. I would suggest perhaps using notation that invokes the relationship between $A, Z, X,$ and $Y$ in the symbols themselves. I found that Sections 4 and 5 were a bit heavy on introducing new notation and then not using it everywhere, such as in the definition of the $r$ variable in Section 5.2. I was still able to track the main arguments, but I believe that clarifying the notation a bit would assist in the overall clarity.
- **A couple of typographical issues/nitpicks.** These don't have an impact on my overall impression of the paper, but I just wanted to point out some small nitpicks I noticed to assist the authors in revising:
- "MIFPO" is never defined as an acronym. I assume that the acronym should stand for "Model Independent Pareto Front Optimization," but I guess it would be MIPFO then?
- In Equation 5, as a minor clarity fix, I would treat make the dependence of $Z$ on $\theta$ explicit and then just mention that, for the rest of the paper, we can assume that it is implicit in the distribution governing $Z$. 
- In Section 5.2, in the first paragraph, I would suggest writing the Lemma D.1 more formally in the main body, or, at least, explaining the $k$ point approximation a bit more. I found it a bit confusing until I checked the Appendix section.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: -- Could you discuss the implications of using different accuracy measures on your optimization formulation? Entropy accuracy seems to be challenging and also more involved than regular accuracy of prediction=true label.
-- Would the Pareto frontier optimization problem be simpler if other accuracy measures were used?
-- Could you simplify the flow chart of the mathematical arguments leading onto your main optimization (which btw has not been written together  with all the constraints)? For instance, what role does the factorisation, invertibility, etc. individually play to simplify and get to your final version?
-- What is the role of post-processing strategies?
soundness: 2
strengths: -- Interesting optimization-based strategy to obtain Pareto frontiers of the fairness-performance tradeoff 
-- Bypasses expensive model training
-- Strength lies in being able to restrict the problem space to invertible transformations, and then use off-the-shelf concave-convex optimization strategies
summary: This paper addresses the problem of understanding the critical tradeoff between fairness and accuracy. They propose strategies to obtain the Pareto frontier without performing any additional model training but instead by formulating an optimization problem. 
They consider the TV as their measure of fairness, and then go on to show how for every representation, one can find an invertible representation of the same data that satisfies at least as good a fairness constraint, and has at least as good performance as the original (shown in Theorem 4.1). Next, using this result they construct a model independent optimization problem -- that they call MIFPO -- which can approximate the Pareto Front of arbitrary high dimensional data distributions, but is much simpler to solve than direct representation learning for such distribution. They specifically use off-the-shelf concave-convex programming methods to obtain the Pareto frontier. Experiments have been performed on a few benchmark datasets such as LSAC, COMPAS, and ADULT.
weaknesses: --The presentation of the paper can be significantly improved. It is difficult to understand or properly check everything. For every subsection, it would be good to start with the main theorem/lemma/assertion being made in that subsection, then provide its significance towards arriving at your main result, and then provide the proof sketch/intuition behind it. 
Specific Example: The Invertibility Theorem, The Factorisation, The MIFPO  -- all these sections start with "This section provides ...." which is sometimes already understood from the title but what is important is to mention what role this particular aspect plays in the final optimization before getting into the details.  

-- In the introduction, it would be nice to summarize the main contributions as a list.
Specific Example: It would be great to have a flow-chart summarizing what are the various Theorems/Assertions made and specifically what role they play/why they are needed for the final optimization.

-- There are related works in accuracy-fairness literature which have proposed model-agnostic optimization formulations to characterize the trade-off. These two prior works share close similarities with the formulation in this paper and should be discussed.
Briefly explaining the key similarities and differences: Interestingly, while these prior works finally arrived at a convex optimization problem, but this paper arrives at a concave minimization problem with convex constraints which presents an intriguing nuance.
[1] Kim, Joon Sik, Jiahao Chen, and Ameet Talwalkar. "FACT: A diagnostic for group fairness trade-offs." International Conference on Machine Learning (ICML) 2020.
[2] Hamman, Faisal, and Sanghamitra Dutta. "Demystifying Local & Global Fairness Trade-offs in Federated Learning Using Partial Information Decomposition." International Conference on Learning Representations (ICLR) 2024.

-- There are several other related works on accuracy-fairness tradeoffs which have been missed. See the references and follow-up works from these two papers above to find more references.

---

confidence: 4
contribution: 2
initial_rating: 8
presentation: 2
questions: All the questions and suggestions are mentioned in the Weaknesses section.
soundness: 3
strengths: 1. **Use of Structural Properties**: The approach leverages the structural properties of optimal fair representations to efficiently approximate the Pareto front. By exploring previously underutilized properties, the authors have created a way to directly compute the fairness-performance front without a specific model structure.

2. **Model-Independent**: MIFPO’s model-agnostic nature allows it to serve as a comparative benchmark against complex fair representation models and classifiers, contributing to broader applications in fair ML model assessment.
summary: This paper introduces a model-independent method called MIFPO for computing the Pareto front of performance versus fairness in machine learning classification models. MIFPO achieves this by discretizing the space of possible distributions of the target variable and formulating a concave minimization problem with linear constraints. This problem can be efficiently solved using off-the-shelf solvers, such as the disciplined convex-concave programming (DCCP) framework. Experimental evaluations demonstrate MIFPO’s advantages over existing methods in both fair representation learning and fair classification.
weaknesses: 1. **Generalizability Issue:** The MIFPO method relies on discretizing the target space, which limits its application to finite or low-dimensional scenarios. This assumption restricts the method's generalizability to cases where target variables are continuous or involve multi-dimensional labels. A preliminary exploration of alternative methods that could apply to these contexts, or potential theoretical adjustments, would strengthen the paper and broaden its impact.

2. **Insufficient Coverage and Comparison with Related Works:** A major concern is the limited discussion of related works, which affects the paper’s positioning and diminishes the impact of MIFPO’s contributions in the context of established fairness-performance trade-offs. This trade-off problem is well-explored in fairness in machine learning, with numerous studies proposing methods to balance these objectives. However, these methods are not cited or analyzed here. Beyond just discussion, comparing MIFPO’s empirical results against these established approaches is essential to validate its contribution, demonstrating where MIFPO achieves improvements or differs significantly in performance. While the following papers represent a sample, many other relevant studies would also merit discussion and empirical comparison:

- [1] Wang, Hao, et al. "Aleatoric and epistemic discrimination: Fundamental limits of fairness interventions." Advances in Neural Information Processing Systems 36, 2023.

- [2] Dehdashtian, Sepehr, et al. "Utility-Fairness Trade-Offs and How to Find Them." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2024.

- [3] Sadeghi, Bashir, et al. "On characterizing the trade-off in invariant representation learning." Transactions on Machine Learning Research, 2022.

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

- [5] Zhao, Han, et al. "Inherent tradeoffs in learning fair representations." Journal of Machine Learning Research, 2022.

3. **Computational Complexity and Practicality:** The MIFPO implementation relies on DCCP which can be computationally intensive, especially for large datasets. The lack of guarantees for global minima in DCCP further raises questions about MIFPO’s ability to reliably converge to optimal solutions on larger, more complex datasets. Addressing scalability concerns would improve MIFPO's applicability to real-world scenarios. Exploring alternative solvers or optimization frameworks with scalability features, or clarifying computational requirements and limitations for different dataset sizes, would make the method more accessible to practitioners.

4. **Consideration of Alternative Fairness Definitions:** The paper exclusively uses statistical parity as the fairness metric; however, multiple definitions of group fairness exist, and studies [2, 6] have shown that statistical parity may not be ideal in practice since it does not consider target attributes. Alternative metrics such as Equality of Odds and Equal Opportunity are often more practical and widely used. The paper would be significantly strengthened if the authors discussed how MIFPO could be adapted to incorporate these alternative fairness definitions, as doing so could broaden its applicability and relevance in real-world settings.

- [6] Hardt, Moritz, et al. "Equality of opportunity in supervised learning." Advances in neural information processing systems 29, 2016.

Meta-review: This paper introduces a method to compute the Pareto front for fairness-constrained learning tasks. The key step is to transform the problem into a lower-dimensional space. Focusing on binary classification, this method is very efficient because the low-dimensional space can be efficiently discretized. The reformulated problem involves concave minimization, which can be solved by convex-concave programming methods. The authors validate their method through experiments on multiple standard fairness datasets.

After reading reviewers' feedbacks and reading this paper, I recommend rejection. Here are the main concerns on the proposed appraoch.
 
1. This work only considers a binary sensitive variable. The authors claim they can extent it for the multi-group case. However, the size of the optimization problem increases exponentially with the number of groups (and it is noncovex). The size is $|S_0|\times |S_1|\times k$ for the binary case and will be $|S_0|\times |S_1|\cdots\times|S_C|\times k$ when there are $C$ cases. This limits the applicability of the proposed method.

2. This method only works for binary classification because the computational cost also increases exponentially with the number of classes. In the binary classification case, the simplex $\Delta_Y$ is a 1-D line segment, which can be discretized easily. If there are $P$ classes, the proposed method has to discretize a simple $\Delta_Y$ in $\mathbb{R}^P$, so the grid size will be exponential in $P$.

3. The authors claim the concave minimization can be solved by existing solver. I don't think it is always easy. It is a nonconvex problem so the problem size cannot be large. However, to get a good approximation of the distribution, they need to create a fine-grid histogram, which will not be a small-size problem. Let alone the size increases with the number of classes and the number of sensitive groups as mentioned above.

4. The author assume the classification model can exactly learn or closely approximate the true probability  $P(Y|X, a)$, which is not always true even with post-training calibration. However, a method that improves the fairness of a model should not have to assume the model's classification accuracy. 

Also, the authors should be careful about using the term "representation learning" to describe their method. Typically, representation learning is to learn a representation of data that provides useful information for various downstream tasks. However, the representation in this work is simply a grid of interval $[0,1]\times [0,1]$, so such a representation is only for this specific binary classification task.

Decision: Reject