FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation

We appreciate the feedbacks by the reviewer, here are our responses:

1. "Could you discuss more on the challenges and potential inaccuracies associated with density estimation, especially in high-dimensional spaces or with complex data types."

   Reply. Thank you for this question. We mention how the quality of density estimation will affect the performance of our ICP (and CP) sampling scheme in line 241-243, and we also provide a theoretical analysis linked to it in the Appendix C.1. Specifically, we show an smaller TV distance bound for ICP compared with CP when density estimation is inaccurate, which aligns with our claims and experimental evidence (Figure 2).

2. "And for the categorical case, multi sensitive attributes can be actually turned to one attribute case by separating the dataset into more subgroups. I am curious about the performance of standard fairness-aware method in this naive way. Maybe you can add this as baseline."

   Reply. We thank the reviewer for this suggestion. We now have also added two more baselines in experiments: FDL [3] and Kearns et al. [2]. Link for experiments added. We also tried Kearns et al. [2] for Adult dataset but it failed to converge with limited number of iteration for the short time given (as evidenced by Figure 1 in its paper), however, we agree this is an important baseline and are working to add it to our revised paper, and we will also update the results once it is done.

3. While the paper compares FairICP with several baseline methods, it does not include some state-of-the-art methods for fairness-aware learning.

   Reply. Thanks for your feedback. We fully understand the need to compare with other methods. However, based on the literature we have searched so far, what we compared in our paper are already the most recent methods that can be applied to our setting (equalized odds, multiple (mixed) sensitive attributes). We would also appreciate it if the reviewer could point out some other cutting-edge fair machine learning methods suitable to our task. Additionally, the major novelty of this work is the ICP sampling for fairness-aware (equalized odds) learning with multiple sensitive attributes. Hence, we should consider the comparison between FairICP and FDL [3] to be the most informative and reliable evaluation of this paper's contribution in a setting where FDL is straightforward to apply.

4. The ICP strategy is specifically designed for EO and may not be generalized to other fairness measures enough.

   Reply. Thank you for pointing this out. Our focus on the equalized odds metric is intentional, as enforcing equalized odds requires ensuring conditional independence. This conditional nature makes it a more challenging fairness criterion compared to unconditional ones like demographic parity (Tang et al.[1]).

   While ICP is well-suited for enforcing equalized odds due to its ability to avoid the challenging density estimation of given, for unconditional fairness notions such as demographic parity, we can utilize unconditional permutation of which is a special case of FairICP without conditioning.

5. Providing detailed information on the exact hyper parameter values or the code for reproducing the results would be more convincing.

   Reply. We apologize for not including code in the initial submission. We have now provided the relevant code Link for code.

Reference

[1] Tang et al. Attainability and optimality: The equalized odds fairness revisited.

[2] Kearns et al.. Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness.

[3] Romano et al. Achieving equalized odds by resampling sensitive attributes.

We appreciate the feedback by the reviewer. Here are our responses:

1. Methods: more baselines.

   Reply. We thank the reviewer for this valuable suggestion. We add two more baselines in experiments: FDL [4] and Kearns et al. [5]. Link for experiments added. For ACS income/Adult, we also ran [5] as the reviewer suggests, but we find it failed to converge with limited time given (also evidenced by Figure 1 in its paper). Nonetheless, we agree this could be a good complement and we will update it once it's done.

   We also thank the reviewer for the generalized DP paper ([3]), however, we find that its goal to extend demographic parity is fundamentally different from our goal (equalized odds), and it's also non-trivial to extend it to the best our knowledge. We have included it into our related work section.

2. Metric:

   (1) Accuracy for classification

   Reply. We apologize for the confusion. Our "Loss" metric is misclassification rate for classification task, which is (1 - accuracy) . We will make it clearer in our revised version.

   (2) Why TPR, FPR, or DEO were not mainly used?

   Reply. Thank you for this question. The reason why we introduce KPC is that it's a flexible metric for conditional independence without constraints for the shape of input, which well aligns with our goal to measure equalized odds for complex $A$. While DEO (TPR, FPR) is a standard measure in the previous work, it's only suitable for binary $Y$/$A$, thus can only be used in a part of our experiments (Adult/COMPAS).

   (3) Presenting TPR and FPR.

   Reply. Thank you for this suggestion. Yes, DEO is a sum of FPR and TPR accross all binary $A$. However, when there are multiple binary $A$, it could be rather subjective to choose which subgroup's TPR(FPR) to be presented, thus making DEO a standard measure ([1, 2]).

3. Math behind line 583

   Reply. We apologize for the confusion. In Task 2, we first prove $\tilde{A} | Y \overset{d}{=} A | Y$, which is done by taking expectation of results from Task 1 ($P(A \leq t \mid Y, S(A)=S)=P(\tilde{A} \leq t \mid Y, S(A)=S)$). We have now explained this in the proof for clarification.

4. How stable is the adversarial learning process?

   Reply. Thank you for this question. We agree that stability could be a potential pitfall for all the adversarial learning approaches, as pointed out in line 432-439. We adopted a vanilla GAN instead of more exquisite ones to provide a fair comparison with FDL [4], but our ICP can integrate with the more efficient methods in the area of adversarial learning. We have now clarified it further in the discussion section.

5. How our method differs from existing adversarial learning-based approaches.

   Reply. Thanks for raising this point.

   While we adopted adversarial learning (Algorithm 1) as in FDL [4], the main contribution of our work is a better way of generating synthetic $\tilde A$ for equalized odds with multi-dimensional (mixed) $A$ (line 090-096). FDL does not discuss how to estimate $q(A \mid Y)$ when $A$ is complex, which is important for fair ML. Also, the nature of conditioning for equalized odds makes it more difficult than the demographic parity setting (e.g., prior work using VAE [6]). As far as we are aware, no other proposal has been designed for our setting.

   The ICP sampling scheme guides both training and evaluating equalized odds (Algorithm 2). The reported KPCs reflect the same trend of the hypothesis testing (Algorithm 2) when the ground truth is known (Figure 3). This result is useful as ground truth is unknown in practice, which makes results from Algorithm 2 subject to density estimation while KPC itself is not (line 354-360).

6. How does the generated $\tilde A$ differ from the fair representation learned through adversarial learning?

   Reply. Thank you for this question and providing the literature. Learning fair representation is another line of work based on adversarial learning, which generally requires model to predict $A$ from the representation $Z$ (and possibly $Y$) (e.g., the work reviewer mention). When facing complex $A$, this direct way of modelling $A$ could run into the same challenge as FDL [4] does, while our FairICP avoids it as discussed. We thank you again for this suggestion and we have included this discussion into our related work part.

Reference

[1] Cho et al. A fair classifier using kernel density estimation.

[2] Agarwal et al. A reductions approach to fair classification.

[3] Jiang et al. "Generalized demographic parity for group fairness."

[4] Romano et al. Achieving equalized odds by resampling sensitive attributes.

[5] Kearns et al. Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness.

[6] Creager et al. "Flexibly fair representation learning by disentanglement."

We appreciate your thorough review and constructive feedback on our paper, here are our responses:

1. Explanation on KPC.

   Reply. Thank you for this constructive feedback. KPC [1] is a recently proposed non-parametric measure for conditional independence without constraints on the shape of inputs. The reason why we choose $KPC(U,V|W)$ aligns with our main goal in this paper: enforcing equalized odds (a conditional independence notion) for multiple $A$ (i.e., making $KPC(\hat{Y}, A|Y)$ small). Additionally, $KPC(U, V|W)$ has been well normalized for direct comparison across different models (supported by our experiments (line 354-360)), and it can be viewed as a generalization of Partial Correlation between $U|W$ and $U|W,V$.

   To see this, we first recall that MMD distance $MMD(U, V)=||\mu_{U}-\mu_{V}||_{\mathcal{H}}^2$ where $\mathcal{H}$ is RKHS and $\mu_U = \int k(,;u)d P_U(u)$ is the kernel mean embedding of a distribution $P\_U(.)$ [9] and consider the simple case where the kernel is linear and $U = \alpha W + \beta V+\varepsilon$ with $W, V, \varepsilon$ being i.i.d $\mathcal{N}(0, 1)$. We then have $P\_{U|W,V}=\mathcal{N}(\alpha W+\beta V, 1)$, $P\_{U|W}=\mathcal{N}(\alpha W, 1+\beta^2)$ and $P\_{U}=\mathcal{N}(0, 1+\beta^2)$. Then, the numerator in $KPC(U,V|W)$ becomes: $E[MMD^2(P\_{U|W,V}, P\_{U|W})]=E[(\alpha W+\beta V-\alpha W)^2]=\beta^2$. The denominator becomes: $E[MMD^2(\delta\_{U}, P\_{U|W})]=E[(U-\alpha W)^2]=\beta^2+1$.

   Hence, we can see that $KPC(U, W, V)$ reduces to the squared correlation between $U|V$ and $U|W,V$: $KPC(U, W, V)=\rho^2_{U,W|V}$. In this simple case, $U$ is conditionally independent of $V$ given $W$ iff the partial correlation/KPC is 0 ($\beta$ = 0).

   KPC is not the only choice in our setting, and one can choose other conditional dependence measures that allow multi-dimensional inputs (e.g., CODEC [2], though it can be viewed as a special case of KPC). In our paper, the robustness of KPC is evidenced by comparing the similar curve given by other metrics (power of hypothesis testing and DEO, figure 4/7/8 and table 1).

   We thank the reviewer again for this valuable question and we have included some of the intuition in our revised paper.

2. "Why the experiments not compare ICP to some methods?"

   Reply. We apologize for this confusion. This is due to the differences in their applicability: HGR [3] is designed for univariate continuous $A$ and Reduction [4] is only for binary classification and binary attributes. We introduce HGR [3] (in line 105-109) and detail how we generalize it to multiple attributes (line 436-439). We cite Reduction [4] in line 083 and detail it in line 422-425. We now have made it clearer in our revised paper.

   We have also added two more baselines in experiments: FDL [7] and Kearns et al. [10] (introduced in line 096). Link for experiments added. We also ran [10] for Adult but find it failed to converge with limited time given (also evidenced by Figure 1 in its paper). Nonetheless, we agree this could be a good complement and we will update it once it's done.

3. "Consider post-processing"

   Reply. Thank you for raising this interesting direction. As post-processing and in-processing conventionally represents two different paradigms: the former focuses on training $f(X)$, whereas the latter focuses on recalibrating the probability cutoffs across binary $A$ for binary response (e.g., [6]) and requires test-time access to $A$. Thus, we view it as complementary rather than competing with each other. In fact, one recent work by Tifrea et al. [8], as the rare post-processing work that can work with both a categorical/continuous $A$, proposed to post-process any baseline model, either ERM or in-processing ones.

   Like many in-processing methods, existing post-processing ones are not designed for complex $A$, especially under the equalized. This also raises the question if the idea of ICP can be also utilized in post-processing. We now have included these discussions as future directions in our discussion section.

Reference

[1] Huang et al. "Kernel Partial Correlation Coefficient---a Measure of Conditional Dependence."

[2] Azadkia et al. A simple measure of conditional dependence. The Annals of Statistics

[3] Mary et al.. Fairness-aware learning for continuous attributes and treatments.

[4] Agarwal et al. A reductions approach to fair classification.

[6] Kim et al.: Black-Box Post-Processing for Fairness in Classification.

[7] Romano et al. Achieving equalized odds by resampling sensitive attributes.

[8] Tifrea et al. "Frappé: A group fairness framework for post-processing everything."

[9] Tolstikhin et al. "Minimax estimation of maximum mean discrepancy with radial kernels."

[10] Kearns et al. Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness.

We appreciate the feedback from the reviewer. Here are our responses:

1. Novelty of the paper over FDL.

   Reply. Thank you for sharing your concern. We agree that our core insight is not complicated, yet it has not been previously explored and is effective.

   1. While we adopted adversarial learning (Algorithm 1) as in FDL [1], the main contribution of our work is a better way of generating synthetic $\tilde A$ for equalized odds with multi-dimensional (mixed) $A$ (line 090-096). FDL does not discuss how to estimate $q(A \mid Y)$ when $A$ is complex, which is important for fair ML. Also, the nature of conditioning for equalized odds makes it more difficult than the demographic parity setting (e.g., prior work using VAE [4]). As far as we are aware, no other proposal has been designed for our setting.

      The ICP sampling scheme guides training and can measure equalized odds (Algorithm 2). The reported KPCs reflect the same trend of the hypothesis testing (Algorithm 2) when the ground truth is known (Figure 3). This result is useful as ground truth is unknown in practice, which makes results from Algorithm 2 subject to density estimation, but the KPC itself is not (line 354-360).

   2. While our proof uses Bayes rule, the ICP procedure has not been proposed before. The simplicity in the proof does not contradict its usefulness. For example, one influential result in the classical density ratio estimation is framed as a classification problem [7]. The validity of this transformation is also just Bayes rule, but doesn’t reduce its novelty or utility.

2. "The estimation of $Y | A$ gets worse with high-dim A."

   Reply. We apologize for the confusion. If the problem is intrinsically hard, e.g., there are $n$ samples with each $(Y_i, A_i)$ being drastically different, even the distribution of $Y|A$ will be poorly estimated. However, estimation of the $(A|Y)$ is not easier in this setting.

   The gain of using $Y|A$ are twofold (line 110-124):

   1. Machine learning approaches can more effectively leverage the structure of $Y | A$ than the direct estimation of $A|Y$. E.g., when $(Y, A)$ are jointly Gaussian with sparse connections, the former can provide better quality from using lasso (MSE bound $\sqrt{\frac{s\log p}{n}}$ under sparsity condition $s$, [e.g.,8]) whereas the latter is prone to more errors even when using graphical lasso (Frobenius bound $~\sqrt{\frac{(s^2+p)\log p}{n}}$, e.g., [6]), which can also be evidenced by our Figures 2. These bounds on density estimation will in turn upper bound the quality of the conditional permutation (Appendix C.1).

   2. Modeling $Y \mid A$ avoids directly estimating complex dependencies in multidimensional $A$ (e.g., continuous and binary variables). Instead, dependence in $A$ is naturally incorporated through $Y \mid A$, simplifying implementation.

   We have now clarified this further in section 2.2.

3. More baselines

   Reply. We thank the reviewer for this valuable suggestion. We add two more baselines in experiments: FDL [1] and Kearns et al. [2]. Link for experiments added. We also ran [2] for Adult but found it failed to converge with limited time given (also evidenced by Figure 1 in its paper). Nonetheless, we agree this could be a good complement and we will update it once it's done.

   For LAFTR, we find it can only be applied to a single binary $A$, which differs from our main target in this paper.

4. "The DEO is still quite large."

   Reply. We apologize for the confusion. We calculated DEO (line 823) as the sum of TPR and FPR differences as in [9], while some work [10] defines it as the max of differences, which explains why our results appear to be large. Our method still provides generally smaller DEOs, which indicates the consistency of KPC and DEO (Figure 8 and Table 1).

References

[1] Romano et al. Achieving equalized odds by resampling sensitive attributes.

[2] Kearns et al. Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness.

[3] Madras et al. Learning Adversarially Fair and Transferable Representations.

[4] Creager et al. "Flexibly fair representation learning by disentanglement."

[5] Tansey et al. "The holdout randomization test for feature selection in black box models."

[6] Wang et al. "Precision matrix estimation in high dimensional gaussian graphical models with faster rates."

[7] Menon et al. Linking losses for density ratio and class-probability estimation.

[8] Wainwright et al. High-dimensional statistics: A non-asymptotic viewpoint.

[9] Cho et al. A fair classifier using kernel density estimation.

[10] Agarwal et al. A reductions approach to fair classification.