Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths
- interesting and overlooked problem of how new data collection impacts fairness guarantees
- theoretical analysis poses reasonable questions on learnability in this setting and finds intuitive answers
- generally well written paper

Weaknesses
- some terms are not made precise like bias or debiasing
- most relevant work are not discussed in the main paper or Appendix
- limitations of the assumptions like unimodal distributions and of the method like not looking at the features are not discussed

Overall 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. 


---
## After the response

The 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.

I 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).
questions: Please address the following five points in the response.

1. 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.

2. Clarify whether the analysis is restricted to single dimensional data and threshold classifiers. Extensions to multiple dimensions is not discussed.

3. Clarify the term speed of debiasing in Proposition 1. The statement and the proof are not precise.

4. 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
(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).

5. 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.


Minor (no response is requested for these)

The 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.
More 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.

Please 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?

Define or provide a reference for alpha-stable distributions

unimodel -> unimodal

Add 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

Overall, 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).

## After response

See comments below.
strengths_and_weaknesses: #### Major Comments

* 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.

* 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.

* 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.

#### Minor Comments

* L131 "This type of assumption is common in the literature" - please provide relevant citations.

* 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.

* 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".

#### Typos etc. 


* 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?

* L154: in my opinion it would be clearer to retain the g subscript in the following analysis.

* "lowerbound" --> lower bound

* L178: "update the estimates to f..." --> update f

* L179: \theta_t^y is not an "unknown" parameter if we are updating it.

* L213: "overestiamted"
questions: See above.
limitations: See above.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

---

*Update*

I 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.

One 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".
strengths_and_weaknesses: Strength
  - Experiments show recovery of shifted parameters.
  - Theoretic results provide convergence and regret analysis.

Weaknesses
  - Writing can be improved. There are aspects of the paper which are very unclear. (enumerated below).
  - Figures in the main text are confusing / missing information.
  - Algorithm / Pseudo-code are not clear.
questions: Questions / Comments / Suggestions
1. 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).
2. 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.
3. 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?
4. Theorem 4, the regret bound, has many undefined symbols in the main-text. 
5. 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.
6. 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.

Minor
  - Line 213 "overestiamted"
  - Appendix Algorithm 1 does not initialize $t$
limitations: The primary limitations are stated.
review_title: null

Meta-review: metareview: This paper has seen a lot of discussion between reviewers and authors. Reviewers are fairly positive after the discussion/rebuttal phase and there have been significant score revisions upwards.

Few concerns that were highlighted during rebuttal/discussion phase are:
  1) Multiple reviewers have pointed out that amongst two sources of bias - data bias and model bias - the authors focus on assembling a dataset to avoid the first type of bias. It has been pointed out using terms like "social bias, unfairness" and "statistical bias" are very misleading . I strongly suggest the authors to better revise the paper according to reviewer comments using more precise terminology -data bias and/or model bias. Clarity has been a concern uniformly shared amongst all reviewers.

2) The authors principally reduce the data to a single dimension using dimension reduction techniques and use thresholded classifier. Authors responded to this concern saying -effective feature learning in general amounts to that and there are optimal data dimension reduction techniques. Further authors also experimentally demonstrate that losses in accuracy is not much due to these techniques. 

In summary, concerns 1 and 2 are not severe enough (as acknowledged by reviewers raising scores) but important to keep in mind while preparing the camera ready.
confidence: Certain
Decision: Accept