Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the impact of importance-weighting in interpolating classifiers. The authors showed that in contrast to the prior works that showed importance-weighting is ineffective due to implicit bias of converging to max-margin, switching to poly-tailed loss circumvents this issue, both theoretically and empirically.
main_review: This paper studies the impact of importance-weighting in interpolating classifiers. The authors showed that in contrast to the prior works that showed importance-weighting is ineffective due to implicit bias of converging to max-margin, switching to poly-tailed loss circumvents this issue, both theoretically and empirically.

Pros:
Overall, this paper is very well-written and the theoretical results are sound. I really like the idea of using a poly-tailed loss - it is simple, effective, and practical - but by far not an obvious one. This idea circumvents the previous negative results in an elegant manner. 

I also like the analysis of poly-tailed loss under Gaussian mixture setting: there are some surprising takeaways, e..g. inverse-frequency weighting being sub-optimal and the optimal re-weighting being roughly cubic in class imbalance. I have never seen these types of results in the prior works.

Cons:

There are some obvious limitations, for example, the gap between linear classifiers and neural networks used in practice, which is a minor issue due to the intractability of analysis. 

There are some more interesting possible extensions, though: for example, a theoretical analysis of (and comparing against) early stopping would be nice.

There is limited discussion about how to pick the hyperparameter alpha, which can be useful for practitioners.

The performance boost (2%-3%) is relatively minor. I am not sure about how it compares to stronger baselines.
summary_of_the_review: I like the paper due to its simplicity, effectiveness, and interesting take-aways from theory. There is some room for improvement in the experiments.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper shows both theoretically and experimentally that importance weighting is not incompatible  with the training of overparameterized models provided that the training loss is appropriately modified so that it does not have an exponential tail. Specifically, for binary classification the authors propose a new loss function with polynomial tail decay. Theoretically, the new loss is shown to outperform weighted cross entropy for linear models and an imbalanced mixtures of gaussian model. Empirically, the new loss outperforms weighted cross entropy on imbalanced CIFAR 10 and the CelebA dataset. 
main_review: Strengths:
- The paper is well-written and enjoyable to read
- The theoretical claims are sound and well presented
- Theorem 4.2 is interesting: It extends the analysis by Chatterji & Long to imbalanced setting and the finding about the scaling of the weight being cubic in \tau is interesting.

Weaknesses:
- The study is limited to binary classification. It is not clear how to extend the loss to multiclass. At least when it comes to experimental results, multiclass experiments would make a stronger case. 
- Experimental results are limited to a comparison between weighted cross entropy and the new loss. How does the new loss compare to other const-sensitive techniques, e.g. LDAM loss [1], Logit-adjusted loss [2], VS loss [3], DRO (Sagawa et al.)?
- More generally, while the presentation is from the viewpoint of distribution shift, all study cases (both theoretical and experimental) are with respect to imbalanced data problems. In this setting there has been a lot of recent work, which appears closely related but is not discussed (eg. [1-4]). Specifically, [3] appears to be very closely related (for example, see their Theorem 1; how does your program in (2) compare to the cost-sensitive svm?). I suggest that the authors try to better place their work within this literature.

[1] Cao, Kaidi, et al. "Learning imbalanced datasets with label-distribution-aware margin loss." arXiv preprint arXiv:1906.07413 (2019).
[2] Menon, Aditya Krishna, et al. "Long-tail learning via logit adjustment." arXiv preprint arXiv:2007.07314 (2020).
[3] Kini, Ganesh Ramachandra, et al. "Label-Imbalanced and Group-Sensitive Classification under Overparameterization." arXiv preprint arXiv:2103.01550 (2021).
[4] Kang, Bingyi, et al. "Decoupling representation and classifier for long-tailed recognition." arXiv preprint arXiv:1910.09217 (2019).
summary_of_the_review: While I appreciate the author's clarity of presentingtheir ideas/theories/proofs/experiments and the paper's finding is quite interesting, it is perhaps not so surprising especially given the recent works and findings on mitigating the effect of weighted CE failure for imbalanced data. Also, the implications of the finding are not made clear. How does the proposed loss compare to state-of-the-art loss adjustments? Does it apply to multiclass settings?
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Previous works pointed out an interesting incompatibility between importance sampling and training overparameterized neural nets. In the view of margin, Soudry et al. (2018) showed that GD on exponentially-tailed loss converges to the max-margin classifier, and Xu et al. (2020) pointed out that this margin maximization is unaffected by importance sampling. This paper then turns to studying polynomially-tailed loss.

* This paper establishes the implicit bias by formulating an optimization problem, which can change according to the importance weights. The convergent classifier is shown to generalize better than the exponentially-tailed loss in a simple linear classification setting, where the dataset contains two sub-Gaussian clusters.
* Experiments on Imbalanced Binary CIFAR10 and CelebA show that the polynomially-tailed loss performs better on imbalanced datasets.
main_review: #### Strengths

1. This paper points out a potential way to make training overparameterized neural nets compatible with importance sampling, which is to change the loss from cross-entropy to a polynomially-tailed loss.
2. A full characterization for the implicit bias of GD on polynomially-tailed loss is given by (2) in Section 4.1 (although it is an easy corollary of Ji et al. 2020). It is clear from (2) that the implicit bias changes with the importance weights.
3. The separation between polynomially-tailed loss and exponentially-tailed loss in Section 4.2 is simple and interesting.

#### Weaknesses

1. The theoretical analysis is only for linear classification. As for the generalization aspect, the analysis is even more restricted as it only holds for the dataset with two sub-Gaussian clusters. So the theoretical result is not very strong. Although we can certainly draw some insights from this simple setting, it is still unclear what generalization guarantees polynomially-tailed loss has in general.
2. The paper claims that the implicit bias of GD changes with importance weights, but such change could be minor when the degree of the polynomial is high, i.e., $\alpha$ is large. In the equation (2) in Section 4.2, if $\alpha \to \infty$, then $\hat{\theta}_{\alpha}$ is just the max-margin solution. Thus the choice of $\alpha$ cannot be arbitrary, and a polynomially-tailed loss with a high degree can perform as badly as the exponential loss. In the later sections, the authors always use $\alpha = 1$. It would be nice if the authors can carefully discuss more the choice of $\alpha$ and provide a recommendation for the choice of $\alpha$. If $\alpha = 1$ is the best in the theoretical setting in Section 4.2 and in the experiments, then the paper should highlight linearly-tailed loss rather than polynomially-tailed loss.
3. The experiment results are not compared against many baselines. It is unclear whether the 2%-3% test accuracy difference can be considered to be a big gain, and whether other methods (e.g., undersampling) can obtain the same gain in terms of the test accuracy. Although this paper is mainly a theoretical paper, the authors do claim that polynomially-tailed loss has practical value, and the current experiment results are not strong enough to support this claim.

#### Minor Comments

* Page 20 looks wried.
* The current proof for Theorem 4.3 is trajectory-based, i.e., it analyzes the trajectory. However, Soudry et al. (2018) have already proved that the convergent classifier is the max-margin classifier, and one can easily show that the max-margin classifier is unique. So I'm wondering whether Theorem 4.3 can be proved by just analyzing the properties of the max-margin classifier, without analyzing the trajectory. It is not a weakness of this paper, but if this paper can provide an argument directly for the max-margin classifier, then the readers will better understand why the max-margin classifier is bad in this setting. After skimming the proof, I think it might be possible to translate Lemma C.3 into a lemma on the upper bounds for the ratio between dual variables (instead of loss values), and it sounds promising to use this upper bound to bound the influence of the samples from the minority class, and hence the max-margin classifier generalizes poorly.
* Section 4.1 should clarify that the optimal solution for (2) is unique. Although it is proved in the appendix that the solution is unique, but clarifying this in the main body can avoid confusion.
summary_of_the_review: This paper provides interesting theoretical results for using polynomially-tailed loss to resolve the incompatibility between importance sampling and training overparameterized neural nets. However, the theoretical setting is quite restrictive. I think this paper is on the borderline, but it is ok to accept this paper.

------------------
Post-rebuttal update:

I am glad to see that the authors have conducted more experiments to compare their method with baselines. I'm not an expert in the empirical methods for dealing with distribution shift, but I think the current empirical results they have are great additions to their theoretical analysis. I have increased my score for the empirical novelty and significance accordingly.
As for the theoretical analysis, which is the main selling point of this paper, I still believe the current setting is restrictive, although I know some previous works are studying it. Therefore, I would like to continue to vote for weak acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper, the author investigates whether importance weighting is incompatible with the training of overparameterized neural networks. In contrast to the recent observation that  importance weighting is ineffective in current deep learning paradigm (Byrd & Lipton 2019), the authors show that it could actually be helpful using polynomially-tailed losses. Both theoretical justifications and empirical evidences are provided to support the claim.
main_review: [Strengths]
- Clear presentation. Figure 1 gives an intuitive example illustrating why importance weighting could fail on exponentially-tailed losses.
- The proposed polynomially-tailed loss could be a very practical tool for importance weighting.
- Theoretical results look solid and well justify the polynomially-tailed loss.

[Weaknesses]
- The theoretical results are based on the assumption of sub-Gaussian data which could be unrealistic.  
- The polynomiallhy-tailed loss does not seem to admit a probabilistic interpretation as the distance between two distributions. How would it perform on a softmax layer?
- The proposed loss has a parameter alpha. However, the impact of the parameter is not discussed in either the theoretical or empirical section. Does the choice of alpha significantly affect the result? 


summary_of_the_review: Overall, I think the paper provides answers to an important question. Both theoretical and empirical results are provided to corroborate the claim.
review_title: null

Meta-review: The paper revisits importance sampling as an approach for combating distribution shift when training over-parameterized neural networks. Contrary to recent results that suggest that importance sampling is perhaps incompatible with over-parameterization, the authors find that the exponential tail of losses such as the logistic loss is the root cause. For polynomial tailed losses, authors analyze gradient descent on importance weighted polynomially-tailed losses and demonstrate the advantage of importance sampling in a label shift setting.

There paper is well-written and the results are sound. Overall, a good paper.
Decision: Accept (Poster)