Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The manuscript follows an intuitively straightforward conclusion: data should focus on the region where the function to learning is steeper. Based on that, a non-trivial method is proposed to improve the performance of NN. Empirical results are provided to support the performance of the proposed method.

According to my understanding, the performance gain from the proposed sampling method mainly comes from the sample complexity part, or in other words, the variance part. Is this correct? The weight approximation method proposed method relies on the derivative of the estimated NN. Will this cause much randomness or error to the approximated weights, since making sure the derivative of the estimation is accurate is more challenging than making the estimation itself is accurate? 

Since provided analysis is mostly on the asymptotic level, it is quite unclear that how much noise/error the proposed sampling method may have, how much these noise will hurt the final NN estimation. So, is there any cases where the proposed sampling method will even hurt the performance of the NN? (For example, what will happen if the weights are poorly approximated?) If not, what are the key conditions to make sure that the sampling method really provides significant performance gains? 

Also, can we iteratively implement the weight approximation and sampling method many times in Algorithm 1? If the proposed sampling method really helps the performance, we can have more accurate weight approximations, and further improve the performance....

In all, the method is interesting with improved performance supported by experiments. However, I believe more analysis on the constraints and potential error of the method will benefit the manuscript. 

  


 
review_title: Intuitive but nontrivial method supported by experiments

final_score: rating: 6: Marginally above acceptance threshold
review_content: A method for computing sample learning weights based on variance is proposed. The method is model independent and a simple k-NN based estimator for the weights is derived. The authors justify their work by appealing to a novel generalisation bound. Overall the idea is interesting but the exposition needs to be significantly improved as proofs are difficult to follow as it currently stands.

# positives

- The idea is interesting and intuitive: essentially concentrate more weight on points that are ambiguous and less on points that are easily learnt
- The approach is potentially quite general covering a large range of learning tasks, though this needs to be carefully evaluated

# cons

- The exposition is very unclear, there are numerous typos and lack of detail in key sections of the proofs
- Though the authors make statements that the method is very general, the empirical evaluation does not validate this. There is no attempt to apply their method to anything other than a NN. Furthermore, many tasks cited by the authors (e.g., class imbalance & noisy labels in the intro) are implied to be covered by this framework, yet are not evaluated. It's difficult to see how this weighting strategy will improve the noisy label scenario in particular.
- The benchmark in experiments is an unweighted NN. While this is a good benchmark, it would be good to see some alternative sample weighting methods since according to the authors "Sample weighting has already been explored in many works and for various goals."

# some examples of confusing sections

- figure 1 lacks axis labels, and panel labels. It takes far too long to read as a result
- page 16: each line states (Jx(theta) <= ...) even though equality holds between the steps. This makes it difficult to see where bounds have been used. Most of this section is simple algebra and could be shortened.
- page 17: The section invoking Hornik's theorem is unclear and need to be expanded with more detail. 

# update

The authors have addressed a number of issues and strengthened their submission.
review_title: Variance based sample weighting

final_score: rating: 3: Clear rejection
review_content: **Summary of paper**

The authors introduce an algorithm called VBSW to re-weight a training data set in order to improve generalization. In summary, VBSW sets the weight of each example to be the sample variance of the labels of its k nearest neighbors. The nearest neighbors are chosen in the embedding space from the second-to-last layer of a pre-trained neural network. The last layer of the pre-trained model is then trained with these new weights.

This approach is quite simple in practice and seems to be theoretically justified.

The authors demonstrate that VBSW achieves better test accuracy than not using VBSW on 3 toy datasets and 5 real-world datasets.

**Conclusions**

Quality: The authors did not experimentally compare VBSW to any alternative algorithms. I find this omission inexcusable. The problem of re-weighting examples to achieve better accuracy has been studied for decades; there are many other algorithms to compare against.

Clarity: The paper is generally well-structured and well-written, although with a few typos and grammatical errors.

Originality: I am not familiar enough with the related work to say whether this idea is novel. However, seems quite simple and potentially very similar to existing published techniques.

**Comments**

Section 3.1 seems to assume that the labels have no noise. For example, if two examples have the same input features, their labels seem to be generated by the same function f, which would always produce the same label for both examples. This seems unrealistic.

Section 2 describes the author's VBSW algorithm as being applied "prior to the training", but the algorithm actually requires a neural network to be pre-trained before the reweighting procedure. I felt the beginning of the paper was misleading in this regard.

**Minor comments**

Table 1: The difference between the mean accuracies of VBSW vs. basline on the BC dataset seems statistically insignificant; I believe VBSW should not be bolded.
review_title: Nice idea, but no experimental comparisons to other algorithms

final_score: rating: 7: Good paper, accept
review_content: This paper is well written and very well structured. I think this paper can be interesting for ICLR community. The authors presented experimental results that show marginal improvement using VBSW in both regression and classification applications. The experimental improvement is limited; however, it makes sense since the proposed approach is a preprocessing stage that can not be dynamically tuned during the learning process. 
I am interested to see experiments (for synthetic and real datasets) wherein the steep region is noisy, demonstrating how well the proposed strategy works in the presence of noise.  
One can expect that focusing too much on the noisy steep regions can be harmful to the learning process. 

In my opinion, the investigated problem has been described and motivated properly. It is interesting to formally show (via the presented generalization bound) why NN needs more points in the steep regions and how the steep regions can be formally approximated. The study has proposed reasonable approximations for the cases where the derivations are not available and computing new labels. The theory that backs the statements made in this study seems correct. However, I am concerned about their experimental results that do not seem significant (gain per model is limited). Also, it would be interesting to see a noise robustness investigation in the steep regions.
review_title: In this study, a strategy called VBSW is proposed to simulate a new distribution over the training set by assigning weights to the data points using their local variance. This strategy is used as a preprocessing stage, which serves to prepare the data for NN learners.  Formally, Taylor expansion is used to describe the local behavior of the unknown function with its derivatives.  Also, a generalization bound is derived to represent the need for having more data points in the steep regions. 

Meta-review: # Paper Summary

This paper proposes "variance based sample weighting" (VBSW). The key observation is that, in areas where the labeling function is changing rapidly, more samples may be required to achieve a good fit. In Section 3, they justify this intuition by showing that areas in which the label gradient is higher disproportionately impact the generalization performance, and go on to propose upweighting examples proportionately to the local label variance.

This label variance is approximated, for each training example, by finding its k-nearest-neighbors (either in the feature space, or a latent space--they use the latter in their experiments), and calculating the sample variance of the labels. There's a bit of a leap here: the authors started advocating for drawing more samples from rapidly-changing regions, but ended up upweighting the existing samples. These are not the same thing, but this issue is not discussed.

The experiments are well-thought out and comprehensive (although Reviewer 4 complained about a lack of nontrivial baselines, and I agree). The first and fourth set of experiments are particularly impressive. The first uses toy datasets to enable easy visualization, while the fourth (added during the response based on a comment of Reviewer 1) explores how robust VBSW is to hyperparameter choices and label noise. The second and third sets of experiments are on "realistic" problems, and while the gains are arguably marginal, VBSW does show consistently positive results.

# Pros

1. The reviewers agreed that the fundamental idea was intuitive and well-explained
1. The algorithm is general, and easy to implement
1. Reviewer 1 asked how robust VBSW was to hyperparameter choices and label noise, and the authors added a new section that I think does an excellent job alleviating such concerns
1. Experiments are comprehensive, including both toy datasets on which the behavior of the algorithm can be easily visualized, and more realistic experiments on MNIST, CIFAR 10,  RTE, STS-B AND MRPC. They show consistently positive results (although not especially large ones)

# Cons

1. The reviewers had mixed opinions on the writing quality, although they generally agreed that it was well-organized. There are a large number of typos, grammatical errors, and awkward phrases
1. Reviewer 4 noted that Section 3 assumes that there is no label noise, which seems unrealistic
1. Reviewers 2 and 4 complained about a lack of nontrivial baselines in the experiments (reviewer 4 called this "inexcusable"). In response, the authors added a new experiment comparing with active bias, on which the results were arguably positive, but not convincingly so. Regardless, this is only one experiment--there should be baselines for all experiments (except perhaps for the ones on UCI datasets), ideally multiple baselines (would a curriculum learning approach be appropriate on any of these tasks?)

# Conclusion

Three of the four reviewers recommended acceptance, but reviewer 4 gave a very negative score (3: clear rejection). Most of this reviewer's criticisms were fairly minor, with the two major ones being (i) that Section 3 unrealistically assumes that there is no label noise, and (ii) that the experiments have no nontrivial baselines. This first criticism is, I think, not a *huge* deal: Section 3 is only intended to provide intuition. The authors attempted to address the second criticism by adding one experiment comparing to "active bias", but I think that this is insufficient. In addition, while the paper is well-structured, I agree with the reviewers who complained about the paper's lack of polish.

All reviewers praised the fundamental idea, and said that the authors gave good intuition for their approach. The experimental results are also fairly comprehensive (aside from the lack of nontrivial baselines), and show positive results. The new section on robustness (in response to Reviewer 1) is a great addition that, I think, fills in most of the remaining "gaps" in this work. The major outstanding issues, in my opinion, are the writing quality, and the lack of nontrivial experimental baselines. These are very fixable, but I think that they're too significant for the paper to be accepted. Overall, I think that this is a borderline paper, but it's on the rejection side of the boundary.
Decision: Reject