Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper provides a theoretical investigation into, and comparison between, two forms of correcting biased data: reweighting, and resampling. In particular, since previous empirical analyses have suggested that reweighting performs better in practice, the author(s) provide several theoretical explanations for this discrepancy. This is a very interesting problem to consider, and I applaud the authors on their general approach and conclusions, which are novel to the best of my knowledge. The paper is also reasonably well-written too.

Unfortunately, as it is presented here, I find the paper underwhelming for two reasons.

1. Currently, the results (aside from Lemma 6, a quick corollary of a known result) are stated to hold only for very specific toy examples. This is nice enough for illustrative purposes, but I don't see why, with a little more effort, these cannot be extended to a much larger class of objectives. In particular:
(a) Why does the stability analysis in section 3 not extend readily to combinations of strongly convex functions with disjoint supports? 
(b) What difficulty does it pose to have more general bimodal functions in Lemmas 3 and 4? To me it seems that the main obstacle is the non-constant diffusion coefficient in the SDE approximation. However, in one dimension at least, the Lamperti transform (which is used in Appendix C) can be used to convert this SDE into one with a constant diffusion coefficient, and the rest of the argument should go through. Am I missing something?

2. A more minor point: some of the discussion (and the title) seems to suggest that resampling is always a better choice, which is certainly not true in general. There are settings, particularly outside of deep learning, where reweighting is superior since it typically yields lower variance. More specific language is needed throughout --- this is a phenomenon that pertains primarily to stochastic gradient methods where stability/robustness is key and weights can be small. Further on this point, the author(s) briefly mention under eqn. (4) that the key reason for the discrepancy is that the variances are quite different. I think more discussion is probably needed about these differences in variance. 

I enjoyed reading the paper, but these two issues (the former in particular) prevent me from recommending acceptance, as it seems it can be greatly improved for theoretical audiences with comparatively little effort. With these improvements, or some good reasoning as to why they are infeasible, I would be happy to boost my score to a 7.

Some other minor comments:

- I am somewhat confused at the value of the numerical experiments presented. I agree that they add to the paper, but my understanding from the introduction is that it was already known that resampling methods work better in these applications than reweighting. Is this not true? If experiments of this form have not been conducted in the literature previously, this is certainly worth mentioning. Otherwise, some of these could be moved to supplementary material in favour of further discussion on the theoretical results.
- Can more than two subpopulations be considered? It seems to me that the general case involving more than two subpopulations could be reduced to successive two-subpopulation problems. Is it possible to extend some of the consequences of these results, especially Lemma 6, to this setting?
- Very minor, but I'm not especially fond of the use of f_1, f_2 for the sampling proportions. Other papers discussing Langevin approximations sometimes use f to denote the potential function, which makes things a little confusing here. Can a different letter be used instead? 
- Two sentences before eqn. (4): "{s}" should just be "s".
- Figures 1 and 2: Can (a),(b),(c) be used instead of (1),(2),(3), so as not to confuse with equation numbers?
- First sentence on pg. 4: "We refer..." -> "We defer...". Also "...shows that reweighting makes problems stiffer in terms of the stability criterion": maybe "reweighting can incur a more stringent stability criterion"?
- Can the size of the axis labels (not tick labels) in Figures 1 and 2 be increased?
- Last line of pg. 5: "not-Lipschitz" -> "non-Lipschitz"
- Last line on pg. 8: "extend our analysis to unsupervised learning problems": since the previous discussion has implied these results hold very generally (point 2), it might be good to provide a little more detail on what is meant by this.
review_title: Official Blind Review #5

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper provides an analysis of why resampling can be better than reweighting in some cases. By observing the behaviour of resampling and reweighting in simple optimizations with SGD, the theoretical results show that resampling tends to be more stable. The general analysis is based on SDE approximation. Experiments on classification and off-policy evaluation show that resampling can be better in some cases.

Strength:
- Simple examples and analysis showing the instability of reweighting and the possible reasons

Weakness:
- The theory is fairly restricted
- Some details are missing
- Experiments are unclear

Detail comments:
1. The assumptions of Lemma 5 and 6 are strong. In most cases, the optimization landscape is likely to have more than two local minimas. Moreover, Lemma 6 assumes that the relative error is bounded by epsilon, which is difficult to verify in practice.

2. The effect of the learning rate is not sufficiently demonstrated. The learning rate \eta plays a role in Lemma 1 and 2. Fig.1 only shows a specific eta=0.5 without explanation. It would be interesting to see how resampling and reweighting behave with different learning rates. The same applies to the example in Sec.4.

3. There are not enough details about how Fig.1(2) and Fig.2(3) are produced. Specifically, how is the resampling conducted?

4. The regression experiment is actually binary classification.

5. The TD(0) update on page 8 is wrong. The minus sign should be plus. Additionally, using \delta_\pi and \delta_\mu can be misleading as the TD error only depends on the functional form of V instead of the policies. The setting and the results are very unclear. There are n=32 states, but the x-axis of Fig.5(left) ranges from 0 to 6. All the curves are using C=1/10, so it is not clear how they differ. What do W and S stand for in the legends?

Minor
- In the proofs of Lemma 3, Z is used as a standard Gaussian RV and partition function.
- The \theta^* in Lemma 5 should be \theta^\circ.

==== Update ====
Increased score according to the revision and discussion.
review_title: Interesting analysis, but some details are missing or wrong

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:

This paper delves into a stability analysis of reweighting and resampling for overcoming imbalanced data in supervised learning. Reweighting employs the use of importance ratios to modify a samples weight to the training in turn changing the effective distribution. There are several resampling procedures which all have a similar effect in the analysis, and the authors consider several algorithms for resampling in their experiments.  The reweighting approach, while convenient, leads to poorer stability under simplifying assumptions. While this is interesting in its own right, they show that under certain distributions of the data reweighting will actually not converge to the optimal minima, while resampling will. This is motivated by a large collection of work developing resampling methods for imbalanced data, which all come to similar conclusions (i.e. that following a resampling procedure outperforms a reweighting procedure in many, but not all, settings). They follow up with a SDE analysis in another toy problem, which they then extend to more realistic assumptions.


Thoughts:

This paper is a good start at trying to understand the behavior of resampling and reweighting in the wild. It is also well written, and contains some interesting discussion on their analysis. The proofs also seem straightforward for the most part and well explained. Unfortunately, I have a few concerns (see below) which have lowered my score. I'm recommending reject at this time, but would be happy to increase my score as we go through the rebuttal phase.


Concerns/suggestions/questions:

1. My first concern has to do with how general we can expect the analysis of these problems to be. I understand that the analysis for larger problems is often harder if not impossible given our current theory, but if we simplify too much the results aren't indicative of the larger picture. Some assumptions which I have some issues with
   - Our problem can be decomposed into several discrete loss functions (i.e. $V_1(\theta)$ and $V_2(\theta)$). I can see how this works for classification where each loss function is for each label, but when moving to regression and RL prediction, this becomes less clear. For the case of learning a value function off-policy, it feels more like the importance weights are shifting the space, rather than reweighting a discrete set of loss functions.
   - For the general results you still only consider the case where there are two minimizers. (Q1-1) Are you only considering the case where the weights only shift within some local ball and only encounters these minima? (Q1-2) Can this be guaranteed in the larger problem you motivate (i.e. using NNs)? Maybe this is close to Lazy training, or results when the NN is overparameterized and the weights don't shift much. (Q1-3) Could these results be extended to a finite number of minimizers within a ball? This seems more reasonable.

These are the main assumptions I'm concerned with. They both are hinting at the larger question of (Q1-4) "how reasonable are these assumptions to the larger motivating problem?" I think it would make the paper much better if there was some examples that were less toy-like.


2. The results in the toy examples for the stability and SDE analysis are really nice. But I'm a bit concerned with the conclusions drawn. Both analysis results in bounds on a notion of "stability" which includes the learning rate as a factor. When testing the result empirically, only a single learning rate is used for both the resampling and reweighting. This gives a facade of a results that reweighting is always unstable, which is not true. When selecting a stepsize in the correct range reweighting should indeed be stable. I think what the authors are wanting to say is that selecting learning rates will be much easier for resampling as they do not rely on the sampling proportions. I agree with the sentiment, but I think this needs to be made more clear. One way is to give effective ranges for the learning rate in which we expect the two approaches to be stable, and observe that in practice we can't always know $(f_1, f_2)$ so selecting in the prober range is an empirical exercise.  You can also show this through uniformly selecting learning rates in the range $(0,1)$ and showing how many result in a stable system around the global minimizer. With these experiments, I would also suggest starting both procedures at the same initial weights and indicate through a color gradient or arrows the temporal direction of the training (right now it is quite ambiguous).

3. Experiments:

   I'm q bit concerned with the lack of details provided for the experimental design. I understand that in theory papers empirical results are not the focus, but the goal should still be to provide enough details to reproduce independent of any accompanying code base. Even with these missing details I'm a bit concerned with the results as well, and how many conclusions we can draw from what is presented.

   Q3-1. How many runs were performed? (all)
   Q3-2. What is the statistical significance of the provided results? (regression and off-policy prediction)
   Q3-3. What were the hyperparameters chosen, how were the parameters chosen? (all)
   Q3-4. What loss functions were used for the classification and regression experiments?
   Q3-5. Why not choose another type of regression problem, rather than another classification problem?
   Q3-6. What optimizer was used for training?

   On top of these missing details, some more general concerns:
   C3-1. I'm assuming we are only using a constant learning rate for all the experiments. Is this reasonable. Could we expect the results to change if the learning rate is able to take the variance of updates into account (i.e. using RMSProp). These experiments could be worthwhile pursuing, because the analysis only covers static learning rates. This would also help elucidate more about the interaction between resampling and reweighting in systems that are closer to what is being used in practice.
   C3-2. For the off-policy prediction setting. What is the discount parameter for the problem you are considering? How are you calculating the error? Only through online data? Or through sampling from the sampling a set of states from the state distribution of the behavior policy? Does this environment relate back to something in the real world that is of interest to make predictions on? What is the motivation for this problem? What are the x and y axis in the left plot of figure 5? Did you mean to calculate error using $V_\pi$? The current notation is often used for the optimal value function, which is a different concept.


Some minor corrections:
 - Page 7 "...objective is to find the value function of police \pi..."
 - Abstract "reweighting outperforms resampling when ...", you draw the opposite conclusions in the paper.

--- Updated score ---
The authors did a nice job of addressing many of my concerns. But there are still some lingering issues with the experimental design (especially with the reinforcement learning experiments). The main concern I have is why the variance for your results is so low from run to run. This could suggest the problem is too easy, or that there is a bug somewhere. While I don't think it is enough to outright reject the paper, it still puts me on the fence about a strong accept.
review_title: Review

final_score: rating: 5: Marginally below acceptance threshold
review_content: 
Summary:
When training data comes from a sampling distribution that is different from the target test distribution, there are two commonly-used machine learning techniques to correct the distribution difference --- re-sampling and re-weighting. This paper investigates why re-sampling outperforms re-weighting when using stochastic gradient descent for optimization. The paper provides two explanations. 
(1) Resampling with SGD is more stable. By stability, the authors mean that the expected L2 distance between the parameter during optimization and the true parameter is small. 
(2) Reweighting with SGD can converge to a worse local minimum with larger probability. 


They also conduct experiments to show that re-sampling outperforms re-weighting. 

Strengths:

1. The problem to compare re-sampling and re-weighting during optimization with stochastic gradient descent is very interesting and important. Machine learning from biased data (e.g. selection bias) is very prevalent and stochastic gradient descent is a popular optimizer. 

2. The paper is clearly written and easy to follow. 

3. The stability analysis and SDE analysis provide two alternatives to explain the difference between re-sampling and re-weighting. 

Weakness

1 The theoretical analysis does not provide strong evidence that re-sampling is better than re-weighting. 

1.1 It would be great if the authors could explain more why Lemma 1 and Lemma 2 show that resampling is better. To me, it just shows that, if we want to achieve stability, we have to use smaller learning rate for reweighting. It makes no sense to me to compare resampling and reweighting with a fixed learning rate. 

1.2 SDE analysis shows that re-weighting sometimes tends to converge to a worse local minimum. But it did not sate re-sampling always tends to converge to a good local minimum. It would be great if authors explain when re-weighting and re-sampling tend to converge to good and bad local minimum. 




2. The experiments details are not clear and I did not see how these experiments reflect the theoretical analysis. 


2.1 It would be great to mention whether the results are performed on the training set. I assume the results presented are for the training set since this paper investigates how the optimization with SGD works instead of focusing on generalization. 

2.2 It would be great to report the final training objective. Since the main theoretical result of the paper is that optimization with SGD using re-sampling tends to be more stable around a better local minimum. 

2.3 In the classification experiments, the ROC-AUC of reweighting method is only around 0.53, that is just 0.03 better than random guess. A large neural network typically can overfit a classification dataset with just two classes. I am wondering why the ROC-AUC is so low. It would be great if the authors could provide the experiment details, e.g. the learning rate. 

2.4 In the nonlinear regression experiment, logistic regression is used. Logistic regression objective is a convex objective. There is no local minimum. So the experiments do not validate the SDE analysis. The authors claimed that they do this experiment to show that ``performance of SGD deteriorates when reweighting is used''. I did not see any previous analysis indicating this. It would be great if the authors could explain more about why they conduct this experiment and how this relates to their theoretical analysis. 






Additional feedback

In the abstract ''reweighting outperforms resampling'' -> ''resampling outperforms reweighting''

Why in equation (3), there is an approximate equal? It seems to me that it is just equal. Same for equation (4). 

learning rate \eta first appears in Lemma 1 without explanation. Also, Lemma 1 uses C= 1 which is not explained in the main paper. 


In SDE analysis: The statement "all iterates will stay in this region'' confuses me. If the learning rate is large enough, I think it can get out of the the region. Say when \hat{\theta}_t is at -2 and we encounter an example from V_1, then the gradient is positive. If the learning rate is large enough, it can get to (0,\infty). 





review_title: Why resampling outperforms reweighting for correcting sampling bias

final_score: rating: 7: Good paper, accept
review_content: Biased datasets are ubiquitous and therefore addressing bias in datasets is a relevant issue for building good ML applications and products. The paper makes a significant contribution by providing a theoretical explanation to the observation that resampling is generally more effective than reweighing as a debiasing tool. This paper does not introduce a novel way to address bias and therefore its originality and impact is limited. It does however provide good proof that the resampling approach is more efficient than reweighing, which will help ML developers to make a more informed choice between the two approaches. The ubiquity of the sampling problem, makes the impact of this work significant despite not being very original. In addition, to the results, the approach used in the paper, namely, the use of numerical methods borrowed from stability analysis of dynamical systems and stochastic differential equations continues an interesting line of research that is helping to understand optimization processes and how to use them efficiently to train unsupervised algorithms. The theoretical results look solid and I cannot see any issue with them to the best of my knowledge. The authors provide and array of numerical results which convincingly demonstrate their theory. The manuscript could be improved by exploring the limitations of their approach, but I do not see this is needed for the paper to be accepted. 
review_title: Paper provides explanation why resampling is better than reweighing for addressing bias problem in supervised learning

Meta-review: 
The paper theoretically investigates two bias-correction methods, reweighting and resampling. It considers a very interesting problem and presents illuminating results. The paper could benefit substantially from improving the experiments so that they clearly validate the theoretical results presented.
Decision: Accept (Poster)