Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This manuscript demonstrates that the popular approaches, such as importance weighting, and Distributionally Robust Optimization (DRO) variants, cannot really improve the distributional drift problem over Empirical risk minimization (ERM). To achieve this goal, this manuscript presents a Generalized Reweighting (GRW) (the above popular algorithms are its special cases). When training overparameterized linear models or wide NN models, the result for GRW is very close to that for ERM. Moreover, it also demonstrates a small regularization that needs to not greatly affect the empirical training accuracy does not help.
strengths_and_weaknesses: Observing that some works uncovered the popular approaches that aim to address distributional drift do not significantly improve over ERM, the authors try to theoretically prove this empirical phenomenon. Moreover, according to the theoretical conclusion, the authors also provide some potential approaches that can alleviate the distributional drift problem.  and it might fundamentally change this direction for distributionally robust approaches.
questions: The theoretical analysis is built on linear models. To extend to neural networks, the manuscripts utilizes existing the neural tangent kernel (NTK) theory to take networks as an approximately linear model. It is known that there is a gap between NTK networks and the practical networks. The width of NTK networks should be infinite; the NTK networks are commonly simple fully-connected networks;  he optimization algorithms should be simple stochastic gradient descent (SGD). All these conditions cannot be satisfied in real-world tasks. Moreover, Assumption assumes the first-order of the active function is Lipschitz continuous. We know it is common to apply ReLU as the active function in the modern networks, which is not satisfied this assumption. In summary, these ideal assumptions will influence the validity of the theoretical analysis. 
limitations: There is no potential negative societal impact for this manuscript.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: As a theoretical work, this paper aims to understand why generalized reweighting does not improve over ERM in the setting of distribution shift. Specifically, it considers the overparameterized linear model and wide neural networks under gradient descent, and prove the same solution between generalized reweighting and ERM methods via the implicit bias of the gradient descent algorithm.  Then, it claims that these two method families should share the same performance empirically. Technically, it mainly utilizes the neural tangent kernel theory for the wide neural networks. 
strengths_and_weaknesses: Strengths:
1. This work is motivated by the empirical results that the reweighting methods often have no superiority over ERM in the distribution shift problem. In my view, its theoretical investigation is valuable.
2. The claim is partially supported by formal theoretical results.

Weaknesses:
1. The considered setting is rather limited as previous work has considered the linear model case. Besides, although this paper considers the wide neural networks via the connection between the kernel method and neural networks (i.e., neural tangent kernel theory), it still has a large gap in practice. 
2. The results are not surprising and interesting as mentioned in 1. The key reason why generalized reweighting and ERM converge to the same solution is the implicit bias of the optimization algorithms (i.e., gradient descent in this paper) for overparameterized models. However, this paper does not highlight the key effects of the overparameterized model case. Thus, I am concerned that the authors may overclaim the results.
3. In practice, regularization and early stopping are usually used to improve the generalization performance. However, this paper neglects them.

questions: 1. The authors mentioned that the reweighting and ERM algorithms converge to the unique interpolator. But which one? Does the interpolator have some special property? 
2. Although this paper mainly considers the distribution shift problem, I haven't seen its key difference or point with the classical setting. Please give more explanations why ERM is not suitable for this case.
3. When theoretically comparing with empirical performance of two or many learning algorithms, generalization analysis is preferred. While this paper focuses on the optimization properties via implicit bias of gradient descent, implicit bias can also offer insight for generalization. Thus, what is the generalization performance of the learning algorithms considered in this paper?
limitations: The authors have mentioned some limitations in this paper. But, I still have the following suggestions.
1. The generalization analysis can provide more insights into the empirical performance.
2. More experiments in real settings can support the theoretical results.
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: This paper shows that Generalized Reweighting (GRW), dynamically weighting each loss term of the empirical risk, used for training a model that is robust to distribution shift has almost no impact on the result of the optimization compared with the ordinary Empirical Risk Minimization (ERM) for regression and classification with linear models or wide neural networks. This implies that despite being a popular approach, GRW fails to improve over ERM in the cases that the authors consider.
The authors also prove that even with regularization that compromise the training loss by $\epsilon$, GRM only brings a change of $O(\sqrt{\epsilon})$ to the minimizer compared to ERM.
Their results suggest that learning robustly to distribution shift may need approaches other than GRM.

strengths_and_weaknesses: # Strengths
- The paper is well-written and provide intuitive explanations even for technical part.
- The paper provides theoretical evidence supporting previously reported empirical observations for failures in training distributionally robust models with the weighting approach.
- While existing theoretical work only handles linear models, the paper consider wide neural networks.
- As a technical contribution, the authors analysis corrects and extends that of Lee et al. (2019).
- Although the main results are negative ones for the GRW approach, the paper discusses implications about other possible approaches.

# Weaknesses
- The paper does not provide concrete algorithms that can avoid their negative results.
- The paper analyzes the asymptotic behavior of wide neural networks when the widths go to infinity, which may not reflect the behavior of neural networks commonly used in reality.
- The results with regularization are hard to interpret because the paper does not analyze how much change we need for truly robust training and we do not know the $O(\sqrt{\epsilon})$ impact is insufficient or not.

questions: - [HNSS18] also provides some theoretical, negative results similarly to this paper. Could the authors discuss the difference?
- Do the authors have any thoughts about how much difference we should expect in the result of optimization, $f^{(t)}$, from that of ERM in order to be distributionally robust? If we only need a small change from ERM to achieve robustness, the result for regularization in the paper may not be a negative one.

limitations: The paper clearly discusses limitations of the work about the theoretical assumptions.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: Focused on understanding the effect of reweighing strategy on improving the robustness of ERM to distributional shift, this paper demonstrates notably that iteratively updating the sample weights does not improve over ERM in an overparametrized setting. With similars results already derived for the method of fixed weights, the main contribution of this work is to confirm, in a more general setting, the fact that the solution obtained by gradient descent in the overparametrized regime converges to an interpolator independent of the samples weights. 
strengths_and_weaknesses: Strengths: Theoretical understanding of reweighing strategy under a more general framework that allows iterative updating of sample weights.

Weaknesses : As previous work already explained the ineffectiveness of sample reweighing in the overparametrized regime with the convergence of the gradient descent solution to an interpolator independent of the sample weights, the generalized results given in this paper do not seem to provide further insight into the effect of the reweighing approach.
questions: As the main contribution of this work concerns the generalization to the iterative reweighing setting, it would help to clarify the originality of this work to discuss the technical challenges brought by the iteratively updated sample weights in obtaining the theoretical results. 

Furthermore, the interest of this study would be significantly increased by adding deeper results in the regularized case to shed light on the impact of the iteratively reweighed samples on the improvement of robustness.
limitations: The limitations of this work are well discussed. There does not seem to be any negative societal impact.

The contribution of this paper would be greatly enhanced if the authors could go further in exploring one of the directions mentioned in the article where the robustness is likely to improve.
review_title: null

Meta-review: metareview: The paper investigates generalized reweighting schemes that assign to each sample a weight during each iteration of GD over the empirical error. In the case of over-parameterized linear models and linearly independent samples it is shown that the final(= GD with infinite trajectory) ERM solution is not affected by the reweighting as long as the weights converge. These results are extended to the NTK regime with 0-initialization of the last layer under the assumption that the samples in the initial NTK-feature space are linearly independent. 

Compared to previous papers it allows different weights at each iteration and applies the setup to neural networks. However, as the weights need to converge (see Assumption 1) and only the NTK-regime (which is rather close to the previously considered linear case) is treated, the novelty is somewhat limited. In addition, it would have been nice to see interesting examples, in which the assumptions are actually satisfied. 

Although I tend to vote for rejection, I think this paper should to be compared to other papers of similar strength in order to make a final decision.
confidence: Less certain
Decision: Reject