Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors study the problem of improving the worst-group accuracy in the over-parametrized setting. They offer theoretical and empirical evidence that reweighting does not affect the final solution in this setting; in other words, the algorithm would converge to the same interpolators as that of basic ERM. The theoretical analysis is done for linear models, linearized networks, and wide fully connected networks. 

The authors also argue that the solution does not change unless a considerable amount of regularization is incorporated, so much so that it affects the training error. Again, some theoretical and empirical evidence is provided.


main_review: Understanding worst-group performance is an important and interesting topic. The paper is relatively easy to read, and provides valuable insights about this problem. However, there are some issues that need to be addressed

+ The abstract and introduction are quite misleading. For example, we see strong statements in the abstract such as "we cannot hope for reweighting algorithms to converge to a different interpolator than ERM..." or "we prove that for regularization to work, it must be large enough to prevent the model from achieving small training error." Such blanket statements without any hint that these are based on important assumptions (that are somewhat scattered in the paper) are misleading for the readers (of course unless if they dig deeper)

+ The first row of figure 1 is a good example of an overparametrized model, where the training accuracy of all models become 1 at some point in training. However, we still clearly see that even after than point, the test accuracies of different approaches are not the same. This is in contrast with the theoretical result by the authors that all of those methods would converge to the same result. The only explanation for this discrepancy is that the assumptions that the authors have made do not make sense for this experiment. For the second row (CelebA) the algorithms do not reach training error zero, and are effectively outside the regime of interest for the theoretical results of this paper. In conclusion, the the theoretical results do not really support the empirical results in this case; they really show different things. 

+ Given the discrepancy between the theoretical and empirical results, it becomes more important for the authors to make the abstract/intro/.. more accurate. For example, someone that reads the abstract will conclude that there is no way for the reweighting to help unless the average accuracy drops significantly, whereas the experiments show otherwise. 

+ The observation in section 3.1 that for linear models, the change in the parameters is always in the span of the data points is quite useful. I believe this is a standard observation that has been made before but I may be wrong. Can the authors comment about this? Are they the first to discover this? If not, they should at least add a citation.

+ More generally, are the other proofs (e.g, for the wide networks) similar to the analyses performed in previous work? If so, can you explicitly name those papers?

+ Is the theoretical analysis specific to the squared loss (e.g., in Thm 4, 5, 6)? If so, this must be clearly indicated as an extra assumption. 

+ Can you elaborate on assumption 1? Why is it intuitively a reasonable assumption (aside from the empirical study)? 

+ It looks like some of your experiments is similar to Sagawa et al. (2020a). Can you elaborate on the differences?

+ In Table 1, I believe you have left out the performance of ERM for early stopping. I think it is quite important to have those to be able to compare with the other methods.

+ As a side-comment, the practice of reporting 95% confidence intervals just based on running the method on a number of  random seeds is not necessarily valid. (usually you need to do cross-validation, or if not, argue that the test set is large enough...)
summary_of_the_review: The paper studies an important problem. The theoretical analysis is interesting though it has its own limitations. It will help if the authors comment about the novelty of the proof techniques compared to the previous work. 

Many statements of the paper are misleading and should be addressed. The empirical study and the theoretical study do not necessarily support each other and this discrepancy has not been discussed in the paper.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper theoretically proves the empirical observation that has been made in a lot of recent works regarding the role of importance reweighing in overparameterized deep networks. For squared loss and independent data points, it theoretically proves that reweighing the data points has no effect on the final model learned for linear models and linearized neural networks. This work also analyzes the role of regularization in preventing this behavior and proves that regularization has to be large enough to prevent small training error to have any effect. This work also has supporting empirical results on two datasets- celeba and waterbirds.
main_review: - The paper is studying an important problem about the effect of importance reweighing in overparameterized models which has attracted a lot of interest recently and thus, would be of interest to the community.
- However, the paper has many serious flaws. First of all, the paper is studying squared loss for its analysis and does not include a discussion about the choice of loss function. Loss function used in the previous works cited in this paper was cross entropy loss. So, there is this discrepancy between the works/experiments that this work is replicating and the theoretical results that are included.
 - This work is missing important citations for example [1] which initiated this study of importance reweighing methods in deep learning to the best of my knowledge.  Moreover, this has already been studied theoretically for cross entropy and other general losses by [2] which has not been cited in this work. So, it is not even clear if studying this paper for the squared loss brings out any new idea or insight on top of what was already known before. The point about regularization being necessary has already been made in previous works.

[1] What is the Effect of Importance Weighting in Deep Learning? Byrd et. al. 
[2]  UNDERSTANDING THE ROLE OF IMPORTANCE WEIGHTING FOR DEEP LEARNING, Xu et al.
summary_of_the_review: - However, the paper has many serious flaws. First of all, the paper is studying squared loss for its analysis and does not include a discussion about the choice of loss function. Loss function used in the previous works cited in this paper was cross entropy loss. So, there is this discrepancy between the works/experiments that this work is replicating and the theoretical results that are included.
 - This work is missing important citations for example [1] which initiated this study of importance reweighing methods in deep learning to the best of my knowledge.  Moreover, this has already been studied theoretically for cross entropy and other general losses by [2] which has not been cited in this work. So, it is not even clear if studying this paper for the squared loss brings out any new idea or insight on top of what was already known before.

I would like to make recommendation for rejecting this paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work studies the problem of training for worst-case subgroup performance. This has been a very prominent research avenue in the past few years and provides a natural approach towards learning fair and "causal" models (that do not perform too badly for any pre-specified subgroup). In practice however there have been some difficulties with existing approaches, and e.g., in the overparameterization regime, these methods do not perform well in terms of  worst-case performance on test sets. This paper provides a theoretical explanation for this fact (using linear models and linearized neural networks) and also illustrates it using numerical experiments on two datasets. Furthermore, the authors assess the role of $L_2$ regularization in training. The practical takeaway is that existing approaches based on reweighting require substantial regularization or early stopping to perform well in terms of test accuracy (in the overparamerized regime).

main_review: 
I enjoyed reading this paper. It is written in a very clear way and it addresses a very timely and important problem. I also enjoyed that it combined both theoretical results and simulations.

Below are some questions that I have and some suggestions that perhaps can be helpful to the authors in improving their paper.

1) If I understand correctly from equation (4) and Assumption 1, the framework of the present paper only applies to training updates based on the full dataset, and not to batch or stochastic updates. If this is the case, then this should be highlighted more prominently in the text and in the abstract. Would it be possible to generalize the analysis?

2) "Each $\mathcal{D}_i$ is a subset of $\mathcal{X} \times \mathcal{Y}$": Is this condition required for the theoretical results? If so, it should be discussed at more length. Can it be relaxed? For example, in my mind often the notion of worst-case performance relates to multiple environmentsl as in e.g, the conceptual framework of Rothenhäusler et al (2021, JRSSB) or to protected attributes that are not directly included in the model. These may not be perfectly recoverable through subsets of predictors and response variables (though of course they may be strongly correlated).

3) Maybe in the high-level statement after Theorem 2 one could clarify that this statement depends on identical initialization $\theta^{(0)}$ for all involved methods?

4) Last paragraph of Section 3, "Moreover our theoretical results can explain the surprising empirical observation": I think this paragraph is not sufficiently justified (i.e., it does not really explain the observation, at most it hints at the plausibility of it). Can the authors make a stronger case for their argument? Otherwise my suggestion would be soften the claim (or even remove the paragraph).

5) I like the experiments since they bring the main point of the paper across very clearly. One additional result I would have liked to see is an empirical illustration of whether the theoretical arguments hold, e.g., are the final solutions of ERM, DRO, and IW initialized at the same $\theta^{(0)}$ very similar (and more similar than solutions of the same method initialized at different $\theta^{(0)}$)? By similarity here I refer to similarity of actual model fits, rather than accuracy/performance.
 


# Typographical errors

* Equation (5), $f^{(t)}$ instead of  $f$
* Page 8: "trained trained" (repeated twice)
* Reproducibility statement: I think speculation should be "specification" (note: the word speculation appears twice in this sentence). Anaconda should be capitalized.


summary_of_the_review: 
I think this is an interesting contribution on the theoretical and practical study of worst-case subgroup performance and therefore I would like to see this work accepted. I also think the paper could be improved a bit further by adding experiments that more closely validate the theoretical results (point 5), and by clarifying limitations/shortcomings to this work.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper mainly focuses on the reweighting algorithms (e.g. Importance Weighting, Group DRO) for the worst-group performance. It tries to theoretically explain why overfitting problems always appears in reweighting algorithms. Specifically, the authors prove that under several conditions (e.g. assumptions for algorithms, wide fully-connected neural networks, squared loss), the worst-group test performance of the reweighting algorithm will converge to the same level as ERM.
main_review: Strengths:
1.	The paper provides good proof for linear models via the intuition that the change in model parameters always lies in a low-dimensional subspace. 
2.	The conclusion gives new insight for designing algorithms, which shows reweighting algorithms without any repair methods may not be better than ERM for the worst-group performance.
3.	The paper writing is generally of high quality.


Weaknesses:
1.	My feeling is that the conclusion is somewhat overclaimed. In both abstract and conclusion, it is emphasized that this work proves the pessimistic result that reweighting algorithms always overfit. However, the paper only proves that this conclusion might be true for some **specific** situations. For example, the reweighting algorithms need to satisfy Assumption 1 and Assumption 2, which means not all reweighting algorithms are considered. The overparameterized models need to be linear models, linearized neural networks or wide fully-connected neural networks, which are not commonly used in practice. Besides, the squared loss needs to be used to confirm the update rule is linear. All those assumptions are not quite mild for me. 
2.	The analysis of neural networks contributes less. With the existing NTK theorem, the extension from linear models to wide fully-connected neural networks is trivial (Section 3.2, 3.3). The work bypasses the core problem of overparametrized neural networks and only considers the easy wide fully-connected neural networks. 
3.	The theoretical results and experiments do not match. The theoretical proof considers wide fully-connected neural networks, while the experiments utilize a ResNet18 as the model, which is quite different.
4.	Some key steps are empirical, although the paper claims that it provides a theoretical backing in the abstract. For example, this paper only proves that reweighting algorithms will converge to the same level as ERM, but the conclusion that ERM has a poor worst-group test performance is summarized through observation in practice. Besides, the paper can only empirically demonstrate that commonly used algorithms satisfy Assumption 2.

summary_of_the_review: The actual main contribution of this paper is proving that for linear overparameterized models, the current reweighting algorithms almost always overfit. It provides a possible way of analyzing overfitting problems by reducing a family of algorithms to the commonly used ERM. However, the analysis of neural networks contributes less, and some key steps are still empirical results. Besides, there is a gap between theoretical results and experiments. In summary, the conclusion of the paper is somewhat overclaimed, and there is still a lot of room for improvement.
review_title: null

Meta-review: This paper studies the effect of importance weighting in three model classes: linear models, linearized networks, and wide fully connected networks, and show that under certain assumptions, gradient descent for training an overparameterized model converges to the same ERM interpolator regardless of the reweighting scheme. The reviewers acknowledge that this paper had good exposition and writing in general, but they were in consensus that the initial version of this paper includes many inaccurate overclaiming statements. In summary, after discussions, the reviewers would like the authors to:

- revise the abstract and the introduction, specifically, adding appropriate qualifiers on the neural networks, losses, full gradient descent training, etc (Reviewers hLzT, M2hT, fZgx)
- address the discrepancy between theory and experiments, e.g. the inconsistency of the loss chosen in theory and experiments, the requirement that the widths of the neural networks need to large (Reviewers wG4N, fZgx)
- add experimental results for early stopping (Reviewer hLzT)
- empirically verify that the final solutions of ERM, DRO, and IW initialized at the same \theta^0 are very similar (Reviewer M2hT)
- discuss the novelty compared to Sagawa et al in the paper (Reviewer wG4N)

thus, this submission needs a major revision, and is not ready for acceptance in its current form. We encourage the authors to revise accordingly, and resubmit in the future.
Decision: Reject