Adapting Fairness Interventions to Missing Values

Summary

This paper presents an information-theoretic finding that reveals the fundamental limitation of impute-then-classify approaches when considering fairness-accuracy tradeoffs. Additionally, it introduces three techniques for addressing missing features within the framework of linear fair classifiers, as well as an ensemble method for non-linear counterparts. One notable aspect of these developments is their ability to capture missing pattern information, which is overlooked by impute-then-classify algorithms. Furthermore, the paper presents experimental results that demonstrate the superior tradeoff performances of the proposed methods, particularly when dealing with datasets that exhibit prominent missing patterns.

Strengths

S1. The paper focuses on a significant issue that arises in numerous applications. S2. By utilizing the concept of mutual information, the paper reveals the fundamental limitation of impute-then-classify methods. S3. The proposed methods effectively harness the information embedded within missing patterns.

Weaknesses

W1. I believe that scenarios where sensitive attributes are missing present more practical relevance, importance, and challenges compared to scenarios where features are missing. Although the authors mention the possibility of extending their findings to such settings in the conclusion section, the specific details of this extension remain unclear as the computation of fairness constraints relies on knowledge of sensitive attributes. W2. The main inspiration for this paper appears to be derived from [3]. While the main contribution of this paper lies in its adaptation to the fairness context, it does not take into account the scenario where sensitive attributes are missing. Exploring this more challenging setting may open up the opportunity for a distinct idea to be explored. W3. The paper introduces several methods for linear and non-linear settings, suggesting that the choice should depend on the data distribution. However, it does not provide concrete guidelines as to how to make the choice. W4. Theorem 1 looks interesting, but the main body of the paper lacks technical discussion, not even including proof sketch.

Questions

In line of W1, can you provide in-depth discussion on the extension of the sensitive-attribute-missing scenario? In light of W4: any intuition why the fundamental degradation of accuracy is expressed in terms of mutual information?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

Please see Weaknesses in the above.

Summary

This paper investigates the impact of missing values on algorithmic fairness and highlights the limitations of the commonly used "impute-then-classify" approach. The authors propose algorithms that preserve the information encoded within missing patterns, leading to improved fairness and accuracy.

Strengths

1. The paper theoretically shows that for the fairness measure of equalized odds, impute-then-classify can significantly reduce the performance. Furthermore, it is also shown that the reduction in the performance grows with the mutual information between the missing pattern and the labels. 2. The paper proposes 3 methods to handle missing values for linear fair classifiers by encoding the missing value patterns. These methods are interpretable and can be combined with any preexisting fairness intervention method including in-processing and post-processing methods. 3. The paper extensively evaluates the proposed method on synthetic data as well as real data. The authors also show the superiorty of the proposed methods for linear setting for the MNAR missing pattern. Overall, the paper is mostly clear and has original ideas.

Weaknesses

1. The proposed method is only applicable to fair classification and when the group attributes are discrete. Furthermore, the approach allows missingness only in the non-group attribute input features, i.e., the method requires the group attribute and the labels to be fully observed. It might be useful to extend the method for fair regression and for missingness in group attribute and labels. 2. The results in the paper focus only on a single measure of fairness, i.e., equalized odds. (By the way, the MEO abbreviation in the figures in the main body should be expanded in the caption when first used.) It might be useful to extend the method for other notions of fairness and provide analogous empirical evaluation.

Questions

1. What is the definition of the function h in equation (1)? Also, Disc(h) should be Disc(h(X)) in equation (1). 2. Can the authors elaborate on how their framework can be extended to multiaccuracy and multicalibration notions of fairness? Are there any empirical evaluations for these settings that the authors have performed? 3. It would help to show empirically how the proposed method performs with respect to the approach of Jeong et al and also state the corresponding runtimes. Also, what does MIA in line 96 stand for? 4. How are the B datasets created in lines 249-250? Line 248 indicates there is only one combined dataset. 5. The algorithm in Section 5 seems closely connected to the idea of using bootstraped subsamples proposed in 'Group Fairness with Uncertainty in Sensitive Attributes'. Could the authors clarify on the similarities and the differences? It might be useful to talk about this in related work. 6. For the HSLS dataset, why do the authors only consider datapoints where race and 9th grade math test score are present? 7. The focus of the paper is on algorithm design for the case of missing non-group attribute input features. I would advise the authors to state this right in the abstract and also talk about it in the introduction. A lot of literature on algorithmic fairness focuses on missing group attribute input features and it is easy to inherently assume that this paper does the same until one reaches line 107.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

The authors talk about the limitations of their work in Section 7. While they briefly talk about potential negative societal impact of data imputation in Section 7 too, I encourage the authors to talk about the potential negative impact of their methodology too.

Summary

This work investigates how different types of missing data affect algorithmic fairness, and provide algorithms that work to address this issue. Three types of missing data are considered: MCAR (missing data is independent of the observed and unobserved values), MAR (missing data depends on the observed values only, and MNAR (dependence of the missing data on the unobserved values). The contributions are (1) Theory showing that a model trained on imputed data (the classic impute-then-classify method) has unavoidable reduced performance; (2) Introduce strategies for adapting mitigation strategies in fair classification to missing data; and (3) provide an empirical analysis that supports the theory and compares against state-of-the-art fair classification algorithms that use impute-then-classify.

Strengths

*ORIGINALITY.* I am not familiar with work in the missing data space, but looked through the related work section, skimmed a few of the works mentioned, and looked briefly at the literature on missing data in ML. This work seems to differ from previous contributions, and is adequately cited. The difference between the approach in this work and the approaches of previous work seems adequately explained. *QUALITY.* The main contribution of this paper is to provide alternative methods to the classically used imputation-then-classify strategy for dealing with missing data in fair classification. This is a well-motivated problem, as imputation is used regularly when data is missing, and this work investigates the information lost when performing imputation, and provides an alternative, competitive strategy for dealing with missing data. *CLARITY.* This work is clearly structured and well-written---I enjoyed the read! *SIGNIFICANCE.* This work is a useful contribution to the literature on mitigating unfairness when values are missing from the feature vector (not including the sensitive attribute). The strategies for finding suitable models in this setting can be used for linear and non-linear classifiers, and the empirical analysis shows promising results that are competitive (and often outperform) methods that use imputation.

Weaknesses

The fairness of models returned by the algorithms is not captured in the graphs in the main body of the work. The paper touts that training classifiers from imputed data can significantly worsen values of group fairness (and average accuracy), but their empirical analysis (in the main body) only compares the accuracy over datasets often used in fair classification. *MINOR COMMENTS* - The core contributions of this work seem to be applicable to general cases of missing data, not just fairness. - Lines 114-117, providing a small example of the different types of reason for missing data could strengthen the description in this paragraph. - Eqn 1 define the indicator function and distribution of interest in the expected value - Fano's inequality (line 193) should be cited

Questions

Could the authors elaborate on the group fairness achieved by their strategy vs the other baselines in the empirical analysis?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

yes

Summary

The paper works on the missing value issues in algorithmic fairness. Typical approaches tend to firstly impute the missing the data, then process for the classification task. However, the authors prove that the imputed data harms the group fairness as well as the averaged accuracy. To avoid losing missing pattern of the data to be imputed, the authors propose to modify the dataset to preserve the feature within the missing patterns, then continue with an off-the-shelf fairness-intervention algorithm to the modified dataset. Experiment results show that the proposed adaptive algorithm improves fairness and accuracy over impute-then-classify methods.

Strengths

* Theoretical illustration on the conclusion that ``imputed data harms the group fairness as well as the averaged accuracy". * The authors propose three methods for adapting linear fair classifiers to missing values: * **Method 1:** Adding missing indicator variables $\to$ this adaptive algorithm improves the accuracy of classifier under the same group fairness constraint than a classifier trained using impute-then-classify; * **Method 2:** Affinely adaptive classification; * **Method 3:** Missing pattern clustering; * A general algorithm for nonlinear classifiers. * Experiments on various datasets demonstrate the effectiveness of the proposed methods.

Weaknesses

* (1) Although the overall presentation is well-done, some parts could be much better if modified accordingly (please refer to **questions**). * (2) Although the motivation of Theorem 1 is good, when I was going through the proof and assumptions made in Theorem 1, I feel like the assumptions are too strong, i.e., in this example, the conclusion should be based on: * (2a) The feature $X$ is of only one dimension; (it would be much better if it could be assumed as a two dimension, since missing values in one dimension feels like completely missing of a feature; while in real-world scenario, missing features are also like to be the case where part of information is missing in a feature $x=[x_1, x_2]$, i.e., $x_2$ is missing). * (2b) The construction of the probability distribution $P_{S, X, Y}$: given the attribute is $S=s$, it seems that the authors are requiring $Y=1$ won't appear in non-missing $X$ (as specified: $\text{Pr}(Y=1, X=0|S=s)\text{Pr}(Y=1, X=1|S=s)=0$), and $Y=1$ appears only for missing values (as specified: $\text{Pr}(Y=1, X=\text{NA}|S=s)=\alpha_s, \text{Pr}(Y=1, X=\text{NA}|S=s)=0$). Although the example itself is correct, it is hard to believe whether the conclusion will remain the same in more complex scenario.

Questions

* (1) It would be much better if the saying of **missing values** could be explained at the beginning of the paper, since missing values may indicate many aspects, for example, missing labels $y$ of a sample $(x, y, z),$ or missing (hidden) attributes $z$, or missing instances $x$. * (2) The notation w.r.t. accuracy $\mathbb{I}$ is given without any explanations. * (3) Should there be any conditional independency between $\hat{X}$ and $Y$, in line 190?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

Please refer to the section of **Weakness**.

Summary

This work examines the impacts of missing values in data on fairness interventions, particularly in contrast to the commonly implemented "impute-then-classify" procedure for handling missing values. The authors present the following: - investigation of how missing values impact algorithmic fairness in the context of three main modes of missing data (missing completely at random, missing at random, and missing not at random); - a theorem capturing the performance gap between optimal solutions when employing a generic imputation mechanism vs. not when using equalized odds (information-theoretic result); - methods for adapting fairness-intervention algorithms to missing data, both for linear and non-linear settings; - empirical evaluation of their proposed methods. Their findings suggest that fairness intervention strategies benefit from the preservation of information encoded in the missingness of data in terms of group fairness and accuracy.

Strengths

- Clear motivation of the problem setting, both in the introduction and recapping in the conclusion. - Overall, mathematical notation is quite clean and easy to follow. - The authors provide an interesting information-theoretic performance gap result under a general imputation mechanism in the context of classification accuracy and equalized odds fairness constraint. This result implies that following imputation, then classification will never perform better (in terms of accuracy and group fairness) than using the information encoded in missing features, and moreover will result sub-optimal performance due to information loss. - Multiple methods are presented to address missing values in the context of linear classification and one bagging-based method for nonlinear classification. These missing-value adaptation methods are flexible and can be used in conjunction with preexisting fairness-intervention algorithms (used in a black-box way). - The authors provide meaningful discussion of challenges and limitations in using their methods (determining choice of fairness intervention, which the adaptation methods depend on; sensitive groups/attributes not being known beforehand). They also effectively demonstrate the value of this research direction in the context of algorithmic fairness. - The authors provide implementation and hyperparameter details used in their experiments in the Appendix, supporting reproducibility (though this should be referenced in the main paper).

Weaknesses

It's unclear what the trade-offs are between the three methods presented for linear classification. The figures comparing the performance between the methods against baselines are very hard to visually interpret, and there is insufficient discussion highlighting the performance differences between these and the baselines. It'd be helpful to further flesh out this section. It also makes it unclear what the value is in providing three methods for a more constrained and less practically-applicable setting given this presentation. Furthermore, it is unclear how one would determine which of the three linear methods one should use - the authors note "we believe that the best adaptive algorithm is not universal, and one should select the adaptive algorithm based on the distribution of the data". What suggestions do you have for the reader in doing this? Additional suggestions: - In alignment with a question provided in the Questions section, proofs in the Appendix would benefit in some places from more rationale between steps - readers may not necessarily share your same mental model or background, and this can help cognitive overhead on the reader. - Overall, the empirical results presented in the plots (Figures 1-3) are very hard to read and interpret, and are unfortunately quite inaccessible (font size, curve markers and overlap, overall size). The paper would benefit from making these more human-interpretable and by highlighting key takeaways (as stated above) and trade-offs. - Nit: Please state upfront in Section 4 the settings you provide algorithms for! Based on the organization of the paper, a reader would have to be motivated to get to Section 5 to uncover that you provide methods for linear and nonlinear settings. :] - Nit: please include references in the main paper to additional results/content in the Appendix throughout, i.e. proofs, additional experimental details, etc. - Minor nit: please include the year in citation references.

Questions

1. In the proof of Theorem 1, I didn't follow the transition between lines 539 and 540, nor where q came from. It'd be helpful to explicitly add a note for arriving at a < 1/3. 2. What implications does Theorem 1 have in a less trivial/higher dimensional setting? The multiclass classification setting? 3. Please refer to the Weaknesses/Suggestions section for additional questions around the linear adaptation methods, results, and trade-offs.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors provide meaningful discussion of challenges and limitations in using their methods, namely that the choice of fairness intervention is an important dependency and choice when utilizing the adaptation methods, along with the challenges introduced when sensitive groups/attributes are not known ahead of time and need to be inferred in an online manner.

Response

I thank the authors for their response! I looked at the discussion with other reviewers as well, and am satisfied with the revisions the authors will make. I will increase my score to a 7.