Adapting Fairness Interventions to Missing Values
Authors: Raymond Feng
Flavio Calmon
Hao Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: algorithmic fairness
discrimination
missing values
machine learning

Abstract: Missing values in real-world data pose a significant and unique challenge to algorithmic fairness. Different demographic groups may be unequally affected by missing data, and the standard procedure for handling missing values where first data is imputed, then the imputed data is used for classification—a procedure referred to as "impute-then-classify"—can exacerbate discrimination. In this paper, we analyze how missing values affect algorithmic fairness. We first prove that training a classifier from imputed data can significantly worsen the achievable values of group fairness and average accuracy. This is because imputing data results in the loss of the missing pattern of the data, which often conveys information about the predictive label. We present scalable and adaptive algorithms for fair classification with missing values. These algorithms can be combined with any preexisting fairness-intervention algorithm to handle all possible missing patterns while preserving information encoded within the missing patterns. Numerical experiments with state-of-the-art fairness interventions demonstrate that our adaptive algorithms consistently achieve higher fairness and accuracy than impute-then-classify across different datasets.

Adapting Fairness Interventions to Missing Values
Raymond Feng', Flavio P. Calmon', Hao Wang²
'Jhhn A. Paulson School of Engineering and Applied Sciences, Harvard University 2MIT-IBM Watson AI Lab
raymond__eng@colleeg hawaeraarrreeg...aaa....... edu, flaviotseas harvard. hao@ibm.com com
Abstract
Missing values in real-world data pose a significant and unique challenge to al- gorithmic fairness. Different demographic groups may be unequally affected by missing data, and the standard procedure for handling missing values where first procedure
data is imputed, then the imputed data is used for classification referred to as thapuue-thee-clasify"" classify"-caaii -ann exacerbate discrimination. In this paper, we analyze how missing values affect algorithmic fairness. We first prove that training classifier from imputed data can worsen the achievable values of group fairness and average accuracy. This is because imputing data results the loss of the missing pattern of the data, which often conveys information about the predictive label. We present scalable and adaptive algorithms for fair classifica- tion with missing values. These algorithms can be combined with any preexisting algorithm to handle missing data while preserving information encoded within the missing patterns. Numerical experiments with state-of-the the-art fairness interventions demonstrate that our adaptive algorithms consistently achieve across different datasets.
higher fairness and accuracy than
Introduction
Missing values exist in many datasets across wide range of real-world contexts. Sources of missing values include underreporting in medical information [18], structural missingness from data collection setups [43], and human error. Missing data poses challenge to algorithmic fairness because the mechanisms behind missing values in dataset can depend on demographic attributes such race, sex, and socioeconomic class. For example, in housing data, noitw housing applicants or sellers may be less likely to report their race due to concerns of discrimination [51]. Real-world data collection and aggregation processes can also lead to disparate missingness between population groups. If missing data is not handled carefully, there is high risk of discrimination between demographic groups with different rates or patterns of missing data. For example, low-income patients have more missing values in medical data involving the results of costly medical tests [37], making them less likely to qualify for early interventions or get treatment for insufficiently severe conditions [17].
The issue of missing values has not been sufficiently addressed in current fairness literature. Most fairness-interventee intervention algorithms that have been proposed are designed for complete data and cannot be directly applied to data with missing values [e.g.. 1, 2, 7, 10, 25, 32, 60, 61]. A common approach to handle missing values is to first perform imputation, filling in missing entries with appropriate values, and then apply an off-the-shelf fairness-inerrvention algorithm to the imputed data (impute- then-classify). However, this standard procedure has several limitations. In many contexts and data formats, imputation is not an appropriate method for handling missing values. In healthcare data, some missing data is categorized as "intended missing data," which, for example, the National Cancer Institute does not recommend imputing [43]. For instance, if a respondent answers NO to the question "Were you seen for illness or injury?", they should skip the question "How often
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

did you get care for an illness or injury as soon as you wanted?". Imputing the second question does not make sense knowing the format of the data. The missingness pattern of the data can also convey important information about the predictive label. For instance, in surveys with questions about alcohol consumption history, missing responses are often correlated with alcoholism due to pervasive social stigma surrounding alcoholism [39]. A model trained on imputed data will suffer from reduced performance, especially for groups with higher missing data rates.
In this work, we investigate how missing values in data affect algorithmic faimess. We focus on the setting where input features of predictive models may have missing values. Although growing body of research [27, 62] is dedicated to addressing the issue of missing group (sensitive) attributes, the problem of missing imput features is equally crucial and widespread yet less studied. Our objective in this paper is to bridge this gap and offer comprehensive study encompassing theory and algorithms for training fair classifiers in the presence of missing input features, particularly when missingness patterns vary per population group (as observed in practice).
First, we show that the performance of fair classifier trained with impute-then-classiyy can be significantly lower than one trained directly from data with missing values. Impute-then-classin may fail because imputation loses information from the missing pattern of the data that can be useful for prediction. Our result is by altering the hypothesis class, using a different imputation method, or increasing the amount of training data.
a data scientist cannot improve this fundamental limit
Next, we introduce methods for adapting fairness-interventio algorithms to missing data. In Section 4, we present three adaptive algorithms for training fair linear classifiers on data with missing values, and in Section 5, we introduce an algorithm that adapts general faimesss interventions to handle missing values. We treat the linear case separately because the interpretability of linear classifiers facilitates their widespread use in practice [11, 47, 54, 56]. Our algorithms work by modifying the dataset to preserve the information encoded in the missing patterns, then applying an off-the-shelf fairnes-interventionn algorithm the new dataset. This avoids the iotommation-thorree
limitation of impute-ther soatte-then-dee clensccassiffy described in our theoretical result above. Most importantly, our algorithms are flexible because they can be combined with any preexisting fairness intervention to handle missing values fairly, accurately, and efficiently. Other ad advantages include scalability to high-dimensions data, generalizability to new data, and the ability to handle new missing patterns that occur only at testing time.
We benchmark our adaptive algorithms through comprehensive numerical experiments. We couple the adaptive algorithms with state-of-the-an fair classification algorithms and compare the performance of these methods against thputte-hee-claasiffy. Our results show that the adaptive algorithms achieve favorable performance compared to thpute-then-classit on several datasets. The gap in performance more pronounced when missing data patterns encode more information, such as when data missingness is correlated with other features. i.e., not missing uniformly at random. Although the relative performance of the adaptive methods depends on the data distribution, even a simple method such as adding missing indicators as input features consistently achieves better fairness-accuran curves than impute-then-clasifff.. When applying faimess interventions on missing data, we find that utilizing information from missing patterns is crucial to mitigate the fairness and accuracy reduction incurred by imputation. Our results suggest that practitioners using fairness interventions should preserve information about missing values to achieve the best possible group fairess and accuracy.
1.1 Related work
Missing values in supervised learning. A line of recent works has investigated the limitations of performing imputation prior to classification [4, 26, 36]. In a remarkable paper, Le Morvan et al. [36] found that even if an imputation method is Bayes optimal, downstream learning tasks generally require learning discontinuous function, which weakens error guarantees. This motivated a neural network algorithm that jointly optimizes imputation and regression using an architecture for learning optimal predictors with missing values introduced in [35, 42]. Among related work in supervised leamning with missing values, the closest to ours is [4] and [31]. Bertsimas et al. [4] devised several algorithms for a general linear regression task with missing values where the missingness pattern of the data is utilized to make predictions. In particular, the static regression with affine intercept algorithm involves adding missing indicators as feature variables and has been found to improve performance for standard prediction tasks [45, 50, 52, 57]. Our work generalizes their algorithms
2

---

to fair classification tasks. We also extend the family of ensemble approaches in Khan et al. [31] to fair classification using a general, non-linear base classifier. Our approach is similar to [49] in using bootstrapping to satisfy strengthened fairness conditions; key difference is that we explicitly use (known) sensitive attributes and labels when drawing subsamples to ensure sample diversity.
Missing values in fair machine learning. Discrimination risks related to missing values were studied in [6. 14, 23, 48, 53, 58]. Caton al. [6]. Fernando al. [14], Jeong al. [23], Mansoor et al. [40], Schelter et al. [48], Zhang and Long [63] provided empirical assessments on how different imputation algorithms impact the fairness risks in downstream prediction tasks. These studies have highlighted that the choice of imputation method impacts the faimess of the resulting model and that the relative performance of different imputation methods can vary depending on the base model. To mitigate discrimination stemming from missing values, researchers have proposed different methods for fair learning with missing values for tabular data [23, 58] and for graph data [53]. Among these works, the closest one to ours is Jeong et al. [23] which proposed fair decision tree model that uses the MIA approach to obtain fair predictions without the need for imputation. However, their algorithm hinges solving a mixed integer program, which can be computationally expensive.
Another related line of work studies how one can quantify the faimess of ML model when the required demographic information (i.e., sensitive group attributes) is missing. Methods to estimate fairness of models in the absence of sensitive group attributes have been developed using only observed features in the data [27] or complete case data [62]. Multiple works have also studied fairness when predictive labels themselves are missing. Wu and He [59] propose a model-agnostic approach for fair positive and unlabeled learning. Ji et al. [24] propose Bayesian inference approach to evaluate fairness when the majority of data are unlabeled. Lakkaraju et al. [33] propose an evaluation metric in settings where human decision-makers selectively label data and make decisions using unobserved features. In contrast, we focus on algorithm design for the case of missing non-group attribute input features.
2 Preliminaries
Throughout, random variables are denoted by capital letters (e.g.. X), and sets are denoted by calligraphic letters (e.g., 2). We consider classification tasks where the goal is to train classifier h that uses an input feature vector x = (I1.- ... Ia) to predict a label y. We restrict our domain to binary classification tasks where y {0, 1). but our analysis can be directly extended to multi-class tasks. In practice, æ may contain missing values, so we let æ E II (X, U (NA)).
We adopt the taxonomy in [38] and consider three main mechanisms of missing data: missing completely at random (MCAR), where the missingness is independent of both the observed and unobserved values, missing at random (MAR), where the missingness depends on the observed values only, and missing not at random (MNAR), where the missingness depends on the unobserved values. We introduce a missingness indicator vector m E M {0, 1]a that represents the missingness pattern of æ: the missingness indicator m, if and only if the jth feature of is missing.
We evaluate differences in classifier performance with respect to group (sensitive) attribute $ E S. stirmess-interventie algorithms often aim to achieve an optimal faimess-accuracy trade-off by solving constrained optimization problem
max E [I((XX Y)] s.t. Disc(h) Se
(1)
for some tolerance threshold 2 0. Here I is the indicator function, which equals 1 when the classifirr produces the correct prediction h(X) Y. and otherwise, it equals Disc(h) represents the violation of (group) fairness constraint. For example, we can define Disc(h) for equalized odds
as
Disc(h) = max (P((((X) = Y S =) PP(((() = Q S = =))]- 8.8.8,8'
Equalized odds addresses discrimination by constraining the disparities in false positive and false negative rates between different sensitive groups. Analogous expressions exist for other group fairness constraints such as equality of opportunity and statistical parity [13, 20]. In the case where multiple, overlapping sensitive attributes exist in the data, our framework can be extended to the multiaccuracy and multicalibration faimeess measures introduced in Kim et al. [32] and Hébert-Johnser et al. [21].
3

---

3 Characterization of Fairness Risk on Imputed Data
Methods for learning a fair classifier can fail when data contains missing values. For example, many faimess interventions use base classifiers such as linear classifiers and random forest that do not support missing values [e.g.. 2, 61]. Others use gradient-based optimization methods that require continuous input space [e.g., IJ. Impute-then-classii is the most common way of circumventing this issue. However, key limitation of impute-then-classify is that imputing missing values loses information that is encoded in the missingness of the data. If the data contains missing values that MCAR, the fact that a feature is missing can be informative. A model trained on imputed data loses the ability to harness missingness to inform its predictions of the label. We introduce a theoretical result that rigorously captures this intuition.
We represent an imputation mechanism formally as a mapping Supp II (X, U (NA)) X; and denote the imputed features by ã (z)) We define the underlying data distribution by xs. and the distribution of imputed data by S. We use the mutual information measure the dependence between the missing patterns M and the label Y:
PM,y(m, log PMa (m, PM (m
1(M;Y) & Σ Σ
MEM (E
Recall the constrained optimization problem in (1) for training fair classifier. When the optimization is over all binary mappings h, the optimal solution only depends on the data distribution Ps.x.y and the fairness threshold c. In this case, we denote the optimal solution of (1) by F. (P The next theorem states that even in the simple case where single feature has missing values, impute- then-classify can significantly reduce a classifier's achievable performance under a group fairness constraint when the missingness pattern of the data is informative with respect to the predictive label.
Theorem 1. Suppose that X composed by a single discrete feature (i.e., d 1) and Disc(h) is the equalized odds constraint. Let 9 [0, 1] 7 IR be the binary entropy function: g(a) = -a log(a) (1-1)) - log(1 11--) u). For any e and a < 1/3, there exists a data distribution Ps.x,y such that I [(M; Y) = g(u) and
sup F. F.(Ps.X.v) S F((P.x.))
Iue
This information-thhoreee result shows that applying a fairmess-intervention algorithm to imputed data can suffer from a significant accuracy reduction which grows with the mutual information between the missing patterns and the label. Note that the supremum is taken over all imputation mechanisms; the inequality holds regardless of the type of classifier, imputation method used, or amount of training data available. In other words, the negative impact to performance due to information loss from imputation is unavoidable if using then-ttthhe--llssiff
4 Adapting Linear Fair Classifiers to Missing Values
In the last section, we showed how a classifier trained from impute-then-Clasifyy may exhibit suboptimal performance under (group) fairness constraint. We now address this issue by presenting adaptive algorithms that can be combined with faimess interventions to make fair and accurate predictions on data with missing values. We extend prior work in [4] to fair classification setting.
We focus first on adapting fairness interventions to missing values linear classifiers, and present results for non-linear methods in the next section. We treat the linear case separately since, despite their simplicity, lincar classifiers are widely used in practice and in high-stakes applications (c.g., medicine, finance) due to their interpretability [11, 47, 54, 56). The adaptive algorithms propose allow a model to handle any missing pattern that appears at training and/or test (deployment) time.
We propose three methods tailored to linear classification: (i) adding missing values as additional features, (ii) affinely adaptive classification, and (iii) missing pattern clustering. Our methods encode missing value patterns via adding new features in the case of (i) and (ii) and partitioning the dataset in the case of (iii), allowing a fairness intervention to then be applied on the encoded data. For example, if the fairness intervention is a post-processing scheme, a linear classifier is fit on the encoded data and then modified by the intervention. For in- in-processing schemes [1, 7, 30], the fair linear classifier is simply trained on the encoded data. The three methods are illustrated in Figure 4a (Appendix C).

---

4.1 Adding missing indicator variables
Our first adaptive algorithm to pass m as part of the input feature vector and impute missing values by zero. Letting è denote the imputed original features, our new feature vectors are now of the form (it, m)) E (II= X.) x {0, 1]dd and we can then train an off-the- shelf algorithm on the new data. This approach is highly scalable as the number of features in the new data is 2d. We can interpret learning linear classifier w (W1:-.. Wd. b1 .... ba) the transformed dataset (where by is the coefficient of m,) as equivalent to jointly learning a linear classifier w' = (wi...., Wa) on the original data and an imputation method that replaces missing values in feature j with bn [4]. Alternatively, noting that w (át, m) = Σー= Wyzy( (1 m2) Σッ= bymy, adding w/ missing indicators effectively allows the bias term to be adjusted by by when feature j is missing.
Intuitively, using missing indicators captures the information encoded in the missingness patterss of the data. We provide an information-theoree interpretation of this intuition in Appendix B.
4.2 Affinely adaptive classification
As mentioned above, adding missing indicator variables allows the bias term of a linear classifier to be adjusted by constant when feature is missing. We can treat the coefficients of the classifier in similar way. Affinely adaptive regression includes additional input features of the form my (1 mm )ay for j, k E [d] with k, then applying zero imputation and off-the-shelf fairness intervention. This can be interpreted as training a linear classifier with coefficients wo + Wm, where we is an initial set of coefficients and 5k: denotes the adjustment to wy when 23. is missing:
d
(wo Wm) T Σ Woy (1 ma)a, + Wyamp(1 my)a3.
Affinely adaptive classification generalizes simply adding missing indicators by including a bias term as an additional input feature. However, a significant drawback that affinely adaptive classification requires O m)) features where Remiss is the number of original features that contain missing values, though this number may be small in practice.
4.3 Missing pattern clustering
The previous two algorithms transform the original dataset by adding additional input features encoding data missingness. We now introduce a two-step missing pattern clustering algorithm. First, the missing patterns in the data are split into clusters. Then, an off-the-shelf fairness intervention algorithm is applied on each cluster separately. Rather than encoding data missingness with additional input features, this algorithm avoids the limitation impute-then-classify by using missing patterns to partition the dataset. We also impose group fairness constraints in the clustering process to ensure sufficient sample size and diversity in each cluster. This allows the fair classifiers on each cluster to generalize to fresh data.
During clustering, we split all possible missing patterns M into Q clusters {M4 using recursive partitioning method. Let P denote the current (intermediate) partition, so initially P (M). At each step, we split each cluster My E P based on the missingness of some feature j into two new sets M 4 (m E M₁ : m, 0} and ME1 = {m E Mg my = 1). We split the training dataset correspondingly into I = {(x,, 9:) m, E MM and IzJ1 = ((I,.))) : m, E MM").. To
determine the feature on which split, introduce a loss function:
L(M,;:) e min Elyi, w TTaa) Ta!))
+ min
Elyy,
Eyy,, w Ta!))
VEI!"
where af is æ, with missing values imputed by zero. In other words, ((Mg. j) is the total loss from training linear classifiers I2 and I
T.MM,.j) satisfies two desirable properties. First, it can be calculated efficiently as it does not include fairness risk, which is crucial there are O(d) candidate features for each split. Second, T(M,.=) j)
guarantees that the total loss with respect to the standard classifiers
Σ
min
E(V, w x²)
M,EP
VEI
5

---

never increases after a split, provided that we split a cluster Mg only if L(Mg..) < minw Eiez, fyy, w x)), ie. the two new classifiers collectively perform at least as well as classifier trained on the whole cluster.
To address the fairness concerns of having clusters with small sample size sample imbalance, we require each cluster to have balanced data from each group. A feature j is considered for splitting only if I and I satisfy bounded representation for chosen parameters a, S:
xx: E I2th ss = Sa, SE E {0, 13.
We also impose minimum permissible cluster size k for IN and Ig'. We will denote the set of features j that satisfy these constraints by G(M,)). At each splitting iteration for each cluster My. split on j" E arg minG(M,) L(Mg. j). After obtaining clusters {My]g we apply an off-the-shellf fairness intervention to train a fair linear classifier on each cluster. The faimess constraints we enforce during clustering ensure that the classifiers for each cluster can generalize to fresh data. We summarize our recursive partitioning method in Algorithm (Appendix C).
5 Adapting Non-Linear Fair Classifiers to Missing Values
The algorithms above take advantage of the interpretability of linear classifiers to "deactivate" missing features via zero imputation. We now provide general algorithm for nonlinear classifiers where the effect of zero imputation may be less clear. We introduce FairKissBag, a fair bagging algorithm that can be applied to any fair classifier to handle missing values. The algorithm proceeds in three steps (see Figure 4b, Appendix C for an illustration).
The training data D is separated into groups by sensitive attribute and label D {(x,, Vi,
Vi. s;) 8; 5, 3, = y}. From each Da.y, we sample (Da.yl data points uniformly with replacement. We combine these samples create a new dataset of the same size as the original dataset. Missing indicators are added to each data point and an imputation method is used on each subsample separately. We repeat this process B times, creating distinct datasets.
Apply off-the-shelf fairness intervention to train classifier each resampled dataset, yielding B classifiers in total.
To make a prediction on new data point, one of the B fair classifiers chosen uniformly at random. We return the prediction from this classifier. Alternatively, if the classifiers output probability or score for each label, the scores from all classifiers are averaged to generate an output.
In the first step, the uniform resampling procedure ensures sufficient sample size and diversity by preserving the balance data across sensitive attribute and outcome, relative to the original data. Additionally, the inclusion of missing indicators as input features (Section 4.1) prevents the issue of reduced fairness-accuracy curve described in Theorem 1. Our procedure is similar to the fair resampling procedure introduced in Kamiran and Calders [28] and Wang and Singh [58] except that we relax the independence assumption of S and Y. This is advantageous in, for example, healthcare scenarios where demographic group may have a higher prevalence of disease (e.g., determined by age). It is likely desirable for a model to select patients from this group for treatment at a higher rate rather than enforce independence between and Y by equalizing the selection rate between groups.
We show that our ensemble strategy in step also preserves fairness by extending the analysis in [19]. We equalized odds here as example; the same faimess guarantee also holds for other fairness constraints such as statistical parity and equality of opportunity. If the base classifiers output scores (probabilities) for each class, an analogous argument justifies averaging the scores.
Lemma 1. Suppose we have an ensemble of classifiers C = (C, J.M such that each classifier sutisfies an equalized odds constraint, i.e. there exists E such that for all
1/Y y, S') Vy (0,1), s, S. Let p(j) denote probability distribution over the classifiers and C(xx) be the prediction obtained by randomly selecting a base classifier Cs, from p(j) and computing Cs (a:). Then C also satisfies the equalized odds constraint.
(X) - 1|2 -, v,S -))

---

6 Numerical Experiments
We evaluate adaptive algorithms with comprehensive set of numerical experiments by comparing our algorithms coupled with state-of-the-art fairness intervention algorithms on several datasets. We describe the setup and implementation and discuss the results of the experiments. Refer to Appendix D for additional experiment details.
6.1 Experimental setup
Datasets. We test our adaptive algorithms on COMPAS [34], Adult [12], the IPUMS Adult recon- struction [9, 15], and the High School Longitudinal Study (HSLS) dataset [22]. We refer the reader to Appendix D.2 for details pre- pre-processing each dataset and generating missing values for COMPAS and the two versions of Adult. The sensitive attribute race in COMPAS and sex in Adult.
HSLS is a dataset of over 23,000 high school students followed from 9th through 12th grade that includes surveys from students, teachers, and school staff, demographic information, and academic assessment results [22]. We use an 11-feturee subset of the dataset. The sensitive attribute is race (White/Asian versus Black, Hispanie, Native American, and Pacific Islander) and the predictive label is student's s 9th grade math test score. We consider only data points where both race and 9th grade math test score are present because our experiments use fairness interventions that use knowledge of the group attribute and label to calculate faimess metrics. HSLS exhibits high rates of missingness as well as significant disparities in missingnesss with respect to race. For instance, 35.5% of White and Asian students did not report their secondary caregiver's highest level of education; this proportion increases to 51.0% for underrepresented minority students [23].
Fairness intervention algorithms. We use DispMistreatmen [61] and FairProjection [2] as two benchmark algorithms and defer additional experimental results using other benchmarks (Reduction [1], EqOdds [20], ROC [29], Leveraging [8]) to Appendix E. All of these algorithms are designed for complete data and require missing values to be imputed before training.
For each combination of adaptive algorithm and fairness intervention, we plot the fairness- tradeoff curve obtained from varying hyperparameters (see Appendix D.3). We obtain convex curve by omitting points that are Pareto dominated, i.e. there exists another point with higher accuracy and lower discrimination. The fairesss metrics used are FNR difference and mean equalized odds, defined as z (FNR difference + FPR difference).
6.2 Linear fair classifiers
We test different combinations of the above faimess interventions with the adaptive algorithms in Section 4 using logistic regression as the base classifier. For the missing pattern clustering algorithm, we reserve part of the training set validation to calculate the clustering objective function. We present results for FairProjection on IPUMS Adul/COMPAS and FairPro jeriion and DispMistreaament HSLS. We defer results for other benchmarks to Appendix E.
IPUMS Adul/COMPAS. Figure I displays fairres-accurracy curves for COMPAS and the IPUMS Adult reconstruction. We observe that for the datasets with MCAR and MAR missing values, the three methods tested have comparable performance with impute- impute-thenn-clsee tlen-classify. However, for the MNAR datasets, adding missing indicators and affinely adaptive classification significantly outperform the baseline especially with regard to accuracy, which is consistent with Theorem 1. We omit results for missing pattern clustering as the majority of trials did not find multiple clusters.
HSLS. Figure 2 displays the fairness- aaiuuasy-accuracy curves for DispMistreatment and FairProjection on HSLS. For Displtistreatment adding missing indicators achieves marginally improved performance over the baseline, while affinely adaptive classification achieves the highest accuracy but at the cost of faimess. For MirPrrojection all three adaptive methods outperform the baseline.
The experiments on linear fair classifiers show that using the adaptive fairness- intervention algorithms proposed in Section 4 consistently outperform impute-then-classffy in terms of accuracy and fairness across different datasets. The performance improvement of the adaptive
Discussion.
7

---

MCAR
MAR
MNAR
0.820
0.020
0.825
0.835
Accurao CCr
Acturacy
0.815
0.810
0.805
0.005
0.805
0.800
2. Mean Equalized Odds
0.15
0.10
0.05
0.00
015
0.20
0.25
Mean Equalized Odds
Mean Equalized Oods
Baseline
Adding missing
Aftinely adaptive classification
(a) IPUMS Adult, FairProjection
MCAR
MAR
MNAR
0,660
0.650
0.72
0.655
0.645
0.71
Recuracy
0.650
Accuracy
0.635
0.640
Accuracy
0.70
0.69
0.645
0.630
0.68
0.625
0.67
0.640
0.620
0.66
0.635
0.615
0.65
0.2
Mean Equalized Odds
Mean Equalized Odds
Mean Equal zed Odds
Baseline
Adding missing indicetors
Affinely adaptive classification
(b) COMPAS, FairProjection
Figure 1: Comparison of adaptive iiirnss--nteeventioo algorithms on IPUMS Adult and COMPAS using FairProjection. For each original dataset, we generate three datasets with missing values corresponding to MCAR, MAR, and MNAR mechanisms (Appendix D.2). Error bars depict the standard error runs with different train-test splits.
fairness-intervenn intervention algorithms also increases when the missing patterns of the data encode signifi- cant information about the label, as is the case in the MNAR COMPAS/Adult datasets. Interestingly. although affinely adaptive classification and missing pattern clustering are both more expressive variants of adding missing indicators, adding missing indicators was able to achieve comparable performance to both methods in most cases. We include an additional experiment in Appendix E on synthetic dataset (see Appendix D.I) where missing pattern clustering outperforms all other adaptive algorithms.
In short, believe that the best adaptive algorithm is not universal. Our suggestion is consider the choice of algorithm as a hyperparameter and select by using validation set and considering the trade- offs between the methods proposed. Missing value indicators, though performing worse on average. has the benefit of being simple and interpretable. Affinely adaptive classification provides a potential accuracy gain at the cost of additional complexity, and missing pattern clustering should preferred when there is sufficient data to cluster missing patterns in an advantageous way. Regardless of this choice, however, our results show that preserving information about missing values important to achieve the best possible group fairness and accuracy.
6.3 Non-linear fair classifiers
We test the FairMissBag ensemble method proposed in Section 5 with PcirProjectiog Reduction onn and EqOdds. The base classifier for all fairness-interveniion algorithms a random for- est consisting of 20 decision trees with maximum depth 3. We run experiments with three imputation methods: mean, K-nearest neighbor (KNN), and iterative imputation [44]. We present results for FairMissBag HSLS and defer additional experimental results to the appendix.

---

DispMistreatment
FairProjection
0.695
0.700
Accuracy
0.690
Accuracy
0.698
0.685
0.696
0.680
0.694
0.02
0.03
0.05
0.06
0.07
0.05
0.07 Mean Equalized Odds
0.06
FNR difference
Baseline
Missing pattern clustering
Adding missing indicators
Affinely adaptive classification
Comparison of adaptive fairness-intervention algorithms HSLS dataset, using DispMistreatment (left) and FairProjection (right). Error bars depict the standard error of 10 runs with different train-test splits.
Figure 2:
Reduction
EqOdds
FairProjoction
0.690
0.670
0.588
Accuracy
Accurary
0.685
0.665
0.584
0,680
0.380
0.05
0.10
0.02 Mean Equallzed Odds
0.03
0.04
0.05
0.10
0.15
Mean Equalized Odds
Mean Eousl ized Odds
C. Baseline (mean)
Basel (KNN)
Baseline (iterative)
FairMisstaag (mean)
FeirMissiaag (KNN)
FairMissBag (iterative)
Figure 3: Results for FairMissBag on HSLS, using Reduction, EqOdds, and Fair PairProjection Fairness-accuracy curves under mean, KNN, and iterative imputation are shown, respectively. Error bars depict the standard error of 5 runs with different train-test splits.
Figure 3 displays the results of the FairMissBag experiment on HSLS. We observe that for Reduction, FairMissBag yields meaningful fairnss-aaccuacyy improvement for KNN and itera- tive imputation. similar improvement observed for EqOdds for mean and KNN imputation. For FairProjecti FairMissBag generally extends the fairness-accuracy curve, providing higher accuracy with a tradcoff of increased fairness risk.
Discussion. We observe that using FairMissBag yields fairness and accuracy improvements over impute-then-clasiin Additionally, for both accuracy and faimess, the relative performance of the three imputation methods we tested depends on the dataset used and fairness-intervention algorithm applied. We conclude that the choice of imputation method can significantly influence accuracy and fairness. This corroborates previous findings e.g. [23, 26, 36) that the best imputation method for given prediction task and setup is not always clear choice.

---

7 Conclusion and Limitations
In this work, we investigated the impact of missing values on algorithmic fairness. We introduced adaptive algorithms that can be used with any preexisting inntreetintervintionn algorithm to achieve higher accuracy and fairness than impute-ther then-classify. The flexibility and consistency of our algorithms highlight the importance of preserving the information in the missing patterns in fair learning pipelines. We note, however, that using missingness information in a fair classifier is not immune to potential negative impacts. For example, an individual may be incentivized to purposefully hide data if their true values are less favorable than even NA. In missing pattern clustering, an individual may be classified less favorably or accurately than if classifier from different cluster were used. These scenarios highlight considcrations with respect to individual and preference- based fairness notions [55] and the importance of making careful, informed choices for both the adaptive algorithm and the fairness intervention. Another potential challenge is if sensitive groups are not known prior to deployment and must be learned online. Nevertheless, hope that our insights can inform future work in fair classification with missing values.
Data imputation remains commonly used in data science pipelines. However, the predictions output by ML. models are dependent on the imputation method used. When considering single data points, this presents an important challenge from an individual fairness perspective, because the choice of imputation may arbitrarily affect an individual's outcome [13]. The effect of imputation choice on individual outcomes parallels the "crisis in justifiabilityy that arises from model multiplicity, where model may be unjustifiable for an individual if another equally accurate model provides the individual better outcome [5, 41J. A future work direction is examining how to choose an imputation given these challenges and how the user may be involved in making this choice. Additionally, increased classification error outcome volatility may harm individuals with many missing values. This raises the critical question of whether to withhold classification for individuals with too many missing values and how provide resources unclassified individuals. Ultimately, the ubiquity of missing data in the real world means that new developments in fairness with missing values have the potential to be broadly impactful and create better, fairer societal outcomes.
10

---

Acknowledgement
The authors would like to thank Prof. Haewon Jeong for her valuable input in the early stage of this project. This material is based upon work supported by the National Science Foundation under grants CAREER 1845852, CIF 2312667, FAI 2040880, CIF 1900750.
References
[1] Agarwal, A., Beygelzimer, A., Dudík, M., Langford, J., and Wallach, H. (2018). A reductions approach to fair classification, In International Conference on Machine Learning, pages 60-69. PMLR.
[2] Alghamdi, W., Hsu, H., Jeong, H., Wang. H.,, Michalak, P. W., Asoodeh, S., and Calmon, F. P. (2022). Beyond Adult and COMPAS: Fair multi-class prediction via information projection. In Advances in Neural Information Processing Systems.
[3] Bellamy, R. K., Dey, K., Hind, M., Hoffman, S. C.,, Houde, S., Kannan, K., Lohia, P., Martino, J., Mehta, S., Mojsilovic, A., et al. (2018). Ai fairness 360: An extensible toolkit for detecting, understanding, and mitigating unwanted algorithmic bias. arXiv preprint arXiv:1810.01944
[4] Bertsimas, D., Delarue, A., and Pauphilet, (2021). Beyond impute-then-regres Adapting prediction to missing data. arXiv preprint arXiv:2104.03155
[5] Black, E., Raghavan, M., and Barocas, S. (2022). Model multiplicity:
Opportunities, concerns, and solutions. In 2022 ACM Conference Fairness, Accountability, and Transparency, pages 850-863.
[6] Caton, S., Malisetty, S., and Haas, C. (2022). Impact of imputation strategies on fairness in machine learning. Journal of Artificial Intelligence Research, 74:1011-1035.
[7] Celis, I.. E., Huang, I.,, Keswani, V., and Vishnoi, N. K. (2019). Classification with fairness constraints: A meta-algorithm with provable guarantees. In Proceedings of the conference on fairness, accountability, and transparency, pages 319-328.
[8] Chzhen, E.,, Denis, C.,, Hebiri, M., Oneto, L.., and Pontil, M. (2019). Leveraging labeled and unlabeled data for consistent fair binary classification. Advances in Neural Information Processing Systems, 32.
[9] Ding, F., Hardt, M., Miller, J., and Schmidt, I.. (2021). Retiring adult: New datasets for fair machine learning. Advances in Neural Information Processing Systems, 34.
[10] Donini, M., Oneto, I.., Ben-David, S., Taylor, S., and Pontil, M. (2018). Empirical risk minimization under faimess constraints. Advances in Neural Information Processing Systems, 31.
[11] Dressel, J. and Farid, H. (2018). The accuracy, fairness, and limits of predicting recidivism. Science Advances, 4(1 =eaas5055
[12) Dua, D. and Graff, C. (2017). UCI machine learning repository.
[13] Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. (2012). Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214-226.
[14] Fernando, M.-P., Cèsar, F., David, N., and José, H.-O. (2021). Missing the missing values: The ugly duckling of fairness in machine learning. International Journal of Intelligent Systems, 36(7):3217-3258.
[15] Flood, S., King, M., Rodgers, R., Ruggles, S., and Warren, J. (2020). Integrated public use microdata series, current population survey: Version 8.0.
[16] Flores, W., Bechtel, K., and Lowenkamp, C. T. (2016). False positives, false negatives, and false analyses: A rejoinder to machine bias: There's software used across the country to predict future criminals. and it's biased against blacks. Fed. Probation, 80:38.
[17] Gianfrancesco, M. A., Tamang, S., Yazdany, and Schmajuk, G. (2018). Potential biases in machine learning algorithms using electronic health record data. JAMA Intern. Med., 178(1 15:1544- 1547.
[18] Glickman, M., He, Y., Yucel, R., and Zaslavsky, A. M. (2008). Here's to your health: Misre- porting, missing data, and multiple imputation: Improving accuracy of cancer registry databases. Chance, 21(3):55-58.
11

---

[19] Grgié-Hlača, N., Zafar, M. B., Gummadi, K. P., and Weller, A. (2017). On fairness, diversity and randomness in algorithmic decision making. arXiv preprint arXiv: 10208.
[20] Hardt, M., Price, E., and Srebro, N. (2016). Equality opportunity supervised learning. In Proceedings of the 30th International Conference Machine Learning, pages 3315-3324.
[21] Hébert-Johnson, U.. Kim, M., Reingold, O., and Rothblum, G. (2018). Multicalibration: Calibration for the ccompuatiionlly--dnnfffaaa masses. In International Conference on Machine Learning, pages 1939-1948. PMLR.
[22] Ingels. S. J., Pratt, D. J., Herget, D. R., Burns, L. J., Dever, J. A., Ottem, R., Rogers, J. E., Jin, Y., and Leinwand, S. (2011), High school longitudinal study of 2009 (hsls: 09): Base-year data file documentation. nces 2011-328, National Center for Education Statistics.
[23] Jeong, H., Wang, H., and Calmon, F. P. (2022). Fairness without imputation: A decision tree approach for fair prediction with missing values. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 9558-9566.
[24] Ji, D., Smyth, P., and Steyvers, M. (2020). Can trust my fairness metric? assessing fairness with unlabeled data and bayesian inference. Advances in Neural Information Processing Systems, 33:18600 18.00-0.186..
[25] Jiang, H. and Nachum, O. (2020). Identifying and correcting label bias in machine learning. In International Conference on Artificial Intelligence and Statistics, pages 702-712. PMLR.
[26] Josse, J., Prost, N., Scornet, E., and Varoquaux, G. (2019). On the consistency of supervised learning with missing values. arXiv preprint
[27] Kallus, N., Mao, X., and Zhou, A. (2022). Assessing algorithmic fairness with unobserved protected class using data combination. Management Science, 1853).199
[28] Kamiran, F. and Calders, T. (2011). Data preprocessing techniques for classification without discrimination. Knowledge and Information Systems, 33:1 -33.
[29] Kamiran, F., Karim, A., and Zhang, X. (2012). Decision theory for discrimination--ware classification. In 2012 IEEE 12th international conference on data mining, pages 924-929. IEEE
[30] Kamishima, T., Akaho, S., Asoh, H.. and Sakuma. J. (2012). Fairesss-awaee classifier with prejudice remover regularizer. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2012, Bristol, UK, September 24-28, 2012. Proceedings, Part 23, pages 35-50. Springer.
[31] Khan, S., Ahmad, A., and Mihailidis, A. (2018). Bootstrapping and multiple imputation ensemble approaches for missing data. arXiv preprint arXiv: 1802.00144..
[32] Kim, M. P., Ghorbani, A., and Zou, J. (2019). Multiaccuracy: Black-box post-processing for fairness in classification. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pages 247-254.
[33] Lakkaraju, H., Kleinberg, Leskovee, J., Ludwig, J., and Mullainathan, S. (2017). The selective labels problem: Evaluating algorithmic predictions in the presence of unobservables. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 275-284.
[34] Larson, J., Angwin, J., Kirchner, I.., and Mattu, S. (2016). How we analyzed the compas recidivism algorithm.
[35] Le Morvan, M., Josse, J., Moreau, T., Scornet, E., and Varoquaux, G. (2020). Neumiss networks: differentiable programming for supervised learning with missing values. Advances in Neural Information Processing Systems, 33:5980-599
[36] Le Morvan, M., Josse, J., Scornet, E., and Varoquaux, G. (2021). What's a good imputation predict with missing values? Advances in Neural Information Processing Systems, 34: 1 1530- 1 11540.
[37] Lewis, C., Zephyrin. L., Abrams, M. K., and Seervai, S. (2019). Listening to low-income patients and their physicians: Solutions for improving access and quality in primary care.
[38] Little, R. J. A. (2019). Statistical analysis with missing data, third edition. Wiley Series in Probability and Statistics. John Wiley & Sons, Nashville, TN, 3 edition.
12

---

[39] Longford, N. T., Ely. M., Hardy, R., and Wadsworth, M. E. J. (2000). Handling missing data in diaries of alcohol consumption. Journal of the Royal Statistical Society. Series (Statistics in Society), 133(3):881 -02..
[40] Mansoor, H., Ali, S., Alam, S., Khan, M. A., Hassan, U. U., and Khan, I. (2022). Impact of missing data imputation the fairness and aceuracy of graph node classifiers. In 2022 IEEE International Conference on Big Data (Big Data), pages 5988-5997. IEFE.
[41] Marx, C., Calmon, F., and Ustun, B. (2020). Predictive multiplicity in classification. In International Conference on Machine Learning, pages 6765-6774. PMLR.
[42] Morvan, M. L., Prost, N., Josse, J., Scornet, E., and Varoquaux, G. (2020). Linear predictor on iweaall-ggenerted data with missing values: non consistency and solutions. In Chiappa, S. and Calandra, R., editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 3165-3174, PMLR.
[43] National Cancer Institute (2020). Guidance document: Missing data in seer-cahps.
[44] Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E. (2011). Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830.
[45] Perez-Lebel, A., Varoquaux, G., Le Morvan, M., Josse, J., and Poline, J.-B. (2022). Bench- marking missing-values approaches for predictive models on health databases. GigaScience, 11.
[46] Polyanskiy, Y. and Wu, Y. (2019). Lecture notes on information theory. Lecture Notes for 6.441 (MIT), ECE 563 (UIUC), STAT 364 (Yale).
[47] Rudin, C. (2019). Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature machine intelligence, 1(5):206-215
[48] Schelter. S., He, Y., Khilnani, J., and Stoyanovich, J. (2019). Fairprep: Promoting data first-class citizen in studies on chimess-enhancee interventions. arXiv preprint arXiv:1911.1258
[49] Shah, A., Shen, M., Ryu, J., Das. S., Sattigeri, P., Bu, Y., and Wornell, G. W. (2023). Group fairness with uncertainty in sensitive attributes. arXiv preprint arXiv:2302.0800
[50] Sharafoddini, A., Dubin, J. A., Maslove, D. M., and Lee, J. (2019). A new insight into missing data in intensive care unit patient profiles: Observational study. JMIR Med Inform, 7(1) 1605.
[51] Sheridan, J. (2021). A black woman says she had to hide her race to get fair home appraisal.
[52] Sperrin, M., Martin, G. P., Sisk, R., and Peek, N. (2020). Missing data should be handled differ- ently for prediction than for description causal explanation. Journal of Clinical Epidemiology. 185-188-187.
[53] Subramonian, A., Chang, K.-W., and Sun, Y. (2022). On the discrimination risk of mean aggregation feature imputation in graphs. Advances in Neural Information Processing Systems.
[54] Tsai, W., Cerdeña, J. P., Goedel, W. C., Asch, W. S., Grubbs, V., Mendu, M. I.., and Kaufman, S. (2021). Evaluating the impact and rationale of race-specife estimations of kidney function: estimations from us nhanes, 2015-2018. EClinicalMedicine, 42:101197.
[55] Ustun, B., Liu, Y., and Parkes, D. (2019). Fairness without harm: Decoupled classifiers with preference guarantees. In International Conference on Machine Learning, pages 6373-6382. PMLR.
[56] Ustun, B. and Rudin, C. (2016). Supersparse linear integer models for optimized medical scoring systems. Machine Learning, 102:349-391.
[57] van der Heijden, G. J., T. Donders, A. R., Stijnen, T., and Moons, K. G. (2006). Imputa- tion of missing values superior to complete case analysis and the missing-indicaten method in multivariable diagnostic research: A clinical example. Journal of Clinical Epidemiology. 59(10): 100-1109.
[58] Wang, Y. and Singh, L. (2021). Analyzing the impact of missing values and selection bias on fairness. International Journal of Data Science and Analytics, 1212)1101-119
[59] Wu, Z.. and He, J. (2022). Fairness-aware model-agnostic positive and unlabeled learning. In 2022 ACM Conference on Fairness, Accountabiliry, and Transparency, pages 1698-1708.
13

---

[60] Yang, F,, Cisse, M., and Koyejo, O. O. (2020). Fairness with overlapping groups; a probabilistic perspective. Advances in Neural Information Processing Systems, 33.
[61] Zafar, M. B., Valera, I., Gomez-Rodriguez, M., and Gummadi, K. P. (2019). Faimess constraints:
A flexible approach for fair classification. The Journal of Machine Learning Research, 20(1):2737- 2778.
[62] Zhang, Y. and Long, Q. (2021a). Assessing faimess in the presence of missing data. Advances in neural information processing systems, 34:16007-16019
[63] Zhang, and Long, Q. (2021b). Fairness in missing data imputation. arXiv preprint arXiv:21 10.10012000 12002.
14

---

A Omitted Proofs
A.1 Proof of Theorem
Proof. We prove this theorem via construction. We consider = {0, 1] and construct the probability
distribution Xs, in the following way:
Pr(Y = 0, X = 0|5 = Pr(Y 0, X 1|5 = - 1- ax.
Pr(Y 0, SA 8) = O,
Pr(Y 1, X = 0|5 Pr(Y = 1, 1/5 =8) =0)=0, =0,
Pr(V 1, NA 8) Oss:
and Pr(S = s) = 9.. By the construction of Ps.x,,, we have
Pr(Y 1,5
Pr(Y = 1, S 1) 01q1
Pr(Y = 0,5 = 0) = (1 00000 40-
Pr(Y = 0 - 1) = (1 a a1)41-
For this probability distribution, can compute
1 log g(a).
I(M; Y) (1 (1-00 a) log 1-a a
a
Consider a classifier such that h()) = h(1) = 0 and h(MA) = 1. This classifier satisfies E [T(((X))== = Y) 1 and Disc(h) = O where Disc(h) is the equalized odds constraint. As result, (F(.s.) = for any e. By symmetry, we assume fimp = 1 without loss generality. Therefore, we have
Pr(Y = 0, X = 0/5 = 8) = 1 O2
Pr(Y = 0, X 1|$ = s) 1 0s
2
2
Pr(Y = 1, = 0/5 = =0
Pr(Y= 1|s 8) =0.-
We represent probabilistic classifier / as
Pr(ř = 0/.8 = 0) = Po,
Pr( = 1| = 0) = 1 Po:
Pr(ř 0|_ = Pl
Pr(ř = 1|1 1) 1 Pt.
Consequently,
Pr(r = 0/Y = 0,5 = 8) Po + p1
Pr(Й = 1|V = =0,5 = 8) = Po + pl
Pr(r Y 115 8) P
Pr(f 1|y = = Pl,
which ensures that Disc(h) = where Disc(h) the equalized odds constraint. Furthermore,
E [ - r) Pr(y YY
= -Pr(f = 1 = 1,5 0) = 1,5 + -) =
+ Pr(f 0 0, 0) Pr(Y 0,5 0) 0) 0JY - 1 0,S
Pa + P1
= (1 - (a000 + +agq)) +
(1 a000 - -1
2
Note that oogo a191 Hence,
Ii(p r
Po + P1
max E
max Po.P1E(0,11
(1 p1)a
(1 a)
2
1 1- a
3a
max Po-P. 10
a
2 +
p1.
2
Since a < 11/3, we have a a >
and 1 3a > a result, the above objective function reaches
its maximum 1 when po and P1 both equal to 1. In other words, (.(sss..v' = 1 - D
15

---

A.2 Proof of Lemma
Proof. Let y E {0,1] and 8,8' E.S. Then
Pr(C(X) = y, 8)
E - =s _ (x) = 11 8
;
Σ Ppp[Pr(C, (x) = 1| 5) (x) 1|Y =v
Σ Pye
B Enformation-Theorelee Interpretation of Adding Missing Indicators
We provide an inforoition-theerrtiic perspective for how adding misisng indicators preserves infor- mation in the missing patterns. Let Y be the unobserved predictive label wish to recover, X variable representing the input features, and X the input features under an imputation function fimp. By the data processing inequality, I(Y; X) I(Y; X), showing that imputation can lose information about Y. contrast, because we can recover perfectly from (X, .)) without using any information from Y, I(Y; x) = I(Y; (X, M)), i.e. all of the original information about Y is preserved.
Furthermore, we can use Fano's inequality [Theorem 6.3 in 46] to relate the information loss from imputation classification error probability. Let h be elassifier and denote the classification error as pe (X) P(Y * h(X)). Fano's inequality states that
H2(p=(X)) + (X( log( D 2 H(
where y' denotes the support of Y, Hz) - log2 (1 p) logz (1- p) is the binary entopy function, and XY = Eis Plyi, log ((); is the conditional entropy. Since Y E (0, 1]. the inequality reduces to
(2(p((X)) H(YI)) px( 2 H(Y)X) (log, 3 1)
since Hp(p) S + log, 3 - with equality achieved at This is lower bound on Pa (X) in terms of H(|[X). Now, we can compare HY) and H HY|((X, M)). By above, we have
I(Y: 18; M)) 2 I(Y;
H(Y) H(I M)) 2 HYY H
H(YI(X, - (Y)
Therefore, Fano's inequality gives better lower bound for Pe (X, .M) than for pe (X). We conclude that a classifier trained from adding missing indicators is more likely to achieve higher accuracy under the same group fairness constraint than classifier trained using ihpute-then-classify.
C More Details Algorithms
include a figure illustrating the three adaptive algorithms presented Section for fair linear classifiers and the FairMissBar algorithm presented in Section 5. We also provide pseudocode for the recursive partitioning procedure the missing pattern clustering algorithm and the fair uniform resampling procedure in FairMissBag.
16

---

C.1
Illustration of adaatiie algorithms
Affinely adaptive
Baseline
classification
Fairesss interventions
31
22
meg
maa
mi Jan
Missing pattern clustering
1
0
D
h1
h1
-1
-1
0
0)
D
-1
1
-1
h22
NA
2
D
hB
Adding missing
Fair resampling
Fair ensemble
indicators
missing indicators
(a) Fair linear classifiers
(b) FairMissBag
Figure 4: Illustration of the three adaptive algorithms for fair linear classifiers (left) and FairMissBag (right). Adding missing indicators and affinely adaptive classification encode missing value patterns via additional imput features, while missing pattern clustering partitions the dataset based on missing patterns. FairMi ssBag intervention to train a fair classifier on each resampled dataset, and obtaining a prediction from the ensemble of fair classifiers.
three-step algorithm consisting of fair resampling, using fairness
C.2 Recursive partitioning algorithm for missing pattern clustering
We begin with a single cluster containing the entire dataset. each step, we split cluster on feature j* E G(M,) that minimizes the objective function T(Mg::), where G(M,) denotes the set of features that satisfy the bounded representation and minimum cluster size constraints.
Algorithm Recursive partitioning of missing patterns.
Input: (as, 8;; 3/ )= Initialize: partition P 0, =M
while P' + Ø do
Mg P'
p' P' M,
if G(M,) Ø then
p - PUM,
continue end if
j" f- arg migmin) I(Mg.J)
if L(M,)) minnew Eie,, E(yi, h(xx)) then
p' {MS M
else
P P-PUM. end if end while
Return: P= (Ma
C.3
Fair uniform resampling algorithm
The data is separated into groups based on sensitive attribute and label. From each group, make new group of the same size by sampling data points uniformly with replacement. These groups are combined to create subsample of the same size the original dataset.
17

---

6-
22
1=55=00
Y 0=
y --0
Figure 5: Plot of the synthetic data. The points on the æ-axis represent data with X₂ missing.
Algorithm 2 Single iteration of fair uniform resampling.
Input: D {ai 81 V- Initialize: D === 2
for E {0. 1 do
for y {0, do
Da.y - {2i, Sú, yi E 8, 1-==-) y)
Sample |Da.yl times from Da,y uniformly with replacement and append D''
end for end for Add missing indicators to D', apply imputation method fimp Return: Resampled dataset D
D Details on the Experimental Results
We provide a description of the synthetic dataset mentioned at the end of Section 6.2 and a description of COMPAS/Adult. We also summarize hyperparameters and implementation details.
D.1 Description synthetic data
We create synthetic dataset by sampling data points from a known distribution and generating artificial missing values. The dataset contains two features, X1 and X2, with binary sensitive attribute and binary label Y. There are 2400 data points in total. X1 present for all data points, while X₂ is missing in 800 of the data points. For each combination of predictive label and sensitive attribute, we sample data points from a different, fixed distribution (bivariate Normal for data points with X2 present and Gaussian for data points with X₂ missing). The distribution of the data points is summarized in table 1, and we visualize 800 of the data points in figure 5.
X present
Gmup
Distribution
N
missing
33
2
0
P,X,,X, = 1, 1) N
0
2
400
Group
Distribution
-3
[2
P(X.Y 1,5 1,5=1) 1) W((,3)
100
X
N
+3
[
2
400
P(X. = 1,5 0) ./(,3))
300
+33
2 0
P(X Y 0,5
WV-3,3)
100
0,5 N
400
-3
0
P(X. = 0.5 (V-3,33)
+3
2 0
P(G, 0,5 NZ
400
0 2
Table 1: Distribution of the synthetic data. N denotes the number of data points sampled from the group distribution.
18

---

D.2 Description of COMPAS and Adult datasets
COMPAS, The COMPAS (Correctional Offender Management Profiling for Alternative Sanctions) software is a proprictary tool that is used in the criminal justice system in the United States to predict recidivism. COMPAS uses a defendant's criminal history along with other features such as demographic information to assign score indicating the predicted risk of the defendant recidivating within two-year period. Racial discrimination in the COMPAS algorithm's predictions has been highly publicized and analyzed [11, 16, 34].
We restrict our experiments with the COMPAS dataset the set of White and Black defendants. The predictive features we use are age (three categories of less than 25, 25 to 45, and over 45), race, sex, normalized number of prior convictions, and charge degree (misdemeanor/felonyy) The predictive label is a binary indicator for whether the defendant recidivated in a two-year period, and the sensitive attribute is race (S 0 for Black defendants, S for White defendants). We additionally balance the dataset so that the number of Black and White defendants in the data are equal, yielding 4206 data points in the dataset.
The Adult dataset is a subset of the data from the 1994 Census. The predictive label is a indicator for whether a person's 's annual income is over $50,000, and the sensitive attribute is gender. We use all of the 14 features in the original dataset except folwgr (see [12]). We first balance the dataset by the predictive label and then by gender, yielding 6530 points in the dataset. All features are scaled to be between 0 and 1. We additionally use IPUMS Adult, a reconstructed superset of the original Adult dataset [9, 15], which contains 11996 points after balancing for predictive label and gender.
Adult.
Missing value generation. Since COMPAS is complete dataset and Adult has very low percentage of missing values, we generate missing values synthetically. For each dataset, we create three datasets with missing values corresponding to MCAR, MAR, and MNAR capture the range of possible missing mechanisms. For each missing mechanism, we choose one or more features to contain missing values. Then, we randomly replace some of the values of the feature(s) with NA with a given probability. Other than the MCAR setting, we allow the probability to vary depending on the value of one of more features in the data or a binary indicator corresponding to the feature, including the missing feature(s). Notably, for MNAR, we allow the missingness of a feature to depend on the predictive label to simulate the scenario where the missingness pattern and label linked. Statisties for missing values in COMPAS and Adult are provided in Table 2.
COMPAS
Mcchanism
Missing feature
Pr(MS) 0)
Pr(MS) = 1)
MCAR
priors_come crorr_ccount
N/A
0.2
0.2
MAR
priors count
sex
0.1
0.4
MNAR
priors_ count
twar year recid
recid
0.1
0.4
SCX
SCX
0.1
0.4
Adult
Mechanism
Missing feature
Pr(MS)/ = 0)
Pr(MS)/ = 1)
MCAR
age
N/A
0.2
0.2
MAR
occupation
gender
0.4
0.1
MNAR
capital-gain
income
0.3
0.1
workclass
L[age < 0.2]
0.1
0.4
Table 2: Missing value statisties for COMPAS and Adult. I denotes the feature or indicator
which the probability of missingness depends. As an example, for COMPAS in the MAR setting, the missing feature is priors_coe _ount: the probability of priors_count being missing is 0.1 among women (sex= = 0) and 0.4 among men (sex = 1).
19

---

D.3 Hyperparameters
For algorithms with tunable hyperparameters used in the experiments, we report the values of the hyperparameters that were tested in Table 3.
Algunihm
Hyperprameter
Symbhtic
COMPAS/Acil
HSLL
Biaghlia astantrentt
(0.11,01111 I, 10, 100)
10.01, 0,1,1,2, 10)
0.1,1, 10, 100)
FairPxojection
10, 0.111..
(0,0.001,000
01.0.1)
(0,0.00100001 0.01,00,..11.,,,00000,
Reduction
NIA
N/A
(0.001, 0,005, 0.01, 6.02, 0.05, 0.5.
RBC
NAA
N/A
10.001, 0.003, 0.01, 0.00, 0.1.O.3. 13
Mossing porsem clustering
1500,
(o..5)
(1,0)
NAA
(0.6.033)
Table 3: Summary of hyperparameters tested for the experiments with linear fair classifiers. The sesparateMistreattteet FairProjections Reducti on, and ROC rithms have tunable hyperparameters, as well as the missing pattern clustering adaptive algorithm.
algo-
Algorithm
Hyperparameter
Values
FairProjection
tol
(0.000,0.001,,.. 0.01, 0.13
Reduction
e
(0.001, 0.110,,0.0 13
FairMissBag
# bags
20 (FairProjection)
10 (Reduction, Eqodds)
Table 4: Summary of hyperparameters tested for the experiments with general fair classifiers. The FairProjection and Reduction fairness-inten interveiinttrenniionn algorithms have tunable hyperparameters, as does FairMissBag.
D.4 Implementation details
We run DispMistreatment with FNR difference constraint, FairProjection, Reduction, EqOdds, ROC with equalized odds/mean equalized odds (EO/MEO) constraint, and Leveraging with an equality of opportunity constraint.
We implement DispMMistreatment using the code at attps:///ithuu: wtw.hhub..cmmmmlllllaaaaaa fair-claasificationn.oor FairProjection, we use code from https://github. com/ HssiangHsauFFiir-PPojjettt The original code for Leveraging is found at https:///itthttt car//Iucaoneet//MIP220001.__L
we use a Python version of the code included in the FairProjection repository. Reduction, EqDdds, and ROC are implemented using the AIF360 library [3]. All experiments were run on a personal computer with 4 CPU cores and 16GB memory.
E
Additional Experimental Results
E.1
Linear fair classifiers
Synthetic data. Figure displays fairness-accurace curves for the synthetic dataset. We see that for both DispMistreatment and PairProjection missing pattern clustering (Section 4.3) achieves near-pertee wear-perfect accuracy with very little discrimination. constrast, the bascline performs much worse in both cases; for DispMtistreatment, the baseline classifier only achieves the same faimess as missing pattern clustering with an accuracy that is essentially no better than a random guess. Adding missing indicators outperforms the baseline for DispMis DispMistreatmm treatment but remains significantly worse than missing pattern clustering, and performs nearly identically to the baseline FairProjection
These results make intuitive sense given the distribution of the synthetic data. [[X1 < 0) is near-perfect linear classifier for the data points with X2 present, and [[X, > 0) is a near-perfect linear classifier for the data points with X₂ missing. However, if we use impute-then-classie zero imputation, a baseline linear classifier will perform poorly on the data points with X₂ missing. Moreover, because the S 0 sensitive group has many more such points, the group will likely suffer
with
20

---

Syrthetic data, eesmmnt
Synthetic data. FeirProjection
1+1
Beselnn
Adling mising inclaaioos
Adding miiiin indicaturs
0.4
Moaling prrtm dustering
Mieding pattern cuatering
0.45
0.7-
0.80
0.3
0.000
0.025
3,050
0.075
0.100
C.125
0.350
0:375
0.05
0:30
0.75
0:20
P00 diffcrance
NEO
Figure 6: Comparison of adaptive fairness-interventioon algorithms on the synthetic dataset, using DispMistreatment (left) and FairProjection (right). Error bars depict the standard error of runs with different train-test splits.
from higher FNR and FPR, increasing the discrimination. Furthermore, this is true even a missing indicator for X2 is added, the indicator only provide adjustment for the bias and not the coefficient X1, However, if missing pattern clustering is used, separate linear classifiers can be trained on each cluster reach very high accuracy and fairness.
MCAR
MAR
PNAR
0.70
0.2
0.82
0.50
0.00
0.58
0.50
0.54
Jaeeine
062
0.5
0.52
Soding mine Indeaso
0.60
0.38
0100
D30
0.r
6125 0.75
0.10
0:32
difernnce
(a) COMPAS, DispMistreatment
taoeline
0.751
Adding ribiing Indeatrr
0772
0.756
87775
1.550
0.754
0746
0.750
0744
0.50
5.5
0.10
315
0.20
0.:0
0.15
0.75
0.10 315
9.20
FNR difforence
PMR difference
RNR 3ifferanze
(b) Adult, DispMisttreammnt
Figure 7: Comparison of adaptive DispMistreaament. For each of COMPAS and Adult, we generate three datasets with missing values corresponding to MCAR, MAR, and MNAR mechanisms (Appendix D.2). Error bars depict the standard error of 10 runs with different train-test splits.
algorithms COMPAS and Adult using
Figure displays the fairncss-accurac curves for Reduction, EqDdds, ROC, Leveraging. We that adding missing indicators improves the fairness-accuracy accuracy tradcoff for all fairness inter- ventions except EqUdds.
HSLS.
We report additional results for the missing pattern clustering algorithm on the HSLS dataset. As indicated above, we tested minimum cluster sizes of 500, 1000, 1500, 2000, and 4000. The average number of clusters produced from missing pattern clustering across all trials was 2.5 for t: = 500, 1.8 for k = 1000 and 1500, 1.5 for 2000, and 1.3 for 4000. The highest number of clusters obtained from single trial was 5. As the minimum cluster size is increased, the average number of clusters decreases monotonically as expected. The low average cluster counts indicate that the missing pattern clustering algorithm was not always able to find viable split of the missing patterns
21

---

HSL5
0.700
0.695
0.690
Accurty
Reduction (Baseline)
Reduction (Adding missing indicators)
(Baseline)
EqOdds (Adding missing indicators)
(Baseline)
ROC (Adding missing indicators)
Leveraging (Baseline)
Leveraging (Adding missing indicators)
0.02
0.04
0.06
0
0.22
0.14
MEO
Comparison of adding missing indicators (Section 4.1) with baseline impute-then-classity on HSLS, using Reduction, EqOdds, ROC, and Leveraging. Error bars depict the standard error of 15 runs with different train-test splits..
Figure 8:
MCAR
0.640
0.70
0.655
Accuracy
Accuracy
0.635
0.68
0.650
0.56
0.645
0.64
0.625
0
0.2
0.3
0.4
0.2
D.3
0.4
0.10
0.15
0.20
0.25
0.30
Mean Equalized Odds
Mean Equalized Dods
Mean Equalized Olds
Baseline (mean)
Basel (KNN)
Basellie (iterative)
FairMissBag (mean)
FairMissBag (KNN)
FairMissBag (iterative)
Figure 9: Results for FairMissBar generate three datasets with missing values corresponding to MCAR, MAR and MNAR mechanisms (Section D.2). Fairness-accuracy eurves for mean, KNN, and iterative imputation shown. Error bars depict the standard error of 5 runs with different train-test splits.
COMPAS using FairProjection Using COMPAS,
(see discussion of semi-synthetic experimental results Section 6.2 an explanation on this behavior).
E.2 Non-linear fair classifiers
COMPAS. Figure 9 displays the results of the FairMissBag experiment on COMPAS. When missing values are MNAR, FairMissBag shows large improvements in both accuracy and faimesss for all three imputation mechanisms.
22


Reviews:
[{"review_id": "zCKSURMZMh", "reviewer": "Reviewer_oma2", "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:\n- 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);\n- a theorem capturing the performance gap between optimal solutions when employing a generic imputation mechanism vs. not when using equalized odds (information-theoretic result);\n- methods for adapting fairness-intervention algorithms to missing data, both for linear and non-linear settings;\n- empirical evaluation of their proposed methods.\n\nTheir 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.", "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.\n\n2. What implications does Theorem 1 have in a less trivial/higher dimensional setting? The multiclass classification setting?\n\n3. Please refer to the Weaknesses/Suggestions section for additional questions around the linear adaptation methods, results, and trade-offs.", "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.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Clear motivation of the problem setting, both in the introduction and recapping in the conclusion.\n\n- Overall, mathematical notation is quite clean and easy to follow. \n\n- 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. \n\n- 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).\n\n- 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.\n\n- 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.\n\nFurthermore, 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?\n\nAdditional suggestions:\n- 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.\n\n- 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.  \n\n- 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. :]\n\n- Nit: please include references in the main paper to additional results/content in the Appendix throughout, i.e. proofs, additional experimental details, etc.\n\n- Minor nit: please include the year in citation references.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments and for appreciating the novelty and value of the work! \n\n---\n**Q1. Trade-offs between the three methods for linear classifiers.**\n\nPlease refer to our response for Q2 below.\n\n**Q2. 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?**\n\nA2. We thank the reviewer for raising this point. We introduced three adaptive algorithms for linear classifiers since, across our experiments in the main text and the appendix, no single method consistently dominates fairness-accuracy performance. Our suggestion is for users to consider the choice of intervention as a hyperparameter and select based on a validation set. We briefly summarize the trade-offs between these methods in terms of complexity and performance [this discussion will be added to the updated paper]:\n\n- Adding missing value indicators [Sec 4.1] is the simplest intervention, which is arguably its main appeal. The advantage of this approach in linear models is that model weights assigned to missing-value indicators may enable users to interpret (to the extent that linear models are interpretable) how missingness is incorporated in classification. Adding missing indicators can achieve comparable performance to the other two methods (cf. Fig 2, 7), though tends to perform worse on average.\n- Affinely adaptive classification [Sec 4.2] is more flexible than adding missing value indicators, with the drawback of requiring additional parameters in the model (see lines 204-207). This method performs competitively with adding missing indicator values and can achieve higher accuracy (cf. Fig 2, 7). However, the user should weigh the benefit of a potential gain in accuracy given against the additional complexity cost.\n- Missing pattern clustering [Sec 4.3] can achieve the best fairness-accuracy performance if the missing value patterns can be clustered such that applying separate fairness interventions on each cluster is advantageous. Note that here the classifier is linear per cluster, but not as a whole. Figure 6 in the appendix displays experiments on synthetic data where missing pattern clustering achieves a far better accuracy-fairness operation point. Appendix E.1 explains why this performance is observed. This gain in performance was more muted in the experiments in Figure 1 and 2. Ultimately, missing pattern clustering should be preferred when sufficient data is available to cluster missing patterns.\n\n---\n**Q3. Providing more rationale between proof steps.**\n\nA3. Absolutely, that's an excellent suggestion! We'll certainly expand on the proofs in the Appendix, providing a more detailed explanation as well as offering intuitive insight. For additional information, please refer to our responses to Q8.\n\n---\n**Q4. Interpretability and accessibility of plots (Figures 1-3).**\n\nA4. Please see above for a discussion of the trade-offs between different proposed methods. We will provide updated figures and captions to improve accessibility and interpretability in the revised paper.\n\n---\n\n**Q5-7. Nits and minor nits stated in Weaknesses.**\n\nA5-7. Thank you for raising these important clarification points – we will update the manuscript addressing all the nits and minor nits. We will add additional pointers to the appendix in the main text.\n\n---\n**Q8. 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.**\n\nA8. Thank you for carefully reviewing the proof. We provide additional details below which will be incorporated into the revised paper. \nBy our constructed data distribution $P_{S,X,Y}$ in lines 531-532, we know\n$$\nPr(Y=1, S=0) \n= (Pr(Y=1, X=0 | S=0) + Pr(Y=1, X=1 | S=0) + Pr(Y=1, X=NA | S=0)) \\cdot Pr(S=0)\n= \\alpha_0 q_0\n$$\nwhere $q_0$ denotes $Pr(S=0)$. \nSimilarly, we have\n$$\nPr(Y=1, S=1) = \\alpha_1 q_1, \nPr(Y=0, S=0) = (1-\\alpha_0) q_0,\nPr(Y=0, S=1) = (1-\\alpha_1) q_1.\n$$\nNow we have\n$$\nPr(\\hat{Y} = Y) = Pr(\\hat{Y} = 1| Y=1, S=0) Pr(Y=1, S=0)  + Pr(\\hat{Y} = 1| Y=1, S=1) Pr(Y=1, S=1) + Pr(\\hat{Y} = 0 | Y=0, S=0) Pr(Y=0, S=0) + Pr(\\hat{Y} = 0 | Y=0, S=1) Pr(Y=0, S=1)\n= (1-p_1) (\\alpha_0 q_0 + \\alpha_1 q_1) + \\frac{p_0 + p_1}{2} \\cdot ((1-\\alpha_0) q_0 + (1-\\alpha_1) q_1)\n$$\nwhere the last step uses the equations between lines 538 and 539, coupled with the equations we elaborated above. Lastly, note that $q_0 + q_1 = 1$. This leads us to the desired equation.\n\nRegarding $\\alpha < 1/3$, we apply it in the final step of the equation from line 540 to 541. Given this condition, we have $1-\\alpha > 0$ and $1-3\\alpha > 0$. As a result, the objective function reaches its maximum when $p_0$ and $p_1$ are both equal to 1.\n\n---\n**Q9. What implications does Theorem 1 have in a less trivial/higher dimensional setting? The multiclass classification setting?**\n\nA9. Yes, Theorem 1 can be extended to the multi-class setting. It can also be extended to the setting where $X$ is composed by two variables $X_{obs}$ and  $X_{ms}$ where  $X_{obs}$ is always observed and $X_{ms}$ has missing values according to a certain probability. In this case, the statement of Theorem 1 still holds while the mutual information is replaced by the conditional mutual information $I(M;Y|X_{obs})$. \n\n---\n**Q10. Please refer to the Weaknesses/Suggestions section for additional questions around the linear adaptation methods, results, and trade-offs.**\n\nA10. We hope our response has addressed all of your comments. Please feel free to let us know if you have any additional comments that can help us further improve the paper.\n"}, {"review_id": "oFL2KSf2FN", "reviewer": "Reviewer_GNEv", "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.", "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$. \n\n* (2) The notation w.r.t. accuracy $\\mathbb{I}$ is given without any explanations.\n\n* (3) Should there be any conditional independency between $\\hat{X}$ and $Y$, in line 190?", "limitations": "Please refer to the section of **Weakness**.", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "* Theoretical illustration on the conclusion that ``imputed data harms the group fairness as well as the averaged accuracy\".\n\n* The authors propose three methods for adapting linear fair classifiers to missing values:\n\n     * **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;\n\n     * **Method 2:** Affinely adaptive classification;\n\n     * **Method 3:** Missing pattern clustering;\n\n* A general algorithm for  nonlinear classifiers.\n\n* 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**).\n\n* (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:\n\n  * (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). \n\n  * (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$).\n\nAlthough the example itself is correct, it is hard to believe whether the conclusion will remain the same in more complex scenario.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the kind comments and the encouragement!\n\n---------\n**Q1. Although the overall presentation is well-done, some parts could be much better if modified accordingly (please refer to questions).**\n\nA1. We appreciate your constructive feedback! Please find our detailed responses to your questions below, where we hope to adequately address all your concerns.\n\n---------\n\n**Q2. 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.**\n\nA2. This is a great point! Regarding your (2a), Theorem 1 can indeed be generalized to a scenario where $X$ is made up of two variables $X_{obs}$ and $X_{ms}$. In this situation, $X_{obs}$ is always observed while $X_{ms}$ has missing values according to a certain probability. Under these setting, Theorem 1 remains valid; however, the mutual information is substituted by the conditional mutual information $I(M;Y|X_{obs})$. Regarding your (2b), our theorem relies on this assumption to maximize the dependency of the predicted label on the missing pattern. We could extend our results to a more general scenario where $Pr(Y=1,X=0|S=s)\\neq 0$, but this might result in a looser upper bound in Theorem 1.\n\n\n---------\n**Q3. 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$.**\n\nA3. Thank you for the suggestion! In this paper, we focus on a specific setting where the input variables $x$ may have missing values. We will clarify this aspect in our abstract.\n\n---------\n**Q4. The notation w.r.t. accuracy $\\mathbb{I}$ is given without any explanations.**\n\nA4. Thanks for highlighting this issue. To clarify, $\\mathbb{I}$ stands for the indicator function. It is defined as $\\mathbb{I}(event) = 1$ if the event is true, otherwise, it is 0. We will add this definition at the beginning of Section 2.\n\n---------\n**Q5. Should there be any conditional independence between $\\hat{X}$ and $Y$ in line 190?**\n\nA5. You are indeed correct! The imputed variable $\\hat{X}$ is derived by applying an imputation mechanism to $X$ without knowledge of $Y$ (since $Y$ is the predicted label), which yields the Markov chain: $Y–X–\\hat{X}$, meaning that $\\hat{X}$ and $Y$ are independent when conditioned on the observed value of $X$. In light of this, we use the data processing inequality, which allows us to arrive at the desired inequality: $I(Y; X) \\geq I(Y; \\hat{X})$.\n"}, {"review_id": "KmJQgND9SW", "reviewer": "Reviewer_ZFNz", "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.", "questions": "Could the authors elaborate on the group fairness achieved by their strategy vs the other baselines in the empirical analysis?", "limitations": "yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "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. \n\n*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. \n\n*CLARITY.* This work is clearly structured and well-written---I enjoyed the read! \n\n*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. \n\n*MINOR COMMENTS* \n- The core contributions of this work seem to be applicable to general cases of missing data, not just fairness.\n- Lines 114-117, providing a small example of the different types of reason for missing data could strengthen the description in this paragraph. \n- Eqn 1 define the indicator function and distribution of interest in the expected value \n- Fano's inequality (line 193) should be cited", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's thoughtful comments and we are glad to learn that you found our paper enjoyable to read!\n\n---------\n**Q1. 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.**\n\nA1. Thank you for raising this clarification point. We highlight that the x-axis of all the plots in the paper (Figs. 1-3 in the main text, and Figs. 6-9 in the Appendix) have a group fairness metric in the x-axis, and accuracy in the y-axis. Consequently, our empirical analysis explicitly compares accuracy and group fairness values achieved by different imputation strategies and fairness interventions across datasets and missing value patterns. Fairness-accuracy plots are standard visualizations for benchmarking fairness interventions (see, for example, [1] and [2]).\n\n---------\n**Q2. The core contributions of this work seem to be applicable to general cases of missing data, not just fairness.**\n\nA2. Indeed, you are correct. A substantial number of our methods and algorithms are applicable to a range of supervised learning scenarios that involve missing values. We chose to concentrate on the fairness implications of missing data as it is a practical problem but has not received adequate attention in the fair ML literature.\n\n---------\n**Q3. Lines 114-117, providing a small example of the different types of reason for missing data could strengthen the description in this paragraph.**\n\nA3. Yes, this is a great point! To illustrate the three missing mechanisms, we can use an example of student survey responses:\n\nMCAR: For each student, each question has an equal probability p of not being answered.\n\nMAR: Certain questions are more likely to be left blank depending on other factors. For example, lower-income students may be less likely to have taken expensive tests and consequently are more likely to leave questions about test scores blank.\n\nMNAR: The probability of a question being left blank depends on the true answer. For example, a student whose parents have not completed high school may leave a question on the parents’ highest degree blank.\n\nWe will include this example in the revised paper.\n\n---------\n**Q4. Eqn 1 define the indicator function and distribution of interest in the expected value.**\n\nA4. The indicator function takes the value of $1$ if $h(x) = y$; otherwise, it is 0. The distribution of interest is the data generating distribution $P_{X,Y,S}$ where $X$ is the input feature vector which may contain missing values; $Y$ is the label; and $S$ is the group attribute. We will include this clarification in the revised paper.\n\n---------\n**Q5. Fano's inequality (line 193) should be cited**\n\nA5. Thanks for pointing out this issue! Please refer to Theorem 6.3 in the textbook by Polyanskiy and Wu, 2022. This reference will be incorporated into our revised paper.\n\n—Polyanskiy, Y. and Wu, Y., 2022. Information theory: From coding to learning.\n\n---------\n**Q6. Could the authors elaborate on the group fairness achieved by their strategy vs the other baselines in the empirical analysis?**\n\nA6. (Please see response to Q1 as well). In all of our plots, the x-axis corresponds to a group fairness metric. For example, in Figure 2, the baseline models are represented by the red curves. The baseline model is a logistic regression classifier combined with the DispMistreatment fairness intervention [58] and FairProjection [2] on the left and right, respectively, both using zero imputation to handle missing values. Their fairness-accuracy trade-off is pareto-dominated by the proposed methods for preserving information about missing values. We observe a similar pattern, i.e. the proposed methods pareto-dominating the fairness-accuracy plot, across all experiments.\n"}, {"review_id": "cQVxB3Eq7S", "reviewer": "Reviewer_RyBS", "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.", "questions": "1. What is the definition of the function h in equation (1)? Also, Disc(h) should be Disc(h(X)) in equation (1).\n\n2. 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?\n\n3. 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?\n\n4. How are the B datasets created in lines 249-250? Line 248 indicates there is only one combined dataset.\n\n5. 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.\n\n6. For the HSLS dataset, why do the authors only consider datapoints where race and 9th grade math test score are present?\n\n7. 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.", "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. ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "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.\n\n2. 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. \n\n3. 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.\n\nOverall, 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.\n\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful review and for appreciating the merits of the work!\n\n**W1. 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.**\n\nA1. This is a great point! Please refer to section (a) in our answer to Q1 in the global response.\n\n\n---\n**W2. 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.**\n\nA2. Thank you for the point of clarification. We note that while the empirical evaluations with FairProjection use equalized odds, we use equality of opportunity (FNR difference) for the results with DispMistreatment. These are primary fairness measures supported by the FairProjection and DispMistreatment fairness interventions. Additionally, while the fairness guarantee for the ensemble algorithm in Section 5 is presented for equalized odds, the guarantee also holds for other fairness measures such as statistical parity and equality of opportunity. We will update the caption with the full name of MEO in the revised paper.\n\n---\n**Q1. Clarification of equation (1).**\n\nA3. The function $h: \\mathcal{X}\\to \\mathcal{Y}$ represents a classifier, predicting the label $y$ based on input features $x$. We will make this clear in the revised paper and replace $Disc(h)$ with $Disc(h(X))$ as you suggested.\n\n---\n**Q2. Extending framework to multiaccuracy and multicalibration notions of fairness.**\n\nA4. Thanks for pointing this out –  please refer to section (b) in our answer to Q1 in the global response where we address this point.\n\n---\n**Q3. Comparing to Jeong et al; definition of MIA**\n\nA5. This is a great point. We encountered some challenges when attempting to compare our proposed methods to the FairMIPForest algorithm in Jeong et al., in that 1) the code for FairMIPForest does not support MEO and 2) DispMistreatment is a linear fairness intervention, hindering a sound comparison between FairMIPForest and either DispMistreatment or FairProjection. MIA stands for the “missingness incorporated in attribute” approach for training decision trees with missing values (see Twala et al. 2008). We will provide the full name in the revised paper.\n\nReferences:\n\nTwala, B. E., Jones, M. C., & Hand, D. J. (2008). Good methods for coping with missing data in decision trees. \n\n---\n**Q4. How are the B datasets created in lines 249-250? Line 248 indicates there is only one combined dataset.**\n\nA6. Lines 247-249 describe the procedure to draw a single resampled dataset from the original dataset. The B datasets are created by repeating this procedure B times. We will clarify this in the revised paper.\n\n---\n**Q5. Comparison to Bootstrap-S algorithm in Shah et al.**\n\nA7. Thank you for bringing this work to our attention. Our algorithm in Section 5 and the Bootstrap-S algorithm presented in Shah et al. are indeed similar in using bootstrapping to satisfy strengthened fairness conditions. The key difference is that our algorithm explicitly uses (known) sensitive attributes and labels when drawing subsamples to ensure sample diversity. We will include this comparison in the related work section in the updated paper.\n\n---\n**Q6. For the HSLS dataset, why do the authors only consider datapoints where race and 9th grade math test score are present?**\n\nA8. This is a great question. For HSLS, we used race as the group attribute and 9th grade math test score as the label. As mentioned above, the fairness interventions with which our proposed methods are used may require knowledge of the group attribute, and our empirical results used interventions that use knowledge of the group attribute and label to calculate fairness metrics.\n\n---\n**Q7. Clarifying the focus of the paper in the abstract and introduction.**\n\nA9. Thank you for highlighting this issue. We will ensure that both the abstract and introduction clearly state the context being considered in this paper.\n\n---\n**Q8. Elaborating on potential negative impact of methodology in Section 7.**\n\nA10. We thank the reviewer for raising this important point. We acknowledge that using missingness information in a fair classifier may have potential negative impacts. For example, an individual may be incentivized to purposefully hide data if their true values are less favorable than even \\texttt{NA}. In missing pattern clustering, an individual may be classified less favorably or accurately than a classifier from a different cluster. These scenarios highlight 1) important considerations with respect to individual and preference-based fairness notions (cf. Ustun et al. 2019), and 2) the importance of carefully weighing the advantages and disadvantages of each of our proposed methods prior to use. We will elaborate on these issues in the revised paper.\n\nReference:\n\nUstun, B., Liu, Y., & Parkes, D. (2019). Fairness without harm: Decoupled classifiers with preference guarantees.\n"}, {"review_id": "7pPrqFP52z", "reviewer": "Reviewer_SEin", "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.", "questions": "In line of W1, can you provide in-depth discussion on the extension of the sensitive-attribute-missing scenario? \n\nIn light of W4: any intuition why the fundamental degradation of accuracy is expressed in terms of mutual information?", "limitations": "Please see Weaknesses in the above.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "S1. The paper focuses on a significant issue that arises in numerous applications.\n\nS2. By utilizing the concept of mutual information, the paper reveals the fundamental limitation of impute-then-classify methods.\n\nS3. 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.\n\nW2. 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.\n\nW3. 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.\n\nW4. Theorem 1 looks interesting, but the main body of the paper lacks technical discussion, not even including proof sketch.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful read of our paper and constructive comments!\n\n---\n**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.**\n\nA1. We completely agree that the problem of missing group (sensitive) attributes is of significant practical importance. Indeed, there is a growing body of research (Kallus et al. 2022, Zhang and Long 2021) in fair ML dedicated to addressing this issue. However, we also emphasize that the problem of missing input features is equally crucial and widespread, yet less studied. For instance, in the HSLS dataset used in our experiment, 35.5% of White and Asian students did not report their secondary caregiver’s highest level of education; this proportion increases to 51.0% for underrepresented minority students. Missingness patterns can vary significantly across population groups and hinder fairness-accuracy performance if not adequately accounted for. Unfortunately, the matter of missing input features has not received adequate attention in fair ML literature, with the majority of interventions assuming complete input features.\n\nThe primary objective of this paper is to bridge this gap and offer a comprehensive study encompassing theory and algorithms for training fair classifiers in the presence of missing input feature values, particularly when missingness patterns vary per population group (as observed in practice). We aim to shed light on this overlooked aspect and propose solutions to challenges arising from disparate missingness patterns. To address your concerns, we will revise our abstract and introduction to provide a clearer presentation of our setup and discuss the issue of missing group attributes by doing a more thorough job acknowledging this important line of work.\n\nReferences:\n\nKallus, N., Mao, X., & Zhou, A. (2022). Assessing algorithmic fairness with unobserved protected class using data combination.\n\nZhang, Y., & Long, Q. (2021). Assessing fairness in the presence of missing data.\n\n---\n**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.**\n\nA2. Please refer to our response to W1. We would like to emphasize the differences between our study and [3]. Not only do we adapt their algorithms for the fairness context, but we also develop a *new* universal adaptive algorithm outlined in Section 5 which allows for the adaptation of *any* group-fairness intervention to account for missing values. In contrast, [3] focuses on linear models only. In Section 3, we also derive a theorem that articulates the fairness risks associated with training on imputed data. Furthermore, our work involves extensive numerical experiments using state-of-the-art fairness interventions across multiple benchmark datasets (see Appendix E).\n\n---\n**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.**\n\nA3. We thank the reviewer for raising this point! Please refer to our response to Reviewer oma2’s Q1 and Q2.\n\n---\n**W4. Theorem 1 looks interesting, but the main body of the paper lacks technical discussion, not even including proof sketch.**\n\nA4. We are glad to learn that you find Theorem 1 interesting! This theorem was established by creating a specific data generating distribution and identifying the optimal classifiers for both data with missing values and imputed data. We intend to add a sketch of the proof in order to provide further clarity and enhance understanding of the theorem's underlying rationale.\n\n---\n**Q1. In line of W1, can you provide in-depth discussion on the extension of the sensitive-attribute-missing scenario?**\n\nA5. Absolutely – please refer to section (a) of our answer to Q1 in the global response.\n\n---\n**Q2. In light of W4: any intuition why the fundamental degradation of accuracy is expressed in terms of mutual information?**\n\nA6. The underlying rationale for Theorem 1 is that as missing patterns provide more information about the predictive label, the fairness-accuracy performance of impute-then-classify deteriorates. This occurs as imputing the data loses information about the label that was contributed by the missing patterns. We use mutual information to measure the extent of this information, since mutual information is a standard metric for assessing the dependence between two random variables. It also enables us to apply Fano’s inequality to relate the information loss from imputation to classification error probability (see Appendix B).\n"}]

Author rebuttal:
We would like to thank all the reviewers for taking the time and effort to review our paper! We are delighted to receive positive feedback for the key components of the paper; in particular, that: our information-theoretic result characterizing the limitation of impute-then-classify provides novel and meaningful theoretical backing for our work (Reviewers oma2, SEin), our proposed algorithms are effective and interpretable (Reviewers GNEv, RyBS), and that our work sufficiently novel and addresses a significant problem in fair ML (Reviewer ZFNz). The thoughtful feedback we received is even more appreciated in light of reviewers having several papers to handle in a short period of time. 

Below, we address the main points and questions raised by each reviewer and outline how we plan to update the paper accordingly; we will add the changes in the final version (both in the main text and appendix). Some common points shared by multiple reviewers are addressed below in this global response and are referred to accordingly in the responses to the individual reviewers.

We would also appreciate it if you could acknowledge that you read the response and, if your concerns are addressed, if you would kindly consider raising your review score. We also welcome any additional feedback or suggestions that could further strengthen our paper and would be glad to hear from the reviewers. 

Thank you!

---

**Q1. Reviewers RyBS and SEin mentioned extending our approach to related settings, such as (a) missing sensitive attributes and/or labels and (b) multiaccuracy and multicalibration notions of fairness.**

A1. We thank the reviewers for raising these great points.

(a) We first note that while missing input features is a challenge with regard to handling missing patterns, missing sensitive attributes and/or labels is a challenge with regard to evaluating (group) fairness metrics and incorporating fairness constraints into model training. Hence, we cannot directly apply existing work on missing sensitive attributes or labels to deal with our missing-input-feature problem setting, nor vice versa. However, one can easily combine our approach with existing work on missing sensitive attributes/labels to provide a complete story that can deal with any possible missing features.

As an example, Yan et al. (2020) use a preprocessing method involving clustering and resampling to improve class balance when sensitive attributes are unknown, prior to training a classifier such as logistic regression. If there are missing values in non-sensitive attribute input features, we can apply our method by e.g. adding missing indicators after the preprocessing scheme, right before classifier training.

The use of sensitive attributes when adapting non-linear fair classifiers (Section 5) is more complex as the sensitive attribute is explicitly used when drawing subsamples from the dataset; we make this limitation explicit in lines 355-358.

(b) We recognize and appreciate the rigor in the definitions of multiaccuracy and multicalibration, as well as the growing literature surrounding it. In practice, any of the three methods in Section 4 can be used prior to applying a multiaccuracy/multicalibration fairness intervention since they do not depend on specific knowledge of the group attribute (as mentioned above) and only require adding more features/parameters (sections 4.1 and 4.2) or training separate fairness interventions on different part of the dataset based on missing value pattern (section 4.3). Adapting the method in Section 5 for multiaccuracy and multicalibration is in contrast non-trivial, since it is tailored to the group fairness setting where group attributes are in a discrete set. Consequently, it cannot be directly extended to the setting where groups are denoted by a finite-complexity (yet potentially uncountable) set of functions against which the error should be uncorrelated (multiaccuracy) or calibrated (multicalibration). Nevertheless, the current experiments in the paper support our main conclusion: not preserving missingess information (such as in the impute-then-classify approach) can hinder the performance of fairness interventions.

References:

Yan, S., Kao, H. T., & Ferrara, E. (2020, October). Fair class balancing: Enhancing model fairness without observing sensitive attributes.

Meta-review: This study delves into the influence of missing data on the effectiveness of fairness interventions. The rationale behind this exploration stems from concerns that the widely employed "impute-then-classify" approach for handling missing values may hinder the process of ensuring fairness.
The research encompasses the following key aspects:
1. An investigation into how missing values impact algorithmic fairness across three primary modes of missing data (missing completely at random, missing at random, and missing not at random).
2. Development of a theorem that quantifies the performance gap between optimal solutions when using a generic imputation mechanism versus when fairness constraints, such as equalized odds, are applied (an information-theoretic result).
3. Methodological approaches for adapting fairness-intervention algorithms to accommodate missing data, applicable to both linear and non-linear scenarios. Companioning with empirical evaluations of the proposed methods, the authors demonstrate the practical insights into their efficacy.

The reviewers are unanimous in the paper’s contributions and the technical soundness. The authors are encouraged to incorporate the discussions during the rebuttal into their final version.
Decision: Accept (poster)