Counterfactual Fairness by Combining Factual and Counterfactual Predictions
Authors: Zeyu Zhou
Tianci Liu
Ruqi Bai
Jing Gao
Murat Kocaoglu
David I. Inouye
Venue: NeurIPS 2024 poster (2024)
Keywords: Counterfactual Fairness
Fairness
Trustworthy ML
Primary area: fairness

Abstract: In high-stakes domains such as healthcare and hiring, the role of machine learning (ML) in decision-making raises significant fairness concerns. 
This work focuses on Counterfactual Fairness (CF), which posits that an ML model's outcome on any individual should remain unchanged if they had belonged to a different demographic group.
Previous works have proposed methods that guarantee CF. 
Notwithstanding, their effects on the model's predictive performance remain largely unclear.
To fill this gap, we provide a theoretical study on the inherent trade-off between CF and predictive performance in a model-agnostic manner. 
We first propose a simple but effective method to cast an optimal but potentially unfair predictor into a fair one with a minimal loss of performance.
By analyzing the excess risk incurred by perfect CF, we quantify this inherent trade-off. 
Further analysis on our method's performance with access to only incomplete causal knowledge is also conducted. 
Built upon this, we propose a practical algorithm that can be applied in such scenarios. 
Experiments on both synthetic and semi-synthetic datasets demonstrate the validity of our analysis and methods.

Counterfactual Fairness by Combining Factual and Counterfactual Predictions
Zeyu Zhou, Tianci Liu, Ruqi Bai, Jing Gao, Murat Kocaoglu, David I. Inouye Elmore Family School of Electrical and Computer Engineering Purdue University
(zhou1059, liu3351, bai116, jinggao, mkocaoglu, dinouye) edu
Abstract
In high-stakes domains such as healthcare and hiring, the role of machine learning (ML) in decision-making raises significant fairness concerns. This work focuses Counterfactual Fairness (CF), which posits that an ML model's outcome on any in- dividual should remain unchanged if they had belonged to a different demographic group. Previous works have proposed methods that guarantee CF. Notwithstanding, their effects the model's predictive performance remain largely unclear. To fill this gap, we provide a theoretical study on the inherent trade-off between CF and predictive performance in model-agnostic manner. We first propose a simple but effective method to cast an optimal but potentially unfair predictor into a fair one with minimal performance degradation. By analyzing the excess risk incurred by perfect CF, we quantify this inherent trade-off. Further analysis on our method's 's performance with access only incomplete causal knowledge is also conducted. Built upon this, we propose practical algorithm that can be applied in such sce- narios. Experiments on both synthetic and semi-synthetic datasets demonstrate the validity of our analysis and methods.
1 Introduction
Machine learning (ML) has been widely used in high-stakes domains such as healthcare [Daneshjou et al., 2021], hiring [Hoffman et al., 2018), criminal justice [Brennan et al., 2009], and loan assessment [Khandani al., 2010], bringing with critical ethical and social considerations. example is the bias observed in the COMPAS tool against African Americans in recidivism predictions [Brackey, 2019]. This issue is particularly alarming an era where large-scale deep learning models, commonly trained their extensive reach and impact, amplify the potential for widespread and systemic biases. This increasing awareness underscores the need for ML practitioners to integrate faimess considerations into their work, extending their focus beyond merely maximizing prediction accuracy [Bolukbasi al., 2016, Calders and Verwer, 2010, Dwork al., 2012, Grgic-Hlaca et al., 2016, Hardt al., 2016]. Various fairness notions have been developed, ranging from group-level measures such as group parity [Hardt al., 2016] to individual-level metrics [Dworkk et al., 2012]. Recently, there has been a growing interest in approaches based on causal inference, particularly in understanding the causal effects of sensitive attributes such as gender and age on decision-make -aaiiinnn [Chiappa. 2019, Galhotra et al., 2022, Khademi et al., 2019]. This has led to the proposal of Counterfactual Fairness (CF), which states that prediction for individual in hypothetical scenarios where their sensitive attributes differ should remain unchanged [Kusner et al., 2017]. As an individual- notion agnostic the choice of similarity measure [Kusner al., 2017, Rosenblatt and Witter, 2023], CF has recently
prominent
noisy data from the internet, are increasingly prevalent. Such models, due to
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

am0, y-1
y=1yy]
Pgus PeiimOa 0.5 countarfactuals
(a) Optimal predictor without counterfactual fairness constraint.
(b) Optimal predictor under perfect counterfactual fairness constraint.
Figure 1:
The optimal (unfair) predictor (a) violates counterfactual fairness in the middle region because the predictions
different for the factual-counterfactn pairs' (denoted by line segments between a = 0 and 1). We prove that the optimal fair predictor (b) simply mixes the optimal unfair predictions the factual and counterfactual points (i.e., mixes the predictions at both endpoints of the line). This mixing incurs the inherent excess risk associated with counterfactual fairness. Colors represent target classes (Y), and dot styles represent sensitive attributes (A).
gained traction [Anthis and Veitch, 2024, Nilforoshan et al., 2022, Makhlouf et al., 2022, Rosenblatt and Witter, 2023].
To achieve CF, Kusner et al. [2017] first proposed naive solution, suggesting that predictions should only use non-descendants of the sensitive attribute in causal graph. This approach only requires causal topological ordering of variables and achieves perfect CF by construction. However, limits the available features for downstream tasks and could be inapplicable in certain cases [Kusner et al., 2017]. For relaxation, they further proposed an algorithm that leverages latent variables. Extending this line of work, Zuo et al. [2023] introduced technique that incorporates additional information by mixing factual and counterfactual samples. Although perfect CF has been established in their work, its predictiveness degraded, and whether the predictive power can be improved remains unknown. In parallel to this, another branch of research employed regularization and augmentation to encourage CF [Garg et al., 2019, Stefano al., 2020, Kim et al., 2021]. However, these methods cannot guarantee perfect CF, analyzing the optimal predictive performance under CF constraints is highly challenging.
To theoretically understand the tradeoff between CF and ML performance, we consider a class of invertible causal models and prove that the optimal solution under perfect Counterfactual Fairness (CF) has a simple form w.r.t. to the Bayes optimal classifier and explicitly quantify the excess risk of imposing perfect CF constraint as has been done for non-causal fairness notions[Zhao and Gordon, 2022, Xian et al., 2023]. The optimal predictor under the fairness constraint can be achieved by combining factual and counterfactual predictions using (potentially unfair) optimal predictor. Next, we quantify the excess risk between the optimal predictor with and without CF constraints. This quantity sheds light on the best possible model, in terms of predictive performance, under the stringent notion of perfect CF. Our results are illustrated in Figure 1. To consider scenarios with incomplete causal knowledge (e.g. unknown causal graph model), further study the CF and predictive performance degradation caused by imperfect counterfactual estimations. Inspired by theoretical findings, we propose plugin method that leverages (potentially unfair) pretrained model to achieve a better tradcoff of faimess and predictive performance than the prior methods. Furthermore, we propose method improve the pretrained model that accounts for counterfactual estimation errors and can achieve good empirical performance even with limited causal knowledge. We summarize our contributions as follows:
1. We propose CF method that is provably optimal in terms of predictive performance under perfect CF.
2. To the best of our knowledge, we are the first characterize the inherent trade-off of CF and ML performance, which applies to all CF methods.
3. We investigate the CF and predictive performance degradation from estimation error resulting from limited causal knowledge and propose methods to mitigate estimation errors in practice.
4. We empirically demonstrate that our proposed CF methods outperform existing methods in both full and incomplete causal knowledge settings 2.
Because of our invertibility assumption. any factual point has a unique counterfacttal.
Code be found in https://github.c http:://gihub..oo/moony.cco com/inouee-lla/pppf

---

Figure Causal graph. A represents sensitive at- tribute, Y represents the target variable, U repre- sents latent confounders, X represents observed features. Note that the validity of theoreti- cal analysis holds for all causal models that isfy the condition given by Assumption 3.1. 1. It is 2 Preliminaries
Notation We use capital letters to represent random variables and lowercase letters represent the realizations of random variables. Now we define a few variables that will be considered in this work. represents the sensitive attribute of an individual (e.g., gender), Y represents the target variable to predict, X represents observed features other than A and Y, and U represents unobserved confounding variables which are caused by any observed variables while a, y, æ, represent their realization respectively.
Counterfactual In this work, we use the framework of Structural Causal Models (SCMs) [Pearl, 2009]. A SCM is a triplet M = (U, V, where U represents exogenous variables (factors outside the model), V represents endogenous variables, and F contains and Parent(V;) to V, A counterfactual query asks question like: what would the value of Y be if had taken a different value given certain observations? For example, given that person is a woman and given everything we observe about her performance in an interview, what is the probability of her getting the job if she had been man? More formally, given a SCM, counterfactual query can be written P(Y, P(YA=al W w). Here W is the evidence and A = a in the subscript represents the intervention on A. For the general procedure to estimate counterfactuals, please refer Pearl [2009].
functions that map from Uj
Counterfactual Fairness Built upon the framework above, we focus on Counterfactual Fairness (CF), which requires the predictors to fair among factual and counterfactual samples. More formally, it is defined as below
A
U
Y
Definition 2.1. (Counterfactual Fairness) We say predictor Ý is coun- terfactually fair if
p( A=a =
2, =
V(z
x
This definition states that intervention A should not affect the distri- bution of Y. Using the same example above, the probability of woman getting the job should the same as that if she had been man. For that goal, we use the following metric evaluate CF
Definition 2.2. (Total Effect) The Total Effect (TE) of a predictor Ý is
TE EljLA= I]=
Therefore, predictor is counterfactually fair if and only if TE 0. Throughout the paper, we use TE to quantify the violation of counterfac- tual faimess.
not restricted to this spe- cific graph.
3 Counterfactual Fairness via Output Combination
3.1 Problem Setup
We assume that all data we have is generated by causal model [Pearl. 2009], and we consider the representative causal graph shown Figure that has been widely adopted in the faimess literature [Grari al., 2023, Kusner et al., 2017, Zuo et al., 2023]. Our analysis is presented based on binary A E {0, 1} given its pivotal importance the literature [Pessach and Shmueli, 2023] and for the sake of presentation clearness, but our analysis and our method can be naturally extended to multi-class A. We first state the main assumptions needed in this section.
Assumption 3.1.
1. A and U are independent of each other.
2. The mapping between X and U is invertible given A.
The first assumption is very common the fairness literature. While the invertibility assumption might be restrictive in certain scenarios, it simplifies the theoretical analysis and has been adopted in

---

recent works on counterfactual estimation that exact invertibility is not required in practice but rather only strong mutual information between X and U given A would be sufficient. Further, we empirically validate the effectiveness of our method after relaxing invertibility the experiment section. To facilitate our discussion, we first define Fx as the mapping between X and (U, A), i.e., X = Fx A). According to our second assumption, Fx(,a) a) is invertible function, i.e., 3fx -, . (xr This assumption simplifies the counterfactual estimation of X for different values of A into a deterministic function. In our context, the counterfactual query is specifically p(Xxr1X = A a). which simplifies to a Dirac delta at a single value given the invertibility assumption. Thus, we introduce the concept of deterministic counterfactual generating mechanism (CGM), denoted as Te' = G(I, a, a'): ). Also, in our case, we will assume A is binary so that a and it's counterfactual a' can be written
et al., 2023, Zhou et al., 2024]. We expect
(I, a) Fx - (u, a), a) = u. V(z, a).
All proofs can be found in Appendix A. Given this setup, the following lemma characterizes the perfect CF constraint on Φ.
Lemma 3.2. Given Assumption 3.1, predictor on (X is counterfactually fair and only if the
predictor returns the same value for a sample and its counterfactuals, i.e., TE(Φ) 0 + ő(2 a) a.z
6(11-a, 1-aa a), V(z,a) a).
The proof is straightforward from the definition of TE. Notably, this lemma helps disambiguate the question of whether counterfactual fairness is a distribution- or individual-level requirements as raised in Plecko and Bareinboim [2022]. In our setup, they are equivalent due to invertibility between X
and U given A.
3.2 Optimal Counterfactual Fairness and Inherent Trade-off'
Given the complete knowledge of the causal model, it is viable to satisfy the perfect CF constraint [Kusner et al., 2017, Zuo et al., 2023]. However, these methods are known to result in empirical degradation of ML models' performance, raising critical concerns about the fairess-utility trade-offs. Moreover, it is still unknown to what extent the ML model performance has be affected in order to achieve perfect CF. In this section we provide a formal study on this to close the gap. Our solution consists of two steps. First, we propose a simple yet effective method that is provably optimal under the constraint of perfect CF. Next, we characterize the inherent trade-off between CF and predictive performance by checking the excess risk compared to a Bayes optimal (unfair) predictor. Our result shows that the inherent trade-off is dominated by the dependency between Y and A, echoing previous analysis on non-causal based fairness notions [Chzhen et al., 2020, Xian et al., 2023]. For brevity, we refer to Bayes optimal predictor as "optimal", and model that satisfies perfect CF as "fair".
We start with the following theorem instantiating an optimal and fair predictor.
Theorem 3.3. Given Assumption 3.1² 3 and loss (i.e., squared L2 loss for regression tasks, and cross cross-entropy loss for classification tasks), an optimal and fair predictor (i.e., the best possible model(s) under the constraint of perfect CF) is given by the average of the optimal (potentially unfair) predictions on itself and all possible counterfactuals:
Φcr a) 2 ((p((=)))) (x, (II-a, (0 1-a) E argmin E))()(X,AA,,))
(:TR())=
where -1-a = a*, 1 is the counterfactual of (xx,a) when intervening with A = 1 - and 6" (x, a) is unconstrained optimal predictor, i.e., 6² (x, a) A argming B[((o(X, A), Y)] B|Y|X=r, xx, a=a..
This result suggests that, if we have to access ground truth counterfactuals, simple algorithm using a (potentially) unfair model could achieve strong fairness and accuracy. Built upon the above result, we are ready characterize the inherent trade-off between CF and model performance by the following theorem.
Theorem 3.4.
The inherent trade-off between CF and predictive performance, characterized by the excess risk of the Bayes optimal predictor under the CF constraint, is given by
R = - (TEy - FyIu==,A=--- V7)
*Note that while the discussion in this paper focuses on the causal model in Figure 2, our theorem is valid for more general cases that satisfy Assumption 1. And for brevity, the following discussion is done under this assumption unless otherwise stated.

---

for regression tasks using squared L2 loss where J denotes the variance of A; and
RCcr R² I(A:Y UU),
for classification tasks using cross-entropy loss.
Remarkably, the excess risks are completely characterized by the inherent dependency between Y and A determined by the underlying causal mechanism, similar to non-causal based group fairness [Chzhen et al., 2020, Xian et al., 2023]. Moreover, they lower bound the excess risk of all possible predictors in order achieve perfect CF.
3.3 Method with Incomplete Causal Knowledge
In this section, we aim to address CF in the scenario where causal knowledge is limited. Inspired by Theorem 3.3, we first present simple plugin method as summarized Algorithm 1. For regression tasks, á is the final output, and for classification tasks, f represents the probability of Y 1, i.e., p(Y 1|x = x, A a) E z, a). is noteworthy that PCF is agnostic to the training of predictor ø that can be determined by the user freely. In fact, with access to the oracle CGM G", then PCF would achieve perfect CF as proved in the next result.
Algorithm Plug-in Counterfactual Fairness (PCF)
Pretrained probabilistic prediction predictor á X' x A + V, CGM G, test datapoint (x, a), prior distribution p of A
Input:
Output: Predicted output ft -1 f- Gz a,
á + p(A = a))(x, a) p(A = 1- - (-)
Proposition 3.5. Given that G is the ground truth counterfactual generating mechanism, i.e., G(I,a,a')) = xa', V(I, a, d'), Algorithm 1 achieves perfect CF for any pretrained predictor ó.
Note that this proposition only requires access to ground truth G and holds valid for any pretrained predictor d. If á is further accurate, then the corresponding PCF is able achieve high accuracy as well, which is empirically validated in the experiments.
3.3.1 Given estimated G
Acquiring counterfactuals in practice can be challenging task and could lead to estimation errors. In this section we provide theoretical analysis on this. Specifically, the theorem below bounds the TE and excess risk due the use of estimated counterfactuals.
Theorem 3.6. Given an optimal predictor o² (z, a), suppose it is L-lipschitz continuous æ, and the counterfactual estimation enror is bounded, i.e.
max || (Za, - - a, a))2 X.
for some 2 O, where G and & represent the ground truth and estimated CGMs respectively. Then, the total effect (TE) of Algorithm based G is bounded by Ls. Moreover, for squared L2 loss, the excess risk bounded by o² L²22 + 20 LeEy [EE U = u, A = E U u, A= O]] and for cross-entropy loss the excess risk is bounded by T.c.
Note that a and Ey E U u, A= I u, A= 0]] are inherent characteristic of the underlying mechanism and is independent of the counterfactual estimation. This suggests that if the counterfactuals are not too far away and d² is smooth, then faimess and prediction performance will not be significantly affected. In practice, CGM in Algorithm I can be obtained using counterfactual estimation methods, as discussed in Section
'err assume the logits L-lipschitz continuous in
5

---

3.3.2 Given estimated G and Ø
In the previous section, we discussed how counterfactual estimation error directly impacts the performance of PCF in terms of CF and predictive performance. Here, we consider the situation where & also needs to be estimated. We first note that the degradation in fairness remains the same as previous result
Remark 3.7. The bound TE
TE given & and follows that in Theorem 3.6.
The proof is straightforward since the original proof in Theorem 3.6 does not use any characteristic of optimality. To achieve good predictive performance, natural approach is to train on the observed data via Empirical Risk Minimization (ERM), which should fit the predictor well given sufficient samples and reasonable predictor class. However, ERM can only approximate Bayes optimality within the support of the training data. Outside this support, its performance can deteriorate signifi- cantly, as extensively studied in areas such as Domain Adaptation [Farahani et al., 2021] and Domain Generalization [Zhou et al., 2022a]. Consequently, when integrated with an approximate G. we may encounter the issue where p(XA==1a A = a) * p(X|A = 1 - a). inducing a distribution shift problem (Note that these would be equal given the graph in Figure and Pearl's rules) [Kulinski and Inouye, 2023]. To mitigate this, we suggest improving é on the estimated counterfactual distribution. More formally we define the following objective called Counterfactual Risk Minimization (CRM):
min Ex.. Y) (( A,1 -)) A))
This can be achieved either by augmenting the original training dataset or by fine-tuning with estimated counterfactual samples. The choice between training from scratch or fine-tur tne-tuning depends on the scale of the experiment and computational constraints. It is important to note that the Y corresponding to the estimated counterfactual should remain the same with that of the factual samples. While the optimal prediction for the counterfactual may differ from that of the original data, under the constraint of perfect CF, a predictor required to predict the same outcome to counterfactual pairs. Hence, the optimal solution will change. This is exactly what causes the excess risk we characterized in Theorem 3.4. Furthermore, we can prove that, given the ground truth G. CRM yields the same optimal solution as PCF. Since this result is dependent on the ground truth G, we provide a more formal statement in Appendix B to ensure consistency.
In summarry this section discusses how to improve the estimation of & under counterfactual estimation error. We propose using data augmentation or fine-tuning based on practical scenarios. Additionally, in domains with abundant off-the-shed pre-trained models [Bommasani et al., 2021]. we can potentially avoid this issue by using these models as good proxy for sb
Related Works
Fairness Notions Fair Machine Learning has accumulated a vast literature that proposes various notions to measure fairness issues of machine learning models. Representative fairness notions can be categorized into three classes. Group fairness, such as demographic parity [Pedreshi et al., 2008] and equalized odds [Hardt et al., 2016), requires certain group-level statistical independence between model predictions and individuals' demographic information. Despite its conceptual simplicity. group fairness is known for ruling out perfect model performance [Hardt et al., 2016] and may allow for bias against certain individuals (Corbett-Davins et al., 2023]. Individual fairness [Dwork et al., 2012), on the other hand, asks a model to treat similar individuals similarly. However, determining the similarity between different individuals is often highly task-specific and open-ended. Recently, counterfactual fairness (CF, Kusner et al. [2017]) further takes the causal relationship of data attributes into consideration when measuring fairness. In words, counterfactual fairness proposes that a model should treat any individual the same their counterfactual if the individual had been from another demographic group. As an individual-level notion agnostic to the choice of similarity measure [Kusner et al., 2017], CF has recently gained traction [Wu et al., 2019, Nilforoshan et al., 2022, Makhlouf et al., 2022, Rosenblatt and Witter, 2023]. Motivated by these recent advances, in this work, focus the counterfactual faimess.
Methods for Fairness Given an unfair dataset, attempts to achieve fairness fall into three categories. Pre Pre-processing cleans the data before running machine learning models on it, typically by resampling

---

samples or removing undesired attributes [Kamiran and Calders, 2012]. In- in-processing intervenes the model-training process by incorporating fairness constraints [Zafar et al., 2017, Donini et al., 2018, Lohaus et al., 2020] or penalties [Mohler et al., 201 8, Scutari et al., 2021, Liu et al., 2023]. Post- processing adjusts the raw model outputs to close the bias gap by, e-g., assigning each demographic group a unique decision threshold [Jang et al., 2022]. Post-processing has been favored as an efficient and practical solution because does not require retraining the original model [Petersen et al., 2021, Xian et al., 2023]. To achieve CF, Kusner et al. [2017] applied pre-processing and discarded all descendants of the sensitive feature. Chen et al. [2024] pre-processed the data via orthogonalization and marginal distribution mapping. Garg et al. [2019], Stefano et al. [2020], Kim et al. [2021] in- in-prceessed the model training by penalizing CF violations but their solutions lack formal CF guarantees and often contain unsatisfactory bias after the intervention [Zuo et al., 2023]. Recently, Zuo et al. [2023] proposed another in-processing based solution that is capable of achieving perfect CF and better performance via mixing features. Ma al. [2023] leveraged mediators estimated by Generative Adversarial Networks and provided a theoretical guarantee of CF under well-estimated counterfactuals, However, it is unclear whether their methods optimal. Wang et al. [2023] leveraged predictor that satisfies equal counterfactual opportunity criterion to construct a counterfactually fair predictor. While they provide results on optimality, their findings assume an ideal setting where non-sensitive features are independent of sensitive features.
Inherent Trade-off between Fairness and Predictiveness Machine learning models are known to suffer from performance drops after fairness interventions [Hardt et al., 2016, Menon and Williamson, 2018, Chen et al., 2018], which is known as the fairness-utilly trade-offs. Recently. inherent trade-offs towards non-causal based fairness such as demographie parity (DP) has been established separately for regression [Chzhen et al., 2020] and classification tasks [Xian et al., 2023]. The excess risks are characterized by certain distribution distance (i.e., Wasserstein-2 barycenter for regression, and total-variation or Wasserstein-1 I barycenter for noiseless or noisy classification) between the conditional distribution of Y given A. A similar trade-off between CF and predictiveness has also been empirically observed [Zuo al., 2023]. Nonetheless, their inherent trade-off remains an open question. In this work we take the first step towards this goal and provide a quantitative analysis in both complete and incomplete causal knowledge settings as presented in Section 3. We hope our work sheds light on future works towards more effective CF.
5 Experiments
In this section, we validate our theorems and the effectiveness of our algorithms through experiments on synthetic and semi-synthetic datasets. On synthetic datasets, we focus on validating our theorems in settings where our assumptions hold. On semi-synthetic datasets, we aim to assess the effectiveness of our methods in more practical scenarios, where limited causal knowledge is available and the invertibility assumption is relaxed.
Metrics We consider two metries in this paper: Error and Total Effect (TE). The former eval- uates whether each method can achieve its goal. irrespective of fairness. This is important be- cause we can achieve perfect Counterfactual Fairness by always outputting fixed prediction given whatever input, but that is not useful at all. The latter is a common metric to evaluate Counter- factual Fairness [Kim et al., 2021, Zuo al., 2023]. Given a test set Diest, Error defined as Error 1
|Diell ExtED.... ((((z()) y ()) where (( is the ground truth target, ((x(0) is the predic-
tion of (0,), and depends on the task. TE is defined TE Paal ExwEpa (7)x(0) 7
where Ø1-a is the ground truth counterfactual corresponding to (01) Since only consider bi- nary sensitive attribute, we further define TEp Tee Eie (+(( (a(2_a) and (i)
TE [(o E (0(x(t)) Ma -o-a-a a>)l to evaluate Counterfactual Fairness for different
group respectively.
Methods In general, we consider the following methods: (1) Empirical Risk Minimization (ERM): Train a classifier on features without any fairness consideration. Specifically y Ma, a), where represents the predictor. (2) Counterfactual Fairness with U (CFU) [Kusner et al., 2017]: To achieve Counterfactual Fairness, CFU proposes to use U for prediction. Specifically. y Φ(u). (3) Counterfactual Fairness with fair representation (CFR) [Zuo et al., 2023]: CFR
7

---

proposes to use U and a symmetric version of z, -. Specifically, 9 = 6( b u). (4) Equal
Counterfactual Opportunity Wang et al., 2023]: An ECO predictor adjusted to become counterfactually fair. Specifically, p(a) [p(p)p(aj)))) (p(a) a) + (1 p(a))
a)] + (1
p(a))((1 p(a))
a) + (((a)((11-a>) a)] (5) PCF: As introduced in Algorithm 1, PCF
mixes the output of factual and counterfactual prediction. Specifically, ú = p(a))(x, a) + (1 p(a)))(z1=e 1-a] a). (6) PCF with analytic solution (PCF-Ana): In synthetic experiments, instead of training via ERM, we can directly acquire bayes optimal á in closed-form. Detailed can be found in Appendix C.2. (7) PCF with CRM (PCF-CRM): As discussed Section 3.3, it could be hard to get the optimal predictor when there is counterfactual estimation error. Here due the scale of our experiment, we augment the dataset with estimated counterfactuals rather than finetuning. Specifically, is trained via ERM on the dataset D (x(1) y0) a J U (01-a' y(),, 1 a ) 1 (0
5.1 Synthetic Dataset
In this section, we consider two regression synthetic datasets and two classification tasks where all of assumptions in Assumption 3.1 are satisfied. The regression tasks are as below
Linear-Reg
Cubic-Reg
A Bernoull(ppa): Ny
A Bernoulli(pA), N( ~((0,)
X WAA+ + WpU
X WAA + woU
Y = wx.X + w'U + WyEy
Y wx + whU + wYrr
The classification tasks take the same form except Y ~ Bernoulli (wxx u/ wyey) and Y ~ Bermoulli(a(wxy) X3 + w/y wy )) for Linear-Cls and Cubic- CCss respectively. More details could be found in Appendix C.1. Results averaged over different runs where the structural model kept the same but data resampled. All results shown the main paper use KNN based predictor. Results with other predictors can be found in Appendix D.
Optimality of PCF given true counterfactuals We first test different methods in situations where all methods have access to ground truth counterfactuals and U as needed. In Figure we observe that while CFE, CFR and PCF all achieve perfect CF, PCF has lowest predictor error. This validates Theorem 3.3 regarding the optimality of PCF under the constraint of CF. Furthermore, since here ERM can get solution close to optimal predictor (this indicates the plugin e used by PCF is also close to being optimal), we can also observe the inherent fairness-utility trade-off discussed in Theorem 3.4.
325
0.255
0.300
CRA
CPU
1.8
3.0
0225
0.055
ERM
3 111
2.5
200
0.000
225
1.4
2.00
240
112
1.90
0230
0.765
0.
0.2
0.5
69
89 07
72
(a) Linear-Reg
(b) Cubic-Rey
(c) Linear-Cls
(d) Cubic-Cls
Figure 3: Results on synthetic datasets given ground truth counterfactuals.
Performance under controllable error Here we investigate a more practical scenario where both counterfactuals and U need to be estimated. To investigate how error and TE changes with counterfactual estimation error in a more controllable way and investigate, we simulate the estimation error by adding gaussian noise. Specifically, &.. = Ia' + e and â = u + e where e ~ A a). In Figure 4, we observe that while the fairness and ML performance (especially faireess) of CFE, CFR and PCF tends to get worse as error gets more significant, PCF remains best for all noise level.
Investigating source of error Here we further investigate what could be source of error in the previous scenario. As discussed in Section 3.3.2, in practice, two things in Theorem 3.3 break down:
Essentially PCF with ERM (PCF-ERM) For brevity, just call PCF.
8

---

35
6270
30
1.2
0.20)
60
6,21
0.8b
00200
20300
1.4
6243
010
DT
0.33
1.5
0.00
0.30
6 90
(a) sinear-Reg
(b) Cubic-Reg
(c) Linear-Cls
(d) Cubic-Cls
Figure 4: Results synthetic datasets under counterfactual estimation error. Different color repre- sents different a indicating the standard deviation of the error (c (0, a)) while shape represents different algorithms. Results with different be found in Appendix D.
3.30
0,255
1.000
St
8.0
0.19
93224
0.345
3.30
00172
inothed
PLP
3118
0:25
0160
6220
6
6 PP 6 Ph,
(a) Linear-Reg
Cubic-Reg
Linear-Cls
Cubic-Cls
Figure 5: Results on synthetic datasets comparing PCF and PCF-Analytic. Different color represents different a indicating the standard deviation the error (0, a:)) while shape represents different algorithms. Results with different can be found in Appendix D.
access to Bayes optimal classifier and ground truth counterfactuals. In Figure 5, observe that PCF-Anale PCF-Analytic tends be more robust against counterfactual estimation error than PCF We argue this is because & used in PCF is not trained well on the estimated counterfactual distribution.
5.2 Semi-synthetic Dataset
In this section, consider Law School Success dataset [Wightman, 1998] where the sensitive attribute is gender and the target is first-year grade.. The main goal of this experiment is to validate the effectiveness of our methods in more practical scenarios where limited causal knowledge is available and the invertibility assumption is relaxed.
To compute TE, need access to ground truth counterfactuals. Hence we train generative model on real dataset to generate semi-synthetic dataset following the method in Zuo et al. [2023]. We want to emphasize that counterfactuals hidden from downstream models and used for the evaluation of TE only. This way, we get access to the ground truth u" and can generate ground
1.700
lemb
0.0
1.065
0.2
0.4
1.055
0.6
0.8
1.000
1.0
1045
method
CFR
1.035
ECOCF
0.300
0.325
0.350
0.375
0.400
0.425
0.450
0.475
0.500
Ze
PCF-CRM
Figure 6: Results on Sim-Law with estimated counterfatuals. The predictor a MLP regressor. We also test the convex combination of each algorithm and ERM. For example, PCF-CRM with À means ÿ = AjpCF-CRM (1 A) This suggests that PCF-CRM can achieve lower Error given the same TE and lower TE given the same Error.

---

truth counterfactuals without any error. In our investigation, exogenous noise, factual data and counterfactual data are all actually the simulated version of original datasets. However they do follow a fixed data generating mechanism that is close to the real data. More details could be found in Appendix C. 1. All experiments are repeated 5 times on the same semi-synthetic dataset.
Results In Figure 6, we observe that PCF-CRM achieves better CF and lower Error in comparison to CFU and CFR. This validates our improvement Section 3.3.2 indeed leads to more practical algorithm. Results on comparing PCF and PCF-CRM can be found in Appendix D, which further justifies this. While ERM could achieve lower error, has worst fairness. This is inevitably determined by the inherent trade-off discussed in Theorem 3.4. Furthermore, inspired by the trade-off, we test the result of mixing all predictors with ERM. The curve shows that PCF-CRM remains optimal given fixed CF and best CF given fixed error. This demonstrates again that PCF-CRM is the best among all methods.
6 Conclusion and Discussion
Conclusion In this work, we conducted a formal investigation of the trade-off between Counterfac- tual Faimess (CF) and predictive performance. We proved that combining factual and counterfactual predictions with potentially unfair, optimal predictor achieves optimal CF. Additionally, we de- rived the excess risk between predictors with and without CF constraints, quantifying the minimum performance degradation necessary to ensure perfect CF. To address incomplete causal knowledge, analyzed the effects of imperfect counterfactual estimations on CF and predictive performance. We proposed a plugin approach that leverages pre-traine pre-trained models for optimal fair prediction and developed a practical method to mitigate estimation errors.
Despite the theoretical contributions of our method, two limitations may impact practical applicability: (1) access to ground-truth counterfactuals and (2) access to Bayes optimal predictors. Below, we delve into these limitations, clarifying how our methods can be practically applied and how they can benefit from contributions from the broader community. We hope this discussion will also inspire future research directions.
Access to ground truth counterfactuals While how to better estimate counterfactuals is out of the scope of this work, it is indeed an unavoidable challenge faced by the community of Counterfactual Fairness. It not only limits the deployment of CF algorithms, but also leads to difficulty in validating proposed CF methods. While counterfactual data can be obtained in specific scenarios, such as through randomized controlled trials, it is challenging to acquire in most applications. There are some works in the field of causality that aims at estimating counterfactuals. For instance, Eafa-as et al. [2023] proves counterfactual identifiability under certain causal graphs. However, in more general scenarios, such causal knowledge may be lacking and identifying the causal graph itself can be challenging. These tasks have been well studied in the field of causal discovery [Chickering, 2002, Colombo et al., 2014] and causal representation learning [Schölkopf et al., 2021]. Solutions to this problem typically rely on strong assumptions, such as the linearity of Structural Causal Models (SCMs) or additive noise [Shimizu et al., 2006, Hoyer et al., 2008, Peters et al., 2014]. More recently, Zhou al. [2024] propose a method of estimating counterfactuals without the need identify the causal model or graph. We believe this approach to direct counterfactual estimation could have the potential to be a good plugin counnterfactual estimator in our algorithm. Additionally, generative models could also be used to generate samples as if they had come from a different sensitive attribute [Choi et al., 2018, Zhou et al., 2022b, 2023, Rombach et al., 2022]. These methods often offer the advantage of higher sample quality, especially in modalities such as images or natural language. However, they must be applied with considerable care, as they generally lack integration with the causal model and may introduce significant estimation errors.
Access Bayes optimal predictors Another crucial plugin estimator of our method is the optimal predictor. In classical ML settings, achieving good estimator for the counterfactual distribution often requires retraining or fine-tuning. However, in this era, with the abundance of pre- pre-trained models, such as foundation models [Bommasani et al., 2021], it could be much easier to get predictor that close to being optimal. Rather, given that these models are trained on noisy internet data and have extensive reach and impact, it is of great importance to find effective ways to debias them. We propose that our plugin algorithm could be suitable solution due to post-processing nature, which avoids incurring significant computational costs.
10

---

Acknowledgement
Z.Z., R.B., and D.I. acknowledge support from NSF (IIS-2212097.. ARL (W911NF-2020221) and ONR NN00014-33-C-1060, M.K. acknowledges support from NSF CAREER 2239375, IIS 2348717, Amazon Research Award and Adobe Research. T.L. and J.G. acknowledge support from NSF-IIS2226108. Any opinions, findings, and conclusions recommendations expressed in this material are those the author(s) and do not necessarily reflect the views any funding source.
References
Jacy Anthis and Victor Veitch. Causal context connects counterfactual fairness robust prediction and group fairness. Advances in Neural Information Processing Systems, 36, 2024.
Arthur Asuncion, David Newman, al. Uci machine learning repository, 2007.
Tolga Bolukbasi, Kai-Wei Chang, James Y Zou, Venkatesh Saligrama, and Adam T Kalai. Man is to computer programmer as woman is to homemaker? debiasing word embeddings. Advances in neural information processing systems, 29, 2016.
Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. On the opportuni- ties and risks of foundation models. arXiv preprint arXiv:2108.07255 2021.
Adrienne Brackey. Analysis of Racial Bias in Northpointe's 's COMPAS Algorithm. PhD thesis, Tulane University School of Science and Engineering, 2019.
Tim Brennan, William Dieterich, and Beate Ehret. Evaluating the predictive validity of the compas risk and needs assessment system. Criminal Justice and behavior, 36(1):21-40, 2009.
Toon Calders and Sicco Verwer. Three naive bayes approaches for discrimination-fres classification. Data mining and knowledge discovery, 21:277-292, 2010.
Haoyu Chen, Wenbin Lu, Rui Song, and Pulak Ghosh. On learning and testing of counterfactual fairness through data preprocessing. Journal of the American Statistical Association, 119(546): 1286-1296, 2024.
Irene Chen, Fredrik D Johansson, and David Sontag. Why is my classifier discriminatory? Advances in neural information processing systems, 31, 2018.
Silvia Chiappa. Path-specific counterfactual fairness. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 7801-7808, 2019.
David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 3(N0v)5507-554, 2002.
Yunjey Choi, Minje Choi, Munyoung Kim, Jung- Woo Ha, Sunghun Kim, and Jaegul Choo. Star- gan: Unified generative adversarial networks for multi-domain image-to-image translation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8789-8797, 2018.
Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. Fair regression with wasserstein barycenters. Advances Neural Information Processing Systems, 33:
7321-7331, 2020.
Diego Colombo, Marloes H Maathuis, et al. Order-independent constraint-bart causal structure learning. J. Mach. Learn. Res,, 15(1):3741-3782, 2014.
Sam Corbett-Davies, Johann D Gaebler, Hamed Nilforoshan, Ravi Shroff, and Sharad Goel. The measure and mismeasure fairness. The Journal of Machine Learning Research, 24(1):14730- 14846, 2023.

---

Roxana Daneshjou, Kailas Vodrahalli, Weixin Liang. Roberto A Novoa, Melissa Jenkins, Veronica Rotemberg, Justin Ko, Susan M Swetter, Elizabeth E Bailey, Olivier Gevaert, al. Disparities in dermatology ai: assessments using diverse clinical images. arXiv preprint arXiv:21 1.08006, 2021.
Michele Donini, Luca Oneto, Shai Ben-David, John $ Shawe-Taylor, and Massimiliano Pontil. Empirical risk minimization under fairness constraints. Advances in neural information processing systems, 31, 2018.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214-226, 2012.
Abolfazl Farahani, Sahar Voghoei, Khaled Rasheed, and Hamid R Arabnia. A brief review of domain adaptation. Advances in data science and information engineering: proceedings from ICDATA 2020 and IKE 2020, pages 877-894, 2021.
Sainyam Galhotra, Karthikeyan Shanmugam, Prasanna Sattigeri, and Kush R Varshney, Causal feature selection for algorithmic fairness. In Proceedings of the 2022 International Conference on Management of Data, pages 276-285, 2022.
Sahaj Garg, Vincent Perot, Nicole Limtiaco, Ankur Taly, Ed H. Chi, and Alex Beutel, Counterfactual fairness in text classification through robustness. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, AIES 20/9, Honolulu, HI, USA, January 27-28, 2019, pages 219-226, 2019.
Vincent Grari, Sylvain Lamprier, and Marcin Detyniecki. Adversarial learning for counterfactual faimesss. Mach. Learn., 1 112(3);411-63, 2023, doi: 10.1007/5100944022-00622 https://doi http:////oooog///...// 1007 / /119994-199999 022 06206-8.
URL
Nina Grgic-Hlaca, Muhammad Bilal Zafar, Krishna P Gummadi, and Adrian Weller. The case for process fairness in learning: Feature selection for fair decision making. In NIPS symposium on machine learning and the law, volume 1, page 11. Barcelona, Spain, 2016.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
Mitchell Hoffman, Lisa Kahn, and Danielle Li. Discretion in hiring. The Quarterly Journal of Economics, 133(2):765-88)) 800, 2018.
Patrik Hoyer, Dominik Janzing, Joris M Mooij. Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models. Advances neural information processing systems, 21, 2008
Taeuk Jang, Pengyi Shi, and Xianqian Wang. Group-aware threshold adaptation for fair classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 6988-6995, 2022.
Faisal Kamiran and Toon Calders. Data preprocessing techniques for classification without discrimi- nation. Knowledge and information systems, 33(1):1-33, 2012.
Aria Khademi, Sanghack Lee, David Foley, and Vasant Honavar. Fairness in algorithmic decision making: An excursion through the lens of causality. In The World Wide Web Conference, pages 2907-2914, 2019.
Amir E Khandani, Adlar J Kim, and Andrew W Lo. Consumer credit-risk models via machine- learning algorithms. Journal of Banking & Finance, 34(11):767-27877 2010.
Hyemi Kim, Seungjae Shin, JoonHo Jang, Kyungwoo Song, Weonyoung Joo, Wanmo Kang, and II-Chul Moon. Counterfactual fairness with disentangled causal effect variational autoencoder. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8128 8136, 2021.
Sean Kulinski and David Inouye. Towards explaining distribution shifts. In International Conference on Machine Learning, pages 17931-17952. PMLR, 2023.
12

---

Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. Advances in neural information processing systems, 30, 2017.
Tianci Liu, Haoyu Wang, Yaqing Wang. Xiaoqian Wang, Lu Su, and Jing Gao. Simfair: A unified framework for Faire multi-label elassification. Proceedings of the AAAI Conference on Artificial Intelligence, (1(12):4338-114444 2023.
Michael Lohaus, Michael Perrot, and Ulrike Von Luxburg. Too relaxed to be fair. In International Conference on Machine Learning, pages 6360-6369, 2020.
Yuchen Ma, Dennis Frauen, Valentyn Meinychuk, and Stefan Feuerriegel. Counterfactual fairness for predictions using generative adversarial networks, 2023. URL htttt::////aate wwwpxii.org/bbb/211110 17687.
Karima Makhlouf, Sami Zhioua, and Catuscia Palamidessi. Survey on causal-based machine learning fairness notions, 2022.
Aditya Krishna Menon and Robert C Williamson. The cost of fairesss in binary classification. In Conference on Fairness, accountability and transparency, pages 107-118, 2018.
George Mohler, Rajeev Raje, Jeremy Carter, Matthew Valasik, and Jeffrey Brantingham. penalized likelihood method for balancing accuracy and fairness in predictive policing. In 2018 IEEE international conference on systems, man, and cybernetics (SMC), pages 2454-2459. IEEE, 2018
Arash EasssEEfah,n, Mohammad Alizadeh, and Devavrat Shah. Counterfactual identifiability of bijective causal models. arXiv preprint arXiv:2302. 20Xi::23002.02228,, 2023.
Hamed Nilforoshan, Johann D Gaebler, Ravi Shroff, and Sharad Goel. Causal conceptions fairness and their consequences. In International Conference Machine Learning, pages 16848-16887. PMLR, 2022.
Judea Pearl. Causality. Cambridge university press, 2009.
Dino Pedreshi, Salvatore Ruggieri, and Franco Turini. Discrimination-wware data mining. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 560-568, 2008
Dana Pessach and Erez Shmueli. Algorithmic Fairness, pages 867-886. 2023.
Jonas Peters, Joris M Mooij. Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. 2014.
Felix Petersen, Debarghya Mukherjee, Yuekai Sun, and Mikhail Yurochkin. Post-processing for individual fairness. Advances Neural Information Processing Systems, 54:25944-22555, 2021.
Drago Plecko and Elias Bareinboim. Causal fairness analysis. arXiv preprint arXiv:2207.11388 2022.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High- resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF confer- ence on computer vision and pattern recognition, pages 10684-10695, 2022.
Lucas Rosenblatt and R. Teal Witter. Counterfactual faimess is basically demographic parity. In Brian Williams, Yiling Chen, and Jennifer Neville, editors, Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI 2023, pages 14461-14463 AAAI Press, 2023. doi: 10.1609/AAAI.
V37112.26691. URL https: //ooi org/ 1609/ www.a....a....aaaaaaaaa www..3........ 26691.
Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning. Proceedings of the IEEE, (09(5)1122-6) 2-434, 2021.
Marco Scutari, Francesca Panero, and Manuel Proissl. Achieving fairness with a simple ridge penalty, 2021.
13

---

Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(10),
2006.
Pietro G. Di Stefano, James M. Hickey, and Vlasios Vasileiou. Counterfactual fairesss: removing direct effects through regularization. CoRR, abs/2002.10774, 2020.
Yixin Wang, Dhanya Sridhar, and David Blei. Adjusting machine learning decisions for equal opportunity and counterfactual fairess.. Transactions on Machine Learning Research, 2023.
Linda Wightman. Lsac national longitudinal bar passage study, Isac research report series. 1998.
Yongkai Wu, Lu Zhang, and Xintao Wu. Counterfactual fairness: Unidentification, bound and International Joint Conference on Artificial Intelligence, IJCAI-19, pages 1438-144 1444, 2019.
algorithm. In Proceedings of the
Ruicheng Xian, Lang Yin, and Han Zhao. Fair and optimal classification via post-processing. In International Conference Machine Learning, pages 37977-38012. PMLR, 2023.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi. Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreat- ment. In Proceedings of the 26th international conference on world wide web, pages 1171-1180, 2017.
Han Zhao and Geoffrey J. Gordon. Inherent tradeoff's in learning fair representations, 2022.
Kaiyang Zhou, Ziwei Liu, Yu Qiao, Tao Xiang, and Chen Change Loy. Domain generalization: survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(4):4396 4415, 2022a.
Zeyu Zhou, Ziyu Gong, Pradeep Ravikumar, and David Inouye. Iterative alignment flows. In International Conference on Artificial Intelligence and Statistics, pages 6409-6444 PMLR, 2022b.
Zeyu Zhou, Sheikh Shams Azam, Christopher G Brinton, and David Inouye. Efficient federated domain translation. In The Eleventh International Conference on Learning Representations, 2023.
Zeyu Zhou, Ruqi Bai, Sean Kulinski, Murat Kocaoglu, and David Inouye. Towards characterizing domain counterfactuals for invertible latent causal models. In The Twelfth International Conference on Learning Representations, 2024. URL /tttps://pperree/ee
Zhiqun Zuo, Mohammad Mahdi Khalili, and Xueru Zhang. Counterfactually fair representation. Advances in neural information processing systems, 2023.
14

---

A Proofs
A.1 Proof of Lemma 3.2
Proof of Lemma 3.2.
TE( 0 Bllo(X,A) 6(X1-1, A)lI + o(x,)) - 6(11-a a), V(z, a)
where the first equality is by definition and the second equality is because absolute value always non-negative for any (x., a). Thus, the predictions must be almost surely equal for all (ar, they are all equal on the non-zero metric set, then the expectation must be 0.
a). a). Similarly,
A.2 Proof of Theorem 3.3
Before proving the main theorem, we first provide one well-known lemma that reminds the reader of the well-known result of the optimal predictor, which is denoted by o² in the theorem statement.
Lemma A.1 (Optimal Predictor is Conditional Mean). The conditional mean E x] is the optimal predictor without fairness constraints for classification with cross-entropy loss and for regression with MSE loss.
Proof. First, let's s establish that the optimal predictor without constraints is in fact E = x]. For
squared L2 loss, we have that derivative:
E[(()(X),)) Y)]
= =x (Y *(X))
-Ex(Er x Y22 2 + B Byyxle
=Ex x Y22 (x xx
= =Ex Y X + 6
Taking the derivative the inside expectation w.r.t ((X) and setting to yields (x(X) [E[Y [X].
Now let's look at cross-entropy loss for classification:
E({(o(X),)) Y)]
= Ex [E log(o(X)) - (1 - (1- -o
- = Ex 1- (og(oo(())) - log(1 - -1 Y)
Again, if you take the derivative w.r.t. (xX) and set to 0, we see that 6= (X) E|
Now we seek to prove Theorem 3.3.
Proof. noise U.
First, we decompose the factual error across the sensitive attribute given the exogenous
EX.A,Y Ex.A,YI((((X (X(
(U)
=Ey (C/
= a) +B
Ev
+ - 11
Consider U u, inside the expectation we have
+ -
p(A = 10g
=(AA = a E6 [() -- http::/h-....aaa..........d.....
where w.l.o.g., I viewed as the factual and Ha is viewed as the counterfactual. Because of invertibility, these two terms are unique for every (u,a) correspondingly (æ,, a) combination and thus the problem decomposes across U. Thus, the factual can viewed as a combination the factual loss from one specific plus the counterfactual loss for a' for each point
15

---

We have the following subproblems indexed by u: The factual loss can be viewed as a combination of the factual loss from one specific plus the counterfactual loss for a for each point z. Notice that the constraint is (xI, a) 6< a) from Lemma 3.2. We can directly push the constraint into the optimization problem by optimizing over do o(z, a) ( 1 a): argmin p(A = By x=r.A=a (d00, Y)] + p(A = a) XY Y)] (2)
Taking & squared L2 loss: have
pe x) - p(A -= - - 2o)
-argmin p(
[ - 20 +
+ ob)
+ 1 (BxIx
Y2 By by 1 x0)
Similarly, if take f as (binary) cross-entropy loss: we have
argmin p(A a x
- (1 Y) log 1 +))]
p
o| log( + (1 - Y) log ()]
It is simple to see that both loss functions are convex, thus could obtain a unique solution by taking the derivative. Thus, for each æ; tta' induced by = u, we could get the optimal Φn:
Φo
Σ
p(A d') (Ia',a') a'),
d'E(0.1)
where o² is the optimal predictor from the lemma above. This result holds for every and thus gives the final result.
A.3 Proof of Theorem 3.4
Proof. Let 6² a) and (Cp(I, a) be the Bayes optimal predictor under no constraint and CF constraint respectively. We have shown that o" (ar, a) [xyxx=e,==o and @ a) = p(A a)o a) p(A
a)σ² (z1-0,1-00
Noting that 6² is Bayes optimal, its risk satisfies R S REp where Rer denotes the risk of Φār(x, a). By definition, the excess risk of @Cr(2, a) is
RBp R =Ex, [Ry]x=n.A=a (( (x, a), El0 (x, Vll
For regression task and real-valued Y, take l as squared T.2 loss and have
RCF R*
=Bx,1 [Ey A= (0 1 Y
=Ex,1
21]]]
=Ex.A -bg.
2Y]]]
-
=Ex.A (()
-Ex,A [(p(A = 11000000000000004111110011011110 -4 8" (x, (r)
=Ex.A [11 p(A
=Ex.A Ip²(A = -000
-EA 1p2 - a - a))
Let's define
A, A Ex A= (Bylx=s,Aza Y ByIx=m [T)
EujA=a (Byluzu.A=olY)
Y B EyIU=u,A=I-ad(1)
( Ey (By Y By - A Ai-as
16

---

where (a) holds from the invertibility between X and U given A, and (b) holds from the fact that U and A are independent. For simplicity, we denote A A. A --a- Notably, A measures the expected change of Y due to the change of A over all possible U, and is in fact measure of their dependency. Furthermore, we have
AA [ = 1 - a) a 0000-00000000 021 a))
=EA (A 1 a
= = P(A = a) = -1aa)
=P(A = 0) = 1)4e + M(A 1)p² 0)
=p(A 0)p(A= 1)
=
Next, for classification task and binary Y using cross-entropy loss, then
RCF -
log(1 =Ex,A [BYIX=R.A=o (cr (1-)) ())(
EyIx=x,A=a
+ - Y) log(1 x3 (x. [)]]
=Bx.Al
1-o'log per (1 - 1og ) + xx log x² (1 x²) log(1 6³)]
o²
=Bx,A
6" log
+(1 log OCF
OCF
Ex.A [DKL X, A)P
XA. A)]]
2 Bu.A (P U, A)) A)]
-BU.A [DKL A) U)]
-ByEa [DY U, (U)
=1(A;Y IU),
where (a) holds from noting that o (1, = = A=
and dCF = E. BY =
X A, A)). and (b) again holds from the invertibility between and given A.
A.4 Proof of Proposition 3.5
Proof.
Úa(x,a) a)
= p(A a) a) - a), a)
p(A () a),)), p(A = 1- a)Φ(0)1000)))10))0) a)
- - a)
= =EVIX
A 1=1-0
where the middle qualities are by the properties of the invertible and ground truth CGM. Because the factual output for the algorithm the same as the counterfactual output, then the TE must be by Lemma 3.2.
A.5 Proof of Theorem 3.6
Proof. We first bound TE.
17

---

Let 2a-11- G* a, a). we have
TE =Ex,1 [|0Per La. a) -0pm(()-111-1-1111))))
=Ex,A [lp(A = a)) 0
[I(A +( 11 o
-p(A a))( - 1
=Ex,A
p(A -
1- 11----
-a)l
(a)
< <XEAA
P(A 0
+p(A = 1 141 a, a, a).
=EX,A
+p(A = 1 1= -
(6)
- - (2,, --
S Exx
a), a.a)
+p(A = 1 - -,
a) - G (I a, a)1
(0) Ex.s -
= as + p(A =1 [s
=L.
Here (a) holds by the convexity of absolute value, (b) is from the L-lipschitz property of Φ, and (c)
by the bound of countcrfactual estimation error.
Now we prove the bound for the error. Taking é as squared Lg loss, we have
R Ex, X=m. (1) v)
Ex.AEy Ama [(évc((x.)) (xr(x, a) (c) - -y)
Taking the inner expectation and omit subscript for brevity, we have
(z) E (orcr (z, a) (Z(( y)
E (1, a) -
+ (deer a))
der (() +
=p(A ( a) (11-; 1-))
a))
+ 2p(A= 10
o" +C
<p(A = - -0
+ 2pp(A = (8) 1- (21 (0 a) 0' (z,
(0)
$ P(A = 1- - 2) 2p(A = (z) o" aI +C,
where C denotes the remaining term that only depends on der. Here (a) holds from the fact that the counterfactual estimation error is bounded by and the assumption that 6² is L-lipschitz.
Next, take the outer expectation,
R < - 12
(z(x,a)) + RRi
= =
22LEEx = (x - a) - xxxxxa)]] + Ric.
18

---

Note that taking expectation of C' with respect to the joint distribution of X, A is in fact the optimal risk c.p Reorgamization gives us
R RèF
<o + 2LE A Ip(A =1 1 (11-
ro, + 2L ((AA= EY X = - - E/ U u, A all
X 2, A all
=02 2 (p(A (A= =1 - a)² Y U
=0y + +2L:Bu
1)p(A = -.
=.=,
= 1) U ", A -=
-=
=0) =0² + L0 |||||| U =u.A= = -| U =. 0][
When is cross-entropy loss, the excess risk
R RCF
OFCF
OPCF
= E By
-Ylog &CF
-(1 -1-- Y) log 1 der
Here we assume the logit (i.e., the inverse function of sigmoid) is L-lipschitz continuous in x, i.e., (x, - a+) < L||x -|1, Vx, H,a
where 00 oo o S and (" = log T- 1- Now we check the excess risk. The first term can be upper bounded by
(zx,))
Y log PCF OFCF
p A a)d² (Ir, a) + p(A = ( aa)
Y log
p(A = a) (z, a) + P(A = a) (f1-a.1-a)
$ ( -1 p((A = o)6² (I, log p(A a)o² a))"(r,
p(A 2))
r(A - a) (1) 0. 4) p(A A = 1 - a) (+) a: 0)
+ p(A = - 0)6² (x1 1 - log
=Y = 0) (x1-0: a)
o' (I -a a)
log
c
0 (i (i1-::1 1 a)
YC₁ log 00 (2 - a)
1-a)
where the inequality holds by applying log sum inequality. For the inequality, is derived from
ÓCF OPCF
<p(A a)Φ² (z, a) log p(1 = a ())²))((000 (z)
&Cp log
p(A a))* 0) + + = a1)
p(A A = 1 - ()00"))(10000 1 - a) pl A 1 - (01)"((1aa:)))
log
And Ci is defined as below
p(A = 1 (5) 1-a) 4)
Ci P(A= a) P(A - a))"(11-a)))) 1 a)
Similarly,
1 1 dbF (1 Y) log
(1 - Y) log p(A= = a) pl =
(1) a,
OFeF
p(A 0) -
-= - -
< (1 - r) p(A = 1 - a - 6² (2) -a. 1- a))
1 1- 1-0"(21-a11-0 log
001-1a,
1 - x (21-0) 1 a)
- =1--r)2 log
1 o' (8) - a)
19

---

where
C2 PA = 1 a)(1 0²(2) a- 1 a))
PCF
p(A a (2- al)
1 P(A = a)Φ* - - 1 a)
--11--- -
p( a) a(A=a)0'(z,00 + -
0)(1 1001-00011 (21
a))
Put together
PCF
Y log
+ (1 - Y) log
OPC
OFCF
[2) -; 1 a)
o" (x) a3 a
SYC log
+ Y)C2 log
(81-01 1 a)
1
0 (8 aa - a
(#1 a)
6² (11 (1 0)
YC1 log
+ (1 C)C2 log
0f1 a)
6 (01-0: 1 0)
(111-a; 1 a)
Ø² (8) -1 1- a)
1N
YCi log
(1 Y)C2 log
00 1 a)
6" ( a: - a)
0 ( -, 1- a)
Ø (x) a.
K max (YC1, (1 - Y)C2}
log
log
( 1- a)
as
[1 -0 1 - 0)
[1) a1 1
log
log
00 1 a)
6" ( aa 1 a)
(I1-a: a) (1 (31
6º (81 1 a)
log
log
< D| - f1-ll-
63 (i) (0;--,11 a)
Step (a) holds from the observation that the two log terms must have different signs: unless
(" 1 - a) = 6= (#1 a) 0.5, otherwise is impossible to have both
(0) 1- -a) a) 2 0"( 1-a) 1 (01-10 a) 2 1- 1
hold simultaneously. Step (b) holds from the fact that the two terms now have the sign can safely upper bound them, and this maximum is upper bounded by 1. Finally, the excess risk
Pe Opef
1 d'F
Y log
+1 Y) log Spes
Byx. [4| 21-all] S Le,
so long as |1-1- 21-all S e. This completes the proof.
B Counterfactual Risk Minimization
Theorem B.1. Given that G is the ground truth counterfactual generating mechanism. CRM and PCF will have the same optimal solution under the constraint of perfect Counterfactual Fairness, iee.
argmin Ex.4Y (x argmin #
de TE))==0
20

---

Proof.
=Bu BB -
+ +p(A = otapa//aaaaakakkaaa..aoooaaaaaaa
=Ex(p(A = 1ttp:///wa..a/aa................ B (
+
X= --)
Enforcing the constraint of CF, we define Φu _ ((x, = σ 6 a). then the optimization
problem of the inner expectation becomes
argminp( RyIX== f)] p(A = a Jy X (( Y)
%
+ + a a] Y)] + p(A = 1 - a 1 Y)]
= argmin22( = a (x Y)1 2p(4 = a B -B
d
where the objective is just a scaled version of that in the proof of Theorem 3.3. Hence, we get the same minimizer.
C Experiment Details
We included the codes to reproduce results. All GPU related experiments are run on RTX A5000.
C.1
Dataset
Synthetic Dataset In this section, consider the two regression synthetic datasets and two classification tasks where all of our assumptions in Assumption 3.1 are satisfied.
Linear-Re Reg
Cubic-Rey Reg
A Bernoull((pa,, ~ -
~ A Bernoulli(pA), U ey
X WAA+ + WpU
X w + wrU
Y = w + w'yU + wyey
Y = x w'yU wyey
where in our experiments the parameters are chosen as WA = wx = 1, wy = 1, Ww = 1, w/y =
We also consider the following two classification tasks
Linear-Ch. Cls
Cubic- Cls
A ~ Beroulli(pa), ~
N(00 U ~ 1)
A ~ Bernoulli(p U N(0,,), ~ N0,1
X WAA+ u
X w WAA+ w
Y Bernouli(o(wxxX- + W + wyey))
Y Bernoulli (a (wx X w/yU U + by Ey))
where in our experiments the parameters are chosen W 2, w = 1, wy = 1, WT 1, w'y 1.
Semi-synthetic Dataset We consider Law School Success [Wightman, 1998]. The sensitive attribute is gender and the target is first-year grade. Other features contain race, LSAT and GPA. However, since need evaluate TE of each method which requires access ground truth, use the simulated version of those datasets. Following a similar setup in [Zuo et al., 2023], we train generative model get semi-synthetic datasets. Specifically, we train VAE with the following structure u ~ Enc(I, a), x ~ Dec1 (u, a), ~ Dec2 u, r). The training objective includes a normal VAE objective reconstruct 2 via Enc and Dec;, and supervised objective generate y via Decz- After training. we first sample prior ~ ~N(0, 7) and a ~ Bernoullipp) (where p is acquired based on empirical frequency in real data), then we get the semi-synthetic z, y using Dec; and Decz- We want to emphasize that counterfactuals, regardless of train or test set, are hidden from downstream models and used for evaluation only. This way, we get access to the ground truth u² and can generate ground truth counterfactuals without any error. In our investigation, exogenous noise, factual data and counterfactull data are all actually the simulated version of original datasets. However they do follow fixed data generating mechanism that is close to the real data.
21

---

C.2 Analytic Solution on Synthetic Datasets
We know the analytic solution of Bayes optimal predictor our synthetic data experiments. More specifically, for Linear-Reg, we have
Wy (r - waa)
(x a) = a = wxx
x2 v,
Wy
For Cubic-Reg, we have
Wiy (x - WAO)
o" = 2, A a) wxxx
wy
For Linear-Cre we have
Φ (x, E|y|X = == = o(wxx + Wt (x- wra))
wy
For Cubic-Cls, have
o" (lz,a)=E|Yp = x, A = a) owxxx3+ + w'y (x-wAA) wy
C.3 Prediction Models
In our synthetic experiments, we mainly use KNN based predictors. We use the default parameters in scikit-learp All MLP methods uses structure with hidden layer (20, 20) and Tanh activation.
In semi-synthetic experiments, use MLP methods uses structure with hidden layer (5, 5) and Tanh activation as this is closer to the ground truth SCM.
D Additional Results
D.1 Additional results synthetic datasets
In Figure 7, we test how how all algorithms perform when using ground truth counterfactuals and U on additional type of predictors. We observe that PCF achieves lower error than CFU and CFR, which similar to what we observe Figure 3. This further validates our theory regarding optimality of PCF.
In Figure 8, following the investigation in Figure 4, we test with adding gaussian noise with different mean. We observe that when it is fixed bias, CFU and CFR achieves better faimeess than PCF Though PCF still achieves best predictive performance. Furthermore, as we increase variance the noise, PCF outperform these two methods in terms of both faimeess and ML performance. In Figure 9, similar to Figure we observe PCF-Anale -calltta significantly improves over PCF. Notably, is not affected by bias as PCF.
D.2 Additional results on semi-synthetic datasets
In Figure 10, included the expanded version of Figure 6 with TE₁ and TE₁- We observe that they show a very similar trend. In Figure 11, we directly compare PCF (with ERM) and PCF-CRM. The results validate the necessity of CRM as plugin estimator in the case of limited causal knowledge.
D.3 Additional experiments
To evaluate the performance of our method across a broader range of data generating mechanisms, counterfactual estimation models, and datasets, we conducted experiments using the Disentangled Causal Effect Variational Autoencoder (DCEVAE) on the Adult dataset [Asuncion et al., 2007]. Similarly, we trained one DCEVAE to simulate the Sim-Adult dataset and another DCEVAE to estimate counterfactuals. Here we followed the data preprocessing, model setup, and hyperparameter choices specified in Zuo et al. [2023]. A key difference between the setup used here and our setup on the Law School dataset that, this case, the encoder of the ground truth DCEVAE takes as input. This modification introduces an inconsistency between the ground truth CGM and the estimated CGM. Figure 12, we observe a trend similar that in Figure which indicates the effectiveness of PCF-CRM.
22

---

0.23
0.25
DRN
OnU
E B215
10.55
0325
10
60
13
6 88
(a) Linear-Reg
(h) Cubic-Reg
(c) Linear-Cls
(d) Cubic-Cls
Figure 7: Results on synthetic datasets given ground truth counterfactuals with MLP predictors.
35
0220
ed
120
0260
50.00
1.1
0.043
O'
metiss
0.259
1.0
69
6:88
848
830
615
6.20
6.25
(a) Linear-Reg
(b) Cubic-Reg
(c) Linear-Cls
(d) Cubic-Cls
Figure 8: Results synthetic datasets under counterfactual estimation error with KNN predictors. Different color represents different a indicating the standard deviation of the error (e ~ (/00001,, a)) while shape represents different algorithms.
1.17
1.16
1.15
5 324
126
0250
0374
0378
$.00.
Ditt
0.240
RCF
320
KC--tra
8230
16
20
(a) Linear-Reg
(b) Cubic-Reg
(c) Linear-Cls
(d) Cubic-Cls
Figure Results on synthetic datasets comparing PCF and PCF-Analytic with KNN predictors. Different color represents different a indicating the standard deviation of the enror (e ~ N (000011, while shape represents different algorithms.
23

---

1.000
0.2
1.60
105
1000
1.0
1045
method
040
CFU
ECDCF
0.300
0.325
9.350
0.378
0.400
0.425
0.450
0.415
0.50
ERM
TE
1.070
lamb
0055
0.5
method
CFR
0.300
0.325
3
0.375
0.400
0.423
0.450
475
ERM
PCF-CRM
(b) TEg
0.2
1050
0.8
1.0
1045
040
033
CRU
0.300
0.325
0,280
0,375
0.400
0.425
9.450
0.455
0,500
2
PCT-CRM1
TE
Figure 10: Results on Sim-Law with estimated counterfatuals. The predictor is a MLP regressor. We also test the convex combination of each algorithm and ERM. For example, PCFAug with means ý AÿdeFAug + (1 A)DERM. This suggests that PCFAug can achieve lower Error given the same TE and lower given the same Error.
lamb
0.4
050
1.445
method
1.00
105
0.390
0,325
0,350
0,375
0.425
4500
0475
0,500
Figure 11: Comparison between PCF and PCF-CRM on Sim-Law with estimated counterfatuals, The predictor is MLP regressor.
24

---

0.2250
lamb
0.2225
0.2
0,2200
0.4
0.2175
0,6
0.8
0.2150
1.0
0.2125
method
CFR
0,2100
CFU
0.2075
ERM
0.06
0.08
0.10
0.12
0.14
0.16
0.18
0.20
0,22
PCF-CRM
7E
Figure 12: Results on Sim-Adul with estimated counterfatuals. The predictor a MLP classifier.
25

---

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

---

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

---

In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code is released.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (uttps://nips.cm ca/
for more details.
While we encourage the release of code and data, we understand that this might be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/nips. wttpccpppppppceteeeeccecccccccet http//uuissse/eee httgg/dd//oooeeubiiiieeeeeeeeeee //oo/eeooiisssseeeeeeeeee cattiisssinooiccyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
See Section 5 and Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: It would be too messy to include error bars in the current plot.
28

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by emror bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: pettps://neurppee http:///eaa.eep.c//ccccccctttcaa cc/publicc/thhcccuudeee
Answer: [Yes]
Justification: To the best of our knowledge we do not violate any portion of the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
29

---

10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
This paper aims to enhance Counterfactual Fairness in practical scenarios, but it's important to note that method's validation is currently limited to semi-simulated datasets with known counterfactuals, Therefore, further auditing and verification are essential before applying this method in real-world fairness scenarios.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairesss considerations (e.g.. dep.lymmet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not believe our work has a risk of misuse
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
30

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
The datasets used are cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged to reach out the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets are released in the paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
31

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "JVJaM6plME", "reviewer": "Reviewer_pyBD", "summary": "This paper focuses on counterfactual fairness (CF), which is a promising framework for evaluating the fairness of machine learning models, and analyzes the trade-off between accuracy and CF. The authors give some theoretical results from the perspective of the Bayes optimal classifier under the perfect CF constraint. They also present theoretical analyses for cases where we can not access the ground truth of the causal structure and Bayes optimal classifier. The theoretical results in this paper were validated by experiments on synthetic and semi-synthetic datasets.", "questions": "- Q1. Can the proposed framework be evaluated by the same experimental setting with [Zuo+ 23]? Their setting includes more complex datasets and causal models than those of this paper, and it seems to be applied to the experimental evaluation for the proposed framework of this paper. \n- Q2 (minor, optional). While the authors state \"our analysis and our method can be naturally extended to multi-class $A$,\" I could not find how to do that in the paper including appendix. Is it trivial? And does it have no impact on the theoretical results? \n- Q3 (minor, optional). Can the proposed framework be adapted to the path-dependent CF constraint? \n\n[Zuo+ 23] Zhiqun Zuo, Mahdi Khalili: Xueru Zhang. Counterfactually Fair Representation. NeurIPS, 2023.", "limitations": "Yes, the authors discussed the limitations and potential impacts of their work in Section 6 and Question 10 of Checklist, respectively.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- S1. This paper is easy to follow and well-organized. Each experiment seems to clearly correspond to what the authors want to validate. \n- S2. In Theorems 3.3 and 3.4, the authors analyze the predictive performance that can be achieved under the constraint of perfect CF from the perspectives of the Bayes optimal classifiers and their excess risk. I think the result that the excess risk of CF is completely characterized by the inherent dependency between Y and A as with the existing group fairness is interesting. \n- S3. The authors also give analyses for cases where we can not access the ground truth of the counterfactual generator (i.e., causal structure) and Bayes optimal classifier. Furthermore, they propose a simple learning framework, named CRM, that can be applied to both training from scratch and fine-tuning.", "weaknesses": "- W1. I am concerned about the practicality of the proposed framework because the experiments in this paper seem insufficient. All the experiments in this paper seem to consider only one observed feature $X$. While these experiments may be sufficient to just validate the theoretical results, they seem too simple to demonstrate the reality and significance of the proposed framework. \n- W2. I am also concerned about the causal graph assumed in this paper. While there may be nothing wrong with assuming a causal graph like Figure 1 to show theoretical statements, I believe the behavior of the proposed framework in the case where this assumption is violated should also be verified by experiments.\n\n**---------- post-rebuttal ----------**\n\nI would like to thank the authors for their comments and clarifications. \nThe author's rebuttal adequately addressed my concerns.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging the writing quality, the theoretical contributions of our paper, and the importance of our practical method. We will address each of your concerns and questions below.\n\n>**W1,Q1: Experiment Settings**\n\nThanks for your thought. We would like to first clarify that in our semi-synthetic experiment (Section 5.2), the Law School dataset contains *more than one features*, here notation $X$ is a vector. In addition, the experiment setup here is indeed based on [Zuo+23]. The dataset is generated by a pre-trained VAE that follows more complex causal models than that in our synthetic experiment. We train another VAE to estimate unobserved $U$ and counterfactuals. By doing so we validate the effectiveness of our algorithm when one doesn't have access to the ground truth counterfactuals. We will make these setup clearer in the final manuscript.\n\nTo further evaluate the performance of our method, we follow the reviewer’s suggestion and add the experiment on UCI Adult. In this experiment we use DCEVAE from [Zuo+23] to make the causal model more complicated --- the same one as that in Figure 4 of [Zuo+23]. *The proposed method again outperforms other baselines on this task*, as shown in Figure 1 in the attached PDF in Response to All. We will add a more comprehensive study in the final manuscript.\n\n>**W2: Assumptions on causal graph**\n\nThe validity of our theoretical analysis holds for all causal models that satisfy the condition given by Assumption 3.1. It is not restricted to the specific graph given in Figure 1, as explained in the footnote on Page 4.  In the paper we present Figure 1 as an illustrative example of how fairness issues can arise from a causal perspective that has been widely used in counterfactual fairness literature [Kusner+ 17][Grari+ 23]. We will modify the caption of Figure 1 to make it more clear in the final manuscript. To test the generality of our method, we experiment with semi-synthetic Law School and Adult (please see above) datasets adapted from [Zuo+23]. Here the causal graphs are designed to be more complicated (Figure 3 and 4 in [Zuo+23]). Experiment results validate the effectiveness of our methods in these situations.\n\n>**Q2: Generalizations to Multi-class A**\n\nIn the case of multi-class A, the counterfactual generation mechanism can be written as $x_{a \\to \\tilde{a}}=G(x,a,\\tilde{a})$.\nThen, Theorem 3.3 can be written as \n$$\\phi^*_{\\textnormal{CF}}(x,a) \n        \\triangleq  p(A=a)\\phi^*(x,a) + \\sum_{\\tilde{{a} }\\neq a}p(A=\\tilde{a})\\phi^*(x_{a \\to \\tilde{a}}, \\tilde{a}) \n        \\in \\arg\\min_{\\phi:\\mathrm{TE}(\\phi)=0}  E[\\ell(\\phi(X,A), Y)]$$\n    where $x_{a \\to \\tilde{a}} = G^*(x,a,\\tilde{a})$.\nThe proof is similar to the current proof for binary $A$. The key difference is that the expectation over $A$ is now over all possible values of $A$ rather than just two terms. After modifying the Lemma 3.2 to $\\phi(x,a)\\overset{\\text{a.s.}}{=}\\phi(x_{a \\to \\tilde{a}}, \\tilde{a}),\\quad\\forall (x,a,\\tilde{a}) $, we can get the multi-class version of Eqn (2) (below Line 490) as \n$  \\arg\\min_{\\phi_0} p(A=a) E_{Y|X=x,A=a}[\\ell(\\phi_0, Y)] + \\sum_{\\tilde{a}\\neq a} p(A=\\tilde{a})E_{Y|X=x_{a \\to \\tilde{a}},A=\\tilde{a}}[\\ell(\\phi_0, Y)]$. Similarly, it is a convex loss function and we could get the result shown above. Similar ideas could be extended to the other theoretical results since none of them fundamentally rely on A being binary. We use binary $A$ mainly for convenience and simplicity of the notation.\n\n>**Q3: Generalizations to Path-dependent CF**\n\nUnder the path-dependent CF constraint, a similar principle will hold: counterfactual pairs need to produce the same outcome. In this case, the counterfactual estimation function will need to be modified to account for the additional intervention. However, we conjecture that similar theoretical results will hold since the core ideas are analogous.\n\n\n[Zuo+ 23] Zhiqun Zuo, Mahdi Khalili: Xueru Zhang. Counterfactually Fair Representation. NeurIPS, 2023.\n\n[Kusner+ 17] Kusner, Matt J., et al. \"Counterfactual fairness.\" Advances in neural information processing systems 30 (2017).\n\n[Grari+ 23] Grari, Vincent, Sylvain Lamprier, and Marcin Detyniecki. \"Adversarial learning for counterfactual fairness.\" Machine Learning 112.3 (2023): 741-763.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "p2epHLihJR", "reviewer": "Reviewer_Kz4o", "summary": "This paper focuses on counterfactual fairness in ML models (regardless of the model), which means that the prediction of the model should not change if the input individual had belonged to a different sub-population. The main contribution of this paper is to provide a theoretical trade-off between the performance of the model and counterfactual fairness.", "questions": "- If A is not binary and is multi-class, what would the results of Theorems 3.3 and 3.4  look like? Specifically, in Theorem 3.3 where $x_a = G^*(x, a, 1-a)$, how can you rewrite this in a multi-class setting? \n\n- Again, in the multi-class case, what would the assumption of theorem 3.6 look like? Do you assume a bound on $G^*$ and $\\hat{G}$ for every pair of A’s possible values?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is very well written and well presented. It is easy to follow and understand the results. \n- The main strength of the paper is that it shows if we have access to the ground truth counterfactuals, using an unfair model (regardless of what model it is), we can achieve strong fairness and accuracy (Theorem 3.3). Later, they characterize the excess risk of the Bayes optimal predictor under the counterfactual fairness constraint (Theorem 3.4), which is again insightful.", "weaknesses": "- Strong assumptions: access to the ground truth counterfactuals and access to the Bayes optimal predictor. However, they attempt to relax the first assumption slightly in Section 3.3. As I am not an expert in this field, I cannot verify how strong the assumptions (before or after relaxation) are and how practical they are.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging the writing and theoretical insight of our paper. We will address each of your concerns and questions below. \n\n>**Assumption of access to ground truth and Bayes optimal predictor**\n\nAccess to ground truth counterfactuals, as discussed in Section 6, is a common challenge in the literature of Counterfactual Fairness (including but not limited to the discussed related works in our paper). However, this limitation does not undermine the contribution of this work.\n1. Similar to the previous works in the literature [1], this assumption is mainly used for theoretical analysis. Notably, we also provide the optimality and inherent trade-offs. Both are important but missing in the literature. \n2. We carefully studied how violating this assumption, namely using imperfectly estimated counterfactuals, can affect performance, both theoretically (Section 3.3) and empirically (Figure 3, Figure 5 in Section 5, and Figure 1, Figure 2 in the attached PDF in Response to All). We note that *our method outperforms baselines by a large margin, showing notable robustness against such violations.*\n\nRegarding access to Bayes optimal predictor, it would be relatively practical to acquire via ERM [2][3][4]. A practical concern would be the performance of the predictor on the estimated counterfactuals when there is counterfactual estimation error. This is similar to the situation of out-of-distribution generalization. Motivated by this, we propose the Counterfactual Risk Minimization (CRM). \n\nThe experiments in our paper validate the effectiveness of PCF-CRM, the practical algorithm we proposed that acts on *estimated counterfactuals* and *ERM-trained predictor*. During the rebuttal, we further add experiments with additional dataset and baselines as shown in the attached pdf in Response to all. Again, these results reveal the effectiveness of our method. \n\n\n[1] Zhiqun Zuo, Mahdi Khalili: Xueru Zhang. Counterfactually Fair Representation. NeurIPS, 2023.\n\n[2] Shalev-Shwartz, Shai, and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.\n\n[3] Mohri, Mehryar, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.\n\n[4] Jana, Soham, et al. \"Empirical Bayes via ERM and Rademacher complexities: the Poisson model.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.\n\n>**Theorem 3.3 and 3.4 in the multi-class case**\n\nIn the case of multi-class A, the counterfactual generation mechanism can be written as $x_{a \\to \\tilde{a}}=G(x,a,\\tilde{a})$.\nThen, Theorem 3.3 can be written as \n$$\\phi^*_{\\textnormal{CF}}(x,a) \n        \\triangleq  p(A=a)\\phi^*(x,a) + \\sum_{\\tilde{{a} }\\neq a}p(A=\\tilde{a})\\phi^*(x_{a \\to \\tilde{a}}, \\tilde{a}) \n        \\in \\arg\\min_{\\phi:\\mathrm{TE}(\\phi)=0}  E[\\ell(\\phi(X,A), Y)]$$\n    where $x_{a \\to \\tilde{a}} = G^*(x,a,\\tilde{a})$.\nThe proof is similar to the current proof for binary $A$. The key difference is that the expectation over $A$ is now over all possible values of $A$ rather than just two terms. After modifying the Lemma 3.2 to $\\phi(x,a)\\overset{\\text{a.s.}}{=}\\phi(x_{a \\to \\tilde{a}}, \\tilde{a}),\\quad\\forall (x,a,\\tilde{a}) $, we can get the multi-class version of Eqn (2) (below Line 490) as \n$  \\arg\\min_{\\phi_0} p(A=a) E_{Y|X=x,A=a}[\\ell(\\phi_0, Y)] + \\sum_{\\tilde{a}\\neq a} p(A=\\tilde{a})E_{Y|X=x_{a \\to \\tilde{a}},A=\\tilde{a}}[\\ell(\\phi_0, Y)]$. Similarly, it is a convex loss function and we could get the result shown above. Similar ideas could be extended to the other theoretical results since none of them fundamentally rely on A being binary. We use binary $A$ mainly for convenience and simplicity of the notation. We will makes clearer in the revised paper. \n\n\n>**Assumption of theorem 3.6 in the multi-class case**\n\nYes, the assumption could be written as \n$$ \\max_{x, a, \\tilde{a}}\\|G^*(x_a,a,\\tilde{a}) - \\hat{G}(x_a,a,\\tilde{a})\\|_2 \\leq \\epsilon.$$\n\nWe will makes clearer in the revised paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LMUAwTnZHc", "reviewer": "Reviewer_e7ax", "summary": "This work studies the problem of counterfactual fairness in ML predictions. The authors first prove the form of the best possible fair predictor in a model-agnostic manner. Then, the excess risk of optimal predictor under the CF constraint is characterized. Based on the theoretical findings, the authors propose a post-preprocessing algorithm to achieve CF given arbitrary ML predictor. The authors perform comprehensive numerical studies to demonstrate the performance of the proposed algorithm compared to several baselines.", "questions": "1. See Weakness 2.\n\n2. Wang et. al [1] proposed a weighted average CF predictor and discussed the optimality of the proposed predictor, which shares similar spirit with this work. The authors can discuss the difference between this work and . Wang et. al [1]'s work in terms of accuracy and fairness guarantee.\n\n3. Line 183; I am confused about the intuition about the objective function for counterfactual risk minimization (CRM). In my opinion, the counterfactual outcome may not be necessarily close to factual outcome $Y$. Can the authors explain more about the reason why adding the second term in the objective function?\n\n\n[1] Wang, Yixin, Dhanya Sridhar, and David Blei. \"Adjusting Machine Learning Decisions for Equal Opportunity and Counterfactual Fairness.\" Transactions on Machine Learning Research (2023).", "limitations": "The authors discuss the limitation of restrictive irreversible assumption in section 3 and access to ground truth counterfactuals and optimal predictors in section 6.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The theoretical analyses throughout the paper are technically sound and comprehensive. \n\n2. Presentation of the work is easy to follow and the writing quality is high.", "weaknesses": "1. Although the authors acknowledges that the access to ground truth counterfactuals is out of the scope of this work, I personally think it is better to incorporate existing counterfactual estimation procedures into the Algorithm 1, which would enhance its practical applicability for the researchers and policy makers.\n\n2. The authors can include more existing methods in the numerical experiments for comparison, such as the post-processing method by Wang et. al [1] and the pre-processing method by Chen et. al [2], to see the performance gap between these algorithms.\n\n\n[1] Wang, Yixin, Dhanya Sridhar, and David Blei. \"Adjusting Machine Learning Decisions for Equal Opportunity and Counterfactual Fairness.\" Transactions on Machine Learning Research (2023).\n\n[2] Chen, Haoyu, et al. \"On learning and testing of counterfactual fairness through data preprocessing.\" Journal of the American Statistical Association (2023): 1-11.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging the writing and theoretical contribution of our paper. We will address each of your concerns and questions below. \n\n>**Incorporate existing counterfactual estimation procedures into the Algorithm 1**\n\nWe will follow your suggestion and modify the Algorithm 1 to an end-to-end solution by incorporating the counterfactual estimation procedure. Our experiments did use estimated counterfactuals. as detailed in Section 5.2. In particular, we trained a VAE to estimate counterfactuals to validate our method’s practical applicability. \n\n>**Comparison with [1]**\n\nWe thank the reviewer for bringing this interesting work to our attention. After carefully reading through the paper, we note the following key differences compared to our work. \n\n1. The two *algorithms are different*.  For the sake of simple illustration, consider the case with binary sensitive attribute $A$ and deterministic counterfactuals (i.e., $G(x, a, a')$ is a deterministic function). The algorithm in [1], according to eq (2) therein, is given by \n$$f_{ecocf}(x,a) = p(a)f_{eco}(x) + p(1-a)f_{eco}(x_{1-a}).$$\nIn words, [1] constructs the fair predictor by taking the (weighted) average over equal counterfactual opportunity (ECO)-fair predictions $f_{eco}$. In contrast, our algorithm, \n$$f_{pcf}= p(a)f(x,a) + p(1-a)f(x_{1-a},1-a),$$\ndirectly averages the original ML predictors $f$ that may be potentially unfair.\n\n2. The *optimality conditions* are different:\nIn essences, in [1] optimality holds only in an ideal world where non-sensitive features $X$ and sensitive features $A$ are independent of each other. Our work, on the other hand, is not restricted to such special case. Mathematically speaking, the expected loss in [1] is over $P(A)P(X)$, while ours is over $P(A,X)$. \n\n3. The *problem setups* are different: the discussions in [1] are mainly done without consideration of hidden confounders, while our discussion explicitly considers the existence of an unobserved confounder $U$.\n\nBesides the above conceptual difference, we also found notable empirical performance gaps between the two method, which is shown in Fig2 of the above rebuttal pdf, and is detailed in the following response.\n\n>**Experiment with additional baselines**\n\nFollowing the reviewer’s suggestion, we conduct additional experiments and compare the proposed method with [1] and [2]. The results are shown in Figure 2 in the attached pdf in Response to All. We note that *our method outperforms these two baselines*. Due to time and space constraints, more comprehensive study will be added in the revised version.\n\n\n>**Discussion of Counterfactual Risk Minimization**\n\nWe wholeheartedly agree that the optimal prediction for the counterfactual might be different from that of the original data. However, under the constraint of Counterfactual Fairness (CF), a predictor needs to predict the same outcome for counterfactual pairs. Hence, the optimal solution will change. This is exactly what causes the excess risk we characterized in Theorem 3.4. Moreover, we could actually prove that the theoretic minimum of CRM optimization is actually the optimal CF solution. We will provide a more formal analysis in the final manuscript. \n\n[1] Wang, Yixin, Dhanya Sridhar, and David Blei. \"Adjusting Machine Learning Decisions for Equal Opportunity and Counterfactual Fairness.\" Transactions on Machine Learning Research (2023).\n\n[2] Chen, Haoyu, et al. \"On learning and testing of counterfactual fairness through data preprocessing.\" Journal of the American Statistical Association (2023): 1-11.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their time reviewing our paper and providing helpful feedback. In summary, all reviewers acknowledge:
1. The theoretical contributions, especially Theorem 3.3 and Theorem 3.4, which provide an optimality solution under the constraint of Counterfactual Fairness (CF) and characterize the inherent trade-off between CF and predictive performance.
2. The writing quality and result presentation.

We address each reviewer’s questions and concerns in separate responses below. Attached is a PDF containing the experimental results requested by Reviewer pyBD and Reviewer e7ax.
1. In response to Reviewer pyBD, Figure 1 shows results with more complex datasets and causal models. It shows that our method outperforms baselines in this new setup.
2. In response to Reviewer e7ax, Figure 2 shows results with additional baselines. It shows that our method outperforms these new baselines.

Meta-review: The authors demonstrated that, under the assumtption that the Bayes optimal predictor and the ground truth counterfactual generating mechanism are known, it is possible to construct a counterfactually fair Bayes optimal predictor through post-processing.
They also showed that under appropriate assumptions, the use of estimated counterfactual generating mechanism, instead of the true one, could lead to fair predictions under some theoretically guarantee.

While the reviewers expressed concerns about the strength of the assumptions requiring the Bayes optimal predictor and the ground truth counterfactual generating mechanism, the reviewers were generally positive about the paper given that the paper discusses some ways to relax these assumptions.
One of the proposed relaxation methods, counterfactual risk minimization, received detailed questions from the reviewers, and the authors have stated that they will add more detailed discussions on these points.
Incorporating the content of these discussions into the manuscript will improve the quality of the paper.
Decision: Accept (poster)