Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors investigate the minimax optimality of classification problems under label and covariance shift on groups. They show that the minimax classification error is characterized by the sample size for the minor group essentially, indicating that increasing the major group's sample size does not affect the classification accuracy. They also demonstrate that the undersampling-based estimator achieves the optimal minimax.
strength_and_weaknesses: Strength:
- Well-written with a clear claim
- Technically sound
- The claim of characterization with a minor group's sample size is interesting

Weakness:
- Lack of significance of techniques.
- The results are limited to too simple cases. 
clarity,_quality,_novelty_and_reproducibility: The robustness is a crucial issue in machine learning. The minimax optimality for the robust classification is thus well-motivated. This paper is clearly written and easy to follow. The results are technically sound. The paper's claim is quite clear, i.e., the minimax optimal error of the group robust classification is characterized by the minor group's sample size and is achieved by undersampling.  

The main weakness of this paper is a lack of originality in the technical contribution. The basic direction of the analyses is equivalent to the traditional techniques of the minimax optimality analysis; that is, the technique for analyzing the Besov space using the wavelet analyses, such as
- Donoho et al. Minimax Estimation via Wavelet Shrinkage. The Annals of Statistics, 1998. 

Such standard techniques cannot directly apply to reveal the characterization with the minor group's sample size. However, the adaptation is easy by constructing a set of distributions such that the distributions for the major group are invariant. Consequently, I'm unsure about the technical contributions of this paper compared to the existing techniques. 

One weakness of this paper is that the results are limited to the Lipschitz density. The existing techniques can handle more various spaces, including Holder, Sobolev, and Besov spaces. I cannot find any difficulty in extending to various such spaces. If my thinking needs to be corrected, I'd like the authors to clarify the difficulty in extending such spaces.
summary_of_the_review: This paper is well-written and technically sound. However, the significance of the technical contribution is unclear. I thus recommend rejection at this time. It is welcome to clarify the significance during the rebuttal.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This draft studies the problem of learning with a distribution shift. The authors show that in the worst case of label shift or group-covariate shift, with the measure of minimax excess risk, no other algorithm can provably outperform the undersampling algorithm without further investigating the structure of distribution shift. The results are also consistent with previous empirical studies.
strength_and_weaknesses: Strength:
+ This work theoretically shows that in the worst case of label shift and group-covariate shift problem, with the measure of minimax excess risk, a simple undersampling algorithm has obtained the minimax optimal result. This result is intuitively obvious, but there is no theoretical proof for it. This work provides a formal formulation and proves this intuitive result. In these two cases, the lower bound of undersampling matches its upper bound. This result also matches the empirical results proposed by other researchers.
+ Overall, the draft is well organized, and its theoretical results are clear.
 

Weaknesses:
- This work analyzes the worst-case scenario for label shift or group-covariate shift. Without any test (labeled) data or knowing the structure of distribution shift, it is easy to see that no other method could provably outperform the undersampling method. This result does not help in the design of a practical algorithm to handle the problem. For example, how to decide whether to use undersampling or other approaches to handling the label shift and group-covariate shift?
clarity,_quality,_novelty_and_reproducibility: This draft is well-organized and easy to follow. The theoretical results are solid and consistent with previous results. The results are intuitively obvious but there is a lack of theoretical analysis for this problem. The reproducibility of this work is good.
summary_of_the_review: This paper provides a theoretical analysis for the problem of worst-case label shift and group-covariate shift. They prove that in the worst case of label shift and group-covariate shift problem, with the measure of minimax excess risk, a simple undersampling algorithm has obtained the minimax optimal result. This result is intuitively obvious, but there is no theoretical proof for it in the literature. The proposed analysis is sound and the empirical studies verify their proposal.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper explores the minimax optimality of undersampling. Specifically, for balanced test sets assuming Lipschitz label shift or group covariate shift, the lower bound on the minimax excess risk depends on the number of samples in the minority class at the rate n_{\min}^{-1/3}, in the univariate case. Undersampling with a binning estimator has the same rate, and so undersampling is minimax optimal.

strength_and_weaknesses: Strengths

* Clear paper.
* Reasonable theory result.

Weaknesses

* Restricting to the univariate covariate case is lazy, or, if the group covariate shift upper bound Theorem 5.2 cannot be generalized to higher dimensions at the same -1/3d rate, deceitful.
* My understanding of the subsampling phenomenon is that we are interested in why subsampling seems to work when the test distributions are not balanced, as they are artificially in this case. My intuition for that phenomenon is just artifacts of SGD training for neural networks. That subsampling is optimal in this case just follows from the fact that the uncertainty of the minority class is still dominant, and this manifests in these lower bounds. So this answers an undersampling problem, but not the undersampling problem.

clarity,_quality,_novelty_and_reproducibility: * Clearly written.
* Seems high-enough quality.
* Not having read the proofs in detail, it's unclear if there is anything particularly novel.

Update
* Late in the review process, some additional questions around novelty and presentation were raised by other reviewers and the meta-reviewer. I’ve adjusted some scores downward as a result.
summary_of_the_review: * This is a clear, well-typeset paper. The theoretical arguments are nice and should be published, but whether they answer the real questions around undersampling is debatable.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proves that the min-max excess risk of nonparametric classification algorithms is bounded by the number of minority samples when there is a distributional shift between train and test, and therefore concludes that in the worst case, undersampling is optimal unless there is a high degree of overlap between the train and test distributions, or if the algorithm leverages additional structure about the distribution shift. They conducted an experimental case study on a label shift dataset and showed that the test accuracy of robust neural network is constrained by the number of minority samples.
strength_and_weaknesses: Strength:
1. The conclusion of the paper is very interesting in that it shows the optimality of a simple undersampling scheme, and dictates the need to design tailored algorithms that exploit the structure of distributional shift between train and test, instead of aiming to design a universal robust algorithm that is agnostic to the type of distributional shift. This is fairly important to lead to a directional change in designing robust algorithms to deal with distributional shift. 

2. The idea is explained very well, using succinct language to explain complicated mathematical theorems so that it is easy to understand. The theoretical results are also justified well by the experimental studies.  

Weakness:
1. The paper makes the assumption that the test set is balanced. I am curious about whether these results still hold when the test set is somehow also unbalanced, but there still exists some distributional shift between the train and test. When the positive - negative ratio is unknown in the test set, how should undersampling be implemented? In this case, do we prefer other state-of-the-art robust algorithms to undersampling, since the test distribution is unknown?

2. The experiments add evidence in supporting the theoretical results. In Fig. 2, the left pane, why the green curve is only up to 500 samples? Can we add the other half of the green curve? Also, if the green and red curves add the same number of minority samples, we expect their performance to be quite close, based on the theoretical results, right? But why do we still see a performance gap in those plots?

3. The experiments used importance weighted classifiers to demonstrate the importance of minority samples. Personally I am also interested in seeing the comparison of undersampling with other robust algorithms, and to understand whether it is true that simple undersampling (without any importance weighting) performs as good as state-of-the-art. In Section 2, the 2nd paragraph, the authors also mentioned that importance weighting is ineffective when it comes to over-parameterized neural networks. If that's the case, I expect undersampling to outperform importance weighted classifiers.


clarity,_quality,_novelty_and_reproducibility: The paper is written very clearly. The conclusions are novel and could potentially lead to a directional change in the study of distributional shift. 
summary_of_the_review: Overall I am satisfied with the quality of the paper. I think it has a fairly important contribution to guide the research direction in robust algorithms dealing with distributional shift. The theoretical results also nicely supporting their conclusions. The experimental section can potentially be improved, by incorporating a comparison between undersampling and other robust algorithms, and may also be extended to other datasets, classification algorithms such as Random Forest.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies two specific types of the distribution shift, namely label and group-covariance shift, in the context of data imbalanceness. The authors claim that minimax regret bounds for these two types depend directly on the number of training examples from the minority group. They also show that undersampling is minimax optimal (with some additional assumptions in the latter case). A simple experiment illustrates the theoretical findings.

After a long discussion among reviewers, area chairs and PC chairs, we need to state that the paper is unfortunately a bit misleading and ignores many important existing results. The two types of distribution shifts are very different in nature and putting them together may not be the best idea. The label shift shall be rather analyzed from the perspective of loss functions. In fact, the analyzed setting is equivalent to optimization of the balanced accuracy or cost-sensitive 0/1 loss (with costs corresponding to class distribution). Let us notice that minimax results already exist for such loss functions (e.g., Minimax Lower Bounds for Cost Sensitive Classification, https://arxiv.org/pdf/1805.07723.pdf). They can also be given in terms of the number of training examples from the minority class (see Theorem 4 and use costs corresponding to class distribution and replace n by n_min appropriately).

The undersampling is commonly used and in general it is not so surprising that this method can be characterized by strong guarantees. But the reference to the results from other papers need to be done very carefully. It is not entirely clear, for example, what results are given in Table 1 (e.g., what is the exact setting and performance metric). It is also not so easy to find these results in the cited papers. And finally, one of these papers writes:

> SUBY, on the other hand, seems to consistently underperform on the datasets in this paper,
even performing worse than ERM. We therefore don’t recommend its use in practice. One possible
explanation for its poor performance is the fact that worst group samples could easily not be picked
at all during subsampling, because of their small number, and lead to poor performance on those
groups

This seems to contradict the main claim of the authors. 

In general, the paper contains interesting discussion and results worth publishing. On the other hand, the presentation is misleading and important results are ignored. The results are also given for very simplified settings and generalization to more real ones is not so obvious as also confirmed by the authors. Taking the above into account, we cannot accept the paper in the current form.

justification_for_why_not_higher_score: Unfortunately, in the final stage of the reviewing process we noticed several flaws of this submission. As a result of the discussion among reviewers, area chairs and PC chairs we decided to not accept the paper in the current form.
Decision: Reject