Fairness without Harm: An Influence-Guided Active Sampling Approach
Authors: Jinlong Pang
Jialu Wang
Zhaowei Zhu
Yuanshun Yao
Chen Qian
Yang Liu
Venue: NeurIPS 2024 poster (2024)
Keywords: Fairness; Sampling
Primary area: fairness
TL;DR: We develop a sampling algorithm such that the ML model jointly learned with training data and unlabeled influential data is fairer with high accuracy.

Abstract: The pursuit of fairness in machine learning (ML), ensuring that the models do not exhibit biases toward protected demographic groups, typically results in a compromise scenario. This compromise can be explained by a Pareto frontier where given certain resources (e.g., data), reducing the fairness violations often comes at the cost of lowering the model accuracy. 
In this work, we aim to train models that mitigate group fairness disparity without causing harm to model accuracy.
Intuitively, acquiring more data is a natural and promising approach to achieve this goal by reaching a better Pareto frontier of the fairness-accuracy tradeoff. The current data acquisition methods, such as fair active learning approaches, typically require annotating sensitive attributes. However, these sensitive attribute annotations should be protected due to privacy and safety concerns. In this paper, we propose a tractable active data sampling algorithm that does not rely on training group annotations, instead only requiring group annotations on a small validation set. Specifically, the algorithm first scores each new example by its influence on fairness and accuracy evaluated on the validation dataset, and then selects a certain number of examples for training. 
We theoretically analyze how acquiring more data can improve fairness without causing harm, and validate the possibility of our sampling approach in the context of risk disparity. We also provide the upper bound of generalization error and risk disparity as well as the corresponding connections.
Extensive experiments on real-world data demonstrate the effectiveness of our proposed algorithm. Our code is available at [github.com/UCSC-REAL/FairnessWithoutHarm](https://github.com/UCSC-REAL/FairnessWithoutHarm).

Fairness Without Harm: An Influence-Guided Active Sampling Approach
Jiinong Pang" UC Santa Cruz
Jialu Wang" UC Santa Cruz
Zhaowei Zhu" Docta.ai 2zw@docta.
Yuanshun Yao Meta GenAI
jpang140ucsc.edu
faldict@ucsc. edu
kevinyaodmeta.com com
Chen Qian UC Santa Cruz
Yang Liu UC Santa Cruz yangl Langliu@ucsc.edu
cqian128ucsc. edu
Abstract
The pursuit of fairness in machine learning (ML), ensuring that the models do not exhibit biases toward protected demographic groups, typically results in compro- mise scenario. This compromise can be explained by Pareto frontier where given certain resources (e.g., data), reducing the fairness violations often comes at the cost of lowering the model accuracy. In this work, we aim to train models that miti- gate group fairness disparity without causing harm model accuracy. Intuitively, acquiring more data is a natural and promising approach to achieve this goal by reaching better Pareto frontier the accurasy tradeoff. The current data acquisition methods, such as fair active learning approaches, typically require anno- tating sensitive attributes. However, these sensitive attribute annotations should be protected due to privacy and safety concerns. In this paper, we propose tractable active data sampling algorithm that does not rely on training group annotations, instead only requiring group annotations algorithm first scores each new example by its influence on fairness and accuracy evaluated the validation dataset, and then selects certain number of examples for training. We theoretically analyze how acquiring more data can improve faimess without causing harm, and validate the possibility of our sampling approach in the context of risk disparity. We also provide the upper bound of generalization error and risk disparity as well the corresponding connections. Extensive experiments on real-world data demonstrate the effectiveness of our proposed algorithm. Our code is available
small validation set. Specifically, the
Introduction
Machine Learning (ML) has dramatically impacted numerous optimization and decision-making pro- cesses across various domains, such as credit scoring [62] and demand forecasting [14. Algorithmic fairness embraces the principle, often enforced by law and regulations, that the decision-maker should not exhibit biases toward protected group membership [84], identified by characteristics such race, gender, or disability. However, the pursuit of fairness unavoidably results compromise scenario where reducing the fairness violations usually leads to degradation in accuracy, which has been observed and verified by numerous literature [52) 25 8T 69 83 Theoretically, the phenomenon
can be understood through Pareto frontier on the tradeoff between group fairness and accuracy
"quual contribution
Corresponning Author: Yang Liu
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

72 1O 74). That is, as illustrated in Figure given certain resources such as training data, when a model has reached a point on the Pareto frontier, without more data resources, it is impossible that one can improve faimess without worsening model accuracy.
One major source of unfairness and major cause of the fairess- accuracy tradeoff' is biased training data. If an unbiased and "fairer" dataset is available, we will be hopeful that unfairness can be alleviated without compromising accuracy. Furthermore, such "fairer" dataset would allow for obtaining a fair and accurate model through the standard empirical risk minimization (ERM) with cross-entropy (CE) loss. The above observation points to a promising way to improve faireess via actively acquiring more informative data, aiming to shift towards a better Pareto frontier of the faimess-accurace trade-off [6). However, existing approaches that seek more data, such as fair active learning A. typically require annotating sensitive attributes for training data. In practice, these sensitive attribute information such as race and gender, should be protected due to privacy regulations 35 5 66]. In the normal active learning scenario, collecting more data with sensitive attributes heightens privacy and safety risks due to the increased probability of leaking sensitive information.
Therefore, we ask the following question: When not disclosing more annotations of training sen- sitive altributes, how can we acquire more data to improve model faimeess without sacrificing accuracy?
0.35
0.30
original point
0.25
taimess velation
In this paper, propose tractable active data sampling algorithm in a training sensitive attributes-rree way, which solely requires sensi- tive attributes on a small validation set. Partic- ularly, the algorithm evaluates each example's 's influence on fairness and accuracy using the val- idation dataset for ranking and then selects certain number of examples to supplement the training set for training. We name our solution Fair Influential Sampling (FIS). The core chal- lenge is approximating the corresponding influ- ences of each new example without accessing its sensitive attributes. Technically, we evaluate the importance (influences) of each new example by comparing its gradient to that derived from the entire validation set. This comparison helps quantify the hypothesized change of group fair- ness disparity metric when adding this example to the training set. As a result, the requirement of training sensitive attributes can be relaxed, as gradient derivation serves role of fairness con- straints to measure the group fairness disparity. The main contributions of our work are summarized as follows.
0.20
shift
0.15
0.10
0.06
nic data
scarce
0.00
error
Figure 1: We compare the Pareto frontiers between the model trained with scarce data and that trained with rich data. Acquiring more data is capable of shifting the Pareto frontier toward lower disparity and lower error rates. In consequence, we can reach a new trade-off point that offers improved fairness and accuracy simultaneously. surpassing the original trade-off point.
We develop a tractable active data sampling algorithm (Algorithm I that does not rely on training sensitive attributes. The algorithm scores each new example based on the combined influences of prediction and fairness and then opts for a certain number of examples for training. [Section]] E] We theoretically analyze how acquiring more data can improve fairness without harm from a distribution shift perspective view, and validate the possibility of our sampling approach in the context of risk disparity. We also provide the upper bound of generalization error and risk disparity as well as the corresponding connections (Theorem 5. and Theorem 5.2). [Section
Empirical experiments on real-world datasets (CelebA, Adult, and COMPAS) substantiate claims, indicating the effectiveness and potential of our proposed algorithm in achieving fairness for ML classifiers. [Section
2 Related work
Fairness-accuracy tradeoff There are numerous works that have been successful at mitigating
fairness disparities [24] 32, 2 78 69] However, these works typically rely protected sensitive

---

attributes of training examples to measure the faimess disparities across groups. Moreover, faimess- accuracy tradeoff has been shown, meaning that enforcing fair constraints heavily degrades the model
performance [52 25 81 Notably, Chen et al. (20) characterized the change of the fairness violation when the data distribution is shifted. Except for training sensitive attributes, this paper does not work in the classical regime of the fairness-accuracy tradeoff. By properly collecting new data, we can improve both accuracy and fairness, which cannot be achieved by working on a static training dataset that naturally incurs such tradeoff. Besides, compared to prior works [52] [56], our method does not require additional assumptions about the classifier and the characteristics of the training/testing datasets (e.g., distribution shifts). Relevant work [42] utilizes the influence function to reweight the data examples but requires re-training. Our method focuses on soliciting additional samples from an external dataset while 22 reweights the existing and fixed training dataset.
Active learning The core idea of active learning is rank unlabeled instances by developing specific measures, including uncertainty [1 representativeness [22]. inconsistency [70], variance [34] and error [59]. related line of work 48
31 [6 concentrates on ranking unlabeled instances based on the influence function. Compared to these studies with a focus on prediction performance, our work poses a distinct challenge taking into account fairness violations. Our approach is more closely with the fair active learning approach [ However, this framework still relies on training sensitive attributes and then unavoidably encounters the tradeoff between fairness and accuracy.
71
Fair classifiers without demographics There are various studies achieve fairness without demographics. For example, Zhao et al. [82] explores the correlations between sensitive attributes and non-sensitive attributes to learn fair and accurate classifiers. Yan et al. (77) investigates the pre-processing method. Chai et al. [66] utilizes the soft
class imbalance problem with a KNN- labels from an overfitting teacher model to train a student model avoid using demographies. A line of research establishes theoretical connections between features and attributes to avoid using demographic information, employing methods like causal graphs (3), correlation shifts (58), and demographic shifts [30] In contrast, our approach refrains from making assumptions. Another line of work utilizes distributionally robust optimization (DRO) to reduce fairness disparity without 40, 67 64). Although these works evaluate the worst-case group performance in the context of fairness, their approaches differ as they do not strive to equalize the loss across groups. Besides, in these studies, accuracy and worst-case accuracy are used as fairness metrics to showcase the efficacy of the proposed algorithms. However, these fairness metrics restrictive and inconsistent with common definitions such as demographic parity (DP).
relying on training sensitive attributes 33 38 47
Fair classification The fairness-award learning algorithms, in general, can be categorized into pre- processing, in pn-processing and post-processing methods. Pre-processing methods typically reweigh or distort the data examples mitigate the identified biases 7 9 63
60 [5]
80 68). More
relevant to this work is the importance reweighring, which assigns weights to training examples Our algorithm bears similarity to specific case of importance reweighting,
37 36 particularly the 0-1 reweighting applied to newly added data. Other parallel studies utilize importance weighting to learn a complex generative model in a weakly supervised setting 23 21,, or to mitigate representation bias in training datasets [44]. Post-processing methods typically enforce fairness
23 21 37
on learned model through calibration 226 27 32], but these work might not achieve the best fiimess-accurace tradcoff [75 (55) In contrast, these post-processing works still require sensitive attributes during the inference phase. Recent work [19] develops a bias score classifier that operates independently of sensitive attributes; however, it is constrained to binary classifications.
3 Preliminaries
We consider a standard K-class classification task whose training (test) data distribution is P (Q). Let P == 1 represent the training dataset following distribution P. where |P| denotes the corresponding sample size. Each example, denoted 2,, (z... Vn) comprises two random variables: the feature vector x and the label y. The model trained on P is evaluated by the test dataset Q == (= |1 where (-)² denotes that the data follows distribution Q. each example = := (I", ,y/" 8)),, and the sensitive group 8% often refers to characteristics such as race, gender, etc. To align the fairness requirements on the test set Q with the model trained P.
Problem setup
3

---

popular way is to exploit the sensitive attributes 224 72 or their proxies [84] in P and use them to formulate Lagrangians during training. However, extending these approaches the active learning setting would require disclosing more sensitive attributes during sampling and training [4] which contradicts our goal. To avoid disclosing more sensitive attributes, we align the fairness requirements
by a small hold-out validation dataset Qu == { | that is independent and identically distributed (IID) with the test set Q. We defer more technical details to Section 4
Following the general active learning setting [4] we would acquire new examples from a large unlabeled dataset U := { )
31 Denote the solicited example by 2/x := (I'n V/), where Vn is the ground-truth label. Note that the protected sensitive attributes from datasets P and U remain undisclosed during sampling and training. this paper, we aim to incrementally update model that was initially trained on P' using standard ERM, by incorporating newly solicited data z/,, such that the model can improve fairness without worsening model accuracy. Thus, the core challenge is efficiently determining new examples that induce significantly better Pareto frontier. In the proceeding section we shall delve into how to acquire new data from unlabeled set.
[V] within a limited labeling budget B(< (U])
48
Fairness definition Note that this work focuses solely on active sampling build a fairer dataset, which is then used to train the model through standard ERM with Cross-Entropy (CE) loss. Without relying on additional assumptions about the model or training/testing dataset, an intuitive and natural approach is to analyze the expected risk. Therefore, we introduce the concept of risk disparity as an intermediate-term for theoretical analysis of fairness.
r
Definition 3.1 (Risk disparity 33 79 3)). Define Qs as the sub-distribution of Q corresponding to group k. Given the optimized model parameters w. trained on set P, risk disparity is defined as: Re, (w,)wPP))) Re(w?) P), where (R((w) == Ez-ol [z~o[[(w..) [[( denotes expected risk induced on target
distribution Q
Definition 3.I naturally quantifies the discrepancy in trained model's performance between specific group set Q& and the entire test set Q. That is, model can be deemed fair if it exhibits consistent performance for a group set Q2 as compared to the test dataset Q. In settings such as face or speech recognition, this fairness definition implies the necessity for all demographic groups to receive the same quality service [3). For completeness, we also include two well- kell- definitions of fairness:
Definition 3.2 (Demographic Parity (DP)). A classifier J adheres to demographic parity concerning the sensitive attribute if: (W, =]] E [=)ss)
Definition 3.3 (Equalized Odds (EDa
32 A classifier meets the equalized odds with respect to [[]f(w/))ly..
the sensitive attribute if: [E[((w w, .z) vl
Even though there may be a general incompatibility between risk disparity and popular group fairness metrics like DP and EOd, under the criteria of the proposed fairness notion, these definitions could be encouraged 61 33 More details and proof can be found in the Appendix B
Proposition 3.1. (Informal) Under appropriate conditions, the risk disparity can serve lower
bound for fairness disparities based on common fairness definitions. such as DP and EOd.
Remark 3.1 (Connections to other fairness definitions). Definition 3.1 targets group-level risk fairness, which has similar granularity other fairness notions such as accuracy parity [78).
device-level parity (3), small accuracy loss for groups 77 T0 50 33 and bounded group loss 3
Improving fairness without harm via data influential sampling
In this section, we first introduce how to measure the importance (influence) of each example on accuracy and fairness without using the corresponding sensitive attributes, respectively. Then, we propose an influence fefluence-guieed guided sampling algorithm that actively acquires new data based on the influences for further training.
4.1 Finding influential examples
To avoid using training sensitive attributes, our primary idea is to find newly acquired data that assists in creating "fairer" dataset, which allows for training fair and accurate model via standard ERM.

---

Initially, we explore whether newly acquired data enhances fairness by examining the training process, where the model is typically updated using gradient descent. The change of model parameters by performing one step gradient descent newly acquired data z' is
W++1 We 17 3w. ((w,,2))
(I)
where 7) refers the learning rate and {(-) is the training loss function. It should be noted that before we solicit the true labels of samples z', we first use proxy labels. In the following subsection 4.2, we
will present strategy for proxy labels. Training on z' affects the model's prediction on validation data 2 regarding both accuracy and fairness. If the updated model We+1 outperforms the previous one W, evaluated on the validation dataset in terms of fairness and accuracy, this acquired data s' helps to reduce the fairness disparity without worsening accuracy.
To separately measure the accuracy and fairness performance of the updated model the validation set, we introduce two types of loss functions: fairness loss ((w, 2n) and accuracy loss +R),
where validation data 2, (Ir D s2.) Note that these loss functions are developed for sampling, for training. Besides, training loss function E(-) can be reused as the accuracy loss function due to the same update target. One can identify training loss f(. z') and accuracy loss f(- = based on the input data used. Without loss of generality, we assume that E(.) and (0-) are differentiable w.r.t. w. Here, we do not restrict the generality of the fairness loss function; it can be any smoothed version of fairness metrics such as DP or EOd. Following this, we develop the influence of the accuracy and fairness components for finding the samples, respectively.
Influence of accuracy component When model parameters are updated from to We+1 by adding a new example 2', the influence of model's accuracy on one validation example zn is:
Inflaco i W., Ws41) == [(W(+1, 2,;) E(We: 27))-
For ease of notation, we use Inflace (#', 2n) to represent Inflaco z We, We41). ). By applying first- order Taylor expansion, we obtain the following closed-form statement:
Lemma 4.1. The accuracy influence of new example z' the validation dataset Qu is:
Inflaco = Σ Enelout Inflaco(2 = -1 Enelo. (0w, ([,,,( 2'), 2'); Ow, el ((we; =())
(2)
Intuitively, the more negative Inflaco(2') is, the more positive the model accuracy (performance) that example can provide.
Influence of fairness component When model parameters are updated from w, to Wr+1 by adding new example z', the influence of model's fainess one validation example 2 is:
Infitair (z', 2: We, We+1) = di W1+1, =.0) Φ6 Wr, =9)-
For simplicity, write Infleai (2', 22: We, w++1) as Infitair (2', 22)) Then, similarly, we have: Lemma 4.2. The fairness influence of new example 2' on the validation dataset Qu is:
Inflair(2")) ;= Σ ne Qul
Inflesid'' 2.)) -1 " (ww. l(w., 2'), Ow, o(w,,22))
(4)
Similar to the accuracy component, the greater the negativity of Inflrai(zz) is, the greater the positive impact that the example has on fairness.
Intuitions These two components evaluate the accuracy and fairness impact of each example by comparing the gradient originating from single data sample with the gradient derived from the entire validation set, respectively. This comparison helps quantify the potential advantage of including this specific example in training. For instance, if the gradient obtained from one example has similar direction to the gradient from the validation set, it indicates that incorporating this example contributes to enhancing the model's 's faimesss accuracy.
5

---

Algorithm Fair influential sampling (FIS)
1: Input:
training set P. unlabeled set U, validation set Qu, new acquired set S, 0, E [T] rounds, number of new selected examples in each round r, tolerance 6.
2: Warmup: Train a classifier / solely on P by minimizing the empirical risk Rg. Obtain model parameters 1 and validation accuracy (on Q+) VAL..
3: for in 21, T do
4: Guess proxy label 8' for new examples using Eq. (5)
5: Compute the influence of accuracy and fairness component using Eq. and Eq.
4
6:
Soriginal = (anf (2') Inflaco (8'== I 0, Inflair (3') Σ 0, EU}
7:
while |S,] r do
8:
Find top-(r- - (S+l) annotated examples z based on the lowest fairness influence and then
inquire about true labels y':
{2/=} inquiring (2)] Top-(r (r (So)i(Graa S Inflaco (2(1) S Inf (2 S 0}
9:
10:
11:
U Un:
S Soriginal Soriginal n,S,
12:
end while
13:
Continue train the model f the set S, via standard ERM. Obtain the updated model parameters W If the model's validation accuracy (on Q,) VAL, does not meet the desired threshold VALg, reject the updated model.
14:
end for
Output: models (w, VAL, VAL. -
Training sensitive attributes are not disclosed One can easily check that neither the influence of accuracy nor fairness components require the sensitive attributes of any example z', as the example a' only appears in the first-order gradient of the accuracy loss 0w, E(wr, z²). In the fairness component, calculating the 8w, Sw.6(w;,, W., 2?) only relies validation example 2 sensitive attributes. Here, also validate how accurate the first-order estimation of the influence is in comparison to the real influence [39], and find that the estimated influences for most of the examples are very close their actual influence values. We refer the readers to Appendix C.1 for more details.
Even without disclosing training sensitive attributes, the correlations between non-demographic features and demographic information may still lead to privacy leakage issues [2 To address this potential privacy concern, we provide further discussions and theoretical analysis using differential privacy in Appendix
4.2 Algorithm: fair influential sampling (FIS)
Following Lemma 4.1 and Lemma 4.2, we can efficiently select those examples with the most negative fairness influence and negative accuracy influence. This sampling method aids in reducing fairness disparities without worsening model accuracy.
Labeling Before presenting sampling algorithm, it is necessary to address the problem of not accessing the true labels new solicited examples. Lacking the label information for new examples poses challenge in determining the corresponding influence accuracy and fairness, fact that is substantiated by Lemma 4.1 and Lemma Intuitively, one can always recruit human annotators to get the ground-truth labels for those unlabeled examples. However, it impractical due the limited labeling budgets. To tackle this problem, another common approach is utilizing model that has been effectively trained on dataset P to produce proxy labels, which approximate the calculation of influences for examples from a substantial unlabeled dataset U. It's important to note that these proxy labels are exclusively used during the sampling phase. To maintain good model performance, we still need to inquire about the true labels of the selected data examples for subsequent training. Here, we propose to annotate the proxy labels with the model trained on the labeled set P. In particular, we introduce a strategy that employs lowest-influence labels for annotating label j/ given a::
j'' arg min
Inflacc (2', k)},
(5)
kE kE(L..-...k
Here, we denote g' := (x',8') for the proxy labels.

---

Proposed algorithm The full procedure is outlined in Algorithm [ Note that the tolerance is applied to monitor the performance drop in validation accuracy. In Line 2. we initiate the process by training a classifier f solely on dataset P. that is, performing a warm start. Subsequently, Tround sampling iterations are applied to acquire more examples to dataset P. Following the iterative fashion, FIS guesses labels using Eq. (5) in Line 4. Then, we calculate the scores for proxy examples based on the accuracy and fairness influence using Eq. (2) and Eq. (4) respectively. In Lines 6-12, we would opt for samples based on the influence scores, and inquire about the true labels of these examples. However, due to the gap between proxy labels j/' and true label y, the accuracy and fairness influences of the top-r samples based on inquired true labels 2' may not necessarily satisfy the same conditions (Inflaco( (2') I 0, Inflair(23) < 0). Therefore, we use a while loop to iteratively select the top-(r |S.l) examples for labeling until we obtain samples whose fairesss influences based on true labels meet the conditions. Subsequently, in Line 11, we update sets U and Soriginal to prevent duplicate sampling. In Line 13, we would continue training using new examples with true inquired labels from set Sy. We save the model parameters at each round as checkpoints w.. To avoid potential accuracy drops incurred by excessively large random perturbations, models for output whose validation accuracy exceeds the initial validation accuracy VALo. Although we propose specific strategy for guessing labels, our algorithm is flexible and compatible with other labeling methods. A comparative analysis of computational costs is detailed in Appendix
exclusively choose and offer
How more data improves fairness without harm?
In general, acquiring new data to supplement the original training dataset would potentially raise the distribution shift problem, affecting both accuracy and fairesss. In this section, from a distribution shift perspective view, we first present generalization error bound (accuracy side, Theorem [5.1 and risk disparity bound (fairees side, Theorem 5.2). The theoretical results jointly provide a high-level key insight that controlling the negative impact of distribution shift on generalization error, which refers to the model accuracy, could allow for improving fairness without harm. This theoretical insight validates the possibility of our sampling approach.
Without loss of generality, we discretize the whole distribution space and suppose that the train/test distributions are both drawn from series of component distributions {T .T) (28) Then, the empirical risk R((w) calculated over a training set can be reformulated by splitting samples based on the component distributions:
Σ'_ ( i) E. [[(w,2)]
(p(w) == E.eple(W, 2)]
where pl (P = i) represents the frequencies of examples in P drawn from component distribution TT Then, we can define the measure of probability distance between two sets or distributions as dist(A, B) Σ/= (T) = (5) x i)). To reflect the implicit unfairness the models,
we introduce two basic assumptions in convergence analysis 43
Assumption 5.1 (L-Lipschitz Continuous). There exists constant L O, for any v, w E Rd Rr((v) < (r(w) + (VRr(w).v w) 1/2 ||v w w|
Assumption 5.2 (Bounded Gradient on Random Sample). The stochastic grudients on any sample are uniformly bounded, i.e., [ =)] < G2, and training epoch l. E (1,...,T) T.
Analogous to Assumption 5.2. we further make a mild assumption to bound the loss over the component distributions ग. according to the corresponding model, that is, Eswn, [e(w", (ww,,2) 2)] < Gp, Vi I, where Gp is bounding constant. For completeness, we first analyze the upper bound of generalization error, specifically from the standpoint of distribution shifts. Omitted proof can be found in Appendix D
Theorem 5.1 (Generalization error bound). Let dist(P. Q), Gp be defined therein. With probability at least 8 with 8 (0, 1), the generalization error bound of the model trained on dataset P. is
1og(4/8) P|
Re(w²) Gp (o-ddi((P,,2)
Rr(ww")
distribution shift
Note that the generalization error bound is predominantly impacted by the shift in distribution, especially when we consider overfitting model, i.c., the empirical risk Re(wP) - 0.
7

---

Theorem 5.2 (Upper bound of risk disparity). Suppose R follows Assumption 5.1
Q). Let disr(P, P.
Gp, dist(Pis 2x) and dist( P) be defined therein. The initial learning rate no satisfies no < V2TT. where T is the number of training epochs. Given model w" and w trained exclusively on group k's data Pk. with probability at least - - with E 1), then the upper bound of risk disparity is
- -Re(w") S ddsst(PPp 2x) + Gp dis Q) + CT dist(Pk: P) +T (6)
distribution shift
group gap
where =
log(4/07 P/P
+
log(4/8)
P/P
+ Wh. Note that Egoa, E .2)1 S Gk. w = Rp(w²)
(o(w)) and we R.p. (w*) - Ro - (wQ:). w and wa can regarded as constants because Rp(w") and R., (w*) correspond to the empirical risks, ()( and R2 (w represent the ideal minimal empirical risk of model w trained on distribution Q and Qu: respectively.
Interpretations of Theorem 5.2 Eq. 6 illustrates several aspects that induce unfaimess. (1) Group biased data. For group-level fairness, the more balanced the data is, the smaller the risk disparity would be: (2) distribution shift. For source/target distribution, the closer the distributions are, the smaller the performance gap would be; (3) Data size. For training data size, a larger data size (potentially eliminating data bias across groups) would lead a smaller performance gap.
Main observation Theorem 5.1 underscores how the generalization error is impacted by distribution shifts. Theorem implies that the risk disparity is essentially influenced by the distribution shift and the inherent group gap term. In practice, approaches that mitigate the group gap, such as imposing fairness regularizers, acquiring new data, reweight the training data samples [37], will inevitably incur additional distribution shifts between the training and test data. The incurred distribution shift further leads performance drop due to the generalization error in Theorem [5.] Nonetheless, one theoretical insight is that if one can control the negative impacts of potential distribution shifts through generalization error while implementing faimess-enhaneing strategies, it is possible achieve the goal of improving fairness without causing harm. This high-level insight supports the effectiveness of our proposed sampling approach, in which we acquire new data reduce the group gap through fairness components while preventing the potential adverse impacts of distribution shifts using the accuracy influence component.
6 Empirical results
In this section, we empirically demonstrate the disparate impact across groups and present the effectiveness of the proposed Fair Influential Sampling method to mitigate the disparity.
6.1 Experimental setup
We evaluate the performance of our algorithm three real-world datasets across three different modalities: CelebA [49), UCI Adult [ and Compas [6). We implement the faimess loss Φ6.) based on three common group fairness metrics: difference of demographic parity (DP), difference of equality of opportunity (EOp), and difference of equal odds (EOd). We compare our method with five baselines: 1) Base (ERM): directly train the model on the training dataset P: 2) Random: train the model on dataset P and randomly sampled data from U with inquired true labels; 3) BALD [2] active sampling according to the mutual information; 4) ISAL [88 selects unlabeled examples based on the calculated influence in an active learning setting. We apply model predictions as pseudo-labels; 5) Just Train Twice (JTT) [ reweighting those misclassified examples for re-training Here, we examine a weight of 20 for misclassified examples, marked as JTT-20. Recall that we present the average result of the classifier w, outputs from Algorithm [ The general term "fairness violation" is utilized to quantify the absolute differences based on fairness metrics, such as DP and EOd. More are provided Appendix E.
details on datasets and
6.2 Main results
Note that all the experimental results presented subsequently are from three independent trials, each conducted with distinct random seeds. We present the primary results tuples in the form
8

---

(RsM
Random
BALD
ISAL
JTT-20
CelebA Smiling (DP)
CelebA Smiling (EOp)
CelebA Attractive
CelebA Artractive (EOp)
faimess violation
0.20
0.00
0.4
0.13
0.23
n6
0.1
6.10
0.04
0.05
0.1
0.30
0.05
0.10
0.75
0.80
3Rts
0.7
0.11
0.9
0.00
085
0.50
0.60
0.05
0.70
CelebA Young (DP)
Young (EOp)
CelebA Nose (DP)
CelebA Big Nose (EOp)
f5 bimege violation
0:25
0.20
0.100
0.13
0.075
0.15
0.050
0.10
0.76
0.72
0.80
0.72
0.74
0.76
0.80
Adult Income (DP)
Adult Income (EOp)
Compas Recidivism (DP)
Compas Reclalvism (EOp)
0,200
fairness vielation
0.30
0:35
0.30
0.25-
0.150
0:30
0.20
0.100
0:25
0.075
0.6
10
test accuracy
test accuracy
test accuracy
test accuracy
Figure 2: Main results CelebA, Adult and Compas datasets. The axis shows fairness_vion violation; X axis denotes
CelebA: Four binary targets: Smiling,
Attractive, Young, and Big_ Nose; Sensitive attribute: gender. Adult: Binary target: Income; Sensitive attribute: Age. Compas: Binary target: Recidivism; Sensitive attribute: Race. We select two fairness metries DP and Eop to measure fairness violations for each setting. The vertical dotted line at the random baseline accuracy helps easily identify which results achieve fairness without sacrificing performance (accuracy).
ceast_accracy, fairness violation) to facilitate comparison of the fairness-accural tradeoff. Due to space limits, we provide a full version of the experimental results (tables) in Appendix E.2
Results image datasets Initially, we train a vision transformer using patch size of (8, 8) on the CelebA face attribute dataset 49]. We select four binary classification targets, including Smi ling, Attractive, Young. and Big Nose. The sensitive attribute is gender. 2% of the labeled data is allocated for training, while the remaining 98% is reserved for sampling purposes. Then, the test dataset is split into independent portions: test data randomly designated as the hold-out validation set. For ease computation, only the last two layers of the model are used to calculate the influence of accuracy and fairness components. For Figure 2] one main observation that FIS outperforms baselines with a significant margin on three fairness metries while maintaining the same accuracy level. This improvement, as indicated in Theorem 5.2 can be attributed to FIS assigning priority to new examples based on the fairness influence, then avoiding accuracy reduction via their accuracy influence.
test set and validation set. with 10% of the
Results on tabular datasets Next, we work with multi-layer perceptron (MLP) with two layers trained on the Adult and Compas dataset (6), respectively. We select age the sensitive attribute for the Adult dataset and race for the Compas dataset. For two datasets, we resample the data to balance the class and group membership [17]. The whole dataset is split into training and sets at a 4:1 ratio. Then, we randomly re- re-select 20% of the training set for initial training and the remaining 80% for sampling. Also, 20% examples of the test set are selected
form validation set. The MLP model is two-layer ReLU network with hidden size of 64. We utilize the whole model parameters to compute the influence of accuracy and fairness for examples. Figure T main results of the Adult and Compas datasets. On the Adult dataset, we observe that our sampling method achieves the lowest violation for equality of opportunity and has a comparable performance for the DP metric. Besides, algorithm achieves much better accuracy -firnesss trade-off than

---

other baselines on the Compas dataset. JTT-20 achieves a lower faimess violation with the price of a significant accuracy drop compared other baselines.
6.3 Ablation study
What is the impact of label budgets? Here, we examine how the varying label budgets affect the trade-off' between accuracy and fairness. For ease of comparison, we adhere a consistent label budget per round to illustrate their respective impacts. As shown in Figure 3 our method consistently preserves a lower fairness violation than the BALD and ISAL baselines with similar test accuracy. While we observe that the JTT-20 algorithm can achieve near-zero faimess violation under a limited budget on the CelebA dataset, we argue that the model accuracy rather uninformative (about 50%). More empirical results can be found in Appendix E.3
How does the validation set size affect the performance? We further explore the impact of adjusting the validation set size on our algorithm's 's performance. We present the test accuracy and fairness violations across different validation set sizes on the CelebA dataset. Note that the default validation set size is set to 1 1% of the whole dataset size. In particular, the minimum scale of the validation set size is set to 1/5x (nearly 400 CelebA images). The results in Figure indicate that our algorithm still retains the test accuracy and fairness violation when we vary the validation set size. Additional results conducted on Adult and Compas datasets are provided in Appendix E.4
1.0
CelebA
ColebA
acturary
0.8
CelehA Smiling
6.6
(Test_ace", DPJ)
(Testacet. BOpl)
(Testacc" BOUL)
0.1
(0.848 0.084)
(0,876, 0,031)
(0.864, 0.030)
SAL
M/x
(0.872 0.105)
(0.891, 0.042)
(0.880, 0.028)
1/xx
(0.872, 0.117)
(0.863, 0.057)
(0.886, 0.028)
0.0
0
10
20
40 label budget
30
50
60
70
0.0
0
10
20
30
50
60
label budget
Figure 3: Left: The impact of label budgets on the test accuracy & DP gap in the CelebA dataset. Right: The impact of the validation set size on (test_ (test_accuracyy, siineess_vollaioon results.
7 Conclusions and limitations
In this work, we are interested in facilitating ML models that mitigate group fairness disparity without harming model accuracy. To achieve this, different from current active sampling methods, we propose a tractable fair influential sampling method FIS, which avoids the need for training group annotations during the sampling training phase, thereby preventing the potential exposure of sensitive information. In particular, this algorithm acquires data samples from a large dataset for training based on the influence of fairness and accuracy evaluated the auxiliary validation dataset. Empirical experiments on real-world data validate the efficacy of our proposed method.
Nonetheless, we recognize that our method has limitations. Although the proposed sampling algorithm does not require sensitive attribute information from the massive data, it relies on a clean and informative validation set that contains the sensitive attributes of data examples. We consider this reasonable requirement in practice, given the relatively modest size of the validation set. Besides, one potential concern is that the sampling strategy may become inefficient when the collected validation set is noisy. However, this practical issue can be heavily alleviated by using loss correction methods
[54 84 moise-tolerant faimess loss functions to rectify the error terms [53 73 29) In future work,
we aim to address this limitation by developing more robust sampling strategies that can perform effectively even with noisy validation sets.
Acknowledgment
This work is partially supported by the National Science Foundation (NSF) under grants IIS- 2143895, IIS- 2040800, ISS-241889, and CCF-2023495. Additionally, Pang and Qian were partially supported by NSF Grants 2322919, 2420632, 2426031, and 2114113.
10

---

Broader Impact
This paper presents work whose goal is advance the field of fairness in machine learning. There are many potential societal consequences of our work. While the proposed algorithm does intend infer sensitive attributes of data examples that may be protected by privacy regulations, does not necessitate direct access to such sensitive information. On the other hand, our work can serve as an effective approach leading mitigating the disparity with a limited annotation budget. We have thoroughly examined the potential ethical implications of our work and, based on our assessment, do not identify any issues that we deem necessary emphasize here specifically.
References
[1] Pareto effiency and production possibility frontier. Prooduetiioni222/000spsssssttt.. frontiier
org/viki/
[2] Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. reductions approach to fair classification. In Proceedings of the 35th International Conference on Machine Learning (ICMI. 18), 2018.
[3] Alckh Agarwal, Miroslav Dudík, and Zhiwei Steven Wu. Fair regression: Quantitative defini- tions and reduction-basee algorithms. In International Conference on Machine Learning, pages 120-129. PMLR, 2019.
[4] Hadis Anahideh, Abolfazl Asudeh, and Saravanan Thirumuruganathan. Fair active learning. Expert Systems with Applications, 199: 1 16981, 2022.
[5] McKane Andrus, Elena Spitzer, Jeffrey Brown, and Alice Xiang. What we can't measure, we can't 't understand: Challenges to demographic data procurement in the pursuit of fairness. In Proceedings of the 2021 ACM conference on fairness, accountability, and transparency, pages 249 249-260, 2021.
[6] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. 2016.
[7] Abolfazl Asudeh, Zhongjun Jin, and HV Jagadish. Assessing and remedying coverage for given dataset. In 2019 IEEE 35th International Conference on Data Engineering (ICDE), pages 354-565. IEEE, 2019.
[8] Arthur Asuncion and David Newman. Uci machine learning repository, 2007.
[9] Fabio Azzalini, Chiara Criscuolo, and Letizia Tanca. Fair-db: Functional dependencies to discover data bias. In EDBT/ICDT Workshops, 2021.
[10] Ananth Balashankar, Alyssa Lees, Chris Welty, and Lakshminarayanan Subramanian. What fair? exploring pareto-efficiency for fairness constrained classifiers. arXiv preprint arXiv: 2019.
[11] Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and machine learning: Limita- tions and opportumities. MIT Press, 2023.
[12] Frédéric Branchaud-Charron, Parmida Atighehchian, Pau Rodríguez. Grace Abuhamad, and Alexandre Lacoste. Can active learning preemptively mitigate faimesss issues? arXiv preprint vrXiv:2104.06879 2021.
[13] Joy Buolamwini and Timnit Gebru. Gender shades: commercial gender classification. In Conference on fairness, accountability and transparency, pages 77-91. PMLR, 2018.
Intersectional accuracy disparities in
[14] Réal André Carbonneau, Kevin Laframboise, and Rustam M. Vahidov. Application of machine learning techniques for supply chain demand forecasting. Eur. Oper. Res., 184: 140-1154, 2008.
[15] I. Elisa Celis, Vijay Keswani, and Nisheeth Vishnoi. Data preprocessing to mitigate bias: A maximum entropy based approach. International conference on machine learning, pages 1349-1359 1359. PMLR, 2020.

---

[16] Junyi Chai, Taeuk Jang, and Xiaoqian Wang. Fairness without demographics through knowledge distillation. Advances Neural Information Processing Systems, 35:19122-19164, 2022.
[17] Nitesh V Chawla, Kevin W Bowyer, Lawrence O Hall, and W Philip Kegelmeyer. Smote: synthetic minority over-sampling technique. Journal of artificial intelligence research, 16:321- 357, 2002.
[18] Irene Chen, Fredrik D Johansson, and David Sontag. Why is my classifier discriminatory? Advances in neural information processing systems, 31, 2018.
[19] Wenlong Chen, Yegor Klochkov, and Yang Liu. Post-hoe bias scoring is optimal for fair classification. arXiv preprint arXiv:2310.05723, 2023.
[20] Yatong Chen, Reilly Raab, Jialu Wang, and Yang Liu. Faimess transferability subject to bounded distribution shift. Advances in Neural Information Processing Systems, 35:1 1261-11662201 11278, 2022.
[21] Kristy Choi, Aditya Grover, Trisha Singh, Rui Shu, and Stefano Ermon. Fair generative modeling via weak supervision. In International Conference Machine Learning, pages 1887-1898. PMLR, 2020.
[22] Sanjoy Dasgupta and Daniel Hsu. Hierarchical sampling for active learning. In Proceedings of the 25th international conference Machine learning, pages 208-215 200--11,,20 2008.
[23] Maurice Diesendruck, Ethan R Elenberg, Rajat Sen, Guy W Cole, Sanjay Shakkottai, and Sinead A Williamson. Importance weighted generative networks. In Machine Learning and Knowledge Discovery in Dutabases: European Conference, ECML PKDD 2019, Würzburg, Germany, September 16-20, 2019, Proceedings, Purt II, pages 249-265. Springer, 2020.
[24] Michele Donini, Luca Oneto, Shai Ben-David, John S -aylo,, and Massimiliano Pon-
til. Empirical risk minimization under fairness constraints. Advances in neural information processing systems, 31, 2018.
[25] Sanghamitra Dutta, Dennis Wei, Hazar Yucksel, Pin-Yu Yu Chen, Sijia Liu, and Kush Varshney. Is there trade-off between fairness and accuracy? perspective using mismatched hypothesis testing. In International conference on machine learning, pages 2803-281 2813. PMLR, 2020.
[26] Michael Feldman. Computational fairness: Preventing leareed discrimination. PhD thesis, 2015.
[27] Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkata- subramanian. Certifying and removing disparate impact. In proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 259-268, 2015.
[28] Vitaly Feldman. Does learning require memorization? short tale about a long tail. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 954-959, 2020.
[29] Lei Feng. Senlin Shu, Zhuoyi Lin, Fengmao Lv, Li Li, and Bo An. Can cross entropy loss be robust to label noise? In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pages 2206-2212, 2021.
[30] Stephen Giguere, Blossom Metevier, Yuriy Brun, Bruno Castro da Silva, Philip S Thomas, and Scott Niekum. Fairness guarantees under demographic shift. In Proceedings of the 10th International Conference on Learning Representations (ICLR), 2022.
[31] Zayd Hammoudeh and Daniel Lowd. Training data influence analysis and estimation: A survey. arXiv preprint 1rXiv:2212.04611 2022.
[32] Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
[33] Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographies in repeated loss minimization. In International Conference on Machine Learning, pages 1938-1938. PMLR, 2018.
12

---

[34] Steven CH Hoi, Rong Jin, and Michael R Lyu. Large-scale text categorization by batch mode active learning. In Proceedings of the 15th international conference on World Wide Web, pages 633-642, 2006.
[35] Kenneth Holstein, Jennifer Wortman Vaughan, Hal Daumé III, Miro Dudik, and Hanna Wallach. Improving fairness in machine learning systems: What do industry practitioners need? In Proceedings of the 2019 CHI conference on human factors in computing systems, pages 1-16, 2019.
[36] Heinrich Jiang and Ofir Nachum. Identifying and correcting label bias in machine learning. In International Conference on Artificial Intelligence and Statistics, pages 702-712. PMLR, 2020.
[37] Faisal Kamiran and Toon Calders. Data preprocessing techniques for classification without discrimination. Knowledge and information systems, 33(1):1-33, 2012.
[38] Polina Kirichenko, Pavel Izmailov, and Andrew Gordon Wilson. Last layer re- re-training is sufficient for robustness to spurious correlations. arXiv preprint arXiv:2204. 029377, 2022.
[39] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pages 1895-1894. PMLR, 2017.
[40] Preethi Lahoti, Alex Beutel, Jilin Chen, Kang Lee, Flavien Prost, Nithum Thain, Xuezhi Wang, and Ed Chi. Faimess without demographics through adversarially reweighted learning. Advances in neural information processing systems, 33:728-744 740, 2020.
[41] David D Lewis and Jason Catlett. Heterogeneous uncertainty sampling for supervised learning. In Machine learning proceedings 1994, pages 148 156.. Elsevier, 1994.
[42] Peizhao Li and Hongfu Liu. Achieving fairness at no utility cost via data reweighing with influence. In International Conference on Machine Learning, pages 12917-12930, PMLR, 2022.
[43] Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. In International Conference on Learning Representations, 2019.
[44] Yi Li and Nuno Vasconcelos. Repair: Removing representation bias by dataset resampling. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9572-9581,20 2019.
[45] Michael Lindenbaum. Shaul Markovitch, and Dmitry Rusakov. Selective sampling for nearest neighbor classifiers. Machine learming, 54:125-152, 2004.
[46] Richard G Lipsey. An introduction positive economics-4. 1975.
[47] Evan Liu, Behzad Haghgoo, Annie Chen, Aditi Raghunathan, Pang Wei Koh, Shiori Sagawa, Percy Liang, and Chelsea Finn. Just train twice: Improving group robustness without training group information. In International Conference on Machine Learning, pages 17792. PMLR, 2021.
[48] Zhuoming Liu, Hao Ding, Huaping Zhong, Weijia Li, Jifeng Dai, and Conghui He. Influence selection for active learning. In Proceedings of the IEFF/CVF International Conference on Computer Vision, pages 9274-9283, 2021.
[49] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of the IEEE international conference on computer vision, pages 3730-3738, 2015.
[50] Natalia Martinez, Martin Bertran, and Guillermo Sapiro. Fairness with minimal harm: A pareto-optimal approach for healthcare. arXiv preprint 1911
111199110000 1.06955,555 2019.
[51] Natalia Martinez, Martin Bertran, and Guillermo Sapiro. Minimax pareto fairness: A multi objective perspective. In International conference on machine learning, pages 6755-6764. PMLR, 2020.
13

---

[52] Aditya Krishna Menon and Robert C Williamson. The cost of fairness in binary classification.
In Conference on Fairness, accountability and transparency, pages 107-118. PMLR, 2018.
[53] Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. In Advances in neural information processing systems, pages 1 1196-1204, 2013.
[54] Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu. Making deep neural networks robust to label noise: loss correction approach. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1944-1952 2017.
[55] Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. On fairness and calibration. In Advances in Neural Information Processing Systems, pages 5680-5689, 2017.
[56] Flavien Prost, Hai Qian, Qiuwen Chen, Ed Chi, Jilin Chen, and Alex Beutel. Toward a better trade-off between performance and faimess with dernel-based distribution matching. arXiv preprint arXiv: 19X.v:9910.11777 2019.
[57] Maan Qraitem, Kate Saenko, and Bryan A Plummer. Bias mimicking: A simple sampling approach for bias mitigation. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2031 20311-20320, 2023.
[58] Yuji Roh, Kangwook Lee, Steven Euijong Whang, and Changho Suh. Improving fair training under correlation shifts. arXiv preprint arXiv: 02322, 2023.
[59] Nicholas Roy and Andrew McCallum. Toward optimal active learning through monte carlo estimation of error reduction. ICML, Williamstown, 2:441 1:441-448, 2001.
[60] Shubham Sharma, Yunfeng Zhang, Jesús M Ríos Aliaga, Djallel Bouneffouf, Vinod Muthusamy, and Kush R Varshney. Data augmentation for discrimination prevention and bias disambiguation. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pages 358 03-36,4, 2020.
[61] Changjian Shui, Gezheng Xu, Qi Chen, Jiaqi Li, Charles X Ling, Tal Arbel, Boyu Wang, and Christian Gagné. On learning fairness and accuracy on multiple subgroups. Advances in Neural 2022.
Information Processing Systems,
[62] Nacem Siddiqi. Credit risk scorecards: developing and implementing intelligent credit scoring, volume 3. John Wiley & Sons, 2012.
[63] Harvineet Singh, Rina Singh, Vishwali Mhasawade, and Rumi Chunara. Fairness violations and mitigation under covariate shift. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pages 3-13, 2021.
[64] Nimit Sohoni, Jared Dunnmon, Geoffrey Angus, Albert Gu, and Christopher Ré. No subclass left behind: Fine-grained robustness in coarse-grained classification problems. Advances in Neural Information Processing Systems, 11119993919352 2020.
[65] Ki Hyun Tae and Steven Fuijong Whang. Slice tuner: A selective data acquisition framework for accurate and fair machine learning models. In Proceedings of the 2021 International Conference on Management of Data, pages 1771-1783, 2021.
[66] Michael Veale and Reuben Binns. Fairer machine learning in the real world: Mitigating discrimination without collecting sensitive data. Big Data & Soociety, 422:20539517117733333 2017.
[67] Akshaj Kumar Veldanda, Ivan Brugere. Sanghamitra Dutta, Alan Mishler, and Siddharth Garg. Hyper-parameter tuning for fair classification without sensitive attribute access. arXiv preprint arXiv:2302.003385 2023.
[68] Jialu Wang, Yang Liu, and Caleb Levy. Fair classification with group-dependent label noise. In Proceedings of the 2021 ACM Conference on Fairness, Accountability and Transparency, FAceT '21, page 526-536, New York, NY, USA, 2021. Association for Computing Machinery.
14

---

[69] Jialu Wang, Xin Eric Wang, and Yang Liu. Understanding instance-level impact of fairesss constraints, In International Conference on Machine Learning pages 23114-23130, PMLR. 2022.
[70] Ran Wang, Sam Kwong, and Degang Chen. Inconsistency-based active learning for support vector machines. Pattern Recognition, 45(10):3751-37777, 2012.
[71] Tianyang Wang, Xingjian Li, Pengkun Yang, Guosheng Hu, Xiangrui Zeng. Siyu Huang. Cheng-Zhong Xu, and Min Xu. Boosting active learning via improving test performance. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8566-8574, 2022.
[72] Yuyan Wang, Xuezhi Wang, Alex Beutel, Flavien Prost, Jilin Chen, and Ed H Chi. Understand- ing and improving fairness- accuracy trade-offs in multi-task learning. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1748 -1577, 2021.
[73] Hongxin Wei, Lei Feng, Xiangyu Chen, and Bo An. Combating noisy labels by agreement: A joint training method with co-regularization. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13726-13735, 2020.
[74] Susan Wei and Mare Niethammer. The fairness pareto front. Statistical Analysis and Data Mining: The ASA Data Science Journal, 15(3):287-302, 2022.
[75] Blake Woodworth, Suriya Gunasekar, Mesrob Ohannessian, and Nathan Srebro. Learning non-discriminatory predictors. In Conference on Learning Theory, pages 1920-1953. PMLR, 2017.
[76] Yichen Xie, Han Lu, Junchi Yan, Xiaokang Yang. Masayoshi Tomizuka, and Wei Zhan. Active finetuning: Exploiting annotation budget the cetraaninngffnetuniiee paradigm. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 23715-23724, 2023.
[77] Shen Yan, Hsien-te Kao, and Emilio Ferrara. Fair class balancing: Enhancing model fairness without observing sensitive attributes. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 1715-1724, 2020.
[78] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi, Faimess constraints: Mechanisms for fair classification. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
[79] Muhammad Bilal Zafar, Isabel Valera, Manuel Monnez-Rodriguez, and Krishna P Gummadi. Fairness constraints: A flexible approach for fair classification. The Journal of Machine Learning Research, 20(1):2737-2776 2019.
[80] Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representa- tions. In International conference on machine learning, pages 325-333, PMLR, 2013.
[81] Han Zhao and Geoffrey J Gordon. Inherent tradeoffs in learning fair representations. The Journal of Machine Learning Research, (3(1):2527-2552 2022.
[82] Tianxiang Zhao, Enyan Dai, Kai Shu, and Suhang Wang. Towards fair classifiers without sensitive attributes: Exploring biases in related features. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pages 1433-1442, 2022.
[83] Zhaowei Zhu, Tianyi Luo, and Yang Liu. The rich get richer: Disparate impact of semi- supervised learning. arXiv preprint arXiv:21 10.06282, 2021.
[84] Zhaowei Zhu, Yuanshun Yao, Jiankai Sun, Hang Li, and Yang Liu. Weak proxies are sufficient and preferable for fairnsss with missing sensitive attributes. In International Conference on Machine Learning, pages 43258 43288. PMLR, 2023.
15

---

Appendix
The Appendix is organized follows.
Section A
provides more details of the related work.
Section explores the relationship between our proposed faimess notion risk disparity and common fairness metrics, such DP and EOd. In particular, we provide the full proof for Proposition 3.1 provides detailed analysis of the FIS algorithm including 1) evaluating first-order influence estimations against real influence, 2) a comparative analysis of computational costs, and 3) the exploration of the labeling strategies.
Section C
Section D
presents the full proofs for the Lemmas and Theorems shown in Section 4 and Section S
Section presents detailed descriptions of all datasets, corresponding parameter settings, and full version of the experimental results. In particular, to demonstrate FIS's advantage at the same levels of information, we introduce a new baseline called Random+Val.
Section F discusses the privacy concern potentially caused by the correlations between non- demographic and demographic features.
A More details of related work
Active learning The core idea of active learning is to rank unlabeled instances by developing specific significant measures, including uncertainty [4T 45 representativeness [22]. inconsistency [70], variance [34], and error [59] Each of these measures has its criterion to determine the importance of instances for enhancing classifier performance. For example, uncertainty considers the most important unlabeled instance to be the nearest one to the current classification boundary. A related line of work [48, [71, 31, (66 concentrates on ranking unlabeled instances based on the influence function. Compared to these studies with focus on prediction accuracy, our work poses distinet challenge taking into account fairness violations. We note that adopting a particular sampling strategy can lead to distribution shifts between the training and testing data. What's worse, even though fairness is satisfied within the training dataset, the model may still exhibit unfair treatments on the test dataset due to the distribution shift. Therefore, it becomes imperative for the sampling approach to also account for its potential impacts on fairness.
Pareto optimality In the field of faimess in machine learning, Pareto optimality indicates the theoretical frontier of fairness accuracy tradeoff, meaning that fairness can not be improved without worsening model accuracy. Existing methods primarily focus seeking the Pareto frontier of faimess accuracy tradeoff for the neural network classifier, instead of reaching a better one. For example, [10 first analyzes the Pareto optimality for classifiers within the context of fairness constraints. [72) explores the multi-dimensional Pareto frontiers of the fairness-accuracy tradeoff in the multi-task setting. [5]] 50) target to obtain Pareto efficient classifier to reduce worst-case group risks by formulating group fairness as a multiplc-ojeectvve optimization problem, where each group risk is an objective function.
Fair classification The fairness- aware learning algorithms, in general, can be categorized into pre- processing, in- processing. and post-processing methods. Pre- processcssi methods typically reweigh
distort the data examples to mitigate the identified biases [ 63] 60, [5]
17 80 [8]. More relevant
us is the importance reweighting, which assigns different weights to different training examples to
ensure fairness across groups [37 36 23 21 57 44.. Our proposed algorithm bears similarity to specific case of importance reweighting. partieularly the 0-1 reweighting applied to newly added data. The main advantage of our work, however, lies in its ability to operate without needing access the sensitive attributes of either the new or training data. Other parallel studies utilize importance weighting to learn a complex fair generative model in a weakly supervised setting [23] 21), or to Post-processing methods typically enforce
mitigate representation bias in training datasets 44
Although this approach is likely to decrease the disparity of the classifier, by decoupling the training from the fairness enforcement, this procedure may not lead to the best trade-off between fairness and accuracy [75] 55]. In contrast, our work can achieve a better trade-off between fairness and accuracy, because we reduce the fairness disparity by mitigating the adverse effects of distribution shifts on generalization error. Additionally, these post-processing techniques necessitate access to the sensitive attribute during the inference phase, which is often not available in many real-word world scenarios.
fairness on a learned model through calibration 26
27
32
16

---

B Understanding risk disparity through common fairness metrics
Here, we provide a brief proof illustrate Proposition 3.1 that is, the relationship between risk parity and common fairness metrics, such as DP and EOd. For completeness, here we provide more detailed version of Proposition 3.1 as well its proof.
Proposition 3.1] Consider a binary classification scenario involving two demographic groups S SE {kt k.. When two groups are balanced, i.e., P = 1, where y denotes the predicted label, risk disparity
lower bound for fairness disparities based EOd. Similarly, if the group sufficiency ratio can be calibrated by i.e., PP(Y y|S k, Y y) TP(Y y K, ".Y y) R where R is calibration score, risk disparity can be formulated as a lower bound for basd fairness disparity.
serve
Proof. Consider scenario involving two demographic groups E (ke M', alongside a 0-1 loss function.
Fairness metric EOd For EOd, the risk disparity be reformulated
RRa, (w Rew (w")l
1( # Un)
Σ
(inn yn)
1Qul
Qui
(omon)ER
P( + Y PP + Y (==skk) k')
Σ [ (Y- = - =)) P(Ý = - =k, -P) - = =yss = k. - w))
P(Y = w|s=M 11) (P(P / s ,,Y y) woo( - k,Y w)) w
P(Y = slt k') (P() = -11s -- = K,Y w0 = -
4. 11)
binary case
+P(Y 0,5 k)) (P(P- = |0 S k, -
k 01)
P(Y 1|s k') (P(8- =1 1 y,
+ +F( 0,8 = (woaR(y = 11
K k-
+PY 0,s R)) (1 w 0))
- P(Y ill k') [1
- -PY = k/) -
# balanced groups
<P(Y = s/l = - +
+ P(Y = = = = -
= k
v)
(0(0,1)
EDd-bbasdd fairness disparity
where we define (y) = P[Y P(y=)SS=F) serving as the bias weight. Here, we make a mild
P(==\(==k)
assumption that the two demographic groups are balanced, i.e., wy) = 1. Then, we can see that the last item measures the fairness disparity based on EOd for binary classification problems. Thus, we can claim that reducing risk disparity can promote the faimess metric EOd.
17

---

Fairness metric DP
Similarly, for DP, we formulate the risk disparity as
|Rqe (wf) Rey (wf))
T(ún # Un) 1Qu1
1
Σ (E
(Ún # vn)
1Qxl
P(Y # 4 8
k) P(ý Y 5 =X)
E (P(r = y == = y K, =) - PP( = = 5= = R)P(Y= = =yls= =w))
Σ P(Y = = = - n) (P(2- = =y|s= k² worlv))(( = = S = =b))
P(Y slt K, 1). (F() = - P(y 11 S = b))
binary case
+P(Y = -|. = K,Y = 0) (PI)) = 0 0 s = k2) worly 0) PF = S b))
P(Y = s|s = = = (F(Y 1 - = 1) P(Ý = 1 S = kt)
+P(Y = 0 k 0) (wDr(y = 0) F(Y 1 1|5 = k) P(V s k')
+ +P(Y = -|. - = 0) (1 wbrly = 0))
Calibrating group sufficiency
P(Y = s/s = 1-s= = = (P() = -) 1|5=
+PYY = 0|0 = K,Y = 0) (P(8 = 1 k) P( =1 s=
P(Y 1|8 K, Y 1) P(Y = 0|8 k, 0/ p(y s = PP 1 - ==== k))
< P( = 1 S= k) - P( 1 S k)
13P-based fairness disparity
where we define wpp(y) = S In fact, (DP(y) measures the group sufficiency P(Y=
ratio [61] Note that the group sufficiency is closely related to the idea of calibration [[]] Thus, we make a mild assumption that the group sufficiency ratio wDr(y) can be calibrated by 1, i.e., P(Y S = k. Ý = y) = P(Y y K. y) = R. where R is calibration score. When two demographic groups are balanced, i.c., (D) L, we can see that the last inequality indicates the DP-based fairness disparity for binary classification problems. Therefore, we can also claim that the fairness metric DP can also be encouraged when reducing the risk disparity.
C Detailed analysis of the fair influential sampling algorithm
C.1
Evaluating first-order influence estimations against real influence
Recall that the influence score derived in this paper primarily utilizes a first-order approach. Here, we will demonstrate how accurate the first-order estimation of the influence is in comparison to the real influence.
C.2 Comparative analysis of computational costs
Recall that the proposed algorithm FIS needs to pre-calculate the accuracy loss and fairness loss for evaluating the performance of a certain example. However, the extra computation cost is comparable to the cost of traditional model training. Note that the main extra computation cost in FIS (Algorithm
18

---

first order estimation per sample
1.0
0.8
0.6
0.4
0.2
0.0
0.0
0.2
0.4
0.6 0.8
1.0
actual influence per sample
Figure 4: We validate how accurate the first-order estimation of the influence is comparison the real influence. The z-axis represents the actual influence per sample, and the y-axis represents the estimated influence. We observe that while some of the examples are away from the diagonal line (which indicates the estimation is inaccurate), the estimated influences for most of the data samples are very close their actual influence values.
T mainly results from model gradients. Let p denote the number of model parameters, then the cost for computing the gradients is Op)) per sample. Specifically, in each round that involves sampling, we need to calculate three parts of gradients: the gradients of [U] unlabeled instances, the average gradient of [Q,1 validation instances w.r.t. accuracy loss, and the gradient of [Q,1 validation instances w.r.t. fairness loss. Note that in general, IQul << <U/ In practical implementation, to speed up the calculation gradients over [U] instances, we randomly sample 0.2-0.5% of the unlabeled dataset in each sampling batch. Additionally, we can increase the number of newly selected examples for each round (r*) to save computation costs. In our experiments, we usually have 10-20 sampling rounds. For instance, running one experiment for the CelebA dataset single GPU roughly requires about 4 hours.
C.3 Exploration of the labeling strategies
Note that we provide strategy that employs lowest-influence labels for annotating labels. This section will explore an alternative strategy that employs model predictions for the purpose of labeling. For completeness, outline the two proposed labeling strategies follows.
Strategy
Use low-influence labels. That 9 arg minke[K] |Inflacc (a', k)), which corre-
sponds using the most uncertain point.
Strategy II
Rely on model prediction. That is, ÿ = arg max [K) [x; (k]), where f(z; w)]l]
indicates the model's prediction probability on label
Remark C.1. Suppose that the model is trained with cross-entropy loss. The labels obtained through Strategy II are sufficient to minimize the influence of the prediction component, i.e., Inflacc(a' (x', k). That said, the Strategy 11 will produce similar labels as SStrategy
Proof. Based on the definition of the influence of the prediction component, as delineated in Eq. (
becomes evident that the most uncertain points are obtained when the proxy labels closely align with the true labels. Consequently, the model predictions used in Strategy II also approximate the true labels minimize the cross-entropy loss. Thus, in a certain sense, Strategy I and Strategy II can be considered equivalent.
19

---

D
Omitted proofs
In this section, we present complete proofs for the lemmas and theorems in Section and 5 respec- tively.
D.1
Proof of Lemma
Lemma
4.1
The influence of predictions the validation dataset Qu can be denoted by
Inflaco(z')=
Σ
Inflaco(z 2n) -1 Σ Enele.1 (Ow,((ws,= 0w, ((We, zR))
nEIQ.l
Proof. Taking the first-order Taylor expansion, we will have
(f( 0f(w, xg) w-
(( 2 R E(We, 2nn)
f f(w++1, f(ee:
where we take this expansion with respect to f(w, x.)) Similarly, we have
f(we+1, S(We, 2.)
We+1 We
Ow
W=W:
0 Of(w,a)) @e(w x')
Ow
dw
where the last equality holds due to Eq.
① Therefore,
de(w, 2n))
0f 0f(w, 29))
de 2')
[Wr+1,, E(We, 2n))
0f(w, xi))
Ow
Ow
W=
( (af(w, xn) ol(w,
Ow
dw
Then the accuracy influence on the validation dataset V can be denoted by
Inflaco Inflaco(2') (z')
Σ
Inflace (z), -1 Ow, ((Werz'),
Σ nelQul
Ow, ((wes
nEIQ.l
D.2
Proof of Lemma 4.2
Lemma 4.2
The influence fairness on the validation datasel Qu can be denoted by
infl)ar(2/))== = Σ Inflear (2', 2
Σ nE|Qul
(0w, (lw, 2/), Ow, ((w,, =n))
nEIQul
Proof. By first-order approximation, have
do(w..
d( 22) ze Φi wr, 2n)) +
f(we11,2)) - f(we,
05( @f(w,
Recall by first-order approximation, we have
@8f(w @f((w xi) ol(w,z'))
f(we+1, S(wi, -n
Gw
Ow
Www.
Therefore,
Φ ((we+1, =0] - o(w,, =00 -n [ol(w,z)) 2!) ( do(We, 2
Ow
dw
20

---

Note the loss function in the above equation should be since the model is updated with E-loss. Therefore.
Bl(w, 2²)
do(wE, =n))
Infitair
Σ
Inflaiir (2) ~=
Σ nE|Qa1
dw
Ow
ne|Q~l
W=w.
D.3 Proof of Theorem 5.1
Theorem 5.1,
(Generalization enror bound). Let dist(P, 2), Gp be defined therein. With probability least 8 with (0.1), the generalization evvor bound of the model trained on dataset is
1og(4/8) P|P
Re(wP) s Gr (..dss((,))) +V
+ Rr(wP).
distribution shift
Note that the generalization error bound is predominanll influenced by the shift in distribution when we think of un overfitting model, i.e., the empirical risk Rr(w 0. The detailed proof is presented as follows.
Proof. The generalization error bound is
Re(wP) (Re(w²) Ro((())
RR((wP) Rp(wP))
+ Rp((w
empirical risk
distribution shift
Hoefiding's inoquality
log( (4))
Gp (,
+ Rp(w²)
P|
For the first term (distribution shift), we have
Ro(wP) - RR(wwP) = Ezn (((w( :2]] EE--E (e ,2]]
(2) ii)BSun [(( [2] Σ
p (P) = =i)EENa [e(wP 22]]
1=1
10 (P) (T i) (0 E [e(wW,
i=1
< Gp dist(P, Q).
where we define dist(P. P. 2
www".2 2)] S Gp, Vi e subscript P of the constant G to clarify the corresponding model wP. Then, for the second term (Hoeffding inequality), with probability at least 1 6, we have [Rp(wP)- Rr(wP)
I because of Assumption 5.2 To avoid misunderstanding. i) and Ez [[(w", Ez-,,
llg((4/)) 2
D.4 Proof of Theorem
Theorem 5.2 (Upper bound fairness disparity). Suppose Ro(-) follows Assumption 5.1 Let di 2), Gp. dist(Pks Qx) and dist(Px, P) be defined therein. The initial learning rate n < VITT. where T denotes the number of training epochs. Given model W and w trained exclusively on group k's data Pk, with probability at least - 8 with å E (0, 1), then the upper bound of the fairness disparity is
Ro.(w²) Re(wP) Gp Gp dist((P GL2 dist PPx, P\ +G dist(Pk, 2x) +
distribution shift
group
21

---

where Y V 1og(1/8)
2|P| V 2/
log(1/6)
50 + Dk.. Note that Bg [e(w"; 2) - Gk. w Rr((w)
Ro (wl+). Specifically, w and we can be regarded as constants because Rp(wP) and Rr (w correspond to the empirical risks, (2 and Re (wox) represent the ideal minimal empirical risk of model w trained distribution and Qks respectively. Moreover, these quantities w and wa are not taken into account during the training phase, but rather in relation to the final model.
R) and wk = Rr,, (w*)
Proof. First of all, we have
Re,(w Re(wP)
-(Re(w Pt) Re(w") ()) (Ro. (wP) - -Re(w**))
-(Ro(w Pr) Re(w?)) (Ro, (w - Ro, (w (t)) + -
- RRo(wPt)
S(Ro(w Re(w")) (Ro, (wP) RR2 (w
where w represents the model trained exclusively on group k's data. For simplicity, when there is no confusion, we use w to substitute w The inequality Ro, (w*) Re(w") 2 0 holds because the model tailored for a single group & can not generalize well the entirety the test set Q.
Then, for the first term, we have
17 (2)
L 2 w
Ro(w") Ro(ww
(VRo
(RR)(W") wh w
L L|| w 11
2L (Re(w"")
IAS
L|
w1 11 (Re(w") R ()
group gap
train-lest model gap
where inequality (a) holds because the L-smoothness of expected loss Re((-), i.e., Assumption 5.1 Specifically, inequality (b) holds because, by Cauchy-Schward inequality and AM-GM inequality, we have
T. l| pP12
(Re(wP), w wP
[VRe(w>)13
2L
Then, inequality (c) holds due to the L-smoothness of Re(-) (Assumption 5.1 of Polak- Lojaieezz inequality, which follows
we can get a variant
(VRe("")l < 2L(Re(w()) - R (R((w))
where (R%(wQ) denotes the ideal minimal empirical risk of model w trained on distribution Q. Following a similar idea, for the second term, we also have
Ro.(w") Rea (w*) L|Iw" w011 2 (Re, (w*) - Re. (R..w22.) (w
Combined with two terms, we have
+ 21 w/112 (w*) -R (w2+)) (w.(w") RR(wP) (Ro(w") R5 (w
train-test model gap
group model gap
Lastly, integrating with Lemmas D.I
D.2 and D.3 we can finish the proof.
Lemma D.I. (Train-test model gap) With probability at least given the model w. trained on truin set P, we have
(4((4/)
Re(w") (G(w)) G dist(( +
2|P) + w.
where dist(P, Q) = E/1 (T( - (TT i) and Bz (l(wP. (((w..))) , S Gr, Vi E I, and
constant Rp(w") R).
22

---

Proof. First of all, we have,
Re(w")- {) = (w( + Rp((w) Re(ww)
- Ro(ww))))))))))))
s G dist (P, + Rp(w") - Re(
S G dist(P, (
R ( R R5(w
distribution shift
Hoefiding inequality
overfiting ideal case
For the first term (distribution shift), we have
Re(w?) RR(wwP) EE~ele(W" .2]1 Bell-E(p ,2]]
[2]]
Σ (0) (T+ =i)BsNT, 1l(w" .2)] Σ p (P) -i)B [((wW,,)
1 Σ
1p (P) = i) - (0) (T=
i) E (((w ,]]
i=1
s Gp.dissPP,
where we define dist(P. 2)
,w], 1= (x= -p -p) = i) and Ez-,, [e(w" 22] < Gp, vi e
because Assumption 5.2 For the second term, with probability least 1 we have Ing(4/8)
[Rp(w") R $ V 2 Note that the third term Rp(w")) R2 (2(w)) can be regarded as constant to. because Re(w") is the empirical risk and R3(w9 (w is the ideal minimal empirical risk of model 2 trained on distribution Q.
Therefore, with probability at least 1 - 6, given model w".
log(4/0)
Q)s R )) G Gp-ddit(PPP)
+ w.
2 PI
Lemma D.2. (Group model gap) Suppose Assumptions 5.1 and 5.2 hold for empirical risk R-(-). The initial learning rate nh "2TLL where T denotes the number of training epochs. Then, we have
Σ ( (T==)) =i) (T b0)
l|w - - w 2LG
Proof. According to the above definition, we similarly define the following empirical risk Rr, (w) over group k's data P& by splitting samples according to their marginal distributions, shown as follows.
RR, (w) = Σ (T= i)E [e(ww 2)].
Let f) indicate the learning rate of epoch f. Then, for each epoch 4, group k's optimizer performs SGD as follows:
w = - T/t Σ p
(k) (T
i=1
23

---

For any epoch t + 1, we have
|| w1+al1
= =1lw/ - T/t
Σ
p
(N = Vj Www.een::l(ww w! + 1/ Σ p (3) (a = i) E. Be (((, 2)]
1=1
< 1|w6 w:'1 +ml
p() (1) (TT = Bww. Ie( 2]
Σ
p (P((( (á = i) w Bew [((w[] 2]]1
1=1
1=1
-w?11 + 2m²
Σ p (P((T i) FWBBwa,ll(W' , W. [ =3] 11
i=1
+ 2m 11 Σ
D(A) (N = i) p)P) (xx = i) W. [e(w =)11
$ </Iw/- w/113=
+ 21
Σ (b) (π = i) 1){
1| - w:llp 1|?
1=1
+ f (w)))
Σ
( =i) - -p(P = =0)l
1=1
p(M) i)L ) l ww?l?
< 1 + 21h
Σ (p(00 (IT =) - -p(P) = 331) 2
+ 2mag
Mmax (w
-p)) Σ 1p(0) (T= =1] - (TT = 0)] 2
< (1 + (1+2 L - w/l1 + 22
where the third inequality holds since we assume that V.EZaT [e( []] is LT,,- -Lisschizz continuous, [e(w], =)] V w Ezn,, [[(w]' =)]l < l|w w/ |l. and denote Jmaz (maz(w?)) (w?")
i.e., //VEE...
max/_1 1/ w E Eenn, [[(w, --]] The last inequality holds because the boove-mentioned assumption that L = Ln, = L Vi I, i.e., Lipschitz-continiie
will not be affected by the samples' classes.
Then, Imaz (w.") S G because of Assumption 5.2
For T training epochs, we have
||w f/1
1
< (1 + 2n/ L )|| [/ - w 2L G2
Σ (n (T = - (pT = -01)
T
T
Σ
< II (1 + L w/ - wf + 22G
Σ
(1 + 2n L2))T~1
(N (x( =) (P) i))
1=0
t=0
1=1
2
< 2LG > 21
1p(h) (T i) -p(P)(T = i)]
where the last inequality holds because the initial models are the same, i.c., wo = w/ wo Vk. When the condition n/2 < n /2TT, satisfies, 2LG² ET=onii (1 + 2 can be simplifited as LG which is independent of the learning algorithm. This condition is easy to be satisfied since the learning rate We is small value (< 0.0001) and usually set to be decay with the training epoch (i.c., 7--1 < 77).
24

---

Lemma D.3. With probability ar least 1 - 6, given the model w trained on group k's dataset Pk.
we have
log(4/6)
Roa ( -Re, (w S Gk dist(Pks 2x) +
P/
where dist(Pk, 2k) Ei=1/o(Pe) and wa = Rp, (w ) Ro (w
pp(())( i) and E [e(ww 2)] I GR, vi I,
Proof. Building upon the proof idea presented in Lemma D.I. for completeness, we provide full proof here. Firstly, we have,
Re. (w.(w") Ro (wle) = (Ro.(w)) - Rp. (px() + (Rp, (R,,(w") - P. (w*)) + (R (w*) Ro. (wew))
distribution shilt
Hoellding's inequality
overfitting case
For the first term, we have
R.o (w*) - Rp,(w")
1 (n) (nr -))R (e(w (((ww[,)))
Σ p (P) (( =)]
$ Σ (T) = - - ( = EZI [((ww ,]]
i=1
s G₁ -dddiisPP... 21)
= where dist(Px. 2x Ele (T -)) i) and Ezwn, [e(w*, x =)] S Gk, Vi due to Assumption 5.2 Recall that the constant G& clarifies the bound of loss on the corresponding model
w For the second term, with probability at least Ó- we have RR, (w*)) - (w*) N
(4/()
2/
For the third term, we define wa == R.p, (w*) ) RSs (w ),), which can be regarded as a constant. This is because Rp, (w*) represents empirical risk and Rss (w is the ideal minimal empirical risk of model w Q. trained on sub-distribution Qk- Therefore, with probability at least 8, given model w
log(4/6)
Res (w*) -Ro, (w s G+ dist(Pk, Qx) +
+ wa
P|
E More experimental results
E.1 Datasets and parameter settings
We empirically evaluate FIS on the CelebA dataset, an image dataset commonly used the fairness
literature 49). We also evaluate FIS on two tabular datasets: UCI Adult [8] and Compas dataset [6].
E.1.1 CelebA dataset
Dataset details CelebA 49 is an image dataset with 202,599 celebrity face images annotated
with attributes, including gender, hair colour, age, smiling, etc. The sensitive attribute is gender: S = (Men, Women). We select four binary classification targets, including smiling, attractive, young, and big nose. For example, the task to predict whether person an image young (Y 1) or non-young (Y = 0), among other attribute predictions.
25

---

details In all our experiments using the CelebA dataset. we train vision transformer with patch size (8, 8) using SGD optimizer and a batch size of 128. The epochs are split into two phases: warm-up epochs (5 epochs) and training epochs (10 epochs). The default label budget per round, which represents the number of solicited data samples, is set to 256. Additionally, the default values for learning rate, momentum, and weight decay are 0.01, 0.9, and 0.0005, respectively. We initially allocate 2% of the training set for training purposes and the remaining 98% for sampling. Then, we randomly select 10% of the test data for validation. For JTT, we explore 10% data for training purposes with weights À = 20 for retraining misclassified examples.
E.1.2 UCI Adult dataset
Dataset details. The Adult dataset [8] predicts whether an individual's 's annual income falls below exceeds 50K, denoted as Y 0 and Y respectively. This prediction is based variety of continuous and categorical attributes, including education level, age, gender, occupation, etc. The default sensitive attribute in this dataset is gender S = {Men, Women] } [80]. In particular, also group this dataset using age 5 = = (Teenager, Non-teenager). To achieve a balanced age distribution in the dataset, individuals with an age of less than 30 are grouped as "Teenagers". The dataset contains total of 45,000 instances. The dataset exhibits an imbalance: there are twice as many men as women, and only 15% of those with high incomes are women.
Plyper-paramette details. In the experiments using the Adult dataset, we train a two-layer ReLU network with hidden size of 64. The epochs are split into two phases: warm-up epochs (100 epochs) and training epochs (60 epochs). The default label budget per round, which represents the number of solicited data samples, is set to 1024. Additionally, the default values for learning rate, momentum, and weight decay 0.00001, 0.9, and 0.0005, respectively. We resample the datasets to balance the class and group membership 17]. The dataset is randomly split into train and a test set in a ratio of 80 to 20. Then, we randomly re-select 20% of the training set for initial training and the remaining 80% for sampling. Also, 20% examples of the test set are selected to form a validation set. We utilize the whole model to compute the prediction influence and fairness for examples. Then, we randomly select 10% of the test data for validation. For JTT, we explore 30% data for training purposes with weights À= 20 for retraining misclassified examples.
E.1.3 Compas dataset
Dataset details. Compas dataset, also known as the Correctional Offender Management Profiling for Alternative Sanctions dataset, is collection of data related to criminal defendants. It contains information on approximately 6,172 individuals who were assessed for risk of re-offending. The primary task associated with this dataset is predicting whether a defendant will re-offend (Y = 1) or not (Y = 0) within a certain time frame after their release. The sensitive attribute often considered to be race, specifically whether the individual is classified as African American or not.
Elyper-parameter details. In the experiments using the Compas dataset, we train a multi-layer neural network with one hidden layer consisting of 64 neurons. The epochs are split into two phases: warm-up epochs (20 epochs) and training epochs (50 epochs). The default label budget per round, which represents the number of solicited data samples, is set 128. Furthermore, the default values for learning rate, momentum, and weight decay are 0.01, 0.9, and 0.0005, respectively. We resample the datasets to balance the class and group membership [17). The dataset is initially split into training and test sets at an 80-20 ratio. Then, we further split 20% of the training set for initial training, reserving the remaining 80% for sampling. Additionally, 20% of the test set is selected to create a validation set. We use the entire model to calculate prediction influence and evaluate fairness for the dataset examples.
E.2
Full version of experimental results
E.3
Exploring the impact of label budgets
In our study, we examine how varying label budgets influence the balance between accuracy and fairness. We present the results of test accuracy and fairness disparity across different label budgets on the CelebA, Compas, and Adult datasets. In these experiments, we use the demographics parity
26

---

Table 2: We report the Kest_accuracyy fairness, _volattion for evaluating the performance on the CelebA dataset with two binary classification targets Young and Big Nose. We select gender as the sensitive attribute.
CelebA Young
0.05
(Test_acet,
DP.)
(Test_ace", EOp()
(Test_acct. EOdL)
Base(ERM)
(0.755 = 0.002. 0.190
(0.759 = 0.005, 0.102 0.005)
(0.755 = 0.002, 0.182 # 0.018)
Random
(0.763 0.008, 0.158 0.016)
(0.698 0. 0099 0.075 0.021)
(0.766 + 0.011, 0.156 0.017)
BALD
(0.776 # 0.021, 0.165 + 0.019)
(0.775 + 0,020, 0.076 0.007)
(0,779 + 0.005, 0.162 # 0.021)
ISAL
(0.781 a 0.020, 0.180 a 0.014)
(0.781 a 0.020, 0.084 0.006)
(0.780 a: 0.021, 0.173 a: 0.012)
JTT-20
(0.774 0.167 0.016)
(0.774 0.024, 0.083 0.007)
(0.772 0.023,
0.025)
FIS
(0.763 0.004, 0.104 0.059)
(0.773 0.003, 0.041 0.015)
(0.763 0.005, 0.118 0.074)
CelebA Big Nose
0.05
(Test (Test_acct, DPJ)
(Test_acet, EOpl)
(Test_acet, [OdL)
BRs)(E
(0.752 # 0.024, 0.198 = 0.034)
(0.755 # 0.022. 0.206 = 0.018)
(0.755 # 0.022, 0.183 # 0.029)
Random
(0.760 0.009, 0.014)
(0.757 0.004, 0.190 0.029)
(0.759 + 0.006, 0.167 * 0.022)
BALD
(0.777 0.004, 0.184 0.016)
(0.765 0.003, 0.209 0.014)
(0.770 i 0.004, 0.170 i 0.015)
ISAL
(0.782 # 0.001, 0.148 0.059)
(0.782 0.001, 0.154 4 0.080)
(0.779 # 0.006, 0.145 # 0.065)
JTT-20
(0.771 + 0.014, 0.191 0.036)
(0.758 0.026, 0.223 0
(0.764 + 0.019, 0.193 : 0.016)
FIS
(0.779 0.009, 0.089
(0.780 0.046
(0.772 0.062= 0.081)
Table 3: The performance results of The sensitive attribute age.
on the Adult dataset.
Income (age)
0.05
TTest_acet, DPJ)
(Test_ace?,
EOpL)
[Test_acet, EOdJ)
B))
(0.665 0.045, 0,255 0.041)
(0.665 a 0.045, 0.115 0.036)
(0.665 a 0.045, 0.158 a 0.030)
Random
(0.765 0.021. 0.209 0.042)
(0.758 4 0.027, 0.127 0.013)
(0.764 i 0.018, 0.133 : 0.027)
BALD
(0.767 a: 0.019, 0.203 0.017)
(0.703 0,111, 0.117 0.013)
(0.763 i 0.022, 0.128 1 0.014)
ISAL
(0.765 + 0.020. 0.015
(0.755 0.028, 0.128 0.013)
(0.761 # 0.024, 0.138 # 0.009)
JTT-20
(0.751 = 0.013, 0.262
(0.742
=.149
(0.745 + 0.014, 0.171 # 0.0112
HIS
(0.766 0.013, 0.214 0.009)
(0.757 + 0.133
(0.763 + 0.011, 0.143 + 0.023)
Table 4: The performance results of Cees_accuracy, Sairress_vvolatiinn on the Compas dataset. The selected sensitive attribute race.
Recidivism
0.05
(Test_acef, DP.)
(Test_ace*, EOp!)
(Test_acc*. EOd()
Base(ERM)
(0.675 = 0.005. 0.333 = 0.008)
(0.675 0.005, 0.267 0.010)
(0.675 a 0.005, 0.284 # 0.010)
Random
(0.689 0.007, 0.305 0.023)
(0.686 0.253 0.0055
(0.688 : 0.006, 0.256 : 0.023)
BALD
(0.688 0.3: 0.011. 0.313 0.012)
(0.686 0.256 3 0.031)
(0.688 # 0.011, 0.263 # 0.011)
ISAL
(0.697 + 0.002, 0.308 0.025)
(0.698 + 0.004, 0.274 0.022)
(0.697 + 0.001, 0.260 + 0.026)
JTT-20
(0.646 0.009, 0.240 0.016)
(0.630 0.024, 0.141 0.028)
(0.646 1 0.009, 0.200 1 0.007)
FIS
(0.690 0.002, 0.299 0.029)
(0.694 0.002, 0.241 0.035)
(0.698 + 0.005, 0.252 + 0.030)
(DP) as our fairness metric. For convenience, we maintain fixed label budget per round, using rounds of label budget allocation to demonstrate its impact. The designated label budgets per round for the CelebA, Compas, and Adult are 256, 128, and 512, respectively. In the following figures, the x-axis is both the number of label budget rounds. The y-axis for the left and right sub-figures are test accuracy and DP gap, respectively. As observed in Figures 7 compared to the three baselines JTT-20., and ISAL), our approach substantially reduces the DP gap without sacrificing test accuracy.
Specifically, on the Adult dataset, both accuracy and fairness violation converge to similar numerical values when the budget is lower than 20, suggesting potential overfitting of the model to insufficient training examples. With a larger budget, our algorithms outperform other baseline methods, achieving higher accuracy and lower demographic disparity.
27

---

CelebA
CelebA
1.0
0.30
BALD
0.25
JTT-20
test accuracy
ISAL
gap
0.20
FIS
0.6
0.15
BALD
0.10
0.4
JTT-20
0.05
RS
0.2
10
20
30
40
50
60
70
10
20
30
40
50
60
70
label budget
label budget
Figure 5: The impact of label budgets on the test accuracy & DP gap in the CelebA dataset. The binary classification targets is Smiling.
Adult
Adult
0,80
0.35
BALD
BALD
accuracy
0.75
JTT-20
ISAL
0.30
JTT-20
ISAL
0.70
0.20
0.55
0.50
0.15
label budget
label budget
Figure 6: The impact of label budgets on the test accuracy & DP gap in the Adult dataset. The sensitive attribute is sex.
E.4 The role of validation dataset size
In this subsection, we explore the impact of adjusting the validation set size on our algorithm's s performance. We present the test accuracy and fairness disparity across different validation set sizes on the CelebA, Compas, and Adult datasets. Note that the default validation set size for image and tabular datasets is set to 1% and 4% the whole dataset size, respectively. That is, the default validation set sizes are 1996 (CelebA), 1800 (Adult), and 247 (Compas) instances, respectively. In particular, given the smaller size the default validation set, the minimum scale of the validation set and
size is set to x/sx (nearly 400 CelebA images). Tables and 6 present the performance results on the CelebA, UCI Adult, and Compas datasets, respectively.
Table 5: The performance results of (test_accuracy fairness fairness_violatiineee violation) on the CelebA dataset when the validation set size is reduced to 1/2x and x/sx. Our algorithm retains the test accuracy and fairness violation when we vary the validation set size.
CelebA Smiling
CelebA Attractive
0.05
-Tsst_cctt. DPL)
(Test_ace (Test_acet. EOp.)
(Test_aoct, BOd[)
(Test_acc", DPL)
(Test_acc' EOp.)
(Test_accf. EOd,)
1x
(0.848, 0.084)
(0.876, 0.031)
(0.864, 0.030)
(0.680, 0,285)
(0.695, 0.148)
(0.692, 0.148)
0.105)
(0.891, 0.042)
(0.880, 0.028)
(0.648, 0.249)
0.188)
(0.678, 041)
f/x
(0.872, 0.117)
(0.863, 0.057)
(0.886, 0.028)
(0.604, 0.171)
(0.707, 0.209)
(0.645, 0.145)
CelebA Young
CelobA Big Nose
0.05
(Test_acoe acct, DPL)
(Test_ccef, EOp.)
(Test_nor); EOd,)
(Test_acc", DPL)
(Test_acct: EOp.)
(Test, (Test_acet, BOd,)
1x
(0.766, 0.1)
(0.775, 0.043)
(0.769, 0. 168))
(0.771, 0.156)
(0.765, 0. 129)
(0.758, 155)
1/xx
(0.735, 0.093)
(0.762, 0.067)
(0.769. 0.055)
(0.771, 0.054)
(0.761, 061)))
(0.748, 0.096)
1/xx
(0.743, 0.107)
(0.780, 0.097)
(0.757, 1616
(0.772, 0.095)
(0.750. 0,300)
(0.760, 0.16)
E.5
Benchmarking model performance with validation set enhancements
Note that we resort an additional validation set for developing FIS. To demonstrate FIS's advantage at the same levels of information, introduce new baseline called Random+Val. This method
28

---

Compas
Compas
0.74
BALD
0.34
BALD
JTT-20
JTT-20
test accuracy
ISAL
ISAL
0.72
0.32
0.70
0.30
DP
0.66
0.26
20
40
80
40
60
label budget
label budget
Figure 7: The impact of label budgets on the test accuracy & DP gap in the Compas dataset. The sensitive attribute is race.
Table 6: We examine the performance results of (test_ accuracy, fairness, violation) on the tabular datasets (Left: Adult; Right: Compas) when the validation set size is reduced to 1/2x, 1/4x, and / / We observe that our algorithm still retains the test accuracy and fairness violation when we vary the validation set size.
Adult Income(Age)
Compas Recidivism
0.05
Tess_acce__a DPL)
(Testaccet, EOp.)
(Test_accf. EOdl)
(Tost_acc", DPL)
(Test_acef. EOp.)
(Test_acef. EOd()
1x
(0.757, 0,198)
(0.718, 0.124)
(0.750, 0,125)
(0,690, 0,313)
(0.696, 0,249)
(0,702, 0.257)
(0.717, 0.259)
(0.634, 0.123)
(0.736, 0.14
(0.683, 0.270)
0.247)
(0.695, 0.244)
(0.749, 0,196)
(0.750, 0.121)
(0.747, 0,137)
(0,677, 0,283)
(0.682, 0,276)
(0,680, 0.244)
(0.721, 0.205)
(0.706, 0.148)
(0.706, 0.179)
(0.689, 0.289)
(0.668, 0.236)
(0.683, 0.252)
involves continuing train the model with a randomly sampled validation set. Specifically, we start with the Random's 's last saved checkpoint and train it further using the validation set. In particular, we would incorporate fairness regularizer with dynamic weight train the model using validation data, considering its sensitive attributes to reduce fairness disparity. Due to its small size, we limit training to 10 epochs to avoid overfitting. The performance results of Random, Random+Val, and FIS are given in Table 7
Table 7: Comparative analysis of (test_accuracy accuracy, fairness fairness_violatioon in the CelebA, Adult and Compas datasets. The table illustrates that even at the same information level (using the validation set to train), FIS can obtain better performances. Similarly, we highlight all the fairer but without sacrificing accuracy results in boldface compared to Random.
Smiling
CelehA Attractive
DJI5
(Test_ fest_acet, DP.)
Tesstacct,_ EOpl)
(Test_acce acc EOd.)
(Tst_accf, DPI)
(Test_ace") EOpl)
(Test_acet, EOd.)
Random
(0.853, 0.132)
(0.863, 0.053)
(0.861, 0.031)
(0.696, 0.367)
(0.708, 0.253)
(0.696, 0.243)
Random + Val
(0.801, 0,115)
(0.872, 0.139)
(0:879, 0.153)
(0.638, 0.199)
(0.699, 0.366)
(0.699, 0.355)
(0.877, 0.122)
(0.886, 0.040)
(0.882, 0.023)
(0.680, 0.285)
(0.695, 0.148)
(0.692, 0.148)
Adult Income(Age)
Compus Recidivism
0.05
(Tost_acee poct, DPJ)
(Test_acef: EOpl)
(Test_occ), BOdl)
(Tost_ace cest_aacf. DPL)
(Tost_acef; BOpl)
(Tst_ace). BOd_)
Rondom
(0.745, 0.236)
(0.729, 0. (313)
(0.748, 0.15
(0.096, 0,316)
(0.698, 0,258)
(0.694, 0.269)
Random Val
(0.762, 0.161)
(0.743, 0.266)
(0.788, 0.131)
(0.604, 0313)
(0.623, 0.147)
(0.628, 0.153)
FIS
(0.751, 0.205)
(0.725, 0.130)
(0.750, 0.125)
(0.688, 0.316)
(0.695, 0.250)
(0.693, 0.254)
F Potential privacy leakage from non-demographic and demographic feature correlations
Note that some non-demographic features may correlate with sensitive attributes (demographic information), which could lead to potential privacy leakage issues [82]. However, it is crucial to clarify that our method specifically limits its query to the data. We only query the true labels for selected subset of unlabeled examples. While correlations between non-demographic variables and sensitive attributes may exist in the underlying data, our method itself does not introduce any additional privacy leakage beyond what is inherent in the original dataset. On the other hand, our
29

---

work's primary focus is not on addressing privacy concerns related to demographic information. Rather, our main objective is reduce faimess disparities while maintaining favorable utility trade-off. We achieve this without explicitly incorporating any additional sensitive information into the process and without directly engaging with the complex privacy implications of demographic data usage.
To address this potential privacy concern, we can analyze via differential privacy. Consider function (6)) that maps non-demographic information (feature æ and label y) to sensitive attribute Due to insufficient information, Φ(-) is not deterministic, making unable to precisely estimate s. If a deterministic mapping function existed, it would unavoidably lead to privacy leakage. Therefore, we assume that given the same features and label, the function e(-) output might vary. For example, in the Adult dataset, a includes age and credit history, is the income, and s is the gender. In practice, both men and women have a probability of earning more than 50K (i.e., y = 1) given the same age, credit history, etc (same feature 2.). Suppose P(o(ær, y) = 8 S 8, y) S 1 and P( y) = 8
8 x. y) 2 61 for all æ, y, 8, s' (where * s'). Here, represents the sensitive attribute variable, which is unknown to ((-). Then, we have
Pio(# v) = 8 8, P( y) = 8|8 st, min Pin 3 S = 8 x. y)
max ((o(a, v) ā 1 = 8, x. v)
1 - 6".
where In
\سال In practice, if the mapping function is too strong, i.e. In we can add additional noise to reduce their informativeness and therefore better protect privacy.
is too large,
<
30

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The claims in the abstract reflect our primary contributions that we propose active sampling approach mitigate unfairness without compromising accuracy. One notable advantage is our approach does not require eliciting sensitive attributes from the unlabeled data.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discussed the limitations in the concluding remarks section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
31

---

Answer: [Yes]
Justification:
We list series of assumptions we used in Assumption 5.1 and Assumption 5.2
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We include all the experimental details in the Appendix. We also include the source code in the supplementary material for reproducing the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
32

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We include the README file for the instructions of reproducing the results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "cipps.c/puulli//guu /ttoe//uuuddeooooouuummiiiiiii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We have included these details in the setup as well the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We report the standard deviations the main result table.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
33

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We report the computational resource in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:////wwrriissscpplillleeeeee httpar/p.....pllaaa///ccccceeeee
Answer: [Yes]
Justification:
The research conducted in the paper conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We have a dedicated broader impact section that addressed the ethical concerns.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
34

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release any data or models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have credited the datasets we used for the experiments.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
35

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
36


Reviews:
[{"review_id": "o9tw1yY9vR", "reviewer": "Reviewer_KagD", "summary": "The authors propose a method called Fair Influential Sampling (FIS), which selects candidate data points for training based on their estimated improvement on both fairness and accuracy. This estimation considers the influence of a new data point as the average gain in accuracy and fairness achieved by performing a gradient descent step with the new data point. This average is empirically computed using a labeled validation dataset. The gain in loss (or fairness) is approximated as the inner product between the gradient of the loss (or fairness) with respect to the parameters evaluated on the new data point and each validation point.\n\nThe proposed influence metric does not require access to the sensitive attributes of the candidate data points. Additionally, when labels for the target variable are unavailable for candidate data points, the authors suggest producing proxy labels by annotating the most confident class. This allows the estimation of the accuracy influence score. If a data point is selected for further training, a user must then perform the actual labeling.\n\nThe selected data points are those that improve the fairness influence score without negatively impacting the average accuracy score on the validation set. Experimental results demonstrate that the proposed approach can select training data points that enhance fairness without reducing accuracy compared to a random sampling strategy. Furthermore, under the constraint of maintaining an accuracy equal to or better than a \"random\" model, FIS achieves superior fairness performance compared to other competing methods.", "questions": "Could the authors indicate if the results in Table 1 are computed with respect to a test dataset that does not include the one used for validation and sample selection? I ask this because in line 330, the paper states that \"10% of the test data is randomly set aside as a hold-out validation set.\" I assume this portion is not used for evaluation.\n\nTypo in Eq 4, shouldn’t \\ell be \\phi?", "limitations": "yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written, addressing a relevant problem with clear formulation and proposed methods. The authors provide theoretical justification for the approximations used in computing their influence scores and offer formal analysis on the impact of adding more data on model generalization.\n\nExperimental results demonstrate that the proposed active sampling approach performs as expected. It does not harm accuracy compared to a base ERM model or random sampling. Moreover, the selected data points improve fairness under this constraint. Additionally, the proposed approach does not necessarily require labeled data, which is advantageous as only ground truth labels for the accepted data are needed. This can motivate the use of this method.\n\nThat being said, I am not entirely familiar with the extensive state-of-the-art literature on active sampling to fully evaluate the novelty of the proposed approach.", "weaknesses": "It seems to me that the data selection strategy based on the proposed influence scores is approximating the process of training with the validation set. I believe it would be beneficial to compare the performance of a model trained with this labeled validation set (without sampling and with random sampling) to demonstrate the advantage of using a data sampling strategy based on the validation set instead of simply including it as part of the training data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for their positive feedback and comments. We will address individual comments below.\n\n**Response to weakness**: Thank you for raising this good point. We appreciate the feedback and apologize for not emphasizing this aspect in the main text of our paper. We have conducted several experiments, which are detailed in the appendix, to highlight this key point. Specifically, in Appendix E.5, we introduced a new baseline, termed 'random+val', which involves training the model on a dataset created through random sampling combined with a full validation set. As shown in Table 8, including the validation data as part of the training set will degrade the violation of EOp. Our experimental results demonstrate the superiority of our sampling method over this new baseline.\n\n**Response to Q1**: Thank you for pointing out the concern regarding data leakage. The \"original\" test dataset has been carefully divided into two independent portions: a new test dataset and a validation set. Therefore, the validation data will not be used for evaluation.\n\n**Response to Q2**: Equation (4) is correct. In this equation, $\\ell(\\cdot)$ represents the typical cross-entropy loss, while $\\phi(\\cdot)$ denotes the fairness loss. Intuitively, we use the inner product of the gradients based on these two types of loss functions for sampling, as shown in Eq. (4). For instance, if the gradient of the fairness loss aligns with that of the accuracy loss for a particular sample, this indicates that incorporating this sample into further training could simultaneously reduce both accuracy loss and fairness loss.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Q8bbQgwFMk", "reviewer": "Reviewer_Pisk", "summary": "Group/statistical notions of fairness are known to be at odds with the accuracy metric. The authors propose an active sampling strategy to improve the tradeoff between fairness and predictive performance. This sampling approach only requires the sensitive information to be known in a small validation set. They estimate the influence of a potential instance on improving the accuracy and fairness, and choose those that most positively influence both objectives.", "questions": "Q1 - What do > symbols refer to in equations (2) and (3)? Vectorial product?\n\nQ2 - According to the definitions of Lemma 4.1 and 4.2 the value of the influence depends on the size of the validation set. Why don’t you use an average so that this characteristic does not influence?\n\nQ3 - In the section *proposed algorithm* you describe an iterative procedure to find the top r instances whose fairness influence based on the true labels meet the conditions, but you are using proxy labels and not the true labels. Then, how do you know the latter?\n\nQ4 - Why do you need to make the assumption that the train/test distributions are drawn from a series of component distributions?\n\nQ5 - Regarding Theorem 5.2 you talk about the group gap, and claim that the more balanced the data is (...). But which gap/balance do you refer to? Is it in terms of representation or performance?\n\nQ6 - Regarding the tabular data, you resample the data to balance the class and group membership; but what is the reason behind this procedure? What happens if there is no such balance?", "limitations": "Limitations are clearly stated by the authors in Section 7.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "S1 - Improving the accuracy fairness trade-off is a very relevant problem. Besides, doing it in the scenario when only minimal sensitive information requires to be known extends its applicability to real-world scenarios.\n\nS2 -  Figure 1 offers a nice overview to situate the problem and provide an intuition regarding the objective of the work. \n\nS3 - In general terms, the readability of the text is quite good. The ideas are presented clearly, with cohesive explanations throughout. The text is well divided into sections and paragraphs, which helps maintain a consistent flow and makes it easy to follow and understand. \n\nS4 - The paper demonstrates commendable attention to reproducibility by providing detailed information regarding the experimental setup.", "weaknesses": "W1 - The related works section needs improvement, starting from the most general topics (active learning and fair classification), to more specific areas of research. Additionally, the claim made by the authors in lines 107-108 is not true. Those approaches do not strive to achieve uniform accuracy over all groups, but rather to improve the predictive performance of the classifier on the worst performing groups. Indeed, it is in the metrics considered by the authors where parity among groups is required. Besides, the acronyms DP and EOp are used before defining them. Moreover, when talking about [39] in line 92 it is not which problem the recent work aims to address.   \n\nW2 - In section 4.1 you introduce the influence of the accuracy component but what you are looking into is the loss, and the loss need not be equal to accuracy. Maybe you could rename it and call it the loss/risk component, or change the definition otherwise.\n\nW3 - When active sampling is used the iid condition is not satisfied anymore, but the authors do not mention this in the work nor address this challenge. \n\nW4 - One of the main claims made in the work is that this strategy is able to improve the fairness guarantees of classifiers without sacrificing accuracy. The authors even claim the latter can be seen from Table 1. However, in the empirical validation there are no numerical results regarding the accuracy, only fairness-related metrics are shown. Consequently, this claim is impossible to validate from the results provided in the main paper. \n\nW5 - The comparison with respect to the JTT method is unfair. In fact, this procedure has a strategy to choose the optimal weight that needs to be given to the misclassified instances, and is learned in the training process. Thus determining the weight to be 20 is unfair. \n\nW6 - It is not very clear how much data/information is given to each of the methods, which makes it difficult to verify whether the empirical validation is fair.\n\nW7 - The main objective of the active sampling paradigm is to achieve superior performance (in this case better accuracy-fairness trade-off) with less datapoints, as they are chosen effectively. However, there is no empirical validation nor theoretical statement that supports the latter.\n\nAdditional minor comments:\n\nW - In the paragraph labelling from section 4.2, the explanation that introduces the paragraph is not very clear, and it is in fact misleading… it would be nice to improve its clarity. \n\nW - In line 235 you talk about ‘most confident labels’, but maybe employing the word confidence is not the most appropriate. \n\nW - The authors do not explicitly state that the fairness loss is something to be minimized. \n\nW - The authors do not clearly state how the hyperparameters of the rest of the methods are tuned. \nW - In the paragraph *proposed algorithm* from section 4.2, the authors talk about tolerance $\\epsilon$ but there is no such parameter in Algorithm 1. \n\nW - You are talking about the trade-off between accuracy and fairness but in line 89 you use the word generalization, which is not a synonym but a word with a completely different meaning.\n\nW - The text contains several typos. For instance, between lines 83-85, work(s) need to be plural, and train examples are better references as training examples. Also the authors employ ‘to us’ in line 113, and it would be better to replace it with a more formal phrase such as ‘to this work’.\n\nW - In line 86 when you talk about the trade-off it would be nice to include some references (as in the introduction).\n\nW - Check how the references are written, missing capital letters in [49] and [23]; no publish information in [57], etc. \n\nW - Regarding the titles of the sections, only the first letter of the first word needs to go in uppercase. \n\nW - $\\G_p$ is not defined.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for their detailed feedback and comments. We will address individual comments below.\n\n**Re to W1**:  We want to clarify that we do not assert that \"Those approaches do not strive to achieve uniform accuracy over all groups.\" Rather, our claim is that these approaches primarily focus on enhancing the worst-affected group performance, and they assess this improvement using accuracy-level metrics. However, this does not necessarily align with popular fairness metrics such as DP.\nWe appreciate you pointing out the need to define the acronym DP clearly. We will ensure this is corrected in the revised version of the paper.\nRegarding reference [39], as indicated by its title, this paper's starting point is to achieve fairness at no utility cost  (predictive utility, synonymous with accuracy). This recent work also motivates us to do active sampling without retraining. Therefore,  this paper is within the scope of the fairness-accuracy tradeoff.\n\n**Re to W2**: Thank you for your feedback. We use the terms \"accuracy\" and \"fairness\" to highlight the goals of different components within our model, which helps in distinguishing their roles more clearly. The ‘loss’ component may be inaccurate because both the fairness and accuracy components are based on the loss.\n\n**Re to W3**: We want to clarify that we do not make any additional assumptions about the iid condition between the train and test data distributions. Our default setting assumes the potential for a distribution shift between two distributions. Our main observations (Lines 297-308) confirm that the proposed method demonstrates robustness under non-iid conditions, effectively addressing potential distribution shifts.\n\n**Re to W4**: Thanks for your feedback. To illustrate the tradeoff between accuracy and fairness, we consistently present the results in the format: (test_accuracy, fairness_violation). We highlight this form in the captions of tables.\n\n**Re to W5**: We want to clarify that the JTT weight is a hyperparameter, which can be easily verified because the weight for misclassified examples is input in Algorithm 1. The value of 20 is the same setting as JTT. Here is the original statement presented in the JTT paper: “For JTT, we additionally tune the number of epochs of training the identification model $T$ and the upsampling factor $\\lambda_{\\text {up }}$. For the final experiments we tune over $\\lambda_{\\text {up }} \\in \n\\\\{20,50,100\\\\}$.” \n\n**Re to W6**: All baselines including our method are done completely in the same data settings. Due to the space limit, we provide only a brief overview of the three datasets in Section 6.2 (line 331 and line 343). More data information can be found in Appendix E.1 (dataset and parameter settings). \n\n**Re to W7**: We want to clarify that our main goal is to reach a better accuracy-fairness tradeoff point while not disclosing more sensitive attributes, instead of focusing on less data points. Nevertheless, in Section 6.3, we conduct experiments to illustrate the impact of the solicited data size, shown in Fig. 2.\n\n\n**Re to m-W1**: We first use pseudo-labels as in Eq. (5) to find appropriate examples due to the labeling budget, then query the ground-truth labels of the selected examples for training purposes.\n\n\n**Re to m-W3**: We want to clarify that the CE loss is the only thing that needs to be minimized during training, rather than fairness loss. The fairness loss is only used to compute the fair influence score. As we highlight in this work,  the selected examples should contribute to a decrease of fairness loss by only minimizing the CE loss.\n\n**Re to m-W4**:  There are not many hyperparameters for tuning. In our work, the learning rate and warm-up epoch are fixed.\n\n**Re to m-W5**:  Thank you for pointing out this. The tolerance is used for the final model selection, that is, $\\\\{\\\\mathbf{w}\\_t \\mid \\\\mathrm{VAL}\\_t>\\\\mathrm{VAL}\\_0 - \\epsilon \\\\}$.\n\n**Re to m-w2, m-W6 to m-W10**: Thank you for pointing out these typos. We will update it in the revised version.\n\n**Re to Q1**:  The <> symbol refers to the vector product.\n\n**Re to Q2**: We can use an average value for calculation. Mathematically, the only difference between calculating the average gradient and the summation of gradients from the validation set is the normalization factor. However, the absolute values of influence scores are not critical in themselves because these scores are only for ranking purposes.\n\n**Re to Q3**: In the active sampling setting, the true labels will be inquired for selected data. Due to the large size of the unlabeled set, we first use the proxy labels to select potential “good” examples for inquiring true labels to reduce the labeling budget. \nOnce received the true labels, due to the difference between true and proxy labels, we double-check whether the influence scores of those samples calculated on true labels meet the condition.\n\n\n**Re to Q4**: We want to clarify that it is not an assumption but rather a general distribution property. Without making any additional assumptions about the training or testing distributions, this property acts as a direct tool for assessing the differences between the train and test distributions.\n\n**Re to Q5**: The group gap is for the term $G_k \\cdot \\operatorname{dist}\\left(P_k, P\\right) := \\operatorname{dist}(\\mathcal{A}, \\mathcal{B}):=\\sum_{i=1}^I\\left|p^{(P)}(\\pi=i)-p^{(P_k)}(\\pi=i)\\right|$. \nAchieving more balance means reducing the distance or disparity in distribution between $P_k$ ​ and $P$, thus allowing for a reduction in the first term. \n\n\n**Re to Q6**: Resampling the data to balance data across groups is a regular preprocessing method, which helps prevent overfitting to the majority class. Class imbalance can introduce biases between groups, affecting model performance and fairness. By ensuring a balanced distribution of classes within each group, we can more accurately and fairly evaluate the model's performance.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eU4TVFFZ3L", "reviewer": "Reviewer_wZhW", "summary": "This paper addresses the challenge of achieving fairness in machine learning (ML) without compromising model accuracy. The authors propose a novel active data sampling algorithm that mitigates group fairness disparity by acquiring more data without requiring sensitive attribute annotations for training, thus protecting privacy. The algorithm scores each new example based on its influence on fairness and accuracy, evaluated on a small validation set, and selects examples for training accordingly. Theoretical analysis demonstrates how acquiring more data can improve fairness without degrading accuracy, and provides upper bounds for generalization error and risk disparity. Extensive experiments on real-world data validate the effectiveness of the proposed approach.", "questions": "1) Could you provide more discussion on the choice of fairness definition used in your evaluation? I have skimmed section B of your appendix, but why is risk disparity selected as the fairness definition throughout, and how does risk disparity compare with other fairness metrics like equalized odds or counterfactual fairness metrics?\n\n2) Your proposed algorithm relies on a clean and informative validation set that contains sensitive attributes. How do you address the potential challenges in obtaining such validation sets in practical scenarios, especially considering privacy concerns and data availability? What are the implications if the validation set is not fully representative or contains noisy labels, and how might this affect the performance and fairness of your algorithm?\n\n3) Based on my understanding of equation 5, your method is compatible with multiple (discrete) sensitive variables. It that correct?\n\n4) For table 1: How is fairness_violation defined? Why is the row of DP of CelebA - Attractive not highlighted? What if the highlighting rule?\n\nWriting suggestion: I am confused with the highlighting scheme of Table 1. It would be better if it's explained in the caption right above.", "limitations": "The authors mentioned limitation that it needs validation set though did not attempt to address it.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Clear & meaningful motivation: The proposed fair influential sampling (FIS) method avoids the need for sensitive attribute annotations during the sampling or training phases, thereby protecting privacy.\n\nSound Theoretical Contributions: The paper includes a thorough theoretical analysis, showing how the proposed algorithm can improve fairness without harming accuracy. It also provides upper bounds for generalization error and risk disparity, enhancing the method's credibility.\n\nApplicability: Based on the method design & setup, it seems it's not limited to single sensitive variable, rather multiple discrete ones. Therefore, this renders the method considerably better applicability compared to most other fairness methods.", "weaknesses": "1) Insufficient discussion of fairness metrics: The choice and justification of the fairness metrics used in the evaluation could be more thoroughly discussed. A deeper explanation of why these particular metrics were selected and how they effectively measure fairness would provide a clearer understanding of how fairness is quantified in this study and the implications of these choices. For example, why choose risk disparity as the fairness definition, and how does it compare & contrast with other metrics, like equalized odds, or counterfactual fairness metrics.\n\n2) As the authors point out, The proposed algorithm relies on a clean and informative validation set that contains sensitive attributes of data examples. This dependency may not always be practical or feasible in real-world scenarios, where obtaining such validation sets can be challenging due to privacy concerns and data availability.\n\n3) Unclear experiment results presentation and significance: I find key result in table 1 confusing. For example, how is fairness_violation defined, and what is the highlighting scheme, and why is the row of DP of CelebA - Attractive not highlighted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for their positive feedback and comments. We will address individual comments below.\n\n**Re to W1**: Thank you for raising this concern. We want to clarify that the definitions of well-known fairness metrics, such as DP and EOd, are provided in Section 3 (Preliminaries). These metrics are used for experimental evaluation in Section 6.\nIn this work, we focus solely on active sampling to build a fairer dataset, which is then used to train the model through standard Empirical Risk Minimization (ERM) with Cross-Entropy (CE) loss. Without relying on any additional assumptions about the model or dataset, an intuitive approach is to analyze the loss function. Risk disparity can thus serve as an intermediate-term for theoretical analysis. Proposition 3.1, in Line 162, clearly illustrates the connections between risk disparity and other metrics. Additional theoretical proof can be found in Appendix B.\n\n**Re to W2**:  In practice, when dealing with a noisy validation set, we can effectively address the issue by applying a loss correction method to the fairness loss. This adjustment is based on the label transition matrix [1], which helps account for the noise in the labels. Therefore, this practical issue can be heavily alleviated, which can be addressed in future work.\n\n\n\n**Re to W3**: Thank you for raising this concern. The term \"fairness violation\" is widely used to quantify the absolute differences based on fairness metrics, such as DP. As outlined in the caption of Table 1, we specifically bold the results that have lower fairness violation meanwhile the accuracy is almost the same as the accuracy obtained by random baseline. For example, in the row for DP on the Celeba-smiling dataset, compared to the random baseline results (0.837, 0.133), we highlight FIS because it achieves a lower DP value (0.084(FIS) < 0.133(random)) while maintaining high accuracy (0.848(FIS) > 0.837(random)). Another baseline, JTT, achieves a lower DP value (0.077(JTT-20) < 0.133(random)), but its accuracy drops significantly (0.698(JTT-20) < 0.837(random)).\nWhen applying this criterion to the row for DP on the CelebA dataset, we observe that no results meet our highlighting scheme. \n\n\n\n**Re to Q1**: Please refer to the response to W1.\n\n**Re to Q2**: Please refer to the response to W2.\n\n\n**Re to Q3**: Thank you for your attention. Your understanding is correct. Eq. (5) is compatible with sensitive variables.\n\n**Re to Q4 & writing suggestion**: Please refer to the response to W3.\n\n\n[1] Weak proxies are sufficient and preferable for fairness with missing sensitive attributes, ICML 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iFaGTeT5Vx", "reviewer": "Reviewer_cxN7", "summary": "In this paper, the authors propose Fair Influential Sampling(FIS) to achieve a better Pareto Frontier of the fairness-accuracy tradeoff through sampling training data. To maintain fairness without diminishing the accuracy, training data examples are validated through a validation dataset. In this case, privacy is maintained by not annotating sensitive attributes in the large training dataset, but doing so for the validation dataset. An example data is selected as training data based on its influence on the accuracy and fairness using the validation dataset. This research also claims that by acquiring new data the proposed algorithm can decrease the group gap by utilizing the fairness components and can also prevent the negative impact of distribution shift by utilizing accuracy influence components, which in theory should improve fairness without harming the accuracy.", "questions": "Please refer to the “Weaknesses” section.", "limitations": "In this paper, the authors propose FIS to preserve the fairness of the model and the privacy of individuals. However, several limitations can be observed in the sampling process. Firstly, the authors should consider the computational expenses of the algorithm involving different scales of datasets. Moreover, as sampling relies on the validation dataset, its fairness may be jeopardized if the validation dataset is skewed. Additionally, it would be much more efficient to develop an algorithm to select a validation dataset that contains little to no bias. The sampling method also does not explain how fairness is maintained in the case of expanding datasets.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The proposed sampling approach attempts to mitigate group fairness without compromising both accuracy and privacy.\n\nAs the FIS does not require annotation of sensitive attributes for the large training dataset a substantial amount of cost and labor is negated.\n\nThe work addresses potential distribution shift issues effectively to maintain fairness and accuracy.\n\nEven though the method is validated on some specific datasets the basic mechanism of the FIS has the potential to be applicable in different sectors where maintaining fairness is a crucial factor.\n\nThe maintenance of privacy supports ethical AI application development practices.", "weaknesses": "The success of the FIS is heavily dependent on the refinement level of the validation set. If the validation set is not a proper representation of the large training dataset then it may compromise the accuracy and fairness.\n\nThe paper's sampling strategy mostly depends on particular influence measurements. The sensitivity of these matrices for different data distributions should be thoroughly explored.\n\nIf there is bias present in the validation dataset, unfairness may be amplified by the FIS method.\n\nThe proposed method relies substantially on a clean and informative validation dataset. Which might be hard to secure in certain cases.\n\nThe paper does not mention several recent studies in the related work section, which could provide additional context or alternative methodologies for addressing fairness without demographic data. Here are a few examples:\n\n[1] Zhao, Tianxiang, et al. \"Towards fair classifiers without sensitive attributes: Exploring biases in related features.\" Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining. 2022.\n\n[2] Yan, Shen, Hsien-te Kao, and Emilio Ferrara. \"Fair class balancing: Enhancing model fairness without observing sensitive attributes.\" Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 2020.\n\n[3] Chai, Junyi, Taeuk Jang, and Xiaoqian Wang. \"Fairness without demographics through knowledge distillation.\" Advances in Neural Information Processing Systems 35 (2022): 19152-19164.\n\nThe authors' method overlooks the presence of non-demographic features that could still relate to demographic information, posing a privacy issue even without direct inclusion of demographic information.\n\nAlthough in “Empirical Results” section states that 4 datasets were used, according to Appendix E, only 3 datasets(CelebA dataset, Adult dataset, COMPAS dataset) were used for experimental purposes.\n \nIn 4.2, it is stated that line no 9 updates U and Soriginal, but according to the pseudo code this process is being executed in line no 11.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for their positive feedback and comments. We will address individual comments below.\n\n**Response to the refinement of validation set**: Thank you for raising this concern. For this issue, we did some ablation study in Section 6.3 to explore the impact of the validation set size on our algorithm’s performance, shown in Fig. 2. Our experimental results also demonstrate the superiority of our sampling method over this new baseline.\n\n**Response to fairness metric sensitivity of sampling strategy**: Thank you for this comment. We want to highlight that our method is general and suitable for all fairness-metric-based fairness losses. It allows for the adjustment of the fairness loss component to suit various fairness metrics as needed.\n\n**Response to bias validation set**: Thank you for your feedback. In this work, we mildly assume that the validation and test sets come from the same distribution. Consequently, any bias present in the validation set will also be reflected in the test set. Therefore, it is impossible to accurately evaluate fairness on a biased test dataset. Nonetheless, we can discuss some cases where the validation set is biased while the test set is not. Such biases might arise from the small size of the validation set. To illustrate the impact of validation set size, we conducted experiments shown in Fig. 2. If the bias is incurred due to noisy sensitive attributes, we can apply loss correction techniques to these attributes. We welcome the reviewer to provide a practical case of bias for further discussion.\n\n\n**Response to the clean and informative validation set**: Thank you for raising this concern. In practice, when dealing with a noisy validation set, we can effectively address the issue by applying a loss correction method to the fairness loss. This adjustment is based on the label transition matrix [1], which helps account for the noise in the labels. Therefore, this practical issue can be heavily alleviated, which can be addressed in future work.\n\n**Response to recent studies**: Thank you for providing more references. We will update accordingly in the revised version.\n\n**Response to the correlation of non-demographic features and demographic information**: Thank you for bringing attention to this important aspect. We acknowledge this as an important consideration in data privacy. It is true that some non-demographic features may correlate with sensitive attributes. However, it's crucial to clarify that our method specifically limits its query with the data. We only query the true labels $y$ for a selected subset of unlabeled examples. This approach means that while correlations between non-demographic variables and sensitive attributes may exist in the underlying data, our method itself does not introduce any additional privacy leakage beyond what's inherent in the original dataset. \nOn the other hand, our work’s primary focus is not on addressing privacy concerns related to demographic information. Rather, our main objective is to reduce fairness disparities while maintaining a favorable utility trade-off. We achieve this without explicitly incorporating any additional sensitive information into the process and without directly engaging with the complex privacy implications of demographic data usage.\n\nTo address this privacy concern, we can analyze it via differential privacy. Consider a function $\\phi(\\cdot)$ that maps non-demographic information (features $X$ and label $y$ ) to sensitive attribute $a$. Due to insufficient information, $\\phi(\\cdot)$ is not deterministic, making it unable to precisely estimate $a$. If a deterministic mapping function existed, it would unavoidably lead to privacy leakage. Therefore, we assume that given the same features and label, the function $\\phi(\\cdot)$ output might vary. For example, in the Adult dataset, $X$ includes age and credit history, $y$ is the income, and $a$ is the gender. In practice, both men and women have a probability of earning more than 50 K (i.e., $y=1$ ) given the same age, credit history, etc (same feature $X$ ). Suppose $P(\\phi(X, y)=a \\mid A=a, X, y) \\leq 1-\\epsilon_0$ and $P\\left(\\phi(X, y)=a \\mid A=a^{\\prime}, X, y\\right) \\geq \\epsilon_1$ for all $X, y, a, a^{\\prime}$ (where $a \\neq a^{\\prime}$ ). Here, $A$ represents the sensitive attribute variable, which is unknown to $\\phi(\\cdot)$. Then, we have\n$\n\\frac{\\mathbb{P}(\\phi(X, y)=\\tilde{a} \\mid A=a, X, y)}{\\mathbb{P}\\left(\\phi(X, y)=\\tilde{a} \\mid A=a^{\\prime}, X, y\\right)} \\leq \\frac{\\max \\mathbb{P}(\\phi(X, y)=\\tilde{a} \\mid A=a, X, y)}{\\min \\mathbb{P}\\left(\\phi(X, y)=\\tilde{a} \\mid A=a^{\\prime}, X, y\\right)} \\leq \\frac{1-\\epsilon_0}{\\epsilon_1}=e^{\\varepsilon}.\n$\nwhere $\\varepsilon=\\ln \\left(\\frac{1-\\epsilon_0}{\\epsilon_1}\\right)$. In practice, if the mapping function is too strong, i.e. $\\ln \\left(\\frac{1-\\epsilon_0}{\\epsilon_1}\\right)$ is too large, we can add additional noise to reduce their informativeness and therefore better protect privacy.\n\n**Response to line number and number of datasets**: Thank you for pointing out these typos. We will update it in the revised version.\n\n\n\n[1] Weak proxies are sufficient and preferable for fairness with missing sensitive attributes, ICML 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes FIS, a tractable active data sampling method that only requires group annotations on the validation set rather than the entire training set. The proposed algorithm evaluates and scores each data sample based on its influence on fairness and accuracy using the validation set, then selects a subset of examples to be added to the training set. The influence is evaluated by comparing the sample's gradient to the one derived from the validation set. This work formally analyses how more data improves fairness, and provides an upper bound on the generalisation error and risk disparity. The effectiveness of FIS is empirically validated on real-world datasets against various baselines. 

* *Merits*: The reviewers found the paper to be well-written with clear a strong motivation, addressing a relevant problem with minimal sensitive information required, enhancing its real-world applicability. It presents solid theoretical analysis, clear formulations, and sufficient empirical results. The paper also provides enough details to ensure reproducibility.

**Revisions for the camera-ready**: The authors should incorporate their responses from the rebuttal and discussion periods into the revised version. In particular:

-  *Related work*: The related work section needs enhancement with some missing literature mentioned by the reviewers [1]-[3] and additional context on risk disparity (i.e., W3 from Reviewer wZhW) in the early sections. 
 
 - *Text revisions*: Some claims need revision (e.g., lines 330 (Q1 from Reviewer KagD), lines 107-108 (W1 from Reviewer Pisk)), and a clear definition of fairness violation should be included (Re to W3, Reviewer wZhW). Also, please fix typos such as m-w2, m-W6 to m-W10 from Reviewer Pisk, and the number of datasets in the main text. 

 - *Results presentation*:  SAC, Reviewers wZhW and Pisk, and AC highlighted that it is difficult to assess the significance of the proposed approach based on how the trade-off results are presented in Table 1. The presentation of Table 1 needs improvement. This could be addressed by turning these results into a trade-off curve (using data also from Figures 2, 4, 5, and 6 if needed) or points in the trade-off plane. If not feasible, please adjust the bolding scheme and provide more context in the main text and figure caption based on your discussions with Reviewer wZhW in W3. Additionally, the authors should include pointers and a brief description of the results presented in the appendix within the main manuscript.

 - *Limitations*: Some reviewers raised concerns about the need for a representative validation dataset, but this issue is already discussed by the authors (lines 372-373) and rebuttal. However, the authors should add their *Response to the clean and informative validation set* to Reviewer cxN7 in the respective discussion on the main text, or to the appendix. 

- *Appendix:* Include *Re to W5* to reviewer  Pisk and *Response to the correlation of non-demographic features and demographic information* to Reviewer cxN7 in the Appendix, along with relevant pointers in the main text.


------

[1] Zhao, Tianxiang, et al. "Towards fair classifiers without sensitive attributes: Exploring biases in related features." Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining. 2022.

[2] Yan, Shen, Hsien-te Kao, and Emilio Ferrara. "Fair class balancing: Enhancing model fairness without observing sensitive attributes." Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 2020.

[3] Chai, Junyi, Taeuk Jang, and Xiaoqian Wang. "Fairness without demographics through knowledge distillation." Advances in Neural Information Processing Systems 35 (2022): 19152-19164.
Decision: Accept (poster)