# FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation
**Authors**: Yuheng Lai, Leying Guan
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.
Machine Learning, ICML
\MakePerPage
footnote
1 Introduction
Machine learning models are increasingly important in aiding decision-making across various applications. Ensuring fairness in these models—preventing discrimination against minorities or other protected groups—remains a significant challenge (Mehrabi et al., 2021). To address different needs, several fairness metrics have been developed in the literature (Mehrabi et al., 2021; Castelnovo et al., 2022). The equalized odds metric defines fairness by requiring that the predicted outcome $\hat{Y}$ provides the same level of information about the true response $Y$ across different sensitive attribute(s) $A$ (e.g. gender/race/age) (Hardt et al., 2016):
$$
\hat{Y}\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern 2.0%
mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{$\textstyle\perp$\hss}\mkern 2%
.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptstyle\perp$\hss}\mkern 2%
.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptscriptstyle\perp$\hss%
}\mkern 2.0mu{\scriptscriptstyle\perp}}}A\mid Y. \tag{1}
$$
Encouraging equalized odds is more challenging due to $Y$ -conditioning compared to encouraging demographic parity, another common fairness notion that emphasizes equity and requires $\hat{Y}$ to be independent of $A$ without conditioning on $Y$ . Most existing algorithms targeting equalized odds can only handle a single protected attribute, and extending them to multi-dimensional sensitive attributes is challenging due to the well-known difficulties of estimating multi-dimensional densities (Scott, 2015). However, real-world scenarios can involve biases that arise from multiple 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 et al., 2018), where a model appears fair when considering each attribute separately but exhibits unfairness when attributes are considered jointly.
To address these limitations, we introduce FairICP, a flexible fairness-aware learning scheme that encourages equalized odds for complex sensitive attributes. Our method leverages a novel Inverse Conditional Permutation (ICP) strategy to generate conditionally permuted copies $\tilde{A}$ of sensitive attributes $A$ given $Y$ without the need to estimate the multi-dimensional conditional density and encourages equalized odds via enforcing similarity between $(\hat{Y},A,Y)$ and $(\hat{Y},\tilde{A},Y)$ . An illustration of the FairICP framework is provided in Figure 1.
Our contributions can be summarized as follows:
- Inverse Conditional Permutation (ICP): We introduce the ICP strategy to efficiently generate $\tilde{A}$ , as conditional permutations of $A$ given $Y$ , without estimating the multi-dimensional conditional density of $A|Y$ . This makes our method scalable and applicable to complex sensitive attributes.
- Empirical Validation: Through simulations and real-world data experiments, we demonstrate FairICP’s flexibility and its superior fairness-accuracy trade-off compared 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.
<details>
<summary>2404.05678v4/x1.png Details</summary>

### Visual Description
# Technical Document Extraction: Fairness-Aware Predictive System
## Diagram Overview
The image depicts a **fairness-aware predictive system** designed to mitigate bias in machine learning models. The workflow involves sensitive attribute handling, inverse conditional permutation, prediction, and fairness validation via a discriminator.
---
## Key Components & Flow
### 1. **Sensitive Attributes**
- **Labels**: Ethnicity, Sex, Financial Status (represented by icons: handshake, gender symbols, and financial charts).
- **Purpose**: Identifies protected attributes that could introduce bias into predictions.
### 2. **Input Data**
- **Structure**:
- **A**: Sensitive attributes (Ethnicity, Sex, Financial Status).
- **(X, Y)**: Feature matrix (X) and target variable (Y).
- **Flow**: Input data (A, X, Y) is processed through the system.
### 3. **Inverse Conditional Permutation**
- **Equation**:
- **Ã = A_II** (transformed sensitive attributes).
- **Purpose**: Generates "fair" data (Ã) by permuting sensitive attributes to decouple them from the target variable Y.
### 4. **Predictor (f)**
- **Input**: (X, Y).
- **Output**: Predicted value **Ŷ**.
- **Role**: Standard predictive model (e.g., regression, classification).
### 5. **Discriminator (D)**
- **Function**: Tests fairness of predictions.
- **Equation**:
- **D(Ŷ, Ã, Y) = (Ŷ ⊥ Ã | Y)?** (tests independence between predictions and transformed attributes given Y).
- **Validation**:
- **Fair data**: Satisfies **Ŷ ⊥ à | Y** (predictions are independent of à given Y).
- **Original data**: May violate fairness (denoted by red text: **Ŷ ⊥ A | Y (approx.)**).
---
## Textual Elements in Diagram
1. **Labels**:
- "Sensitive Attributes" (top-left).
- "Input Data" (center-left).
- "Predictor" (center).
- "Prediction" (top-right).
- "Discriminator" (bottom-right).
2. **Equations**:
- **Ã = A_II** (inverse conditional permutation).
- **D(Ŷ, Ã, Y) = (Ŷ ⊥ Ã | Y)?** (fairness condition).
3. **Annotations**:
- "Fair data" (blue text) vs. "Original data" (red text).
---
## Spatial Grounding & Component Isolation
- **Regions**:
1. **Header**: Sensitive Attributes (Ethnicity, Sex, Financial Status).
2. **Main Chart**:
- Input Data (A, X, Y) → Inverse Conditional Permutation (Ã) → Predictor (f) → Prediction (Ŷ).
- Discriminator (D) validates fairness.
3. **Footer**: None explicitly labeled.
---
## Critical Observations
1. **Fairness Mechanism**: The system uses inverse conditional permutation (Ã = A_II) to decouple sensitive attributes from predictions.
2. **Validation**: The discriminator checks if predictions (Ŷ) are statistically independent of transformed attributes (Ã) given Y.
3. **Bias Mitigation**: The goal is to ensure **Ŷ ⊥ Ã | Y** (predictions are fair) rather than relying on original biased data (**Ŷ ⊥ A | Y**).
---
## Limitations
- No numerical data or trends (e.g., heatmaps, line charts) are present.
- The diagram focuses on **conceptual workflow** rather than empirical results.
---
## Conclusion
This diagram outlines a **bias mitigation framework** for predictive models, emphasizing fairness through attribute transformation and statistical validation. The absence of numerical data suggests it is a **conceptual blueprint** rather than an empirical analysis.
</details>
Figure 1: Illustration of the FairICP framework. $A$ , $X$ , and $Y$ denote the sensitive attributes, features, and labels. We generate $\tilde{A}$ as permuted copies of $A$ which satisfies $(\hat{\mathbf{Y}},{\mathbf{A}},{\mathbf{Y}})\,{\buildrel d\over{=}}\,(\hat{%
\mathbf{Y}},\tilde{\mathbf{A}},{\mathbf{Y}})$ when the equalized odds holds, using a novel inverse conditional permutation (ICP) strategy, and construct a fairness-aware learning method through regularizing the distribution of $(\hat{Y},A,Y)$ toward the distribution of $(\hat{Y},\tilde{A},Y)$ .
Background and Related Work
Fairness in machine learning has emerged as a critical area of research, with various notions and approaches developed to address potential biases in algorithmic decision making. These fairness concepts can be broadly categorized into three main types: (1) group fairness (Hardt et al., 2016), which aims to ensure equal treatment across different demographic groups; (2) individual fairness (Dwork et 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, existing 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).
Our work focuses on in-processing learning for the equalized odds (Hardt et al., 2016), a 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 unconditional independence. The conditional nature of equalized odds makes it particularly challenging when dealing with complex sensitive attributes that may be multidimensional 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 equalized odds primarily considers one-dimensional sensitive attributes, with no 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-Gebelein-Rényi Maximum Correlation Coefficient to accommodate for a continuous sensitive attribute in both regression and classification settings. Another line of in-processing algorithms for equalized odds uses adversarial 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-processing framework specifically designed for equalized odds with complex sensitive attributes.
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 applications. While numerous methods have been proposed to test for parametric or non-parametric conditional independence, measuring the degree of conditional dependence for multi-dimensional variables remains challenging. We note recent progress in two directions. One direction is the resampling-based approaches (Sen et al., 2017; Berrett et al., 2020; Tansey et al., 2022). These methods allow flexible and adaptive construction of test statistics for comparisons. However, their accuracy heavily depends on generating accurate samples from the conditional distribution of $A|Y$ , which can be difficult to verify in real-world applications with unknown $A|Y$ . Efforts have also been made towards direct conditional dependence measures for multi-dimensional variables. Notably, Azadkia & Chatterjee (2021) proposed CODEC, a non-parametric, tuning-free conditional dependence measure. This was later generalized into the Kernel Partial Correlation (KPC) (Huang et al., 2022):
**Definition 1.1**
*Kernel Partial Correlation (KPC) coefficient $\rho^{2}\equiv\rho^{2}(U,V\mid W)$ is defined as:
$$
\rho^{2}(U,V\mid W):=\frac{\mathbb{E}\left[\operatorname{MMD}^{2}\left(P_{U%
\mid WV},P_{U\mid W}\right)\right]}{\mathbb{E}\left[\operatorname{MMD}^{2}%
\left(\delta_{U},P_{U\mid W}\right)\right]},
$$
where $(U,V,W)\sim P$ and $P$ is supported on a subset of some topological space $\mathcal{U}×\mathcal{V}×\mathcal{W}$ , MMD is the maximum mean discrepancy - a distance metric between two probability distributions depending on the characteristic kernel $k(·,·)$ and $\delta_{U}$ denotes the Dirac measure at $U$ .*
Under mild regularity conditions (see details in Huang et al. (2022)), $\rho^{2}$ satisfies several good properties for any joint distribution of $(U,V,W)$ in Definition 1.1: (1) $\rho^{2}∈[0,1]$ ; (2) $\rho^{2}=0$ if and only if $U\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern 2.0mu{%
\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{$\textstyle\perp$\hss}\mkern 2.0%
mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptstyle\perp$\hss}\mkern 2.%
0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptscriptstyle\perp$\hss}%
\mkern 2.0mu{\scriptscriptstyle\perp}}}V\mid W$ ; (3) $\rho^{2}=1$ if and only if $U$ is a measurable function of $V$ given $W$ . A consistent estimator $\hat{\rho^{2}}$ calculated by geometric graph-based methods (Section 3 in Huang et al. (2022)) is also provided in R Package KPC (Huang, 2022). KPC allows us to rigorously quantify the violation of equalized odds for multi-dimensional $A$ via $\hat{\rho^{2}}(\hat{Y},A\mid Y)$ , where $A$ can take arbitrary forms and response $Y$ can be continuous (regression) or categorical (classification). Additionally, ${\rho^{2}}(\hat{Y},A\mid Y)$ has been properly 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 $U$ and $V$ given $W$ (see Appendix A for a simple example). In this paper, we consider KPC as our main evaluation metric 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.
2 Method
We begin by reviewing how to conduct fairness-aware learning via sensitive attribute resampling to encourage equalized odds and its challenges with complex attributes. We then introduce our proposed method, FairICP, 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.
Let $\left(X_{i},A_{i},Y_{i}\right)$ for $i=1,...,n_{\mathrm{tr}}$ be i.i.d. generated triples of (features, sensitive attributes, response). Let $f_{\theta_{f}}(.)$ be a prediction function with model parameter $\theta_{f}$ . While $f_{\theta_{f}}(.)$ can be any differentiable prediction function, we consider it as a neural network throughout this work. Let $\hat{Y}=f_{\theta_{f}}(X)$ be the prediction for $Y$ given $X$ . For a regression problem, $\hat{Y}$ is the predicted value of the continuous response $Y$ ; for a classification problem, the last layer of $f_{\theta_{f}}(.)$ is a softmax layer and $\hat{Y}$ is the predicted probability vector for being in each class. We also denote ${\mathbf{X}}=\left(X_{1},...,X_{n_{\mathrm{tr}}}\right),{\mathbf{A}}=\left(%
A_{1},...,A_{n_{\mathrm{tr}}}\right)$ , ${\mathbf{Y}}=\left(Y_{1},...,Y_{n_{\mathrm{tr}}}\right)$ and $\hat{\mathbf{Y}}=(\hat{Y}_{1},...,\hat{Y}_{n_{\mathrm{tr}}})$ .
2.1 Baseline: Fairness-Aware Learning via Sensitive Attribute Resampling
We begin by presenting the baseline model developed by Romano 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.
The key idea of FDL is to construct a synthetic version of the original sensitive attribute as $\tilde{{\mathbf{A}}}$ based on conditional randomization (Candès et al., 2018), drawing independent samples $\tilde{A}_{i}$ from $Q(·|Y_{i})$ for $i=1,...,n_{tr}$ where the $Q(·|y)$ is the conditional distribution of $A$ given $Y=y$ . Since the re-sampled $\tilde{{\mathbf{A}}}$ is generated independently without looking at the features ${\mathbf{X}}$ , and consequently, the predicted responses $\hat{{\mathbf{Y}}}$ , $\tilde{{\mathbf{A}}}$ satisfies equalized odds: $\hat{Y}\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern 2.0%
mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{$\textstyle\perp$\hss}\mkern 2%
.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptstyle\perp$\hss}\mkern 2%
.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptscriptstyle\perp$\hss%
}\mkern 2.0mu{\scriptscriptstyle\perp}}}\tilde{A}\mid Y$ . Given the resampled sensitive attribute, FDL uses the fact that $A$ satisfies equalized odds if and only if $(\hat{Y},A,Y)\overset{d}{=}(\hat{Y},\tilde{A},Y)$ , and promotes equalized odds by enforcing the similarity between joint distributions of $(\hat{Y},A,Y)$ and $(\hat{Y},\tilde{A},Y)$ via an adversarial learning component (Goodfellow et al., 2014), where the model iteratively learn how to separate these two distributions and optimize a fairness-regularized prediction loss. More specifically, define the negative log-likelihood loss, the discriminator loss, and the value function respectively:
$$
\displaystyle\mathcal{L}_{f}\left(\theta_{f}\right)=\mathbb{E}_{XY}\left[-\log
p%
_{\theta_{f}}(Y\mid X)\right], \displaystyle\mathcal{L}_{d}\left(\theta_{f},\theta_{d}\right)=\mathbb{E}_{%
\hat{Y}AY}[-\log{D}_{\theta_{d}}(\hat{Y},A,Y)] \displaystyle\quad\quad\quad+\mathbb{E}_{\hat{Y}\tilde{A}Y}[-\log(1-{D}_{%
\theta_{d}}(\hat{Y},\tilde{A},Y))], \displaystyle V_{\mu}(\theta_{f},\theta_{d})=(1-\mu)\mathcal{L}_{f}(\theta_{f}%
)-\mu\mathcal{L}_{d}(\theta_{f},\theta_{d}), \tag{2}
$$
where $D_{\theta_{d}}(.)$ is the classifier parameterized by $\theta_{d}$ which separates the distribution of $(\hat{Y},A,Y)$ and the distribution of $(\hat{{\mathbf{Y}}},\tilde{\mathbf{A}},{\mathbf{Y}})$ , and $\mu∈[0,1]$ is a tuning parameter that controls the prediction-fairness trade-off. Then, FDL learns $\theta_{f},\theta_{d}$ by finding the minimax solution
$$
\hat{\theta}_{f},\hat{\theta}_{d}=\arg\min_{\theta_{f}}\max_{\theta_{d}}V_{\mu%
}(\theta_{f},\theta_{d}). \tag{5}
$$
Challenges with Complex Sensitive Attributes
FDL generates $\tilde{A}$ through conditional randomization and resamples it from the (estimated) conditional distribution $Q(A\mid Y)$ . However, FDL was proposed primarily for the scenario with a single continuous sensitive attribute, as the estimation of $Q(A\mid Y)$ is challenging when the dimension 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 estimation unreliable. Also, when $A$ includes mixed-type variables, modeling the joint conditional distribution $q(A|Y)$ becomes complex. Therefore, an approach that allows $A$ to have flexible types and scales well with its dimensionality is crucial for promoting improved equalized odds in many social and medical applications.
2.2 FairICP: Fairness-Aware Learning via Inverse Conditional Permutation
To circumvent the challenge in learning the conditional density of $A$ given $Y$ , we propose the Inverse Conditional Permutation (ICP) sampling scheme, which leverages Conditional Permutation (CP) (Berrett et al., 2020) but pivots to estimate $Y$ given $A$ , to generate a permuted version of $\tilde{{\mathbf{A}}}$ which is guaranteed to satisfy $(\hat{\mathbf{Y}},{\mathbf{A}},{\mathbf{Y}})\,{\buildrel d\over{=}}\,(\hat{%
\mathbf{Y}},\tilde{\mathbf{A}},{\mathbf{Y}})$ when the equalized odds defined in eq. (1) holds.
Recap of CP and Why It’s Not Sufficient
FDL constructs synthetic and resampled sensitive attributes based on conditional randomization. CP offers a natural alternative approach to constructing the synthetic sensitive attribute $\tilde{{\mathbf{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 $\tilde{\mathbf{A}}$ . Let $\mathcal{S}_{n}$ denote the set of permutations on the indices $\{1,...,n\}$ . Given any vector $\mathbf{x}=\left(x_{1},...,x_{n}\right)$ and any permutation $\pi∈\mathcal{S}_{n}$ , define $\mathbf{x}_{\pi}=\left(x_{\pi(1)},...,x_{\pi(n)}\right)$ as the permuted version of $\mathbf{x}$ with its entries reordered according to the permutation $\pi$ . Instead of drawing a permutation $\Pi$ uniformly at random, CP assigns unequal sampling probability to permutations based on the conditional probability of observing $A_{\Pi}$ given $Y$ :
$$
\mathbb{P}\left\{\Pi=\pi\mid{\mathbf{A}},{\mathbf{Y}}\right\}=\frac{q^{n}\left%
({\mathbf{A}}_{\pi}\mid{\mathbf{Y}}\right)}{\sum_{\pi^{\prime}\in\mathcal{S}_{%
n}}q^{n}\left({\mathbf{A}}_{\pi^{\prime}}\mid{\mathbf{Y}}\right)}. \tag{6}
$$
Here, $q(·\mid y)$ is the density of the distribution $Q(·\mid y)$ (i.e., $q(·\mid y)$ is the conditional density of $A$ given $Y=y$ ). We write $q^{n}(·\mid{\mathbf{Y}}):=\prod_{i=1}^{n}q\left(·\mid Y_{i}\right)$ to denote the product density. This leads to the synthetic $\tilde{\mathbf{A}}={\mathbf{A}}_{\Pi}$ , which, intuitively, could achieve a similar purpose as the ones from conditional randomization for encouraging equalized odds when utilized in constructing the loss eq. (5).
Compared to the conditional randomization strategy in FDL, one strength of CP is that its generated synthetic sensitive attribute $\tilde{\mathbf{A}}$ is guaranteed to retain the marginal distribution of the actual sensitive attribute $A$ regardless of the estimation quality of $q(·|y)$ . However, it still relies strongly on the estimation of $q(·|y)$ for its permutation quality and, thus, does not fully alleviate the issue arising from multivariate density estimation as we mentioned earlier.
ICP Circumvents Density Estimation of $A\mid Y$
To circumvent this challenge in estimating the multi-dimensional conditional density $q(·|y)$ which can be further complicated by mixed sensitive attribute types, we propose the indirect ICP sampling strategy. ICP scales better with the dimensionality of $A$ and adapts easily to various data types.
ICP begins with the observation that the distribution of $({\mathbf{A}}_{\Pi},{\mathbf{Y}})$ is identical as the distribution of $({\mathbf{A}},{\mathbf{Y}}_{{\Pi}^{-1}})$ . Hence, instead of determining $\Pi$ based on the conditional law of $A$ given $Y$ , we first consider the conditional permutation of $Y$ given $A$ , which can be estimated conveniently using standard or generalized regression techniques, as $Y$ is typically one-dimensional. We then generate $\Pi$ by applying an inverse operator to the distribution of these permutations. Specifically, we generate $\tilde{\mathbf{A}}={\mathbf{A}}_{\Pi}$ according to the following probabilities:
$$
\mathbb{P}\left\{\Pi=\pi\mid{\mathbf{A}},{\mathbf{Y}}\right\}=\frac{q^{n}\left%
({\mathbf{Y}}_{{\pi}^{-1}}\mid{\mathbf{A}}\right)}{\sum_{\pi^{\prime}\in%
\mathcal{S}_{n}}q^{n}\left({\mathbf{Y}}_{{\pi^{\prime}}^{-1}}\mid{\mathbf{A}}%
\right)}. \tag{7}
$$
We adapt the parallelized pairwise sampler developed for the vanilla CP to efficiently generate ICP samples (see Appendix C), and show that ICP generate valid conditional permutations of ${\mathbf{A}}$ given any set of its observed value set ${\mathbf{a}}$ .
**Theorem 2.1**
*Let $({\mathbf{X}},{\mathbf{A}},{\mathbf{Y}})$ be i.i.d observations of sample size $n$ , $S({\mathbf{A}})$ denote the unordered set of rows in ${\mathbf{A}}$ , and $p$ be the dimension of $A$ . Let $\tilde{\mathbf{A}}$ be sampled via ICP based on eq. (7). Then, (1) $\tilde{\mathbf{A}}$ is a valid conditional permutation of ${\mathbf{A}}$ : for any $\pi$ ,
$$
\mathbb{P}\left\{{\mathbf{A}}={\mathbf{a}}_{\pi}\right|S({\mathbf{A}})=S,{%
\mathbf{Y}}\}=\mathbb{P}\left\{\tilde{\mathbf{A}}={\mathbf{a}}_{\pi}\right|S({%
\mathbf{A}})=S,{\mathbf{Y}}\}.
$$ (2) If $\hat{Y}\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern 2.0%
mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{$\textstyle\perp$\hss}\mkern 2%
.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptstyle\perp$\hss}\mkern 2%
.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptscriptstyle\perp$\hss%
}\mkern 2.0mu{\scriptscriptstyle\perp}}}A\mid Y$ , we have $(\hat{\mathbf{Y}},{\mathbf{A}},{\mathbf{Y}})\,{\buildrel d\over{=}}\,(\hat{%
\mathbf{Y}},\tilde{\mathbf{A}},{\mathbf{Y}})$ .*
Theorem 2.1 is derived from Bayes’ Rule, with its proof provided in Appendix B
Input: Data $({\mathbf{X}},{\mathbf{A}},{\mathbf{Y}})=\{(X_{i},A_{i},Y_{i})\}_{i∈\mathcal%
{I}_{\mathrm{tr}}}$
Parameters: penalty weight $\mu$ , step size $\alpha$ , number of gradient steps $N_{g}$ , and iterations $T$ .
Output: predictive model $\hat{f}_{\hat{\theta}_{f}}(·)$ and discriminator $\hat{D}_{\hat{\theta}_{d}}(·)$ .
1: for $t=1,...,T$ do
2: Generate permuted copy $\tilde{\mathbf{A}}$ by eq. (7) using ICP as implemented in Appendix C.
3: Update the discriminator parameters $\theta_{d}$ by repeating the following for $N_{g}$ gradient steps:
$$
\theta_{d}\leftarrow\theta_{d}-\alpha\nabla_{\theta_{d}}\hat{\mathcal{L}}_{d}(%
\theta_{f},\theta_{d}).
$$
4: Update the predictive model parameters $\theta_{f}$ by repeating the following for $N_{g}$ gradient steps:
$$
\theta_{f}\leftarrow\theta_{f}-\alpha\nabla_{\theta_{f}}\left[(1-\mu)\hat{%
\mathcal{L}}_{f}(\theta_{f})-\mu\hat{\mathcal{L}}_{d}(\theta_{f},\theta_{d})%
\right].
$$
5: end for
Output: Predictive model $\hat{f}_{\hat{\theta}_{f}}(·)$ .
Algorithm 1 FairICP: Fairness-aware learning via inverse conditional permutation
FairICP Encourages Equalized Odds with Complex Sensitive 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 $\tilde{A}$ using ICP, i.e., eq. (7) which requires estimated $q(y|A)$ , as opposed to the one from direct resampling using estimated $q(A|y)$ . Let $\hat{\mathcal{L}}_{f}(\theta_{f})$ and $\hat{\mathcal{L}}_{d}(\theta_{f},\theta_{d})$ be the empirical realizations of the losses $\mathcal{L}_{f}(\theta_{f})$ and $\mathcal{L}_{d}(\theta_{f},\theta_{d})$ defined in (2) and (3) respectively. Algorithm 1 presents the details.
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/maximizer to $L_{f}(\theta_{f})$ / $L_{d}(\theta_{f},\theta_{d})$ may not be shared as a result. In this situation, setting $\mu$ to a large value will preferably enforce $f$ to satisfy equalized odds while setting $\mu$ 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.
ICP Enables Equalized Odds Testing with Complex Sensitive Attributes
As a 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 $\tilde{A}$ from the conditional distribution of $A|Y$ , we can utilize the conditionally permuted copies to test if equalized odds are violated after model training. Algorithm 2 provides the detailed implementation of this hypothesis testing procedure: we repeatedly generate synthetic copies $\tilde{\mathbf{A}}$ via ICP and compare $T(\hat{\mathbf{Y}},{\mathbf{A}},{\mathbf{Y}})$ to those using the synthetic sensitive attributes $T(\hat{\mathbf{Y}},\tilde{{\mathbf{A}}},{\mathbf{Y}})$ for some suitable test statistic $T$ . According to Theorem 2.1, $(\hat{\mathbf{Y}},\tilde{\mathbf{A}},{\mathbf{Y}})$ will have the same distribution as $(\hat{\mathbf{Y}},{\mathbf{A}},{\mathbf{Y}})$ if the prediction $\hat{Y}$ satisfies equalized odds, consequently, the constructed $p$ -values from comparing $T(\hat{\mathbf{Y}},{\mathbf{A}},{\mathbf{Y}})$ and $T(\hat{\mathbf{Y}},\tilde{{\mathbf{A}}},{\mathbf{Y}})$ are valid for controlling type-I errors.
**Proposition 2.2**
*Suppose the test observations $({\mathbf{X}}^{te},{\mathbf{A}}^{te},{\mathbf{Y}}^{te})=\{(X_{i},Y_{i},A_{i})$ for $1≤ i≤ n_{\mathrm{te}}\}$ are i.i.d. and $\hat{\mathbf{Y}}^{te}=\{\hat{f}(X_{i})$ for $1≤ i≤ n_{\mathrm{te}}\}$ for a learned model $\hat{f}$ independent of the test data. If $H_{0}:\hat{\mathbf{Y}}^{te}\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle%
\perp$\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{$%
\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{$%
\scriptstyle\perp$\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0%
pt{$\scriptscriptstyle\perp$\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}{%
\mathbf{A}}^{te}\mid{\mathbf{Y}}^{te}$ holds, then the output p-value $p_{v}$ of Algorithm 2 is valid, satisfying $\mathbb{P}\{p_{v}≤\alpha\}≤\alpha$ for any desired Type $I$ error rate $\alpha∈[0,1]$ .*
Input: Data $({\mathbf{X}}^{te},{\mathbf{A}}^{te},{\mathbf{Y}}^{te})=\{(\hat{Y}_{i},A_{i},Y%
_{i})\}$ , $1≤ i≤ n_{\mathrm{test}}$
Parameter: the number of synthetic copies $K$ .
1: Compute the test statistic $T$ on the test set: $t^{*}=T(\hat{\mathbf{Y}}^{te},{\mathbf{A}}^{te},{\mathbf{Y}}^{te})$ .
2: for $k=1,...,K$ do
3: Generate permuted copy $\tilde{\mathbf{A}}_{k}$ of ${\mathbf{A}}^{te}$ using ICP.
4: Compute the test statistic $T$ using fake copy on the test set: $t^{(k)}=T(\hat{\mathbf{Y}}^{te},\tilde{\mathbf{A}}_{k},{\mathbf{Y}}^{te})$ .
5: end for
6: Compute the $p$ -value:
$$
p_{v}=\frac{1}{K+1}\left(1+\sum_{k=1}^{K}\mathbb{I}\left[t^{*}\geq{t}^{(k)}%
\right]\right).
$$
Output: A $p$ -value $p_{v}$ for the hypothesis that equalized odds (1) holds.
Algorithm 2 Hypothesis Test for Equalized Odds with ICP
2.3 Density Estimation
The estimation of conditional densities is a crucial part of both our method and previous work (Berrett et al., 2020; Romano et al., 2020; Mary et al., 2019; Louppe et al., 2017). However, unlike the previous work which requires the estimation of $A\mid Y$ , our proposal looks into the easier inverse relationship of $Y\mid A$ . To provide more theoretical insights into how the quality of density estimation affects ICP and CP differently, we have additional analysis in Appendix D.
In practice, ICP can easily leverage the state-of-the-art density estimator and is less disturbed by the increased complexity 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 continuous and $A_{1},...,A_{k}$ can take arbitrary data types (discrete or continuous) In Papamakarios et al. (2017), to estimate $p(U=u\mid 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$ . In a classification scenario when $Y∈\{0,1,...,L\}$ , one can always fit a classifier to model $Y|A$ . To this end, FairICP is more feasible to handle complex sensitive attributes and is suitable for both regression and classification tasks.
3 Experiments
In this section, we conduct numerical experiments to examine the effectiveness of the proposed method on both synthetic datasets and real-world datasets. All the implementation details are included in Appendix E.
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 permutations to achieve a more favorable accuracy–fairness trade-off for complex sensitive attributes. For the second task, we run a series of ablation studies, replacing ICP with alternative strategies for generating the “fake copies” $\tilde{A}$ . Specifically, we compare FairICP to FairCP—which is an intermediate new procedure that generates $\tilde{A}$ by CP—and FDL (Romano et al., 2020), the previously proposed equalized-odds learning model that uses conditional randomization to generate $\tilde{A}$ . All methods use the same model architectures and training schemes for consistency.
3.1.1 The Quality of Conditional Permutations
First, we investigate whether ICP can generate better conditional 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 a restricted subset of permutations from swapping operation.
Simulation Setup. We generate data as the following: 1) Let $A=(U_{1},...,U_{K_{0}},U_{K_{0}+1},...,U_{K_{0}+K})\Theta^{1/2}$ , where $U_{j}$ are independently generated from a mixed Gamma distribution $\frac{1}{2}\Gamma(1,1)+\frac{1}{2}\Gamma(1,10)$ , and $\Theta$ is a randomly generated covariance matrix with $\Theta^{\frac{1}{2}}$ eigenvalues equal-spaced in $[1,5]$ ; 2) Generate $Y\sim\mathcal{N}\left(\sqrt{\omega}\sum_{j=1}^{K_{0}}A_{j},\ \sigma^{2}+(1-%
\omega)*K_{0}\right)$ . Here, $Y$ is influenced only by the first $K_{0}$ components of $A$ , and is independent of the remaining $K$ components. The parameter $\omega∈[0,1]$ controls the dependence on $A$ .
We set $K_{0}∈\{1,5,10\}$ , $K∈\{0,5,10,20,50,100\},\omega=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, we consider density estimation $\hat{q}_{Y|A}$ based on regularized linear fit when comparing CP and ICP, where we assume $q(y|A)$ or $q(A|y)$ to be Gaussian. We estimate the conditional mean for ICP using LASSO regression (or OLS when $K_{0}=1$ and $K=0$ ) with conditional variance based on empirical residuals, and we estimate $q_{A|Y}$ for CP via graphical LASSO (or using empirical covariance when $K_{0}=1$ 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 a 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.
Evaluation on Permutations Quality. Due to the large permutation space, the calculation of the actual total variation distance is infeasible. To circumvent this challenge, we consider a restricted TV distance where we restrict the permutation space to swapping actions. Concretely, we consider the TV distance restricted to permutations $\pi$ that swap $i$ and $j$ for $i≠ j,i,j=1,...,n$ and the original order, and compare ICP/CP to the oracle conditional permutations on such $\frac{n(n-1)}{2}$ permutations only.
Results
Figure 2 shows restricted TV distance between permutations generated by CP/ICP and the oracle conditional permutations using the true densities, averaged over 20 independent trials. We observe that the restricted TV distances 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 $K_{0}$ and dimensions of the irrelevant sensitive attributes $K$ . These results confirm our expectation that ICP can provide higher-quality sampling by more effectively capturing potentially intrinsic structures between $Y$ and $A$ , For instance, when $K_{0}=1$ , ICP achieves substantially better estimation quality than CP for moderately large $K$ . Additional discussions and mathematical intuitions on why this occurs can be found in Appendix D.1.
<details>
<summary>2404.05678v4/x2.png Details</summary>

### Visual Description
# Technical Document Analysis of Box Plot Image
## 1. Labels and Axis Titles
- **X-axis**: Labeled "K" with discrete markers at values: 0, 5, 10, 20, 50, 100.
- **Y-axis**: Labeled "Restricted TV" with a range from -6 to -4.
- **Legend**: Located on the right side of the plot, with two entries:
- **CP**: Red color (represented by red squares and dots).
- **ICP**: Teal color (represented by teal squares and dots).
## 2. Chart Structure
- **Type**: Box plot comparing two methods (CP and ICP) across three scenarios (K0=1, K0=5, K0=10).
- **Subcategories**:
- **K0=1**: Top-left section of the plot.
- **K0=5**: Middle section of the plot.
- **K0=10**: Rightmost section of the plot.
- **X-axis Categories**: For each K0 scenario, K values are plotted at 0, 5, 10, 20, 50, 100.
## 3. Textual Elements
- **K0 Labels**:
- "K0 = 1" (top-left),
- "K0 = 5" (center-top),
- "K0 = 10" (top-right).
- **Legend Text**:
- "method" (title),
- "CP" (red),
- "ICP" (teal).
## 4. Data Trends
### K0=1
- **CP (Red)**:
- Median Restricted TV decreases slightly from ~-5.5 (K=0) to ~-5.0 (K=100).
- Outliers are sparse, with most data clustered between -5.5 and -4.5.
- **ICP (Teal)**:
- Median Restricted TV decreases from ~-5.2 (K=0) to ~-4.8 (K=100).
- Outliers are more frequent, especially at K=0 and K=100.
### K0=5
- **CP (Red)**:
- Median Restricted TV decreases from ~-5.3 (K=0) to ~-4.7 (K=100).
- Box plots show tighter interquartile ranges (IQR) compared to K0=1.
- **ICP (Teal)**:
- Median Restricted TV decreases from ~-5.1 (K=0) to ~-4.9 (K=100).
- Outliers are moderate, with increased spread at K=50 and K=100.
### K0=10
- **CP (Red)**:
- Median Restricted TV decreases from ~-5.4 (K=0) to ~-4.6 (K=100).
- Box plots exhibit consistent IQRs across K values.
- **ICP (Teal)**:
- Median Restricted TV decreases from ~-5.2 (K=0) to ~-4.8 (K=100).
- Outliers are concentrated at K=0 and K=100.
## 5. Spatial Grounding
- **Legend Placement**: Right-aligned, outside the main plot area. Coordinates approximate to [x > 100, y ≈ midpoint of y-axis].
- **K0 Sections**: Horizontally segmented into three equal-width regions (K0=1, K0=5, K0=10).
## 6. Trend Verification
- **CP (Red)**: Across all K0 values, CP shows a general downward trend in Restricted TV as K increases. The rate of decrease slows for higher K0 values.
- **ICP (Teal)**: ICP also shows a downward trend, but with greater variability (more outliers) compared to CP. The trend is more pronounced for lower K0 values.
## 7. Component Isolation
- **Header**: Contains K0 labels (K0=1, K0=5, K0=10) at the top of each section.
- **Main Chart**: Box plots for CP and ICP across K values, grouped by K0.
- **Footer**: No explicit footer; y-axis label and legend occupy the lower and right edges, respectively.
## 8. Data Extraction
- **Key Observations**:
- For all K0 values, CP consistently achieves lower Restricted TV than ICP.
- As K increases, both methods show reduced Restricted TV, but the effect is more significant for lower K0 values.
- ICP exhibits higher variability (wider IQRs and more outliers) compared to CP.
## 9. Final Notes
- The image contains no textual data tables or non-English content.
- All numerical values (e.g., median, IQR) are inferred from visual inspection of the box plots and y-axis scale.
</details>
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 $K_{0}={1,5,10}$ respectively.
3.1.2 Influence of CP on Fairness-Aware Learning
Next, we compare the performance of models trained using different resampling methods. Specifically, we compare four models: (1) FairICP (Algorithm 1 with estimated density $\hat{q}(Y|A)$ ); (3) Oracle (Algorithm 1 with true density $q(Y|A)$ ); (3) FDL (Romano et al., 2020). Apart from the baseline FDL, we also consider another similar but a new model in our simulation (4) FairCP (Algorithm 1 who are almost identical to FairICP with the only difference being permutations generated by CP using estimated density $\hat{q}(A|Y)$ , aiming to investigate if the gain of ICP over CP in generating accurate permutation actually affect the downstream predictive model training. The synthetic experiments allow us to reliably evaluate the violation of the equalized odds using different methods with known ground truth.
Simulation Setup
We conduct experiments under two simulation settings where $A$ influence $Y$ through $X$ , which is the most typical mechanism in the area of fair machine learning (Kusner et al., 2017; Tang & Zhang, 2022; Ghassami et al., 2018).
1. Simulation 1: The response $Y$ depends on two set of features $X^{*}∈{\mathbb{R}}^{K}$ and $X^{\prime}∈{\mathbb{R}}^{K}$ :
| | $\displaystyle Y\sim\mathcal{N}\left(\Sigma_{k=1}^{K}X_{k}^{*}+\Sigma_{k=1}^{K}%
X_{k}^{\prime},\sigma^{2}\right),$ | |
| --- | --- | --- |
1. Simulation 2: The response $Y$ depends on two features $X^{*}∈{\mathbb{R}}$ and $X^{\prime}∈{\mathbb{R}}$ :
| | $\displaystyle Y\sim\mathcal{N}\left(X^{*}+X^{\prime},\sigma^{2}\right),$ | |
| --- | --- | --- |
In both settings, $A$ are generated as in Section 3.1.1: $A=(U_{1},...,U_{k})\Theta^{1/2}$ , where $k=1,...,K$ for Simulation 1 (where all the $A_{1:K}$ affects $Y$ ) and $k=1,...,K+1$ for Simulation 2 (where only $A_{1}$ affects $Y$ , with the rest serving as noises to increase the difficulty of density estimation). We set $K∈\{1,5,10\},\omega∈\{0.6,0.9\}$ to investigate different levels of dependence on $A$ , and the sample size for training/test data to be 500/400. For all models, we implement the predictor $f$ as linear model and discriminator $d$ 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).
Evaluation on the Accuracy-Fairness Tradeoff. For evaluating equalized odds, we use the empirical KPC $=\hat{\rho}^{2}(\hat{Y},A\mid Y)∈[0,1]$ , 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 a suitable model-comparison metric by examining trade-off curves in terms of (KPC, prediction loss) versus (fairness testing power, prediction loss). The fairness test power is defined as the ability to reject the hypothesis test outlined by Algorithm 2 —which uses the true conditional density of $Y|A$ and the KPC statistic $T$ with targeted type I error at $\alpha=0.05$ . The greater $\hat{\rho}^{2}$ or rejection power indicates stronger conditional dependence between $A$ and $\hat{Y}$ given $Y$ . The power metric provides a fair comparison of equalized-odds violations when the true density is known, however, the true density is unavailable 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 a viable metric for evaluating fairness in real data settings. Note that, in Simulation 2 only $A_{1}$ influences the $Y$ , so the test will be based on $\hat{\rho}^{2}(\hat{Y},A_{1}\mid Y)$ to exclude the effects of noise (though the training is based on $A_{1:K+1}$ for all methods to evaluate the performance under noise).
Results
<details>
<summary>2404.05678v4/x3.png Details</summary>

### Visual Description
# Technical Document Extraction: Violation of Equalized Odds Analysis
## Overview
The image contains **8 line graphs** arranged in a 2x4 grid, comparing algorithmic performance metrics across different dimensionality settings. All graphs share consistent labeling conventions and color-coded data series.
---
### **Legend & Color Mapping**
- **Legend Location**: Top-left corner of all graphs
- **Color Assignments**:
- **Blue**: Oracle
- **Green**: FairICP
- **Cyan**: FairCP
- **Red**: FDL
---
### **Graph 1: Violation of Equalized Odds (KPC, dim=1)**
- **X-axis**: KPC: dim = 1 (0.000 → 0.100)
- **Y-axis**: Increased Dimensions (2.00 → 2.25)
- **Trends**:
- Red (FDL) starts highest (2.25) and declines steeply
- Blue (Oracle) and Green (FairICP) converge near 2.00
- **Key Data Points**:
- At X=0.000: FDL=2.25, Oracle=2.18, FairICP=2.18
- At X=0.100: All ≈2.00
---
### **Graph 2: Violation of Equalized Odds (Statistical Power, dim=1)**
- **X-axis**: Power: dim = 1 (0.2 → 1.0)
- **Y-axis**: Increased Dimensions (2.00 → 2.25)
- **Trends**:
- Red (FDL) dominates early (2.25 at X=0.2), then declines
- Cyan (FairCP) and Blue (Oracle) show gradual convergence
- **Key Data Points**:
- At X=0.2: FDL=2.25, FairCP=2.18
- At X=1.0: All ≈2.00
---
### **Graph 3: KPC Loss (dim=5)**
- **X-axis**: KPC: dim = 5 (0.10 → 0.30)
- **Y-axis**: Loss (15 → 50)
- **Trends**:
- Red (FDL) spikes sharply at X=0.15 (≈45)
- Blue (Oracle) and Green (FairICP) remain stable
- **Key Data Points**:
- At X=0.10: FDL=38, Oracle=22
- At X=0.30: All ≈18
---
### **Graph 4: Statistical Power Loss (dim=5)**
- **X-axis**: Power: dim = 5 (0.6 → 1.0)
- **Y-axis**: Loss (15 → 50)
- **Trends**:
- Red (FDL) declines from 40 to 20
- Cyan (FairCP) shows gradual decrease
- **Key Data Points**:
- At X=0.6: FDL=40, FairCP=45
- At X=1.0: All ≈18
---
### **Graph 5: KPC Loss (dim=10)**
- **X-axis**: KPC: dim = 10 (0.10 → 0.25)
- **Y-axis**: Loss (50 → 175)
- **Trends**:
- Red (FDL) spikes dramatically at X=0.20 (≈150)
- Blue (Oracle) and Green (FairICP) remain below 75
- **Key Data Points**:
- At X=0.10: FDL=175, Oracle=50
- At X=0.25: All ≈50
---
### **Graph 6: Statistical Power Loss (dim=10)**
- **X-axis**: Power: dim = 10 (0.85 → 1.00)
- **Y-axis**: Loss (50 → 175)
- **Trends**:
- Red (FDL) declines from 175 to 50
- Cyan (FairCP) shows moderate decrease
- **Key Data Points**:
- At X=0.85: FDL=175, FairCP=125
- At X=1.0: All ≈50
---
### **Cross-Graph Observations**
1. **Dimensionality Impact**:
- Higher dimensions (dim=10) show more extreme loss spikes (FDL)
- KPC-based metrics exhibit sharper declines than power-based metrics
2. **Algorithm Performance**:
- FDL consistently shows highest violation/loss in early ranges
- Oracle and FairICP/FairCP demonstrate better stability
3. **Convergence**:
- All algorithms converge toward baseline loss (≈2.00/50) at maximum X-values
---
### **Critical Notes**
- All y-axis scales are **linear** (no log transformations)
- X-axis ranges vary significantly by dimension (0.000–0.100 for dim=1 vs 0.85–1.00 for dim=10)
- No textual annotations present beyond axis labels and legends
</details>
<details>
<summary>2404.05678v4/x4.png Details</summary>

### Visual Description
# Technical Document Extraction: Violation of Equalized Odds Analysis
## Overview
The image contains **8 comparative line graphs** organized in a 2x4 grid, analyzing the performance of fairness algorithms across different dimensions. All graphs share consistent labeling conventions and color-coded data series.
---
## Graph Structure
### Axes
- **Y-axis**: "Increased Dimensions" (ranging from 0 to 15 in some subplots)
- **X-axis**:
- Left column: "KPC" (values 0.0–0.3)
- Right column: "Power" (values 0.2–1.0)
### Legend
Positioned in the **top-left corner** of each graph. Color-mapped methods:
- **Blue**: Oracle
- **Green**: FairICP
- **Cyan**: FairCP
- **Red**: FDL
---
## Key Trends
### Left Column: "Violation of Equalized Odds: test on KPC"
1. **KPC: dim = 1**
- All methods show **steep initial decline** as KPC increases
- Oracle (blue) consistently lowest loss (~1.0–1.5 range)
- FDL (red) highest loss (~2.5–3.0 range)
- FairICP (green) and FairCP (cyan) show similar trajectories
2. **KPC: dim = 5**
- Similar trend but with **higher baseline loss** (~2.5–8 range)
- Oracle maintains lowest loss (~2.0–2.5)
- FDL exhibits **sharp spike** at KPC=0.1 (~12.5 loss)
3. **KPC: dim = 10**
- Oracle loss remains stable (~2.0–2.5)
- FDL shows **extreme outlier** at KPC=0.1 (~15 loss)
- Fair methods converge toward Oracle performance
### Right Column: "Violation of Equalized Odds: test on statistical power"
1. **Power: dim = 1**
- All methods decline gradually as Power increases
- Oracle (blue) lowest loss (~1.0–1.5)
- FDL (red) highest loss (~2.5–3.0)
2. **Power: dim = 5**
- Oracle loss stable (~2.0–2.5)
- FDL exhibits **sharp spike** at Power=0.5 (~12.5 loss)
3. **Power: dim = 10**
- Oracle loss minimal (~2.0–2.5)
- FDL shows **extreme outlier** at Power=0.5 (~15 loss)
- Fair methods demonstrate improved performance at higher dimensions
---
## Critical Observations
1. **Dimension Sensitivity**:
- Higher dimensions (dim=10) show **more pronounced performance gaps** between methods
- FDL consistently underperforms across all dimensions
2. **Algorithm Robustness**:
- Oracle maintains **lowest violation rates** regardless of dimension
- FairICP and FairCP show **diminishing returns** with increased dimensions
3. **Statistical Power Impact**:
- Power tests reveal **consistent trends** across dimensions
- FDL's performance degradation becomes **more extreme** at higher dimensions
---
## Data Point Verification
All legend colors match data series:
- Blue (Oracle) points consistently lowest on y-axis
- Red (FDL) points highest, with **notable spikes** at x=0.1 (KPC) and x=0.5 (Power)
- Green (FairICP) and cyan (FairCP) show intermediate values with similar trajectories
---
## Conclusion
The graphs demonstrate that:
1. Oracle algorithm maintains optimal performance across all tested conditions
2. FDL algorithm exhibits **catastrophic failure** at low KPC/Power values in higher dimensions
3. FairICP and FairCP provide **moderate improvements** over baseline methods
All textual elements have been extracted with spatial grounding and trend verification. No non-English text detected.
</details>
Figure 3: Prediction loss (MSE) and violation of equalized odds in simulation over 100 independent runs under Simulation 1 /Simulation 2 and $w=0.9$ . For each setting, conditional dependence measure KPC and statistical power ${\mathbb{P}}\{p\text{-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 equalized odds and the Y-axis is the prediction loss. The Pareto front for each algorithm is obtained by varying the fairness trade-off parameter $\mu$ .
Figure 3 shows the trade-off curves between prediction loss and equalized odds violation measured by KPC and the associated power using Algorithm 2 ( $T=KPC$ ) under the high-dependence scenariors $w=0.9$ in Simulation 1 and Simulation 2 respectively, with $K∈\{1,5,10\}$ . We train the predictor $f$ as linear models and the discriminator $d$ as neural networks with different penalty parameters $\mu∈[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 low-dependence scenarios are provided in Appendix E.1, which convey the same stories.
Figure 3 A shows the results from Simulation 1. All approaches reduce to training a plain regression model for prediction when $\mu=0$ , resulting in low prediction loss but a severe violation of fairness (evidenced by large KPC and statistical power); as $\mu$ increases, models pay more attention 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 3 B shows the results from Simulation 2 and delivers a similar message as Figure 3 A.
**Remark 3.1**
*The power measure (Algorithm 2) depends on how the permutation/sampling is conducted in practice. In simulations, we can trust it by utilizing the true conditional density, but its reliability hinges on the accuracy of density estimation. In contrast, the direct KPC measure is independent of density estimation.*
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 a training set (60%) and a test set (40%) 100 times, with the average results on the test sets reported .
| FairICP HGR FDL | 0.386(0.045) 0.386(0.044) 0.402(0.046) | 0.016(0.10) 0.026(0.16) 0.023(0.17) | 0.418(0.047) 0.596(0.050) 0.621(0.48) | 0.054(0.37) 0.068(0.48) 0.058(0.37) | 0.215(0.003) 0.220(0.004) / | 0.025(0.80) 0.021(0.82) / | 0.159(0.003) 0.165(0.004) 0.161(0.005) | 0.010(0.13) 0.006(0.10) 0.011(0.26) | 0.212 0.198 0.251 | 0.402(0.02) 0.443(0.04) 0.417(0.03) | 0.008(0.04) 0.008(0.06) 0.008(0.11) | 0.471 0.459 0.421 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| GerryFair | / | / | / | / | 0.262(0.004) | 0.050(1.00) | 0.187(0.004) | 0.031(0.78) | 0.298 | 0.438(0.07) | 0.02(0.14) | 0.368 |
| Reduction | / | / | / | / | / | / | 0.161(0.004) | 0.005(0.15) | 0.212 | 0.400(0.02) | 0.002(0.05) | 0.460 |
Table 1: Comparisons of methods encouraging equalized odds across five real data tasks. FairICP (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 ${\mathbb{P}}{p\text{-value}<0.05}$ in parentheses). For the Adult and COMPAS datasets, which use categorical $A$ , the DEO equalized odds violation metric is also included. ”Fairness trade-off parameters in equalized-odds models are selected to achieve similar violation levels, with the full prediction loss-KPC trade-off curves shown in Figure 4.
<details>
<summary>2404.05678v4/x5.png Details</summary>

### Visual Description
# Technical Document Extraction: Chart Analysis
## Chart 1: Crimes 1dim & 3dim
- **Title**: Crimes 1dim & 3dim
- **X-axis**: KPC (Kernel Principal Components)
- **Y-axis**: Loss
- **Legend**:
- **FairICP**:
- 1dim: Blue circles (●)
- 3dim: Blue circles (●)
- **FDL**:
- 1dim: Red squares (■)
- 3dim: Red squares (■)
- **HGR**:
- 1dim: Green dashed line (--), Green pluses (+)
- 3dim: Green dashed line (--), Green pluses (+)
- **Trends**:
- **FairICP 1dim**: Starts at ~0.42 (KPC=0.0), decreases to ~0.35 (KPC=0.2).
- **FDL 1dim**: Sharp decline from ~0.62 (KPC=0.0) to ~0.35 (KPC=0.2).
- **HGR 1dim**: Gradual decline from ~0.58 (KPC=0.0) to ~0.35 (KPC=0.2).
- **FairICP 3dim**: Similar to 1dim but slightly higher loss values.
- **FDL 3dim**: Slightly higher loss than 1dim but similar trend.
- **HGR 3dim**: Slightly higher loss than 1dim but similar trend.
## Chart 2: ACS Income
- **Title**: ACS Income
- **X-axis**: KPC
- **Y-axis**: Loss
- **Legend**:
- **FairICP**: Blue circles (●)
- **HGR**: Green dashed line (--), Green pluses (+)
- **GerryFair**: Purple triangles (▲)
- **Trends**:
- **FairICP**: Gradual decline from ~0.22 (KPC=0.02) to ~0.21 (KPC=0.06).
- **HGR**: Slight decline from ~0.22 (KPC=0.02) to ~0.21 (KPC=0.06).
- **GerryFair**: Sharp drop from ~0.26 (KPC=0.02) to ~0.21 (KPC=0.06).
## Chart 3: Adult
- **Title**: Adult
- **X-axis**: KPC
- **Y-axis**: Loss
- **Legend**:
- **FairICP**: Blue circles (●)
- **Reduction**: Orange stars (★)
- **HGR**: Green dashed line (--), Green pluses (+)
- **FDL**: Red squares (■)
- **GerryFair**: Purple triangles (▲)
- **Trends**:
- **FairICP**: Gradual decline from ~0.16 (KPC=0.01) to ~0.15 (KPC=0.04).
- **Reduction**: Slight dip from ~0.16 (KPC=0.01) to ~0.15 (KPC=0.04).
- **HGR**: Gradual decline from ~0.16 (KPC=0.01) to ~0.15 (KPC=0.04).
- **FDL**: Slight decline from ~0.16 (KPC=0.01) to ~0.15 (KPC=0.04).
- **GerryFair**: Sharp drop from ~0.185 (KPC=0.01) to ~0.15 (KPC=0.04).
## Chart 4: COMPAS
- **Title**: COMPAS
- **X-axis**: KPC
- **Y-axis**: Loss
- **Legend**:
- **FairICP**: Blue circles (●)
- **Reduction**: Orange stars (★)
- **HGR**: Green dashed line (--), Green pluses (+)
- **FDL**: Red squares (■)
- **GerryFair**: Purple triangles (▲)
- **Trends**:
- **FairICP**: Gradual decline from ~0.38 (KPC=0.0) to ~0.34 (KPC=0.04).
- **Reduction**: Moderate decline from ~0.40 (KPC=0.0) to ~0.34 (KPC=0.04).
- **HGR**: Gradual decline from ~0.48 (KPC=0.0) to ~0.34 (KPC=0.04).
- **FDL**: Slight decline from ~0.42 (KPC=0.0) to ~0.34 (KPC=0.04).
- **GerryFair**: Sharp drop from ~0.44 (KPC=0.0) to ~0.34 (KPC=0.04).
## Spatial Grounding & Color Verification
- **Legend Placement**:
- All charts: Top-right corner.
- **Color Consistency**:
- Confirmed all legend colors match line/marker colors in respective charts.
## Component Isolation
- **Header**: Chart titles and axis labels.
- **Main Chart**: Data series with trends and markers.
- **Footer**: No additional text or data.
## Data Table Reconstruction (Hypothetical)
| Dataset | KPC=0.0 | KPC=0.1 | KPC=0.2 | KPC=0.3 | KPC=0.4 |
|---------------|---------|---------|---------|---------|---------|
| FairICP 1dim | 0.42 | 0.38 | 0.36 | 0.35 | 0.35 |
| FDL 1dim | 0.62 | 0.50 | 0.40 | 0.35 | 0.35 |
| HGR 1dim | 0.58 | 0.45 | 0.38 | 0.35 | 0.35 |
| FairICP 3dim | 0.43 | 0.39 | 0.36 | 0.35 | 0.35 |
| FDL 3dim | 0.55 | 0.45 | 0.38 | 0.35 | 0.35 |
| HGR 3dim | 0.57 | 0.44 | 0.37 | 0.35 | 0.35 |
## Notes
- All datasets show decreasing loss with increasing KPC.
- GerryFair consistently exhibits the steepest decline across datasets.
- HGR and FDL perform similarly in most charts, with HGR slightly higher loss.
- FairICP and GerryFair are the most effective in reducing loss.
</details>
Figure 4: Prediction loss and violation of equalized odds (measured by KPC) obtained by different methods on Crimes / ACS Income / Adult / COMPAS 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.
- Communities and Crime Data Set: This dataset contains 1994 samples and 122 features. The goal is to build a regression model predicting the continous violent crime rate. We take the continuous percentages of all three minority races (African American, Hispanic, Asian, referred to as “3 dim”) as sensitive attributes instead 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 “1 dim”) for better comparisons.
- ACSIncome Dataset: We use the ACSIncome dataset from Ding et al. (2021) with 100,000 instances (subsampled) and 10 features. The task is a binary classification to predict if income exceeds $50,000. We consider a 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 recidivism dataset contains 5278 examples and 11 features (Fabris et al., 2022). The goal is to build a binary classifier to predict recidivism with two binary sensitive attributes $A$ : race (white vs. non-white) and sex.
Results
We compare FairICP with four state-of-the-art baselines encouraging equalized odds with the predictor $f$ implemented as a neural network (the results for linear regression/classification is reported in Appendix E.6): FDL (Romano et al., 2020), HGR (Mary et al., 2019), GerryFair (Kearns et al., 2018) and Exponentiated-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 (Adult/COMPAS), and GerryFair adopts a linear threshold method to binarize sensitive attributes for classification (ACSIncome/Adult/COMPAS) and targets equal TPR or FPR as an approximation of equalized odds. HGR handles both continuous and categorical sensitive attributes for both regression and classification, but how to efficiently generalize it to handle multiple sensitive attributes has not been discussed by the authors In Mary et al. 2019, since their method can’t be directly adapted to multiple sensitive attributes, we compute the mean of the HGR coefficients of each attribute as a penalty.. We implement FDL with conditional density of $A|Y$ estimated by MAF (Papamakarios et al., 2017) in the continuous case (Crimes); for the classification with mixed-type sensitive attributes (ACSIncome), it’s not straightforward to estimate $A|Y$ , so we only consider FDL in the categorical case (Adult/COMPAS) where we calculate the frequencies of each class as an estimation of $A|Y$ . For our proposed method FairICP, we estimate $Y|A$ with MAF as the same as in FDL in the continuous case, and use a two-layer neural network classifier in the classification (ACSIncome/Adult/COMPAS).
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 tuned to 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-aware learning baselines. Although the unfair vanilla baseline achieves the highest prediction accuracy, its equalized-odds violations are several times worse than FairICP’s. Finally, FairICP’s computational cost is on par with FDL and only slightly higher than HGR (see Appendix E.5 for running time).
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 FairICP to achieve an 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 inverse 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.
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-processing adjusts prediction thresholds after training—typically by recalibrating predicted probabilities across outcome classes (Hardt et al., 2016). Recent work by Tifrea et al. (2023) extends post-processing to handle either a continuous or a 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 improving the resampling or adjustment steps when working with multi-dimensional $A$ .
Finally, we acknowledge the computational overhead associated 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 stabilization techniques or exploring alternative discrepancy measures such as kernel-based objectives.
Impact Statement
This work advances the field of fairness-aware machine learning by addressing the underexplored challenge of enforcing equalized odds for multi-dimensional sensitive attributes, such as intersections of race, gender, and socioeconomic status. While our primary contribution is methodological—introducing a theoretically grounded and adaptable framework (FairICP) for multi-attribute fairness—we recognize the broader societal implications of this research. Below, we outline key ethical considerations and potential impacts: 1) By enabling compliance with equalized odds under complex sensitive attributes, FairICP could improve the equity of algorithmic systems in domains like hiring, healthcare, and criminal justice; 2) While our method promotes fairness through adversarial training and inverse conditional permutation, it inherently requires access to sensitive attributes during training. We emphasize that practitioners must carefully evaluate whether collecting such data aligns with ethical and legal standards in their jurisdiction.
In summary, while our work primarily contributes to algorithmic fairness methodology, its societal impact hinges on responsible implementation. We urge practitioners to contextualize FairICP within broader ethical frameworks, engage impacted communities, and prioritize transparency in deployment.
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.
References
- Agarwal et al. (2018) 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.
- Azadkia & Chatterjee (2021) Azadkia, M. and Chatterjee, S. A simple measure of conditional dependence. The Annals of Statistics, 49(6):3070 – 3102, 2021. doi: 10.1214/21-AOS2073. URL https://doi.org/10.1214/21-AOS2073.
- Berrett et al. (2020) 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 Statistical Society Series B: Statistical Methodology, 82(1):175–197, 2020.
- Candès et al. (2018) Candès, E., Fan, Y., Janson, L., and Lv, J. Panning for gold: Model-X knockoffs for high-dimensional controlled variable selection. Journal of the Royal Statistical Society: Series B, 80(3):551–577, 2018.
- Castelnovo et al. (2022) Castelnovo, A., Crupi, R., Greco, G., Regoli, D., Penco, I. G., and Cosentini, A. C. A clarification of the nuances in the fairness metrics landscape. Scientific Reports, 12(1):4209, 2022.
- Cho et al. (2020) Cho, J., Hwang, G., and Suh, C. A fair classifier using kernel density estimation. Advances in neural information processing systems, 33:15088–15099, 2020.
- Creager et al. (2019) Creager, E., Madras, D., Jacobsen, J.-H., Weis, M., Swersky, K., Pitassi, T., and Zemel, R. Flexibly fair representation learning by disentanglement. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1436–1445. PMLR, 09–15 Jun 2019. URL https://proceedings.mlr.press/v97/creager19a.html.
- Ding et al. (2021) Ding, F., Hardt, M., Miller, J., and Schmidt, L. Retiring adult: New datasets for fair machine learning. Advances in neural information processing systems, 34:6478–6490, 2021.
- Dwork et al. (2012) 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, pp. 214––226, 2012. doi: 10.1145/2090236.2090255.
- Fabris et al. (2022) Fabris, A., Messina, S., Silvello, G., and Susto, G. A. Algorithmic fairness datasets: the story so far. Data Mining and Knowledge Discovery, 36(6):2074–2152, September 2022. ISSN 1573-756X. doi: 10.1007/s10618-022-00854-z. URL http://dx.doi.org/10.1007/s10618-022-00854-z.
- Feldman et al. (2015) Feldman, M., Friedler, S. A., Moeller, J., Scheidegger, C., and Venkatasubramanian, S. Certifying and removing disparate impact. In Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 259–268, 2015. doi: 10.1145/2783258.2783311.
- Ghassami et al. (2018) Ghassami, A., Khodadadian, S., and Kiyavash, N. Fairness in supervised learning: An information theoretic approach. In 2018 IEEE International Symposium on Information Theory (ISIT), pp. 176–180, 2018. doi: 10.1109/ISIT.2018.8437807.
- Ghassemi et al. (2021) Ghassemi, M., Oakden-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: https://doi.org/10.1016/S2589-7500(21)00208-9. URL https://www.sciencedirect.com/science/article/pii/S2589750021002089.
- Ghosal & van der Vaart (2017) Ghosal, S. and van der Vaart, A. W. Fundamentals of nonparametric Bayesian inference, volume 44. Cambridge University Press, 2017.
- Goodfellow et al. (2014) 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 Information Processing Systems 27, pp. 2672–2680, 2014.
- Gretton et al. (2012) 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.
- Hardt et al. (2016) Hardt, M., Price, E., and Srebro, N. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
- Huang (2022) Huang, Z. KPC: Kernel Partial Correlation Coefficient, 2022. URL https://CRAN.R-project.org/package=KPC. R package version 0.1.2.
- Huang et al. (2022) Huang, Z., Deb, N., and Sen, B. Kernel partial correlation coefficient — a measure of conditional dependence. Journal of Machine Learning Research, 23(216):1–58, 2022. URL http://jmlr.org/papers/v23/21-493.html.
- Kearns et al. (2018) Kearns, M., Neel, S., Roth, A., and Wu, Z. S. Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2564–2572. PMLR, 10–15 Jul 2018. URL https://proceedings.mlr.press/v80/kearns18a.html.
- Kusner et al. (2017) Kusner, M. J., Loftus, J., Russell, C., and Silva, R. Counterfactual fairness. In Advances in Neural Information Processing Systems 30, pp. 4066–4076. 2017.
- Louppe et al. (2017) 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.
- Madras et al. (2018) 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.
- Mary et al. (2019) Mary, J., Calauzenes, C., and El Karoui, N. Fairness-aware learning for continuous attributes and treatments. In International Conference on Machine Learning, pp. 4382–4391, 2019.
- Mehrabi et al. (2021) 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–35, 2021.
- Papamakarios et al. (2017) Papamakarios, G., Pavlakou, T., and Murray, I. Masked autoregressive flow for density estimation. Advances in neural information processing systems, 30, 2017.
- Romano et al. (2020) Romano, Y., Bates, S., and Candes, E. Achieving equalized odds by resampling sensitive attributes. Advances in neural information processing systems, 33:361–371, 2020.
- Scott (2015) Scott, D. W. Multivariate density estimation: theory, practice, and visualization. John Wiley & Sons, 2015.
- Sen et al. (2017) 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 & Zhang (2022) Tang, Z. and Zhang, K. Attainability and optimality: The equalized odds fairness revisited. In Conference on Causal Learning and Reasoning, pp. 754–786. PMLR, 2022.
- Tansey et al. (2022) Tansey, W., Veitch, V., Zhang, H., Rabadan, R., and Blei, D. M. The holdout randomization test for feature selection in black box models. Journal of Computational and Graphical Statistics, 31(1):151–162, 2022.
- Tifrea et al. (2023) Tifrea, A., Lahoti, P., Packer, B., Halpern, Y., Beirami, A., and Prost, F. Frappé: A group fairness framework for post-processing everything. arXiv preprint arXiv:2312.02592, 2023.
- Yang et al. (2022) Yang, J., Soltan, A. A. S., Yang, Y., and Clifton, D. A. Algorithmic fairness and bias mitigation for clinical machine learning: Insights from rapid covid-19 diagnosis by adversarial learning. medRxiv, 2022. doi: 10.1101/2022.01.13.22268948. URL https://www.medrxiv.org/content/early/2022/01/14/2022.01.13.22268948.
- Zemel et al. (2013) Zemel, R., Wu, Y., Swersky, K., Pitassi, T., and Dwork, C. Learning fair representations. In International conference on machine learning, pp. 325–333. PMLR, 2013.
- Zhang et al. (2018) Zhang, B. H., Lemoine, B., and Mitchell, M. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pp. 335–340, 2018.
Appendix A Example of KPC as a 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 $MMD^{2}(P_{U},P_{V})=\|\mu_{U}-\mu_{V}\|_{\mathcal{H}}^{2}$ where $\mathcal{H}$ is RKHS and $\mu_{U}=\mathbb{E}k(·,U)$ is the kernel mean embedding of a distribution $P_{U}$ (Gretton et al., 2012) and consider the special case where the kernel is linear and $U=\alpha W+\beta V+\varepsilon$ with $W,V,\varepsilon$ being independently distributed with mean 0 and variance 1. In this case, we 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+\alpha^{2}+\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$ . Hence, we can see that $KPC(U,V|W)$ reduces to the squared classical partial correlation between $U$ and $V$ given $W$ : $KPC(U,V|W)=(\rho_{UV· W})^{2}=\frac{\beta^{2}}{1+\beta^{2}}$ . In this special model, we know that $U$ is conditionally independent of $V$ given $W$ if and only if the partial correlation/KPC is 0 ( $\beta$ = 0).
Appendix B Proofs
* Proof of Theorem2.1*
Let $S({\mathbf{A}})=\{A_{1},...,A_{n}\}$ denote the row set of the observed $n$ realizations of sensitive attributes (unordered and duplicates are allowed). Let ${\mathbf{X}}$ , $\hat{\mathbf{Y}}\coloneqq f({\mathbf{X}})$ and ${\mathbf{Y}}$ be the associated $n$ feature, prediction, and response observations. Recall that, with a slight abuse of notations, we have used $q(.)$ to denote both the density for continuous variables or potentially point mass for discrete observations. For example, if we have a continuous variable $U$ and discrete variable $V$ , then, $q_{U,V}(u,v)=q_{U|V}(u|v)q_{V}(v)$ with $q_{V}(v)$ the point mass at $v$ for $V$ and $q_{U|V}(u|v)$ is the conditional density of $U$ given $V=v$ . Similar convention is adopted for the definition of $\mathbb{P}$ , e.g., $\mathbb{P}(U=u,V=v)=q_{U|V}(u|v)q_{V}(v)$ , $\mathbb{P}(U=u,V≤ v)=\sum_{v^{\prime}≤ v}q_{U|V}(u|v)q_{V}(v^{\prime})$ , $\mathbb{P}(U≤ u,V≤ v)=\sum_{v^{\prime}≤ v}∈t q_{U|V}(u^{\prime}|v^{%
\prime})q_{V}(v^{\prime})du^{\prime}$ . 1. Task 1: Show that $\tilde{\mathbf{A}}$ generated by ICP is a valid conditional permutation of ${\mathbf{A}}$ , as generated by CP.
Proof of Task 1. Recall that conditional on $S({\mathbf{A}})=S$ for some $S=\{a_{1},...,a_{n}\}$ , we have (Berrett et al., 2020):
$$
\mathbb{P}\left\{{\mathbf{A}}={\mathbf{a}}_{\pi}\right|S({\mathbf{A}})=S,{%
\mathbf{Y}}\}=\frac{q^{n}_{A|Y}\left({\mathbf{a}}_{\pi}\mid{\mathbf{Y}}\right)%
}{\sum_{\pi^{\prime}\in\mathcal{S}_{n}}q_{A|Y}^{n}\left({\mathbf{a}}_{\pi^{%
\prime}}\mid{\mathbf{Y}}\right)}, \tag{8}
$$
where ${\mathbf{a}}=(a_{1},...,a_{n})$ is the stacked $a$ values in $S$ . On the other hand, conditional on $S(\tilde{\mathbf{A}})=S$ , by construction:
$$
\displaystyle\mathbb{P}\left\{\tilde{\mathbf{A}}={\mathbf{a}}_{\pi}|S({\mathbf%
{A}})=S,{\mathbf{Y}}\right\}=\frac{q_{Y|A}^{n}\left({\mathbf{Y}}_{\pi^{-1}}%
\mid{\mathbf{a}}\right)}{\sum_{\pi^{\prime}}q^{n}_{Y|A}\left({\mathbf{Y}}_{{%
\pi^{\prime}}^{-1}}|{\mathbf{a}}\right)}=\frac{q_{A|Y}^{n}\left({\mathbf{a}}_{%
\pi}\mid{\mathbf{Y}}\right)}{\sum_{\pi^{\prime}}q_{A|Y}^{n}\left({\mathbf{a}}_%
{\pi}\mid{\mathbf{Y}}\right)}. \tag{9}
$$
where the last equality utilizes the following fact,
| | $\displaystyle\frac{q_{Y|A}^{n}\left({\mathbf{Y}}_{\pi^{-1}}\mid{\mathbf{a}}%
\right)}{\sum_{\pi^{\prime}}q^{n}_{Y|A}\left({\mathbf{Y}}_{{\pi^{\prime}}^{-1}%
}|{\mathbf{a}}\right)}=\frac{q^{n}_{Y,A}\left({\mathbf{Y}}_{\pi^{-1}},{\mathbf%
{a}}\right)}{\sum_{\pi^{\prime}∈\mathcal{S}_{n}}q^{n}_{Y,A}\left({\mathbf{Y}%
}_{{\pi^{\prime}}^{-1}},{\mathbf{a}}\right)}=\frac{q^{n}_{Y,A}\left({\mathbf{Y%
}},{\mathbf{a}}_{\pi}\right)}{\sum_{\pi^{\prime}∈\mathcal{S}_{n}}q^{n}_{Y,A}%
\left({\mathbf{Y}},{\mathbf{a}}_{\pi^{\prime}}\right)}=\frac{q_{A|Y}^{n}\left(%
{\mathbf{a}}_{\pi}\mid{\mathbf{Y}}\right)}{\sum_{\pi^{\prime}}q_{A|Y}^{n}\left%
({\mathbf{a}}_{\pi^{\prime}}\mid{\mathbf{Y}}\right)}.$ | |
| --- | --- | --- |
Hence, by construction, we must have $\mathbb{P}\left\{\tilde{\mathbf{A}}={\mathbf{a}}_{\pi}|S({\mathbf{A}})=S,{%
\mathbf{Y}}\right\}=\mathbb{P}\left\{{\mathbf{A}}={\mathbf{a}}_{\pi}\right|S({%
\mathbf{A}})=S,{\mathbf{Y}}\}$
1. Task 2: Show that $(\hat{\mathbf{Y}},{\mathbf{A}},{\mathbf{Y}})\overset{d}{=}(\hat{\mathbf{Y}},%
\tilde{\mathbf{A}},{\mathbf{Y}})$ given conditional independence $\hat{Y}\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern 2.0%
mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{$\textstyle\perp$\hss}\mkern 2%
.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptstyle\perp$\hss}\mkern 2%
.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptscriptstyle\perp$\hss%
}\mkern 2.0mu{\scriptscriptstyle\perp}}}A|Y$ .
Proof of Task 2. By Task 1, we can show that $\tilde{{\mathbf{A}}}|{\mathbf{Y}}\overset{d}{=}{\mathbf{A}}|{\mathbf{Y}}$ :
$$
\mathbb{P}({\mathbf{A}}\leq{\mathbf{t}}|Y)=\mathbb{E}_{S|{\mathbf{Y}}}\mathbb{%
P}({\mathbf{A}}\leq{\mathbf{t}}|{\mathbf{Y}},S({\mathbf{A}})=S)]=\mathbb{E}_{S%
|Y}\mathbb{P}(\tilde{{\mathbf{A}}}\leq{\mathbf{t}}|{\mathbf{Y}},S({\mathbf{A}}%
)=S)]=\mathbb{P}(\tilde{{\mathbf{A}}}\leq{\mathbf{t}}|Y).
$$
Additionally, under the assumption that $A\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern 2.0mu{%
\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{$\textstyle\perp$\hss}\mkern 2.0%
mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptstyle\perp$\hss}\mkern 2.%
0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptscriptstyle\perp$\hss}%
\mkern 2.0mu{\scriptscriptstyle\perp}}}\hat{Y}|Y$ , $\tilde{A}\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern 2.%
0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{$\textstyle\perp$\hss}\mkern 2%
.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptstyle\perp$\hss}\mkern 2%
.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{$\scriptscriptstyle\perp$\hss%
}\mkern 2.0mu{\scriptscriptstyle\perp}}}\hat{Y}|Y$ by construction since $\tilde{A}$ depends on the observed data only through $Y$ and $S({\mathbf{A}})$ . Consequently, we have
$$
q_{\hat{\mathbf{Y}},{\mathbf{A}},{\mathbf{Y}}}(\hat{\mathbf{y}},{\mathbf{a}},{%
\mathbf{y}})=q_{\hat{\mathbf{Y}}|{\mathbf{Y}}}(\hat{\mathbf{y}}|{\mathbf{y}})q%
_{{\mathbf{A}}|{\mathbf{Y}}}({\mathbf{a}}|{\mathbf{y}})q_{{\mathbf{Y}}}({%
\mathbf{y}})=q_{\hat{\mathbf{Y}}|{\mathbf{Y}}}(\hat{\mathbf{y}}|{\mathbf{y}})q%
_{\tilde{\mathbf{A}}|{\mathbf{Y}}}({\mathbf{a}}|{\mathbf{y}})q_{{\mathbf{Y}}}(%
{\mathbf{y}})=q_{\hat{\mathbf{Y}},\tilde{\mathbf{A}},{\mathbf{Y}}}(\hat{%
\mathbf{y}},{\mathbf{a}},{\mathbf{y}}).
$$
∎
* Proof of Proposition2.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 1 in (Berrett et al., 2020) . ∎
Appendix C Sampling Algorithm for ICP
To sample the permutation $\Pi$ from the probabilities:
$$
\mathbb{P}\left\{\Pi=\pi\mid{\mathbf{A}},{\mathbf{Y}}\right\}=\frac{q^{n}\left%
({\mathbf{Y}}_{{\pi}^{-1}}\mid{\mathbf{A}}\right)}{\sum_{\pi^{\prime}\in%
\mathcal{S}_{n}}q^{n}\left({\mathbf{Y}}_{{\pi^{\prime}}^{-1}}\mid{\mathbf{A}}%
\right)},
$$
we use the Parallelized pairwise sampler for the CPT proposed in Berrett et al. (2020), which is detailed as follows:
Input: Data $({\mathbf{A}},{\mathbf{Y}})$ , Initial permutation $\Pi^{[0]}$ , integer $S≥ 1$ .
1: for $s=1,...,S$ do
2: Sample uniformly without replacement from $\{1,...,n\}$ to obtain disjoint pairs
$$
\left(i_{s,1},j_{s,1}\right),\ldots,\left(i_{s,\lfloor n/2\rfloor},j_{s,%
\lfloor n/2\rfloor}\right).
$$
3: Draw independent Bernoulli variables $B_{s,1},...,B_{s,\lfloor n/2\rfloor}$ with odds ratios
$$
\frac{\mathbb{P}\left\{B_{s,k}=1\right\}}{\mathbb{P}\left\{B_{s,k}=0\right\}}=%
\frac{q\left(Y_{\left(\Pi^{[s-1]}\left(j_{s,k}\right)\right)}\mid A_{i_{s,k}}%
\right)\cdot q\left(Y_{\left(\Pi^{[s-1]}\left(i_{s,k}\right)\right.}\mid A_{j_%
{s,k}}\right)}{q\left(Y_{\left(\Pi^{[s-1]}\left(i_{s,k}\right)\right)}\mid A_{%
i_{s,k}}\right)\cdot q\left(Y_{\left(\Pi^{[s-1]}\left(j_{s,k}\right)\right)}%
\mid A_{j_{s,k}}\right)}.
$$
Define $\Pi^{[s]}$ by swapping $\Pi^{[s-1]}\left(i_{s,k}\right)$ and $\Pi^{[s-1]}\left(j_{s,k}\right)$ for each $k$ with $B_{s,k}=1$ .
4: end for
Output: Permuted copy $\tilde{\mathbf{A}}={\mathbf{A}}_{{\Pi^{[S]}}^{-1}}$ .
Algorithm 3 Parallelized pairwise sampler for the ICP
Appendix D Additional Comparisons of CP/ICP
When we know the true conditional laws $q_{Y|A}(.)$ (conditional density $Y$ given $A$ ) and $q_{A|Y}(.)$ (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 densities are denoted as $\check{q}_{Y|A}(.)$ and $\check{q}_{A|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, is beyond the scope, we provide some additional heuristic insights to 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 4 in Berrett et al. (2020), let ${\mathbf{A}}_{\pi_{m}}$ be some permuted copies of $A$ according to the estimated conditional law $\check{q}_{A|Y}()$ , an upper bound of exchangeability violation for ${\mathbf{A}}$ and ${\mathbf{A}}_{\pi}$ is related to the total variation between the estimated density $\check{q}_{A|Y}(.)$ and $q_{A|Y}(.)$ (Theorem 4 in Berrett et al. (2020)):
$$
\displaystyle d_{TV}\{(({\mathbf{Y}},{\mathbf{A}}),({\mathbf{Y}},{\mathbf{A}}_%
{\pi}))|{\mathbf{Y}}),(({\mathbf{Y}},\check{{\mathbf{A}}}),({\mathbf{Y}},{%
\mathbf{A}}_{\pi}))|{\mathbf{Y}})\} \displaystyle\leq \displaystyle d_{TV}(\prod_{i=1}^{n}\check{q}_{A|Y}(.|y_{i}),\prod_{i=1}^{n}q_%
{A|Y}(.|y_{i}))\overset{(b_{1})}{\leq}\sum_{i=1}^{n}d_{TV}(\check{q}_{A|Y}(.|y%
_{i}),q_{A|Y}(.|y_{i})), \tag{10}
$$
where step $(b_{1})$ is from Lemma (B.8) from Ghosal & van der Vaart (2017). We adapt the proof arguments of Theorem 4 in Berrett et al. (2020) to the ICP procedure.
Specifically, let ${\mathbf{Y}}_{\pi}$ be the conditional permutation of ${\mathbf{Y}}$ according to $\check{q}_{Y|A}(.)$ and $\check{{\mathbf{Y}}}$ be a new copy sampled according to $\check{q}_{Y|A}(.)$ . We will have
$$
\displaystyle d_{TV}\{(({\mathbf{Y}},{\mathbf{A}}),({\mathbf{Y}}_{\pi},{%
\mathbf{A}})|{\mathbf{A}})\}\leq\sum_{i=1}^{n}d_{TV}(\check{q}_{Y|A}(.|A_{i}),%
q_{Y|A}(.|A_{i})). \tag{11}
$$
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 $\pi^{-1}$ to $({\mathbf{Y}},{\mathbf{A}})$ and $({\mathbf{Y}},{\mathbf{A}}_{\pi^{-1}})$ . The resulting $({\mathbf{Y}}_{\pi^{-1}},{\mathbf{A}}_{\pi^{-1}})$ is equivalent to $({\mathbf{Y}},{\mathbf{A}})$ and the resulting $({\mathbf{Y}},{\mathbf{A}}_{\pi^{-1}})$ is exactly the ICP conditionally permuted version. Next we can remove the conditioning event by marginalizing out ${\mathbf{Y}}$ and ${\mathbf{A}}$ in (D.1) and (11) respectively. Hence, we obtain upper bounds for violation of exchangeability using CP and ICP permutation copies, which is smaller for ICP if $\check{q}_{Y|A}(.)$ is more accurate on average:
$$
\mathbb{E}_{A}\left[d_{TV}(\check{q}_{Y|A}(.|A),q_{Y|A}(.|A))\right]<\mathbb{E%
}_{Y}\left[d_{TV}(\check{q}_{A|Y}(.|Y),q_{A|Y}(.|Y))\right].
$$
D.2 ICP Achieved Higher Quality Empirically with MAF Density Estimation
Here, we compare ICP and CP using MAF-generated densities. The data-generating 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 $q_{Y|A}$ 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.
<details>
<summary>2404.05678v4/x6.png Details</summary>

### Visual Description
# Technical Document Extraction: Scatter Plot Analysis
## Image Description
The image is a comparative scatter plot with box plots, analyzing two statistical methods (`CP_MAF` and `ICP_MAF`) across varying values of `K` under three distinct `K0` settings (`K0=1`, `K0=5`, `K0=10`). The y-axis represents "Restricted TV" (Total Variation), and the x-axis represents `K` (a parameter ranging from 0 to 100). The plot is divided into three horizontal sections, each corresponding to a `K0` value.
---
## Key Components
### 1. **Axes and Labels**
- **X-axis**: Labeled `K`, with discrete values at `0, 5, 10, 20, 50, 100`.
- **Y-axis**: Labeled `Restricted TV`, with values ranging from `-6.0` to `-4.0` in increments of `0.5`.
- **Legend**: Located in the **right-middle** of the plot, with:
- **Red squares**: `CP_MAF` method.
- **Cyan squares**: `ICP_MAF` method.
### 2. **Sections by `K0`**
The plot is segmented into three horizontal regions, each with a title indicating the `K0` value:
- **Top Section**: `K0 = 1`
- **Middle Section**: `K0 = 5`
- **Bottom Section**: `K0 = 10`
Each section contains scatter points and box plots for `CP_MAF` (red) and `ICP_MAF` (cyan) across the `K` values.
---
## Data Trends and Observations
### 1. **`K0 = 1`**
- **`CP_MAF` (Red)**:
- Starts at `K=0` with a median Restricted TV of approximately `-5.0`.
- Shows a slight upward trend as `K` increases, reaching a median of `-4.5` at `K=100`.
- Outliers are sparse but present at lower `K` values (e.g., `K=0` has points near `-5.5`).
- **`ICP_MAF` (Cyan)**:
- Begins at `K=0` with a median of `-5.5`, higher than `CP_MAF`.
- Exhibits a steeper upward trend, reaching a median of `-4.5` at `K=100`.
- More outliers at lower `K` values (e.g., `K=0` has points near `-6.0`).
### 2. **`K0 = 5`**
- **`CP_MAF` (Red)**:
- Starts at `K=0` with a median of `-5.0`.
- Shows a gradual increase, stabilizing around `-4.5` at `K=100`.
- Fewer outliers compared to `K0=1`.
- **`ICP_MAF` (Cyan)**:
- Begins at `K=0` with a median of `-5.0`.
- Follows a similar upward trend to `CP_MAF`, with tighter clustering at higher `K` values.
- Outliers are less frequent than in `K0=1`.
### 3. **`K0 = 10`**
- **`CP_MAF` (Red)**:
- Starts at `K=0` with a median of `-5.0`.
- Maintains a consistent upward trend, reaching `-4.5` at `K=100`.
- Minimal outliers across all `K` values.
- **`ICP_MAF` (Cyan)**:
- Begins at `K=0` with a median of `-5.0`.
- Shows a slightly steeper increase than `CP_MAF`, stabilizing at `-4.5` at `K=100`.
- Outliers are rare, with tighter clustering than in `K0=5`.
---
## Spatial Grounding and Color Verification
- **Legend Position**: Right-middle of the plot.
- **Color Consistency**:
- All red data points correspond to `CP_MAF`.
- All cyan data points correspond to `ICP_MAF`.
- Box plots for each method match their respective colors.
---
## Summary of Key Data Points
| K0 | Method | K Value | Median Restricted TV | Notable Trends |
|----|-----------|---------|----------------------|-------------------------------|
| 1 | CP_MAF | 0 | -5.0 | Slight upward trend |
| 1 | ICP_MAF | 0 | -5.5 | Steeper upward trend |
| 5 | CP_MAF | 0 | -5.0 | Gradual increase |
| 5 | ICP_MAF | 0 | -5.0 | Tighter clustering at high K |
| 10 | CP_MAF | 0 | -5.0 | Minimal outliers |
| 10 | ICP_MAF | 0 | -5.0 | Steeper increase than CP_MAF |
---
## Conclusion
The plot demonstrates that both `CP_MAF` and `ICP_MAF` methods show improved performance (higher Restricted TV) as `K` increases, with `ICP_MAF` generally outperforming `CP_MAF` across all `K0` settings. The effect is most pronounced at lower `K0` values (`K0=1`), where `ICP_MAF` exhibits a steeper upward trend. At higher `K0` values (`K0=10`), the performance gap narrows, with both methods converging toward similar Restricted TV values.
</details>
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 as the noise level $K$ increases, with $K_{0}={1,5,10}$ respectively.
Appendix 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 R 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 as follows:
- We set $f$ as a linear model and use the Adam optimizer with 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, 120, 140, 160, 180, 200}. The discriminator is implemented as a four-layer neural network with a hidden layer of size 64 and ReLU non-linearities. We use the Adam optimizer, with a fixed learning rate of 1e-4.
For the MAF used to estimate the conditional density ( $Y|A$ and $A|Y$ ) in the training phase, we use MAF with one MADE component and one hidden layer with $2*\text{conditional inputs}$ nodes, and for optimizer we choose Adam with 0.01 $l_{1}$ penalty and 0.1 learning rate.
E.1.1 Low sensitive attribute dependence cases
We report the results with A-dependence $w=0.6$ in Figure 6.
<details>
<summary>2404.05678v4/x7.png Details</summary>

### Visual Description
# Technical Document Extraction: Analysis of Loss Metrics Across Methods
## Overview
The image contains six subplots arranged in a 2x3 grid, comparing loss metrics across four methods (Oracle, FairICP, FairCP, FDL) under varying conditions. All subplots share a common y-axis labeled "Increased Dimensions" or "Loss," while x-axes vary by parameter (KPC dimensions, statistical power). The legend is positioned in the top-left corner of the grid.
---
### **Legend**
- **Oracle**: Blue line with circular markers
- **FairICP**: Green line with circular markers
- **FairCP**: Cyan line with circular markers
- **FDL**: Red line with circular markers
---
### **Subplot Analysis**
#### **Top Row**
1. **Left Subplot**
- **Title**: "Violation of Equalized Odds: test on KPC"
- **X-axis**: "KPC: dim = 1" (values: 0.02 → 0.06)
- **Y-axis**: "Increased Dimensions" (values: 2.00 → 2.25)
- **Trends**:
- All methods show a **downward trend** as KPC dimension increases.
- **FDL (red)** starts highest (~2.25) and drops sharply to ~2.00.
- **Oracle (blue)** and **FairICP (green)** converge near 2.00.
- **FairCP (cyan)** remains slightly above Oracle/FairICP.
2. **Right Subplot**
- **Title**: "Violation of Equalized Odds: test on statistical power"
- **X-axis**: "Power: dim = 1" (values: 0.1 → 1.0)
- **Y-axis**: "Increased Dimensions" (values: 2.00 → 2.25)
- **Trends**:
- Loss decreases as power increases for all methods.
- **FDL (red)** starts highest (~2.25) and drops steeply to ~2.00.
- **Oracle (blue)** and **FairICP (green)** remain stable near 2.00.
- **FairCP (cyan)** shows moderate decline.
---
#### **Middle Row**
3. **Left Subplot**
- **Title**: "KPC: dim = 5"
- **X-axis**: "KPC: dim = 5" (values: 0.05 → 0.25)
- **Y-axis**: "Loss" (values: 12.5 → 25)
- **Trends**:
- **FDL (red)** starts highest (~25) and drops sharply to ~12.5.
- **Oracle (blue)** and **FairICP (green)** converge near 12.5.
- **FairCP (cyan)** declines gradually.
4. **Right Subplot**
- **Title**: "Power: dim = 5"
- **X-axis**: "Power: dim = 5" (values: 0.6 → 1.0)
- **Y-axis**: "Loss" (values: 12.5 → 25)
- **Trends**:
- Loss decreases as power increases.
- **FDL (red)** starts highest (~25) and drops steeply to ~12.5.
- **Oracle (blue)** and **FairICP (green)** remain stable near 12.5.
- **FairCP (cyan)** shows moderate decline.
---
#### **Bottom Row**
5. **Left Subplot**
- **Title**: "KPC: dim = 10"
- **X-axis**: "KPC: dim = 10" (values: 0.100 → 0.200)
- **Y-axis**: "Loss" (values: 40 → 120)
- **Trends**:
- **FDL (red)** exhibits a **sharp spike** at x=0.150 (~120) before dropping to ~40.
- **Oracle (blue)** and **FairICP (green)** remain stable near 40.
- **FairCP (cyan)** declines gradually.
6. **Right Subplot**
- **Title**: "Power: dim = 10"
- **X-axis**: "Power: dim = 10" (values: 0.80 → 1.00)
- **Y-axis**: "Loss" (values: 40 → 120)
- **Trends**:
- Loss decreases as power increases.
- **FDL (red)** starts highest (~120) and drops steeply to ~40.
- **Oracle (blue)** and **FairICP (green)** remain stable near 40.
- **FairCP (cyan)** shows moderate decline.
---
### **Key Observations**
1. **Method Performance**:
- **FDL (red)** consistently shows the highest initial loss but steep declines in most subplots.
- **Oracle (blue)** and **FairICP (green)** exhibit the most stable performance across dimensions and power levels.
- **FairCP (cyan)** performs intermediately, with gradual declines.
2. **Dimensionality Impact**:
- Loss values increase with higher KPC dimensions (e.g., dim=10 subplots show higher loss ranges).
3. **Statistical Power Impact**:
- Higher power (closer to 1.0) correlates with lower loss across all methods.
---
### **Spatial Grounding**
- **Legend Position**: Top-left corner of the grid.
- **Axis Alignment**:
- X-axes vary by parameter (KPC dimensions, power) and dimension (1, 5, 10).
- Y-axes alternate between "Increased Dimensions" (top row) and "Loss" (middle/bottom rows).
---
### **Data Table Reconstruction**
| Method | KPC dim=1 (Loss) | KPC dim=5 (Loss) | KPC dim=10 (Loss) | Power dim=1 (Loss) | Power dim=5 (Loss) | Power dim=10 (Loss) |
|----------|------------------|------------------|-------------------|--------------------|--------------------|---------------------|
| Oracle | ~2.00 | ~12.5 | ~40 | ~2.00 | ~12.5 | ~40 |
| FairICP | ~2.00 | ~12.5 | ~40 | ~2.00 | ~12.5 | ~40 |
| FairCP | ~2.05 | ~13.0 | ~45 | ~2.05 | ~13.0 | ~45 |
| FDL | ~2.25 | ~25 | ~120 (spike) | ~2.25 | ~25 | ~120 |
---
### **Language Notes**
- All text is in **English**. No non-English content detected.
</details>
(a) Simulation 1
<details>
<summary>2404.05678v4/x8.png Details</summary>

### Visual Description
# Technical Document Extraction: Violation of Equalized Odds Analysis
## Overview
The image contains **eight comparative line graphs** organized in a 2x4 grid, analyzing the **violation of equalized odds** under two testing frameworks: **KPC (Kernel Principal Component Analysis)** and **statistical power**. Each graph evaluates four fairness metrics across increasing dimensionality (dim=1, 5, 10). The y-axis represents **Increased Dimensions** (logarithmic scale), while the x-axis varies between KPC/Power values.
---
## Legend & Color Mapping
- **Oracle**: Blue (circle markers)
- **FairICP**: Green (circle markers)
- **FairCP**: Cyan (circle markers)
- **FDL**: Red (circle markers)
**Legend Position**: Top-left corner of each graph.
---
## Graph Analysis
### 1. **Violation of Equalized Odds: test on KPC**
#### a. KPC: dim = 1
- **X-axis**: 0.00 to 0.10 (KPC values)
- **Y-axis**: Increased Dimensions (log scale)
- **Trends**:
- All lines decline sharply as x increases.
- **Oracle** (blue) starts at ~1.3, drops to ~1.0 by x=0.1.
- **FairICP** (green) starts at ~1.4, converges to ~1.0.
- **FairCP** (cyan) starts at ~1.9, declines steeply.
- **FDL** (red) starts at ~1.8, drops to ~1.0.
- **Key Data Points**:
- Oracle: [0.00, 1.3], [0.10, 1.0]
- FairICP: [0.00, 1.4], [0.10, 1.0]
- FairCP: [0.00, 1.9], [0.10, 1.0]
- FDL: [0.00, 1.8], [0.10, 1.0]
#### b. KPC: dim = 5
- **X-axis**: 0.00 to 0.20
- **Trends**:
- Lines flatten as x increases.
- **Oracle** starts at ~1.2, drops to ~1.0 by x=0.2.
- **FairICP** starts at ~1.3, converges to ~1.0.
- **FairCP** starts at ~1.6, declines to ~1.0.
- **FDL** starts at ~1.5, drops to ~1.0.
- **Key Data Points**:
- Oracle: [0.00, 1.2], [0.20, 1.0]
- FairICP: [0.00, 1.3], [0.20, 1.0]
- FairCP: [0.00, 1.6], [0.20, 1.0]
- FDL: [0.00, 1.5], [0.20, 1.0]
#### c. KPC: dim = 10
- **X-axis**: 0.00 to 0.30
- **Trends**:
- Minimal variation across x.
- All lines plateau near y=1.0.
- **Oracle** starts at ~1.1, remains flat.
- **FairICP** starts at ~1.2, converges to ~1.0.
- **FairCP** starts at ~1.3, declines to ~1.0.
- **FDL** starts at ~1.3, drops to ~1.0.
- **Key Data Points**:
- Oracle: [0.00, 1.1], [0.30, 1.0]
- FairICP: [0.00, 1.2], [0.30, 1.0]
- FairCP: [0.00, 1.3], [0.30, 1.0]
- FDL: [0.00, 1.3], [0.30, 1.0]
---
### 2. **Violation of Equalized Odds: test on statistical power**
#### a. Power: dim = 1
- **X-axis**: 0.2 to 1.0 (Power values)
- **Y-axis**: Increased Dimensions (log scale)
- **Trends**:
- Lines decline steeply, then flatten.
- **Oracle** starts at ~1.3, drops to ~1.0 by x=1.0.
- **FairICP** starts at ~1.4, converges to ~1.0.
- **FairCP** starts at ~1.9, declines to ~1.0.
- **FDL** starts at ~1.8, drops to ~1.0.
- **Key Data Points**:
- Oracle: [0.2, 1.3], [1.0, 1.0]
- FairICP: [0.2, 1.4], [1.0, 1.0]
- FairCP: [0.2, 1.9], [1.0, 1.0]
- FDL: [0.2, 1.8], [1.0, 1.0]
#### b. Power: dim = 5
- **X-axis**: 0.2 to 1.0
- **Trends**:
- Lines drop sharply at x=0.4, then flatten.
- **Oracle** starts at ~1.3, drops to ~1.0 by x=1.0.
- **FairICP** starts at ~1.4, converges to ~1.0.
- **FairCP** starts at ~1.9, declines to ~1.0.
- **FDL** starts at ~1.8, drops to ~1.0.
- **Key Data Points**:
- Oracle: [0.2, 1.3], [1.0, 1.0]
- FairICP: [0.2, 1.4], [1.0, 1.0]
- FairCP: [0.2, 1.9], [1.0, 1.0]
- FDL: [0.2, 1.8], [1.0, 1.0]
#### c. Power: dim = 10
- **X-axis**: 0.2 to 1.0
- **Trends**:
- Lines drop sharply at x=0.4, then flatten.
- **Oracle** starts at ~1.3, drops to ~1.0 by x=1.0.
- **FairICP** starts at ~1.4, converges to ~1.0.
- **FairCP** starts at ~1.9, declines to ~1.0.
- **FDL** starts at ~1.8, drops to ~1.0.
- **Key Data Points**:
- Oracle: [0.2, 1.3], [1.0, 1.0]
- FairICP: [0.2, 1.4], [1.0, 1.0]
- FairCP: [0.2, 1.9], [1.0, 1.0]
- FDL: [0.2, 1.8], [1.0, 1.0]
---
## Observations
1. **Dimensionality Impact**:
- Higher dimensions (dim=10) show reduced sensitivity to KPC/Power changes.
- All metrics converge to y=1.0 (no violation) as x increases.
2. **Metric Performance**:
- **FDL** (red) consistently shows the steepest initial decline.
- **FairCP** (cyan) exhibits the highest initial violation but stabilizes fastest.
3. **Logarithmic Scale**:
- Y-axis compression emphasizes early-stage violations (x < 0.1 for KPC, x < 0.4 for Power).
---
## Notes
- No non-English text detected.
- All data points cross-referenced with legend colors.
- Trends verified visually before numerical extraction.
</details>
(b) Simulation 2
Figure 6: Prediction loss and metrics of fairness in simulation over 100 independent runs under Simulation 1 /Simulation 2 and $w=0.6$ . For each setting, conditional dependence measure KPC and statistical power ${\mathbb{P}}\{p\text{-value}<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 FairICP, FDL, and oracle model with different hyperparameters $\mu$ .
E.2 Real Data Model Architecture
Regression Tasks
For FairICP and FDL (code is adapted from https://github.com/yromano/fair_dummies), the hyperparameters used for linear model and neural network are as 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 a 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 $\mu$ is set as $\{0,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9\}$ .
- 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.
- Density estimation of $Y|A$ and $A|Y$ : we use MAF with 5 MADE components and two hidden layers of 64 nodes each. We use Adam optimizer with 0.001 learning rate.
For HGR (code is adapted from https://github.com/criteo-research/continuous-fairness), 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 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 penalty parameter $\lambda$ is set as $\{0,0.25,0.5,0.75,1,2,4,8,16\}$ .
- Neural network: we 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.
Classification Tasks
For FairICP and FDL, the hyperparameters used for 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 a mini-batch size in {128, 256}, learning rate in {1e-4, 1e-3, 1e-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 a hidden layer of size 64 and ReLU non-linearities. We use the Adam optimizer, with cross-entropy loss and a fixed learning rate in {1e-5, 1e-4, 1e-3}. The penalty parameter $\mu$ is set as $\{0,0.3,0.5,0.7,0.8,0.9\}$ .
- 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.
- Density estimation of $Y|A$ : we use a 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 a mini-batch size in {64, 128, 256}, learning rate in {1e-4, 1e-3, 1e-2}, and the number of epochs in {20, 40, 60, 80, 100}. The penalty parameter $\lambda$ is set as $\{0,0.0375,0.075,0.125,0.25,0.5,0.75,1,1.5\}$ .
- Neural network: we 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://github.com/algowatchpenn/GerryFair), the hyperparameters used for the linear model and neural network are as follows:
- Linear: we 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: we set $f$ as a 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.005} and batch size in {128, 256}. The rest of the parameters are the same as in the linear case.
For Reduction (we use the package from https://github.com/fairlearn/fairlearn), the hyperparameters used for the linear model and neural network are as follows:
- Linear: we use the default logistic regression in sklearn. The maximum iteration is 50, and the trade-off parameter is in [0.5, 100].
- Neural network: we set $f$ as a 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, 256}. The rest of the parameters are the same as in the linear case.
E.3 Pareto Trade-Off Curves Based on Equalized Odds Testing Power
<details>
<summary>2404.05678v4/x9.png Details</summary>

### Visual Description
# Technical Document Extraction: Line Charts Analysis
## Chart 1: Crimes 1dim & 3dim
### Header
- **Title**: Crimes 1dim & 3dim
### Axes
- **X-axis**: Power (range: 0.0 to 1.0)
- **Y-axis**: Loss (range: 0.35 to 0.60)
### Legend
- **Placement**: Right-aligned
- **Entries**:
- **Blue Circle**: FairICP: 1dim
- **Red Square**: FDL: 1dim
- **Green Dash**: HGR: 1dim
- **Blue Circle**: FairICP: 3dim
- **Red Square**: FDL: 3dim
- **Green Dash**: HGR: 3dim
### Data Trends
1. **FairICP: 1dim** (Blue Circle):
- Starts at ~0.38 (Power=0.0)
- Decreases steadily to ~0.35 (Power=1.0)
2. **FDL: 1dim** (Red Square):
- Starts at ~0.62 (Power=0.0)
- Sharp decline to ~0.35 (Power=1.0)
3. **HGR: 1dim** (Green Dash):
- Starts at ~0.37 (Power=0.0)
- Gradual decline to ~0.35 (Power=1.0)
4. **FairICP: 3dim** (Blue Circle):
- Starts at ~0.42 (Power=0.0)
- Decreases to ~0.35 (Power=1.0)
5. **FDL: 3dim** (Red Square):
- Starts at ~0.58 (Power=0.0)
- Sharp decline to ~0.35 (Power=1.0)
6. **HGR: 3dim** (Green Dash):
- Starts at ~0.45 (Power=0.0)
- Gradual decline to ~0.35 (Power=1.0)
## Chart 2: ACS Income
### Header
- **Title**: ACS Income
### Axes
- **X-axis**: Power (range: 0.80 to 1.00)
- **Y-axis**: Loss (range: 0.21 to 0.26)
### Legend
- **Placement**: Right-aligned
- **Entries**:
- **Blue Circle**: FairICP
- **Green Dash**: HGR
- **Purple Triangle**: GerryFair
### Data Trends
1. **FairICP** (Blue Circle):
- Starts at ~0.215 (Power=0.80)
- Slightly decreases to ~0.21 (Power=1.00)
2. **HGR** (Green Dash):
- Starts at ~0.22 (Power=0.80)
- Gradual decline to ~0.21 (Power=1.00)
3. **GerryFair** (Purple Triangle):
- Starts at ~0.25 (Power=0.80)
- Sharp decline to ~0.21 (Power=1.00)
## Chart 3: Adult
### Header
- **Title**: Adult
### Axes
- **X-axis**: Power (range: 0.20 to 0.80)
- **Y-axis**: Loss (range: 0.155 to 0.185)
### Legend
- **Placement**: Right-aligned
- **Entries**:
- **Blue Circle**: FairICP
- **Orange Star**: Reduction
- **Green Dash**: HGR
- **Red Square**: FDL
- **Purple Triangle**: GerryFair
### Data Trends
1. **FairICP** (Blue Circle):
- Starts at ~0.158 (Power=0.20)
- Slightly decreases to ~0.155 (Power=0.80)
2. **Reduction** (Orange Star):
- Starts at ~0.16 (Power=0.20)
- Gradual decline to ~0.155 (Power=0.80)
3. **HGR** (Green Dash):
- Starts at ~0.165 (Power=0.20)
- Gradual decline to ~0.155 (Power=0.80)
4. **FDL** (Red Square):
- Starts at ~0.16 (Power=0.20)
- Sharp decline to ~0.155 (Power=0.80)
5. **GerryFair** (Purple Triangle):
- Starts at ~0.185 (Power=0.20)
- Sharp decline to ~0.155 (Power=0.80)
## Chart 4: COMPAS
### Header
- **Title**: COMPAS
### Axes
- **X-axis**: Power (range: 0.10 to 0.40)
- **Y-axis**: Loss (range: 0.34 to 0.48)
### Legend
- **Placement**: Right-aligned
- **Entries**:
- **Blue Circle**: FairICP
- **Orange Star**: Reduction
- **Green Dash**: HGR
- **Red Square**: FDL
- **Purple Triangle**: GerryFair
### Data Trends
1. **FairICP** (Blue Circle):
- Starts at ~0.40 (Power=0.10)
- Decreases to ~0.34 (Power=0.40)
2. **Reduction** (Orange Star):
- Starts at ~0.38 (Power=0.10)
- Gradual decline to ~0.34 (Power=0.40)
3. **HGR** (Green Dash):
- Starts at ~0.48 (Power=0.10)
- Sharp decline to ~0.34 (Power=0.40)
4. **FDL** (Red Square):
- Starts at ~0.42 (Power=0.10)
- Sharp decline to ~0.34 (Power=0.40)
5. **GerryFair** (Purple Triangle):
- Starts at ~0.44 (Power=0.10)
- Sharp decline to ~0.34 (Power=0.40)
## Notes
- All charts use a consistent color scheme for legend entries across datasets.
- No non-English text detected.
- Data points extracted visually; exact numerical values approximated from chart scales.
</details>
Figure 7: Prediction loss and violation of equalized odds (measured by Power) obtained by different methods on Crimes / ACS Income / Adult / COMPAS data over 100 random splits. The Pareto front for each algorithm is obtained by varying the fairness trade-off parameter.
E.4 Pareto Trade-Off Curves Based on 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 a binary classification task with categorical sensitive attributes to quantify equalized odds:
$$
\mathrm{DEO}:=\sum_{y\in\{0,1\}}\sum_{z\in\mathcal{Z}}|\operatorname{Pr}(\hat{%
Y}=1\mid Z=z,Y=y)-\operatorname{Pr}(\hat{Y}=1\mid Y=y)|,
$$
where $\hat{Y}$ is the predicted class label.
<details>
<summary>2404.05678v4/x10.png Details</summary>

### Visual Description
# Technical Document Extraction: Fairness Metrics Analysis
## Chart 1: Adult Dataset
### Spatial Grounding
- **Legend Position**: Top-right quadrant
- **X-axis (DEO)**: 0.20 to 0.40 (increments of 0.05)
- **Y-axis (Loss)**: 0.155 to 0.185 (increments of 0.005)
### Key Trends
1. **GerryFair (purple line)**:
- Starts at 0.185 loss (DEO=0.30)
- Sharp decline to 0.155 loss (DEO=0.40)
- *Visual verification*: Steep negative slope
2. **FairICP (blue line)**:
- Flat line at ~0.155 loss (DEO=0.20–0.40)
3. **Reduction (orange line)**:
- Initial drop from 0.160 (DEO=0.20) to 0.155 (DEO=0.25)
- Stabilizes at 0.155 (DEO=0.30–0.40)
4. **HGR (green line)**:
- Starts at 0.165 (DEO=0.20)
- Gradual decline to 0.155 (DEO=0.40)
5. **FDL (red line)**:
- Sharp spike to 0.160 (DEO=0.25)
- Stabilizes at 0.155 (DEO=0.30–0.40)
### Data Points (Adult)
| Model | DEO=0.20 | DEO=0.25 | DEO=0.30 | DEO=0.35 | DEO=0.40 |
|------------|----------|----------|----------|----------|----------|
| FairICP | 0.156 | 0.155 | 0.155 | 0.155 | 0.155 |
| Reduction | 0.160 | 0.155 | 0.155 | 0.155 | 0.155 |
| HGR | 0.165 | 0.156 | 0.155 | 0.155 | 0.155 |
| FDL | 0.155 | 0.160 | 0.155 | 0.155 | 0.155 |
| GerryFair | 0.185 | 0.180 | 0.175 | 0.170 | 0.155 |
## Chart 2: COMPAS Dataset
### Spatial Grounding
- **Legend Position**: Top-right quadrant
- **X-axis (DEO)**: 0.40 to 0.80 (increments of 0.10)
- **Y-axis (Loss)**: 0.34 to 0.48 (increments of 0.02)
### Key Trends
1. **GerryFair (purple line)**:
- Starts at 0.44 loss (DEO=0.40)
- Gradual decline to 0.34 loss (DEO=0.80)
- *Visual verification*: Linear negative slope
2. **HGR (green line)**:
- Starts at 0.48 loss (DEO=0.40)
- Steeper decline than GerryFair
- Ends at 0.34 loss (DEO=0.80)
3. **FairICP (blue line)**:
- Starts at 0.40 loss (DEO=0.40)
- Linear decline to 0.34 loss (DEO=0.80)
4. **Reduction (orange line)**:
- Starts at 0.38 loss (DEO=0.40)
- Linear decline to 0.34 loss (DEO=0.80)
5. **FDL (red line)**:
- Starts at 0.42 loss (DEO=0.40)
- Linear decline to 0.34 loss (DEO=0.80)
### Data Points (COMPAS)
| Model | DEO=0.40 | DEO=0.50 | DEO=0.60 | DEO=0.70 | DEO=0.80 |
|------------|----------|----------|----------|----------|----------|
| FairICP | 0.40 | 0.36 | 0.34 | 0.34 | 0.34 |
| Reduction | 0.38 | 0.36 | 0.34 | 0.34 | 0.34 |
| HGR | 0.48 | 0.42 | 0.38 | 0.36 | 0.34 |
| FDL | 0.42 | 0.38 | 0.36 | 0.34 | 0.34 |
| GerryFair | 0.44 | 0.40 | 0.38 | 0.36 | 0.34 |
## Cross-Validation Summary
1. **Color Consistency**: All legend colors match line colors in both charts
2. **Trend Verification**:
- All models show decreasing loss with increasing DEO
- GerryFair demonstrates most significant improvement in Adult dataset
- COMPAS dataset shows more gradual convergence across models
3. **Data Integrity**: No discrepancies between visual trends and numerical values
## Observations
- **Adult Dataset**: GerryFair achieves optimal performance (lowest loss) at DEO=0.40
- **COMPAS Dataset**: All models converge to identical loss (0.34) at DEO=0.80
- **Model Performance**:
- HGR shows highest initial loss in COMPAS
- FDL demonstrates most erratic behavior in Adult dataset
*Note: No non-English text detected. All axis labels, legends, and data points transcribed verbatim from source.*
</details>
Figure 8: Prediction loss and violation of equalized odds (measured by DEO) obtained by different methods on Adult / COMPAS data over 100 random splits. The Pareto front for each algorithm is obtained by varying the fairness trade-off parameter.
E.5 Running Time
We report the running time with neural networks as below:
| | Crimes (one race) | Crimes (all races) | ACS Income | Adult | COMPAS |
| --- | --- | --- | --- | --- | --- |
| FairICP | 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 5 trials.
E.6 Pareto Trade-Off Curves for Linear Models
We report the results with $f$ 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.
<details>
<summary>2404.05678v4/x11.png Details</summary>

### Visual Description
# Technical Document Extraction: Violation of Equalized Odds Analysis
## Chart 1: Violation of Equalized Odds (Dependence Measure KPC)
### Title
Violation of Equalized Odds: test on dependence measure KPC
### Axes
- **X-axis**: KPC (range: 0.00 to 0.30)
- **Y-axis**: Loss (range: 0.350 to 0.525)
### Legend
- **Placement**: Upper right corner
- **Entries**:
- **FairICP: 1dim** (blue circles)
- **FDL: 1dim** (red squares)
- **HGR: 1dim** (green crosses)
- **FairICP: 3dim** (blue dashed circles)
- **FDL: 3dim** (red dashed squares)
- **HGR: 3dim** (green dashed crosses)
### Data Series Trends
1. **FairICP: 1dim** (blue circles)
- Starts at [0.00, 0.43] and decreases to [0.30, 0.36]
- Slope: Steep initial decline, flattening at higher KPC
2. **FDL: 1dim** (red squares)
- Starts at [0.00, 0.43] and decreases to [0.30, 0.36]
- Slope: Steeper than FairICP: 1dim, with sharper initial drop
3. **HGR: 1dim** (green crosses)
- Starts at [0.00, 0.43] and decreases to [0.30, 0.36]
- Slope: Gradual decline, consistent with other 1dim series
4. **FairICP: 3dim** (blue dashed circles)
- Starts at [0.00, 0.43] and decreases to [0.30, 0.36]
- Slope: Similar to FairICP: 1dim but with dashed line pattern
5. **FDL: 3dim** (red dashed squares)
- Starts at [0.00, 0.43] and decreases to [0.30, 0.36]
- Slope: Similar to FDL: 1dim but with dashed line pattern
6. **HGR: 3dim** (green dashed crosses)
- Starts at [0.00, 0.43] and decreases to [0.30, 0.36]
- Slope: Similar to HGR: 1dim but with dashed line pattern
## Chart 2: Violation of Equalized Odds (Statistical Power)
### Title
Violation of Equalized Odds: test on statistical power
### Axes
- **X-axis**: Power (range: 0.0 to 1.0)
- **Y-axis**: Loss (range: 0.350 to 0.525)
### Legend
- **Placement**: Upper right corner
- **Entries**:
- **FairICP: 1dim** (blue circles)
- **FDL: 1dim** (red squares)
- **HGR: 1dim** (green crosses)
- **FairICP: 3dim** (blue dashed circles)
- **FDL: 3dim** (red dashed squares)
- **HGR: 3dim** (green dashed crosses)
### Data Series Trends
1. **FairICP: 1dim** (blue circles)
- Starts at [0.0, 0.43] and decreases to [1.0, 0.36]
- Slope: Steep initial decline, flattening at higher power
2. **FDL: 1dim** (red squares)
- Starts at [0.0, 0.43] and decreases to [1.0, 0.36]
- Slope: Steeper than FairICP: 1dim, with sharper initial drop
3. **HGR: 1dim** (green crosses)
- Starts at [0.0, 0.43] and decreases to [1.0, 0.36]
- Slope: Gradual decline, consistent with other 1dim series
4. **FairICP: 3dim** (blue dashed circles)
- Starts at [0.0, 0.43] and decreases to [1.0, 0.36]
- Slope: Similar to FairICP: 1dim but with dashed line pattern
5. **FDL: 3dim** (red dashed squares)
- Starts at [0.0, 0.43] and decreases to [1.0, 0.36]
- Slope: Similar to FDL: 1dim but with dashed line pattern
6. **HGR: 3dim** (green dashed crosses)
- Starts at [0.0, 0.43] and decreases to [1.0, 0.36]
- Slope: Similar to HGR: 1dim but with dashed line pattern
## Key Observations
1. **Consistency Across Charts**:
- All models show decreasing loss with increasing KPC (Chart 1) or Power (Chart 2)
- 3dim variants (dashed lines) generally follow similar trends to their 1dim counterparts but with slightly different slopes
2. **Performance Patterns**:
- FDL models consistently show steeper declines than FairICP/HGR models
- HGR models exhibit the most gradual declines across both metrics
3. **Legend Validation**:
- All legend entries match corresponding line styles and markers
- Color coding remains consistent between charts for equivalent model types
## Technical Notes
- No non-English text detected
- All data points appear to be plotted at integer KPC/Power values (0.00, 0.05, 0.10, etc.)
- Loss values are consistently reported to three decimal places
- No data tables present; all information conveyed through line charts
</details>
Figure 9: Prediction loss and violation of equalized odds (measured by KPC and statistical power ${\mathbb{P}}\{p\text{-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 3 dim $=$ (African American, Hispanic, Asian). The Pareto front for each algorithm is obtained by varying the fairness trade-off parameter.
<details>
<summary>2404.05678v4/x12.png Details</summary>

### Visual Description
# Technical Document Extraction: Violation of Equalized Odds Analysis
## Chart 1: Violation of Equalized Odds (Dependence Measure KPC)
### Spatial Grounding & Component Isolation
- **Legend Position**: Upper left corner
- **Legend Entries**:
- `FairICP`: Blue circles (`●`)
- `HGR`: Green dashed line (`--`)
- `GerryFair`: Purple triangles (`▲`)
### Axis Labels & Scales
- **X-Axis (KPC)**:
- Range: 0.04 → 0.07
- Tick Intervals: 0.01
- **Y-Axis (Loss)**:
- Range: 0.24 → 0.30
- Tick Intervals: 0.02
### Data Series Analysis
1. **FairICP (Blue Circles)**:
- **Trend**: Slight downward slope
- **Data Points**:
- [0.04, 0.24]
- [0.05, 0.23]
- [0.06, 0.23]
- [0.07, 0.23]
2. **HGR (Green Dashed Line)**:
- **Trend**: Sharp initial decline, then plateau
- **Data Points**:
- [0.04, 0.26]
- [0.05, 0.23]
- [0.06, 0.23]
- [0.07, 0.23]
3. **GerryFair (Purple Triangles)**:
- **Trend**: Initial increase, then steep decline
- **Data Points**:
- [0.04, 0.24]
- [0.05, 0.24]
- [0.06, 0.30]
- [0.07, 0.23]
## Chart 2: Violation of Equalized Odds (Power)
### Spatial Grounding & Component Isolation
- **Legend Position**: Upper left corner (identical to Chart 1)
- **Legend Entries**: Same as Chart 1
### Axis Labels & Scales
- **X-Axis (Power)**:
- Range: 0.96 → 1.00
- Tick Intervals: 0.01
- **Y-Axis (Loss)**:
- Range: 0.24 → 0.30
- Tick Intervals: 0.02
### Data Series Analysis
1. **FairICP (Blue Circles)**:
- **Trend**: Gradual decline
- **Data Points**:
- [0.96, 0.24]
- [0.97, 0.23]
- [0.98, 0.23]
- [0.99, 0.23]
- [1.00, 0.23]
2. **HGR (Green Dashed Line)**:
- **Trend**: Linear decline
- **Data Points**:
- [0.96, 0.26]
- [0.97, 0.25]
- [0.98, 0.24]
- [0.99, 0.23]
- [1.00, 0.23]
3. **GerryFair (Purple Triangles)**:
- **Trend**: Stable until x=1.00, then sharp increase
- **Data Points**:
- [0.96, 0.24]
- [0.97, 0.24]
- [0.98, 0.24]
- [0.99, 0.24]
- [1.00, 0.30]
## Cross-Reference Validation
- **Color Consistency**:
- All blue circles (`●`) correspond to `FairICP`
- All green dashed lines (`--`) correspond to `HGR`
- All purple triangles (`▲`) correspond to `GerryFair`
- **Legend Accuracy**: Confirmed 100% alignment with chart data
## Observations
1. **KPC Analysis**:
- GerryFair exhibits extreme volatility (spike at KPC=0.06)
- HGR shows strongest performance (lowest loss at KPC=0.05+)
- FairICP maintains stable performance across KPC range
2. **Power Analysis**:
- GerryFair demonstrates catastrophic failure at maximum power (x=1.00)
- HGR maintains consistent improvement as power increases
- FairICP shows minimal sensitivity to power changes
## Language Declaration
- **Primary Language**: English
- **Secondary Languages**: None detected
</details>
Figure 10: Prediction loss and violation of equalized odds (measured by KPC and statistical power ${\mathbb{P}}\{p\text{-value}<0.05\}$ ) obtained by 3 different training methods in ACS Income data over 100 random splits. The Pareto front for each algorithm is obtained by varying the fairness trade-off parameter.
<details>
<summary>2404.05678v4/x13.png Details</summary>

### Visual Description
# Technical Document Extraction: Violation of Equalized Odds Analysis
## Chart 1: Violation of Equalized Odds (Dependence Measure KPC)
### Axes & Labels
- **X-axis**: KPC (0.005 to 0.035)
- **Y-axis**: Loss (0.180 to 0.210)
- **Title**: "Violation of Equalized Odds: test on dependence measure KPC"
### Legend
| Method | Marker | Color |
|-----------|--------|--------|
| FairICP | Circle | Blue |
| Reduction | Star | Orange |
| HGR | Dashed | Green |
| FDL | Square | Red |
| GerryFair | Triangle | Purple |
### Data Trends
1. **FairICP (Blue Circles)**:
- Starts at ~0.189 (KPC=0.005), decreases steadily to ~0.182 (KPC=0.035).
- Slope: Gradual decline.
2. **Reduction (Orange Stars)**:
- Starts at ~0.190 (KPC=0.005), decreases to ~0.182 (KPC=0.035).
- Slope: Slightly steeper than FairICP.
3. **HGR (Green Dashed Line)**:
- Starts at ~0.190 (KPC=0.005), decreases to ~0.182 (KPC=0.035).
- Slope: Similar to Reduction.
4. **FDL (Red Squares)**:
- Starts at ~0.189 (KPC=0.005), decreases to ~0.182 (KPC=0.035).
- Slope: Consistent with other methods.
5. **GerryFair (Purple Triangles)**:
- Starts at ~0.190 (KPC=0.005), drops sharply to ~0.182 (KPC=0.035).
- Slope: Steep decline at final data point.
## Chart 2: Violation of Equalized Odds (Power)
### Axes & Labels
- **X-axis**: Power (0 to 0.8)
- **Y-axis**: Loss (0.180 to 0.210)
- **Title**: "Violation of Equalized Odds: test on power"
### Legend
Same as Chart 1 (FairICP, Reduction, HGR, FDL, GerryFair).
### Data Trends
1. **FairICP (Blue Circles)**:
- Starts at ~0.188 (Power=0), decreases to ~0.182 (Power=0.8).
- Slope: Gradual decline.
2. **Reduction (Orange Stars)**:
- Starts at ~0.190 (Power=0), decreases to ~0.182 (Power=0.8).
- Slope: Slightly steeper than FairICP.
3. **HGR (Green Dashed Line)**:
- Starts at ~0.190 (Power=0), decreases to ~0.182 (Power=0.8).
- Slope: Similar to Reduction.
4. **FDL (Red Squares)**:
- Starts at ~0.189 (Power=0), decreases to ~0.182 (Power=0.8).
- Slope: Consistent with other methods.
5. **GerryFair (Purple Triangles)**:
- Starts at ~0.190 (Power=0), drops sharply to ~0.182 (Power=0.8).
- Slope: Steep decline at final data point.
## Chart 3: Violation of Equalized Odds (Dependence Measure DEO)
### Axes & Labels
- **X-axis**: DEO (0.1 to 0.5)
- **Y-axis**: Loss (0.180 to 0.210)
- **Title**: "Violation of Equalized Odds: test on dependence measure DEO"
### Legend
Same as Chart 1 (FairICP, Reduction, HGR, FDL, GerryFair).
### Data Trends
1. **FairICP (Blue Circles)**:
- Starts at ~0.189 (DEO=0.1), decreases to ~0.182 (DEO=0.5).
- Slope: Gradual decline.
2. **Reduction (Orange Stars)**:
- Starts at ~0.190 (DEO=0.1), decreases to ~0.182 (DEO=0.5).
- Slope: Slightly steeper than FairICP.
3. **HGR (Green Dashed Line)**:
- Starts at ~0.190 (DEO=0.1), decreases to ~0.182 (DEO=0.5).
- Slope: Similar to Reduction.
4. **FDL (Red Squares)**:
- Starts at ~0.189 (DEO=0.1), decreases to ~0.182 (DEO=0.5).
- Slope: Consistent with other methods.
5. **GerryFair (Purple Triangles)**:
- Starts at ~0.190 (DEO=0.1), drops sharply to ~0.182 (DEO=0.5).
- Slope: Steep decline at final data point.
## Key Observations
1. **Consistency Across Metrics**: All methods show similar loss trends across KPC, Power, and DEO.
2. **GerryFair Anomaly**: The GerryFair method exhibits a sharp drop in loss at the final data point in all charts, suggesting potential overfitting or metric-specific behavior.
3. **FairICP Performance**: FairICP consistently achieves the lowest loss across all metrics, indicating robustness.
## Spatial Grounding
- **Legend Position**: Top-left corner of each chart (exact coordinates not specified in image).
- **Color-Marker Matching**: All legend entries align with their respective data series (e.g., blue circles = FairICP).
## Notes
- No non-English text detected.
- No data tables or heatmaps present.
- All trends are visually consistent with numerical data points.
</details>
Figure 11: Prediction loss and violation of equalized odds (measured by KPC, statistical power ${\mathbb{P}}\{p\text{-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 of GerryFair are out of the graph on the right.
<details>
<summary>2404.05678v4/x14.png Details</summary>

### Visual Description
# Technical Document Extraction: Violation of Equalized Odds Analysis
## Chart 1: Violation of Equalized Odds - test on dependence measure KPC
### Axes & Labels
- **X-axis**: KPC (values: 0.01, 0.02, 0.03, 0.04, 0.05)
- **Y-axis**: Loss (values: 0.34, 0.36, 0.38, 0.40, 0.42, 0.44, 0.46)
- **Title**: "Violation of Equalized Odds: test on dependence measure KPC"
### Legend (Top Right)
| Color | Label |
|-------|-----------|
| Blue | FairICP |
| Orange| Reduction |
| Green | HGR |
| Red | FDL |
| Purple| GerryFair |
### Data Series Trends & Points
1. **FairICP (Blue)**
- Trend: Steady downward slope from left to right
- Points:
- KPC=0.01 → Loss≈0.44
- KPC=0.02 → Loss≈0.42
- KPC=0.03 → Loss≈0.36
- KPC=0.04 → Loss≈0.34
- KPC=0.05 → Loss≈0.34
2. **Reduction (Orange)**
- Trend: Gradual decline with slight curvature
- Points:
- KPC=0.01 → Loss≈0.46
- KPC=0.02 → Loss≈0.44
- KPC=0.03 → Loss≈0.38
- KPC=0.04 → Loss≈0.36
- KPC=0.05 → Loss≈0.34
3. **HGR (Green)**
- Trend: Linear downward trajectory
- Points:
- KPC=0.01 → Loss≈0.46
- KPC=0.02 → Loss≈0.44
- KPC=0.03 → Loss≈0.38
- KPC=0.04 → Loss≈0.36
- KPC=0.05 → Loss≈0.34
4. **FDL (Red)**
- Trend: Sharp initial drop, then flattening
- Points:
- KPC=0.01 → Loss≈0.46
- KPC=0.02 → Loss≈0.44
- KPC=0.03 → Loss≈0.38
- KPC=0.04 → Loss≈0.36
- KPC=0.05 → Loss≈0.34
5. **GerryFair (Purple)**
- Trend: Steep initial decline, then gradual flattening
- Points:
- KPC=0.01 → Loss≈0.46
- KPC=0.02 → Loss≈0.44
- KPC=0.03 → Loss≈0.38
- KPC=0.04 → Loss≈0.36
- KPC=0.05 → Loss≈0.34
---
## Chart 2: Violation of Equalized Odds - test on power
### Axes & Labels
- **X-axis**: Power (values: 0.1, 0.2, 0.3, 0.4)
- **Y-axis**: Loss (values: 0.34, 0.36, 0.38, 0.40, 0.42, 0.44, 0.46)
- **Title**: "Violation of Equalized Odds: test on power"
### Legend (Top Right)
| Color | Label |
|-------|-----------|
| Blue | FairICP |
| Orange| Reduction |
| Green | HGR |
| Red | FDL |
| Purple| GerryFair |
### Data Series Trends & Points
1. **FairICP (Blue)**
- Trend: Consistent downward slope
- Points:
- Power=0.1 → Loss≈0.44
- Power=0.2 → Loss≈0.38
- Power=0.3 → Loss≈0.36
- Power=0.4 → Loss≈0.34
2. **Reduction (Orange)**
- Trend: Gradual decline with curvature
- Points:
- Power=0.1 → Loss≈0.46
- Power=0.2 → Loss≈0.42
- Power=0.3 → Loss≈0.36
- Power=0.4 → Loss≈0.34
3. **HGR (Green)**
- Trend: Linear downward trajectory
- Points:
- Power=0.1 → Loss≈0.46
- Power=0.2 → Loss≈0.40
- Power=0.3 → Loss≈0.36
- Power=0.4 → Loss≈0.34
4. **FDL (Red)**
- Trend: Sharp initial drop, then flattening
- Points:
- Power=0.1 → Loss≈0.46
- Power=0.2 → Loss≈0.40
- Power=0.3 → Loss≈0.36
- Power=0.4 → Loss≈0.34
5. **GerryFair (Purple)**
- Trend: Steep initial decline, then gradual flattening
- Points:
- Power=0.1 → Loss≈0.46
- Power=0.2 → Loss≈0.42
- Power=0.3 → Loss≈0.38
- Power=0.4 → Loss≈0.36
---
## Chart 3: Violation of Equalized Odds - test on dependence measure DEO
### Axes & Labels
- **X-axis**: DEO (values: 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8)
- **Y-axis**: Loss (values: 0.34, 0.36, 0.38, 0.40, 0.42, 0.44, 0.46)
- **Title**: "Violation of Equalized Odds: test on dependence measure DEO"
### Legend (Top Right)
| Color | Label |
|-------|-----------|
| Blue | FairICP |
| Orange| Reduction |
| Green | HGR |
| Red | FDL |
| Purple| GerryFair |
### Data Series Trends & Points
1. **FairICP (Blue)**
- Trend: Steady downward slope
- Points:
- DEO=0.2 → Loss≈0.44
- DEO=0.3 → Loss≈0.40
- DEO=0.4 → Loss≈0.38
- DEO=0.5 → Loss≈0.36
- DEO=0.6 → Loss≈0.36
- DEO=0.7 → Loss≈0.34
- DEO=0.8 → Loss≈0.34
2. **Reduction (Orange)**
- Trend: Gradual decline with curvature
- Points:
- DEO=0.2 → Loss≈0.46
- DEO=0.3 → Loss≈0.44
- DEO=0.4 → Loss≈0.40
- DEO=0.5 → Loss≈0.38
- DEO=0.6 → Loss≈0.36
- DEO=0.7 → Loss≈0.34
- DEO=0.8 → Loss≈0.34
3. **HGR (Green)**
- Trend: Linear downward trajectory
- Points:
- DEO=0.2 → Loss≈0.46
- DEO=0.3 → Loss≈0.44
- DEO=0.4 → Loss≈0.40
- DEO=0.5 → Loss≈0.38
- DEO=0.6 → Loss≈0.36
- DEO=0.7 → Loss≈0.34
- DEO=0.8 → Loss≈0.34
4. **FDL (Red)**
- Trend: Sharp initial drop, then flattening
- Points:
- DEO=0.2 → Loss≈0.46
- DEO=0.3 → Loss≈0.44
- DEO=0.4 → Loss≈0.40
- DEO=0.5 → Loss≈0.38
- DEO=0.6 → Loss≈0.36
- DEO=0.7 → Loss≈0.34
- DEO=0.8 → Loss≈0.34
5. **GerryFair (Purple)**
- Trend: Steep initial decline, then gradual flattening
- Points:
- DEO=0.2 → Loss≈0.46
- DEO=0.3 → Loss≈0.44
- DEO=0.4 → Loss≈0.40
- DEO=0.5 → Loss≈0.38
- DEO=0.6 → Loss≈0.36
- DEO=0.7 → Loss≈0.34
- DEO=0.8 → Loss≈0.34
---
## Key Observations
1. **Consistent Trends**:
- All methods show decreasing loss as dependence measures (KPC, Power, DEO) increase.
- **HGR** consistently follows a linear trajectory across all charts.
- **FDL** and **GerryFair** exhibit sharp initial declines followed by flattening.
2. **Performance Comparison**:
- **FairICP** and **Reduction** show similar performance but with slight curvature differences.
- **GerryFair** demonstrates the steepest initial improvement across all tests.
3. **Axis Ranges**:
- KPC: 0.01–0.05
- Power: 0.1–0.4
- DEO: 0.2–0.8
4. **Legend Placement**:
- All legends are positioned in the **top-right corner** of their respective charts.
---
## Notes
- No non-English text or embedded diagrams were identified.
- All data points were extracted based on visual approximation from the chart grid.
- Color-legend alignment was verified for all series in all charts.
</details>
Figure 12: Prediction loss and violation of equalized odds (measured by KPC, statistical power ${\mathbb{P}}\{p\text{-value}<0.05\}$ and DEO) obtained by 5 different training methods in COMPAS data over 100 random splits. The Pareto front for each algorithm is obtained by varying the fairness trade-off parameter.