Efficient Fairness-Performance Pareto Front Computation
Authors: Mark Kozdoba
Binyamin Perets
Shie Mannor
Venue: NeurIPS 2025 spotlight ()
Keywords: fairness
fair representations
Pareto front
algorithmic fairness
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: Theory of Fair Representations, and a computationally tractable fairness performance Pareto front algorithm.

Abstract: There is a well known intrinsic trade-off between the fairness of a representation and the performance of classifiers derived from the representation. In this paper we propose a new method to compute the optimal Pareto front of this trade off. In contrast to the existing methods, this approach does not require the training of complex fair representation models. 


Our approach is derived through three main steps: We analyze fair representations theoretically, and derive several structural properties of optimal representations. We then show that these properties enable a reduction of the computation of the Pareto Front to a compact discrete problem. Finally, we show that these compact approximating problems can be efficiently solved via off-the shelf concave-convex programming methods. 


In addition to representations, we show that the new methods may also be used to directly compute the Pareto front of fair classification problems. Moreover, the proposed methods may be used with any concave performance measure. This is in contrast to the existing reduction approaches, developed recently in fair classification, which rely explicitly on the structure of the non-differentiable accuracy measure, and are thus unlikely to be extendable. 

The approach was evaluated on several real world benchmark datasets and compares favorably to a number of recent state of the art fair representation and classification methods.

Efficient Fairness-Performance Pareto Front Computation
Mark Kozdoba "I Binyamin Perets "I and Shie Mannor
TTechnion Israel Institute of Technology, Haifa, Israel
NVIDIA
Abstract
There is a well known intrinsic trade-off between the fairness of representation and the performance of classifiers derived from the representation. In this paper propose new method to compute the optimal Pareto front of this trade off. In contrast to the existing methods, this approach does not require the training complex fair representation models.
Our approach is derived through three main steps: We analyze fair representations theoretically, and derive several structural properties of optimal representations. We then show that these properties enable a reduction of the computation of the Pareto Front to compact discrete problem. Finally, show that these compact approximating problems can be efficiently solved via off-the shelf concave-convex programming methods.
In addition to representations, we show that the new methods may also be used to directly compute the Pareto front of fair classification problems. Moreover, the proposed methods may be used with any concave performance measure. This is contrast the existing reduction approaches, developed recently in fair classi- fication, which rely explicitly on the structure of the non-differentiable accuracy measure, and thus unlikely be extendable.
The approach was evaluated on several real world benchmark datasets and compares favorably to number of recent state of the art fair representation and classification methods.
Introduction
Mehrabi Fair representations central topic in the field of Fair Machine Mehrabii al. (2021) Pessach and Shmueli (2022) Chouldechova and Roth (2018). Since their introduction in Zemel et al. (2013), Fair representations have been extensively studied, giving rise 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. (2015), Madras et al. (2018). Gordaliza et al. (2019); Zehlike et al. (2020), SSng et al. (2019), Du (2020), Zhao and Gordon (2022), Jovanović et (2023) Dehdashtian al. (2024). for a sample of existing methods.
For given representation learning problem and target classification problem, since the fairness constraints reduce the space of feasible classifiers, the best possible classification performance will usually be lower 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 given representation learning method, one is often interested in the fairnss--eeffommacce curve (7, E())). Here, 7 is the fairness level, and F((r) is the classification performance of the method at
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

A=0
z
PY--IX-AA-01
PYY=)Ne=AAD))
Pi
PIZEA-= A=D.
x
POY-)IZ-X) - PPO-yyaaaPPoaa
Figure 1: Fair Representation Problem Setting.
that level. The curve E())) where E(7) is the best possible performance over all representations and classifiers under the constraint is known the Fairness-Performann 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 sensitivity to a variety of nyper-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
Perieess-Prffrmmncee curve is close to the true Pareto Front.
In this paper propose new method to compute the optimal Pareto front, which does not require the training of complex fair representation models. 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 number of structural properties. While these properties may be of independent interest, here we use them to express the points on the Pareto Front the solutions of small discrete optimisation problems. These problems, known concave minimisation problems [ensonn (995),, have been extensively studied and can be efficiently solved using modern dedicated optimisation frameworks, Shen et al. (2016).
We now describe the results in more detail. Let X E X' and A E denote the data features and the sensitive attribute, respectively. We assume that A is binary, while X may take values in arbitrary space X' typically with X' = TRd In addition, we have a target variable Y, taking values a finite set V. We then 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 IP (Z x, A a), for {0, 1). The problem setting is illustrated in Figure]]
Our approach consists of three main steps: We first observe that (z, a) X'x A to a much smaller space Ay of distributions on the set of label values V, without loosing any information necessary for the computation of the Pareto front. The mapping is done by means of the optimal Bayes classifier. This result is referred to as Factorization Lemma, Section 3.2. where the mapping done via the optimal Bayes classifier. Similar arguments were recently implicitly used in the study fair classification tradeoffs, (Xian et al. 2023: Wang et al. 2023 but restricted to classification and to accuracy loss (Section 2).
map the data features
The advantage of working with small space such as Ay is that can easily discretized. For instance, if Y 0, 1, then we essentially have Ay = [0, 1]. which is descretised trivially. We note that other, data dependent discretisation schemes, such as clustering, maybe possible for problems involving highly multi label targets. Altematively, one also consider the dataset itself as grid, view that is typically taken by transportation based approaches, e.x. Gordaliza et al. (2019). Xian
et al. (023).
Next, assuming the data discretized and finite, we ask how large the represntation space Z should be, in order to support both optimal performance and fairesss? For instance, we believe the answer to the following question not apriori obvious: Can representations on infinite spaces be approximated, in terms of performance and fairness, by representations on finite and bounded spaces 2? These questions are addressed by the Invertibility Theorem, Section 33 which asserts that all optimal representations may be taken in certain canonical form, which term invertible. This

---

result, in conjunction with an additional approximation lemma, is used in Section 4.1 to construct representations with any desired degree of approximation.
Finally, based on these results in Section 4.1 we also introduce the MIFPO (Model Independent Pairness-Peffommnnce Optimization), discrete optimisation problem that is essentially equivalent to a computation of the fairnss--perfonee performance tradeoff on a discrete set. We show that in this situation MIFPO a concave minimisation problem with linear constraints, and solve it using the disciplined convex-concave programming framework, DCCP, Shen et al. (2016).
We evaluate approach standard faimess benchmark datasets and compare its faimesss- performance curve to multiple state-of tart fair representation methods. We also compare MIFPO to the fairess--pete performance Pareto front of fair classifiers" As expected, MIFPO effectively serves as an upper bound on almost all other algorithms both cases.
fairmes-performance
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 model indepen- dent 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 organised as follows: Section 2 discusses the literature and related work. In Section 3 we discuss the theoretical results. including factorization and the Invertibility Theorem. The MIFPO problem construction and the full Pareto Front computation algorithm are provided in Section 4 Experimental results are presented in Section [ and we conclude the paper in Section 6
All proofs are provided in the Supplementary Material.
2 Literature and Prior Work
We refer to the book Barocas et al. (202)), and surveys Mehrabi et al. (2021) Du et al. (2020), for general overview of representations. Tradeoffss in particular where explicitly studied in Song et al. (2019), Balunović et al. (2022a), Zhao and Gordon (2022), Jovanović et al. (2023) Dehdashtian et al.
(2024). among others.
In this paper we use the total variation based fairness constraints, similarly to the line of work in Madras al. (2018), Zhao and Gordon (2022). [alunović al. (2022a). Jovanović et al. (2023).
Other constraints used in the literature include entropy based constraints, [Song et al. (2019). or RKHS
based independence test constraints, Dehdashtian et al. (2024).
As discussed earlier, the vast majority of the work above concentrates on finding neural network based fair representations via involved optimization schemes with possible local minima, which may be hard to analyze. This highlights the usefulness of our approach direct approach to the computation of the Pareto front, which has clear theoretical grounding, and in which sources of approximation eтror are well understood and may be controlled.
Relations between fairness and performance were studied in Zhao and Gordon 2022). In particular, for perfectly fair representations, they derived lower bounds on the accuracy in terms of the difference of the base rates between the groups. However, this work did not introduce new algorithms for the computation of fair representations or of the associated Pareto front. The extension of the considerations in this paper the full front was carried in Xian et al. (2023) for classification (see below).
The accuracy fairness tradeoff has also been extensively studied in the context of fair classification (without representations), see for instance Agarwal et al. (20T8), Kim et al. (2020) Allghamii et al. (2022). Xian et al. (2023), Wang et al. (2023). for sample of recent approaches. In particular, the papers Xian et al. 2023). Wang et al. (2023) are state of the art, and are also the most closely related to our methods, among the existing work.
Similarly to our approach, the analysis in these two papers starts with the estimation of the prob- abilities P (Y|X, A), which are then used to compute the constrained performance. However, the subsequent steps are different. Crucially, the analysis in both Xian et al. (2023) and Mang al.) (2023) relies critically on the properties of the accuracy as the performance metric. Consequently,
'See Sections 2 and 3.2 for the relation between our representation framework and fair classification results.
3

---

it can not be extended to general concave performance measures, such as the standard (minus) log loss, for instance. Roughly speaking, the appropriate sense, accuracy largely ignores classification probabilities. This allows the simple description of classifiers as small confusion matrices in Wang al.] (023) (extending the approach of Kim et al. (2020), and the restriction of the distributions to the vertices of the simplex in Xian et al. (2023). The special structure of accuracy is highlighted also in our Lemma [.I] where we show that classifiers with accuracy may be effectively described by representations using only 2 points. We conclude that even when restricted to classification, our approach analyses a fundamentally more complex situation compared to previous work. On the other hand, Xian et al. (202)) and Wang et al. (2023) support non binary sensitive attributes and group labels, while such an extension for our methods is out of scope for this paper. A comparison of computational complexities for these algorithms may be found in Supplementary J
3 Structure of Fair Representations
In this Section we describe several theoretical properties of fair representations. In Section 3.1 we introduce the problem setup and the necessary notation. In Section (32 we discuss relations to classification with accuracy loss and the factorization result, which allows to reduce the size of the representation space. The Invertibility Theorem is introduced in Section 3.3
3.1 Problem Setting
Let A be a binary sensitive variable, and let X be an additional feature random variable, with values in set X' typically with X' = =d. Assume also that there is target variable Y with finitely many values a set V. jointly distributed with X, A.
A representation Z of (X, A) is defined as a random variable taking values in some space 2, with (i) distribution given through Pe (Z) Ix, A), where 0 are the parameters of the representation, and (ii) such that conditioned on (X, A), Z is independent of the rest of the variables of the problem. In particular, we have
LLY A(,,
where denotes statistical independence.
Fairness in this paper will be measured by the Total Variation distance. For two distributions, μe, on Rd, with densities fur for respectively, this distance is defined as
/ g(x) (n(()) - fc(x)] de sup
= / - (u(x)) -t
|/ - Ullrv g gx |I
(2)
Note that (ff( fz)) dr is in fact the L, distance, and the equivalence 11-11rv 111-11,, is well known, see Cover and T'homas (2012).
(Z For E 1). let Pa be the distribution of 7 given A = i.e. (aa()) = P = ||A= = a). We denote the distance induced by the representation as Drv (Z) = || - 11 mIllTv, and for 7 2 0, we say that the representation Z is f-ir iff
Drv ()) I|uo - pi LIv S (Fairness Condition).
Note that 33 is a quantitative relaxation of the "perfect fairness"' condition in the sense of statistical parity, which requires Z 1L A. Specifically, observe that by definition, 2 J.L A iff (3) holds with 7 = (i.c. Ho = M1). In addition, as shown in Madras et al. (2018). (3) implies several other common faimness criteria, in particular, bounds 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 Ay > be a continuous and concave function on the set of probability distributions on y, Ay. The quantity h(P (Y = x²)) will measure the best possible prediction accuracy of Y conditioned on X = for varying x. As an example, consider the case of binary Y. y = {0, 1}. Every point in Ay can be written (p, p) for E [0, 1J. and we may choose h to be the optimal binary classification error,
h((1 p)) min(p, 1 p).
Another possibility it to use the entropy, 1i((1 - p.P)) = p log + - pl)y)l - p). The average uncertainty of Y is given by (x-xh(P (Y X ==)). Note that this notion does not depend on

---

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 given 2 satisfy the constraint and under that constraint minimize the objective F. Fg given by
E ((P (YIZ =z)).
(5)
That is, the representation should minimise the optimal Y prediction error (using 2) under the faimeess constraint.
The curve that associates to every 0 I I 1 the minimum of (5) over all representations which satisfy (3) with y referred as the Pareto Front of the Chirness-Performaand trade-off.
In supplementary material Section A we show that for any representation, Ez-zh(P (Y - =)) 2 Ex (Y = z)), i.c. representations generally decrease maintain the performance.
3.2 Classification and Factorization
In this section we show that the Pareto front of binary classifiers, with accuracy performance and statistical parity fairness measure, can be computed from the Pareto front of representations with total variation fairness measure. In fact, Lemma 3.1 below states that both Pareto fronts amount to the same curve. As discussed in Section this equivalence implies that MIFPO can be used to evaluate fair classifiers, in addition to fair representations.
For binary classifier Y of Y, with (X, as features. The prediction error defined as usual by e(P) IP + xY) The statistical parity of Ý is defined
Dsr(P): = PP 1|A 11111) PP - 1|4=)
1|
(6)
Lemma 3.1. Let Y be classifier of , let the representation uncertainty measure be given by (4)
Then there is representation given by random variable Z. on set 2 with |2| = 2, such that
Er-zh(P ( =)) S <P and llvo - -illry S DV)
Conversely, for any given representation Z, there is classifier V of a function of Z (and thus of (X, A)), such that
( S Rz =)) and Dsp(Y) ||p0 millr-
The Proof of Lemma 3.1 is presented in Supplementary Material Section !
We now describe the Factorization result. Let f* :'' A Ay be the Bayes optimal classifier of given X, A. That is, for every I E X, E A, fz, a) is the conditional distribution of Y given n, a, i.e. f"
P (Y = -|X x. A = a). Denote by (X', A) new pair of random variables, taking values in Ay x A, given by (X', A) = (S"(X, A), A).
Lemma 3.2 (Factorization). For any representation Z of (X,A), there is a representation Z' of (X', A). such that
E. E. (P = 2 < E(P 2)) and Drv & (Z).
(9)
In words, for every representation Z. we can find a representation Z' that only accesses (z, a) through the value f (zx a). and is at least good in terms of both fairness and performance. Equivalently, this means that any two points (I1, a) and (x2, a) with coinciding conditional Y distribution may be treated identical for the purposes of constructing optimal representations. As result, to find optimal tradeoffs, we can only consider the representations Z' on the small space Ay x A, rather than Z on the much bigger space X' A.
Observations related to Lemma 3.2 were made the context of classification in Kim al. 2020 Xian
et al. (202)), and Wang et al. (003)), which also start from the Bayes optimal classifier. Lemma 3.2 generalizes these observations to representations and general losses. The proof may be found in
Supplementary K
5

---

B
ACS
ACS US
Health
A=0
A-1
Frequency
92
6,00
P(Y)
(a)
(b)
Figure 2: (a) The MIFPO Setting (b) Distribution P(Y = 1(x,A) A) for each group across datasets.
3.3 The Invertibility Theorem
In this section we define the notion of invertibility for representations, and show that considering invertible representations is sufficient for computing the Pareto front.
representation Z on set Z is invertible if for every 2 E Z and every E {0. 1}, there is at most one x E X' such that IP (Z 2|XX = A = a) > O. In words, a representation is invertible, if any given can be produced by at most two original features (z, a), and at most one for each value a. For E 2, we say that an (æ, a) is parent of if FF (Z x|X
A = a) > 0.
Theorem 3.1. Let Z be any representation of (X, A) on a set Z. Then there exists an invertible representation Z' of A), some set Z', such that
22''2 h(P (Y = =z)) < (T (Y = 2)) and Drv (Z)
(10)
In words, for every representation, we can find an invertible representation of the same data which satisfies least good faimess constraint, and has at least good performance 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 has more than one parent for a fixed a, then can split this atom into two, with each having less parents. However, the details of this construction are somewhat intricate and the full argument can be found in Section
Although in this paper we concentrate on the case of binary sensitive variable, we note that Theorem 3.1 may extended to multi valued attributes, with similar argument. In that case, invertibility would mean that every E Z would still have at most two parents, corresponding to different values a, a' of A.
The Model Independent Optimization Problem
In this Section we motivate and introduce the MIFPO optimisation problem, and then discuss the full Pareto front computation procedure starting from the raw data.
4.1 MIFPO Definition
For the purposes of this Section, we assume that the x feature space is finite. the next section, Section 4.2 deseribe how we obtain such finite spaces by using the factorization result and discretizing Ay. Note, however, that the full original, possibly high dimensional feature space X', is never discretized.
Write S, = (xx 0) E E XXxx X {0), and similarly S₁ = X' x {1), for the two halves of the full feature space, X' x A = So U1.
The MIFPO parameters model data distribution and are as follows: (a) the probabil- ity distributions 30 As, and 31 E As. on So and S, respectively, modeling P. ((X. A 0) and IP ((X, A)]4 1) respectively, i.e. the distribution of the data features on each sensitive sub- group. (b) The subgroup proportions a, (AA = a), and (c) the conditional Y distributions.
Parameters:

---

Pu.Pr E Ay, modeling Pa = P P( = ((X, = u) when a = 0 or Pe = P (Y (X =)
when a
Representation Space: Perhaps the first question one can ask when constructing representation of
the data as above is: How large the representation space should be? We now answer this question using the theory of Section 3
Fix an integer k 2 2. The representation space Z will be a finite set which can be written
2 = So x S x [A:],
(11)
Z corresponds some triplet (u, v,j), with u E So, u E $1,j E [k. To explain this choice, recall that by the Invertibility result, we know that we may consider only invertible representations. In such representations, every point E 2 is indexed by a pair of parents (u, v) E So x S1, suggesting that we may index the points by So x Si to begin with. Next, for given such pair (u, v). we may ask how many points = should have the same pair (u, u) as their parents? In Supplementary Section D we show that using k points for every pair, we can obtain uniform approximation over all representations. That is, given degree of approximation é, Lemma D.I provides bound on & which is sufficient to obtain such approximation. While such bound would clearly depend on E, we not that does note depend on the sizes |So] |S1]. These considerations explain the choice of (IT) as the representation space. We have used k = 5 in all experiments.
where [=] := 11.......Kk k). That is, every point
Variables: The variables of the problem model the representation itself. They will be de- noted by ra,n.j for (u, U. E 2 and E A, and model the probabilities ru,o
So. or a 1 and for some v E X. That is, for a = O, points u transition to (u, v. for some E Si, E [k]. and similarly for
P = (u, v. (XX A) =s), where either a 0 and
Si
points v transition to (u, j, for some X, E [k).. This notation preserves our convention that (u, v, E Z has u and v as its only parents. The situation is illustrated in Figure aa...
Note that the variables represent probabilities, and thus satisfy the following constraints:
T.oo 2 V(u, v,j) 2, Va A
(12)
a...j
Vu E So and SESO
Σ
Ta,es
E
(13)
Performance Objective and Fairness Constraints: With these preparations, we are ready write the performance cost (5) in the new notation:
( a. (1) a08o(u)r a.ss + 8, (v)r u.v.j
E
Σ 2= ()
[ooBo(u)ra + (()
(14)
Indeed, observe that due to the structure of our representations, every has two parents, and we have P (Z = =) = (u) u.ou + (v)r, (...)) Similarly, P PYY|Z Z =) is computed via
P (Y Σ P (Y 2 (a, x|2)
Σ (Y (= la, xr) (a, (P)
and substituted inside obtain 14). As we show in Supplementary E the cost 14 a concave function of the variables r.
We now proceed to discuss the fairness constraint. Recall that we define pa(z) P (Z 2|A a). for a E (0, 1}. For 2 = (u, j. we have then pa((u, v.r)) = (u(u) ammjj for E {0, 1), and we write
Drv (Z) = l|po #1 pill = Σ [mo()) n1 (z) = 2
Σ 1 -1:(0) (15)
2
(w,es)
and the Fairness constraint, for given 7 E [0, 1). is thus simply
(B(()) (1(v)r 57
(16)
2 (u,e.))
We now summarise the full MIFPO problem.
7

---

Definition 4.1 (MIFPO). For a fixed finite ground set X x A Ur, the problem parameters are the weight agg. the distributions So 3,, on Sn and S₁ respectively, and the distributions P= E Ay for every E So U1. The problem variables are (ru.e.:"' "u,v. (a.e.))ez as defined above. We are interested in minimizing the concuve concuvefunction
14 subject to the constraints
12 and 16
The relationship between MIFPO and the Optimal Transport problem is detailed in Supplementary
Finally, observe that the MIFPO constraints above linear, with (16) being equivalent to two linear inequality constraints. We note that these constraints may be replace by equivalent linear equality constraints, via appropriate slack variables, which is more convenient in practice. See Supplementary for details.
4.2
The Full Algorithm
In this Section we summarize the full Pareto front computation algorithm, including the estimation of the MIFPO parameters ar and p as discussed above.
a; = a}, so that Let D = [(((,, a:), y1) be the dataset, and write Da = [((Fx, a.), E
D Do C D1.
The algorithm proceeds in the following steps: Step 1: we learn the probability estimators co. g Ay. separately on Do and Dj. These estimators should approximate the optimal Bayes classifier (Section 3.2p. Note that such estimation of probabilities is well studied, and is known as calibration, see Niculescu-Mizii and Caruana (2005). Kumar et al. (2019). (Berta et al. 2024).
Step 2: (Discretization and Parameter estimation) For a given integer L > O, the space Ay is discretized into L bins. This corresponds to taking the ground sets So.Si in MIFPO to be of size L. The data Da is then mapped into the I, bins using ca- The distribution (w) is then simply measures the proportion of points (ca()) (a,a)eD, that fall into bin S L.. Finally, for every bin w, we choose an arbitrary point inside that bin as the representative distribution, Pw- The parameters de are estimated simply by aa |Dal / DJ. Note that for binary Y, Dy is simply the interval [o, 1], which is trivial to discretize. See Figure Z(b) for an example of such histograms on real data. We note that one could easily consider more complex discretization schemes, such as clustering, which could be applied efficiently multi label problems. See Supplementary D for a discussion.
Step 3: For a given a fairness threshold 7 > O, we can now construct the MIFPO instance. Definition 4.1, with |So| [S] I., the additional approximation parameter k; and a, B, p discussed above. As discussed in Section 4.1, we found it sufficient to use k = 5 throughout the paper. The MIFPO is then solved using the existing methods, as detailed in Section 5 The full algorithm is schematically
show as Algorithm[1 [1
Supplementary H.
5
Experiments
Our approach requires two main computational components: building calibrated classifiers to evaluate Ca, and solving the discrete optimization problem described in Section For the calibrated classifier, we have used XGBoost (Chen et al. in skleamn, PPedregosa et al.] (2011). l). Next, as discussed in Sections | 4.1 MIFPO is a concave minimisation problem, under linear constraints. To solve its, we have used the DCCP framework and the associated solver (Shen et al. 2016 2024), which are based on the combination of convex- concave programming (CCP) and Boyd (2016) and disciplined convex programming, Grant le al. (2006). We note that although local minima are theoretically possible, the above framework well-established, and the concave structure can be exploited to allow finding optimal solutions in most practical cases, (Shen et al. 2016). In particular, our results do not indicate local minima issues. However, it may also be worth noting that MIFPO could in principle be also solved with the classical faanch-nnd-ouun methods, Benson (1955, which may be slower but do guarantee the global optimum solution.
2015). with Isotonic Regression calibration, as implemented
Throughout the experiments, we use the missclassification error loss h given by Additional implementation details may be found in Supplementary Section H
Our experimental validation MIFPO encompasses three standard fairness benchmarks: the Health datasct alongside two variants of ACSIncome one restricted to California (ACSIncome-CA) and
8

---

Health
ACSIncome-CA
ACSIncome-US
0.2
0.2
Statistical Parity
0.5
0.13
0.15
0.4
0.2
0.05
0.05
0.1
Accuracy
MIFPO SSipm
Fcrl
FnF
Cvib Fare
Figure 3: Comparison of Surmess-accuragee trade-offs across three benchmark datasets: Health (left), ACSIncome- CA (middle), and ACSIncome-US (right). MIFPO's Pareto front is represented as solid line with markers. The horizontal axis represents the fairness constraint (statistical parity distance), while the vertical axis shows prediction accuracy.
another spanning the entire United States (ACSIncome-ul US). Figure we evaluate MIFPO against five state-of-the-ar fair representation techniques: CVIB (Moyer et 2019), FCRL (Gupta al. 2021). FNF (Balunović et al. 2022b), sIPM Kimm et al. 2023). and Fare (Jovanović et al. (023).
tuned across diverse hyperparameter settings to generate a spectrum of representations balancing fairness and accuracy. Moreover, we evaluated MIFPO against several fair-classification methods on multiple datasets as presented in the Supplementary Section H
Each competitive approach
The empirical results presented Figure 3 demonstrate MIFPO's effectiveness relative to prior approaches. MIFPO consistently achieves performance equal superior than the baseline methods across almost all operating points. Furthermore, MIFPO provides a significant methodological advantage through its ability characterize the complete Pareto frontier. In the figure, MIFPO's performance is visualized as solid line with points that trace the entire Pareto front, while com- peting algorithms are represented as individual points corresponding different hyperparameter configurations.
5.1 Implementation
All evaluations
can be
found
https://github. http://gitthub.cooom6666722
Efficient-Farr-Paett--
The MIFPO algorithm's source code is available in the the
repository. The algorithm is also implemented "FairPareto" Python package on PyPI, which provides a scikit-learn compatible API for computing optimal fairness perness-prformancee Pareto fronts. The package supports two usage modes: a tabular mode with automatic classifier training and calibration given a sensitive attribute column, and second mode for any data type (images, text) where users provide pre-trained classifiers for each sensitive group. This enables researchers to benchmark their fair classification methods against theoretical optimality with minimal code and make informed decisions about cüiress--performen trade-offs. The package is open-source, available on PyPI, and includes comprehensive documentation with examples for both tabular and image data.
https:/// //gi wwt.gttttuuu...o httpaa/....oopp////aaaaare.ae
Conclusions, Limitations, And Future Work
In this paper we have introduced new fundamental properties of optimal fair representations, In particular, these are the first theoretical results that allow approximation of the Pareto front for arbitrary concave performance measures. We have used these results to develop a model independent procedure for the computation of Piirness-Performance Pareto front from data, demonstrated the procedure on real datasets, and have shown that may be used as a benchmark for other representation learning algorithms.

---

We now discuss limitations and few possible directions for future work. This work primarily concentrated on binary sensitive attribute and binary Y. with the aim to develop the underlying new principles in the simplest case first. As discussed earlier (Sections) D the multi-label case may be treated by more elaborate discretizations. We also noted that the Invertibility Theorem holds for multi valued sensitive attributes as well, which allows to extend the approximation analysis to that case too. Both of these steps, however, would increase the MIFPO problem size. On the other hand, it is also worth noting that this size does not depend directly neither on the feature dimension d, nor on the sample size N and thus the problem scales well that sense.
In view of these observations, we believe it would be of interest to study the following question on the true complexity of the tradeoff evaluation: Suppose we are given access the Bayes optimal classifier of the data, f*. This encapsulates, in a sense, most of the "continuous" information of the problem. Then, how scalable can Pareto estimation methods be made theoretically, terms of [)), [A), while still maintaining controllable approximation bounds?
Acknowledgments and Disclosure of Funding
This work has received funding from the European Union's Horizon Europe research and innovation programme under grant agreement No. 101070568.
Bibliography
Agarwal, A., Beygelzimer, A., Dudík, M., Langford, J., and Wallach, H. (2018). reductions approach to fair classification. In International conference on machine learning, pages 60-69. PMLR.
Alghamdi, W., Hsu, H., Jeong, H., Wang, H., Michalak, P., Asoodeh, S., and Calmon, F. (2022). Beyond adult and compas: Fair multi-class prediction via information projection. Advances in Neural Information Processing Systems, 35:38747-38760.
Balunović, M., Ruoss, A., and Vechev, M. (2022a). Fair normalizing flows. In The Tenth International Conference Learning Representations (ICLR 2022).
Balumović, M., Ruoss, A., and Vechev, M. (2022b). Github for fair normalizing flows.
https
7/gi wtw.eo/oeeeeeeeeeeee
www./thhsaeeeecccooeooeceeeeeeee eth- sri/fff.
Barocas, S., Hardt, M., and Narayanan, A. (2023). Fairness and machine learning: Limitations and opportunities. MIT Press.
Benson, H. P. (1995). Concave minimization: theory, applications and algorithms. In Handbook of global optimization, pages 43-148. Springer.
Berta, E., Bach, F., and Jordan, M. (2024). Classifier calibration with roc-regularized isotonic regression, In International Conference on Artificial Intelligence and Statistics, pages 1972-1980. PMLR.
Chen, T., He, T., Benesty, M.. Khotilovich, V., Tang, Y., Cho, H., Chen, K.,, Mitchell, R., Cano, I.,
Zhou, T., et al. (2015). Xgboost: extreme gradient boosting. R package version 0.4-2, 144):1-4.
Chouldechova, A. and Roth, A. (2018). The frontiers of fairness in machine learning. arXiv preprint 1rXiv:1810.088/00
Cover, T. M. and Thomas, J. A. (2012). Flements of Information Theory. John Wiley & Sons.
Cruz, A., Belém, C. G., Bravo, J., Saleiro, P., and Bizarro, P. (2023). Fairgbm: Gradient boosting with faimess constraints. In The Eleventh International Conference on Learning Representations.
Dehdashtian, S., Sadeghi, B., and Boddeti, V. N. (2024). Utility-fairness trade-offs and how to find them. Proceedings of the IEEF/CVF Conference on Computer Vision and Puttern Recognition, pages 12037-12046.
10

---

Du, M., Yang. F., Zou, N., and Hu, X. (2020). Fairness in deep learning: A computational perspective. IEEE Intelligent Systems, 36(4):25-34.
Fefferman, C., Mitter, S., and Narayanan, (2016). Testing the manifold hypothesis. Journal of the American Mathematical Society, 29(4):983-0049
Feldman, M., Friedler, S. A.. Moeller, J., Scheidegger, C.,, and Venkatasubramaniaa. S. (2015). Certifying and removing disparate impact. In proceedings of the 2/th ACM SIGKDD international conference on knowledge discovery and data mining, pages 259-268.
Gordaliza, P., Del Barrio, E., Fabrice, G., and Loubes, J.-M. (2019). Obtaining fairness using optimal transport theory. In International Conference on Machine Learning, pages 2357-2365. PMLR.
Grant, M., Boyd, S., and Ye, Y. (2006). Disciplined comvex programming. Springer.
Gupta, U., Ferber, A. M., Dilkina, B., and Steeg, G. V. (2021). Controllable guarantees for fair outcomes via contrastive information estimation.
Jang. T., Shi, P., and Wang. X. (2021). Group-aware threshold adaptation for fair classification. CoRR, abs/2111.04271.
Jovanović, N., Balunovic, M., Dimitrov, D. I., and Vechev, M. (2023). Fare: Provably fair representa- tion learning with practical certificates. In International Conference on Machine Learning, pages 15401-15420. PMLR.
Kim, D., Kim, K., Kong, I., Ohn, I., and Kim, Y. (2023). Learning fair representation with parametric integral probability metric.
Kim, J. S., Chen, J., and Talwalkar, A. (2020). Fact: A diagnostic for group fairness trade-offs. In International Conference on Machine Learning, pages -2744. PMLR.
Kumar, A., Liang. S., and Ma, T. (2019). Verified uncertainty calibration. Advances in Neural Information Processing Systems, 32.
Lipp. T. and Boyd, S. (2016). Variations and extension of the convex-coneave procedure. Optimization and Engineering. 17:263-287.
Madras, D., Creager, E., Pitassi, T., and Zemel, R. (2018). Learning adversarially fair and transferable representations. In International Conference Machine Learning, pages 3384-3393. PMLR.
Mehrabi, N., Morstatter, F., Saxena, N., Lerman, K., and Galstyan, (2021). survey on bias and fairness in machine learning. ACM computing surveys (CSUR), 54(6):1-35.
Moyer, D., Gao, S., Brekelmans, R., Steeg, G. V., and Galstyan, A. (2019). Invariant representations without adversarial training.
Niculescu-Mizil, A. and Caruana, R. (2005). Predicting good probabilities with supervised learning. In Proceedings of the 22nd international conference on Machine learning, pages 625 2622.
Pedregosa, F, Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M.,
Prettenhofer, P., Weiss, R., Dubourg. V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E. (2011). Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830
Pessach, D. and Shmueli, E. (2022). A review on faimess in machine learning. ACM Computing Surveys (CSUR), 5-43):1-444.
Peyré, G., Cuturi, M., et al. (2019). Computational optimal transport: With applications data science. Foundations and Trends@ in Machine Learning, 11(-66)3555-07.
Saleiro, P., Kuester, B., Stevens, A., Anisfeld, A., Hinkson, L., London, J., and Ghani, R. (2018). Aequitas: A bias and fairness audit toolkit. arXiv preprint 1..0577
Shen, X., Diamond, S., Gu, Y., and Boyd, S. (2016). Disciplined convex-concave programming. In
2016 IEEE 55th conference decision and control (CDC), pages 1009-1014, IEEE.

---

Shen, X., Diamond, S., Gu, Y. and Boyd, S. (2024). Github for disciplined convex-coneane programming. https://githut com/ cvxgrp/dccp//
Song, J., Kalluri, P., Grover, A., Zhao, S., and Ermon, S. (2019). Learning controllable fair repre- sentations. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2164-2173. PMLR.
Wang, H., He, L.,, Gao, R., and Calmon, F. (2023). Aleatoric and epistemic discrimination: Fun- damental limits of fairness interventions. Advances in Neural Information Processing Systems, 36:27040-27062.
Wang. H., He, L. L., Gao, R., and Calmon, F. P. (2024). Aleatoric and epistemic discrimination: fundamental limits of fairness interventions. NIPS '23, Red Hook, NY, USA. Curran Associates Inc.
Xian, R., Yin, L.,, and Zhao, H. (2023). Fair and optimal classification via post-processing. In International conference on machine learning, pages 37977-38012. PMLR.
Zehlike, M., Hacker, P., and Wiedemann, E. (2020). Matching code and law: achieving algorithmic faimess with optimal transport. Data Mining and Knowledge Discovery, 34(1):163-200.
Zemel, R., Wu, Y., Swersky, K., Pitassi, T., and Dwork, C. (2013). Learning fair representations. In Dasgupta, S. and McAllester, D., editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 325-333, Atlanta, Georgia, USA. PMLR.
Zhao, H. and Gordon, G. J. (2022). Inherent tradeoffs in learning fair representations. Journal of Machine Learning Research, 23(57):1-26.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
All claims supported in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: discussion may be found in Section 6 as well as in Section 2 in context of comparison to other methods.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification:
All results are formally stated and have proofs in the Supplementary.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All information on reproducibility is included in Section S and corresponding Supplementary sections. The full code will be published with the final version of the paper.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [No]
Justification: While we describe all reproducibility details, the full code will be published with the final version of the paper. The datasets used publicly available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/ public/guides//e
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//ips.cccpublic/guideee wwwpee//guiie//eee Soaess/ooooeSesiiooono..o
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We supply all the necessary details for the reproduction of the results. Further- more, the full details will be included as part of the published code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The methods discussed in this paper produce identical results over multiple runs (std <= le-5). We note that for some benchmark methods we have used existing evaluation results; however, the authors of those evaluations claim to have conducted multiple runs to validate stability, and the results presented on the graphs are from different hyperparameters as an integral part of the analysis.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative етrоr rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, relevant information is provided in the Supplementary. We note that all experiments of this paper together run in under day on standard desktop.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https:
Answer: [Yes]
Justification: We have examined the Code of Ethics and verified that the research conforms with the code.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
This work is in Faimess, with obvious societal impact implications. However, while our approach is algorithmically new and can provide practically and empirically better evaluation of hhiness-performmane tradeoffs, the general socictal implications of such tradcoffs are well understood the field and we believe require no special new consideration in this particular work.
Guidelines:
16

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do see reasonable scenarios in which release of our code may be risky.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All assets are precisely referenced.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
17

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, batasets.papersstt paperswi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We do not release assets this time. As mentioned earlier, the implementa- tion of the methods in this paper will be released with the final version of the paper.
Guidelines:
The answer NA means that the paper does not release assets. Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing or reesearch with humans.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
18

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: This research does not involve LLMs any important, original, or non- standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
19

---

Supplementary Material
Monotonicity of Loss Under Representations
20
MIFPO and Optimal Transport
21
Proof Of Theorem 3.1
21
Uniform Approximation and Two Point Representations
25
Concavity Of E,
27
MIFPO Equality Constraint
28
Additional Proofs
28
H
Experiments
29
Implementations and computational details
2 Additional Evaluations
30
H.3
Minimization of Concave Functions under Convex Constraints and the Entropy Loss
31
Fair Classifiers As Fair Representations
33
Computational Complexities
34
Factorization
34
A Monotonicity of Loss Under Representations
As discussed in Section 3.1 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), A), every representation as above, and concave
Ez-zh(PP ( =)) 2 (XE.))-(XX,)) = a)).
(17)
Note that the right hand-side above can be considered a "trivial" representation, 7 A).
In what follows, to simplify the notation we use expressions of the form P' (x, a/z) to denote the formal expressions IP (X- x, A alZ z). whenever the precise interpretation is clear from context.
Proof. For every value E D, we have
P(Y = y = 2) 2)= Ef dr P(Y = y|,,
OP (rraa 2) dr OP (x| (a|z)
(a|z)
(18)
Σ f dr P(Y = = a)
(19)
dr
(x..)) P (Y
w| a)
(20)
Here, on line 18) 8P(z)a.2) the density of P (xla, 2) with respect to dr. Crucially, the transition
dr
from 18 to 19 is using the property (I) The transition 19 to (20) is change of notation. Using
20

---

20 and the concavity of h, we obtain
Ez (YIZ = =z)) 2,-=2(eaa))(xx)))=====
(21)
= -xx,))-(xx (Y z, = a)).
(22)
B MIFPO and Optimal Transport
In this Section we discuss the relation between the MIFPO minimisation problem, Definition 4. and the problem of Optimal Transport (OT). General background on OT may be found in Peyré et al. (011). We discuss the similarity between OT and the minimisation of (14) under the constraint (16 with ? 0, i.e. the perfectly fair case. In this case, {16) is equivalent to the condition 3o Bo(u) 3: (v)r for all (u, v, E Z. Next, note that thus in is case the expression for P( 7 (0,,,(,,,,,, (u,
Pu Pa + 32 (u)olu)ra,,,, + (1)r,an
Pu + P.01
(23)
ag + a1
and this independent of the variables r! Therefore we can write the cost 14) as
E(ao+ 1A
+ pr0l ( 1
Σ
Bolu)runoss + (1(())
(24)
2
ag 01
.is
Note further that for fixed u, v, the different j's in this expression play similar roles and could be effectively merged single point.
The cost (24 has several similarities with OT. First, in both problems have sides, So and Sj, and we have a certain fixed loss associated with "matching" to and v. In case of (24). this loss is (ao + +a))
which describes the information loss incurred by colliding u and representation. And second, similarly to OT, (24) is linear in the variables r. Linear programs conceptually considerably simpler than minimisation of the concave objective (4).
2=00+p.0 ao+t
C Proof Of Theorem 3.1
In this Section we prove Theorem
To keep the notation and the main argument concise, we prove the result under the assumption that (X, A) is finitely supported. Since no assumptions are made on the cardinalities of the supports, the general measurable case follows by standard approximation arguments.
We now introduce the additional notation necessary for the proof. Let So. S, be finite disjoint sets, where S, represents the values of (X, A) when = a, for E {0, 1}. Denote S = So U Sj. We are assuming that there probability distribution ( S, and A is the random variable A 1 (.ES.)- X is defined as taking the values S, with P (X s) {(s). Further, the variable Y is defined to take values in a finite set V. and for every s S. its conditional distribution is given by Pa E Ay- That is, IP (Y y X A a) p. (v( pr.a (v). This completes the description of the data model.
For (0,1) we denote a. P (A= a) = ((S.), and Ba(s) P P(X = = a). Observe that (s) = 0f s & S.. and (a(s) = <(s)/C(S.) if s S..
We now describe the representation. The representation will take values in a finite set Z. For every s and Z, let (z, (Z 2 X s, A a) be the conditional probability of representing as 2. T2 are sometimes referred as the transition kernels of the representation. For
NNote that there a slight redundancy the notation by 8. However, to retain compatibility with the standard notation, literature, 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.
y|X s, A a) here, since is determined
21

---

fixed A), the Ta 's fully define the distribution of the representation Z and we shall refer to the representation as T as Z in interchangeably. Finally, for {0. 1) denote
Ma(2) =. = P 2|A a) a) Σ (o(s)
(25)
.ES
With the new notation, a representation T' is invertible if for every & E 2 and every E {0, 1}, there most one s S2 such that Ta (z, s) > O. In words, a representation is invertible, if any given can be produced by at most two original features s, and at most one in each of So and S1.
Given a representation T and 2, we say that appropriate a.
is parent of if Ta(2, s) > 0 for the
Proof Of Theorem 3.7
Assume T' is not invertible. Then there is E Z which has at least two parents in either So or St. Assume without loss of generality that z has two parents in So. Let
be the sets of parents of = S. and S respectively. Chose point v E U, and denote by U = M²} 8)
U {s So 0), = E | Ti > 0}
(s
(26)
the remainder of U. By assumption we have |0" 2 1. We also assume that [V] > O. The easier case [V] = 0 will be discussed later.
Now, we construct new representation, TV. The range of T" will be Z' = 2 (z',2"} That is, we remove z and add two new points. Denote
Bo(x)To(2xx)
k == P. (=|2,a==
(27)
E.EU (0(8)To(2,8)
Then T" is defined as follows:
s) = (h)
for all a E {0, all s E S and all h E Z {2}
T) = x)
Th(2", uu) u))
for all U" for all V for all V.
(28)
Ti('',) xTi(Z,0)
Ti(=", = -(1-x)Ti(Z;))
All values of T' that were not explicitly defined in 28 set to O. In words, on the side of Sp, move all the parents of z except x to be the parents of 2",, while will have a single parent, x. On the S1 side, both z' and =" will have the same parents respectively. The multiplication by x. is crucial for showing both inequlaities in (10).
with transitions multiplied by and 1
Note that 7" can be though of as splitting into z' and z", such that z' has one parent on the So side, and z" has strictly less parents than 2 had. Once we show that T' satisfies (10). it is clear that by induction we can continue splitting 7" until we arrive at an invertible representation which can no longer be split, thus proving the Lemma.
In order to show 10) for T", we will sequentially show the following claims:
=P (z') + (x") and P (x') = =KP (z) P( =
(29)
= ( for a E {0,
(30)
for 1
(s) = P (s) [P(x)z',
VsES
()))=",a)= =0
(31)
for s. Ur
(P(s)2 =0 (ss)2",)) = -1-x) -1p((aa))
P(Y = xP (1
(32)
2 (P)) "P"
(33)
[mo(2)- - (x)) = (/((=) -<(=="><<<=""))
(34)
Here the probabilities involving =",=" refer to the representation T". Observe that the left hand side
of (33) is the contribution of to the performance cost EE (Y)Z = t)) of T, while the right
22

---

hand side of (33) is the contribution of 2', x" to the performance cost of T'. Since all other elements t Z have identical contributions, this shows the first inequality in (TO.. Similarly, recall that
1 2 Σ YEZ
M10 PIllTv
(u(() (2(()),
(35)
2
and thus the left hand side of (3 is the contribution of to I| ju rv with the right hand
side being the contribution of llnó pillry, therefore yielding the claim I - Pillrv
I|oo Pa lilly.
Claim 29 : By definition,
P(e') = 00 +01 Σ (1())
(36)
sEV
(2) + Kαj
Bi (s)
(37)
sEV
K0g
Σ 8o(s)76(2,8) + k0
Σ (2))
(38)
SEU
sEV
xP (=).
(39)
Similarly, by definition we have
P(=") 0z Σ Bo())To(228) + - kx)ka Σ (s)
(40)
SEV
and summing this with 37 we obtain PP (x) = P (=') + (z").
Claim (30): Note that it is sufficient to prove the claim for a = since the probabilities sum to 1.
Write
P (a- 0/2) = (aa = 0,2)
(41)
P(2)
ao Ever (o(s)To(2,s)
(42)
(2))
k a0 E,Et (o(s) 8)
(43)
K (2)
(1)6(z)Ta(2.
(44)
= (a = 0|2²).
(45)
Similarly,
P (a- = 0,2)
PP (a- = 0|2) =
(46)
(2)
0o EvEr (0())))(2)8)
(47)
((2)
(1 k) ag Σ EEU (o())T((z)
(48)
(1 K) P())
00 Σ Exer (0(8)To(zz5)
(49)
P ((=")
P (a = 012").
(50)
23

---

Claim 31 : For a = 1, let us show P (()|2,a) = P(s|z', .a).
a151(5)Ti
P(s|z, a = 1)= Evev (1(5))
(51)
(52)
R01 Evev (1(8))((222))) a131 8)
(53)
a1 Eve (1(s')T s')
=s|='',
(54)
The statement IP (s|z, a) = (s|x", a) is shown similarly. Next, for a O, we have P(x|=', =
and P (z||=", a) 0 by the definition of the coupling T'. Moreover, for E U", (s|l2' 0 also
follows by the definition of TV. Finally, write
(o8 .8)
P ((s|2", a = 0) = EeEU. 30 (T s')
(55)
(n (8) (o
(56)
E EEU 30.3 (2)
(s) 8)
(57)
k) E.er 00,0 (8))o())) x) (s|22, 0)
(58)
Claim 32
We first observe that for any representation (and any z).
P (Y = y| = 2) = Σs. s.a P (Y = 8,,
(59)
P (())
Σ.a PY P(,
(60)
((z)
(all))
PP
- (sla,
(61)
LeESa
where we have used the property
I for the transition
59
660). Now, using for we have
Σ P( a Ps = 1, P( y/s, (sla 1,2²)
SES1
sES1
Σ yys 1) 1,²").
(62)
SES.
For = 0, we have for z' using 31
= u/2. a = 1).
(63)
sESu
For and z" we have
= 1)PP P(Y- y|s, 1) 1 Σ PY a/ =/) 1,2")
(64)
#E8p
k) Σ P(Y y|s, Ps [s|a= 1,2)
SEU
(65)
where we have used (31) again on the last line.
Combining 62 63
65
and using 300 and the general expression 61
we obtain the claim
32
Claim 33 This follows immediately from 32 by using 29 and the concavity of h.
24

---

Claim 34
By definition, for every representation, Ma(z) = (Z =2aa) F(s P(a)
Thus, using
30p we have for {0,1}. Pa(=') K(aa(z) and Ma(=") (000))=11-(()p)))) (=)a
-1--)))
(66)
which in turn yields (34).
It remains only to recall that we have derived (3 under the assumption that [V] > 0. That is, we assumed that the point 2 which fails invertability on Sy has some parents St. The case when [V| = 0, i.e. there Indeed, in this case one can simply split into z' and 2" and splitting the S weight between them as before, without the need to carefully balance the interaction of probabilities with S1 via K.
parents in S1 can be treated using similar argument, but is much simpler.
D Uniform Approximation and Two Point Representations
interested in showing that all optimal invertible representations, no matter which, and no matter on which set Z', can be approximated using a representation with the following property: For every E So, S1, there are at most & points Z that have (u, v) as parents, see Figure a). Here would depend only on the desired approximation degree, but not on Z', or the exact representation we approximating. We therefore refer to this result the Uniform Approximation result. Its implications for practical use were discussed Section 4.1
As discussed in Sections 4.1
The notation used in this Section was introduced in the beginning of Section
To proceed with the analysis, in what follows introduce the notion of two-point representation. The main result is given as Lemma D.I below.
This Section uses the notation of Section 3.3
Let T be an invertible representation, let u So, Si k } the set of all points 2 E Z which have u and v as be some points, and denote by Zue = 2 parents. Denote by
wy Σ 3olu)To(22, u) and w. Σ ((TOTT((2).)))
(67)
the total weights of 30 and 31 transferred by the representation from u and v respectively to Zuv- Recall that Pus P. denote the distributions of Y conditioned on u, We call the situation above, iee the collection of numbers (()o())7o(z), ")) ( (v) ( (2),))
a two point repre- sentation, since it describes how the weight from the points u, is distributed in the representation, independently of the rest of the representation. The contribution of Zuv to the global performance cost
Euv,T Σ Jsk
h(P ((P))((((Y(22))
(68)
(100 u)pu + (1)31 u)p
(ooSo(u)Ta(2', (o (v)Ti (25, (2),0)
Σ jšk
(2o + +)
(69)
while its contribution to the fairness condition is
FUN.
( jsk
(70)
Let us now consider two extreme cases of two-point representations. Assume that the total amounts of weight to be represented, Wa: W. are fixed. The first case is when A: = 1, and this is the maximum fairness case, since in this case the weights Wa, w. overlap as much possible. Indeed, the contributions to the fairness penalty and performance cost in this case are
Iw wol and (agwa + a1w;) w h [QgWyPu + o1WePe
(71)
Wn + O1 W2
25

---

respectively. The other extreme case is when wi and w. do not overlap at all. This case be realised with & = 2. by sending all Wa to 2! and all w. to z². The fairness and performance contributions would be
Wy + We and On (pw) + oow, - (Po);
(72)
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. We thus observed that each two points u, v, with fixed total One could, in principle, fix a threshold Yuu- Iw,, Wy S Yuv S W., + We for the faimess penalty (7), and obtain a performance cost between that in (71) and (72). However, it is not clear how large the number of points I should be in order 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 of = points, and have guaranteed bounds on the possible amount of loss incurred with respect to all representations of all other sizes.
weight Wa: Wy, can have their own Pareto front of performance-
Lemma D.I. For every on the Sunction h, with the sollowing properly: For every two-point representation ((Bo(u)To(z)) , jss {BI(W)T((Z), .)) jea). with total weights Wa, Wv there is two point representation T" set Ze, with the same total weights, such that (2 S n, and such that Foe,T S F and E EEeeTT + 2( + w.)e.
O, there number n.
The depending only
(73)
Proof. To aid with brevity of notation, define for j S k
cf ao)o(u)To(2', u), di = (1
(74)
Then we can write
T (gt + cc)) -h Capa + deee)
FuN,T = > Acd
(75)
cj + dj
2
JSk
JSK
where A is the vector = (ar -u ) et = (cr, G)) and Act is the inner product of the two.
Observe that the cost Exv,T depends on e mainly through the fractions cf Our strategy thus
would be to approximate all A of such fractions by 6-net of size independent of k. To this end, set
1/ df
(76)
C + c
and define Awo 10, 1] + R by
huv (p) = hppp. + (1 p)pv).
(77)
Since h is continuous (by assumption), and defined on compact set, is uniformly continuous, and so is hwo. By definition, this means there is a ô > 0 such that for all p' with Ip -p'l < 8, it holds that h (p) New (v') S e. Let us now choose { to be ô net on [0. 1]. For every S set
r. {j Ip' py-zzp x.| S 8, and is minimal with this property).
(78)
That is, T, the set of indices j such that p² is approximated by x Using 2; we construct the representation T" as follows: For E {0, 1} set
(79)
JEL.
For n new points, 2' E 2 set To(2", u) = ///BBouu (u), Ti( x)) = (t). Note that the total
weights are preserved, Eisn of = w. and Eisn of Wy.
Next, for every E T2 we have
of
86.
(80)
of + c
26

---

Thus
Σ E 1 - (cb + d
Ejer, + +(+++))) o c
C0
6 ci
3/3
o + dt
=6. 5.
(81)
Next, observe that by the construction of dig.
E - -Eodi + Mu)())) = Σ Σ
( + ()) E (c) + cu))io)
(82)
JET;
Σ (cb c))s
(83)
ser,
= (wa + w.ee.
(84)
In addition,
ci
Eun,T E(e (n)
E(O + tho
Σ
(c8 + (no
(85)
c c
I (wa wo)e,
(86)
where we have used (81 in the last transition. Combining the two inequalities yields the second part of 73
Eu Euo.T 2(w,, w,)e.
(87)
Finally, note that
Σ Ac
Σ
Σ
Aci
(88)
JET,
Σ
Σ
Acd
(89)
.jET
Σ |Ac/,
(90)
yielding the first part of, and thus completing the proof of, statement
73
It remains to observe that above we have used a d net for hav. which depends on Pur Pe. However, we can directly build an appropriate n-net in full range of h, the simplex Ay, which would produce bounds valid for all u, Indeed, let 8' be such that Ih(v) h(v)) < for all μ, Ay with ||u - xll1 I 8'. Observe that the map + ppu + (1 - p)pu is 2-Lipschitz from R to Ay equipped with the 1-:l12 norm, for any u, e E Ay. Thus, choosing 5 = 3,,, we have ( - Au h S e
[p- - y'1 < 8. This completes the proof of the Lemma.
E
Concavity Of Er
Note that the variables appear in (14) 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 l is. We record this in the following Lemma.
Lemma E. If h Ay - IR is concave, then of every P1,P2 E Ay the function g .R. -> IR, given by g((e), (2)) = (ci + c2) c2) (IP: +CPp2 concave.
te
Proof. It is sufficient to show that for every e, E RR we have g((c + cl)/2) ( (0(()) + s(d)). To this end, define the map F g2 Ay by
F(c) C1P1 + 0222
(91)
C1 +
27

---

and note that
d+2
F((c (((c+d)) cd/2) F(c)
+(d)
(92)
ai t + a+
It then follows that
g((c+ + c)/2) 2 + (
(93)
= +((
F(c)
7 a + a+ +
ei t
+(())
G 4
(94)
2 (c + +
c1 + MF((c)
4+C
h h(P(d))
11 02
o + +
6 + + + 0
(95)
= = +(0)))(())))
(96)
F MIFPO Equality Constraint
As noted in the main text, although the inequality 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 F.I Let po: lu E Az be two probability distributions over Z and fix some 7 0. l|me Pillze lllly = then there exist du, d1 E Ag such that μo + 700 = fn + 701- In the other direction, there exist do. Φ1 Az such that po + +00 = #1 701, then I| -illtv S %
The proof may be found in Section G
As consequence of this result, if we find distributions Φo, de Az such that Mo + 7000 = #1 y0u holds, then we know that (66) also holds, and conversely, if (16) holds, then distributions as above exist.
Using this observation, we introduce new variables, oi. and &u.n,, for every (u, v,j) E 2, which correspond to éo((u, v)))) and Φ1 ((u, v,j)) respectively. These variables will be required to satisfy the following constraints:
u.u. 2 0, Ru.v. 20 v(u,U,))
(97)
Σ M,e
8 Panns and Σ Bu. =1
(98)
Br(w)r a.
(i(r + Toee V(u, v, 2.
(99)
Here the first two lines encode the fact that do. Φ1 are probabilities, while the third line encodes the fairness constraint, as discussed above.
G Additional Proofs
Proof Of Lemma
Proof. For this proof it is more convenient work with the & norm ||-I|, directly. Recall that [|po Pillzy- Il/o - frll1 and that
I| - -1ll1
Σ (Ao()) - (z())
(100)
28

---

Assume that ll - -illi = 2y. Define the functions do(2) = 1 (m12no) (2) (11(2) - mo(2)) and
(z) = ( (2) (mo(2) (1(2)). Note that we then have
Σ Øu(z) (z((2)=
(101)
Indeed, define
(22) = 1 mm) (2) [H1(2) + (m) ] (2) Mo(2).
(102)
Clearly, 77 + Φ0 Yr and thus Σ> (12) + [z)2)) = 1. Similarly, E. n(x) + x1)2) = 1. Therefore
we have
Σ 0o(2) = Σ का (2).
(103)
Note also that we can write
27 = Il - m1ll1
Σ (mo(z) - 111 (2) = Σ (0o(2)+
(104)
which combined with (103) yields (IOI). Next, we can also directly verify that
140 60 = + Ø1,
(105)
and thus setting Φu = - Φ1 = y 61 completes the proof of this direction.
In the other direction, given 60, Φ1 E Az such that μo + 700 = + 701, we have
Σ [mo(2)) M1(2)] = Σ (0)(2) - e= - 2%
(106)
thus completing the proof.
H
Experiments
This section describes additional evaluation details and experiments with fair classifiers. In Section we provide the main algorithm figure, and discuss technical implementation details. Section H.2 contains the comparison to number of fair classifiers, and Section H.3 discusses implementation of the entropy cost within the DCCP framework.
H.1 Implementations and computational details
Algorithm MIFPO Implementation
Input: Data {x2 a, yt #1).s. integers L, k.
For E {0, 1} denote X. (x;
a).
1. Learn calibrated classifiers
co,ei RR + [0, 1]. such that (x()) ~ P (Y = 1 = x, = a)
2. Construct the histograms (8(())
E 10, for the sets
(x, E Da} c [0.1]. Choose bin representatives {pt)t=
Ha = (x)
3. Solve MIFPO, given by Definition with parameters i and
(Ba(0) (e ag = Hi | a; a)//N.
The Pareto front evaluation requires two main parts building calibrated classifier required for evaluating ea P(Y|X, A a), and later solving the optimization problem MIFPO (see Algorithm
29

---

Comparison to FGBM and Post-processed LGBM across Datasets
LSAC
COMPAS
ADULT
07
Accurway
Accurwcy
0.60
Accuracy
0.6
0.
LoSa Nok proces Pareett From
FGOM
0.50
Statistical Parity
Statistical Parity
Statistical Parity
Figure 4: Comparing common fair classification pipelines the MIFPO Pareto front, for LSAC, COMPAS, and ADULT datasets. For FGBM and LGBM+Post Process methods, each point represents trade-off obtained single hyper-parametter configuration.
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 Here, we used Isotonic regression (Berta al. 2024) for model calibration with XGBoost (Chen et al.) (0155) as the base model. For training the XGBoost model, 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 19-12900KS CPU (16 cores, 24 threads), 64 GB of RAM, and an NVIDIA GeForce RTX 3090 GPU.
H.2 Additional Evaluations
Following the equivalence between the Pareto fronts of fair binary classification and representations for the accuracy cost (Section 3.1). we evaluated the accuracy-fairness trade-off for some common fair classification algorithms. For our evaluation, we selected the most widely used algorithms based on GitHub repository stars and citation counts in the literature, demonstrating the importance of our proposed method in comparison to common approaches. We also evaluate FairFront, more recent approach introduced in Wang al. (202)).
Fair classifiers generally fall into pre-processing, in-processing, and posteprocessing categories. Pre- and post-processing types often utilize standard classifiers part of their fair classification pipeline. We specifically evaluated two widely adopted algorithms, representing different categories: FairGBM Cruz al. (2023): An in-processing method where boosting trees algorithm (LightGBM) is subjected to pre-defined fairness constraints. Balanced-Groupp Thresholddehoeeeeeeeeoooooooeldd post-processing method which adjusts the threshold per group obtain fairness criterion. For FairGBM, we used the original implementation provided by the authors. For Balanced-Grous Threshold post-processing, we utilized implementations available via Acquitas Saaciro al. (2018), popular bias and fairness audit toolkit.
JJan Groop-Threshooddd Jang et al. (2021): 1): A
We conducted our evaluation using three of the most common datasets in this field, which are known to have relevance to real-world decision Docision-mmking processes: the Adult dataset (income prediction), COMPAS (recidivism prediction), and LSAC (law school admission).
important to note that, as a rule, common fairness classification methods are not designed to control the Bairness-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-ace -accuesy trade-off points. However, there typically is no direct known and controlled relation between hyperpatameters and the obtained trade-off. For FairGBM, we utilized the hyperparameter ranges specified in the original paper. Cruz et al. (2023). In the case of the balancing post-pro proc-procs method, we conducted a grid search over the full range of all possible hyperparameters to ensure comprehensive analysis.
accuuaccy
Figure shows Isows 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 theoretically possible at a given fairness level. (b) the existing methods are also unable to present solutions for
30

---

AaE ADULT
AaE COMPAS
0.664
0.845
Fair Front
Fair Front
0.662
Acc
0.840
MIFPO
Acc
MIFPO
0.835
0.658
0.830
0.656
a²
8 Statistical Parity
1.0
1.0
Statistical Parity Figure 5: Comparing FairFront MIFPO accuracy-faimess tradeoff on two curated datasets.
the full range of the statistical parity values. The values from the FGBM and the post-processing algorithms all have statistical parity I 0.2. Similarly to to the case of fair representations, these results emphasize the limitations of current fair classifiers in achieving optimal trade-offs between accuracy and fairness across the full range of fairness values.
Additionally, we add comparison to FairFront (Wang et al. 2024). which, similarly to our work, depends on estimates of P)Y|X). See the discussion Section We note, however, that the utility of this comparison is limited due the very strict setup defined in that paper, which cannot be applied to natural datasets. Specifically: 1) The implementation in Wang et al. (2023) requires creating a finite discrete space by binning over the full Rd feature space which allows for perfect modeling of the distribution P(Y ) (by simple counting). This is not normally possible on real datasets in practice. 2) The binning itself was performed manually for each dataset separately, and we were unable to discern the logic behind the selected parameters. 3) To allow reasonable binnig, the true dimensions of the data are manually reduced, again by picking features manually for each dataset. Due to these issues, it was practically impossible to apply the method in Wang et al.) (2023) to other standard datasets, even the datasets used in WWnn al. (2023) but with standard features.
Nonetheless, for the sake of comparison, we compared MIFPO and FairFront on the same restricted, preprocessed version of the datasets that FairFront used, with the same bin-based probability estimator. The results are shown in Figure
H.3 Minimization of Concave Functions under Convex Constraints and the Entropy Loss
As described in figure 5 used the disciplined convex concave programming (DCCP) framework and the associated solver, (Shen et al. 2016 2024) for solving the concave minimization with convex constraints problem.
Minimizing concave functions under convex constraints is 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 lot of popularity in recent years.
The DCCP framework extends disciplined convex programming (DCP) handle nonconvex problems with objective and constraint functions composed of convex and concave terms. The idea behind "disciplined" methodology for convex optimization is to impose set of conventions inspired by basic principles of convex analysis and the practices of convex optimization experts. These "dscciplined" 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
'This is completely different from the discretizaton of Ay used in MIFPO. The space Rd is the feature space. and is much larger than Ay.
31

---

obvious reasons), which limits the usability. Notice, that for the prediction accuracy measure h(p) min(p. p) this is not problem. but for the entropy classification error h((1 p. p.) -p pogp (1 p) log(1 - p). this is more challenging. Nevertheless, here we show that the standard DCCP framework allows for entropy classification error.
Lemma H.1. Let a = (1 - (o)r,, and b = a -U())a,, with pe = Pa and Pu pb-
We can write the cost function under the entropy accuracy error as:
a Pa b.pb
(a + b) entropy
+
- Pa) +b. (1-p))) + entropy(a Pa + b. po) entropy(a + = entropy(aa (1-
Proof.
entropy(x) = entropy(z,, (z, xx) = x [log(2) log - z)] + logg1 x)
Thus.
entropy
a Pa b. ph
a Pa
b.p.b. ph
log
a Pa + b.bb. pb
log 1
Pa + ph
+
+6 b
a+b b
a + b
a Pa + b pb
log
a +
Pa + b. Pb
[log(a Pa b pb) log(a b a Pa b. pb)l
a
log(a + - a Pa b pb) - log(a + b)
Hence:
a aa.Pa Pa + A.b.p Pb
a Pa + b. Pb [log(a Pa + b. pb) log(a + a. b pb)l
(a b) entropy
(a (a+
a+b
a b
+ (a + b) looga + b a Da - bb b.p))
(a + b) log(a + b)
= entropy(a Pa + b- pb) - (a Pa b- pb) log(a + 6 a Po - pb)
+ (a + b) log(a + Po b pb) entropy (a b)
Finally, the expression can be written as:
entropy + b Pa b. pb) entropy(a Pa b. pb) entropy + b)
entropy(a Pa) b (1 pp)) + entropy(a Pa + pb) entropy bb)
Given the element-wing wise entropy function (1 x) is with known characteristics and under the decp framework, we can use the entropy error for our cost using:
=entrop a))(()r (1-p.)
U(u)rua (1 - p.))
entropy((1 a)V(u)r,, Po + a. u..uuuuTTe Pw)
entropy((1 a)V(u)ro, + aal)(
32

---

I Fair Classifiers As Fair Representations
As discussed in Section 3.1 Pareto front of binary classifiers with statistical parity can be computed from the Pareto front of representations with total variation fairness distance. In this Section we provide the proof of this result, Lemma 3.1 The Lemma and the related notation are restated here for convenience.
For binary classifier y of Y, its prediction error defined as usual by <(Y) == P (8 + #V). The statistical parity distance of Y is defined as
(Y)
P (v=11A=11 P 1|4 -f-------P---A--000000
(107)
Let the uncertainy measure h be defined by ( Note that the first part of the Lemma does use the special properties of this h and does not necessarily hold for other costs h.
Lemma 1.1. Let Y be classifier Yf Then there is representation given by random variable Z on a set Z with Z = 2, such that
Y.
E (2 (YIZ- 2 = =)) S <X) and Iluo - Pillrv S (
(108)
Conversely, for any given representation Z, there is a classifier Y of Y as a function of Z (and thus of A)), such that
c(M) E (Y 2)) and (Yp || - -uillrv
(109)
Proof. Let us begin with the second part of the Lemma, inequalities (I09). Given a representation Z, <(r) I (I (Y = 2)) follows since E2= (Yl = 2)) is the error of the optimal classifier of Y as a function of Z. We choose y to be such an optimal classifier and thus satisfy the above inequality, with equality. Next, the second inequality in (T09) holds for for any classifier Y derived from Z. The argument below is slight generalisation of the argument in Madras et al. (2018).
Define f(z) IP (Y 11z =
=²). Note that for E {0, P (y =A= f())
Thus
P P 1|A-1) = o) -P (r :frr
1|A / f())duolz) / f())d)((z)
(110)
/ ((()))u(()) - 9(2)dm)())
s sup
(111)
= || - pallry,
(112)
where we have used | < 1 in the second line. Repeating the argument also for P (1=1
P 8 1|A
= 1|A-=))
[)) we obtain the second inequality in (T9p.
We now turn to the first statement, (08). Let Y be a classifier of Y as a function of (X, A). Observe that thus by definition P (YIX, induces distribution on the set f0, 1}, and thus may be considered as representation Z = Ý of (X, A) on that set. We now relate the properties of this Z as representation to the quantities e(-) and (Y)( Similarly to the argument above, the first part of (108) follows since Ez-z/((P (Yiz- = z)) is the best possible error over all classifiers. For the second part, note that since Y is binary, we have
P (Ý -y=1144 1|4 - 0) P (v 1|A=1 = 1) P 014
= 0) P (p - 0/4=1)- (113)
follows that
||AO - 1---lllly = 1 Σ
PP (8- 0) - P (8 (8= r/A 1-AA111 1)
(114)
2
mE(0.1)
= |p (P(Y - 1 -) 1|A= -P P (8= 1|A - 1)
-P
(115)
= (Ý),
(116)
where we have used 113) for the second to third line transition. This completes the proof of the second part of [108]
D
33

---

J Computational Complexities
In this Section we discuss alternative discretization schemes for the MIFPO algorithm. We also discuss various complexity aspects of the classification algorithms Xian et al. (2023) and Wang et al. (2023) and relate them the complexity of MIFPO.
In Section 4.2 we described a data independent discretization of Ay by binning. While effective for small label sets V/ larger sets would require different approach. One alternative is cluster the data instead of binning Ay itself. Indeed, by choosing cluster centers {m:)1 C Ay, such that each data point (x, a) ()) (x.a)ED is well approximated by one the centers (or just most points are approximated), we can guarantee arbitrarily good approximation of the true Pareto front. The cardinality M of such clustering would depend on the intrinsic dimension of the data, which we typically expect to be lower than the full dimension of Ay, due to the Manifold Hypothesis, Fefferman al. 2016).
Another possibility is to not use any explicit discretization, and instead to use each data point as separate bin (equivalently, we use the points themselves as the cluster centers {m:}). In this case, the complexity scales with the size of the dataset, but not with the dimensions of Ay. The MIFPO construction in Section 4.1 iiplies that MIFPO in this case would have O(N)) variables for a dataset of size N. While not applicable for large N, this is similar to the complexity of variety of often used algorithms. Classical example of such complexity is the Spectral Clustering. We also observe that Xian et al. (2023), recent state of the art fairness classification algorithm mentioned above, also has such complexity.
Indeed, the approach in Xian et al. (2023) involves the computation of a certain transportation plan between data points, and the encoding such plans also requires O(N2) variables. Thus problem sizes occuring in MIFPO would be smaller or equal to those in Xian et al. (002)), despite the fact that MIFPO is solving considerably more general problem (see Section
Finally, the algorithm in Wang et al. (2023) involves optimization in the space of confusion matrices, with dimensions of size A x DI. As discussed in Section 2 the reduction of the problem to confusion matrices of possible due to special properties of the classification problem and the accuracy
loss.
The algorithm in Wang al. 2023). FairFront, an iterative algorithm, where each iteration involves solving certain difference-of-coneee (DC) program which is constructed from full dataset. The class of DC programs is equivalent to that convex-concave programs considered in this paper (see Shen et al. (216)). In fact, similarly to MIFPO, the algorithm in Wang et al. (2023) also uses DCCP, Shen et al. 2016), although applied to a different problem.
In each iteration, the solution of DC program is then used to add new constraints to certain main convex program. While it is proved that asymptotically this process converges to the optimal front, there are no bounds on the number of iterations. This may lead to the convex solver crashing due to too many constraints, and fact we have observed such crashes in our evaluation.
To summarize MIFPO involves solving one convex-concave problem, with size which may be independent of the data size. In contrast, FairFront involves iteratively solving convex-concave problems and a main convex program, where the number of terms in the objective of each convex- concave problem scales with the size of the data, and the number of constraints grows in the convex problem grows with iterations, thus making the iterations progressively harder.
K Factorization
In this Section we the factorization result, Lemma 3.2
We restate the result for convenience.
Recall that f"(x;, a) denotes the Bayes optimal classifier of Y, i.e. I : X' x A + Ay is given by
ax = |X = x, A a).
(117)
We define a new variable X', with values in Ay, by X' = (X,
'In this Section we have discussed the theoretical complexity aspects of FairFront. Additional details pertaining to the official implementation of Wang al. (2023) may be found in Section H.2
34

---

Lemma K.1 (Factorization). For any representation Z of (X, A), there is a representation Z' of (X',A) such that
R2 (P = 1P and Drv(Z') S (2)
(118)
Proof. The representation Z' of X', A will be defined as follows: For a E Ay, E A, 2 set:
P P = 2 X = 0, A = a) = = (Z = oo,=
(119)
PP (Z
(120)
where the second line is the definition and is added for clarity. To see intuition behind this definition note that have
P (2 = a) - = = =]] = o, A = a)
(121)
FEX
Σ FEX
=|x = = PCc=NN=-AA-.PKKaa//a=oo-
(122)
In words, for fixed a, to compute TP (Z' =o we effectively collect all æ such that f (z, a) and average all of their representations. Equivalently. all points x with the same are merged into one point, and their representations summed up according to their relative weight.
We will now show that neither the performance nor the fairness condition change under this operation.
Since (rv is defined solely in terms of the distributions PP (Z =IA =a), to show that Drv = DZv it enough to show that
=
E.
(123)
To this end, we have
=|
Σ P PZZ' = -, = o|A= a)
(124)
a
ΣP (Z 2|X' =. P o|A=al =a) a)
(125)
(Z 2|A - n)
(126)
where the transition Dry (Z').
124) to 125 is by the definition of Z'. Thus we have shown that Drv (Z) =
Next, note that the above argument implies also that IP (Z = 2) P = =2). Thus, in order to show
the performance equality,
E z (P
Er (Y =))),
(127)
it is enough to show that P 2 = =) = PP(Y = =) for every E 2. Further, again since
(Z = .) = (Z' .), we can show that
P(Y = =) PP y, =)
(128)
35

---

for all 2 E 3, E V. Write
P(Y = 2,
(129)
y. Σ PY y. a, -,
(130)
ΣΣ "=00==
(131)
(132)
ΣΣ = = "
(133)
ΣΣ Σ
(2,)==
(134)
PZZ= = = a) P(x = = -=
Σ
=
P(X' = o-A=a
(B,0==
(135)
()) = -
E
x| -,
0, 0 a))
(136)
Σ E (U)P = o, =,A==)
= =| = a
(137)
(138)
P PY = =y a) = 2, =,,
(139)
= (Y Z' = 2).
(140)
Here, the transition 132 133
is due to the independence condition I On line (34) we split the
x into sum subsets fo
f ((xxa) o} and an outer some over all a. The transition
(36) (37) is due to the equality 122
I21). Finally, for the transition (137)- [38 we have used
the fact that
(1) P (Y = v|X'= = a, A=
(141)
which holds by definition of X'. Similarly to the earlier discussion on merging of x with similar
value of f*, the above argument proceeded by regrouping the summation over by the value of f"(x, a). The computation thus showed that this process yields the definition of Z'. In particular, this regrouping process and equation [41] explain why the space Ay is special and all representations may be factored through it. This completes the proof of the Lemma.
In the above argument have used the summation over a, i.e. E. ... This is formally possible when (X, A) has a discreet distribution. The full general case may be obtained simply by replacing the summation by integration and conditioning by the general conditional expectation operator.
36


Reviews:
[{"review_id": "8Tzn2mG5ck", "reviewer": "Reviewer_rVkf", "summary": "The paper creates a method to get the pareto-front of a representation of samples in the dataset with regards to statistical parity (a fairness measure) and performance of the method. In order to create this pareto-front mathematical proofs are provided, showing a theoretical basis for the information that can still be captured in the representation while becoming independent of a binary sensitive attribute.", "questions": "I would like the authors to provide some clarity on how their method will be made accessible to the research field itself in the form of a technical implementation. Given a sufficient answer to this question, I would improve my score.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper makes careful work of providing mathematical proofs for the steps that lead to creating the perato-front; \n\nThe authors make careful work of providing a detailed related works section, allowing the reader to place the paper in the context of the research field. \n\nThe authors accompany their theoretical work with some experimental works. These results do show that the pareto-front is not fully a pareto-front as some of the results from the models exhibit better performance. Related to this, the authors state that the other methods are run several times for different hyperparameters. It would have been good to run each combination of hyperparameters for several seeds in order to report the volatility of the resulting method, perhaps with the use of confidence ellipses. \n\nAlthough this is largely a theoretical work on fairness, it would have been nice of some reference was made that this pareto-front only works on the dataset and that it's performance in the real-world might still be different as there are biases in the data that a method cannot account for. \n\nThe most significant results of this paper is the possibility of creating pareto-fronts for datasets. While the theoretical proofs are interesting and necessary, its contribution would be the algorithm to generate the pareto-front. Currently no implementation of this code is provided with the submission (no link in the paper itself to the code, nor the code itself included in the supplementary material). \n\nThe scope of the paper is rather limited as the method only works for binary sensitive attributes and binary prediction. The authors do note future work in order to broaden the scope for these purposes too.", "was_revised": true, "final_justification": "The authors addressed my concern for the need of a code implementation to accompany the paper in order to provide a significant contribution for the research field. \n\nThe possibility of having pareto-fronts on datasets to conduct fairness experiments is useful for determining method capabilities. The paper achieves this goal from a theoretical point and provides experimental results showcasing its use.", "rebuttal": "Thank you for your feedback! \n\nWe were glad to hear that the reviewer found our proofs to be interesting and careful, and that the results are well positioned  within the general context of the research field. \n\n\nIn what follows, we discuss the other points raised in this review. Please let us know if there are any further questions, we would be glad continue the discussion! \n\n\nFirst, to address the main question in the review:\n> I would like the authors to provide some clarity on how their method will be made accessible to the research field itself in the form of a technical implementation. Given a sufficient answer to this question, I would improve my score.\n\n\nWe completely agree with the reviewer on the importance of making the imlementation publicly accessible. \n We are fully committed to ensuring our work is accessible and useful to the research community, and we have already prepared the code repository for public release. We are also committed to this as part of our research obligations under our funding grant agreement.\n\nWhile the conference's current policy prevents us from sharing a link, we can provide clarity on the technical implementation of our software package, which is ready for publication:\n1. Our code is a Python package, installable via `pip`. It follows Scikit-learn's API guidelines(as scikit-learn estimator) for seamless use.\n2. For tabular data, the API requires a single table `X`, a labels vector `y`, and the column name of the sensitive attribute. In this mode, users can optionally provide their own pre-trained calibrated classifiers. If no classifiers are given, the package defaults to using an internally calibrated XGBoost model to learn the probabilities $P(Y|X,S)$.\n3. For non-tabular data (e.g., images, text), the API accepts data that is already pre-split by the sensitive attribute (`X_0`, `X_1`, `y_0`, `y_1`). In this scenario, the user must also provide the corresponding pre-trained calibrated classifiers capable of handling the specific data type.\n4. The package and the paper's experiments are in **separate repositories**. The experiments repository uses the package as a third-party dependency, which demonstrates its real-world usability and provides a clear usage example.\n\n\nDo these  notes address the question  regarding the publishing of the code?\n\n\n>The authors state that the other methods are run several times for different hyperparameters. It would have been good to run each combination of hyperparameters for several seeds in order to report the volatility of the resulting method, perhaps with the use of confidence ellipses. \n\nWe assume that the discussion here is about the runs of the existing methods we compare with. There are over 200 different runs, that correspond to different methods and different hyperparameter values (that result in the different tradeoff points for those methods). Thus it will be quite time consuming to repeat everything with multiple seeds. Moreover, since every separate run uses a separate seed, while individual run results might shift, it is quite unlikely that the whole *tradeoff line* of the method would shift significantly (as it contains multiple independet runs). Thus we belive that the presented results are fairly stable. \nHowever, if the reviewer finds this experiment to be of high imprtance, please let us known, and we will include this in the final version of the paper. \n\n\nFor our method, MIFPO, we have observed very little dependence on the initailization parameters (of the probabiliy estimator, and of the DCCP initialization). The variance clouds would be practically invisible on the plots. We will include these numbers formally in the supplementary.\n\n\n\n>Although this is largely a theoretical work on fairness, it would have been nice of some reference was made that this pareto-front only works on the dataset and that it's performance in the real-world might still be different as there are biases in the data that a method cannot account for. \n\nUnfortunately, we are not quite sure what was meant in this point. Could the reviewer clarify? We would be glad to discuss this further. \n\nIn general, we follow the same experimental protocol as other works in the field. We agree that of course, there may be some aspects of bias that are not captured by any given protocol. \n\n\n>The scope of the paper is rather limited as the method only works for binary sensitive attributes and binary prediction. The authors do note future work in order to broaden the scope for these purposes too.\n\nIndeed, for non-binary sensitive attributes and labels, we discuss the associated difficulties, and considerations towards resolving them, in the Conclusions and Future Work section. \n\nWe would like to note, however,  that non-binary quantities appear to be an issue *for any method* for which computational complexity can be meaningfully quantified, not just ours.  \nFor instance, the complexity of Xian et al, 2023, for multi-valued labels would be similar to the complexity of our method (See Supplementary J), despite the fact that they solve a simpler problem (only accuracy metric, only classification). Additional details and discussion on this topic can be found in Section 2 and Supplementary J."}, {"review_id": "WdAPnKqwwU", "reviewer": "Reviewer_8C6m", "summary": "This paper proposes an efficient, model-independent method to compute the fairness-performance Pareto front without requiring the training of complex fair representation models. The authors leverage theoretical analysis to reduce the Pareto computation into a compact discrete optimization problem (MIFPO), which can be solved using disciplined convex-concave programming (DCCP). The method supports arbitrary concave performance measures (beyond accuracy) and can be applied to fair classification directly. Experimental evaluations on benchmark fairness datasets (Health, ACSIncome-CA, ACSIncome-US) demonstrate that MIFPO outperforms in most cases state-of-the-art fair representation and classification methods.", "questions": "- The authors state \"...this size does not depend directly neither on the feature dimension d, nor 359 on the sample size N and thus the problem scales well in that sense...\". Then, could the authors clarify any practical bottlenecks when the feature space is high-dimensional and how feature preprocessing or dimensionality reduction could be (if needed) integrated with MIFPO?\n\n- While the paper effectively computes the fairness-performance Pareto front, it would be valuable to include a qualitative interpretability analysis of the learned trade-offs for downstream decision support. For example, in the Health dataset, what does it mean in practice to choose a point with greater fairness but lower accuracy? Answering this could help practitioners decide which point on the Pareto frontier aligns with their operational goals.\n\n- Since MIFPO relies on the Bayes optimal classifier estimation, could the authors comment on how sensitive the results are to imperfect calibration or estimator mis-specification in practice?\n\nMinor Suggestion:\nConsider defining “MIFPO” explicitly in the abstract.\n\nVery nice work !", "limitations": "Yes. The authors explicitly discuss limitations regarding binary attributes/targets and outline potential extensions while noting the scalability in terms of feature dimensionality and dataset size.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- Introduces theoretically grounded structural results (factorization, invertibility) for fair representations.\n- MIFPO addresses the challenge of obtaining the Pareto front efficiently and handles arbitrary concave performance measures, not limited to accuracy.\n- The paper provides clear reproducibility details, well-structured algorithmic steps, and evaluation with multiple benchmark datasets.\n\nWeaknesses:\n- Evaluation is limited to binary sensitive attributes and binary targets, restricting generality.\n- Lack of qualitative interpretability analysis on the learned trade-offs for downstream decision support.\n- The implementation of DCCP-based solvers may still encounter local minima in some scenarios (though authors state this was not observed).", "was_revised": true, "final_justification": "The authors have addressed most of my concerns with detailed clarifications.\nI find the core contributions of the paper to be novel, theoretically grounded, and practically valuable. The methodology is broadly applicable and avoids the need for complex model training, which is a notable strength.", "rebuttal": "Thank you for the favourable review! \n\n\nIn particular, thanks so much for mentioning that the work is very nice! We were also glad to hear that the results were found to be theoretically grounded and  the presentation and reproducibility to be \nclear. \n\n\nIn what follows we discuss the questions and other points raised in the review. Please let us know if there are other questions!\n\n\n\n>Since MIFPO relies on the Bayes optimal classifier estimation, could the authors comment on how sensitive the results are to imperfect calibration or estimator mis-specification in practice?\n\n\nBefore discussing our empirical observations, we would like to mention two points: \n\n(a) Calibration, i.e., the estimation of probabilities, can be done quite easily *with guarantees*, given a continuous valued classifer, \nsince its esentially a 1d problem. (That may come at some expense of accuracy, however.) See for instance Kumar et al 2019, Berta et al 2024 refs in the paper. \n\n(b) Given such calibration, the Pareto front we find is a lower bound on the true Pareto front. That is, the true front can only be better than what MIFPO computes. \n\n\nIn that sense, miss-specification is never too bad, as we err on the safe side. That said, we by all means agree that if the source classifier is poor, then the calibration and the resulting MIFPO Pareto front would be weaker than the true ones. \n\n\nRegarding the empirical results, we have not observed considerable issues with calibration.  On some low dimensional discreet feature datasets, it may be possible to construct \"true\" probability estimators simply by counting. However, such estimators yielded negligible (less then 0.5 percent) improvements over a generic claibrated xgboost estimator. \n\n\n\n\n\n>Then, could the authors clarify any practical bottlenecks when the feature space is high-dimensional and how feature preprocessing or dimensionality reduction could be (if needed) integrated with MIFPO?\n\n\nIn our approach (and also in several other leading fairness classification approaches; see discussion around lines 120-127), the relation between the label and featires is encapsulated by the probability function $\\mathbb{P}(Y|X,A)$. Once this function is reliably estimated, it no longer matters for MIFPO what dimension the data was. \n\n\nOf course, when the feature dimension $d$ is high, then estimating $\\mathbb{P}(Y|X,A)$ may be non-trivial, depending on the data, and it is here that the dimension reduction may be used. \n\nWe note that typically probability estimation can be done quite well given a reliable classifier (see also the related notes in the discussion of misspecificaton above). \n\n\n\n\n>    While the paper effectively computes the fairness-performance Pareto front, it would be valuable to include a qualitative interpretability analysis of the learned trade-offs for downstream decision support. For example, in the Health dataset, what does it mean in practice to choose a point with greater fairness but lower accuracy? Answering this could help practitioners decide which point on the Pareto frontier aligns with their operational goals.\n\nWe completely agree that interpretability analysis is important for decision making in practice. \n\nOn the ASCIncome dataset [5], as an example, the sensitive attribute is geneder and the label is high/low income. \n\n\nStatistical parity here means that we want a classifier such that the proportion of individuals with predicted high income to be equal between the genders. \n\n\nNote that this is not the situation for the data itself, i.e., the data is considered *biased* in that sense. \nIf the classifier was perfect, it would have to flip some income values from their values in data (\"true data values\"), to become statistical-parity fair. It thus must \ndecrease performance to become fair, but this is viewed as corrective bias and is desirable. \n\n\nOn the other hand, when the classifier is not perfect to begin with, there may be many classifiers with the same error, some of which are more fair, and some of which are less. In that situation, we would like to pick the most fair one. \n\n\nSo the tradeoff question may be also viewed as: Given and amount of \"true data values\" that we can flip, what is fairest  classifier we can pick?\n\n\nWith this in mind, we now look at Figure 3 (the rightmost panel): We see that the best accuracy, without regard of fairness, is around 0.825. Perhaps somewhat strikingly, we also see that we can almost achive this level of accuracy (0.81), with 0 statistical parity distance, i.e., perfect fairness.  MIFPO achieves this, while other methods have considerably larger errors at this fairness level and could errorneously suggest the fairness would result in more information loss. \n\n\nDo these comments help clarify the interpretability question?\n\nWhile here we considered a brief example, for a general in-depth analysis of the notions of fairness tradeoffs, we refer to the excellent book [6].\n\n\nFinally, we note that while the Health dataset [1], originally mentioned in the review, is a standard banchmark in fairness, see for instance [2], [3], [4], and is a very good example for testing *computational aspects of algorithms*, we feel we do not have the appropriate background to discuss the \n*interpretation* for this particular dataset.\n\n\n\n\n[1] Kaggle. Health heritage prize, 2012. URL https://www.kaggle.com/c/hhp\n\n[2] Jovanovic et. al. ICML 2023,  Fare: Provably fair representation learning with practical certificates. \n\n[3] Louizos et al, ICLR 2016, The variational fair autoencoder. \n\n[4] Madras et al. NeurIPS 2018, Predict responsibly: Improving fairness and accuracy by learning to defer. \n\n[5] Ding et al, NeurIPS 2021 Retiring\nadult: New datasets for fair machine learning. Advances\nin Neural Information Processing Systems, 34, 2021\n\n[6] Barocas, S. et al (2023). Fairness and machine learning: Limitations and opportunities."}, {"review_id": "VP9oC0Rk3W", "reviewer": "Reviewer_DJzQ", "summary": "This paper proposed an interesting approach to address the fairness–performance trade-off in representation learning. Based on the structural properties of optimal fair representations, this approach reduces Pareto-front computation to a compact concave minimization problem (MIFPO) over discrete variables, which can be solved via off-the-shelf disciplined convex–concave programming (DCCP). The key insight is that we can factor the high-dimensional representation problem through the Bayes optimal classifier to a small simplex (Factorization Lemma), then further restrict our attention to invertible representations (Invertibility Theorem). Empirically, MIFPO provides competitive fairness–accuracy pareto comparing five other methods (CVIB, FCRL, FNF, sIPM, Fare) on Health and ACSIncome datasets. It provides the full Pareto front rather than isolated operating points .\n\nThe main contributions are\n1) By proving the Factorization Lemma and the Invertibility Theorem, the paper presents an approach of reducing an intractable infinite-dimensional search over representations to a finite concave minimization problem\n2) The paper offers the first model independent algorithm that applies to any concave performance measure including accuracy, log loss, etc. \n3) The authors create a model independent procedure that can be used to compute the fairness-performance pareto from data. Experimental results show its effectiveness comparing to other methods.", "questions": "1) In Section 4.1, what criteria or heuristics should guide the selection of the number of bins L and the replication factor k? Is it possible to quantify the trade-off between approximation error and solver runtime as a function of L and k?\n\n2) What are the size of the datasets used? Can you provide cpu and memory usage? Will the proposed approach scale as the dataset size increases?\n\n3) The solution of MIFPO relies on the DCCP convex-concave solver, which in general only guarantees convergence to a local minimum. Does solution quality matter for this approach?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The paper has following main strengths:\n1) The proposed approach is the first to prove fundamental  theorems that produce exact Pareto front reduction.\n2) Unlike prior research restricted to non-differentiable accuracy, the proposed framework accommodates any concave performance measure including log-loss and Brier score by using a unified concave minimization formulation .\nDecoupling Representation Learning\n3) The proposed approach not only finds a single point but traces the entire fairness–performance frontier, offering deep insight into the trade-off that point-wise methods cannot provide\n\nThe main weakness include\n1)  The theory and algorithm are developed for binary sensitive attributes and targets and extension to multi-class or group settings is deferred and may increase problem size significantly\n2) DCCP handles moderate sizes, but concave minimization can stuck into local minima and also may not scale to large-scale problem without specialized global solvers\n3) The reported empirical study is limited to three variants of a socioeconomic task. There is no assessment on other sensitive features like race and gender or on higher-dimensional data like text", "was_revised": true, "final_justification": "The author provided a comprehensive rebuttal.", "rebuttal": "Thank you for the favourable review! \n\nWe were glad to hear that the reviewer found our approach interesting, and that the theoretical contributions, and this work being the first to treat general concave performace losses in particular,  were cited as stregths. \n\n\nWe now discuss the questions and other points mentioned in the review. \nPlease let us know wether these notes help clarify the questions in the review. \n\n\n>    In Section 4.1, what criteria or heuristics should guide the selection of the number of bins L and the replication factor k? Is it possible to quantify the trade-off between approximation error and solver runtime as a function of L and k?\n\nWe have found the empirical results to be  fairly insensitive to the values of L and k, as long as L is high enough. \n\n\n**Values of L**:\nConsider for instance L = 50, with corresponding bin width being 0.02. For such bin width, it is possible to show that the maximal error in accuracy and/or statistical parity would be 0.02, and a similar stability result would hold for general losses too. The general result would state that if two distributions on the simplex are close in the transportation (or earth mover) distance, then the corresponding Pareto fronts are close, with distance depending on the modulus of continuity of the perfromance metric. Because with growing bin count L we can uniformly approximate any distribution on the simplex, this result would imply the above statement for L=50. \n\nShould we add this stability result to the paper?\n\n**Values of k**: \nOne consequence of Lemma 3.1 is that when  the accuracy performance metric is used, k=2 is theoretically sufficient (see also the discussion on lines 127-139, and 184-188). Interestingly, however, we have found that using k=5 *slightly* increases the performance, which is likely due to non-convex nature of the optimization. \nWe have then used k=5 throughout.\n\n>Is it possible to quantify the trade-off between approximation error and solver runtime as a function of L and k?\n\nBecause the approximation is non-convex, we are not aware of any possible approach to theoretically quantify the relation between L and runtime. \n\nEmpirically, on the other hand, since the  values of L do not influence the performance strongly above a certain level, and since the runtimes were not a bottleneck, we have not fully investigated this  relationship.\nHowever, here we provide some results about the order of magnitude of the time complexity results for a single point on the Pareto front for different k and l, avraged on few datasets: \n\n| l\\k | 2 | 5 |\n|-----|---|---|\n| **10** | 0.18 sec | 0.41 sec |\n| **15** | 0.24 sec | 0.53 sec |\n| **20** | 0.24 sec  | 0.55 sec |\n| **30** | 0.37 sec | 0.82 sec |\n| **50** | 1.06 sec | 4.66 sec |\n\n\nAs mentioned above, we used $k=5$ and $L=50$ throughout, thus generating a full Pareto front (30 points) would be under 3  minutes.\n\n\n\n>  What are the size of the datasets used? Can you provide cpu and memory usage? Will the proposed approach scale as the dataset size increases?\n\nThe dataset sizes are as follows:\n| | #features | #samples |\n|-----|---|---|\n|Health | 52 | $1.22 \\cdot 10^5$  |\n|ACSIncome-US | 11 | $10^6$ |\n|ACSIncome-CA | 11  | $1.15 \\cdot 10^5$ |\n\n\nAs we detailed above, the runtimes for each of these datasets were all under 3 minutes. \n\n**Scaling**:\nAlthough due to space constraints we have only discussed this briefly in the paper (lines 357-359), we believe the sclaing  with the dataset size is one of the strongest points of our approach. \n\nIndeed, note that the MIFPO problem itself, as defined in Section 4, does not depend **at all** neither on the dataset size $N$ nor on the data features dimension $d$. The only way in which MIFPO dependes on the data is through the distributions on the simplexes, provided by the probability estimators, as discribed in Step 2 in Section 4.2. \nBecause we discretize those distributions, there would be dependence on $L$, but not on $N$! \n\nThat said, there are two ways in which $N$ and $d$ may still influence the results. \n**(a)** First, generally, as the dimension grows, it may be harder to construct the probability estimator. Depending on the model used, the dataset size may be either an issue or an asset here. We note however, that calibration/probablility estimation, is the easier part. The harder part is contructiong a base classifier, and that problem is general, i.e., not specifically a fairness problem. \n**(b)** If we consider the extension to the multi-label case, then instead of directly discretizing the simplex, we would have to find a more efficient approach. As we discussed in Section 6 and Supplementary J, we believe the correct approach would be a form of clustering. The complexity of such clustering would depend on N, but the MIFPO would still only depend on the number of clusters. Alternatively, however, one could consider the datapoints themselves (mapped to the simplex), as individual clusters. \nThat would result in a problem complexity of $O(N^2)$. Although we do not advocate for such an approach, we note that some recent work (Xian et al 2023) does have $O(N^2)$ complexity (see Supplementary J for additional details).\n\n\nDo these considerations clarify the dependence of MIFPO on the data size?\n\n\n\n\n>    The solution of MIFPO relies on the DCCP convex-concave solver, which in general only guarantees convergence to a local minimum. Does solution quality matter for this approach?\n\nSolution quality defnitely matters! However, we have not observed any considerable local minima issues. \n\nWe would also like to note that **any** solution that we find is automatically a lower bound on the true Pareto front. That is, the true front can only be better than what we find. Therefore, even if we had local minima issues, the output of MIFPO would be of interest if its better than other methods. \n\n    \n\n\n> The reported empirical study is limited to three variants of a socioeconomic task. There is no assessment on other sensitive features like race and gender or on higher-dimensional data like text\n\nOur experimental protocol follows that of \n(Jovanovic et al 2023), since their method, FARE, is state of the art among methods that learn representations. \nThe Health dataset has age (higher or lower than 60) as the sensitive attribute, and the target is a certain co-morbidity rate. The ACSIncome, on the other hand, are socioeconomic datasets, where the label is yearly income (higher or lower than 50k), and the sensitive attribute is gender. \n\n\nRegarding text/image data: We can easily evaluate MIFPO on a number of image and text datasets. As discussed above,  this amounts only to training a standard classifier on the new datset and converting it to probability estimator by calibration. From there, MIFPO is exactly the same as in the other datasets. \n\nHowever, because none of the methods *we already compare against* has been previously evaluated on such datasets, it is a considerable amount of work to see wether *their existing code* may be adapted. This is not something we can execute in the timeline of the rebuttal, and we hope this is understandable. Please let us know if you believe using such large datasets is important, and we would add them in the final version of the paper."}]

Author rebuttal:

Meta-review: The authors characterize the possibility of fair representation learning in single-group binary classification settings. They show that the computation of the fairness-utility pareto front reduces to a discrete optimization problem, for which existing methods can be deployed. Reviewers were positive about the paper, and expressed an excitement for the future work opened up by a theoretically-grounded model-agnostic method to generate pareto fronts for fairness datasets. While some limitations (e.g. restriction to binary targets) were acknowledged, I recommend accepting the paper and encourage the authors to integrate reviewer feedback (e.g. publishing the github repo) into the final revision.
Decision: Accept (spotlight)