FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
Authors: Yuheng Lai
Leying Guan
Venue: ICML 2025 poster (2025)
Keywords: Algorithmic fairness
Equalized odds
Adversarial learning
Inverse conditional permutation
Primary area: social_aspects->fairness
TL;DR: A fairness-aware learning approach for complex sensitive attributes to achieve equalized odds: employing adversarial learning with novel inverse conditional permutations.

Abstract: *Equalized odds*, an important notion of algorithmic fairness, aims to ensure that sensitive variables, such as race and gender, do not unfairly influence the algorithm's prediction when conditioning on the true outcome. Despite rapid advancements, current research primarily focuses on equalized odds violations caused by a single sensitive attribute, leaving the challenge of simultaneously accounting for multiple attributes under-addressed.  We bridge this gap by introducing an in-processing fairness-aware learning approach, FairICP, which integrates adversarial learning with a novel inverse conditional permutation scheme. FairICP offers a flexible and efficient scheme to promote equalized odds under fairness conditions described by complex and multi-dimensional sensitive attributes. The efficacy and adaptability of our method are demonstrated through both simulation studies and empirical analyses of real-world datasets.

FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
Yuheng Lai
Leying Guan
Abstract
Encouraging equalized odds is more challenging due to Y -cconditioning compared to encouraging demographic par- ity, another common fairness notion that emphasizes equity and requires Y to be independent of A without condition- ing on Y. Most existing algorithms targeting equalized odds can only handle a single protected attribute, and ex- tending them to multi-dimensional sensitive attributes is challenging due to the well-known difficulties of estimat- ing multi-dimensional densities (Scott, 2015). However, real-world scenarios can involve biases that arise from mul- tiple sensitive attributes simultaneously. For example, in healthcare settings, patient outcomes can be influenced by a combination of race, gender, and age (Ghassemi et al., 2021; Yang et al., 2022). Moreover, ignoring the correlation between multiple sensitive attributes can lead to fairness gerrymandering (Kearns al., 2018), where model ap- pears fair when considering each attribute separately but exhibits unfairness when attributes are considered jointly.
Equalized odds, an important notion of algorith- mic fairness, aims to ensure that sensitive vari- ables, such as race and gender, do not unfairly influence the algorithm's 's prediction when condi- tioning on the true outcome. Despite rapid ad- vancements, current research primarily focuses on equalized odds violations caused by a sin- gle sensitive attribute, leaving the challenge of simultaneously accounting for multiple attributes under-addressed. We bridge this gap by intro- ducing in processing fairness-awar learning approach, FairICP, which integrates adversarial learning with novel inverse conditional permu- tation scheme. FairICP offers a flexible and effi- cient scheme to promote equalized odds under fairness conditions described by complex and multi-dimensional sensitive attributes. The ef- fieacy and adaptability of our method demon- strated through both simulation studies and em- pirical analyses of real-world datasets.
To address these limitations, we introduce FairlCP, a flexi- ble fairness-aware learning scheme that encourages equal- ized odds for complex sensitive attributes. Our method leverages a novel Inverse Conditional Permutation (ICP) strategy to generate conditionally permuted copies Á of sensitive attributes A given Y without the need to estimate the multi-dimennional conditional density and encourages equalized odds via enforcing similarity between (Ý, A, Y) and (Y A, Y). An illustration of the FairICP framework is provided in Figure 1.
1. Introduction
Machine learning models are increasingly important aid- ing decision-making across various applications. Ensuring fairness these modelss-pevvnte minorities other protected gromps-rrmains significant challenge (Mehrabi et al., 2021). To address different needs, several fairness metrics have been developed in the litera- ture (Mehrabi et al., 2021; Castelnovo et al., 2022). The equalized odds metric defines fairness by requiring that the predicted outcome Y provides the same level of informa- tion about the true response across different sensitive attribute(s) A (e.g. gender/race/age) (Hardt et al., 2016):
discrimination against
Our contributions can be summarized follows:
Inverse Conditional Permutation (ICP): We introduce the ICP strategy to efficiently generate A, as conditional permutations of given Y, without estimating the multi- dimensional conditional density of ALY. This makes our method scalable and applicable to complex sensitive attributes.
YLAY..
Empirical Validation: Through simulations and real- world data experiments, we demonstrate FairICP's flex- ibility and its superior fairness-accuracy trade-off com- pared to existing methods targeting equalized odds. Our results also confirm that ICP is an effective sensitive attribute resampling technique for achieving equalized odds with increased dimensions.
'Department of Statistics, University of Fisconsin-MMadison *Department of Biostatistics, Yale University. Correspondence to: Leying Guan <leying, eleying.guan@& guan@yale.eddd yale.edu>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
Sama Live Act lbutes
Input bata
prodicciion
line of in-processing algorithms for equalized odds uses ad- versarial training for a single sensitive attribute (Zhang et al., 2018; Louppe et al., 2017; Romano et al., 2020; Madras et al., 2018). Our proposed FairICP is the first in in-prceessing framework specifically designed for equalized odds with complex sensitive attributes.
Sic
[x,>)
Precidar
Flannial
Inswesse Connciionnll Permuzation Å e--Al Au
Dieziminttor
Selected Review on Metrics Evaluating Equalized Odds Violation Reliable evaluation of equalized odds violations is crucial for comparing equalized odds learning methods and assessing model performance in real-world applica- tions. While numerous methods have been proposed to test for parametric or non parameeeetiic conditional inddpne- dence, measuring the degree of conditional dependence for multi calti-dimensional variables remains challenging. We note recent progress in two directions. One direction the resampling-baser approaches (Sen et al., 2017: Berrett et al., 2020; Tansey al., 2022). These methods allow flexible and adaptive construction of test statistics for comparisons. However, their accuracy heavily depends on generating ac- curate samples from the conditional distribution of A|Y, which can be difficult to verify in real-world applications with unknown A Efforts have also been made towards di- rect conditional dependence measures for multi-dimensiona variables. Notably, Azadkia & Chatterjee (2021) proposed CODEC, non-parametric, tuning-firee free conditional depen- dence measure. This was later generalized into the Kernel Partial Correlation (KPC) (Huang et al., 2022y:
A
Figure 1: Illustration of the FairICP framework. A, X, and Y denote the sensitive attributes, features, and labels. We generate Á as permuted copies of A which satisfies (Y, Y) (Ý, A, Y) when the equalized odds holds, using a novel inverse conditional permutation (ICP) strategy, and construct fairness-awan learning method through regularizing the distribution of (Y, A. Y) toward the distribution of (8, A, Y).
Background and Related Work Fairness in machine learning has emerged
critical area of research, with various notions and approaches developed to address poten- tial biases in algorithmic decision making. These fairness concepts can be broadly categorized into three main types: (1) group faimesss (Hardt et al., 2016), which aims to ensure equal treatment across different demographic groups; (2) individual fairness (Dwork al., 2012), focusing on similar predictions for similar individuals; and (3) causality-based fairness (Kusner et al., 2017), which considers fairness in counterfactual scenarios. Given a fairness condition, exist- ing fair ML methods for encouraging it can be classified into three approaches: pre-processing (Zemel et al., 2013: Feldman et al., 2015), in-processing (Agarwal et al., 2018: Zhang et al., 2018), and post-processing (Hardt et al., 2016).
Definition 1.1. Kernel Partial Correlation (KPC) coeffi- cient p² = (U, () is defined as:
E [MMD? (Powy, Puiw)] (UU W) = E [MMDD (ōu, Polw)]
Our work focuses on in-processing learning for the equal- ized odds (Hardt et al., 2016), group fairness concept. Equalized odds requires that predictions are independent of sensitive attributes conditional on the true outcome, unlike demographic parity (Zemel et al., 2013), which demands un- conditional independence. The conditional nature of equal- ized odds makes it particularly challenging when dealing with complex sensitive attributes that may be multidimen- sional and span categorical, continuous, or mixed types. Under demographic parity, there have been several methods developed for classification tasks with multiple categorical A (Agarwal et al., 2018; Kearns et al., 2018; Creager et al., 2019), however, these ideas can not be trivially generalized to equalized odds. As a result, existing work on equal- ized odds primarily considers one-dimensional sensitive attributes, with prior work designed to handle multi- dimensional continuous or mixed-type sensitive attributes. For example, Mary et al. (2019) introduces a penalty term using the Hirschfeld-Gebbelei Gebelein-Reeee Rénnii Maximum Correlation Coefficient to accommodate for a continuous sensitive at- tribute in both regression and classification settings. Another
where (U.V. W) ~ P and P is supported on a subset of some topological space U x x W, MMD is the maximum mean discrepancy- distance metric between two proba- bility distributions depending on the characteristic kerell k((,-) and dy denotes the Dirac measure at U.
Under mild regularity conditions (see details in Huang et al. (2022)), p² satisfies several good properties for any joint distribution of (U, V, W) in Definition 1.1: (1) p² [0, 1]; (2) p² 0 if and only if 1 V W; (3) p² = if and only if U is a measurable function of V given W. A consistent estimator p² calculated by geometric graph-base based methods (Section 3 in Huang et al. (2022)) is also provided in R Pack- age KPC (Huang, 2022). KPC allows to rigorously quan- tify the violation of equalized odds for multi-dimensione A via p² Y), where A can take arbitrary forms and response Y can be continuous (regression) or categorical (classification). Additionally, (Y, A Y) has been prop- erly normalized in [0, 1] to enable direct comparisons across different models in a given problem as it can be viewed as a generalized version of squared partial correlation between
2

---

FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
U and V given W (see Appendix A for a simple example). In this paper, we consider KPC our main evaluation met- ric of equalized odds, where its robustness is also supported by comparison with other popular metrics (e.g,, DEO for classification with categorical A as in Agarwal et al. (2018); Cho et al. (2020)) in Section 3.
tively:
(0₁) = =00))=Exx Exy [- looggo, (Y [x]]
(2)
La (0),0a) = BB log Do. (Y, A, Y)
+ Vi,(0,, 02) (1 ())))) pCa(0) 0s),
Do, , A, Y))I
(3)
(4)
2. Method
where (.) is the classifier parameterized by 0₂ which separates the distribution of (Y.A, A) and the distribution of (Y, A. Y), and μ E [o.1] is a tuning parameter that controls the prediction-fairen trade-off. Then, FDL learns oz, Oa by finding the minimax solution
We begin by reviewing how conduct aawree learn- ing via sensitive attribute resampling to encourage equalized odds and its challenges with complex attributes. We then in- troduce our proposed method, FairlCP, which leverages the simpler estimation of Y |A to perform resampling, providing theoretical insights and practical algorithms. All proofs in this section are deferred to Appendix B.
oz. Os arg min max Vu 0a).
(5)
By 8a
Challenges with Complex Sensitive Attributes FDL generates Á through conditional randomization and re- samples it from the (estimated) conditional distribution Q(A Y). However, FDL was proposed primarily for the scenario with a single continuous sensitive attribute, as the estimation of Q(A Y) is challenging when the dimen- sion of A increases due to the curse of dimensionality (Scott, 2015). For example, with categorical variables, combining categories to model dependencies leads to an exponentially decreasing amount of data in each category, making estima- tion unreliable. Also, when A includes mixed-type variables, modeling the joint conditional distribution (A(Y) becomes complex. Therefore, an approach that allows to have flex- ible types and scales well with its dimensionality is crucial for promoting improved equalized odds in many social and medical applications.
Let (X,, Yi) for i ,,..., Dar be i..d. generated triples of (features, sensitive attributes, response). Let fe, (.) be prediction function with model parameter f While (-) can be any differentiable prediction func- tion, we consider it as a neural network throughout this work. Let y = (X) be the prediction for Y given X. For a regression problem, y is the predicted value of the continuous response Y; for classification problem, the last layer of fe, (.) is a softmax layer and Y is the predicted probability vector for being in each class. We also denote X= =
:aa......AA))) Y (Y,,...,YY Yn..) and Y = (YI,..., ).
Xx..) A
2.1. Baseline:
Fairness-Aware Learning via Sensitive Attribute Resampling
We begin by presenting the baseline model developed by Ro- mano et al. (2020). Fair Dummies Learning (FDL), whose high-level model architecture is the same as FairICP. We then discuss the challenge it may face when dealing with complex sensitive attributes.
2.2. FairICP: Conditional Permutation
Fairness-Aware Learning via Inverse
To circumvent the challenge in learning the conditional density of A given Y, we propose the Inverse Conditional Permutation (ICP) sampling scheme, which leverages Con- ditional Permutation (CP) (Berrett et al., 2020) but pivots to estimate Y given A, to generate a permuted version of Á which is guaranteed satisfy (Ý, A, Y) - (Ý, Y) when the equalized odds defined in eq. (1) holds.
The key idea of FDL is to construct synthetic version of the original sensitive attribute as A based on conditional ran- domization (Candès et al., 2018), drawing independent sam-
ples A, from Q(-IY) for = I,..., ,etr where the Q(- (w) is the conditional distribution of A given Y = y. Since the re-sampled A is generated independently without looking at the features X, and consequently, the predicted responses Y, Á satisfies equalized odds: Y JL Á | Y. Given the resampled sensitive attribute, FDL uses the fact that A sat- isfies equalized odds if and only if (Ý, AY, Y) - (Y,A, YYY), Y). and promotes equalized odds by enforcing the similarity be- tween joint distributions of (Y, A, Y) and (Y, A, Y) via an adversarial learning component (Goodfellow et al., 2014). where the model iteratively learn how to separate these two distributions and optimize fairness- regulaarze prediction loss. More specifically, define the negative log- likeliool loss, the discriminator loss, and the value function respec-
Recap of CP and Why It's Not Sufficient FDI. con- structs synthetic and resampled sensitive attributes based on conditional randomization. CP offers natural alternative approach to constructing the synthetic sensitive attribute A (Berrett et al., 2020). Here, we provide a high-level recap of the CP sampling and demonstrate how we can apply it to generate synthetic sensitive attributes A. Let S, denote the set of permutations on the indices (1...., n). Given Sn.
AAY
any vector x (f1, 2x) and any permutation define X, (I+(1). (..())...... Iz(n)) as the permuted version of x with its entries reordered according to the permutation т. Instead of drawing a permutation II uniformly at random, CP assigns unequal sampling probability to permutations based on the conditional probability of observing An given
3

---

FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
Y:
Algorithm 1 FairCCP:
Fairness-aware learning via inverse
9"t (A, Y) F F(U==|AYY Evres, 9" (An' YY)
conditional permutation
(6)
Input:
Data (X, Y) = 4,,
Here, q(- 4) is the density of the distribution Q(- y) (i.e.. q(- y) is the conditional density of A given Y = y
Parameters: penalty weight μ., step size a, number of gradient steps Ng. and iterations T.
). We write (- (- Y) := -T Yi) to denote the densityy This leads to the synthetic À An. which, intuitively, could achieve similar purpose the ones from conditional randomization for encouraging equalized odds when utilized in constructing the loss eq. (5).
Output: predictive model ())()) and discriminator
Dog ().
1: for 1.,.. do
2: Generate permuted copy A by eq. (7) using ICP as implemented in Appendix C.
Compared to the conditional randomization strategy in FDL., one strength of CP is that its generated synthetic sensitive attribute A is guaranteed retain the marginal distribution of the actual sensitive attribute A regardless of the estima- tion quality of q--ly). However, it still relies strongly on the estimation of q(-ly) for its permutation quality and, thus, does not fully alleviate the issue arising from multivariate density estimation as we mentioned earlier.
3: Update the discriminator parameters 0g by repeating the following for Ng gradient steps:
0. ー 0a Vo, 0a).
4: Update the predictive model parameters B, by repeat- ing the following for Ng gradient steps:
Of Va [ (1-)));(05)- -nCa((s,00) 0a)
ICP Circumvents Density Estimation of A ||Y Y To cir- cumvent this challenge in estimating the multi-dimensional conditional density ((-1)) which can be further complicated by mixed sensitive attribute types, we propose the indirect ICP sampling strategy. ICP scales better with the dimen- sionality of A and adapts easily to various data types.
5: end for Output: Predictive model fo,
FairICP Encourages Equalized Odds with Complex Sen- sitive Attributes We propose FairICP, an adversarial learning procedure following the same formulation of the loss function shown previously in the discussion for FDL (Section 2.1) but utilizing the permuted sensitive attributes À using ICP, i.e., eq. (7) which requires estimated q(y) as opposed to the one from direct resampling using esti- mated ((Al))) Let (0r) and La(0,, (a) be the empirical realizations of the losses L and Lu(O), Oa) defined in (2) and (3) respectively. Algorithm presents the details.
ICP begins with the observation that the distribution of (An. Y) is identical as the distribution of (A, Yu 1). Hence, instead of determining II based on the conditional law of A given Y. we first consider the conditional permu- tation of Y given A, which can be estimated conveniently using standard or generalized regression techniques, Y is typically one- mee-dmeniional. We then generate II by applying an inverse operator to the distribution of these permutations. Specifically, we generate À = Ai according to the follow- ing probabilities:
In practice, a fair predictor in terms of equalized odds that can simultaneously minimize the prediction loss may not exist (Tang & Zhang, 2022), and the minimizer/maximizzrr to L,((,))L((0) 02) may not be shared as a result. In this situation, setting μ to a large value will preferably enforce f to satisfy equalized odds while setting μ close to 0 will push f to purely focus on the prediction loss: an increase in accuracy would often be accompanied by a decrease in fairness and vice-versa.
(Y A)
P = [[=+||AYY; Ex'Es,, 4" aY A)
We adapt the parallelized pairwise sampler developed for the vanilla CP to efficiently generate ICP samples (see Ap- pendix C), and show that ICP generate valid conditional permutations of A given any set of its observed value set
Theorem 2.1. Let (X, Y) be i.d observations of sam- ple size n, S(A) denote the unordered set of rows in A, and p be the dimension of A. Let A be sampled via ICP based on eq. (7). Then,
ICP Enables Equalized Odds Testing with Complex Sen- sitive Attributes As by-product of ICP, we can now also conduct more reliable testing of equalized odds violation given complex sensitive attributes. Following the testing procedure proposed in Holdout Randomization Test (Tansey et al., 2022) and adopted by Romano et al. (2020) which uses a resampled version of À from the conditional distri- bution of A|Y, we can utilize the conditionally permuted copies to test if equalized odds are violated after model training. Algorithm provides the detailed implementation
(I) A is a valid conditional permutation of A: for any P [A a. ((A) S. Y) P a, S(A) S. Y).
(2) Y 1 LAY,, we have (Ý,A,Y) YY.
Theorem 2.1 is derived from Bayes' Rule, with its proof provided in Appendix B
4

---

FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
of this hypothesis testing procedure: we repeatedly generate synthetic copies À via ICP and compare T(Y, A, Y) to those using the synthetic sensitive attributes T(Y, A, Y) for some suitable test statistic T. According to Theorem 2.1, (Y, A, Y) will have the same distribution as (Y, A, Y) if the prediction Y satisfies equalized odds, consequently, the constructed y-values from comparing T(Y, A, Y) and T(Y,A, Y) are valid for controlling type-l errors.
In a classification scenario when Y (0, 1,..., [),, one can always fit a classifier to model YJA. To this end, FairlCP is more feasible to handle com- plex sensitive attributes and is suitable for both regression and classification tasks.
crete or continuous) 1.
3. Experiments
In this section, we conduct numerical experiments to ex- amine the effectiveness of the proposed method on both synthetic datasets and real-world datasets. All the imple- mentation details are included in Appendix E.
Proposition 2.2. Suppose the test observations Yi, for S S nhe)
(X's, A's, Yte) are i.d. and ÿrte (f(x)) for 1 S i mec) for a learned model f independent of the test data. If Hg Yte 1 A Yte holds, then the output p-value Pe of Algorithm 2 is valid, satisfying Pl(pe S Sa}= S a for any desired Type I error rate E [0, 1].
3.1. Simulation Studies
In this section, we conduct simulation studies to (1) assess the quality of the conditional permutations generated by ICP and (2) understand how FairICP leverages these permuta- tions to achieve more favorable accuracy-fairnes: trade-off for complex sensitive attributes. For the second task, we run series of ablation studies, replacing ICP with alternative strategies for generating the "fake copies" Á. Specifically, we compare FairICP to WaichP-which is an intermediate new procedure that generates A by CP-and FDL (Romano et al., 2020), the previously proposed equalized-odds learn- ing model that uses conditional randomization to generate Á. All methods use the same model architectures and training schemes for consistency.
Algorithm 2 Hypothesis Test for Equalized Odds with ICP
Input: Data (X* A Yte {0r, A, Y.),, 1 S <
Nltest
Parameter:
the number of synthetic copies K. 1: Compute the test statistic T on the test set: 1"
T(Y*t, A te Y
2: for k =olk K do
3: Generate permuted copy A of te using ICP
4: Compute the test statistic T using fake copy the
1.1.1. THE QUALITY OF CONDITIONAL PERMUTATIONS
test set: {(k) T(Ý's, Ar, yte).
5: end for
First, we investigate whether ICP can generate better condi- tional permutations than the vanilla CP by comparing them to the oracle permutations (generated using the ground truth in the simulation setting). We measure the Total Variation (TV) distance between the distributions of permutations generated by ICP/CP and those of the ground truth on restricted subset of permutations from swapping operation.
6: Compute the p- p-vuuue:
Pe K+1 1+ Σ ET
(1+
k=1
Output: A p-value Pe for the hypothesis that equalized odds (1) holds.
Simulation Setup. We generate data as the follow- ing: 1) Let A (UI...., .Ko,
2.3. Density Estimation
where U, are independently generated from a mixed Gamma distribution 1I, + (T), and θ is a randomly generated covariance matrix with O eigen- values equal-spaced in [1,5]; 2) Generate y
The estimation of conditional densities is a crucial part of both method and previous work (Berrett al., 2020;
Romano et al., 2020; Mary et al., 2019; Louppe et al., 2017). However, unlike the previous work which requires the esti- mation of A Y, our proposal looks into the casier inverse relationship of Y | A. To provide more theoretical insights into how the quality of density estimation affects ICP and CP differently, we have additional analysis Appendix D.
N/ (vD Aj, o² +1+(111 (1-w) w) Ko). Here, Y is influ- enced only by the first Ko components of A, and is inde- pendent of the remaining K components. The parameter w E [0, 1] controls the dependence on A.
We set K, E {1, 5, 10), K E (0, 5, 10, 20, 50, 100), w = 0.6, and the sample size for density estimation and quality evaluation are both set to be 200. Since the ground truth dependence structure between the mean of A and Y is linear,
In practice, ICP can easily leverage the state-of-the-ard den- sity estimator and is less disturbed by the increased com- plexity in A, due to either dimension or data types. Unless otherwise specified, in this manuscript, we applied Masked Autoregressive Flow (MAF) (Papamakarios et al., 2017) to estimate the conditional density of Y|A when Y is con- tinuous and A A1,..., Ag can take arbitrary data types (dis-
In Papamakarios et al. (2017), to estimate p(U u V v). U is assumed to be continuous while V can take arbitrary form, but there are no requirements about the dimensionality of U and V
5

---

FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
K0ml
KG 10
Restricted
method
-5
CP
ICP
10 20 50
100
30
20
50
100
10 50
100
K
Figure 2: Restricted TV distances (log 10 transformed) between permutations generated by ICP/CP using estimated densities and the oracle permutations generated by true density. Each graph contains results over 20 independent trials as the noise level K increases, with Ko 1,5, 5, respectively.
we consider density estimation ς based on regularized linear fit when comparing CP and ICP, where assume ((y] or ((Aly)
3.1.2. INFLUENCE OF CP ON FAIRNESS- AWARE LEARNING
be Gaussian. We estimate the condi- tional mean for ICP using LASSO regression (or OLS when Ko = 1 and K = 0) with conditional variance based on em- pirical residuals, and we estimate 94/Y for CP via graphical LASSO (or using empirical covariance when Kg- = and K = 0). We compare permutations generated by ICP/CP using estimated densities and those using the true density, which is known in simulation up to normalization constant. Comparisons using the default MAF density estimation are provided in Appendix D.2, which shows the same trend while being uniformly worse for both CP and ICP.
Next, we compare the performance of models trained using different resampling methods. Specifically, we compare four models: (1) FairlCP (Algorithm 1 with estimated den- sity @(Y (();: (3) Oracle (Algorithm 1 with true density A)): (3) FDL (Romano et al., 2020). Apart from the baseline FDL., also consider another similar but new model in simulation (4) FairCP (Algorithm who are almost identical to FairICP with the only difference be- ing permutations generated by CP using estimated density q( A (Y), aiming to investigate if the gain of ICP over CP in generating accurate permutation actually affect the down- stream predictive model training. The synthetic experiments allow us to reliably evaluate the violation of the equalized odds using different methods with known ground truth.
Evaluation on Permutations Quality. Due to the large permutation space, the calculation of the actual total vari- ation distance is infeasible. To circumvent this challenge, consider restricted TV distance where restrict the permutation space to swapping actions. Concretely, we con- sider the TV distance restricted to permutations æ that swap i and j for i + j. = 1,..., n and the original order, and compare ICP/CP to the oracle conditional permutations on such a(n=1) permutations only.
Simulation Setup We conduct experiments under two simulation settings where influence Y through X, which is the most typical mechanism in the area of fair machine learning (Kusner et al., 2017; Tang & Zhang, 2022; Ghas- sami et al., 2018).
1. Simulation 1: The response Y depends on two set of features X E RRK and X' E ER:
2
Y~ N (EK ( + EK Xx,
Xi.k ~ NN(WAA. (1 w)I XI,K ~ NOK,, Ix).
Results Figure 2 shows restricted TV distance between permutations generated by CP/ICP and the oracle condi- tional permutations using the true densities, averaged over 20 independent trials. We observe that the restricted TV dis- tances between permutations by ICP and the oracle are much lower compared to those from CP with increased sensitive attribute dimensions, for both dimensions of the relevant sensitive attributes Ko and dimensions of the irrelevant sen- sitive attributes K. These results confinm our expectation that ICP can provide higher-quality sampling by more effec- tively capturing potentially intrinsic structures between Y and A, For instance, when Ko 1, ICP achieves substan- tially better estimation quality than CP for moderately large K. Additional discussions and mathematical intuitions on why this occurs can be found in Appendix D.
Simulation 2: The response Y depends on two features X E R and X' E R:
Y~ T~ (xN(X**X'oo') +''
X ~
1).
In both settings, A are generated as in Section 3.1.1: A (UI...., U,)), 1222, where k 1...., (where all the A affects Y) and = 1,..., K + 1 for Simulation 2 (where only A₁ affects Y, with the rest serving as noises to increase the difficulty of density estimation). We set K E {1,5, 10}, w E {0.6, 0.9} to investigate dif- ferent levels of dependence on A, and the sample size for training/test data to be 500/400. For all models, we imple- ment the predictor f as linear model and discriminator d
....,,K K for Simulation 1
6

---

FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
as neural networks; for density estimation part, we utilize MAF (Papamakarios et al., 2017) for all methods except the oracle (which uses the true density).
A
Violation of Equalized Odis:
Violation of Equalized Odds:
test KPC
on sta statistical power
Oracle
Evaluation on the Accuracy-Fairness Tradeoff. For evaluating equalized odds, we use the empirical KPC = (² A | Y) E [0, 1J, which is a flexible conditional independence measure allowing different shapes of A and serves as a natural metric for quantifying equalized-odds violations. We also assess whether KPC is suitable model- comparison metric by examining trade-off curves in terms of (KPC, prediction loss) versus (fairness testing power, pre- diction loss). The fairness test power is defined as the ability to reject the hypothesis test outlined by Algorithm 2 which 2-which uses the true conditional density of Y| and the KPC statis- tic T with targeted type error at a 0.05. The greater p² or rejection power indicates stronger conditional depen- dence between A and Y given Y. The power metric pro- vides a fair comparison of equalized-odds, violations when the true density is known, however, the true density is un- available in practice, which discounts our trust of it. If the trade-off curves based on KPC closely mirror those based on the power metric under a known density, then KPC can be considered viable metric for evaluating faimess in real data settings.'
2.20
FairCCP
2.20
FairCP
2.15
2.35-
FDL
2.05
2.03
2:50
7.00
2950 0.75
KPC: dim
Power: dim
50
40
10-
0.20
0:30
0.7
08
KPC: dim 5
Power: dim
175
175
120
150
Loss
20
6.32
0.1
0.20
0.25
0.35
0.35
1.00
KPC: dim 10
Power: dim = -00
B
Violation of Equalized Odds:
Violation of Equalized Osds: best on statistical power
test on KPC
Results Figure 3 shows the trade-off curves between pre- diction loss and equalized odds violation measured by KPC and the associated power using Algorithm 2 (T = KCC under the high-dependence scenariors w = 0.9 in Simula- tion I and Simulation 2 respectively, with K- E 51, 10). We train the predictor/ f as linear models and the discrimina- tor d as neural networks with different penalty parameters y E [0, 1]. The results are based on 100 independent runs with a sample size of 500 for the training set and 400 for the test set. Results from the oowdeeendencce scenarios are provided in Appendix E.I, which convey the same stories.
2.5
Oracle
FairCCP
2.0
FairCP
3.5
2.5
3.0
0.05
0.10
6.15
3.2
0.4
0.5
KPC: dim
Power: dim
Loss
Figure 3A shows the results from Simulation 1. All ap- proaches reduce to training a plain regression model for prediction when μ = O, resulting in low prediction loss but severe violation of fairness (evidenced by large KPC and statistical power); as f increases, models pay more atten- tion to fairness (lower KPC and power) by sacrificing more the prediction performance (higher loss). FairICP performs very closely to the oracle model while outperforming both FDL and FairCP as the dimension of K gets larger, which fits our expectation and follows from the increased difficulty of estimating the conditional density of A|Y. Figure 3B shows the results from Simulation and delivers a similar message Figure 3A.
0.5
KPC:
6.3
dim =
0.2
0.
Power: dim =
0.1
0.
5.8
3.0
15.0
15.0
12.5
12.5
30.0
30.0
7.5
7.5
5.0
5.0
2.5
2.5
0.0
0.2
0.2
2.5
0.2
0.4
0.5
1.0
KPC:
dim
10
Power: dim 10
Figure 3: Prediction loss (MSE) and violation of equalized odds in simulation over 100 independent runs under Simulation I/ Simulation and w = 0.9. For each setting, conditional de- pendence measure KPC and statistical power PPfp-value < 0.05) are shown in the left column and right column respectively. From top to bottom shows the results on different choices of sensitive attribute dimension K. The X-axis represents the metrics of equal- ized odds and the Y-axis is the prediction loss. The Pareto front for each algorithm is obtained by varying the fairness trade-off parameter
'Note that, Simulation 2 only Ai influences the Y, so the test will be based on (2 AA | Y) to exclude the effects of noise (though the training is hased on A for all methods to evaluate the performance under noise).
7

---

FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
Crimes (one mice)
Crimes (all races)
ACS Income
Adult
COMPAS
(Sid)
KPC (Power)
(Sud)
KPC (Power)
Loss (Sid)
(Power)
(Sud)
KPC (Power)
(Sud)
(Power)
DBO
Baseline (Unfair)
0.34400.039)
0.13000.68)
0. 0.340((0.039)
0.259(1.00)
0.21000.003)
0.078(1.00)
0.155(0.0044
0.02(0.93)
0.451
0:336(0.01)
004000441)
0.858
FairCP
0.3960.045)
0.016/0.10)
0.418(0.047)
0.054:0.37)
0.215(0.003)
0.025(0.80)
0.15900.003)
0.01000113)
0.212
0.002/0.02)
0.008(0.04)
0.471
0.386(00044)
1.02600166)
05596(0.050)
(.068(0.48)
0.22000.044
0.021(082))
0.165(0.0044
0.00000110
0.198
0.44(00004)
0.00800.06
0459
FDL
0.402/0.016)
0.023/0.17)
(.621(0.48)
0.058(0.37)
/
0.161000005)
0.01(0026))
0.251
0.117(0.03
0.008/0.11
0.421
GarryFair
0.262/0.00-)
0.050(1.00)
0.18770.004)
0.03100786
0.298
0:138(0.07)
0.02(0.14)
0.368
Reduction
0.161(0.004)
0.00((0115)
0.212
0.400/0.02)
0.002/0.05)
0.460
Table 1: Comparisons methods encouraging equalized odds across five real data tasks. FairlCP (ours), FDL, HGR, and Reduction are compared, with "Baseline (Unfair)" included as a reference which is the pure prediction model. Reported are the mean prediction loss (with standard deviations in parentheses) and the mean KPC for equalized odds violations (with testing power Pp-value < 0.05 in parentheses). For the Adul and COMPAS datasets, which categorical A. the DEO equalized odds violation metric is also included. "Fairness tra parameters trade-off curves shown in Figure 4.
gqualized-odde models are selected to achieve similar violation levels. with the full prediction loss-KPP KPC
Crimes 1dim & 3.imi
ACS Income
Adult
COMPAS
0.60
FarlCP: 1dim
FOL: 1dim
026
HGR
FainKCP
FairICP
Reduccion
0.46
0.48
FainCPP
Reduction
0.55
HGR: 1dim
RartCP: 3dim
025
GerryFair
HGR FDL
0.44
FDL
HGR
0.50
HGR:: 3dim
FDL: dim
0.24
GerryFair
0.42
GerryFair
0.40
0.45
023
0.165
0.38
0.40
022
0.36
0.35
021
0.155
0.34
0.2
0.02
0.04
0.01
0.02
0.03
0.04
0.00
0.04
KPC
KPC
KPC
KPC
Figure 4: Prediction loss and violation of equalized odds (measured by KPC) obtained by different methods on CrimeslACS Incomel AduldCCOMPAS data over 100 random splits. The Pareto front for each algorithm is obtained by varying the fairness trade-off parameter. Similar results measured by testing power is in Appendix E.3.
Remark 3.1. The power measure (Algorithm 2) depends on how the permuration/sampling is conducted in practice. In simulations, we can trust it by utilizing the true condi- tional density, but its reliability hinges on the accuracy of density estimation. In contrast, the direct KPC measure is independent of density estimation.
mixed-type sensitive attributes: sex (male, female), race (Black, non-Black), and age (continuous).
Adult Dataset: The dataset consists of 48,842 instances and the task is the same as ACSIncome. We use both sex and race as two binary sensitive attributes.
COMPAS Dataset: The ProPublica's COMPAS recidi- vism dataset contains 5278 examples and 11 features (Fabris et al., 2022). The goal is to build binary clas- sifier to predict recidivism with two binary sensitive attributes A: race (white non-white) and sex.
3.2. Experiments on Real Data
In this section, we consider several real-world scenarios where we may need to protect multiple sensitive attributes. For all experiments, the data is repeated divided into train- ing set (60%) and a test set (40%) 100 times, with the average results on the test sets reported.
Results We compare FairICP with four state-of-the-ar baselines encouraging equalized odds with the predictor f implemented as neural network (the results for linear regressionlllassifcationn is reported in Appendix E.6): FDL (Romano et al., 2020), HGR (Mary et al., 2019), GerryFair (Kearns et al., 2018) and Exponentiateddgraaan gradient reduction (Agarwal et al., 2018) (referred to as "Reduction "). These baselines are originally designed for different tasks. Among them, Reduction is designed for binary classification with categorical sensitive attributes (AdulsCOMPASS) and Gerry- Fair adopts a linear threshold method to binarize sensitive attributes for classification and targets equal TPR or FPR as an approximation of equal- ized odds. HGR handles both continuous and categorical sensitive attributes for both regression and classification, but how to efficiently generalize it to handle multiple sen-
Communities and Crime Data Set: This dataset con- tains 1994 samples and 122 features. The goal is to build a regression model predicting the continous vio- lent crime rate. We take the continuous percentages of all three minority races (African American, Hispanic, Asian, referred to as "3 dim") as sensitive attributes in- stead of only one race as done in the previous literature. We also consider the case where A only includes one race (African American, referred to as "I dim") for better comparisons.
CCSShcoom/Adul//CMMPAA
ACSIncome Dataset: We use the ACSIncome dataset from Ding et al. (2021) with 100,000 instances (subsam- pled) and 10 features. The task is a binary classification to predict if income exceeds $50,000. We consider a
8

---

FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
sitive attributes has not been discussed by the authors I. We implement FDL with conditional density of A|Y esti- mated by MAF (Papamakarios et al., 2017) in the continuous case (Crimes); for the classification with mixed-type sensi- tive attributes (ACShıcome) it's not straightforward to esti- mate A|Y, so we only consider FDL in the categorical case (AdulsCCMPAS) where we calculate the frequencies of each class as an estimation of A|Y. For our proposed method FairICP, estimate A with MAF the same as in FDL in the continuous case, and use a two-layer neural network classifier in the classification (ACSIncome/Adall/COMM)
predicted probabilities across outcome classes (Hardt et al., 2016). Recent work by Tifrea al. (2023) extends post- processing to handle either continuous or categorical sensitive attribute through suitable loss-based optimization. In this context, ICP could serve as a valuable building block to enhance post-processing procedures, particularly by im- proving the resampling or adjustment steps when working with multi-diieensinall A.
Finally, we acknowledge the computational overhead as- sociated with adversarial learning, especially on large or complex datasets-a limitation noted in prior work (Zhang et al., 2018; Romano et al., 2020). Future directions include improving the training efficiency of FairICP through sta- bilization techniques or exploring alternative discrepancy measures such as kernel- objectives.
In Table 1, we compare FairICP to the baseline methods in terms of predictive performance (MSE for regression and misclassification rate for classification) with model-specific fairness trade-off parameters tnndd yield similar levels of KPC. We find that FairICP achieves the best performance across most tasks, offering lower or similar fairness loss (as measured by KPC or empirical power using estimated density) while also attaining lower prediction loss than the other fairness-awad aware learning baselines. Although the unfair vanilla baseline achieves the highest prediction accuracy, its equalized-odds violations are several times worse than Fair- ICP's. Finally, FairlCP's computational cost on par with FDL and only slightly higher than HGR (see Appendix E.5 for running time).
Impact Statement
This work advances the field of fairness-aware machine learning by addressing the underexplored challenge of en- forcing equalized odds for multi-dimension sensitive at- tributes, such as intersections of race, gender, and socioeco- nomic status. While our primary contribution is methodolog- ioal-introducing a theoretically grounded and adaptable framework (FairICP) for multi- fairness we rec- ognize the broader societal implications of this research. Below, we outline key ethical considerations and potential impacts: 1) By enabling compliance with equalized odds un- der complex sensitive attributes, FairICP could improve the equity of algorithmic systems in domains like hiring, health- care, and criminal justice; 2) While method promotes fairness through adversarial training and inverse conditional permutation, it inherently requires access to sensitive at- tributes during training. We emphasize that practitioners must carefully evaluate whether collecting such data aligns with ethical and legal standards in their jurisdiction.
Figure 4 shows their full Pareto trade-off curves using KPC (see Appendix E.3 for trade-off curves based on testing powers, , Appendix E.4 for trade-off curves based on DEO in Adult/COMPAS dataset). These results confirm that the effective multi-dimensional resampling scheme ICP enables FairCCP to achieve improved prediction and equalized odds trade-off compared to existing baselines in the presence of complex and multi-dimensional sensitive attributes.
4. Discussion
We introduced a flexible fairness-aware learning approach FairICP to achieve equalized odds with complex sensitive attributes, by combining adversarial learning with a novel in- verse conditional permutation strategy. Theoretical insights into the FairICP were provided, and we further conducted numerical experiments on both synthetic and real data to demonstrate its efficacy and flexibility.
In summary, while our work primarily contributes to al- gorithmic fairness methodology, its societal impact hinges on responsible implementation. We urge practitioners to contextualize FairCCP within broader ethical frameworks, engage impacted communities, and prioritize transparency in deployment.
Although this work applies ICP within an in-processing framework, the challenge of handling complex sensitive attributes also arises in post-processing approaches. In- processing methods incorporate fairness constraints directly into model training, whereas post- processon adjusts pre- diction thresholds after maining-typicett by recalibrating
Acknowledgment
We thank the anonymous reviewers and area chair for their constructive feedback, which helped improve this work. This research was supported in part by NSF grant DMS 2310836.
'In Mary et al. 2019, since their method can't be directly adapted to multiple sensitive attributes. we compute the mean of the HIG coefficients of each attribute a penalty.
9

---

FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
References
Feldman, M., Friedler, S. A., Moeller, J., Scheidegger, C., and Venkatasubramanian, S. Certifying and re- moving disparate impact. In Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp- 259-268, 2015. doi:
Agarwal, A., Beygelzimer, A., Dudík, M., Langford, J., and Wallach, H. A reductions approach to fair classification. In International conference on machine learning, pp. 60- 69. PMLR, 2018.
10.1 00.11442788255227883333
Azadkia, M. and Chatterjee, S. A simple measure of con- ditional dependence. The Annals of Statistics, 49(6): 3070 - 3102, 2021. doi: 10. (0.1214/21- ht https:: / /doii www..oorgoi... .21...12100
Ghassami, A., Khodadadian, S., and Kiyavash, N. Fair- ness in supervised learning: An information theoretic approach. In 2018 IEEE International Symposium on Information Theory (ISIT), pp. 176-180, 2018. doi: 10.110991S1T2221883337777
URL
AOS2073.
Berrett, T. B., Wang, Y., Barber, R. F., and Samworth, R. J.
The conditional permutation test for independence while controlling for confounders. Journal of the Royal Sta- ristical Society Series B: Statistical Methodology, 82(1): 175-197, 2020.
Ghassemi, M., Oakden-Rayme Rayner, L., and Beam, A. L.
The false hope of current approaches to explainable artificial intelligence in health care. The Lancet Digital Health, 3(11):e745-e750, 2021. ISSN 2589-7500. doi: http://oooooo/////oooooo3335s220 URL https::/www.scienneeeeee sc /ttpc///arttclle/aa////999222220
Candès, E., Fan, Y., Janson, L., and Lv, J. Panning for gold: Model-X knockoffs for high-dimensional controlled vari- able selection. Journal of the Royal Statistical Society: Series B, 80(3):511-57) 2018.
Ghosal, S. and van der Vaart, A. W. Fundamentals of non- parametric Bayesian inference, volume 44. Cambridge University Press, 2017.
Castelnovo, A., Crupi, R., Greco, G., Regoli, D., Penco, G., and Cosentini, A. C. A clarification of the nuances in the fairness metrics landscape. Scientific Reports, 12 (1):4209, 2022.
Goodfellow, I., Pouget-Abadie J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. Generative adversarial nets. In Advances in Neural Infor- mation Processing Systems 27, pp. 2672-2680, 2014.
Cho, J., Hwang, G., and Suh, C. A fair classifier using kernel density estimation. Advances in neural information processing systems, 005550888155 2020.
Gretton, A., Borgwardt, K. M., Rasch, M. J., Schölkopf, B., and Smola, A. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
Creager. E., Madras, D., Jacobsen, J.-H., Weis, M., Swer- sky, K., Pitassi, T., and Zemel, R. Flexibly fair rep- resentation learning by disentanglement. In Chaud- huri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learn- ing, volume 97 of Proceedings of Machine Learning Research, pp. 1436-1445. PMLR, 09-15 Jun 2019. URI htt.s::/ httppss://prreeeeeeee proceedi creager1 9a html.
Hardt, M., Price, E., and Srebro, N. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
Huang. Z. KPC: Kernel Partial Correlation Coefficient, 2022. URL https:/ CRAN R- i--rrojecte org/ package=KPC. R package version 0.1.2.
Ding, F., Hardt, M., Miller, J., and Schmidt, I.. Retiring adult: New datasets for fair machine learning. Advances in neural information processing systems, 34:6478-6498 2021.
Huang, Z., Deb, N., and Sen, B. Kernel partial correlation
coefficient - a measure of conditional dependence. Jour- nal of Machine Learning Research, 23(216):1-58, 2022. URL http: jmlr. wttp:/pppppp///////222.2 493. html.
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, doi: 10.1 144/2099236.209022222
Kearns, M., Neel. S., Roth, A., and Wu, Z. Preventing fairness gerrymandering: Auditing and learning for sub- group fairness. In Dy. J. and Krause, A. (eds.), Proceed- ings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learn- ing Research, pp. 2664-2572. PMLR, 10-15 Jul 2018 URL https: wttptttssppp/ooo/eee http///cceeinngg///// mllr. press vv0 kearns Ba html.
pp. 214-226, 2012.
Fabris, A., Messina, S., Silvello, G., and Susto, G. A. Algorithmic fairness datasets: the story so far. Data Mining and Knowledge Discovery, 36()):2074-2152, September 2022. ISSN 1573-756X.
doi: 10.1/07/ URL http:/ /xxx doi. doi.org/ 10. 1007 /101110011111 8 0200002--200 00082--2.
10

---

FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
Kusner, M. Loftus, J., Russell, C., and Silva, Coun- terfactual fairness. In Advances in Neural Information Processing Systems 30, pp. 4066-4076. 2017.
rapid covid-19 diagnosis by adversarial learning.
medRxivv 2022. doi: 10.10012002.0013322226944
URL https: htwp:://wwwww/// http://wwwwwedii.oooooooooo//o//
01.............................. htrly/2022/01/14/// 2tt.:222.....11..2288.2.44449
Louppe, G., Kagan, M., and Cranmer, K. Learning to pivot with adversarial networks. In Advances in Neural Information Processing Systems 30. pp. 981-990, 2017.
Zemel, R., Wu, Y., Swersky, K., Pitassi, T., and Dwork, C. Learning fair representations. In International conference machine learning, pp. 325-333, PMLR, 2013.
Madras, D., Creager, E., Pitassi, T., and Zemel, R. Learning adversarially fair and transferable representations. In International Conference on Machine Learning, pp. 3384- 3393. PMLR, 2018.
Zhang, B. H., Lemoine, B., and Mitchell, M. Mitigating un- wanted biases with adversarial learning. In Proceedings the 2018 AAAI/ACM Conference on Al, Ethics, and Society, pp. 335-340, 2018.
Mary, J., Calauzenes, C., and El Karoui, N. Fairness-aware learning for continuous attributes and treatments. In In- ternational Conference on Machine Learning, pp. 4382- 4391, 2019.
Mehrabi, N., Morstatter, F., Saxena, N., Lerman, K., and Galstyan, A. A survey on bias and fairness in machine learning. ACM computing surveys (CSUR), 54(6):1-33, 2021.
Papamakarios, G., Pavlakou, T., and Murray, I. Masked autoregressive flow for density estimation. Advances in neural information processing systems, 30, 2017.
Romano, Y., Bates, S., and Candes, Achieving equal- ized odds by resampling sensitive attributes. Advances in neural information processing systems, 33:361-371, 2020.
Scott, D. W. Multivariate density estimation: theory, prac- tice, and visualization. John Wiley Sons, 2015.
Sen, R., Suresh, A. T., Shanmugam, K., Dimakis, A. G., and Shakkottai, S. Model-powered conditional independence test. Advances in neural information processing systems, 30, 2017.
Tang, Z. and Zhang, K. Attainability and optimality: The equalized odds fairesss revisited. In Conference Causal Learning and Reasoning, pp. 754-786. PMLR, 2022.
Tansey, W., Veitch, V., Zhang, H., Rabadan, R., and Blei, D. M. The holdout randomization test for feature selec- tion in black box models. Journal of Computational and Graphical Stutistics, 31(1):151-16 2022.
Tifrea, A., Lahoti, P., Packer, B., Halpern, Y., Beirami, A., and Prost, F. Frappé: group fairness framework for post- processing everything. arXiv preprint arXiv:2312.02592, 2023.
Yang, J., Soltan, A. A. S., Yang, Y., and Clifton, D. A. Algorithmic faimess and bias mitiga- tion for clinical machine learning: Insights from

---

FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
A. Example of KPC as Generalized Squared Partial Correlation
We use a simple example to illustrate that KPC can be viewed as the generalized squared partial correlation between U and V given W. To see this, we first recall that M D2 Pv) ll -vvl where H RKHS and pe Ek(,, U) is the kernel mean embedding of distribution Pt (Gretton et al., 2012) and consider the special case where the kernel is linear and U aW + 3V with W, V E being independently distributed with mean 0 and variance 1. In this case, we have w. (aW + 3V, 1), Puiw = NaaW, 1 + (²) and Pt= NN 1 + a² + 8²). Then, the numerator in KPC(U, VIW) becomes: E|MM D2 (Po,, P Poww] = El(aW + BV - a 3². The denominator becomes: 3 + 1. Hence, we can see that KPC(U, V(W) reduces to the squared s
E[MMD (ōv, Pu = EIU a
classical partial correlation between U and V given W: PCC(U, VIW) = (puv-w) ) = 14 In this special model, we know that U is conditionally independent of given W if and only the partial correlation/KPC is (B =0).
B. Proofs
Proof of Theorem 2.1. Let S(A) (AI...., A denote the row set of the observed realizations of sensitive attributes (unordered and duplicates are allowed). Let X, Y == f(X) and Y be the associated feature, prediction, and response observations. Recall that, with slight abuse of notations, we have used g(-) to denote both the density for continuous variables or potentially point mass for discrete observations. For example, if we have continuous variable U and discrete variable V, then, qu.v (u, v) = QUIV (ulv)gv(() with (v) the point mass at for V and (uj((ule) is the conditional density of U given V = e. Similar convention is adopted for the definition of IP, e.g., P(U = u, V =) (ulv (v), PUU = u, V S v) = E' (wlv/vlv) (v'), IPU S u, V u) = Ev' quiv (1f (V (v))gv(( (v")))gv("")))) (v")du'.
1. Task I: Show that À generated by ICP is valid conditional permutation of A, as generated by CP.
Proof of Task 1. Recall that conditional on S (A) S for some S = {(a,,..,, an). we have (Berrett et al., 2020):
P'Iy (a Y)
(A = a. S(A) S. Y) Evess, DAlY (ax Y)
(8)
where a = (ai,..., (.))))....)) is the stacked a values in S. On the other hand, conditional on S(A) = S, by construction:
P (Y,-) 7-1 a) Ex 98 A (Y 1/a) En Li (ar Y
2a (ax Y)
P (AA=a,(S(A)=
(9)
//
where the last equality utilizes the following fact,
Si.A (Y a)) Ex M (Y 1/a) Exess, Pi, (Yx 1, Ex'es, Li,A (Y, arr)
2/ (Y,-) a)
S (Y,a,) aa))
LApr (az Y
Exe rr d'Ily (ar YY)
Hence, by construction, we must have P 7 {A a. (S(A = =
P P a. S(A) S, Y}
2. Task 2: Show that (Y,A,
given conditional independence Y 1 A\Y. Proof of Task By Task 1, we can show that A Y d A|Y:
PA < t|Y)= = Y < Y S(A)= = S)] = ES < t/Y, = =P]]= tt|Y).
Additionally, under the assumption that A J. ý Á 1 V1 by construction since Á depends on the observed data only through Y and S(A). Consequently, we have
98 A. v a.y) 1 ( 988 (11)) (f.
Proof of Proposition 2.2. The proposed test is a special case of the Conditional Permutation Test (Berrett et al., 2020), so the proof is a direct result from Theorem 2.1 in our paper and Theorem in (Berrett et al., 2020).
12

---

FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
C. Sampling Algorithm for ICP
To sample the permutation from the probabilities:
9" (Y A)
P = Y,
E ES, 9"' (Y x
A)
we use the Parallelized pairwise sampler for the CPT proposed in Berrett et al. (2020), which is detailed as follows:
Algorithm 3 Parallelized pairwise sampler for the ICP
Input: Data (A, Y), Initial permutation IT.0,, integer S 2 1.
1: sor 1.......: do
2: Sample uniformly without replacement from {I,...,,y n to obtain disjoint pairs
..... (I,,1.0,1),. ...., (is. (fs.1m//)).a.((=/2))
3: Draw independent Bernoulli variables Bs,,,..., Ba,In/21 with odds ratios
P {B.b = (Y(m-- (Gan)) Aine) (Ymm-- ((swa Ajax))
P (Ba,k =0] (Y(nt-)(ss)e)) Ainx) -9 (Y(nl- AAsni
Define [1s) by swapping [1 (da,)) and I1[s-1] (Jo.k) for each & with B = 1.
4: end for
Output: Permuted copy À A [[s]] 1.
D. A dditional Comparisons of CP/ICP
When we know the true conditional laws (+) (conditional density Y given A) and (-) (conditional density A given Y). both CP and ICP show provide accurate conditional permutation copies. However, both densities are estimated in practice, and the estimated densitics are denoted as (.)) and i y (.) respectively. The density estimation quality will depend on both the density estimation algorithm and the data distribution. While a deep dive into this aspect, especially from the theoretical aspects, beyond the scope, we provide some additional heuristic insights assist our understanding of the potential gain of ICP over CP.
D.1. When ICP Might Improve over CP?
According to proof argument of Theorem in Berrett al. (2020), let A be some permuted copies of A according the estimated conditional law 4 (), upper bound of exchangeability violation for A and A, is related to the total variation between the estimated density Z (-) and ΩA (.) (Theorem 4 in Berrett et al. (2020)):
drv ((YY,)), (Y, A. Y). (YY,)), (Y, A
n <drv ( QAIl T (.lee), II aA (y
12
(b))
" < Σ dwwl
(10)
where step (b2) is from Lemma (B.8) from Ghosal & van der Vaart (2017). We adapt the proof arguments of Theorem in Berrett al. (2020) to the ICP procedure.
Specifically, let Y, be the conditional permutation of Y according to q (a.) and Y be new copy sampled according (r)a(.). We will have
n2
(iv(((YA),CC) A)JA)) Σ
dnv(ária(1A)) a(1A.))
(11)
13

---

FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
There is one issue before we can compare the two CP and ICP upper bounds for exchangeability violations: the two bounds consider different variables and conditioning events. Notice that we care only about the distributional level comparisons, hence, we can apply permutation x- to (Y, A) and (Y, AA-1). The resulting (Y, Ar 1) is equivalent to (Y, A) and the resulting (Y, - is exactly the ICP conditionally permuted version. Next we can remove the conditioning event by marginalizing out and A in (10) and (11) respectively. Hence, we obtain upper bounds for violation of exchangeability using CP and ICP permutation copies, which is smaller for ICP if (.) is more accurate on average:
A [drv (
< By [(rr((0ar((1))-arr(()))
D.2. ICP Achieved Higher Quality Empirically with MAF Density Estimation
Here, we compare ICP and CP using MAF-generated densities. The gettaaeeeggiingg process is the same as Section 3.1. Note that by design, the linear fit shown in the main paper is favored over MAF for estimating y in this particular example. There may be better density estimation choices in other applications, but overall, estimating Y|A can be simpler and allows us to utilize existing tools, e.g., those designed for supervised learning.
KD+3
KO-5
KO 1000
-4.0
Resticied TV
method
CP MAF
-5.0
ICP, NAF
-60
10
20 100
100
Figure 5: Restricted TV distances (log 10 transformed) between permutations generated by ICP/CP using estimated densities by MAF and the oracle permutations generated by true density. Each graph contains results over 20 independent trials the noise level K increases, with Ku- 1,5, 5, respectively.
E. Experiments on Fairness-Aware Learning Methods Comparisons
In both simulation studies and real-data experiments, we implement the algorithms with the hyperparameters chosen by the tuning procedure as in Romano et al. (2020), where we tune the hyperparameters only once using 10-fold cross-validation on the entire data set and then treat the chosen set as fixed for the rest of the experiments. Then we compare the performance metrics of different algorithms on 100 independent train-test data splits. This same tuning and evaluation scheme is used for all methods, ensuring that the comparisons are meaningful. For KPC (Huang et al., 2022), we use Package KPC (Huang, 2022) with the default Gaussian kernel and other parameters.
E.1. Simulation Studies
For all the models evaluated (FairICP, FairCP, FDL., Oracle), we set the hyperparameters follows:
We set ff as linear model and use the Adam optimizer with a mini-batch size in (16, 32, 64). learning rate in {lc-4, 1c-3, 1e-2), and the number of epochs in (20, 40, 60, 80, 100, 120, 140, 160, 180, 200). The discriminator is implemented as a four-layer neural network with hidden layer of size 64 and ReLU non-linearities. We use the Adam optimizer, with a fixed learning rate of le-4.
For the MAF used to estimate the conditional density (YlA and A|Y) in the training phase, we use MAF with one MADE component and one hidden layer with 2 conditional inputs nodes, and for optimizer we choose Adam with 0.01 4 penalty and 0.1 learning rate.
14

---

FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
E.I.I. LOW SENSITIVE ATTRIBUTE DEPENDENCE CASES
We report the results with A-dependence w 0.6 in Figure 6.
A
B
Violation of Equalized Odds:
Violatoon of Equalized Odds: test on statistical power
Violation of Equalized Odds:
Violation of Equa izzalized Odds: test statistical power
test on KPC
test on KPC
2.25
Oracle
225
Oracle
2.20
FairCCP
2.00
FairICP
2.0
1.6
2.15
FairCP
215-
Lo50
FairCP
FDL
FDL
1.4
2.05
2.05
3.2-
1:2
2.20
2.00
2.0
1.0
0.2
0.5
5.05
0.05
0.10
566
suossualig pasearyui
25.0
KPC:
23.0
Power: dim
1o0gssaae Dn mrreased
KPC: dim
Power:
22.5
22.5
Less
20.0
Lo55
17.5
17.5
15.0
15.0
12.5
12.5
0.05
0.10
0.15
0.20
6.25
0.7
0.6
0.50
0.05
0.10
0.15 0.20
0.2
0.4
0.5
0.8
KPC: dim =
Power: dim 5
KPC: dim = 5
Power: dim
=
120
120
10-
10-
100
100
LO:55
0.200 0.125 0.150
5:175
0.200
0.80
0.85
0.30
1.50
0.0
9.1
0.2
0.6
KPC: dim 10
Power: dim
KPC: dim
Power: dim -10
(a) Simulation
(b) Simulation 2
Figure 6: Prediction loss and metrics of fairness in simulation over 100 independent runs under Simulation I/Simulation 2 and wr 0.6. For each setting, conditional dependence measure KPC and statistical power ['ppvvluee < 0.05) are shown in the left column and right column respectively. From top to bottom shows the results on different choices of the noisy sensitive attribute dimension of K. The X-axis represents the metrics of fairness and the Y-axis is the prediction loss. Each graph shows the proposed method FairlCP, FDL, and oracle model with different hyperparameters js.
E.2. Real Data Model Architecture
Regression Tasks For FairICP and FDL (code is adapted from petps://githhn htttps////gttub..co//rraaaae www./////ooooooaaatt.oooo
dummies), the hyperparameters used for linear model and neural network are follows:
Linear: we set f as a linear model and use the Adam optimizer with MSE loss and a mini-batch size in {16, 32, 64), learning rate in {1e-4, 1e-3, 1e-2), and the number of epochs in {20, 40, 60, 80, 100). The discriminator is implemented as four-layer neural network with a hidden layer of size 64 and ReLU non-linearities. We use the Adam optimizer, with cross entropy loss and a fixed learning rate of 1e-4. The penalty parameter is set as (0,0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.93.
Neural network: we set f as a two-layer neural network with a 64-dimensional hidden layer and ReLU activation function. The hyperparameters are the same as the linear ones.
: we use MAF with 5 MADE components and two hidden layers of 64 nodes each. We use Adam optimizer with 0.001 learning rate.
Density estimation of Y|A and AlY:
For HGR (code is adapted from https: hyperparameters used for the linear model and neural network are as follows:
the http:///tttteeeeeererre//ooooooa
Linear: we set / as a linear model and use the Adam optimizer with MSE loss and a mini-batch size in [16, 32, 64). learning rate in { [Ic-4, 1c-3, 1c-2), and the number of epochs in {20, 40, 60, 80, 100). The penalty parameter À is set as (0, 0.25,, 0.5, 0. 0.75, 2,4, 16).
Neural network: we set f as a two-layer neural network with a 64-dimmesio hidden layer and SeLU activation function. The hyperparameters are the same as the linear ones.
15

---

FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
Classification Tasks
For FairCCP and FDL, the hyperparameters used for linear model and neural network are as follows:
Linear: we set f as linear model and use the Adam optimizer with cross entropy loss and mini-batch size in {128, 256}. learning rate in {le-4, 1e-3, le-2), and the number of epochs in {20, 40, 60, 80, 100, 120, 120, 140, 160, 180, 200). The discriminator is implemented as a four-layer neural network with hidden layer of size 64 and ReLU non-linearities. We use the Adam optimizer, with cross-entropy loss and fixed learning rate in (1e-5, le-4, 1e-3). The penalty parameter J is set as {0, 0.3, 0.5, 0.7, 0.8, 0.9}.
Neural network: set f as two-layer neural network with 64-dimensional hidden layer and ReLU activation function. The hyperparameters are the same as the linear ones.
Density estimation of Y|A: we use two-layer neural network classifier with 64 hidden nodes and ReLU. We use Adam optimizer with cross-entropy loss and a 0.001 learning rate.
For HGR, the hyperparameters used for the linear model and neural network are as follows:
Linear: we set f as a linear model and use the Adam optimizer with cross entropy loss and mini-batch size in {64, 128, 256), learning rate in { f1e-4, le-3, le-2), ,, and the number of epochs in {20, 40, 60, 80, 100}. The penalty parameter À is set as {0, 0.0375, 0.075, 0.125, 0.25, 0.5, 0.75, 1, 1.5).
Neural network: set f as a two-layer neural network with a 64-dimensional hidden layer and SeLU activation function. The hyperparameters are the same as the linear ones.
For GerryFair (code is adapted from https: /ttp:://gittie githtb..bb......g wwt. ccwp/alllooaacccppm//errraaaaal the hyperparameters used for the linear model and neural network are as follows:
Linear: use the default linear regression in sklearn. The iteration of fictitious play is 500, and the trade-off parameter is in [0.001, 0.03). We choose FPR as the fairness metric.
Neural network: set as a two-layer neural network with 64-dimensional hidden layer and ReLU activation function. Adam optimizer is used with learning rate set in {0.001, 0.005) and batch size in (128, 256). The rest of the parameters are the same in the linear case.
For Reduction (we use the package from https:://gtthtie used for the linear model and neural network are as follows:
http://hh...co/aaaaaaaaaaaaaaalr the hyperparameters
Linear: we use the default logistic regression in sklearn. The maximum iteration 50, and the trade-off parameter is in [0.5, 100].
Neural network: we set f as two-layer neural network with a 64-dimensional hidden layer and ReLU activation function. Adam optimizer is used with a learning rate set in (0.001, 0.0001} and batch size in {128, 2563. The rest of the parameters are the same as the linear case.
E.3. Pareto Trade-Off Curves Based on Equalized Odds Testing Power
Crimes 1dim 3dim
ACS Income
Adult
COMPAS
TairCCP: 1dim
0.26
FainCP
0.185
FairCP
0.48
FainCCP
FDL: Idim
HGR
Reduction
0.46
Reduction
0.55
HGR: Idim
3dim
0.25
GerryFiir
0.100
FDL
HGR
0.44
HGR
0.50
FDL: 3dim
0.24
Gerryfair
0.42
Gerryfair
3dim
0.170
0.45
0.165
0.38
0.40
0.22
0.36
0.35
0.21
0.155
0.34
0.2
0.4
0.6
0.8
1.0
0.80
0.85
0.90
0.95
1.00
0.2
0.4
0.6
0.8
0.1
0.2
0.3
0.4
Power
Power
Power
Power
Figure 7: Prediction loss and violation of equalized odds (measured by Power) obtained by different methods on CrimesIACS Incomel AdulsCOMPAS data 100 random splits. The Pareto front for each algorithm obtained by varying the faimess trade-off parameter.
16

---

FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
E.4. Pareto Trade-Off Curves Based DEO
Apart from KPC and the corresponding testing power, we also consider the standard fairness metric based on the confusion matrix (Hardt et al., 2016; Cho et al., 2020) designed for binary classification task with categorical sensitive attributes to quantify equalized odds:
DEO Σ
Σ vef0,1) =E2
Pr(Y 11 Z 2, Y v) Pr(Y = 1 = n)1
where Y is the predicted class label.
Adult
COMPAS
FaInCP
0.48
FairiCP
0.185
Reduction
Reduction
HEi
0.46
HGR
0.180
Gerryfair
CerryFair
0.42
0.40
0.165
0.160
0.36
0.155
0.34
0.20
0.25
DEO
DEO
Figure 8: Prediction loss and violation of equalized odds (measured by DEO) obtained by different methods Adul:/CMMAA data over 100 random splits. The Pareto front for each algorithm obtained by varying the faimess trade-off parameter.
E.5. Rumning Time
We report the running time with neural networks as below:
Crimes (one race)
Crimes (all races)
ACS Income
Adult
COMPAS
FairCCP
29.4
34.6
680.7
293.1
59.8
HGR 14.6
17.8
309.8
98.2
61.4
FDL.
28.9
39.2
/
289.4
67.6
GerryFair
2834.4
1487.4
194.8
Reduction
334.1
171.1
Table 2: The running time (in seconds) to run a single point on the trade-off curve for each method. Each number is an average of trials.
E.6. Pareto Trade-Off Curves for Linear Models
We report the results with / as a linear model in Figure 9 for the Communities and Crime dataset (regression), in Figure 11 for the Adult dataset (classification) and in Figure 12 for the COMPAS dataset (classification), which are similar to NN version.
Violation of Equalized Odds: test dependence measure KPC
Violation of Equalized Odds: test on statistical power
- FairCPP: 1dim
FairiCP: idim
1dim
0.525
1dim
0.500
HGR: 1dim
0.500
HGR: ddmm
FairlPP; 30lm
PairCPP: 3dim
0.475
3dim
0.475
3dim
HGR: 3dim
HGR: 3dim
0.450
0.450
0.425
0.425
0.400
0.400
0.375
0.375
0.350
0.00
0.05
0.15
0.25
0.30
1.0
KPC
Power
Figure 9: Prediction loss and violation of equalized odds (measured by KPC and statistical power (pp-value < 0.05)) obtained by 3 different training methods in Communities and Crime data over 100 random splits. Each graph shows the results of using different A: 1 dim = (African American) and dim (African American, Hispanie, Asian). The Pareto front for each algorithm is obtained by varying the fairness trade-off parameter.
17

---

FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
Violation of Equalized Odds:
Violation Equalized Odds:
test dependence KPC
test power
FairCCP
FairCCP
0.30
HGR
0.30
HGR
Gerryfair
Gerryfair
0.29
0.28
Loss
0.26
0.26
0.24
0.24
0.04
0.05
0.06
0.07
0.96
0.97
0.98
0.99
1.00
KPC
Power
Figure 10: Prediction loss and violation of equalized odds (measured by KPC and statistical power P(p- valuee < 0.05)) obtained by different training methods in ACS Income data over 100 random splits. The Pareto front for each algorithm is obtained by varying the faimess tradc-off parameter.
Violation of Equalized Odds: test on dependence measure KPC
Violation Equalized Odds: test on power
Violation of Equalized Odds:
test on dependence measure DEO
FairlCP
FairICP
FairICP
Reduction
Reduction
HGR
HGR
HGR
0.200
FDL
0:200
FDL
0.200
FDL
Loss
0.195
GerryFair
0.195
Gerryaair
Loss
0.195
GerryFair
0.190
0.130
0.130
0.185
0.185
0.185
0.180
0.180
0.005 0,010 0.015 0.020 0.025 0.030 0.035
0.0
0.2
0.4
0.6
0.8
0.1
0.2
0.3
0.4
0.5
KPC
Power
DEO
Figure 11: Prediction loss and violation of equalized odds (measured by KPC, statistical power P(p-value < 0.05) and DEO) obtained by 5 different training methods in Adult data over 100 random splits. The Pareto front for each algorithm is obtained by varying the fairness trade-off parameter. Some points GerryFair are out of the graph on the right.
Violation of Equalized Odds: test on dependence measure KPC
Violation of Equalized Odds:
Violation of Equalized Odds: test on dependence measure DEO
test power
FairICP
FairCCP
FainCP
0.46
Reduction
0.46
Reduction
0.46
0.44
HGR
0.44
HGR
0.44
HGR
FDL
GerryFair
0.42
GerryFair
Gerryfair
Loss
0.40
0.38
0:38
0.38
0.36
0.36
0.34
0.1
0.4
0.7
KPC
Power
DEO
Figure 12: Prediction loss violation equalized odds (measured by KPC, statistical power P(p-value < 0.05) and DEO) obtained by 5 different training methods in COMPAS data over 100 random splits. The Pareto front for each algorithm obtained by varying the faimesss trade-off parameter.
18


Reviews:
[{"review_id": "5vK5YpLY7C", "reviewer": "Reviewer_Vhcm", "summary": "The authors tackle the problem of enforcing equal odds during training, where the protected attribute is multi-dimensional. They propose FairICP, which constructs a synthetic sensitive attribute via a procedure which involves sampling from a learned $q(Y \\mid A)$. Then, a discriminator network is added to distinguish between the real and fake $(Y, A, \\hat{Y})$, and the model is penalized if these are distinguishable. The authors evaluate their method against the baselines and find that it achieves a better Pareto front.\n\n## update after rebuttal\n\nI have gone through the rebuttal and the comments from other reviewers. I thank the authors for their additional experiments. However, I believe the lack of novelty (W1) is still a significant weakness that I am not satisfied with. Further, I still believe that the potential application of the method is limited (W2), as it is only useful in cases where the A is high dimensional enough that there is a significant difference in estimation of Y|A vs A|Y, but not high dimensional enough that both fail (and where Kearns et al., (2018) would presumably be better). Finally, as also raised by other reviewers, the performance/fairness improvements are not consistent over the baselines, especially in the rebuttal results. For these reasons, I will keep my score.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the feedback from the reviewer. Here are our responses:\n\n1. Novelty of the paper over FDL. \n    \n    **Reply.** Thank you for sharing your concern. We agree that our core insight is not complicated, yet it has not been previously explored and is effective. \n\n    1) While we adopted adversarial learning (Algorithm 1) as in FDL [1], the main contribution of our work is a better way of generating synthetic $\\tilde A$ for equalized odds with multi-dimensional (mixed) $A$ (line 090-096).  FDL does not discuss how to estimate $q(A \\mid Y)$ when $A$ is complex, which is important for fair ML. Also, the nature of conditioning for equalized odds makes it more difficult than the demographic parity setting (e.g., prior work using VAE [4]). As far as we are aware, no other proposal has been designed for our setting. \n\n        The ICP sampling scheme guides training and can measure equalized odds (Algorithm 2). The reported KPCs reflect the same trend of the hypothesis testing (Algorithm 2) when the ground truth is known (Figure 3). This result is useful as ground truth is unknown in practice, which makes results from Algorithm 2 subject to density estimation, but the KPC itself is not (line 354-360).  \n\n    2)  While our proof uses Bayes rule, the ICP procedure has not been proposed before. The simplicity in the proof does not contradict its usefulness. For example, one influential result in the classical density ratio estimation is framed as a classification problem [7]. The validity of this transformation is also just Bayes rule, but doesn’t reduce its novelty or utility.\n\n2. \"The estimation of $Y | A$ gets worse with high-dim A.\"\n\n    **Reply.** We apologize for the confusion. If the problem is intrinsically hard, e.g., there are $n$ samples with each $(Y_i, A_i)$ being drastically different, even the distribution of $Y|A$ will be poorly estimated. However, estimation of the $(A|Y)$ is not easier in this setting. \n\n    The gain of using $Y|A$ are twofold (line 110-124): \n\n    1) Machine learning approaches can more effectively leverage the structure of $Y | A$ than the direct estimation of $A|Y$. E.g., when $(Y, A)$ are jointly Gaussian with sparse connections, the former can provide better quality from using lasso (MSE bound $\\sqrt{\\frac{s\\log p}{n}}$ under sparsity condition $s$, [e.g.,8]) whereas the latter is prone to more errors even when using graphical lasso (Frobenius bound $~\\sqrt{\\frac{(s^2+p)\\log p}{n}}$, e.g., [6]), which can also be evidenced by our Figures 2. These bounds on density estimation will in turn upper bound the quality of the conditional permutation (Appendix C.1). \n\n    2) Modeling $Y \\mid A$ avoids directly estimating complex dependencies in multidimensional $A$ (e.g., continuous and binary variables). Instead, dependence in $A$ is naturally incorporated through $Y \\mid A$, simplifying implementation.\n\n    We have now clarified this further in section 2.2.\n\n3. More baselines\n    \n    **Reply.** We thank the reviewer for this valuable suggestion. We add two more baselines in experiments: FDL [1] and Kearns et al. [2].   [Link for experiments added](https://docs.google.com/document/d/1CLwxWwBRsVrYhhIfeC3_IsDBZ0mAoRiZVWWGLv4DDIw/edit?usp=sharing). We also ran [2] for Adult but found it failed to converge with limited time given (also evidenced by Figure 1 in its paper). Nonetheless, we agree this could be a good complement and we will update it once it's done.\n    \n    For LAFTR, we find it can only be applied to a single binary $A$, which differs from our main target in this paper.\n\n5. \"The DEO is still quite large.\"\n    \n    **Reply.** We apologize for the confusion. We calculated DEO (line 823) as the sum of TPR and FPR differences as in [9], while some work [10] defines it as the max of differences, which explains why our results appear to be large. Our method still provides generally smaller DEOs, which indicates the consistency of KPC and DEO (Figure 8 and Table 1).\n\n## References\n\n[1] Romano et al. Achieving equalized odds by resampling sensitive attributes. \n\n[2] Kearns et al. Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness. \n\n[3] Madras et al. Learning Adversarially Fair and Transferable Representations. \n\n[4] Creager et al. \"Flexibly fair representation learning by disentanglement.\" \n\n[5] Tansey et al. \"The holdout randomization test for feature selection in black box models.\" \n\n[6] Wang et al. \"Precision matrix estimation in high dimensional gaussian graphical models with faster rates.\"\n\n[7] Menon et al. Linking losses for density ratio and class-probability estimation. \n\n[8] Wainwright et al. High-dimensional statistics: A non-asymptotic viewpoint.\n\n[9] Cho et al. A fair classifier using kernel density estimation.\n\n[10] Agarwal et al. A reductions approach to fair classification.", "claims_and_evidence": "1. The novelty of the paper over Romano et al. (2020) is rather limited. Algorithm 2 is identical to this prior work, and the overall architecture (and Algorithm 1) are essentially the same as this prior work with a small tweak to the sampling which is a simple application of Bayes rule. As such, I do not believe it presents a sufficiently novel algorithmic or theoretical contribution.\n\n2. The main motivation of this work is to allow for equal odds when the attribute is multi-dimensional. However, as the dimension of A grows, the estimation of $Y \\mid A$ will become worse due to smaller per-group sample size. This seems to limit the utility of the method, and the authors have not characterized this theoretically.\n\n3. The authors state (L94) that \"While several studies have successfully addressed demographic parity under multiple sensitive attributes via permutations(Kearns et al., 2018; Creager et al., 2019), these ideas can not be trivially generalized to equalized odds since permutation of A conditional Y is still difficult and does not circumvent the challenge in distribution estimation of multidimensional complex attributes\". I do not believe this is true for Kearns et al., (2018), as they specifically examine equalizing FPR in their paper (and equalizing FNR is also possible by symmetry); and do not require estimating the conditional density. The authors should add this method as a baseline.", "methods_and_evaluation_criteria": "1. The Adult and COMPAS datasets are not great testbeds for the method as the number of groups (intersections of sex and race) is only 4. Thus, given that these are also binary classification problems, it is possible to estimate the conditional probability distribution by data analyses (without training any models), and any in-processing equal odds method would work here. For these datasets, the authors should at least show FDL as a baseline. They should also compare against the line of work on fairness via adversaries (e.g. [1]), which has a similar architecture but does not require conditional randomization.\n\n2. The author should show ERM as a single point on all Pareto plots.\n\n\n[1] Learning Adversarially Fair and Transferable Representations. ICML 2018.", "theoretical_claims": "I did not check any proofs in detail.", "experimental_designs_or_analyses": "Please see \"Methods And Evaluation Criteria\".", "relation_to_broader_scientific_literature": "The work is one of many that enforces equal odds during supervised learning. However, the paper distinguishes itself by examining the case of multidimensional attributes, where existing methods would not work or are less effective. The proposed method relies heavily on the idea of conditional randomization (Candes et al., 2018), which has been applied to enforce equal odds for univariate attributes in Romano et al. (2020). The main contribution of the paper is an alternative sampling procedure which adapts Romano et al. (2020) to the multi-attribute setting.", "essential_references_not_discussed": "Please see above.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Empirically, the DEO is still quite large (Figure 8 and Table 1). Is this because DEO is measuring fairness for binary $\\hat{Y}$ whereas the method enforces equal odds wrt the continuous score?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eMZalFJYYw", "reviewer": "Reviewer_pxLZ", "summary": "The paper introduces FairICP, a method for enforcing equalized odds fairness in machine learning models that handle multiple sensitive attributes. The key idea is to improve how synthetic versions of sensitive attributes are generated in fairness-aware learning. Instead of relying on traditional resampling or conditional permutations, FairICP estimates the relationship between the outcome and the sensitive attribute to create better-conditioned synthetic attributes. \n\nThe paper compares FairICP to existing methods such as Fair Dummies Learning (FDL) and Conditional Permutation (CP), using Kernel Partial Correlation as a fairness metric. Using a number of experiments, relying on both synthetic data and widely used datasets, the paper argues that FairICP is more effective at reducing fairness violations while maintaining predictive accuracy.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thorough review and constructive feedback on our paper, here are our responses:\n\n1. Explanation on KPC.\n\n    **Reply.** Thank you for this constructive feedback. KPC [1] is a recently proposed non-parametric measure for conditional independence without constraints on the shape of inputs. The reason why we choose $KPC(U,V|W)$ aligns with our main goal in this paper: enforcing equalized odds (a conditional independence notion) for multiple $A$ (i.e., making $KPC(\\hat{Y}, A|Y)$ small). Additionally, $KPC(U, V|W)$ has been well normalized for direct comparison across different models (supported by our experiments (line 354-360)), and it can be viewed as a generalization of Partial Correlation between $U|W$ and $U|W,V$. \n\n    To see this, we first recall that MMD distance $MMD(U, V)=||\\mu_{U}-\\mu_{V}||_{\\mathcal{H}}^2$ where $\\mathcal{H}$ is RKHS and $\\mu_U = \\int k(,;u)d P_U(u)$ is the kernel mean embedding of a distribution $P\\_U(.)$ [9] and consider the simple case where the kernel is linear and $U = \\alpha W + \\beta V+\\varepsilon$ with $W, V, \\varepsilon$ being i.i.d $\\mathcal{N}(0, 1)$. We then have $P\\_{U|W,V}=\\mathcal{N}(\\alpha W+\\beta V, 1)$,  $P\\_{U|W}=\\mathcal{N}(\\alpha W, 1+\\beta^2)$ and $P\\_{U}=\\mathcal{N}(0, 1+\\beta^2)$. Then, the numerator in $KPC(U,V|W)$ becomes: $E[MMD^2(P\\_{U|W,V}, P\\_{U|W})]=E[(\\alpha W+\\beta V-\\alpha W)^2]=\\beta^2$. The denominator becomes: $E[MMD^2(\\delta\\_{U}, P\\_{U|W})]=E[(U-\\alpha W)^2]=\\beta^2+1$.\n\n    Hence, we can see that $KPC(U, W, V)$ reduces to the squared correlation between $U|V$ and $U|W,V$: $KPC(U, W, V)=\\rho^2_{U,W|V}$. In this simple case, $U$ is conditionally independent of $V$ given $W$ iff the partial correlation/KPC is 0 ($\\beta$ = 0). \n\n    KPC is not the only choice in our setting, and one can choose other conditional dependence measures that allow multi-dimensional inputs (e.g., CODEC [2], though it can be viewed as a special case of KPC). In our paper, the robustness of KPC is evidenced by comparing the similar curve given by other metrics (power of hypothesis testing and DEO, figure 4/7/8 and table 1).\n\n    We thank the reviewer again for this valuable question and we have included some of the intuition in our revised paper.        \n\n2. \"Why the experiments not compare ICP to some methods?\"\n\n    **Reply.** We apologize for this confusion. This is due to the differences in their applicability: HGR [3] is designed for univariate continuous $A$ and Reduction [4] is only for binary classification and binary attributes. We introduce HGR [3] (in line 105-109) and detail how we generalize it to multiple attributes (line 436-439). We cite Reduction [4] in line 083 and detail it in line 422-425. We now have made it clearer in our revised paper.\n\n    We have also added two more baselines in experiments: FDL [7] and Kearns et al. [10] (introduced in line 096).   [Link for experiments added](https://docs.google.com/document/d/1CLwxWwBRsVrYhhIfeC3_IsDBZ0mAoRiZVWWGLv4DDIw/edit?usp=sharing). We also ran [10] for Adult but find it failed to converge with limited time given (also evidenced by Figure 1 in its paper). Nonetheless, we agree this could be a good complement and we will update it once it's done.\n\n    \n3. \"Consider post-processing\"\n\n    **Reply.** Thank you for raising this interesting direction. As post-processing and in-processing conventionally represents two different paradigms: the former focuses on training $f(X)$, whereas the latter focuses on recalibrating the probability cutoffs across binary $A$ for binary response (e.g., [6]) and requires test-time access to $A$. Thus, we view it as complementary rather than competing with each other. In fact, one recent work by Tifrea et al. [8], as the rare post-processing work that can work with both a categorical/continuous $A$, proposed to post-process any baseline model, either ERM or in-processing ones. \n\n    Like many in-processing methods, existing post-processing ones are not designed for complex $A$, especially under the equalized. This also raises the question if the idea of ICP can be also utilized in post-processing. We now have included these discussions as future directions in our discussion section.\n\n## Reference\n\n[1] Huang et al. \"Kernel Partial Correlation Coefficient---a Measure of Conditional Dependence.\" \n\n[2] Azadkia et al. A simple measure of conditional dependence. The Annals of Statistics\n\n[3] Mary et al.. Fairness-aware learning for continuous attributes and treatments. \n\n[4] Agarwal et al. A reductions approach to fair classification.\n\n[6] Kim et al.: Black-Box Post-Processing for Fairness in Classification.\n\n[7] Romano et al. Achieving equalized odds by resampling sensitive attributes. \n\n[8] Tifrea et al. \"Frappé: A group fairness framework for post-processing everything.\"\n\n[9] Tolstikhin et al. \"Minimax estimation of maximum mean discrepancy with radial kernels.\"\n\n[10] Kearns et al. Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness.", "claims_and_evidence": "The core claims of the paper are that ICP is a superior method for approximating the true conditional distribution and that this better sampling method leads to a better fairness-accuracy tradeoff (which is the ultimate goal). \n\nNot being a theorist it is hard for me to fully evaluate the theoretical merits of the analysis but I do think that the authors could have put more effort into intuition building. For example, a key element of the analysis is the metric for measuring fairness- kernel partial correlation (KPC). While the authors define the metric mathematically, they do not explain why KPC is an appropriate metric for fairness in this context. Even a simple graphical intuition would have been helpful in understanding what this metric is capturing. It would have been helpful to have a toy example that could concretely demonstrate why CP struggles in a way that ICP does not, or why FDL might introduce bias.", "methods_and_evaluation_criteria": "The paper evaluates the method on widely used datasets like COMPAS and ACSIncome, which facilitates comparison with previous work. However, the various choices over which approaches to compare are somewhat opaque. For example, why do the empirical examples not compare ICP to CP? Why is FDL not considered consistently? Why is there a comparison to HGR, which is only very briefly mentioned in the theoretical discussion? The reduction method is not discussed before being used in the example.\n\nRelated to the point above, what are the alternatives to the KPC fairness metric? How sensitive are the results of the use of KPC?", "theoretical_claims": "I did not check for the correctness of appendix proofs.", "experimental_designs_or_analyses": "See above for my discussion of experiments.", "relation_to_broader_scientific_literature": "The paper relates to a core challenge within the algorithmic fairness literature of how to treat fairness when sensitive attributes are multidimensional.", "essential_references_not_discussed": "I do not have a specific reference that was not included", "other_strengths_and_weaknesses": "The biggest strength of the paper is the importance of the issue it is addressing. It has always been a fundamental weakness of the algorithmic fairness literature that it focuses on fairness within one dimension of a protected characteristic when in many cases there are multiple such characteristics that often intersect. Similarly, the choice of the article to focus on equalized odds, although not explicitly discussed, is reasonable given the importance of considering how predictions vary by group, conditional on real outcomes. \n\nGiven the potential policy significance of creating an easily implementable method, it is unfortunate the paper is not written in a more accessible way and that it spends little time explaining the intuition for its choices of metrics, superiority of methods and shortcomings of other methods.", "other_comments_or_suggestions": "To reiterate the point above, I think it would really improve the paper if the authors spent more time building up intuition for the theoretical claims, the superiority of their claims, and their choice of evaluation metrics. \n\nIn analyzing the evaluation of their method, the authors might also consider other methods for equalizing odds, like post-processing, and how they compare with respect to the fairness-accuracy tradeoff. While their choice to focus narrowly on equalizing odds rather than other fairness metrics, it would be beneficial to compare other approaches to equalizing odds. \n\nI also suggest clarifying the various choices made with respect to the real-world experiments, particularly because the comparison to other methods does not fully align with the methods discussed in the previous theoretical section.", "questions_for_authors": "To summarize the points above, my main questions/issues are:\n1. Why do the real world experiments compare ICP to some methods and not others?\n2. How does ICP compare to post-processing methods?\n3. Is there a way to make the paper more accessible by building up intuition and explaining evaluation choices?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5mfmrbiRwy", "reviewer": "Reviewer_NoT1", "summary": "- This study introduces a permutation-based learning algorithm for developing fair predictive models.\n- The fairness notion considered in this work is equalized odds.\n- The proposed permutation mechanism generates pseudo-sensitive attributes with aligning the distributions of $(\\hat{Y}, A, Y)$ and $(\\hat{Y}, \\tilde{A}, Y)$.\n- The proposed generation mechanism is designed to accommodate both continuous and discrete sensitive attributes.\n- Experimental results suggest that the proposed method achieves a superior fairness-prediction trade-off compared to two baseline approaches.\n\n## update after rebuttal\n\n- Thanks to the rebuttal, which includes the additional experiments, I will raise my rating to 3.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the feedback by the reviewer. Here are our responses:\n\n1. Methods: more baselines.\n    \n    **Reply.** We thank the reviewer for this valuable suggestion. We add two more baselines in experiments: FDL [4] and Kearns et al. [5].   [Link for experiments added](https://docs.google.com/document/d/1CLwxWwBRsVrYhhIfeC3_IsDBZ0mAoRiZVWWGLv4DDIw/edit?usp=sharing). For ACS income/Adult, we also ran [5] as the reviewer suggests, but we find it failed to converge with limited time given (also evidenced by Figure 1 in its paper). Nonetheless, we agree this could be a good complement and we will update it once it's done.\n\n    We also thank the reviewer for the generalized DP paper ([3]), however, we find that its goal to extend demographic parity is fundamentally different from our goal (equalized odds), and it's also non-trivial to extend it to the best our knowledge. We have included it into our related work section.\n\n2. Metric:\n\n    (1) Accuracy for classification\n        \n    **Reply.** We apologize for the confusion. Our \"Loss\" metric is misclassification rate for classification task, which is (1 - accuracy) . We will make it clearer in our revised version.\n\n    (2) Why TPR, FPR, or DEO were not mainly used?\n    \n    **Reply.** Thank you for this question. The reason why we introduce KPC is that it's a flexible metric for conditional independence without constraints for the shape of input, which well aligns with our goal to measure equalized odds for complex $A$. While DEO (TPR, FPR) is a standard measure in the previous work, it's only suitable for binary $Y$/$A$, thus can only be used in a part of our experiments (Adult/COMPAS). \n\n    (3) Presenting TPR and FPR.\n    \n    **Reply.** Thank you for this suggestion. Yes, DEO is a sum of FPR and TPR accross all binary $A$. However, when there are multiple binary $A$, it could be rather subjective to choose which subgroup's TPR(FPR) to be presented, thus making DEO a standard measure ([1, 2]).\n\n3. Math behind line 583\n\n    **Reply.** We apologize for the confusion. In Task 2, we first prove $\\tilde{A} | Y \\overset{d}{=} A | Y$, which is done by taking expectation of results from Task 1 ($P(A \\leq t \\mid Y, S(A)=S)=P(\\tilde{A} \\leq t \\mid Y, S(A)=S)$). We have now explained this in the proof for clarification.\n\n4. How stable is the adversarial learning process? \n\n    **Reply.** Thank you for this question. We agree that stability could be a potential pitfall for all the adversarial learning approaches, as pointed out in line 432-439. We adopted a vanilla GAN instead of more exquisite ones to provide a fair comparison with FDL [4], but our ICP can integrate with the more efficient methods in the area of adversarial learning. We have now clarified it further in the discussion section.\n\n5. How our method differs from existing adversarial learning-based approaches.\n    \n    **Reply.** Thanks for raising this point. \n\n    While we adopted adversarial learning (Algorithm 1) as in FDL [4], the main contribution of our work is a better way of generating synthetic $\\tilde A$ for equalized odds with multi-dimensional (mixed) $A$ (line 090-096).  FDL does not discuss how to estimate $q(A \\mid Y)$ when $A$ is complex, which is important for fair ML. Also, the nature of conditioning for equalized odds makes it more difficult than the demographic parity setting (e.g., prior work using VAE [6]). As far as we are aware, no other proposal has been designed for our setting. \n\n    The ICP sampling scheme guides both training and evaluating equalized odds (Algorithm 2). The reported KPCs reflect the same trend of the hypothesis testing (Algorithm 2) when the ground truth is known (Figure 3). This result is useful as ground truth is unknown in practice, which makes results from Algorithm 2 subject to density estimation while KPC itself is not (line 354-360). \n\n6. How does the generated $\\tilde A$ differ from the fair representation learned through adversarial learning? \n    \n    **Reply.** Thank you for this question and providing the literature. Learning fair representation is another line of work based on adversarial learning, which generally requires model to predict $A$ from the representation $Z$ (and possibly $Y$) (e.g., the work reviewer mention). When facing complex $A$, this direct way of modelling $A$ could run into the same challenge as FDL [4] does, while our FairICP avoids it as discussed. We thank you again for this suggestion and we have included this discussion into our related work part.\n\n\n## Reference\n\n[1] Cho et al. A fair classifier using kernel density estimation.\n\n[2] Agarwal et al. A reductions approach to fair classification.\n\n[3] Jiang et al. \"Generalized demographic parity for group fairness.\" \n\n[4] Romano et al. Achieving equalized odds by resampling sensitive attributes. \n\n[5] Kearns et al. Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness.\n\n[6] Creager et al. \"Flexibly fair representation learning by disentanglement.\"", "claims_and_evidence": "- Overall, the flexibility of the proposed algorithm in handling various types of sensitive attributes is supported by the experimental results.\n- However, while the authors claim that the proposed method offers a superior fairness-accuracy trade-off, it seems not consistently outperforms the baselines when the prediction model is linear.", "methods_and_evaluation_criteria": "- Metrics:\n   - (1) The authors use \"Loss\" as the primary measure of prediction performance. Including accuracy as an additional metric in classification task would enrich the evaluation part.\n   - (2) KPC: The paper primarily employs KPC as the fairness metric. Could the authors clarify why standard measures such as TPR, FPR, or DEO were not mainly used instead?\n   - (3) DEO: The paper defines DEO as the sum of TPR and FPR over $y \\in {0, 1}$. Presenting TPR and FPR separately could provide a more detailed analysis of the fairness evaluation.\n- Baseline methods\n   - The proposed method is primarily compared against three baselines. Evaluating it against additional baselines would further strengthen the validation of its effectiveness.\n   - Examples: \n      - (1) For continuous sensitive attributes: Generalized Demographic Parity, https://openreview.net/pdf/3f9ffe7eafbd44f0205f3629edbcfb60ec738e7c.pdf. Although this work focuses on demographic parity, its approach could be extended to equalized odds.\n      - (2) For mixed-type sensitive attributes: Subgroup fairness could also be applicable in this setting, as continuous sensitive attributes can be categorized via binning. https://proceedings.mlr.press/v80/kearns18a.html", "theoretical_claims": "- Question: In the proof of Task 2 of Theorem 2.1, the first equation holds when $P(A \\le t | Y, S(A) = S) = P (\\tilde{A} \\le t | Y, S(A) = S),$ while the given result from Task 1 states that $\\tilde{A} | Y \\overset{d}{=} A | Y$. Could the authors can further explain the math behind how the result of Task 1 directly leads to this equation?", "experimental_designs_or_analyses": "- Implementation details\n   - How stable is the adversarial learning process? Given that stability is critical for practical deployment, analyzing it would be valuable.", "relation_to_broader_scientific_literature": "- This paper suggests that generating pseudo sensitive attributes can contribute to learning fair prediction models.", "essential_references_not_discussed": "- Please see `Baseline methods’ in **Methods And Evaluation Criteria**.", "other_strengths_and_weaknesses": "- While the direct generation of pseudo-sensitive attributes through adversarial learning appears to be novel (to the best of my knowledge), adversarial learning-based approaches for developing fair prediction models have been extensively explored in the literature. It would be helpful if the authors could clarify how their proposed method differs from existing adversarial learning-based approaches in terms of intuition, motivation, technical aspects, and experimental results.\n- More specifically, how does the generated $\\tilde{A}$ differ from the fair representation learned through adversarial learning? It would be helpful if the authors distinguish these two approaches.\n   - Several examples are:\n      - https://dl.acm.org/doi/pdf/10.1145/3278721.3278779\n      - https://arxiv.org/abs/1511.05897\n      - https://www.cs.toronto.edu/~toni/Papers/laftr.pdf \n      - https://proceedings.mlr.press/v162/kim22b/kim22b.pdf", "other_comments_or_suggestions": "- (Minor typo) Algorithm 2: In the “Input” line, should ($X^{te}, A^{te}, Y^{te}$) be replaced by ($\\hat{Y}^{te}, A^{te}, Y^{te}$)?", "questions_for_authors": "- N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zF4Khc9E92", "reviewer": "Reviewer_pguj", "summary": "This paper introduces FairICP, a novel fairness-aware learning method designed to promote equalized odds in machine learning models when dealing with complex and multi-dimensional sensitive attributes. The method combines adversarial learning with an innovative Inverse Conditional Permutation (ICP) strategy to generate conditionally permuted copies of sensitive attributes without estimating multi-dimensional conditional densities. The paper provides a comprehensive theoretical foundation for the method and evaluates its performance through extensive simulations and real-world datasets.\n\n## Update after rebuttal\n\nThanks for your explanation, I will maintain my rating.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the feedbacks by the reviewer, here are our responses:\n\n1. \"Could you discuss more on the challenges and potential inaccuracies associated with density estimation, especially in high-dimensional spaces or with complex data types.\"\n    \n    **Reply.** Thank you for this question. We mention how the quality of density estimation will affect the performance of our ICP (and CP) sampling scheme in line 241-243, and we also provide a theoretical analysis linked to it in the Appendix C.1. Specifically, we show an smaller TV distance bound for ICP compared with CP when density estimation is inaccurate, which aligns with our claims and experimental evidence (Figure 2).\n\n\n2. \"And for the categorical case, multi sensitive attributes can be actually turned to one attribute case by separating the dataset into more subgroups. I am curious about the performance of standard fairness-aware method in this naive way. Maybe you can add this as baseline.\"\n    \n    **Reply.** We thank the reviewer for this suggestion. We now have also added two more baselines in experiments: FDL [3] and Kearns et al. [2].   [Link for experiments added](https://docs.google.com/document/d/1CLwxWwBRsVrYhhIfeC3_IsDBZ0mAoRiZVWWGLv4DDIw/edit?usp=sharing). We also tried Kearns et al. [2] for Adult dataset but it failed to converge with limited number of iteration for the short time given (as evidenced by Figure 1 in its paper), however, we agree this is an important baseline and are working to add it to our revised paper, and we will also update the results once it is done.\n\n3. While the paper compares FairICP with several baseline methods, it does not include some state-of-the-art methods for fairness-aware learning.\n    \n    **Reply.** Thanks for your feedback. We fully understand the need to compare with other methods. However, based on the literature we have searched so far, what we compared in our paper are already the most recent methods that can be applied to our setting (equalized odds, multiple (mixed) sensitive attributes). We would also appreciate it if the reviewer could point out some other cutting-edge fair machine learning methods suitable to our task. Additionally, the major novelty of this work is the ICP sampling for fairness-aware (equalized odds) learning with multiple sensitive attributes. Hence, we should consider the comparison between FairICP and FDL [3] to be the most informative and reliable evaluation of this paper's contribution in a setting where FDL is straightforward to apply.\n\n4. The ICP strategy is specifically designed for EO and may not be generalized to other fairness measures enough.\n    \n    **Reply.** Thank you for pointing this out. Our focus on the equalized odds metric is intentional, as enforcing equalized odds requires ensuring conditional independence. This conditional nature makes it a more challenging fairness criterion compared to unconditional ones like demographic parity (Tang et al.[1]).\n\n    While ICP is well-suited for enforcing equalized odds due to its ability to avoid the challenging density estimation of given, for unconditional fairness notions such as demographic parity, we can utilize unconditional permutation of which is a special case of FairICP without conditioning.\n\n5. Providing detailed information on the exact hyper parameter values or the code for reproducing the results would be more convincing.\n    \n    **Reply.** We apologize for not including code in the initial submission. We have now provided the relevant code [Link for code](https://drive.google.com/file/d/1gX4UIDPGKYEcL-yK9TtYmazi28gc_4tv/view?usp=sharing).\n\n\n## Reference\n\n[1] Tang et al. Attainability and optimality: The equalized odds fairness revisited. \n\n\n[2] Kearns et al.. Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness.\n\n[3] Romano et al. Achieving equalized odds by resampling sensitive attributes.", "claims_and_evidence": "Yes, the claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes, the proposed methods make sense for the problem (improving fairness measure EO) at hand.", "theoretical_claims": "The theoretical claims in the paper are supported by detailed proofs. The authors provide proofs for the validity of the ICP-generated permutations and their ability to promote equalized odds. The proofs are mathematically sound and well-structured. However, the robustness of these theoretical claims under model misspecification or inaccurate density estimation could be further explored.", "experimental_designs_or_analyses": "The experimental designs and analyses are generally sound. The authors conduct extensive experiments on both synthetic and real-world datasets, providing a comprehensive evaluation of the method's performance. The experimental results are presented in a clear and organized manner, and the comparisons with baseline methods are thorough. However, the paper could benefit from a sensitivity analysis to assess the impact of hyperparameters and data characteristics (how complex the sensitive attributes are) on the method's performance.", "relation_to_broader_scientific_literature": "The key contributions of the paper are well-related to the broader scientific literature. The paper builds upon existing work in fairness-aware machine learning and addresses the underexplored challenge of handling multi-dimensional sensitive attributes. The authors provide a comprehensive review of related work, including prior methods for achieving equalized odds and the limitations of existing approaches.", "essential_references_not_discussed": "The paper cites relevant prior work in the field of fairness-aware machine learning. However, it could benefit from additional references to recent advancements in multi sensitive attributes fairness techniques.", "other_strengths_and_weaknesses": "**Strengths:**\n1. The introduction of the ICP strategy is a significant contribution that addresses the challenge of handling multi-dimensional sensitive attributes.\n2. The integration of ICP with adversarial learning provides a flexible and efficient framework for promoting equalized odds.\n3. The empirical validation on both synthetic and real-world datasets demonstrates the effectiveness of the method.\n\n**Weakness:**\n1. My concern is that the ICP strategy heavily relies on the accurate estimation of the conditional density $q(Y|A)$. Could you discuss more on the challenges and potential inaccuracies associated with density estimation, especially in high-dimensional spaces or with complex data types.\n2. I feel like the experiments are conducted on a limited set of datasets. The number of sensitive attributes is limited. And for the categorical case, multi sensitive attributes can be actually turned to one attribute case by separating the dataset into more subgroups. I am curious about the performance of standard fairness-aware method in this naive way. Maybe you can add this as baseline.\n3. While the paper compares FairICP with several baseline methods, it does not include some state-of-the-art methods for fairness-aware learning.\n4. The ICP strategy is specifically designed for EO and may not be generalized to other fairness measures enough.", "other_comments_or_suggestions": "Providing detailed information on the exact hyper parameter values or the code for reproducing the results would be more convincing.", "questions_for_authors": "Please see weakness.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes FairICP, an in-processing method for enforcing equalized odds as a fairness notion in supervised learning settings with multi-dimensional and mixed-type sensitive attributes. The central technical contribution is an Inverse Conditional Permutation (ICP) procedure, which uses Bayes rule to generate pseudo-sensitive attributes without directly estimating high-dimensional conditional distributions. The ICP mechanism is coupled with adversarial training to enforce equalized odds. FairICP is evaluated across synthetic and real-world datasets and compared with several recent fairness-aware learning methods.

**Strengths**:
* The paper addresses a non-trivial gap in the fairness literature: enforcing equalized odds when sensitive attributes are multi-dimensional, mixed-type, or not easily binarized.
* The ICP-based sampling approach is a natural yet underexplored extension of prior permutation-based techniques and is simple and practical.
* The authors offer theoretical justification for the advantages of ICP over classical conditional permutation, particularly when density estimation is inaccurate (which can be a realistic scenario).
* The empirical evaluation is broad: synthetic setups and several widely used datasets (Adult, COMPAS, ACSIncome), and includes comparisons with relevant baselines like FDL, Kearns et al., and various adversarial approaches.
* The authors were responsive during the discussion phase and added additional baselines, ablations, and clarity to address reviewer concerns.

**Reviewer discussions**:
* Reviewer pxLZ (Weak Accept) appreciates the importance of the problem and finds the method promising but criticizes the writing and lack of intuition, especially around metrics like KPC. Their review is ultimately cautious but supportive.
* Reviewer NoT1 (Weak Accept) notes that while FairICP is flexible and shows good performance, it does not consistently outperform baselines under linear models. They also request more clarity in comparisons with adversarial learning-based methods. These concerns were addressed in the rebuttal.
* Reviewer Vhcm (Weak Reject) argues that the method is an incremental extension of prior work (notably Romano et al.), and point that the method’s utility is limited to a narrow set of cases and raise concerns about inconsistent performance. These concerns were addressed by the authors (and the reviewer did not engage further).
* Reviewer pguj (Weak Accept) praises the ICP idea and the ability to handle complex sensitive attributes but raises concerns about reliance on density estimation, limited datasets, and whether FairICP can generalize to other fairness criteria. These points were acknowledged and partially addressed.

**Conclusion**:
This is a borderline paper with a solid technical contribution and an important practical motivation. The proposed method is not radically novel in its architecture (building on adversarial fairness and conditional permutation), but the ICP sampling mechanism for complex sensitive attributes does seem a useful and generalizable idea. The authors provide theoretical support and empirical validation. While presentation could be improved and some reviewers remain skeptical about novelty, I find the core contribution meaningful and the paper sufficiently substantiated.
Decision: Accept (poster)