Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: ### Summary

This paper analyzes the bias of models in pool-based active learning settings where the sampling procedure is probabilistic (non-deterministic). It proposes two unbiased estimators of the population risk that weight the loss for each sampled data point. Empirical experiments demonstrate that these unbiased estimators work well for active learning settings with under-parameterized models, but are less effective for over-parameterized models. For the latter case, the authors provide meaningful insights into why biased estimators of population risk may actually be beneficial for over-parameterized models.

### Reasons for score

**Strong points**

1. The authors identify a common problem in active learning, namely the problem of non-IID data. The authors also propose theoretically-sound solutions to addressing the active learning bias.

2. The authors experientally demonstrate their estimators in both linear regression and a deep learning experiment, showing how their estimators are beneficial in one case but not the other.

3. The paper explains why the proposed estimators may have lower variance than the standard estimator for population risk.

**Room for improvement and/or more clarity**

1. The paper mentions the "quality" of the "acquisition proposal" several times (e.g., p.4, p.6, Figure 2, etc.). However, it is unclear what is meant by "quality." What makes for a "good" acquisition proposal?

2. The paper only discusses the setting where the active learning sampling procedure is probabilistic (non-deterministic), with non-zero support over all remaining data points in the pool. However, many active learning procedures proposed in the literature are deterministic (e.g., choosing the K examples with highest loss, or the greedy core-set approach proposed by Sener & Savarese (2018)). Could the authors provide more context for bias in these deterministic active learning strategies?
3. While I did not spend time reading the appendix in detail, it seems that points for the BNN were selected under $\tilde{R}$ (the biased sub-sample empirical risk). How do the results compare if the points were selected under $R_{SURE}$, which is a more relevant setting given that $R_{SURE}$ is the proposed estimator?
4. Other than running active learning twice (once using $\tilde{R}$ and once using $R_{SURE}$), are there methods to determine when one would be preferred over the other, especially in deep learning settings?


### Minor comments /  typos / formatting concerns

(these did not affect my score)

1. Please use vector graphics for figures. For example, save the figures as SVG or PDF files (instead of JPG or PNG) and then include them in the LaTeX file. In particular, the legend in Figure 2a is difficult to read.

2. Figure 2: Does "shading is one standard deviation" mean +/- 1 std (for a total of 2 std), or +/- 0.5 std (for a total of 1 std)? Please clarify.

3. In Equation (5), why not factor out the $1/N$ in front of the summation?

4. The authors write,
> "Using our corrective weights recovers the ideal line." (p.6)

    Unless I am reading the graph wrong, this sentence is slightly misleading. It seems like the linear regression model trained using the corrective weights much more closely approximates the ideal line, but doesn't recover the ideal line exactly.

5. In general, the paper is written in an "opinionated" or imprecise manner which detracts from the main points of the paper. Words like "surprising" and "greatly" are unnecessary. Phrases such as "better variance" should be replaced with more precise terminology, such as "lower variance".

review_title: Informative Analysis of Bias in Active Learning

final_score: rating: 7: Good paper, accept
review_content: The motivation of the paper is well done and it is written clearly as well as well organized although could be improved for the sake of more clarity and precision. 

This kind of analysis is important to understand the successes/failures of active learning strategies commonly used in ML and grounding the analysis in bias-variance trade-off is a very useful start. 

I have a couple of clarifying questions that I hope the authors can elaborate on. My main suggestion would be to have an even more explicit discussion (in a separate subsection) on connections to the loss + different acquisition/active learning strategies. 

In the analysis of Thm 5, I don't understand what the authors mean by "when things are working well", the expected variance should be low for term 2. 

The analysis in Section 7 and connections to fitting model parameters vs acquistion strategies is also unclear. What exactly is the choice of R_X when the acquisition strategy minimizes $R_{PURE}$ or $R_{SURE}$? Rather why should optimization itself not use these estimators (maybe some thing else other than $\hat{R}$ to update model parameters? 

I think elaborating these will help readers separate the effects of i) acquisition strategies, ii) updating parameters and ii) choice of risk estimators to be used in both cases. All these moving parts are meshed together in between focusing on proofs. I think if the authors could elaborate on how these play together in a more prescriptive manner, it will help the manuscript.

In the discussion, the authors talk about active model selection. What is active model selection and can authors elaborate what they mean the proposed estimators are useful in this setting? 






review_title: This work analyzes bias-variance of estimators commonly used for active learning. I think the analyses and particularly the connections drawn between overfitting bias vs bias induced by the active learning strategies themselves is a very interesting analysis. Other than a few clarification questions I have, which I outline below, I think this paper is a useful contribution to the ICLR and ML community.

final_score: rating: 4: Ok but not good enough - rejection
review_content: **Summary**: 
The authors consider the bias (in the risk) introduced by active sampling strategies with respect to the true underlying data generating distribution. They then propose two estimators of the risk -- SURE and PURE -- that are unbiased and asymptotically consistent under certain assumptions. The authors consider two toy examples where they show the existence of active learning bias, and the effect of removing this. In particular, the authors notice that while training a linear regression (based on actively acquired datapoints) with their unbiased risks improves test loss, the opposite happens for a Bayesian Neural Network (BNN). They then provide a potential explanation for this phenomenon. 

**+ves**: 
+ The risk estimator proposals make sense, and their motivation is clear. 
+ The calculations (and the proofs) are presented very clearly; the overall writing quality and the story arc of the paper is very clear

**Concerns** 
- The condition that the proposal distribution needs a non-trivial weight on the entire pool of data seems too strong. Intuitively, if there are irrelevant parts of the distribution (say, far away from the decision boundary), a proposal distribution that doesn't focus there shouldn't introduce too much bias. It would have been nice to see a more nuanced version of this analysis. 
- In fact, the variance depends on this weight (as $1/\beta^2$). This could imply an extremely large variance in several reasonable scenarios, and hence affect the performance of any active learning algorithm. 
- The authors address the above concern by claiming that this paper is only about the "statistical bias" of active learning. I find this unsatisfactory since without the aspect of downstream learning, this is simply an estimation of an expectation with samples from a mismatched distribution. 
- The experimental section could have used significant strengthening. Especially given the difficulty of making theoretical claims about generalization, it would have been useful to see more experiments that shed light on how a learning algorithm that adaptively selects data can benefit from the proposal of this paper. 
review_title: Interesting take on estimating expected risk from adaptively acquired data, but deficient in theory and experiments

final_score: rating: 7: Good paper, accept
review_content: **The changes of the review after rebuttal are  indicated in bold text.**

### Summary
The paper discusses the issue of bias in active learning, the problem of actively selecting new training points to label when the labelling task is expensive. 
Because of the labelling cost, we wish to select only the most informative points, which are not representative of the full dataset, hence incurring a statistical bias. 
The classical estimator of the risk is the unweighted average loss, which carries the bias of the active training set.
The authors propose 2 unbiased estimators of the risk, named $R_{PURE}$ and $R_{SURE}$, in order to treat the statistical bias.
Although both unbiased, they differ in the ponderation on the loss for each active sample and do not have the same variance. 
While $R_{PURE}$ depends on the order in which the observations are actively chosen, $R_{SURE}$ removes this dependency. 
Both estimators are tested and compared with the classical biased risk estimator in two settings: a linear model applied on a toy dataset, 
and a Bayesian convolutional neural network (BNN) applied on a modified version of MNIST putting the data in more difficult setting.
The authors show that both their estimators behave much better than the standard one in the linear case, while they are very similar albeit a little worse in the MNIST problem.
They finish the paper by explaining that unbiased estimators of the risk are better for low parametrized models, such as the linear one, which are very dependent of the statistical bias;
while they decrease a bit the performances of an over-parametrized estimator, such as the BNN, for which the statistical bias seems to be cancelled out with the overfitting bias.

### Strengths
The paper is well written and clear. It addresses the interesting problem of active learning, and it is very insightful of the particular issue of bias in that context.
Each expression is explained with the meaning of its components, and the authors attempt to provide insight to both the positive and negative results.
It is very refreshing to see negative results, showing clearly the limitations of the proposed estimators, and to have a clear suggestion from the authors as to when to use which estimator (theirs or the biased one).
The math seems correct, although I have not checked all the proofs. 

### Weaknesses and concerns
1. Proofs
The explanations often rely more on intuition than on mathematical proof. While they may be true, it seems to me that it lacks a bit of theoretical grounding.
**After discussion with the authors, it turns out that this comment was not clear enough. It concerned only the paragraphs after Theorems 3 and 5. I apreciate greatly that the authors made an effort to clarify these paragraphs.**

2. Experiment
    a. Limitations
The experimental study is limited: the estimators have been applied only on two extreme models (a linear model and a BNN), and for each case, only one dataset has been tested. While both are very much used in practice, it is not enough to draw conclusions. There should at least be an emphasis of that, saying that it is only a preliminary, and that more tests will be performed in a more extensive version of the work. Has it been tested on more models (e.g. random forests) or on various architectures of neural networks, as well as on several datasets?
As for the choice of the proposal distribution, it seems only one was tested in the linear setting, while a range of them were tested for the BNN. This should be more explicit in the main article, referring to the appendix for more details.
    b. Reproducibility and relevance of the experiment
There are issues on the toy example:
      * it is a highly nonlinear dataset on which a linear model is trained, which is weird: what happens when using the proposed estimators to train a linear model on (close to) linear data?
      * the density function on which $X$ is drawn does not seem to sum to 1.
      * there seems to be an issue in the generation of $y$ (Eq. 124), as there no bias added, yet Figure 1 shows an oscillation for $y$ between 1 and 2.5 and $x$ in $[1, 1.5]$, while I found an oscillation around 0 by applying the formula as specified

  In the modified MNIST dataset:
      - it seems to me that the proportion of each class used for the pool subset makes this particular dataset somewhat easier rather than harder, as it basically removes the ambiguity between numbers that look alike; for instance, there are very few observations of 9, and a few of 6, and there are 5 times less 7 than 1; in such a case, the accuracy is not a good measure of the quality, as it will be good even if the smaller classes are poorly classified. 
      - Has there been a test on a balanced subset?

**In the revision, the authors added a few experiments to complete the first ones, namely adding a third dataset (Fashion MNIST), testing a balanced subset for MNIST, and testing another acquisition function to see its impact on the results. I think this gives more grounding to the nice theoretical results and insights.**

3. Active sampling for test
The authors claim that their estimators should have a positive impact on the actively selecting samples at test time. This claim appears in the introduction and in the conclusion, but it seems more like intuition and there is no explanation as to why this may be true. 
I suggest removing it from the introduction, as it is clearly future work, and if possible add some explanation behind the intuition.

### Minor comments:
- Please put equation numbers only on equations you refer to, not on all equations. 
- The name $R_{SURE}$ can be confused with Stein's Unbiased Risk Estimator (even though I assume it is so as a reference to that estimator).
- In Section 6, the acronym BALD is not defined
- In Figure 4a, the colors and order in the legend are reversed for $R_{PURE}$ and $R_{SURE}$

### Overall evaluation 
I believe this is very promising and insightful work, tackling the important issue of bias. 
However, I cannot give it a high score due to the issues I raised about the experiment.

**The revision answered my concerns about the experiment by enlarging it, which is why I upgrade the score I gave. I think it is a very good and interesting paper.**

review_title: Insightful paper, but with limited experiments 

Meta-review: This is an excellent paper that provides analytical and empirical insights on the sample selection bias of pool-based active learning. It provides two very practical methods of removing the bias.  Also, it shows that in over-parameterized networks (like modern neural networks), the active learning bias could actually be useful.   I enjoyed reading the paper.  Reviewers are mostly very positive about the paper.  Experiments in the initial version were limited, and the authors have since added more experiments.   With the increasing interest on learning with limited data, this paper is very timely and useful.  I expect the paper to be of interest to many in the community.
Decision: Accept (Spotlight)