Flexible Fairness-Aware Learning via Inverse Conditional Permutation

Authors: Yuheng Lai, Leying Guan
Primary area: alignment, fairness, safety, privacy, and societal considerations
Keywords: Algorithmic fairness, Equalized odds, Adversarial learning, Inverse conditional permutation

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

Decision: reject
Reviewer scores: 5, 3, 3, 6

Reviews and discussion:
<thread>
creation date:
1730167164412

thread_type:
official_review

<thread_object>
creator: reviewer_jxqo

<content>
summary:
This work proposes an in-processing method to enforce equalized-odds, a popular notion of fairness in the algorithmic fairness literature. In particular, they propose a method called Fair Inverse Conditional Permutation (FairICP) that is an extension/improvement of Fair Dummies Learning (FDL) proposed by Romano et al. 2020. FairICP addresses two shortcomings of FDL:

1) It can handle multiple complex sensitive attributes unlike FDL
2) Unlike FDL which requires learning the distribution of A | Y, FairICP leverages an inverse conditional permutation (ICP) strategy that relies on learning Y | A which is easier and more tractable.

The work provides theoretically guarantees that demonstrate that the equalized odds condition holds asymptotically for triples $(\hat{Y}, \tilde{A}, Y)$ where the $\tilde{A}$ are generated by ICP and furthermore the authors empirically validate their method with experiments.

strengths:
First and foremost, this paper is very well organized and easy to understand. Furthermore, I think this paper has many strengths

1) Using ICP to generate $\tilde{A}$ in a more tractable manner is very interesting. In much of the conditional randomization literature, the difficult part is estimating the conditional distribution, yet the the authors have proposed a method that can circumnavigate this issue and generate dummy random variables that can be used for the method

2) I appreciate the theoretical guarantees the authors provide to really reinforce that their proposed method will work

3) The authors ran many experiments to highlight the effectiveness of their approach

weaknesses:
My main concern with this work is if the contribution is substantial. If I am not mistaken, the main contribution of this work is simply using ICP instead of generating dummies using $A | Y$. Besides this, they authors simply use the methods of Romano et al. 2020 where the sampling approach is changed to ICP. The authors argue that ICP is better because 

1) it relies on estimating $Y | A$ which I agree for the most part but at the same
2) it can handle multiple complex sensitive attributes

I have some issues with point 2. Assume $A = (A_1, ..., A_k)$ then sampling dummies from $A | Y$, I agree, can be difficult. However, why should we sample the vector A from $A | Y$. In doing so, we are enforcing a strong condition, that $\hat{Y}$ be independent of the joint $A_1,..., A_k$ given Y, when in reality, if we have $k$ sensitive attributes, I would think we would simply want to enforce $\hat{Y}$ independent of $A_k$ given Y for all $k$. If $\hat{Y}$ be independent of the joint $A_1,..., A_k$ given Y, then we get $\hat{Y}$ independent of $A_k$ given Y for all $k$ due to conditional rules, but we are also additionally enforcing many, potentially unnecessary conditional independencies that are not needed. In my opinion, for multiple sensitive attributes, we would just want  $\hat{Y}$ independent of $A_k$ given Y for all $k$, in which case learning $A_k | Y$ is not nearly as difficult anymore and maybe ICP wouldn't be needed.

Overall, I question the necessity for ICP and if the authors can provide more detail as to why ICP is the way to go then that would be great. However, then I do question if the use of ICP with all the methods in Romano et al. 2020 is a large enough contribution. If the reviewers could elaborate on how their method greatly differs from FDL and offers a major improvement, that would be great.

questions:
See weaknesses. I will gladly raise my score if the authors can address my main concern regarding ICP.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730660916909

thread_type:
official_review

<thread_object>
creator: reviewer_mx2y

<content>
summary:
Fairness methods that focus on qualized odds usually select a single protected attribute, which has problems (fairness gerrymandering, etc.) This paper introduces FairICP which is a method in a line of work of fairness-aware learning schemes (specifically, FDL, Romano et. al 2020) for equalized odds across complex sensitive attributes e.g. sensitive attributes jointly along multiple protected attributes. They introduce a slightly modified Conditional Permutation method (from Berrett et. al 2020, who introduce CP), which they call their Inverse CP (ICP) technique. This technique generates conditionally permuted versions of sensitive attributes given the an observed outcome. This circumvents estimating the complex conditional distributions. In terms of contributions, the paper (1) introduces the ICP strategy for multi-attribute fairness, (2) has some theoretical remarks on equalized odds under ICP, and (3) has some empirical results on  trade-offs between fairness and accuracy for ICP vs. FDL and the Reductions frameworks (Agarwal et. al, 2018).

strengths:
S1/Overall: I felt conflicted about this paper. On the one hand, the authors present a reasonable problem (accounting equalized odds violations across multiple attributes), and use some recent statistical advances to develop a principled method to estimate conditional permutations of the sensitive attributes A given Y while avoiding a difficult multi-dim density estimation problem. On the other hand, some of their results are over- or under-stated, and their consideration of the context of fairness in machine learning is certainly inadequate. Thus, though my starting score is low, I am willing to raise it if they can work to address some of the issues I will discuss, although the revision may be too significant of an edit.

S2: Theoretically, the authors provide a nice convergence result as part 2 of Theorem 2.1, the consequence of which is summarized in Remark 2.3.

S3: The “Hypothesis Test for Equalized Odds with ICP” is actually probably the most interesting motivation/application of FairICP in the paper, to me, particularly in contrast to the Fair Dummies test from Romano et. al. This test performs a direct comparison with A, is non-parametric and fairly adaptable. Of course it relies on the quality of the estimation of $P(A | Y)$, but that seems ok given the observations on ICP/CP in Figure 2. This is a nice contribution, and should be highlighted more in the paper (e.g. it would be nice to see how this method allows for more principled testing of existing methods for equalized odds more extensively).

S4: It does appear as though empirically FairICP performs well (Figure 4 in particular), although more on this in W4/W5.

weaknesses:
W1: Essentially, my understanding of the main motivation of the paper is that its difficult to generate accurate samples from A|Y (line 107). The authors then do not spend any more time justifying this, empirically or theoretically. I had to examine prior work and think about this to convince myself.

W2: Comments on the derivation of Theorem 2.1.
For this theorem, the authors wanted to show equivalence of distributions $(\hat{\mathbf{Y}}, A, \mathbf{Y})$ and $(\hat{\mathbf{Y}}, \tilde{A}, \mathbf{Y})$ under the conditional independence $\hat{\mathbf{Y}} \perp A \,|\, \mathbf{Y}$. 

For Task 1, though I often appreciate more details in derivations to help me follow, this may have been overly detailed (distractingly so) given the simpleness of the claim, namely that we know $A$ and $\tilde{A}$ will be exchangeable in this context if $\hat{\mathbf{Y}}$ does not provide additional information about $A$ beyond $\mathbf{Y}$. Additionally, the factorization is overly granular. Given the initial independence assumption, many of the steps the authors present in equations 10 and 11 can be trivially concluded. For instance, if $\hat{\mathbf{Y}} \perp A \,|\, \mathbf{Y}$, then the transition from $(b_1)$ to $(b_4)$ follows almost immediately.

Similarly, for Task 2, though all the conditional probability manipulations are correct, everything could be simplified by directly applying the conditional independence property. Then, Task 3 is a direct application of a result from (Naaman 2021 (line 770)). This application was non-trivial and the authors need to make some interesting observations and introduce some new bounds. I’d like to note that I checked the derivations line by line for Tasks 1 and 2, but for Task 3 I basically reviewed the statement of the Lemma in Naaman 2021, and lightly checked the author’s setup and application of this result.

W3: The authors did not provide code - I wanted to spot check some parameter settings and was unable to. Furthermore, I’d like to assess their experimental setup to ensure its validity. For a conference like ICLR, with a paper that claims empirical contributions, this is a pretty big issue in my opinion.

W4: A major weakness of this work is in the empirical claims in Section 3.3, which are supposed to be on real data. In particular, these authors solely use antiquated fairness datasets like Adult and Compas, without considering the issues with these datasets (Rudin et. al 2020 on COMPAS https://arxiv.org/abs/1811.00731, for example) or new, better alternatives (Ding et. al 2021, “Retiring Adult” i.e. the folktables package). I would like to see some experiments on this realistic data (for example, at minimum on the ACSIncome prediction task from folktables, optionally subsampled). It is important, as a field, that we begin to present results on realistic fairness datasets, instead of the older, normative datasets that have been continually debunked.

W5: (W4) leads to my other critique with the empirical results, which is that the authors only present results on KPC/Power, and not on incredibly standard metrics like error rate or observed equalized odds difference. Additionally, some of the results reported in Table 1 make me skeptical: why are we bolding FairICP results for the Adult dataset when its improved by 1/1000 in terms of loss and the improvement is well within the standard deviation of the HGR method? This table needs work, more metrics and needs to be less deceptively reported.

Nit: In the derivation of Theorem 2.1 in section A, “Taks” should be “Task” in multiple places.

Nit: “simultaneously” used twice in the statement of Theorem 2.4.

questions:
Q1: Theorem 2.4 is a little weird to me. The argument sketch seems as follows: (1) there exists a minimax solution for the loss specified in the FDL paper with some form from some other prior work. (2) This solution is achieved asymptotically. (3) Theorem 2.1 shows how ICP achieves equalized odds asymptotically. (4) Therefore, FairICP is optimal. This is weird to me - in what way does this make FairICP “optimal”? Asymptotically, I could keep guessing at the conditional distribution of interest, for example, and eventually find a suitable one, but that’s not optimal. I think you’re missing a more formal statement of what you mean here by optimal (e.g. sample complexity), but it's still a weird way to state a result thats fundamentally about a fairness definition.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730662986676

thread_type:
official_review

<thread_object>
creator: reviewer_mgqp

<content>
summary:
This paper addresses supervised learning under the constraint of equalized odds, a fairness definition. To achieve fair predictions, the authors apply the strategy proposed by Romano et al. In this approach, dummy labels are generated to be associated with the true label but remain independent of the non-sensitive features. The learned predictor is then constructed such that the distribution of the predicted label, sensitive feature, and true label closely resembles the distribution where the sensitive feature is replaced by the dummy label. The primary contribution of this paper is a novel and more accurate algorithm for generating dummy-sensitive features. Theoretical analysis demonstrates that this algorithm achieves equalized odds, and its resulting predictor is Bayes-optimal. Empirical evaluations show that the proposed algorithm outperforms existing fair learning algorithms that use equalized odds as their fairness criterion.

strengths:
The authors tackle the crucial problem of the unfairness of machine learning algorithms, which is highly relevant to the conference's topics.

The proposed algorithm for generating dummy-sensitive features is methodologically novel. As the authors mention, Romano et al. introduced the technique of conditional randomization, a technique for generating dummy-sensitive features, into the fair learning problem with the fairness definition of equalized odds. The conditional permutation by Berrett et al. is an improved technique of conditional randomization suitable for testing conditional independence, which this paper is the first to introduce into the fair learning problem. The authors further improve the conditional permutation technique by utilizing the conditional density of the label given the sensitive feature for estimating the sampling distribution, whereas Berrett et al.'s technique leverages the conditional density of the sensitive feature given the label. The proposed technique is beneficial when the conditional density of the label given the sensitive feature can be estimated accurately and stably.

The empirical evaluations demonstrate the superior efficiency of the trade-off between accuracy and fairness, especially for high-dimensional sensitive features. This supports the authors' claim that the proposed method is effective for complex sensitive features.

weaknesses:
The paper's main weakness lies in the lack of clarity regarding the situations where the proposed method is more beneficial than existing methods. The authors claim that their method achieves an efficient trade-off between accuracy and fairness when the sensitive features are complex. However, the paper does not clearly define what "complex" means in this context, leaving the reader with unanswered questions about the method's applicability.

The authors mention several aspects regarding the complexity of the sensitive features. One is the complexity stemming from multiple sensitive features. However, if the sensitive features are all categorical, most existing methods can handle them by combining them into a single sensitive feature that takes a combined value of the multiple sensitive features. Furthermore, HGR and FDL can handle multiple real-valued sensitive features, as kernel density estimation can handle a density over multi-dimensional real values. Consequently, the capability to handle multiple sensitive features is not novel.

Another aspect of complexity the authors mention might be handling real-valued sensitive features instead of discrete ones. However, HGR and FDL can handle this complexity as well. Furthermore, there is a method not mentioned by the authors that can handle this complexity: 
- Narasimhan et al. "Pairwise Fairness for Ranking and Regression." AAAI '20. 

Again, the capability to handle real-valued sensitive features is not novel.

To demonstrate the proposed method's benefits, the authors need to discuss more about the efficacy of the trade-off between accuracy and fairness for circumstances with complex sensitive features, rather than just their capability to handle complex sensitive features. Such a discussion appears in part of the explanation of the construction of their proposed method; however, the introduction serves as a discussion about the capability to handle complex sensitive features. As I mentioned, the capability to handle complex sensitive features is not novel.

In the construction part of their proposed method, the authors discuss the efficacy of the trade-off between accuracy and fairness for circumstances with complex sensitive features. They claim that their method, which utilizes the conditional density estimation of $Y|A$, achieves a more efficient trade-off than existing methods employing the conditional density estimation of $A|Y$. However, the paper lacks a logical explanation to support this claim. A clear and convincing argument is necessary to validate the authors' claims and ensure the reader's understanding.

In conclusion, the authors' failure to demonstrate the benefits of their proposed algorithm is a significant shortcoming. The paper lacks rigorous comparisons of their method with existing methods, especially regarding the extent of the complexity of the sensitive features that each method can handle. Demonstrating the situations where existing methods suffer from an ineffective trade-off between accuracy and fairness due to the complexity of the sensitive features is crucial for clarifying the motivation behind the proposed method.

I found several misstatements of the theoretical results and mathematical inaccuracies in the proofs:
- Proposition 2.5 is only valid when the true conditional density is known, which is not specified in the statement. If there is a gap between the true and estimated conditional densities, an error term between them should appear as in Berrett et al.
- The derivation in Lines 678-694 is meaningless when the sensitive features are real-valued and admit density, as the probabilities in Eqs. (10) and (11) are always zero. A similar derivation using the density is necessary, which might be valid.
- In Eq. (12), $P(Y=y, S(A)=S)=0$ for real-valued $Y$ and/or $S$, resulting in zero division. Similarly, in Line 729, $P(Y=t^3)=0$ for real-valued $Y$.
- In Line 765, the formal definition of the $S$-induced empirical cdf should be provided. I'm concerned about violating the assumption of Naaman's result.
- In Line 792, there is no proof that the equality of the lower bound holds at the minimizer. This is a crucial and non-trivial step to validate the statement.

The experimental results of FDL for the Adult and COMPAS datasets are missing, even though the method can be applied to the discrete sensitive attributes. A comparison with the baseline method is crucial to confirm the superiority of the proposed method.

In Section 3.1.1, the authors employ a density estimation method different from the one employed in the other experiments, namely the Masked Autoregressive Flow. It is questionable whether the experimental results in Section 3.1.1 are valid when employing the Masked Autoregressive Flow. This is important because the authors suggest using the Masked Autoregressive Flow for real applications.

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730692934972

thread_type:
official_review

<thread_object>
creator: reviewer_zxud

<content>
summary:
This paper proposed a fairness-aware learning approach FairICP to achieve equalized odds with multiple sensitive attributes. The key technique is combining adversarial learning with an inverse conditional permutation strategy. They also provided theoretical insights and numerical experiments demonstrate its efficacy and flexibility.

strengths:
1. I agree that addressing fairness with multiple sensitive attributes is an interesting problem. It is good to see authors can start by pointing out the issues of using existing methods under this problem.
2. The basic idea is clearly exhibited in Fig. 1, and algorithm 1 is also nicely presented.
3. The theoretical part looks good while I did not check every detail.

weaknesses:
1. They used complex sensitive attributes in the paper. But according to the content, it only refers to multiple independent attributes. The correlation of attributes are not touched. Please clarify this point.
2. I felt confused why this work only focuses on EOd metric when I started reading tit. But it turns out that the ICP might be only appropriate for this setting. Is this a limitation of ICP?
3. Why KPC and loss trade-off is highlighted in experiments? Typically, ACC/Error and EOd are expected to be shown.
4. \tilde A should be "generated" and labelled as "fake" in Eq. 3. Then in the last sentence of caption in Fig. 1, it should be regularizing \tilde A towards A.

questions:
1) Regarding FairICP’s flexibility, are you referring to that the proposed technique can be used for both classification and regression?
2) I understand the advantages of using Eq. 7 over Eq. 6, while I am not certain if Eq. 7 is a perfect alternative. Is there a condition for applying ICP here?
3) If I have corrected understand the proposed method, the trained model would be only fair in terms of EOd on observed sensitive attributes. I mean if a new sensitive attribute is specified during testing, it cannot be handled.
4) Can you explain the meaning of Recap on line 180?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732298241744

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Common responses

comment:
We sincerely thank all the reviewers for your thorough evaluations and valuable feedback on our paper. We greatly appreciate the time and effort you invested in reviewing our work, as well as your acknowledgment of its strengths, including our theoretical contributions, the flexibility of our method, and the novelty of our hypothesis testing procedure.

We are pleased to provide a revised manuscript and a summary response addressing the common points raised across the reviews below. 

1. More explanation on "complex sensitive attributes" and difficulty of sampling from $q(A | Y)$

    In our work, "complex sensitive attributes" refer to attributes that are multi-dimensional and can be of arbitrary types—including continuous, categorical, or mixed. Our proposed method, FairICP, is specifically designed to handle such complex sensitive attributes effectively.


    We have clarified this point in the revised manuscript in line 171-173 by providing a more detailed discussion on the challenges of estimating $q(A∣Y)$. Estimating the conditional distribution $q(A∣Y)$, or even the density $q(A)$, is known to be challenging as the dimension of $A$ increases. Non-parametric density estimation methods, such as kernel density estimation, suffer significantly in high dimensions due to the well-known phenomenon of curse of dimensionality. The required sample size for accurate estimation scales exponentially with the dimension $p$. Also, when $A$ includes multiple correlated or even mixed-type variables, modeling the joint conditional distribution $q(A∣Y)$ becomes complex. For categorical variables, combining categories to model dependencies leads to exponentially decreasing amount data in each category, making estimation unreliable.

2. More experiments on ACS Income dataset for mixed-type sensitive attributes and more metrics provided.

    We have expanded our experimental evaluation to include more extensive experiments on the more realistic ACSIncome dataset. We addressed scenarios involving mixed-type sensitive attributes, including sex, race, and age, which pose additional challenges due to their continuous and categorical nature. To the best our knowledge, this is the first trial to study mixed-type sensitive attributes.

    We also have included more standard metric to measure fairness in our experiments, i.e., using DEO as a standard metric for equalized odds when there is a binary classification task with categorical sensitive attributes (Adult/COMPAS datasets).

3. Simplification of proofs.

    We have carefully revised the proofs in the appendix to make them more concise and accessible by removing overly detailed derivations while ensuring that all critical steps and justifications are clearly presented.

We are grateful for all constructive feedbacks provided by reviewers, which has significantly enhanced the quality of our paper. We believe that the revisions have strengthened our work by providing clearer explanations, more comprehensive experiments, and a deeper discussion of the challenges and solutions related to complex sensitive attributes. We hope that the revised manuscript will address all these concerns, and we look forward to any further comments reviewers may have.
</content>
</thread_object>

</thread>


Metareview:
metareview:
# a) Summarization

This paper addresses the problem of equalized odds in fairness-aware machine learning, specifically in considering multiple, potentially correlated sensitive attributes. Following existing methods for generating dummy feature data by estimating P(A|Y), the paper proposes using inverse conditional permutation (ICP) to estimate P(Y|A). The paper demonstrates favourable theoretical properties of the method and claims improved trade-offs between performance and fairness.

# b) Strengths

1. The problem studied is meaningful, and the challenge of estimating P(A|Y) in prior works is well-motivated.
2. The paper provides theoretical insights into the properties of the proposed approach.
3. Results demonstrate an improved balance between performance and fairness.

# c) Weaknesses

1.*Presentation Issues*: The central problem (difficulty estimating P (A | Y)) is not well-explained from early in the paper. This has been pointed out by several reviews and the authors take efforts in the rebuttal to state the problem. Although the rebuttal brings some sense to the meaningless of the problem, there are substantial works to make them an integrated part of the paper - which has not been finished in the revised version. Several issues in the presentation were noted, including unclear or erroneous theoretical statements, insufficient reasoning for the method's advantages, and a lack of scenarios where the proposed method outperforms existing ones. Although some issues were addressed in the rebuttal, the presentation requires significant revision, particularly in clarifying the problem and evaluating the method's contributions.
   
2.*Experimental Limitations*: The empirical evaluation lacks diversity in data types (e.g., image data), comparisons to alternative methods, and dataset variety. 

# d) Reasons for Decision

The paper tackles an important problem and shows promise through theoretical contributions and performance-fairness trade-offs. However, substantial improvements are needed in both presentation and empirical evaluation, and the paper is not yet ready for publication.