Adaptive Data Debiasing through Bounded Exploration
Authors: Yifan Yang
Yang Liu
Parinaz Naghizadeh
Venue: NeurIPS 2022 Accept (2022)
Keywords: Debiasing
bounded exploration
fairness

Abstract: Biases in existing datasets used to train algorithmic decision rules can raise ethical and economic concerns due to the resulting disparate treatment of different groups. We propose an algorithm for sequentially debiasing such datasets through adaptive and bounded exploration in a classification problem with costly and censored feedback. Exploration in this context means that at times, and to a judiciously-chosen extent, the decision maker deviates from its (current) loss-minimizing rule, and instead accepts some individuals that would otherwise be rejected, so as to reduce statistical data biases. Our proposed algorithm includes parameters that can be used to balance between the ultimate goal of removing data biases -- which will in turn lead to more accurate and fair decisions, and the exploration risks incurred to achieve this goal. We analytically show that such exploration can help debias data in certain distributions. We further investigate how fairness criteria can work in conjunction with our data debiasing algorithm. We illustrate the performance of our algorithm using experiments on synthetic and real-world datasets.

Adaptive Data Debiasing through
Bounded Exploration
Yifan Yang Ohio State University yang. 54830osu. edu
Yang Liu University of California, Santa Cruz yangliuduesc.er
Parinaz Naghizadeh Ohio State University naghizadeh. 10osu. edu
Abstract
Biases in existing datasets used to train algorithmic decision rules can raise ethical and economic concerns due to the resulting disparate treatment of different groups. We propose an algorithm for sequentially debiasing such datasets through adaptive and bounded exploration in a classification problem with costly and censored feedback. Exploration in this context means that at times, and to a judiciously- chosen extent, the decision maker deviates from its (current) loss-minimizing rule, and instead accepts some individuals that would otherwise be rejected, so as reduce statistical data biases. Our proposed algorithm includes parameters that can used to balance between the ultimate goal of removing data biases which will in turn lead to more accurate and fair decisions, and the exploration risks incurred to achieve this goal. We analytically show that such exploration can help debias data in certain distributions. We further investigate how fairness criteria can work in conjunction with our data debiasing algorithm. We illustrate the performance our algorithm using experiments synthetic and woal-world datasets.
Introduction
Data-driven algorithmic decision making is being adopted widely to aid humans' decisions, in applications ranging from loan approvals determining recidivism in courts. Despite their ability to process vast amounts of data and make accurate predictions, these algorithms can also exhibit and amplify existing social biases (e.g.. [T]
(3) There are at least two possible sources unfairness in algorithmic decision rules: (data) biases in the training datasets, and (prediction) biases arising from the algorithm's 's decisions 29 The latter problem has been receiving increasing attention, and is often addressed by imposing fairness constraints on the algorithm. In contrast, in this paper, we are primarily focused on the former problem of statistical biases in the training data itself.
The datasets used for training machine learning algorithms might not accurately represent the agents they make decisions on, due to, e.g., historical biases in decision making and feature selection, changes in the populations' characteristics or participation rates since the data was initially collected. disadvantaged groups; i.e., data bias can cause prediction/model bias, as also verified by recent work Motivated by this, we focus on data biases, and propose an algorithm which, while attempting to make accurate (and fair) decisions, also aims to collect data in way that helps it recover unbiased estimates of the characteristics of agents interacting with
Such data biases in turn result in disparate treatment of underrepresented [8 40] 4% 255
In particular, we study a classification problems with censored and costly feedback. Censored feedback means that the decision maker only observes the true qualification state of those individuals admits (e.g.. a bank will only observe whether an individual defaults on or repays a loan the loan is extended in the first place; employer only assesses the performance of applicants it hires). In such settings, any mismatch between the available training data and the true population may grow over time due to adaptive sampling bias: a decision rule is adopted based on the current training
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

data, the algorithm's 's decisions will impact new data collected in the future, in that only agents passing the requirements set by the current decision rule will be admitted going forward. In response, the decision maker may attempt to collect more data from the population; however, such data collection is costly (e.g., in the previous examples, may require extending loans to/hiring unqualified individuals). Given these challenges, we present an active debiasing algorithm with bounded exploration: our algorithm admits some agents that would otherwise be rejected (i.c., it explores), yet adaptively and judiciously limits the extent and frequency of this exploration.
Formally, consider a population of agents with features z, true qualification/laells y, and group memberships g based on their demographic features. To design a (fair) algorithm that can minimize classification loss, the decision maker (implicitly) relies on estimates (z) of the feature- dis- tribution of agents from group g. obtained from the current training dataset He = {(In: Un 9n ) However, the resulting assumed distribution fe)e(z)) (2) may be different from the true underlying dis- tribution f (Ir); this is the statistical data bias issue we focus on herein. Specifically, we consider distribution shifts between the estimates and the true distributions (Assumption D
Our algorithm. We propose an active debiasing algorithm (Algorithm D.. which actively adjusts its decisions with the goal of ensuring unbiased estimates of the underlying distributions f (a) over time. In particular, at each time t, the algorithm selects a ftairness-constraige would minimize classification error based on its current, possibly biased estimates fg, (x);; adopting this decision rule corresponds to exploitation of the current information by the algorithm. At the same time, to circumvent the censored feedback nature of the problem, our algorithm also deviates from the prescriptions of this loss- poss-minimizing classifier adaptively, based on the current estimates); this will constitute exploration. Our algorithm includes two parameters to limit the costs of this exploration: one modulates the frequency of exploration (an exploration probability E, which can be adjusted using current bias estimates), and another limits the depth of exploration (by setting a threshold LB, on how far from the classifier one is willing to go when exploring). We show that these choices can strike a balance between the ultimate goal of removing statistical biases in the training data which will in turn lead more accurate and fair decisions, and the cost of exploration incurred to achieve this goal.
decision rule that
judiciously chosen extent (the extent is chosen
Summary of findings and contributions. Our main findings and contributions
follows:
Comparison with baselines. We contrast our proposed algorithm against two baselines: an exploitation-oni baseline (one that does not include any form of exploration), and pure exploration baseline (which may randomly accept some of the agents rejected by the classifier, but does not bound exploration). We show (Theorem [ that overestimates of the underlying distributions. Further, while pure exploration can debias the distribution estimates in the long-run (Theorem 2 it does at the expense of accepting any agent, no matter how far from the classifier's 's threshold, leading to more costly exploration (Section 5)
always leads to
2. Analytical support for our proposed algorithm. We show (Theorem Bp that our proposed active debiasinn sng algorithm with bounded exploration can correct biases unimodal distribution estimates. We also provide an error bound for our algorithm (Theorem 4
3. Interplay with fairness criteria. We analyze the impact of fairness constraints on our algorithm's performance, and show (Proposition | that existing fairness criteria may speed up debiasing of the data in one group, while slowing it down for another.
4. Numerical experiments. We provide numerical support for the performance of our algorithm using experiments synthetic and real-world (Adult and FICO) datasets.
Related work. Our paper is closely related to the works of 20 of data biases on (fair) algorithmic decision making. Among these works, Bechavod et al. 4 and learning in the presence of censored feedback. While these works also use exploration, the form and purpose of exploration is different: the algorithm in 4 starts with a pure exploration phase, and subsequently explores with the goal of ensuring the fairness constraint is not violated; the stochastic (or exploring) policies in [40 conduct (pure) exploration to address the censored feedback issue. In contrast, we start with a biased dataset, and conduct bounded exploration to debias data; fairness constraints may may not be enforced separately and are orthogonal to our debiasing process. Also, as shown in Section 5 such pure exploration processes can incur higher exploration costs than our proposed bounded exploration algorithm.
which study the impact
Kilbertus et al. 20 study fairness-constrrinee
2

---

Our work is also closely related to 30 30 !1l, which study adaptive sampling biases induced by a decision rule, particularly when feedback is censored. Among these, Neel and Roth E01 also consider an adaptive data gathering procedure, and show that no debiasing will be necessary if the data is collected through a differentially private method. We similarly propose an adaptive debiasing algorithm, but unlike 30 account for the costs of exploration in our data collection procedure. The recent work of Wei |I studies data collection in the presence of censored feedback, and similar to our work, accounts for the cost of exploration in data collection, by formulating the problem as a partially observable Markov decision processes, Using dynamic programming methods, the data collection policy is shown to be threshold policy that becomes more stringent (in terminology, reduces exploration) as learning progresses. Our works are similar in that we both propose using adaptive and cost-sensitive exploration, but we differ in the problem setup and our analysis of the impact of fairness constraints. More importantly, in contrast to both 30 our starting point is biased dataset (which may be biased for reasons other than adaptive sampling in its collection, including historical biases); we then show how, while attempting to debias this dataset by collecting new data, any additional adaptive sampling bias during data collection can be prevented.
Our work also falls within the fields of selective labeling bias, fair learning, and active learning. From the selective labeling bias perspective, Lakkaraju et al. [22] propose a contraction technique to compare the performance of the predictive model and a human judge while they are forced to have the same acceptance rate. De-Arteaga al. [ propose data augmentation scheme by adding more samples that are more likely to be rejected (we refer to this as exploration) to correct the sample selection bias. From the fair learning perspective, Kallus and Zhou [8] propose a re-weighting technique (re-weighting ideas are also explored in ① 6 17 to solve the residual unfairness issue while accounting for adaptive sampling bias. From the active learning perspective,
Carfega-CCamero et al. 22 adaptively acquire additional information according to the needs of different groups or individuals given information budgets, achieve fair classification. Similar to the approaches of these papers, we also compensate for adaptive sampling bias through exploration; the main difference, aside from the application, is in our analytical guarantees as well as our study of the interplay of data debiasing with fairness constraints.
More broadly, our work has similarities to Bandit learning and its focus on exploration-exploitaaie trade-offs. A key difference of our work with existing bandit algorithms (e-greedy, UCB, EXP3, etc.) is our focus bounded exploration. We provide additional discussion on this, and review other related works 35 3
18 32 in more detail, in Appendix B
2 Model and Preliminaries
The environment. We consider a firm or decision maker. who selects an algorithm to make decisions on population of agents. The firm observes agents arriving over times t = 1, 1...... makes a decision for agents arriving at time based on the current algorithm, and can subsequently adjust its algorithm for times t - 1 onward based on the observed outcomes.
Each agent has an observable feature or score x E X C R These represent the agent characteristics that are leveraged by the firm in its decision; examples include credit scores or exam scores. Each agent is either qualified or unqualified to receive a favorable decision; this is captured by the agent's true label or qualification state E {0, 1}. with = 1 and y = 0 denoting qualified and unqualified agents, respectively. In addition, each agent in the population belongs a different group based on its demographic or protected attributes (c.g., race, gender); the agent's 's group membership is denoted g E {a, b). We consider threshold-based group-specific, binary classifiers h9g, (x) : X {0, 1} as (part of) the algorithm adopted by the firm, where fgt denotes the classifier's 's decision threshold. An agent from group g with feature x arriving at time t admitted x 2 .g.t-
Quantifying bias. Let f (x) denote the true underlying probability density function for the feature distribution of agents from group g with qualification state y. The algorithm has an estimate of these unknown distributions, at each time I, based on the data collected so far (or an initial training set). Denote the algorithm's 's estimate at by fg (z). In general, there can be a mismatch between the estimates (x) and the true f' (x);; this is what we refer to as bias. We assume the following.
We use a one mie-dennniioal feature setting in our analysis, and generalize to X' C 12" in Section S Dis- cussions and numerical experiments on potential loss of information due to our feature dimension reduction technique is given in Appendix A
3

---

Assumption 1. The firm updates its estimates (x) by updating single parameter w
This type of assumption is common in the multi-armed bandit learning literature [38 (there, the algorithm aims to learn the mean arm rewards). In our setting, it holds when the assumed underlying distribution single-parameter or when only one of the parameters of multi-parameter distribution is unknown. Alternatively, it can be interpreted as identifying and correcting distribution
36
shifts by updating a reference point in the distribution (c.g., adjusting the mean) More specifically, we will let ae, be the a-th percentile of (z). We discuss potential limitations of Assumption in Appendix A and present an extension
case with two unknown parameters in Appendix !|
Under Assumption M the bias can be captured by the mismatch between the estimated and true parameters W and w. In particular, we set the mean absolute error BlJa =ill as the measure for quantifying bias, where the randomness is due to that in w the estimate of the unknown parameter based on data collected up to time
Algorithm choice without debiasing, Let ay be the fraction of group agents with label y. A boss-minimizing fair algorithm selects thresholds f, at time follows:
Σ ob 5.. Saeladd + +ag gE(a,))
( (a)((r)de s.t. C(Oa,t, 0. 00,
min 0a.
(1)
Here, the objective is the misclassification error, and C(O.. 0,) = 0 is the fairness constraint imposed by the firm, if any. For instance, C(fa,.. 0,.c) = u,, 0,. for same decision rule, or C(Oa,e, 6b.e) =
Jo.. fl (z)dx - Ie. ft,c(z)dd for equality of opportunity. Note that both the objective function
and the fairness constraint are affected by any inaccuracies in the current estimates fg. As such, biased training dataset can lead to both loss of accuracy and loss in desired fairness.
3 An Active Debiasing Algorithm with Bounded Exploration
In this section, we present the active debiasing algorithm which uses both exploitation (the decision rules of (T) and exploration (some deviations) to remove any biases from the estimates fy Although the deviations may lead to admission of some unqualified agents, they can be beneficial to the firm in the long-run: by reducing biases in f% both classification loss estimates and fairness constraint evaluations can be improved. In this section, we drop the subscripts g from the notation; when there are multiple groups, our algorithm can be applied to each group's 's estimates separately.
As noted in Section I our algorithm is of bounded exploration: it includes lower bound LB, which captures the extent to which the decision maker is willing to deviate from the current classifier O., based on its current estimate fo of the unqualified agents' underlying distribution. Formally, Definition 1. At time I, the firm selects lower bound LB, such that
LB: =
(O.)).
where Og is the (current) loss-minimizing threshold determined from Q.. EP (E are the cdf and inverse edf of the estimated distribution fe, respectively, and We is (wlog) the a-th percentile of fe-
In more detail, we choose I.B, such that (0)) - -
1o (a²)) that is, such that af is the median in the interval (LB,, 6.) based on the current estimate of the distribution F at the beginning of time t. Then, once a new batch of data is collected, we update ae 40 the realized median of the distribution between (LBr, 0,) based on the data observed during [1, l + 1). Once the underlying distribution is correctly estimated, (in expectation) we will observe the same number of samples between (L,B,, ug²) and between (wf, 02), and hence wi will no longer change. We also note that by selecting a high a-th percentile in the above definition, LB, can be increased so as to limit the depth of exploration. As shown in Thcorem B and in numerical experiments, these thresholding choice will enable debiasing of the distribution estimates while controlling its costs.
Our active debiasing algorithm is summarized below. A pseudo-code is given in Appendix C
For instance, a bank may want to adjust for increases in average credit scores 15 over time.

---

Algorithm 1 (The active debiasing algorithm), Denote the loss-minimizing decision threshold determined from ①1 by tr and let LB, be given by Definition 4 Let {a} be a sequence of exploration probubilities. At each time i, and for agents (xt y , arriving at t: Step Admit agents and collect data. Admit all agents with xt 2 0t. Additionally, if
LB, S xx < 0g, admit the agent with probability et.
Step H: Update the distribution estimates based on new data collected Step I.
Qualified agents' distribution update: Identify new data with LB, < x² and y = Use all such x¹ with LB, S. x! < O2, and such x² with 0, S x² with probability to update w/- Unqualified agents' distribution update: Identify new data with LB; S x² and y = O. Use all such x¹ with LB, I x² 6,, and such x¹ with 0 S x² with probability e, to update 40.
In more detail, our algorithm repeatedly performs the following two steps:
Step I: Data collection. At the beginning of time period loss-minimizing classifier with threshold O, (according to ( and the exploration lower bound LB, (Definition [ are selected based on the data collected so far. Then, given Oz, the new data collected during period will consist of arriving agents with features x 2 8,. Additionally, to address the censored feedback issues, with probability ç,, the algorithm will also accept agents with LB, S x 0g. Note that this step balances between exploration and exploitation through its choice of both LB, (which limit the depth of exploration) and exploration probabilities e (which limits the frequency of exploration).
Step I: Updating estimates. At the end of period I, the data collected in Step will be used to update fo and ft. Under Assumption the estimates ff are updated by updating the parameter ay. We assume, without loss of generality, that the firm sets Wy to the a-th percentile of f." This a-th percentile the reference point that will be adjusted over time as new data collected. As an example, when the reference point @ is set to the median (the 50-th percentile), the parameter can be adjusted that half the label data collected in Step will lic on each side of the reference point.
Theoretical Analysis
We begin by analyzing two baselines: exploitation-oni (which only accepts agents with x 2 Os. and uses no exploration or thresholding) and pure exploration (which accepts arriving agents at time t who have x Og with probability <t, without setting any lower bound). The motivation for the choice of these two baselines is as follows: the exploitation-one inriiinoonll onlly baseline tracks the performance of a decision maker who is unaware of underlying data biases, and makes no attempt at fixing them. The pure exploration oration baseline, on the other hand, is motivated by the Bandit learning literature, and is also akin debiasing algorithms proposed in recent work (see Section [ Related Work). We. in contrast, propose and show the benefits of bounded exploration through our active debiasing algorithm.
4.1 The exploitation-only baseline
Our first baseline algorithm only updates its estimates of the underlying distributions based on agents with x 2 6, who pass the (current) loss-mini classifier (1) The following result shows that this approach consistently suffers from adaptive sampling bias, ultimately resulting overestimation of the underlying distributions.
Theorem 1. An exp i
algorithm overestimates w i.e. lim B|aa1| > w Vy.
detailed proof is given in Appendix D
4.2 The pure exploration baseline
In this second baseline, at each time t, the algorithm may accept any agent with x < 9 with probability e,. The following result establishes that using the data collected this way, the distributions can be debiased in the long-run, if the data collected above the classifier is also sampled with probability 6 when updating the distributions.
Theorem 2. Using the pure exploration algorritii Wf + wd as 0o, Vy.
5

---

The proof follows from assuming (wlog) that the unknown parameter wt being estimated is the distribution's 's mean (can be generalized to arbitrary statisties under Assumption []. Then, as we are collecting i.i.d. samples from across the distribution, we can be set to the sample mean of the collected data, and the conclusion follows from the strong law of large numbers. Note also that if all the data above the classifier was considered when making the updates, following similar arguments to those in the proof of Theorem | the algorithm would obtain overestimates of the distributions. Lastly, we could equivalently balance data by resampling the exploration data (rather than downsampling the exploitation data), to debias data through this procedure.
4.3 The active debiasing algorithm
While pure exploration can successfully debias data in the long-run, it does so at the expense of accepting agents with any dt. Below, provide analytical support that our proposed exploration and thresholding procedure in the active debiasing algorithm can still debias data in certain distributions, while limiting the depth of exploration to LB, < x < O2.
Let for and fo denote the true feature distribution and their estimates at the beginning of time t, with respective a-th percentiles wiil and w.. Assume these are unimodal distributions, Et > O, Vt, and of S 02 S wi, Vt. Then, using the active debias ing algorithm.
Theorem 3.
(a) If If is underestinated (resp. overestimated), then E[@"-1] 2 Wy, (resp. E[ S (F) Vt, Vy.
(b) The sequence { } converges, with wil" + w as l + 0o, Vy-
We provide proof sketch for debiasing ff which highlights the main technical challenges addressed in our analysis. The detailed proof is given in Appendix E
Proof sketch: Our proof involves the analysis of statistical estimates af based on data collected from truncated distributions. In particular, by bounding exploration, our algorithm will only collect data with features x 2 LB,, and can use only this truncated data to build estimates of the unknown parameter of the distributions.
Part (a) establishes that the sequence of {a{}} } produced by our active debiasing algorithm "moves" in the right direction over time, and ultimately converges. The main challenge in this analysis is that as the exploration and update intervals [LB,,, (o) are themselves adaptive, there is no guarantee on the number of samples in each interval, and therefore we need to analyze the estimates in finite sample regimes. To proceed with the analysis, we assume the feature distribution estimates follow unimodel distributions (such as Gaussian, Beta, and the family of alpha-stable distributions) with w as reference points. We then consider the expected parameter update following the arrival of a batch of agents; Denote the current left portion in (LB,, aP) as p1 :=
f (2() (LB.) Based on Definition
(LB,)
1 we can also obtain the current portion in (4f, 02) denoted as P2 Fo(6,)- ( (1.BB)) P1. The new expected estimates B[4[-1] is the sample median in (LB,, 0e), where samples come from the true distribution. We establish that this expected update will be higher/lower than wi/ if the current estimate is an under/over estimate of the true parameter.
Then, in Part (b) we first show that the sequence of over- and under-estimation errors in {a)} relative to the true parameter w are supermartingales. By the Doobs Convergence theorem and using results from part (a), these will converge to zero mean random variables with variance going to zero as the number of samples increases. This establishes that (4i²) converges. It remains to show that this convergence point is the true parameter of the distribution. To do so, as detailed in the proof, we note that the density function of the sample median estimated on label 0 data collected in [LB,, 0:]
PP v)dv=
(2m + 1)! ( ym (0c)- (v) ym (=( FO)) (F. de
(v)
(2)
m!m!
which beta distribution pushed forward by HVv)= := truncated 1d distribution in [LB., Oz). We then establish that the convergence point will be the true median of the underlying distribution.
("() F( this is the CDF of the
4.4 Error bound analysis
Our error bound analysis compares the errors (measured as the number of wrong decisions made) of our adaptive debiasing algorithm against the errors that would be made by oracle which knows

---

the true underlying distributions. We measure the performance using 0-1 loss, E(tt, 3:k 1 * yel. where y; and yi denote the predicted and true label of agent respectively. We consider the error accumulated when updating the estimates using a total of m batches of data. We split the total T samples that have arrived during [t. + 1) into four groups, corresponding to four different distributions f Specifically, we use by to denote the number of samples from each label-group pair at round i E {O,.... m). We update the unknown distribution estimates once all batches meet size requirement 8, i.c, once min(by,) 2 Vy, Vg. The error our algorithm is given by:
Error E[EEror Adoptive
Errororacte]
62, +bb tb, tb
T
Σ
E (2..)..)))D
[(hs, (zi:
The following theorem provides an upper bound on the error incurred by active debiasing.
Theorem 4. Let fy (z) be the estimated feature- distributions at round E {0...., m]. We consider the threshold- based, group-specifee binary classifier heg.. and denote the Rademacher complexity of the classifier family H with n training samples by RR, (H). Let 4gg be a v-approximately optimal classifier based on data collected up to time t. At round f, let Ng. tt be the number of exploration errors incurred by our algorithm, Nggtt be the sample size at time t from group 9. duan((yy. Dg) be the distance between the true unbiased data distribution Dg and the current biased estimate D Dat, and el a(D Dg) be the minimum error on an algorithm trained on unbiased and biased data. Then, with probability at least 48 with ô > O, the active debiasing algorithm s error is bounded by:
Err. S
El
2
+ +1R (H) M.gt
lm(2/5)
No. + duan D,) Dc( Da) expion
Rgght
e-apprax
empirical estiaation
farger distribution milsmatch
More details on the definitions of the distance measure dHAH, and the error term c(.), and the exploration error term Ng.t, along with a a detailed proof, are given in Appendix F From the expression above, we can see that the error incurred by our algorithm consists of four types of error: errors due to approximation of the optimal (fair) classifier at each round, empirical estimation errors, exploration errors, and errors due our biased training data (viewed as source-target distribution mismatches); the latter two are specific to our active debiasing algorithm. In particular, as we collect more samples, R2,, will increase. Hence, the empirical estimation errors decrease over time. Moreover, as the mismatch between Dy and Dy decreases using our algorithm (by Theorem 3). the error due to target domain and source domain mismatches also decrease. In the meantime, exploration probability e also becomes smaller over time, decreasing Ng.
4.5 Active debiasing and fairness criteria
We next consider our proposed active debiasing algorithm when used in conjunction with demographic fairness constraints (e.g., equality of opportunity, same decision rule, and statistical parity (2)). Imposing such fairness rules will lead to changes to the selected classifiers compared to the caimess-unconstraiie decision rules obtained from (b at time t for
case, Let g.t and g.t denote the fairness constrained and unconstrained group g, respectively. We say group g is being over- selected (resp. under-selected) following the introduction fairness constraints 0"
g.t < 00 g.t (resp. oh, > (..)) Below, we show how such peer/under-selection can differently affect the debiasing of estimates on different agents.
In particular, let the speed of debiasing be the rate at which El[Ay - w0 decreases with respect to f; then, for given an algorithm for which this error is larger has slower speed of debiasing. The following proposition identifies the impacts of different fairness constraints on the speed of debiasing attained by our active debiasing algorithm. The proof is given in Appendix G
Proposition 1. Let f4 and f% be the true and estimated featurr feature distributions, with respective a-th percentiles w and WY. Assume these are unimodal distributions, and active debiasing is applied. If group g is over selected (resp. under-selected) under a fairness constraint, i.e., 05, < 8 g.t (resp.
oF. > 8%.2). the speed of debiasing on the estimates fo will decrease (resp. increase).
7

---

Proposition [ highlights the following implications of using both faimess rules and our active debiasing efforts. Some fairness constraints (such as equality of opportunity) can lead to an increase in opportunities for (here, over-selection of) agents from disadvantaged groups, while others (such as same decision rule) can lead to under-selection from that group. Proposition shows that active debiasing may in turn become faster or slower at debiasing estimates on this group.
Intuitively, over-selection provides increased opportunities agents from group (compared to an unconstrained classifier). In fact, the reduction of the decision threshold to 0% g. can itself be interpreted as introducing exploration (which is separate from that introduced by our debiasing algorithm). When a group is over-selected under fairness constraint, the threshold fy. will be lower than the unconstrained threshold 6 Therefore, the exploration range will be narower, which means by adding a fairness constraint, the algorithm needs to wait and collect more samples (takes longer time) before manages to collect sufficient data to accurately update the unknown distribution parameter, and hence, it has a slower debiasing speed. More broadly, these findings contribute to our understanding of how fairness constraints can have long-term implications beyond the commonly studied fairness-accuracy tradeoff when we consider their impacts data collection and debiasing efforts.
Numerical Experiments
In this section, we illustrate the performance of our algorithm through numerical experiments on both Gaussian and Beta distributed synthetic datasets, and on two real-world datasets: the Adult dataset [12 and the FICO credit score dataset 3 pre-processed by [6.. Additional details (ground- truth information) on the experiments, and larger versions of all figures, are available Appendix H wwom//ifaaeeviiiicmcommmmmm
Our code is available at: https:///itthb:
Throughout, we either choose a fixed schedule for reducing the exploration frequencies {Et), or reduce these adaptively as function of the estimated error. For the latter, the algorithm can select a range (e.g., above the classifier for label 0/1) and adjust the exploration frequency proportional to the discrepancy between the number of observed classification errors in this interval relative to the number expected given the distribution estimates.
Comparison with the expl welloiiaaiiononlyy and pure exploration baselines: Our first exper- iments in Fig. D compare our algorithm against two baselines. The underlying distributions are Gaussian and no fairness constraint is imposed. Our algorithm sets a² = 50 and a = 60 percentiles, and exploration frequencies e, are selected adaptively by both our algorithm and pure exploration.
Weighted Sugnet
Mean Estimaaas
Eppotser. 200
slo sato placasio Number Samples Observed
Number
olc d00 vil soop colo valn
Mitter of Samtlle (heeroed
Number of Samplcs Observed
(a) Rate of debiasing, ('(b) Rate of debiasing, fl and 1" underestimated.
(c) Regret.
(d) Weighted regret.
and f overestimated.
Figure 1: Speed of debiasing, regret, and weighted regret, of active debiasing vs. exploitation-on and pure exploration (larger figures in Appendix H).
Speed of debiasing: Figs. (a) and I(b) show that consistent with Theorem exploitation-on.. overestimates the distributions due adaptive sampling biases. Further, consistent with Theo- rem 2 pure exploration successfully debiases data. We also observe that as expected, pure exploration debiases faster than active debiasing. The difference is more pronounced in the label 0 distributions compared to label 1, where pure exploration collects more "diverse" observations than our algorithm. For this same reason, the gap between pure exploration and our algorithm larger when f is overestimated. This is because pure exploration observes samples with lower features x than active debiasiin, and can use these to reduce its estimate faster.
Regret: Figs. I(c) and I(d] compare the regret and weighted regret of the algorithms. Regret is measured as the difference between the number of FN+FP decisions of an algorithm vs the oracle
8

---

minimiznn algorithm derived on unbiased data. Formally, regret is defined as in Section weighted regret is defined similarly. but also adds a weight each FN FP decision, with the weight exponential in the distance of the feature of the admitted agent from the classifier. We observe that reploitationnonn
's regret super-linear, as not only it fails to debias, but has increasing error due to biases from overestimating On the other hand, while algorithms that explore "deeper" have lower regret (e.g. pure exploration < active debiasing with a = 50 < active debiasing with a = 60 in Figs. I(e). they have higher weighted regret (the order is reversed in Fig. [d). In other words, exploring to admit agents with low features leads to some errors, but ultimately helps reduce future mistakes, leading to sub-lineat regret. However, if the risk/cost of these wrong decisions is taken into account, the firm may be better off adopting slower, but less risky exploration thresholds (e.g. a 70).
Performance of active debiasing on Beta distributions: Fig. 2 shows that our
Alpha Estimates
Estrates
Alpha 1 Alpho_
algorithm can debias data for which the
underlying feature-label distributions fol-
low Beta distributions. We have assumed mistmach between the parameter of the true and estimated distributions, and se- lected these so that the estimated and true distributions have different relative skew- ness. This verifies that Theorem B holds for asymmetric distributions.
Alpha_1 1
Alpha_o
Number Updates
Number of Updates
Figure 2: Debiasing under Beta distributions.
Group A Label o
(eoog e saocel 2
Interplay of debiasing and fairness con-
muJ groupA, NC
mu, c_ grcupp NC
mwL._grruudd_ SD muu grrropp
straints: Fig. 3 compares the performance
muu groruup FD
of active debiasing when there are two groups of agents with underlying Gaus- sian distributions, and the algorithm is cho- sen subject to three different fairness set- tings: no fairness, equality of opportunity (EO), and the same decision rule (SD). The findings are consistent with Proposition ! For instance. SD will over-select the majority group (i.e., 0SD < 0%,)) so that, as shown in the left panel in Fig. the speed of debiasing on the estimates f²', will decrease. In contrast, an opposite effect will happen in the minority group b which is under-selected (i.e., 0 0%,)). The effects of EO can be similarly explained by noting that it under-selects the majority group and over-selects the minority group.
Sammple iiee
Samples Obwerved
(a) Advantaged label O.
(b) Disadvantaged label O.
Figure 3: Debiasing used with fairness constraints.
Active debiasing on the Adult dataset: Fig. 4 illustrates the performance of algorithm on the Adult dataset. Data is grouped based on race (White G2 and Woh-Wh Gb), with labels y = for income > $50k/ yyar.. A one-dimensional feature E TR is constructed by conducting logistic regression on four quantitative and qualitative features (education number, sex, age, workelass), based on the initial training data Using an input analyzer, we found Beta distributions as the best fit the underlying distributions. We use 2.5% of the data to obtain biased estimate of the parameter a. The remaining data arrives sequentially. We use a' 50 and a = 60 and a fixed decreasing {c),, with the equality of opportunity faimess constraint imposed throughout.
spra Entreenn groph
AMNi Aghi Rurrahh
Apha grxpp
200 con peor Samoles Observed
(a) Debiasing Ga. Adult. (b) Debiasing Go, Adult. (c) Go. augmented with (d) Debiasing FICO.
synthetic data (Adult).
Figure 4: Active debiasing the Adult and FICO datasets.
We observe that our proposed algorithm can debias estimates across groups and for both labels, but that this happens in the long-run and given access to sufficient samples. In particular, we note that
While this experiment maintains the same mapping throughout, the mapping could be periodically revised.

---

for label I agents from Go, as there are only 1080 samples in the dataset, although the bias initially decreases, the final estimate still differs from the true value. Fig. [[c] verifies that this estimate would have been debiased in the long-run, had additional samples from the underlying population become available (i.e., as more such agents arrive).
Active debiasing on the FICO dataset: Fig. also illustrates the performance of our algorithm on the FICO dataset [37 [6 and shows that successful in debiasing distribution estimates on both groups and on both labels.
6 Conclusion, Limitations, and Future Work
We proposed an active debiasing algorithm which recovers unbiased estimates of the underlying data distribution of agents interacting with it over time. We also analyzed the interplay of our proposed statistical/data debiasing effort with existing social/model debiasing efforts, shedding light on the potential alignments and conflicts between these two goals in fair algorithmic decision making. We further illustrated the performance of our proposed algorithm, and its interplay with fairness constraints, through numerical experiments both synthetic and real-world datasets.
The single-unknown parameter assumption. Our work focuses on learning of single unknown parameter (A (Assumption D. Despite the commonality of this assumption in the multi-armed bandit learning literature, also entails parametric knowledge of the underlying distribution with the other parameters such as variance or spread being known. We extend our algorithm to a Gaussian distribution with two unknown parameters in Appendix | Extensions beyond this, especially those not requiring parametric assumptions on the underlying distributions, remain a main direction of future work.
On dimeninenii features and threshold classifiers. Our analytical results have been focused on one-dimensional feature data and threshold classifiers. These assumptions may not be too restrictive in some cases: the optimality of threshold classifiers has been established in the literature by, c.g., | Thm 3.2] and (36), as long as a multi-dimensional feature can be mapped to a properly defined scalar. Moreover, the recent advances in deep learning have helped enable this possibility: one can take the last layer outputs from a deep neural network and use as the single dimensional representation. That said, any reduction of muuli-dimensiooas features to single- dinge--ammssional score may lead to some loss of information. debiasing algorithm on the Adult dataset with dimension reduction to a single-dimensional score; we find that this reduction can lead to a ~ 5% loss in performance (see Appendix for details). One potential solution to this is to adopt mapping from high-ding -igh-dimnnsional features to scores that is revised repeatedly as the algorithm collects more data. Alternatively, one may envision debiasing algorithm which targets its exploration towards collecting data on features that are believed to be highly biased; these remain as potential extensions of our algorithm.
particular, our experiments have considered the use of our active
features by first performing
Potential social impacts. More broadly, while our debiasing algorithm imposes fairness constraints on its exploitation decisions (see problem (D). it does not consider fairness constraints in its explo- ration decisions. That means that our proposed algorithm could be disproportionate in the way increases opportunities for qualified or unqualified agents in different groups during exploration. Imposing fairness rules on exploration decisions, as well as identifying algorithms that can improve the speed of debiasing of estimates underrepresented populations, can be explored to address these potential social impacts, and remain as interesting directions of future work.
Additional discussions on limitations, extensions, and social impacts, are given in Appendix A
Acknowledgments and Disclosure of Funding
We sincerely thank the three reviewers and the area chair for their comments and feedback which helped improve our paper. We are also grateful for support from the National Science Foundation (NSF) program on Fairness in AI in collaboration with Amazon under Award No. I1S-2040800, the NSF under grant 114-21,,,5 and Cisco Research. Any opinion, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF, Amazon, or Cisco.
10

---

References
[1] J. Abernethy, P. Awasthi, M. Kleindessner, J. Morgenstern, C. Russell, and Zhang. Active sampling for min-max fairess. arXiv preprint arXiv:2006.0663 2020.
[2] A. Agarwal, A. Beygelzimer. M. Dudfk, J. Langford, and H. Wallach. A reductions approach to fair classification, In International Conference Machine Learning, pages 60-69. PMIR, 2018.
[3] M.-F. Balcan, A. Broder, and T. Zhang. Margin based active learning. In International Conference on Computational Learning Theory, 2007.
[4] Y. Bechavod, Ligetl, A. Roth, B. Waggoner, and S. Z. Wu. Equal opportunity in online classification with partial feedback. In Advances in Neural Information Processing Systems, pages 8974-8984, 2019.
[5] S. Ben-David, J. Blitzer, K. Crammer, A. Kulesza, Pereira, and J. W. Vaughan. theory of learning from different domains. Machine learning, 79(1):1511175, 2010.
[6] A. Blum and K. Stangl. Recovering from biased data: Can fairness constraints improve accuracy? In Ist Symposium on Foundations of Responsible Computing (FORC 2020). Schloss Dagstuhl-Lccimiiz-ZZnrmm für Informatik, 2020.
[7] CNBC. The average U.S. FICO score is up 8 points from last year. https://wwwt http:///wwwwwccc...////oo cow/select/ saresshow--oe -hee-th-vveeegee
average american can- increased- their fico- score- last-year// 2021.
[8] S. Corvest-Davies, E. Pierson, A. Feller, S. Goel, and A. Hug, Algorithmic decision making and the cost of fairness. In Proceedings the 23rd aem sigkdd international conference on knowledge discovery and data mining, pages 797-806, 2017.
[9] M. De-Arteaga, A. Dubrawski. and A. Chouldechova. Learning under selective labels in the presence of expert consistency. arXiv preprint arXiv:1807.00900 2018.
[10] Y. Deshpande, I.. Mackey, V. Syrgkanis, and M. Taddy. Accurate inference for adaptive linear models. In International Conference on Machine Learning, pages 1203, 2018.
[11] J. Dressel and H. Farid. The accuracy, fairness, and limits of predicting recidivism. Science advances, 4(1); eaao5580, 2018.
[12] D. Dua and C. Graff. UCI machine learning repository, 2017. URL http::/arrchive.esss
[13] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel. Faimess through awareness. In Proceedings of the 3rd innovations in theoreticul computer science conference, 2012.
[14] D. Ensign, S. A. Friedler, S. Neville, C. Scheidegger, and S. Venkatasubramanian, Runaway feedback loops in predictive policing. In Conference on Fairness, Accountability and Transparency, pages 160-171. PMLR, 2018.
[15] Experian. What Is the Average Credit Score in the U.S.? https:/ www www.experian.nommmmmmmmmmmmmm..w com/blogs ask sak-experiann/hat-iiee wh-tttittttteeeeeee the- aveaa--verae---eedtttee-
in- the-u-s/ 2020.
[16] M. Hardt, E. Price, and N. Srebro. Equality of opportunity supervised learning. In Advances in neural information processing systems, pages 3315-3323, 2016.
[17] H. Jiang and Nachum. Identifying and correcting label bias machine learning. International Conference on Artificial Intelligence and Statistics, pages 702-712, 2020.
[18] N. Kallus and Zhou. Residual unfaimess in fair machine learning from prejudiced data. International Conference on Machine Learning, pages 2439 2448. PMLR, 2018.
[19] A. Kazerouni, Q. Zhao, J. Xie, S. Tata, and M. Najork. Active learning for skewed data sets. arXiv preprint arXiv:2005.1 1442, 2020.
[20] N. Kilbertus, M. G. Rodriguez, B. Schölkopf, K. Muandet, and I. Valera. Fair decisions despite imperfect predictions. In International Conference Artificial Intelligence and Statistics, pages 277-287. PMLR, 2020.
[21] T. Lai and Z. Ying. Estimating a distribution function with truncated and censored data. The Annals of Statistics, pages 417-442, 1991.
[22] H. Lakkaraju, J. Kleinberg. J. Leskovec, J. Ludwig, and Mullainathan. The selective labels problem: Evaluating algorithmic predictions in the presence of unobservables. In Proceedings of the 23rd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pages 275 284, 2017.
11

---

[23] A. Lambrecht and C. Tucker. Algorithmic bias? an empirical study of apparent gender-based discrimination in the display of stem career ads. Management Science, 65(7):2966-291, 2019.
[24] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[25] Y. Liao and P. Naghizadeh. Social bias meets data bias: The impacts of labeling and measurement errors on fairness criteria. arXiv preprint arXiv:2206.00 00137, 2022.
[26] L. T. Liu, S. Dean, E. Rolf, M. Simchowitz, and M. Hardt. Delayed impact of fair machine learning. In International Conference Machine Learning, pages 3150 3158. PMLR, 2018.
[27] L. T. Liu, A. Wilson, N. Haghtalab, A. Kalai, C. Borgs, and J. Chayes. The disparate equilibria of algorithmic decision making when individuals invest rationally. In Proceedings of the 2020 Conference on Faimess, Accountability, and Transparency, 2020.
[28] Maritz and R. Jarrett. A note on estimating the variance the sample median, Journal of the American Statistical Association, (3(361):194-199)) 1978.
[29] N. Mchrabi, Morstatter, N. Saxena, Lerman, and Galstyan. survey on bias and fairness in machine learning. arXiv preprint arXiv: 09635, 2019.
[30] S. Neel and A. Roth. Mitigating bias in adaptive data gathering via differential privacy. In International Conference on Machine Learning, pages 3720-3729. PMLR, 2018.
[31] X. Nie, X. Tian, J. Taylor, and J. Zou. Why adaptively collected data have negative bias and how to correct for it. In International Conference on Artificial Intelligence and Statistics, pages 1261-1269, 2018.
[32] A. Sariega-Campero, M. A. Bakker, B. Garcia-Bulle and A. Pentland. Active fairness algorithmic decision making. In Proceedings of the 2019 AAAI/ACM Conference on AI, Fthics, and Society, pages 77-83. 2019.
[33] Z. Obermeyer, B. Powers, C. Vogeli, and Mullainathan. Dissecting racial bias an algorithm used to manage the health of populations. Science, 36666464):447-453, 2019.
[34] V. Patil, G. Ghalme, V. Nair, and Y. Narahari. Achieving faimess in the stochastic multi-armed bandit problem. J. Mach. Learn, Res., 22: 12-11,11222 2021.
[35] J. Perdomo, T. Zanic C. Mendler-Dünnee and M. Hardt. Performative prediction. In International Conference Machine Learning, pages 7599-7609) PMLR, 2020.
[36] R. Raab and Y. Liu, Unintended selection: Persistent qualification rate disparitics and interventions. Advances in Neural Information Processing Systems, 34:26053 26065, 2021.
[37] Reserve. Report to the congress on credit scoring and effects on availability afford- ability of credit. https://ww...eeeeeerrrreeeeeeeee creditacore, pdf 2007.
[38] C. Schumann, 7. Lang, N. Mattei, and J. Dickerson. Group fairness in bandit arm selection. arXiv preprint A9/i: 0338000 2019.
[39] A. Slivkins. Introduction to multi-armed bandits. arXiv preprint arXiv: 194.0777,, 2019.
[40] Wang, Y. Liu, and C. Levy. Fair classification with group-dependent label noise. In Proceedings of the
2021 ACM conference on fairness, accountability, and transparency, pages 526-536, 2021.
[41] D. Wei. Decision- makinn under selective labels: Optimal finite-domain policies and beyond. Interna- tional Conference on Machine Learning, pages 11035- 1046. PMLR, 2021.
[42] X. Zhang, M. Khaliligarekani, C. Tekii, and M. Liu. Group retention when using machine learning in sequential decision making: the interplay between user dynamics and faimess. In Advances Neural Information Processing Systems, pages 15269-15278, 2019.
[43] 7. Zhu, T. Luo, and Y. Liu. The rich get richer: Disparate impact of semi-supervised learning. In International Conference Learning Representations, 2021.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Have you read the ethics review guidelines and ensured that your paper conforms to
them? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Fairness
implications of our algorithm are discussed Section 4.5 A limitation of our algorithm
for groups with smaller representation are discussed at the end of Section 5 See also Appendix
A for more discussion.
(d) Did you describe the limitations of your work? [Yes] See the remark in Section 3 and
the paragraph before the proof of Theorem 3 in Section 4 and Appendix A
2. If you including theoretical results....
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
(b) Did you include complete proofs of all theoretical results? [Yes] See Section 4 for the main proofs, and additional proofs the supplementary material, Appendix and G
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as URL)? [Yes] Code is included in the supplementary material. Dataset used are the Adult dataset, publicly available from the UCI machine learning repository [[2], and the FICO credit score
dataset [37 pre- preeprocessed by [16]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section for details.
(c) Did you report error bars (e.g., with respect the random seed after rumning ex- periments multiple times)? [Yes] See Figure 2 details
Adult Dataset, T2(a) 12(b) for
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A] All experiments were local computer.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]] See Section
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as URL? [Yes] Our algorithm's 's code is available in the supplementary material. No new data was curated or generated.
(d) Did you discuss whether and how consent was obtained from people whose data you're 'r using/curating? [N/A] We use the publicly available Adult dataset from the UCI machine learning repository [12], for which data was extracted from a 1994 Census
database; and the FICO credit score dataset 3 pre-processed by [6]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A] We use the publicly available Adult dataset from the UCI machine learning repository [ for which data extracted from 1994 Census database; and the FICO credit score dataset 37 pre-processed by [16]. They do not contain PII or offensive content.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "mbnPRwN00w", "reviewer": "Reviewer_ESAg", "summary": "The paper presents a method for \"data debiasing\" in a sequential-data setting with one feature (analysis extended to two in supplement). The algorithm conducts a form of bounded-random exploration in this one-dimensional setting, and can be used to perform learning under fairness constraints. The authors provide a theoretical analysis of the proposed algorithm, demonstrating convergence and analyzing the regret bound. The paper includes experiments on a simluated datasets and versions of two fairness datasets.\n\nOverall, the paper is mostly well-written and notation clear (with some exceptions, noted below). I have three main concerns about the paper. The first is about the practical significance of the problem: this seems to be of limited real-world significance, and the authors do not identify a meaningful application where such a model and the described setting hold. Second, I have some concerns with the presentation of the work as \"data debiasing\", as their work is really about model debiasing in an active-sampling setting. Third, I find the real-world experiments somewhat unconvincing (see below).\n\n## After response\n\nSee comments below.", "questions": "See above.", "limitations": "See above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "#### Major Comments\n\n* This work strikes me as inappropriately framed, in two ways. First, it seems to be about *model* debiasing, not data debiasing. For example, the authors' own definition of bias is a property of the model, not of the data (cf. L43-49; L125-129). Second, this definition of \"bias\" seems wholly unrelated to any fairness concerns and is effectively a measure of model error. The work would make sense as a fairness work if their measure of bias was, for example, related to disparities in this error over subgroups, but as-is, the proposed algorithm seems to simply be a one-dimensional active-learning method that could incorporate fairness (or any other) constraints.\n\n* The entirety of the main text focuses on the case of one-dimensional data (with a reference to 2-D case in supplement). If this is the case, the proposed method seems to be of limited usefulness in most real-world classification scenarios, where many features are typically available. The authors' own somewhat contrived experiments on \"real-world\" datasets (Adult, FICO) which reduce these datasets to a single feature in order to apply their proposed method, seem to demonstrate the limited real-world usefulness. I understand that this may be an interesting theoretical case for the bandit literature, but the authors' claim to solve a meaningful fairness problem is hard to take at face value without any clear examples of such a scenario emerging in the real world.\n\n* The real-world data experiments, in particular, are weak. The authors do not provide the ground-truth values in Fig. 4a/4b/4c/4d; only one panel compares the proposed method to baselines; and the synthetic data augmentation in 4(c) seems ad hoc and is not described. Most concerning, however, is the authors' distilling these richly-featured tabular datasets into a single feature for the purposes of their experiments, which amounts to discarding information in order to shoehorn in the proposed method. This is effectively ignoring hundreds of published results on these datasets in the fairness literature, which would perhaps be an appropriate baseline. The results are also missing any notion of classification error or loss, if I understand them correctly.\n\n#### Minor Comments\n\n* L131 \"This type of assumption is common in the literature\" - please provide relevant citations.\n\n* Definition 1 could use more unpacking; some of the properties described as \"intuitive\" or otherwise are not immediately clear to me. A clearer description of the properties of LB_t would clarify the work considerably.\n\n* The intuition in L304-312 is not clear; in particular the sentence in L306-L309 could use more unpacking. It currently reads, paradoxically, as \"an increase in exploration makes the model more conservative at exploration\".\n\n#### Typos etc. \n\n\n* I am confused why there is no \"hat\" on \\theta, as there is on \\omega. Isn't it the case that there exists a true \\theta_a, \\theta_b, which we are estimating via \\hat{\\theta}_a, \\hat{\\theta}_b, respectively?\n\n* L154: in my opinion it would be clearer to retain the g subscript in the following analysis.\n\n* \"lowerbound\" --> lower bound\n\n* L178: \"update the estimates to f...\" --> update f\n\n* L179: \\theta_t^y is not an \"unknown\" parameter if we are updating it.\n\n* L213: \"overestiamted\"", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OEgGmfg5xOk", "reviewer": "Reviewer_Hsp8", "summary": "The work studies the problem of collecting new data to learn outcome distribution of sensitive groups. It analyses three schemes of data collection — (exploitation only) one in which decisions to give a positive decision to individuals are solely based on current classifier, and (exploration only and active debiasing) other two where the individuals who would not have been given a positive decision are given so randomly with or without some constraints. Theoretical analysing the cases of unimodal and univariate distributions, the work shows that the latter two schemes estimate the outcome distributions correctly. It also proves bounded regret in making correct decisions for the active debasing scheme. These observations are verified in experiments on two real datasets.", "questions": "Please address the following five points in the response.\n\n1. Assumption 1 is not clear mainly because the parameter \\omega is not explained. Similarly Definition 1 is introduced without giving the context for the formula in line 159-161.\n\n2. Clarify whether the analysis is restricted to single dimensional data and threshold classifiers. Extensions to multiple dimensions is not discussed.\n\n3. Clarify the term speed of debiasing in Proposition 1. The statement and the proof are not precise.\n\n4. Related work can be made more comprehensive by discussing important papers on the three relevant parts of the problem - selective labelling, fair learning from imperfect data, and active learning of fair models. For example, see Lakkaraju et al. 2017\n(https://dl.acm.org/doi/10.1145/3097983.3098066) and De-Arteaga et al. 2018 (https://arxiv.org/abs/1807.00905) for selective labeling, and Blum and Stangl 2019 (https://arxiv.org/abs/1912.01094) and Kallus and Zhou 2018 (https://arxiv.org/abs/1806.02887) for fairness learning from imperfect data. For active debiasing please see Abernethy et al. 2020 (https://arxiv.org/abs/2006.06879) and Noriega-Campero et al. 2019 (https://dl.acm.org/doi/10.1145/3306618.3314277).\n\n5. For the first four results the problem seems to be more related to online mean estimation than fair learning — how to learn two parameters (which are means of some distribution) online with the difference being the constraint of bounded exploration. The final result Proposition 1 is interesting in terms of interplay between online data collection and putting fairness constraints. Because of this, I would suggest discussing differences from the related work on online mean estimation. Please motivate the unique aspects of the problem setting like how the bounded exploration makes the problem and the analysis harder.\n\n\nMinor (no response is requested for these)\n\nThe presentation of the problem can be improved in the Introduction. It is a bit stylistic preference, but I would suggest adding a discussion of what has been done in the past work in Introduction itself and pointing out the shortcomings and improvements by the current work.\nMore importantly, the idea of bias in data is not clear. Does this refer to the training data being censored i.e. labels are available only for individuals with positive predictions? Or, the idea is more general? Lines 47-49 can be made more precise. For example, clarify if the mismatch between estimated and true label distribution refer to estimation error i.e. mismatch due to finite samples or the estimate is biased.\n\nPlease clarify whether the analysis depends on the form of the loss-miniminizing fair algorithm in Eq. (1). Does it matter if it is solved when the fairness constraints are defined with some slack (i.e. the difference need not be exactly zero) as done in many fair learning algorithms? Can the constraints be defined for differences in positive predictions (instead of the differences in thresholds) between the groups?\n\nDefine or provide a reference for alpha-stable distributions\n\nunimodel -> unimodal\n\nAdd a conclusion section", "limitations": "Limitations of the work are not discussed in the main paper. Please discuss the limitations of the analysis for unimodal distributions and of the method in ignoring the feature information in data collection. Please discuss related work and use it to motivate the uniqueness of the problem setup. Some of the discussion from Appendix A can be moved to the main paper. Potential negative impacts are discussed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- interesting and overlooked problem of how new data collection impacts fairness guarantees\n- theoretical analysis poses reasonable questions on learnability in this setting and finds intuitive answers\n- generally well written paper\n\nWeaknesses\n- some terms are not made precise like bias or debiasing\n- most relevant work are not discussed in the main paper or Appendix\n- limitations of the assumptions like unimodal distributions and of the method like not looking at the features are not discussed\n\nOverall I like the research direction of studying the interplay between data collection and fairness when starting from imperfect data. Proposition 1 is a good step towards understanding this interplay. \n\n\n---\n## After the response\n\nThe response addresses my queries adequately. Hence I have updated my score to 7, Accept. The paper explores interesting ideas on controlled data collection to correct biased estimates and the effect of putting fairness constraints during collection. There are limitations like the restriction to single dimensional data. Overall, the work makes a good contribution.\n\nI appreciate the thorough review of related work in the response. Please include the discussion into the main paper differentiating the problem setting and analysis from past work. Clarity of presentation needs to be improved as noted by the other reviewers including clarifying the problem and notation. I would suggest addressing the restriction to single-dimensional data by pointing to ways in which the insights can be transferred to the multi-dimensional case. It is unreasonable to expect that dimension reduction would be as lossless as shown in the Adult Income experiment (also, I could find the exact procedure used for dimension reduction, so the result is a bit surprising if it is completely unsupervised).", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IG3Te1dLQkh", "reviewer": "Reviewer_e1EM", "summary": "The paper considers an algorithm to debias datasets through adaptive and bounded exploration for classification. In particular, the bias in the data is defined as inaccuracy in the estimation of a univariate distribution (assumed known to be fit). Their algorithm works by adaptively picking a lower bound corresponding to a function of the percentile of the estimated univariate distribution (with current parameters). Then given a decision threshold classification algorithm, a threshold is fitted to determine if samples / agents are accepted, where violation of the threshold can occur wrt to the lower bound calculated (with low probability). Data is then selected for: (1) retraining the classifier; and (2) updating the parameters of the distribution.The paper presents properties of a purely exploitation and purely exploitation algorithms, and further shows that their algorithm has a favorable properties in a mix. This leads to convergence of estimated parameters. Regret analysis is done on the classifiers learnt; and the analysis of how a fairness constraint can effect the speed of convergence is done. Experiments are presented over synthetic and real world datasets.\n\n---\n\n*Update*\n\nI have updated my score to a 7. Similar to other reviewers, I would also highlight that additional clarity in the paper would improve the paper greatly.\n\nOne specific point on this is to make the types of fairness less ambiguous. In the discussion and in the author responses, language has been used for different types of fairness which is confusing. There are two (broad) types of (un)fairness being highlighted: (1) from data; versus (2) from prediction. The authors are focusing on the former. However, the language used to describe both is confusing. For instance, when describing prediction fairness, terms like \"social bias/model bias/unfairness\" are used, but data fairness is also \"social\" and \"unfairness\" is too broad of a term. In my opinion, this should simply be stated as \"prediction fairness\" or something similar. On the other hand, data fairness is labelled \"statistical bias/data bias\". Here, the \"statistical bias\" term could refer to predictive fairness as constraints for this are \"statistical\" in nature. Simply put, the language here needs to be made specific, especially so in fairness where there are many \"flavors\".", "questions": "Questions / Comments / Suggestions\n1. Algorithm 1 is not especially clear in the psuedo-code (/ main-text description). In particular, it is unclear that \"new data\" is used to retrain the classifier (which I believe is the case from what I have seen via code / appendix). Furthermore, even in the appendix, algorithm 1, it does not specify what data the retraining is being done with. Also it seems to be incorrect? The way it is currently written seems to suggest that it should be looping over $ t < T $ (alongside the currently loop(?) over samples / batches).\n2. In the main-text / proofs / definitions, \"wlog\" statements are given for what the parameters are specified as (mean, percentile). Following the logic of the paper it appears that if we can prove, \\ie, Theorem 2, for a single type of statistic(?) of the distributions, then it will work for any arbitrary statistic / parameter. If true, I assume this is from assumption 1? It would help to clarify this step.\n3. Furthermore, with this assumption, it appears that the exploration and exploitation baselines also depend on how the parameters are specified. This is not clear. In particular, Theorem 1 & 2 are wrt the distribution parameters. In Theorem 2 the mean is specified, but what about Theorem 1? Is it the median as discussed on line 181?\n4. Theorem 4, the regret bound, has many undefined symbols in the main-text. \n5. The figures in the main-text are confusing. They state some algorithms \"successfully debiases data\". However, from the information given in the main-text, there is no way to verify the claim. For instance, for Fig 1, (a) + (b), how can we tell that the mean estimate is correct, when we don't know the true value? The corresponding figures in the appendix does have this information in their title.\n6. Statistical data bias being specified as the error in parameters is confusing. I initially though this criteria such as the statistical parity or representation rate of the data.\n\nMinor\n  - Line 213 \"overestiamted\"\n  - Appendix Algorithm 1 does not initialize $t$", "limitations": "The primary limitations are stated.", "rating": 7, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n  - Experiments show recovery of shifted parameters.\n  - Theoretic results provide convergence and regret analysis.\n\nWeaknesses\n  - Writing can be improved. There are aspects of the paper which are very unclear. (enumerated below).\n  - Figures in the main text are confusing / missing information.\n  - Algorithm / Pseudo-code are not clear.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept