Counterfactual Fairness by Combining Factual and Counterfactual Predictions

Authors: zeyu  zhou
tianci  liu
ruqi  bai
jing  gao
murat  kocaoglu
david i inouye
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 17:18:56

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.

Main paper: 
 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 et al., 2010] , bringing with it critical ethical and social considerations. A prominent example is the bias observed in the COMPAS tool against African Americans in recidivism predictions [Brackey, 2019] . This issue is particularly alarming in an era where large-scale deep learning models, commonly trained on noisy data from the internet, are increasingly prevalent. Such models, due to their extensive reach and impact, amplify the potential for widespread and systemic biases. This increasing awareness underscores the need for ML practitioners to integrate fairness considerations into their work, extending their focus beyond merely maximizing prediction accuracy [Bolukbasi et al., 2016 , Calders and Verwer, 2010 , Dwork et al., 2012 , Grgic-Hlaca et al., 2016 , Hardt et al., 2016] . Various fairness notions have been developed, ranging from group-level measures such as group parity [Hardt et al., 2016] to individual-level metrics [Dwork 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-making [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 an individual in hypothetical scenarios where their sensitive attributes differ should remain unchanged [Kusner et al., 2017] . As an individual-level notion agnostic to the choice of similarity measure [Kusner et al., 2017, Rosenblatt and Witter, 2023] , CF has recently 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 a naive solution, suggesting that predictions should only use non-descendants of the sensitive attribute in a causal graph. This approach only requires a causal topological ordering of variables and achieves perfect CF by construction. However, it 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 a 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 et al., 2020 , Kim et al., 2021] . However, as 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 a 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 a (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. To consider scenarios with incomplete causal knowledge (e.g. unknown causal graph or model), we further study the CF and predictive performance degradation caused by imperfect counterfactual estimations. Inspired by our theoretical findings, we propose a plugin method that leverages a (potentially unfair) pretrained model to achieve a better tradeoff of fairness and predictive performance than the prior methods. Furthermore, we propose a method to 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 a 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 to 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 settings1 .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 in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
preliminaries: 
 Notation We use capital letters to represent random variables and lowercase letters to represent the realizations of random variables. Now we define a few variables that will be considered in this work. A 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 not caused by any observed variables while a, y, x, u 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, F) where U represents exogenous variables (factors outside the model), V represents endogenous variables, and F contains a set of functions F i that map from U i and P arent(V i ) to V i . A counterfactual query asks a question like: what would the value of Y be if A had taken a different value given certain observations? For example, given that a 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 a man? More formally, given a SCM, a counterfactual query can be written as P (Y A=a |W = w). Here W = w is the evidence and A = a in the subscript represents the intervention on A. For the general procedure to estimate counterfactuals, please refer to Pearl [2009] .Counterfactual Fairness Built upon the framework above, we focus on Counterfactual Fairness (CF), which requires the predictors to be fair among factual and counterfactual samples. More formally, it is defined as below Definition 2.1. (Counterfactual Fairness) We say a predictor Ŷ is counterfactually fair ifp( ŶA=a |X = x, A = a) = p( ŶA=a ′ |X = x, A = a), ∀(x, a).This definition states that intervention on A should not affect the distribution of Ŷ . Using the same example above, the probability of a woman getting the job should be the same as that if she had been a man. For that goal, we use the following metric to evaluate CF Definition 2.2. (Total Effect) The Total Effect (TE) of a predictor Ŷ isTE ≜ E[| ŶA=a -ŶA=a ′ |].Therefore, a predictor is counterfactually fair if and only if TE = 0. Throughout the paper, we use TE to quantify the violation of counterfactual fairness.3 Counterfactual Fairness via Output CombinationQuestion: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: It is discussed in both Section 3 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 are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect 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 a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
problem setup: 
 We assume that all data we have is generated by a causal model [Pearl, 2009] , and we consider the representative causal graph shown in Figure 1 that has been widely adopted in the fairness literature [Grari et al., 2023 , Kusner et al., 2017 , Zuo et al., 2023] . Our analysis is presented based on binary A ∈ {0, 1} given its pivotal importance in 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. A represents sensitive attribute, Y represents the target variable, U represents latent confounders, X represents observed features. Note that the validity of our theoretical analysis holds for all causal models that satisfy the condition given by Assumption 3.1. It is not restricted to this specific graph.Assumption 3.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 in 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 [Nasr-Esfahany et al., 2023 , Zhou et al., 2024] . We expect 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 in the experiment section. To facilitate our discussion, we first define F X as the mapping between X and (U, A), i.e., X = F X (U, A). According to our second assumption, , a) . 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(X a ′ |X = x, A = a), which simplifies to a Dirac delta at a single value given the invertibility assumption. Thus, we introduce the concept of a deterministic counterfactual generating mechanism (CGM), denoted as x a ′ = G(x, a, a ′ ). Also, in our case, we will assume A is binary so that a and it's counterfactual a ′ can be written as 1 -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, A) is counterfactually fair if and only if the predictor returns the same value for a sample and its counterfactuals, i.e., TE(ϕ) = 0 ⇔ ϕ(x, a)F X (•, a) is an invertible function, i.e., ∃F * X -1 , F * X -1 (x, a) = F * X -1 (F * X (u, a), a) = u, ∀(xa.s. = ϕ(x 1-a , 1 -a), ∀(x, 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.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 fairness-utility trade-offs. Moreover, it is still unknown to what extent the ML model performance has to 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 a Bayes optimal predictor as "optimal", and a 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.12 and loss ℓ (i.e., squared L 2 loss for regression tasks, and 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:ϕ * CF (x, a) ≜ p(A = a)ϕ * (x, a) + p(A = 1-a)ϕ * (x 1-a , 1-a) ∈ argmin ϕ:TE(ϕ)=0 E[ℓ(ϕ(X, A), Y )] ,where x 1-a = G * (x, a, 1 -a) is the counterfactual of (x, a) when intervening with A = 1 -a, and ϕ * (x, a) is an unconstrained optimal predictor, i.e., ϕ * (x, a)≜ argmin ϕ E[ℓ(ϕ(X, A), Y )] = E[Y |X= x, A = a].This result suggests that, if we have to access to ground truth counterfactuals, a simple algorithm using a (potentially) unfair model could achieve strong fairness and accuracy. Built upon the above result, we are ready to 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 byR * CF -R * = σ 2 A E U E Y |U =u,A=a [Y ] -E Y |U =u,A=1-a [Y ] 2 ,for regression tasks using squared L 2 loss where σ 2 A denotes the variance of A; and R * CF -R * = I(A; Y | U ), for classification tasks using cross-entropy loss.Remarkably, the excess risks are completely characterized by the inherent dependency between Y and A as 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 to achieve perfect CF.In this section, we aim to address CF in the scenario where causal knowledge is limited. Inspired by Theorem 3.3, we first present a simple plugin method as summarized in Algorithm 1. For regression tasks, μ is the final output, and for classification tasks, μ represents the probability ofY = 1, i.e., p(Y = 1|X = x, A = a) = E[Y |X = x, A = a].It 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 1 Plug-in Counterfactual Fairness (PCF)Input: Pretrained probabilistic prediction predictor ϕ : X × A → Y, CGM G, test datapoint (x, a), prior distribution p of A Output: Predicted output μ x1-a ← G(x, a, 1 -a) μ ← p(A = a)ϕ(x, a) + p(A = 1 -a)ϕ(x 1-a , 1 -a)Proposition 3.5. Given that G is the ground truth counterfactual generating mechanism, i.e., G(x, a, a ′ ) = x a ′ , ∀(x, a, a ′ ), 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 ϕ. If ϕ is further accurate, then the corresponding PCF is able to achieve high accuracy as well, which is empirically validated in the experiments.Acquiring counterfactuals in practice can be a challenging task and could lead to estimation errors. In this section we provide a theoretical analysis on this. Specifically, the theorem below bounds the TE and excess risk due to the use of estimated counterfactuals. Theorem 3.6. Given an optimal predictor ϕ * (x, a), suppose it is L-lipschitz continuous in x, and the counterfactual estimation error is bounded, i.e., maxX,A ∥G * (x a , a, 1 -a) -Ĝ(x a , a, 1 -a)∥ 2 ≤ εfor some ε ≥ 0, where G * and Ĝ represent the ground truth and estimated CGMs respectively. Then, the total effect (TE) of Algorithm 1 based on Ĝ is bounded by Lε. Moreover, for squared L 2 loss, the excess risk is bounded byσ 2 A L 2 ε 2 + 2σ 2 A LεE U [|E[Y | U = u, A = 1] -E[Y | U = u, A = 0]|],and for cross-entropy loss3 , the excess risk is bounded by Lε.A and E U [|E[Y | U = u, A = 1] -E[Y | U = 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 ϕ * is smooth, then fairness and prediction performance will not be significantly affected. In practice, CGM in Algorithm 1 can be obtained using counterfactual estimation methods, as discussed in Section 6.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 of 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, a natural approach is to train ϕ on the observed data via Empirical Risk Minimization (ERM), which should fit the predictor well given sufficient samples and a reasonable predictor class. However, ERM can only approximate Bayes optimality within the support of the training data. Outside this support, its performance can deteriorate significantly, 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=1-a |A = a) ̸ = p(X|A = 1 -a), inducing a distribution shift problem (Note that these would be equal given the graph in Figure 1 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 ϕ E X,A,Y [ℓ(ϕ(X, A), Y ) + ℓ(ϕ(G(X, A, 1 -A), A), Y )]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-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 is 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 summary, 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-shelf pre-trained models [Bommasani et al., 2021] , we can potentially avoid this issue by using these models as a good proxy for ϕ.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
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-Davies 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 as 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, we focus on the counterfactual fairness.Methods for Fairness Given an unfair dataset, attempts to achieve fairness fall into three categories. 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-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., 2018 , Scutari et al., 2021 , Liu et al., 2023] . Postprocessing 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 it 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-processed 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. However, their model still suffered performance drops, and it is unknown whether their method is 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-utility trade-offs. Recently, inherent trade-offs towards non-causal based fairness such as demographic 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 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 et 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. 
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 metrics in this paper: Error and Total Effect (TE). The former evaluates whether each method can achieve its goal, irrespective of fairness. This is important because 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 Counterfactual Fairness [Kim et al., 2021 , Zuo et al., 2023] . Given a test set D test , Error is defined as Error = 1 |Dtest| x (i) ∈Dtest ℓ( y(x (i) ), y (i) ) where y (i) is the ground truth target, y(x (i) ) is the prediction of x (i) , and ℓ depends on the task. TE is defined as TE= 1 |Dtest| x (i) ∈Dtest | y(x (i) ) -y(x (i) 1-a )|where x 1-a is the ground truth counterfactual corresponding to x (i) . Since we only consider binary sensitive attribute, we further define TE 0 =1 |{i:a (i) =0}| i:a (i) =0 | y(x (i) ) -y(x (i) 1-a )| and TE 1 = 1 |{i:a (i) =1}| i:a (i) =1 | y(x (i) ) -y(x (i)1-a )| to evaluate Counterfactual Fairness for different group respectively.Methods In general, we consider the following methods: (1) Empirical Risk Minimization (ERM): Directly train a classifier on all features without any fairness consideration. Specifically y = ϕ(x, 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 proposes to use U and a symmetric version of x, x 1-a . Specifically, y = ϕ( x+x1-a 2 , u). (4) Equal Counterfactual Opportunity (ECOCF) [Wang et al., 2023] : An ECO predictor is adjusted to become counterfactually fair. Specifically,ŷ = p(a)[p(a)ϕ(x, a) + (1 -p(a))ϕ(x, 1 -a)] + (1 - p(a))[(1 -p(a))ϕ(x 1-a , 1 -a) + p(a)ϕ(x 1-a , a)] (5) PCF 4 : As introduced in Algorithm 1, PCFproposes to mix the output of factual and counterfactual prediction. Specifically, ŷ = p(a)ϕ(x, a) + (1 -p(a))ϕ(x 1-a , 1 -a). (6) PCF with analytic solution (PCF-Ana): In our synthetic experiment, 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 in Section 3.3, it could be hard to get the optimal predictor when there is counterfactual estimation error. Here due to the scale of our experiment, we augment the dataset with estimated counterfactuals rather than finetuning. Specifically, ϕ is trained via ERM on the datasetD train = {x (i) , y (i) , a (i) } N i=1 ∪ {x (i) 1-a , y (i) , 1 - a (i) } N i=1 .In this section, we consider two regression synthetic datasets and two classification tasks where all of our assumptions in Assumption 3.1 are satisfied. The regression tasks are as belowLinear-Reg A ∼ Bernoulli(p A ), U ∼ N (0, 1), ϵ Y ∼ N (0, 1) X = w A A + w U U Y = w X X + w ′ U U + w Y ϵ Y Cubic-Reg A ∼ Bernoulli(p A ), U ∼ N (0, 1), ϵ Y ∼ N (0, 1) X = w A A + w U U Y = w X X 3 + w ′ U U + w Y ϵ Y The classification tasks take the same form except Y ∼ Bernoulli(σ(w X X + w ′ U U + w Y ϵ Y ) and Y ∼ Bernoulli(σ(w X X 3 + w ′ U U + w Y ϵ Y ))for Linear-Cls and Cubic-Cls respectively. More details could be found in Appendix C.1. Results are averaged over 5 different runs where the structural model is kept the same but data is resampled. All results shown in the main paper use KNN based predictor. Results with other predictors can be found in Appendix D.We first test different methods in situations where all methods have access to ground truth counterfactuals and U as needed. In Figure 2 , 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 ϕ used by PCF is also close to being optimal), we can also observe the inherent fairness-utility trade-off discussed in Theorem 3.4. 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, xa ′ = x a ′ + ϵ and û = u + ϵ where ϵ ∼ N (β, α). In Figure 3 , we observe that while the fairness and ML performance (especially fairness) 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: access to Bayes optimal classifier and ground truth counterfactuals. In Figure 4 , we observe that PCF-Analytic tends to 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.In this section, we 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, we need access to ground truth counterfactuals. Hence we train a generative model on real dataset to generate semi-synthetic dataset following the method in Zuo et al. [2023] .We want to emphasize that counterfactuals are 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 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.In Figure 5 , 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, it 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.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: The code is released.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
conclusion and discussion: 
 Conclusion In this work, we conducted a formal investigation of the trade-off between Counterfactual Fairness (CF) and predictive performance. We proved that combining factual and counterfactual predictions with a potentially unfair, optimal predictor achieves optimal CF. Additionally, we derived 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, we analyzed the effects of imperfect counterfactual estimations on CF and predictive performance.We proposed a plugin approach that leverages 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, Nasr-Esfahany 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 et al. [2024] propose a method of estimating counterfactuals without the need to 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 to Bayes optimal predictors Another crucial plugin estimator of our method is the optimal predictor. In classical ML settings, achieving a good estimator for the counterfactual distribution often requires retraining or fine-tuning. However, in this era, with the abundance of pre-trained models, such as foundation models [Bommasani et al., 2021] , it could be much easier to get a predictor that is 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 a suitable solution due to its post-processing nature, which avoids incurring significant computational costs.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?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 to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Justification: It would be too messy to include error bars in the current plot.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence 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).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: This paper aims to enhance Counterfactual Fairness in practical scenarios, but it's important to note that our 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.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 a 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 to 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 a best faith effort.12. Licenses for existing assets• According to the NeurIPS 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. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing 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 we 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. 
 
 Appendix: A.1 Proof of Lemma 3.2Proof of Lemma 3.2.EQUATIONwhere the first equality is by definition and the second equality is because absolute value is always non-negative for any (x, a). Thus, the predictions must be almost surely equal for all (x, a). Similarly, if they are all equal on the non-zero metric set, then the expectation must be 0.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 ϕ * in the theorem statement.Lemma A.1 (Optimal Predictor is Conditional Mean). The conditional mean E[Y |X = x]is the optimal predictor without fairness constraints for classification with cross-entropy loss and for regression with MSE loss.Proof. First, let's establish that the optimal predictor without constraints is in factE[Y |X = x].For squared L 2 loss, we have that derivative:E[ℓ(ϕ(X), Y )] = E X [E Y |X [(Y -ϕ(X)) 2 ]] = E X [E Y |X [Y 2 ] -2E Y |X [Y ϕ(X)] + E Y |X [ϕ(X) 2 ]] = E X [E Y |X [Y 2 ] -2ϕ(X)E Y |X [Y ] + ϕ(X) 2 E Y |X [1]] = E X [E Y [Y 2 ] -2ϕ(X)E[Y |X] + ϕ(X) 2 ]Taking the derivative of the inside expectation w.r.t. ϕ(X) and setting to 0 yields ϕ * (X) = E[Y |X]. Now let's look at cross-entropy loss for classification:E[ℓ(ϕ(X), Y )] = E X [E Y |X [-Y log(ϕ(X)) -(1 -Y ) log(1 -ϕ(X))]] = E X [-log(ϕ(X))E[Y |X] -log(1 -ϕ(X))E[(1 -Y )|X]]]Again, if you take the derivative w.r.t. ϕ(X) and set to 0, we see thatϕ * (X) = E[Y |X].Now we seek to prove Theorem 3.3.Proof. First, we decompose the factual error across the sensitive attribute A given the exogenous noise U .E X,A,Y [ℓ(ϕ(X, A), Y )] = E U,A,Y [ℓ(ϕ(F * X (U, A), A), Y )] = E U [E A [E Y |U,A [ℓ(ϕ(F * X (U, A), A), Y )]]] = E U [p(A = a)E Y |U,A=a [ℓ(ϕ(F * X (U, a), a), Y )] + p(A = 1 -a)E Y |U,A=1-a [ℓ(ϕ(F * X (U, 1 -a), 1 -a), Y )]] . Consider U = u, inside the expectation we have p(A = a)E Y |U =u,A=a [ℓ(ϕ(F * X (u, a), a), Y )] + p(A = 1 -a)E Y |U =u,A=1-a [ℓ(ϕ(F * X (u, 1 -a), 1 -a), Y )] = p(A = a)E Y |X=x,A=a [ℓ(ϕ(x, a), Y )] + p(A = 1 -a)E Y |X=x1-a,A=1-a [ℓ(ϕ(x 1-a , 1 -a), Y )] ,where w.l.o.g., x is viewed as the factual and x a ′ is viewed as the counterfactual. Because of invertibility, these two terms are unique for every (u, a) or correspondingly (x, a) combination and thus the problem decomposes across U . Thus, the factual loss can be viewed as a combination of the factual loss from one specific a plus the counterfactual loss for a ′ for each point x.We have the following subproblems indexed by u: The factual loss can be viewed as a combination of the factual loss from one specific a plus the counterfactual loss for 1 -a for each point x. Notice that the constraint is ϕ(x, a) a.s.= ϕ(x 1-a , 1 -a) from Lemma 3.2. We can directly push the constraint into the optimization problem by optimizing over ϕ 0 ≜ ϕ(x, a) a.s.= ϕ(x 1-a , 1 -a):argmin ϕ p(A = a)E Y |X=x,A=a [ℓ(ϕ 0 , Y )] + p(A = 1 -a)E Y |X=x1-a,A=1-a [ℓ(ϕ 0 , Y )] (2)Taking ℓ as squared L 2 loss: we have argminϕ p(A = a)E Y |X=x,A=a [(Y -ϕ 0 ) 2 ] + p(A = 1 -a)E Y |X=x1-a,A=1-a [(Y -ϕ 0 ) 2 ] = argmin ϕ p(A = a){E Y |X=x,A=a [Y 2 ] -2ϕ 0 E Y |X=x,A=a [Y ] + ϕ 2 0 } + p(A = 1 -a){E Y |X=x1-a,A=1-a [Y 2 ] -2ϕ 0 E Y |X=x1-a,A=1-a [Y ] + ϕ 2 0 } .Similarly, if we take ℓ as (binary) cross-entropy loss: we have argminϕ p(A = a)E Y |X=x,A=a [-(Y log(ϕ) + (1 -Y ) log(1 -ϕ))] + p(A = 1 -a)E Y |X=x1-a,A=1-a [-(Y log(ϕ) + (1 -Y ) log(1 -ϕ))]It is simple to see that both loss functions are convex, thus could obtain a unique solution by taking the derivative. Thus, for each x, x a ′ induced by U = u, we could get the optimal ϕ 0 :ϕ 0 = a ′ ∈{0,1} p(A = a ′ )ϕ * (x a ′ , a ′ ) ,where ϕ * is the optimal predictor from the lemma above. This result holds for every u and thus gives the final result.A.3 Proof of Theorem 3.4Proof. Let ϕ * (x, a) and ϕ * CF (x, a) be the Bayes optimal predictor under no constraint and CF constraint respectively. We have shown that ϕ* (x, a) = E Y |X=x,A=a [Y ] and ϕ * CF (x, a) = p(A = a)ϕ * (x, a) + p(A = 1 -a)ϕ * (x 1-a , 1 -a).Noting that ϕ * is Bayes optimal, its risk satisfies R * ≤ R * CF where R * CF denotes the risk of ϕ * CF (x, a). By definition, the excess risk of ϕ* CF (x, a) is R * CF -R * =E X,A E Y |X=x,A=a [ℓ(ϕ * CF (x, a), Y ) -ℓ(ϕ * (x, a), Y )] .For regression task and real-valued Y , we take ℓ as squared L 2 loss and haveR * CF -R * =E X,A E Y |X=x,A=a [(ϕ * CF (x, a) -Y ) 2 -(ϕ * (x, a) -Y ) 2 ] =E X,A E Y |X=x,A=a [(ϕ * CF (x, a) -ϕ * (x, a))(ϕ * CF (x, a) + ϕ * (x, a) -2Y )] =E X,A (ϕ * CF (x, a) -ϕ * (x, a))E Y |X=x,A=a [(ϕ * CF (x, a) + ϕ * (x, a) -2Y )] =E X,A (ϕ * CF (x, a) -ϕ * (x, a)) 2 =E X,A ((p(A = a)ϕ * (x, a) + p(A = 1 -a)ϕ * (x 1-a , 1 -a) -ϕ * (x, a)) 2 =E X,A (1 -p(A = a)) 2 (ϕ * (x, a) -ϕ * (x 1-a , 1 -a)) 2 =E X,A p 2 (A = 1 -a)(ϕ * (x, a) -ϕ * (x 1-a , 1 -a)) 2 =E A p 2 (A = 1 -a)E X|A=a [(ϕ * (x, a) -ϕ * (x 1-a , 1 -a)) 2 ] . Let's define ∆ a ≜ E X|A=a E Y |X=x,A=a [Y ] -E Y |X=x1-a,A=1-a [Y ] 2 (a) = E U |A=a E Y |U =u,A=a [Y ] -E Y |U =u,A=1-a [Y ] 2 (b) = E U E Y |U =u,A=a [Y ] -E Y |U =u,A=1-a [Y ] 2 = ∆ 1-a ,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 = ∆ 1-a . Notably, ∆ measures the expected change of Y due to the change of A over all possible U , and is in fact a measure of their dependency. Furthermore, we haveE A p 2 (A = 1 -a)E X|A=a [(ϕ * (x, a) -ϕ * (x 1-a , 1 -a)) 2 ] =E A p 2 (A = 1 -a)∆ a = a p(A = a)p 2 (A = 1 -a)∆ a =p(A = 0)p 2 (A = 1)∆ 0 + p(A = 1)p 2 (A = 0)∆ 1 =p(A = 0)p(A = 1)∆ =σ 2 A ∆.Next, for classification task and binary Y using cross-entropy loss, thenR * CF -R * =E X,A E Y |X=x,A=a [-Y log ϕ * CF (x, a) -(1 -Y ) log(1 -ϕ * CF (x, a))] + E Y |X=x,A=a [Y log ϕ * (x, a) + (1 -Y ) log(1 -ϕ * (x, a))] =E X,A [-ϕ * log ϕ * CF -(1 -ϕ * ) log(1 -ϕ * CF ) + ϕ * log ϕ * + (1 -ϕ * ) log(1 -ϕ * )] =E X,A ϕ * log ϕ * ϕ * CF + (1 -ϕ * ) log 1 -ϕ * 1 -ϕ * CF (a) = E X,A [D KL [p(Y | X, A)∥E A [p(Y | X A , A)]] (b) =E U,A [D KL [p(Y | U, A)∥E A [p(Y | U, A)]] =E U,A [D KL [p(Y | U, A)∥p(Y | U )] =E U E A [D KL [p(Y | U, A)∥p(Y | U )] =I(A; Y | U ),where (a) holds from noting that ϕ* (x, a) = p(Y = 1 | X = x, A = a) and ϕ * CF = E A [p(Y = 1 | X = x A , A)],and (b) again holds from the invertibility between X and U given A.Proof.E[ Ŷ |X = x, A = a] = μ(x, a) = p(A = a)ϕ(x a , a) + p(A = 1 -a)ϕ(G(x, a, 1 -a), 1 -a) = p(A = a)ϕ(G(x 1-a , 1 -a, a), a) + p(A = 1 -a)ϕ(x 1-a , 1 -a) = μ(x 1-a , 1 -a) = E[ Ŷ |X = x 1-a , A = 1 -a] ,where the middle qualities are by the properties of the invertible and ground truth CGM. Because the factual output for the algorithm is the same as the counterfactual output, then the TE must be 0 by Lemma 3.2.A.5 Proof of Theorem 3.6Proof. We first bound TE.Let x a→1-a ≜ G * (x a , a, 1 -a), we haveTE =E X,A [|ϕ PCF (x a , a) -ϕ PCF (x a→1-a , 1 -a)|] =E X,A [|p(A = a)ϕ(x a , a) + p(A = 1 -a)ϕ(x a→1-a , 1 -a) -p(A = a)ϕ(x 1-a→a , a) -p(A = 1 -a)ϕ(x a→1-a , 1 -a)|] =E X,A |p(A = a)ϕ(x a , a) + p(A = 1 -a)ϕ( Ĝ(x a , a, 1 -a), 1 -a) -p(A = a)ϕ( Ĝ(G * (x a , a, 1 -a), 1 -a, a) -p(A = 1 -a)ϕ(G * (x a , a, 1 -a), 1 -a)| (a) ≤ E X,A p(A = a)|ϕ(x a , a) -ϕ( Ĝ(G * (x a , a, 1 -a), 1 -a, a), a)| +p(A = 1 -a)|ϕ( Ĝ(x a , a, 1 -a), 1 -a) -ϕ(G * (x a , a, 1 -a), 1 -a)| =E X,A p(A = a)|ϕ(G * (G * (x a , a, 1 -a), 1 -a, a), a) -ϕ( Ĝ(G * (x a , a, 1 -a), 1 -a, a), a)| +p(A = 1 -a)|ϕ( Ĝ(x a , a, 1 -a), 1 -a) -ϕ(G * (x a , a, 1 -a), 1 -a)| (b) ≤E X,A p(A = a)L|G * (G * (x a , a, 1 -a), 1 -a, a) -Ĝ(G * (x a , a, 1 -a), 1 -a, a)| +p(A = 1 -a)L| Ĝ(x a , a, 1 -a) -G * (x a , a, 1 -a)| (c) ≤ E X,A [p(A = a)Lε + p(A = 1 -a)Lε] =Lε.Here (a) holds by the convexity of absolute value, (b) is from the L-lipschitz property of ϕ, and (c) is by the bound of counterfactual estimation error. Now we prove the bound for the error. Taking ℓ as squared L 2 loss, we haveR = E X,A E Y |X=x,A=a (ϕ PCF (x, a) -y) 2 = E X,A E Y |X=x,A=a (ϕ PCF (x, a) -ϕ * CF (x, a) + ϕ * CF (x, a) -y) 2 ,Taking the inner expectation and omit subscript for brevity, we haveE (ϕ PCF (x, a) -ϕ * CF (x, a) + ϕ * CF (x, a) -y) 2 =E (ϕ PCF (x, a) -ϕ * CF (x, a)) 2 + 2E [(ϕ PCF (x, a) -ϕ * CF (x, a))(ϕ * CF (x, a) -y)] + C =p(A = 1 -a) 2 (ϕ * (x 1-a , 1 -a) -ϕ * (x 1-a , 1 -a)) 2 + 2p(A = 1 -a)(ϕ * (x 1-a , 1 -a) -ϕ * (x 1-a , 1 -a))(ϕ * CF (x, a) -ϕ * (x, a)) + C ≤p(A = 1 -a) 2 (ϕ * (x 1-a , 1 -a) -ϕ * (x 1-a , 1 -a)) 2 + 2p(A = 1 -a)|ϕ * (x 1-a , 1 -a) -ϕ * (x 1-a , 1 -a)(ϕ * CF (x, a) -ϕ * (x, a)| + C (a) ≤ p(A = 1 -a) 2 L 2 ε 2 + 2p(A = 1 -a)Lε|ϕ * CF (x, a) -ϕ * (x, a)| + C,where C denotes the remaining term that only depends on ϕ * CF . Here (a) holds from the fact that the counterfactual estimation error is bounded by ε and the assumption that ϕ * is L-lipschitz.Next, take the outer expectation,R ≤ E A [p(A = 1 -a) 2 ]L 2 ε 2 + 2LεE X,A [p(A = 1 -a)|ϕ * CF (x, a) -ϕ * (x, a)|] + R * CF = σ 2 A L 2 ε 2 + 2LεE X,A [p(A = 1 -a) 2 |ϕ * (x 1-a , 1 -a) -ϕ * (x, a)|] + R * CF .Note that taking expectation of C with respect to the joint distribution of X, A is in fact the optimal risk R * CF . Reorganization gives usR -R * CF ≤σ 2 A L 2 ε 2 + 2LεE X,A [p(A = 1 -a) 2 |ϕ * (x 1-a , 1 -a) -ϕ * (x, a)|] =σ 2 A L 2 ε 2 + 2LεE X,A [p(A = 1 -a) 2 |E[Y | X = x 1-a , A = 1 -a] -E[Y | X = x, A = a]|] =σ 2 A L 2 ε 2 + 2LεE U,A [p(A = 1 -a) 2 |E[Y | U = u, A = 1 -a] -E[Y | U = u, A = a]|] =σ 2 A L 2 ε 2 + 2LεE U [p(A = 1)p(A = 0) 2 |E[Y | U = u, A = 0] -E[Y | U = u, A = 1]| + p(A = 0)p(A = 1) 2 |E[Y | U = u, A = 1] -E[Y | U = u, A = 0]|] =σ 2 A L 2 ε 2 + 2σ 2 A LεE U [|E[Y | U = u, A = 1] -E[Y | U = u, A = 0]|].When ℓ is cross-entropy loss, the excess risk isR -R * CF =E X,A E Y |X=x,A=a -Y log ϕ PCF ϕ * CF -(1 -Y ) log 1 -ϕ PCF 1 -ϕ *Here we assume the logit (i.e., the inverse function of sigmoid) is L-lipschitz continuous in x, i.e.,|f * (x, a) -f * (x, a)| ≤ L∥x -x∥, ∀x, x, a where ϕ * ≜ σ • f * and f * (x, a) = log ϕ * (x,a) 1-ϕ * (x,a). Now we check the excess risk. The first term can be upper bounded byY log ϕ * CF ϕ PCF = Y log p(A = a)ϕ * (x, a) + p(A = 1 -a)ϕ * (x 1-a , 1 -a) p(A = a)ϕ * (x, a) + p(A = 1 -a)ϕ * (x 1-a , 1 -a) ≤ Y (ϕ * CF ) -1 p(A = a)ϕ * (x, a) log p(A = a)ϕ * (x, a) p(A = a)ϕ * (x, a) + p(A = 1 -a)ϕ * (x 1-a , 1 -a) log p(A = 1 -a)ϕ * (x 1-a , 1 -a) p(A = 1 -a)ϕ * (x 1-a , 1 -a) = Y p(A = 1 -a)ϕ * (x 1-a , 1 -a) ϕ * CF log ϕ * (x 1-a , 1 -a) ϕ * (x 1-a , 1 -a) = Y C 1 log ϕ * (x 1-a , 1 -a) ϕ * (x 1-a , 1 -a) ,where the inequality holds by applying log sum inequality. For the inequality, it is derived fromϕ * CF log ϕ * CF ϕ PCF ≤p(A = a)ϕ * (x, a) log p(A = a)ϕ * (x, a) p(A = a)ϕ * (x, a) + p(A = 1 -a)ϕ * (x 1-a , 1 -a) log p(A = 1 -a)ϕ * (x 1-a , 1 -a) p(A = 1 -a)ϕ * (x 1-a , 1 -a)And C 1 is defined as belowC 1 = p(A = 1 -a)ϕ * (x 1-a , 1 -a) P (A = a)ϕ * (x, a) + P (A = 1 -a)ϕ * (x 1-a , 1 -a) Similarly, (1 -Y ) log 1 -ϕ * CF 1 -ϕ PCF = (1 -Y ) log p(A = a) -p(A = a)ϕ * (x, a) + p(A = 1 -a) -p(A = 1 -a)ϕ * (x 1-a , 1 -a) p(A = a) -p(A = a)ϕ * (x, a) + p(A = 1 -a) -p(A = 1 -a)ϕ * (x 1-a , 1 -a) ≤ (1 -Y ) p(A = 1 -a)(1 -ϕ * (x 1-a , 1 -a)) 1 -ϕ * CF log 1 -ϕ * (x 1-a , 1 -a) 1 -ϕ * (x 1-a , 1 -a) = (1 -Y )C 2 log 1 -ϕ * (x 1-a , 1 -a) 1 -ϕ * (x 1-a , 1 -a) .whereC 2 = p(A = 1 -a)(1 -ϕ * (x 1-a , 1 -a)) 1 -ϕ * CF = p(A = 1 -a)(1 -ϕ * (x 1-a , 1 -a)) 1 -P (A = a)ϕ * (x, a) -P (A = 1 -a)ϕ * (x 1-a , 1 -a) = p(A = 1 -a)(1 -ϕ * (x 1-a , 1 -a)) p(A = a) -P (A = a)ϕ * (x, a) + p(A = 1 -a)(1 -ϕ * (x 1-a , 1 -a)) Put together Y log ϕ * CF ϕ PCF + (1 -Y ) log 1 -ϕ * CF 1 -ϕ PCF ≤Y C 1 log ϕ * (x 1-a , 1 -a) ϕ * (x 1-a , 1 -a) + (1 -Y )C 2 log 1 -ϕ * (x 1-a , 1 -a) 1 -ϕ * (x 1-a , 1 -a) ≤ Y C 1 log ϕ * (x 1-a , 1 -a) ϕ * (x 1-a , 1 -a) + (1 -Y )C 2 log 1 -ϕ * (x 1-a , 1 -a) 1 -ϕ * (x 1-a , 1 -a) (a) ≤ Y C 1 log ϕ * (x 1-a , 1 -a) ϕ * (x 1-a , 1 -a) -(1 -Y )C 2 log 1 -ϕ * (x 1-a , 1 -a) 1 -ϕ * (x 1-a , 1 -a) (b) ≤ max {Y C 1 , (1 -Y )C 2 } log ϕ * (x 1-a , 1 -a) ϕ * (x 1-a , 1 -a) -log 1 -ϕ * (x 1-a , 1 -a) 1 -ϕ * (x 1-a , 1 -a) ≤ log ϕ * (x 1-a , 1 -a) ϕ * (x 1-a , 1 -a) -log 1 -ϕ * (x 1-a , 1 -a) 1 -ϕ * (x 1-a , 1 -a) = log ϕ * (x 1-a , 1 -a) 1 -ϕ * (x 1-a , 1 -a) -log ϕ * (x 1-a , 1 -a) 1 -ϕ * (x 1-a , 1 -a) ≤ L∥x 1-a -x1-a ∥.Step (a) holds from the observation that the two log terms must have different signs: unless ϕ * (x 1-a , 1 -a) = ϕ * (x 1-a , 1 -a) = 0.5, otherwise it is impossible to have bothϕ * (x 1-a , 1 -a) ≥ ϕ * (x 1-a , 1 -a) 1 -ϕ * (x 1-a , 1 -a) ≥ 1 -ϕ * (x 1-a , 1 -a), hold simultaneously.Step (b) holds from the fact that the two terms now have the same sign so we can safely upper bound them, and this maximum is upper bounded by 1. Finally, the excess riskE X,A E Y |X=x,A=a Y log ϕ * cf ϕ pcf + (1 -Y ) log 1 -ϕ * cf 1 -ϕ pcf ≤ E X,A E Y |X=x,A=a [L∥x 1-a -x1-a ∥] ≤ Lε, so long as ∥x 1-a -x1-a ∥ ≤ ε.This completes the proof.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, i.e.,argmin ϕ:TE(ϕ)=0 E X,A,Y [ℓ(ϕ(X, A), Y )] = argmin ϕ:TE(ϕ)=0 E X,A,Y [ℓ(ϕ(X, A), Y )+ℓ(ϕ(G(X, A, 1-A), A), Y )]We know the analytic solution of Bayes optimal predictor in our synthetic data experiments. More specifically, for Linear-Reg, we haveϕ * (x, a) = E[Y |X = x, A = a] = w X x + w ′ U w U (x -w A a)For Cubic-Reg, we haveϕ * (x, a) = E[Y |X = x, A = a] = w X x 3 + w ′ U w U (x -w A a)For Linear-Cls, we haveϕ * (x, a) = E[Y |X = x, A = a] = σ(w X x + w ′ U w U (x -w A a))For Cubic-Cls, we haveϕ * (x, a) = E[Y |X = x, A = a] = σ(w X x 3 + w ′ U w U (x -w A a))In our synthetic experiments, we mainly use KNN based predictors. We use the default parameters in scikit-learn. All MLP methods uses a structure with hidden layer (20, 20) and Tanh activation.In semi-synthetic experiments, we use MLP methods uses a structure with hidden layer (5, 5) and Tanh activation as this is closer to the ground truth SCM.In Figure 6 , 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 is similar to what we observe in Figure 2 . This further validates our theory regarding optimality of PCF.In Figure 7 , following the investigation in Figure 3 , we test with adding gaussian noise with different mean. We observe that when it is a fixed bias, CFU and CFR achieves better fairness than PCF. Though PCF still achieves best predictive performance. Furthermore, as we increase variance of the noise, PCF outperform these two methods in terms of both fairness and ML performance. In Figure 8 , similar to Figure 4 , we observe PCF-Analytic significantly improves over PCF. Notably, it is not affected by bias as PCF.In Figure 9 , we included the expanded version of Figure 5 with TE 0 and TE 1 . We observe that they show a very similar trend. In Figure 10 , we directly compare PCF (with ERM) and PCF-CRM. The results validate the necessity of CRM as a plugin estimator ϕ in the case of limited causal knowledge.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 is that, in this case, the encoder of the ground truth DCEVAE takes y as an input. This modification introduces an inconsistency between the ground truth CGM and the estimated CGM. In Figure 11 , we observe a trend similar to that in Figure 5 , which indicates the effectiveness of PCF-CRM. NeurIPS Paper ChecklistJustification: 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 NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).Code can be found in https://github.com/inouye-lab/pcfNote that while the discussion in this paper focuses on the causal model in Figure1, our theorem is valid for more general cases that satisfy Assumption3.1. And for brevity, the following discussion is done under this assumption unless otherwise stated.Here we assume the logits are L-lipschitz continuous in x.Essentially PCF with ERM (PCF-ERM). For brevity, we just call it PCF. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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. 
- 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.

**---------- post-rebuttal ----------**

I would like to thank the authors for their comments and clarifications. 
The author's rebuttal adequately addressed my concerns.
questions: 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. 
- 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? 
- Q3 (minor, optional). Can the proposed framework be adapted to the path-dependent CF constraint? 

[Zuo+ 23] Zhiqun Zuo, Mahdi Khalili: Xueru Zhang. Counterfactually Fair Representation. NeurIPS, 2023.
limitations: limitations: Yes, the authors discussed the limitations and potential impacts of their work in Section 6 and Question 10 of Checklist, respectively.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
questions: 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? 

- 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: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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.


[1] Wang, Yixin, Dhanya Sridhar, and David Blei. "Adjusting Machine Learning Decisions for Equal Opportunity and Counterfactual Fairness." Transactions on Machine Learning Research (2023).

[2] Chen, Haoyu, et al. "On learning and testing of counterfactual fairness through data preprocessing." Journal of the American Statistical Association (2023): 1-11.
questions: questions: 1. See Weakness 2.

2. 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.

3. 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?


[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: 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.

Comments: comment: Dear Reviewer e7ax,

We're pleased to hear that we've addressed your concerns. Thank you for your time and effort!

Best regards,

The Authors
Dear Reviewer Kz4o,

We're pleased to hear that we've addressed your concerns. Thank you for your time and effort!

Best regards,

The Authors
Dear Reviewer pyBD,

We're pleased to hear that we've addressed your concerns. Thank you for your time and effort!

Best regards,

The Authors
Thank you for the detailed rebuttal and for addressing my questions. After considering your responses, I have carefully reviewed my initial evaluation and decided to maintain my original score.
Dear Authors,

Thank you for your clarification and additional experiments. Your responses have been helpful, and I have accordingly increased my score.

Best
Dear Authors, 

Thank you for your clear response, which has adequately addressed my concerns (especially, W1) and my questions. 
Thus, I changed my score accordingly.
Dear Reviewer pyBD,

We kindly request your feedback on whether our response has satisfactorily addressed your concerns. If any issues remain or further clarification is needed, please let us know, and we will try to address them before the discussion period ends.

We are looking forward to hearing from the reviewer.

Best regards,

The Authors
Dear Reviewer Kz4o,

We kindly request your feedback on whether our response has satisfactorily addressed your concerns. If any issues remain or further clarification is needed, please let us know, and we will try to address them before the discussion period ends.

We are looking forward to hearing from the reviewer.

Best regards,

The Authors
Dear Reviewer e7ax,

We kindly request your feedback on whether our response has satisfactorily addressed your concerns. If any issues remain or further clarification is needed, please let us know, and we will try to address them before the discussion period ends.

We are looking forward to hearing from the reviewer.

Best regards,

The Authors