Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper points out that minimax excess risk is lower bounded by a function of only the size of the minority group without additional parametric model assumptions or knowledge of the problem at hand. However, an undersampling + binning estimator achieves said lower bound. This implies that using samples from the majority-class/group does not improve, meaning that undersampling is optimal.
strengths_and_weaknesses: The paper targets an important problem and the paper does a very good job pointing out both why undersampling does wonders in many cases and also why further work toward improve OOD should assume more structure. Good work!
questions: I think many existing methods do infact use more structure than is allowed by the theory in the paper. Can the authors comment on what kinds of structure in the existing OOD literature helps do better than the proved lower-bound?
limitations: See questions.
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: The paper studies group-structured distribution shift, in which there exists an identifiable majority and minority group in the dataset. The later group having fewer samples in train time even though at test they are equally likely to be in either group. The paper looks into two specific types of this type of distribution shift. In the case in which the distribution shift is controlled via the balance of labels, the paper proves that the minimax excess risk can be lower bounded with only the size of the minority class samples. They further introduce an undersampled binning estimator which achieves this lower bound up to a constant. The paper also examines group-covariate shift, in which the distribution shift is over the marginal of a feature. In this case the minimax excess risk can be lower bounded, but also requires the ratio of samples (wrt minority / majority groups) and the overlap of group-covariate measures, alongside the size of the minority class samples. Their undersampled binning estimator also has an upper bound on the minimax excess risk, but there is a gap when there is a high overlap in the minority / majority distributions. Simple experiments are presented which are consistent with the theory.
strengths_and_weaknesses: Strength
  - The paper presents lower bounds for the lower bounds for the minimax excess risk for label shift and group-covariate shifts.
  - Their proposed "Undersampled Binning Estimator" are optimal (or optimal in certain scenarios) up to a constant.
  - The explanations and intuition provided of the setting and results.

Weakness
  - There are a few symbols which are not defined and some components in the experiments section which are not clear.
questions: Questions / Comments / Suggestions
1. Is the 1-Lipschitz assumption common? It would be useful for a discussion on if this assumption appears in practice or if its is a common technical assumption.
2. Short definitions / descriptions of $\mathrm{TV}$ and VS loss would be useful for completeness
3. There are short notes about the generalization of Theorem 4.1 and 4.2 for higher dimensions. Does the "1/3" to "1/3d" also hold for corresponding Theorem 5.1 and 5.2?

Minor / Typos
  - There seems to be a few typos / errors in the Appendix, the set of equation below Line 483: (1) on the first line the summation seems to be misplaced; and (2) the second last line seems to be incorrect / should be removed. This doesn't invalidate the proof.
  - In the Appendix, equations below Line 514: "$n_{maj}$" -> "$ n_{min}$"
limitations: Assumptions / limitations of analysis is clear.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: Motivated by the fact that undersampling the majority class remains a competitive approach to learning in the presence of class imbalance, this paper sets out to answer the following question: Is it fundamentally possible to learn a better model than that of undersampling? The paper also considers a related question pertaining to covariate shift, which I am dropping to make the summary concise. To answer this question, the authors prove a lower bound (converse bound) that shows that the number of samples needed to learn a min-max optimal classifier in this setting scales with $n^{-1/3}$. They show a matching upper bound based on undersampling based on which they conclude that undersampling is min-max optimal. The authors provide some experiments that confirm the results. Overall, I like the general positioning of the paper and the story is told nicely. However, I have serious concerns about the main theoretical results of the paper (Theorems 4.1 and 4.2) based on which I recommend the paper to be rejected given that these lower bounds are major contributions of this work.


***** Update ******

The authors clarified my concerns in the rebuttal; in particular, I can see that the proof of Thm 4.1 was suffering from a typo, and the additional details clarified my concerns about the proof of Thm 4.2. As such, I agree with the other two reviewers that this is a significant piece of work and think should be highlighted in the conference (adjusting the score to 8). 
strengths_and_weaknesses: Strengths:
* The authors ask an important question about min-max optimality of undersampling.

* The paper is nicely written, nicely exposed, and the results appear to be novel to me.

* The upper bounds for undersampling are intuitive, and the analysis is nicely done.

Weaknesses:
* The main weakness of the paper lies in the constant $c$ in Theorem 4.1. A closer look at the proof on page 19, line 514, shows that the constant $c = e^{-\frac{n_{maj}}{3 n_{min}}},$ which *does* depend on both $n_{min}$ and $n_{maj}$ as opposed to the general story of the paper. In fact, $c \to 0,$ as $n_{maj} \to \infty$ which contradicts parts of the story of the paper. The only way to keep $c$ to be a constant as $n_{maj} \to \infty$ is to let $n_{min} \to \infty$ with $\frac{n_{maj}}{n_{min}} \to \eta$ for constant $\rho$ in which case the result loses its interestingness because there is no distinguishable difference between $\frac{c}{n_{min}^{1/3}} = \frac{c_2}{n_{maj}^{1/3}}$ for some other constant $c_2$ and the theorem doesn't tell us anything non-trivial about class imbalance. In summary, the lower bound is vacuous unless $\frac{n_{maj}}{n_{min}} \to \eta,$ in which case the lower bound is trivial.

* A similar weakness applies to Theorem 4.2 for any $\tau \in (0,1)$, where $c$ vanishes as $n_{maj} \to \infty$. This can be seen based on the equation on line 637 which vanishes as $n_{maj} \to \infty$. Hence, similarly the lower bound is either vacuous or trivial in this setting as well.

* Since the metric of interest is min-max excess risk, I wonder why the authors didn't consider a min-max baseline (instead of ERM) in this setting; Also smoothened versions of such min-max loss for better generalization, e.g., tilted loss (Li et al 2021): 
Li, T., Beirami, A., Sanjabi, M. and Smith, V., 2021. Tilted empirical risk minimization. ICLR.
I also wonder if these baselines would be subject to the same empirical observations of Figure 2.
questions: * Can you please elaborate on the main weaknesses listed above with respect to the lower bounds in Theorems 4.1 and 4.2? There might be a way to fix this by updating the construction that is considered and working through the details but I was not able to immediately see a way out.

* The proof of Theorems 4.1 and 4.2 are dense. It would be best to give an outline of how the proof goes first. For example, I was confused when $K$ was introduced for the first time, as it was not clear how this was going to be used.
limitations: The main limitation of this paper is that Theorems 4.1 and 4.2 in their current form are either vacuous or trivial (depending on how $n_{maj}$ is related to $n_{min}$), and hence they do not support the narrative of the paper. It is not clear to me how this might be fixed.
review_title: null

Meta-review: metareview: This paper provides bounds and some empirical results on specific distribution shift scenarios, where there is a majority and minority group (group identity is known to the learner) and while at training time data from the two groups is unbalanced at the test distribution is assume to be a balanced mixture. The paper considers two specific scenarios, one where a type of covariate shift and one where a type of label shift is induced.

This submission considers the non-parametric setting, a one-dimensional feature space (examples are assumed to be from [0,1] x {-1, +1}) and Lipschitz continuity for the conditional label probability function. It then analyzes error rates for the above two scenarios and also provides some empirical confirmation that "undersampling", namely subsampling from the majority group so that the two groups are balanced at training time, is minimax optimal.

Given the large literature on learning bounds for domain adaptation (for parametric, but also for non-parametric learning) this submission appears suprisingly unaware of these existing studies and bounds. This literature should be acknowledged and compared to  in details before publication (if the results in here are not in fact just specific cases of known results). I can therefore not support acceptance, despite the reviewers positive recommendations.

Steve Hanneke, Samory Kpotufe:
On the Value of Target Data in Transfer Learning. NeurIPS 2019: 9867-9877

Samory Kpotufe, Guillaume Martinet:
Marginal Singularity, and the Benefits of Labels in Covariate-Shift. COLT 2018: 1882-1886

Christopher Berlind, Ruth Urner:
Active Nearest Neighbors in Changing Environments. ICML 2015: 1870-1879

Shai Ben-David, Ruth Urner:
Domain adaptation-can quantity compensate for quality? Ann. Math. Artif. Intell. 70(3): 185-202 (2014)

Shai Ben-David, Ruth Urner:
On the Hardness of Domain Adaptation and the Utility of Unlabeled Target Samples. ALT 2012: 139-153

Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, Jennifer Wortman Vaughan:
A theory of learning from different domains. Mach. Learn. 79(1-2): 151-175 (2010)

Shai Ben-David, Tyler Lu, Teresa Luu, Dávid Pál:
Impossibility Theorems for Domain Adaptation. AISTATS 2010: 129-136

Shai Ben-David, John Blitzer, Koby Crammer, Fernando Pereira:
Analysis of Representations for Domain Adaptation. NIPS 2006: 137-144


confidence: Certain
Decision: Reject