Undersampling is a Minimax Optimal Robustness Intervention in Nonparametric Classification
Authors: Niladri S. Chatterji
Saminul Haque
Tatsunori Hashimoto
Venue: Accepted by TMLR ()

Abstract: While a broad range of techniques have been proposed to tackle distribution shift, the simple baseline of training on an undersampled balanced dataset often achieves close to state-of-the-art-accuracy across several popular benchmarks. This is rather surprising, since undersampling algorithms discard excess majority group data. To understand this phenomenon, we ask if learning is fundamentally constrained by a lack of minority group samples. We prove that this is indeed the case in the setting of nonparametric binary classification. Our results show that in the worst case, an algorithm cannot outperform undersampling unless there is a high degree of overlap between the train and test distributions (which is unlikely to be the case in real-world datasets), or if the algorithm leverages additional structure about the distribution shift. In particular, in the case of label shift we show that there is always an undersampling algorithm that is minimax optimal. In the case of group-covariate shift we show that there is an undersampling algorithm that is minimax optimal when the overlap between the group distributions is small. We also perform an experimental case study on a label shift dataset and find that in line with our theory, the test accuracy of robust neural network classifiers is constrained by the number of minority samples.

Published in Transactions on Machine Learning Research (06/2023)
Undersampling is a Minimax Optimal Robustness Interven- tion in Nonparametric Classification
Niladri S. Chatterji
miladri@ccsstanffoee
Deportment of Computer Science
Stanford University
Saminul Haque*
saminalh Sattraauhhsssfforooo edu
Deportment Computer Science Stanford University
Tatsunori B. Hashimoto
thashim Sstan ford. edu
Department of Computer Science Stanford University
Reviewed on OpenReview: https: /ttps://opeeeeee wpw.r/vee...e.eee.ooeee net/ forum9 id= r6oHDY0266
Abstract
While broad range of techniques have been proposed to tackle distribution shift, the simple baseline of training on an undersampled balanced dataset often achieves close to state-of- the-art-accuracy across several popular benchmarks. This is rather surprising, since under- sampling algorithms discard excess majority group data. To undorstand this phenomenon, we ask learning is fundamentally constrained by a lack of minority group samples. We prove that this is indeed the case in the setting of nonparametric binary classification. Our results show that in the worst casc, algorithm cannot outperform undersampling unless there is a high degree of overlap between the train and test distributions (which is unlikely to be the case in real-world datasets), or if the algorithm leverages additional structure about the distribution shift. In particular, in the case of label shift we show that there is always an undersampling algorithm that is minimax optimal. In the case of group-covariate shift we show that there is an undersampling algorithm that minimax optimal when the overlap between the group distributions is small. We also perform an experimental case study on label shift dataset and find that in line with our theory, the test accuracy of robust neural network classifiers is constrained by the number of minority samples.
1
Introduction
A key challenge facing the machine learning community is to design models that are robust to distribution shift. When there a mismatch between the train and test distributions, current models are often brittle and
perform poorly on rare examples (Hovy & Søgaard, 2015 Blodgett et al. 2016 Tatman 2017 Hashimoto et al. 2018 Alcorn et al. 2019). In this paper, our focus is on group-structured distribution shifts. In the training sct, we have many samples from a majority group and relatively few samples from the minority group, while during lest time we are equally likely to get a sample from either group.
To tackle such distribution shifts, naïve algorithm is one that first undersamples the training data by discarding excess majority group samples (Kubat & Matwin 1997 Wallace et al. 2011) and then trains a model on this resulting dataset. (see Figure [ for an illustration of this algorithm). The samples that remain in this undersampled dataset constitute i.id. draws from the test distribution. Therefore, while classifier trained on this pruned dataset cannot suffer biases due distribution shift, this algorithm is discards training samples. This perceived inefficiency of undersampling has led the design of several algorithms to combat such distribution shift (Chawla al. 2002 Lipton et. al. 2018
clearly wasteful,

---

Published in Transactions on Machine Learning Research (06/2023)
No Undersampling
Undersampling
Leurned Boundary
Predicted Minority
Minority Samples
Dropped Samples
Predicted Majority
Majority Samples
--
True Boundary
Figure 1: Example with linear models and linearly separable data. On the left we have the maximum margin classifier over the entire dataset, and on the right we have the maximum margin classifier over the undersampled dataset. The undersampled classifier is less biased and aligns more closely with the true boundary.
Sagawa al. 2020 Cao et al. 2019 Menon al. 2020 Ye et al. 2020 Kini et al. 2021 Wang et al. 2022
In spile of this algorithmic progress, the simple baseline of training models on undersampled dalaset remains competitive. In the case of label shift, where one class label is overrepresented in the training data, this has been observed by Cui et al. (2019); Cao et al. (2019), and Yang & Xu (2020). While in the case of group-covariate shift, a study by Idrissi et al. (0022 showed that the empirical effectiveness of these more
complicated algorithms limited.
For example, Idrissi et al. (022)) showed that on the group-covariate shift CelebA dataset the worst-group accuracy of ResNet-50 model the undersampled CelebA dataset which discards 97% of the available
seportance-weighter. ERM (hii- training data is as good as methods that use all of available data such {Liu et al 2021). In Table 1 modaira 2000). Group-DRO (Sagawa et al. 2020) and Just-Train-TTers we report the performance of the undersampled classifier compared to the slate-of-hhe-art-meenne literature across several label shift and group-covarinn shift datasets. We find that, although undersampling isn't always the optimal robustness algorithm, it typically very competitive basclinc and within 1-4% the performance of the best meChod.
in the
Table I: Performance of undersampled classifier compared the best classifier across several popular label shift and group-covariate shift datasets. When reporting worst-group accuracy denote it by *. When available, report the 95% confidence interval. We find that the undersampled classifier is always within 4% of the best performing robustness algorithm, except the CIFAR100 and MultiNLI datasets. In A Appendix we provide more details about each of the results in the table.
Test/ Worst-Group Accuracy
Shift Type
Dataset Paaper
Best
Undersampled
Imb. CIFAR10 (step 10)
Cao et al.
2019
87.81
84.59
Label
Imb. CIFAR100 (step 10)
Cao et al.
2019
59.46
53.08
CelebA Idrissi et al.
2022
86.9 + 1.1*
85.6 + 2.3*
Waterbirds Idrissi et al. 2022
87.6 + 1.6*
89.1 + 1.1*
Croai-Covariate
MuluiNL [Idrissi et al. 2022
78.0 +: 0.7*
68.9 + 0.8*
CivilComments Idrissi al. 2022
72.0 + 1.9*
71.8 + 1.4*
Inspired by the strong performance of undersampling in these experiments, ask:
2

---

Published in Transactions on Machine Learning Research (06/2023)
Is the performance of model under distribution shift fundamentally constmined by the lack of minorily group samples?
To answer this question we analyze the minimar ercess risk. We lower bound the minimax excess risk prove that the performance of any algorithm is lower bounded only as function of the minority samples (nmin). This shows that even if robust algorithm optimally trades off between the bias and the variance, it is fundamentally constrained by the variance on the minority group which decreases only with minn
Our contributions. In our paper, we consider the well-studied setting of nonparametric binary classifi- cation [Tsybakov] 2010). By operating in this nonparametric regime we are able to study the properties of undersampling in rich data distributions, but are able to cireumvent the complications that arise due to the optimization and implicit bias of parametric models.
We provide insights into this question in the label shift scenario, where one of the labels is overrepresented in the training data, Ptrain (y = 1) 2 Ptrain(1 (y = -1), whereas the test samples are equally likely to come from either class. Here the class-conditional distribution P(x | y) is Lipschitz in x. We show that in the label shift setting there is a fundamental constraint, and that the minimax excess risk of any robust learning method is lower bounded by 1/mmmnn 1/3, That is, minority group samples fundamentally constrain performance under distribution shift. Furthermore, by leveraging previous results about nonparametric density estimation (Freedman & Diaconis 1981) show matching upper bound on the excess risk of standard binning estimator trained on an undersampled dataset to demonstrate that undersampling is optimal.
Further, we experimentally show in a label shift dataset (Imbalanced Binary CIFAR10) that the accuracy of popular classifiers generally follow the trends predicted by our theory. When the minority samples are increased, the accuracy of these classifiers increases drastically, whereas when the number of majority samples are increased the gains in the accuracy are marginal at best.
We also study the covariate shift case. In this setting, there has been extensive work studying the effectiveness of transfer (Kpotufe & Martinet] 20188 Hanneke & Kpotufe 2019) from train to test distributions, often focusing on deriving specific conditions under which this transfer is possible. In this work, we demonst that when the overlap (defined in terms of total variation distance) between the group distributions Pa and P& small, transfer is difficult, and that the minimax excess risk of any robust lcarning algorithm lower bounded by 1/nminn 1/3, While this prior work also shows the impossibility of using majority group samples in the extreme case with overlap, our results provide a simple lower bound that shows that the amount of overlap needed to make transfer feasible is unrealistic. We also show that this lower bound is tight, by proving an upper bound on the excess risk of the binning estimator acting on the undersappedd dataset.
Taken together, our results underline the need to move beyond designing "general-purpose" robustness algorithms (like aapportance-eeighting (Cao et al. 2019 Menon et al. 2020 Kini et al. 2021 Wang et al., 2022), g-DRO (Sagawa et al., (020)) JTT (Liu al. 2021). SMOTE (Chawla al. 2002). etc.) that are agnostic to the structure in the distribution shift. Our worst case analysis highlights that to successfully beat undersampling, algorithm must leverage additional structure in the distribution shift.
2 Related work
On several group-covariate shift benchmarks (CelebA, CivilComments, Watcrbirds), Idrissi et al. (2022) showed that training ResNet classifiers on an undersampled dataset either outperforms performs as well other popular reweighting methods like Group-DRO (Sagawa et al. 2020), reweighted ERM, and Just- Train-Twice (Liu et al. 2021). They find Group-DRO performs comparably to undersampling, while both tend to outperform methods that don't utilize group information.
One classic method to tackle distribution shift is importance weighting (Shimodaira 2000). which reweights the loss of the minority group samples to yield an unbiased estimate of the loss. However, recent work (Byrd & Lipton 2019 Xu et al.] 2020) has demonstrated the ineffectiveness of such methods when applied
overparameteriizel neural networks. Many followup papers Caoo et al. 2019 Ye et. al. 2020 Menon et al.
3

---

Published in Transactions on Machine Learning Research (06/2023)
Kini et al. 2021 Wang et al. 2022) have introduced methods that modify the loss function in various ways to address this. However, despite this progress undersampling remains a competitive alternative to these importance weighted classifiers.
2020
Our theory draws from the rich literature on non-parametric classification (Tybakovv 2010 Apart from borrowing this setting of nonparametric classification, we also utilize upper bounds on the estimation error of the simple histogram estimator (Freedman & Diaconis 1981 Devroye & Györfi [985) to prove our upper bounds in the label shift case. Finally, we note that to prove minimax lower bounds we proceed by using the general recipe of reducing from estimation to testing (Wainwright, 2019. Chapter 15). One difference from this standard framework is that our training samples shall be drawn from different distribution than the test samples used to define the risk.
Past work has established lower bounds on the minimax risk for binary classification without distribution shift for general VC classes (scc, e.g., Massart Nédélec. 2006). Note that, these bounds are not directly applicable in the distribution shift setting, and consequently these lower bounds scale with the total number of samples majj min rather than with the minority number of samples (Nmin). There are also refinements of this lower bound to obtain minimax lower bounds for cost-sensitive losses that penalize errors the two class classes differently (Kamalaruban & Williamson, 2018). By carefully selecting these costs it is possible to apply these results in the label shift setting. However, these lower bounds remain loose and decay with n and Aajj in contrast to the tighter Rmin dependence in our lower bounds. We provide a more detailed discussion about potentially applying these lower bounds to the label shift setting after the presentation of our theorem in Section 4.1
There is rich literature that studics domain adaptation and transfer learning under label shift (Maity et al. 2020 and covariate shift (Ben-David et al., 2006 David et al.] 2010 Ben-David et al. 2010 Ben-David & Urner 2012 2014 Berlind & Urner 2015 Kpotufe & Martinet 2018 Hanneke & Kpotufe 2019). The principal focus of this line of work was to understand the value of unlabeled data from the target domain, rather than to characterize the relative value of the number labeled samples from the majority and minority groups. Among these papers, most closely related to our work are those the covariate shift setting [potufe & Martinet 2018 Hanneke & Kpotufe 2011)). Their lower bound results can be reinterpreted to show that under covariate shift in the absence of overlap, the minimax excess risk is lower bounded by 1/mminn 1/3 We provide a more detailed comparison with their results after presenting our lower bounds in Section 4.2
Finally, we note that Arjovsky et al. (022)) recently showed that undersampling can improve the worst-class accuracy of linear SVMs in the presence of label shift. In comparison, our results hold for arbitrary classifiers with the rich nonparametric data distributions.
3 Setting
In this section, we shall introduce our problem setup and define the types of distribution shift that we consider.
3.1 Problem setup
The setting for our study is nonparametric binary classification with Lipschitz data distributions. We are given n training datapoints S ;= [(11,))),... (I Bn)} E ((o, 1] x {)1, that are all drawn from a train distribution Prrain- During test time, the data shall be drawn from different distribution Pres- Our paper focuses on the robustness this shift in the distribution from train to test time. To present clean analysis, we study the case where the features are bounded scalars, however, it is easy to extend our results to the high-dimensional setting.
Given a classifier f [0, (-1,1,, we shall be interested in the test error (risk) of this classifier under the test distribution Prest:
R(f; Ptest) = E Pp [1(((z) + v)].
4

---

Published in Transactions on Machine Learning Research (06/2023)
3.2 Types of distribution shift
We assume that Prrain consists of mixture of two groups of unequal size, and Prest contains equal numbers of samples from both groups. Given majority group distribution Pmaj and a minority group distribution Pmin; the learner has access to maaj majority group samples and min minority group samples:
Smaj
Panj and Smin
PPain min
P
Here Amaj > n2/2 and monn < nn22 with maj + Rmin = n. The full training dataset S = Smaj U ((11, vi)...., (Z }n))- We assume that the learner has access to the knowledge whether a particular sample (z,, yr) comes from the majority or minority group.
The test samples will be drawn from Ptest maj P a uniform mixture over maj and P Thus, the training dataset is imbalanced draw from the distributions Pmaj and P Pmin: whereas the test samples are balanced draws. We let = Mmii//minn > 1 denote the imbalance ratio in the training data. We consider the uniform mixture during Lest time since the resulting lest loss is of the same order as the worst-group loss.
We focus on two-types of distribution shifts: label shift and group-covariate shift that we describe below.
3.2.1 Label shift
In this setting, the imbalance in the training data comes from there being more samples from one class over another. Without loss of generality, we shall assume that the class = 1 is the majority class. Then, we define the majority and the minority class distributions as
P Pmaj(2: y) = P 1) and Pmin P-1(x)1 = -1),
where P-1 are class-conditional distributions over the interval [0, 1]. We assume that class-conditional distributions P; have densities on (0, 1] and that they are 1-Lipschitz: for any x, x. E [0, 1),
(P:(x) Px(x)))
x'|.
We denote the class of pairs of distributions (Pmaj: Pmin) that satisfy these conditions by PLs. We note that such Lipschitzness assumptions are common the literature (see Tsybakov 2010
3.2.2 Group-covariate shift
In this setting, we have two groups {a, b), and corresponding to each of these groups is a distribution (with densitics) over the features Pa(x) and Po(x). We let a correspond to the majority group and b correspond to the minority group. Then, we define
P (ma y) Pa (a) and P Pmin (z. y) (v
We assume that for y E [-,, for all x, x' [0, 1]:
PP æ) P(y xx)] s |z 2'1,
that is, the distribution of the label given the feature is 1-Lipschitz, and it varies slowly over the domain.
To quantify the shift between the train and test distribution, we define notion of overlap between the group distributions Pa and P3 as follows:
Overlap(Pa.. Pb) = 1 TV((a. Ps)
where TV,,., Pa) == su (E) - Po(E), denotes the total variation distance between P., and Pp- Notice that when P. and Po have disjoint supports, TV(P.. ; Pb) = 1 and therefore Overlap Pa. Pb) = 0. On the other hand when P. P.. TV(P Pb) = and Overlap(P.. P,) = When the overlap is 1, the majority and minority distributions are identical and hence we have no shift between train and test. Observe that Overlap(P... P.) Overlap(P Pmin) since P(y x)) is shared across maj and Pmin-
5

---

Published in Transactions on Machine Learning Research (06/2023)
Given level of overlap [0, 1] we denote the class of pairs of distributions (P maj- Pmin) with overlap least T by PGs(T). It is easy to check that, Pas(T) (as((0) at any overlap level E []
Considering a notion of overlap between the marginal distributions Pa(z) and (a(x)) is natural in the group covariate setting since the conditional distribution that we wish to estimate P x) remains constant from train to test. time. Higher overlap between Pa and Ps allows classifier to learn more about the underlying conditional distribution P(y z) when sees samples from either group. In contrast, in the label shift setting P( y) remains constant from train to test time and higher overlap between P( 1) and P(x: -1) does not help to estimate Pyy z).
4 Lower bounds on the minimax excess risk
In this section, we shall prove our lower bounds that show that the performance of any algorithm is con- strained by the number of minority samples minn- Before state our lower bounds, need to introduce the notion of excess risk and minimax excess risk.
Excess risk and minimax excess risk. We measure the performance of an algorithm A through its excess risk defined in the following way. Given an algorithm A that takes as input a dataset S and returns a classifier AS, and a pair of distributions (Pmaj, Pmin) with Prest = Pmjj + 2 P the expected encess risk is given by
Excess Risk[A; (Pmaj Pmnin] = Pp
my x Pnin [R(AS; Ptest)) - R(J"((Pee))) Prest)]
(1)
where (Ptest) test) is the Bayes classifier that minimizes the risk R(: Ptest). The first term corresponds to the expected risk for the algorithm when given maj samples from P maj and R'min samples from P Pmins whereas the second term corresponds to the Bayes error for the problem.
Excess risk does not let us characterize the inherent difficulty of problem, since for any particular data distribution (Pmaj, min) the best possible algorithm to minimize the excess risk would be the trivial mapping A = (Pisst) Therefore, to prove meaningful lower bounds on the performance of algorithms we need to define the notion of minimax excess risk (see Wainwright 2019 Chapter 15). Given class of pairs of distributions P define
Minimax Excess Risk(P) = inf sup
Excess Risk[A: (P Pmin)],
(2)
(Pmmj Pain)E
where the infimum is over all measurable estimators A. The minimax excess risk is the excess risk of the "best" algorithm in the worst case over the class of problems defined by P.
4.1 Label shift lower bounds
We demonstrate the hardness of the label shift problem in general by establishing lower bound on the minimax excess risk.
Theorem 4.1. Consider the label shift setting described in Section 3.2.1 Recall that Pis is the class of pairs of distributions (P (Pmaj. Pmin) that satisfy the assumptions in that section. The minimar encess risk over this class is lower bounded as follows:
Minimax Excess Risk(Pis) = inf sup (mn
Excess Risk[A; (Pmaj Pmii)] 600 Timin 1/3"
We establish this result in Appendix B We show that rather surprisingly, the lower bound on the minimax
excess risk scales only with the number of minority class samples Rmin 1/3 and does not depend on R'mjj
Intuitively, this is bocause any learner must predict which class-conditional distribution (P(x 11) or P(x 1)) assigns higher likelihood that æ. To interpret this result, consider the extreme scenario where Mmaj - oo but mini is finite. In this case, the learner has full information about the majority class distribution. However,

---

Published in Transactions on Machine Learning Research (06/2023)
the learning task continues to be challenging since any learner would be uncertain about whether the minority class distribution assigns higher or lower likelihood at any given x. This uncertainty underlies the reason why the minimax rate of classification is constrained by the number of minority samples 7mmi--
We briefly note that, applying minimax lower bounds from the transfer learning literature Maity et al, 2020, Theorem 3.1 with a = 1, 3 and d d= =) our problem leads to a more optimistic lower bound of 1/n Our lower bounds that scale as 1/mmin 1/3, uncover the fact that only adding minority class samples helps reduce the risk.
As noted above in the introduction, it is possible to obtain lower bounds for the label shift setting by applying bounds from the cost-sensitive classification literature. However, as we shall argue below they are loose and predict the incorrect trend when applied in this selting. Consider the result (Kamalaruban & Williamson 2018 Theorem 4) which is a minimax lower bound for cost sensitive binary classification that applies to VC classses (which does not capture the nonparameteric sctting studied here but it is illuminating to study how that bound scales with the imbalance ratio p "mmaj/mmin): Assume that the joint distribution during training is mixture distribution given by P I 1 Pmmi that average the ratio of the number of samples from the majority and minority class is equal to p. Then by applying their lower bound we find that it scales with 1/(mp) (see Appendix E for detailed calculation). This scales inversely with p the imbalance ratio and incorrectly predicts that the problem gets easier as the imbalance is larger. In contrast, our lower bound scales with 1/mmin = (1+ p)/n, which correctly predicts that as the imbalance larger, the minimax lest error is higher.
4.2 Group-covariate shift lower bounds
Next, we shall state our lower bound on the minimax excess risk that demonstrates the hardness of the group-covariate shift problem.
Theorem 4.2. Consider the group shift selling described in Section 3.2.2 Given any overlap t E [0, 1] recall that (T) is the class of distributions such that Overlap(P maj, P min) 2 r. The minimar encess risk in this setting is lower bounded as follows:
Minimax Excess Risk Risk(Pos(T)) = inf sup
Excess Risk[A; (P maj; Pmin)]
A (Pmaj Pain Pain)
(4)
200 (0min (2 - T) + mmaj T)1/3 200m 1/3 T 2)1/3*
where p /mmaj/ /imin >> 1.
We prove this theorem in Appendix C
We see that in the low overlap setting (7 < 1/p), the minimax excess risk is lower bounded by 1/ 1/rmin 1/3 and are fundamentally constrained by the number of samples in minority group. To why this is the case, consider the extreme example with 0 where P. has support [0, 0.5] and P, has support [0.5, 1). The m'aj majority group samples from Pa provide information about the correct label predict in the interval [0, 0.5) (the support of P.). However, since the distribution P(y x) is 1-Lipschitz in the worst case these samples provide very limited information about the correct predictions in [0.5, 1] (the support of Ps). Thus, predicting on the support of Po requires samples from the minority group and this results in the m'mn dependent rate. In fact, this extreme case (r (r=00 0) even Mmaj -> 00, the minimax excess risk still bounded away from zero. This intuition also carries over to the case when the overlap is small but non-zero and our lower bound shows that minority samples are much more valuable than majority samples at reducing the risk.
On the other hand, when the overlap is high (r > 1/p) the minimax excess risk is lower bounded by 1/(niiin2 (2 - T) + 1//3 and the extra majorily samples are quile beneficial. This is roughly because the supports Pa and Ps have large overlap and hence samples from the majority group are useful in helping make prodictions even regions where P, is large. In the extreme case when 1, we have that P. P, and therefore recover the classic i.idd setting with no distribution shift. Here, the lower bound scales with 1/3 one might expect.
7

---

Published in Transactions on Machine Learning Research (06/2023)
Previous work transfer learning with covariate shift has considered other more elaborate notions of trans- ferability (Kpotufe & Martinet 2018 Hanneke & Kpotufe 2019) than overlap between group distributions considered here. In the case of no overlap (r = 0), previous results (Kpotufe & Martinet 2018 Theorem 1 with a = B = 0 and y o0) yield the same lower bound 1/mmin 173, On the other extreme, applying their result. potule & Martinel, 2018 Theorem with a 1, = and y = 0) in the high transfer regime yields a lower bound on 1/n This result aligned with the high overlap here.
case that we consider
Beyond these two edge cases of no overlap (r 0) and high overlap (r = 1), our lower bound is key to drawing the simple complementary conclusion that even when overlap between group distributions is small as compared to 1/p, minority samples alone dictate the rate of convergence.
5 Upper bounds on the excess risk for the undersampled binning estimator
We will show that an undersampled estimator matches the rates in the previous section showing that under- sampling an optimal robustness intervention. We start by defining the undersampling procedure and the undersampling binning estimator.
Undersampling procedure. Given training data S = {(11, v1), (Fn, generate new undersam- pled dataset Sus by
including all min samples from Smin and,
including mmin samples from Smaj by sampling uniformly at random without replacement.
This procedure ensures that in the undersampled dataset Sus; the groups are balanced, and that |Sus| mmn
The undersampling binning estimator defined next will first run this undersampling procedure to obtain Sus and just uses these samples to output a classifier.
Undersampled binning estimator The undersampled binning estimator Ausa takes as input dataset S and positive integer K corresponding to the number of bins, and returns classifier A [0, 1] - 1), This estimator is defined as follows:
First, we compute the undersampled dataset Sus-
Given this dataset. Sus, let my be the number of points with label +1 that lie in the interval ( kl. Also, define n-1. analogously. Then set
{
1
if fin > n- otherwise.
A
3. Define the classifier S.K such that if I, then
A (x) As-
(5)
Essentially in each bin L5 we set the prediction to be the majority label among the samples that fall in this bin.
Whenever the number of bins K is clear from the context we shall denote AS.. by ASse- Below we establish upper bounds the excess risk of this simple estimator.
8

---

Published in Transactions on Machine Learning Research (06/2023)
5.1 Label shift upper bounds
We now establish upper bound the excess risk of AusB in the label shift setting (see Section 3.2.1 Below we let e, C > O be absolute constants independent of problem parameters like Raaj and Ammn-
For any (P majs mmnn) E PLs the expected encess risk of the Undersampling Binning Estimator (Eq. 5 with number of bins with K cf emmmmn 1/3 is upper bounded by
Theorem 5.1. Consider the label shift setting described in Section 3.2.1
C
Excess Risk[AAus:: (Pmaj Pmin]] S. "mai xP "imin [R(AusB: Prest) R(f";
Pomin
1/3"
We prove this result in Appendix This upper bound combined with the lower bound in Theorem 4.1 shows that undersampling approach is minimax optimal up to constants in the presence of label shift.
Our analysis leaves open the possibility of better algorithms when the learner has additional information about the structure of the label shift beyond Lipschitz continuity.
5.2 Group-covariate shift upper bounds
Next, we present our upper bounds on the excess risk of the undersampled binning estimator in the group- covariate shift setting (see Section 3.2.2) In the theorem below, C' > 0 is an absolute constant independent of the problem parameters Aaaj Amin and т.
Theorem 5.2. Consider the group shift setting described in Section 3.2.2 For any overlop T E [0, and for any (Pmaj Pmin) E (TG the expected excess risk of the Undersampling Binning Estimator (Eq. 55 with number of bins with K [ 1/31
Excess Risk[AusB: (P maj: Pmin)] = E S~ x P [[(AUSB: Prest) - R(f"; S
Ammin 1/3"
We provide a proof for this theorem in Appendix C Compared to the lower bound established in Theorem 4.2 which scales as 1/ ((2 Minn + Amaaj7) 1/3 the upper bound for the undersampled binning estimator always scales with m/ 1/3 since it operates the undersampled dataset (Sus).
Thus, we have shown that in the absence of overlap (r & 1/p mmmn mmin/nmaj) there is undersampling algorithm that is minimax optimal up to constants. However when there is high overlap (T >> L/p) there is a non-trivial gap between the upper and lower bounds:
Upper Bound
c(p 2)
Lower Bound
6 Minority sample dependence in practice
Inspired by our worst-case theoretical predictions in nonparametric classification, we ask: how does the accuracy of neural network classifiers trained using robust algorithms evolve as a function of the majority and minority samples?
To explore this question, we conduct a small case study using the imbalanced binary CIFAR10 dataset (Byrd & Lipton 2019 Wang al. 2022) that is constructed using the "cat" and "dog" classes. The test set consists of all of the 1000 cat and 1000 dog test examples. To form our initial train and validation sets, we take 2500 cat examples but only 500 dog examples from the official train set, corresponding to a 5:1 label imbalance. We then use 80% of those examples for training and the rest for validation. In our experiment, we cither (a) add only minority samples; (b) add only majorily samples; (c) add both majority and minority samples in 5:1 ratio. We consider competitive robust classifiers proposed in the literature that are convolutional neural networks trained either by using (i) the importance weighted cross entropy loss, or (ii) the importance weighted VS loss (Kiii et al. 20211). We early stop using the importance weighted validation loss in both cases. The additional experimental details are presented in Appendix G
9

---

Published in Transactions on Machine Learning Research (06/2023)
Cross Entropy Loss Importance Weighted Classifiers
68
Only Majority
Test Accuracy (%)
Proportional Increase
66
64-
64-
62-
62
Only Minority
60
Proportional Increase
500
1000
1500
500
1000
1500
2000
Extra Minority Samples Added
Extra Majority Samples Added
VS Loss Importance Weighted Classifiers
68
68
Only Majority
Propottional Increase
Accuracy
66
66
64
64
62
Only Minorily
62-
Proportional Incrense
60
60
500
1000
1500
500
1000
1500
2000
Extra Minority Samples Added
Extra Majority Samples Added
Figure 2: Convolutional neural network classifiers trained on the Imbalanced Binary CIFAR10 dataset with 5:1 label imbalance. (Top) Models trained using the importance weighted cross entropy loss with carly stopping. (Bottom) Models trained using the importance weighted VS loss (Kini et al. 2021) with early stopping. We report the average test accuracy calculated on a balanced test set over 5 random seeds. We start off with 2500 cat examples and 500 dog examples in the training datasct. We find that in accordance with our theory, for both of the classifiers adding only minority class samples (red) leads large gain accuracy (~ 6%), while adding majority class samples (blue) leads to little no gain. In fact, adding majority samples sometimes hurts test accuracy due to the added bias. When we add majority and minority samples in 5:1 ratio (green), the gain is largely due to the addition of minority samples and is only marginally higher (< 2%) than adding only minority samples. The green curves correspond to the same classifiers in both the left and right panels.
Our results in Figure 2 are generally consistent with our theoretical predictions. By adding only minority class samples the test accuracy of both classifiers increases by great extent (6%), while by adding only majorily class samples the lest accuracy remains constant or in some cases even decreases owing to the added bias of the classifiers. When we add samples to both groups proportionately, the increase in the test accuracy appears to largely to be due to the increase in the number of minority class samples. We see this on the left panels, where the difference between adding only extra minority group samples (red) and both minority and majority group samples (green) is small. Thus, we find that the accuracy for these neural network classifiers is also constrained by the number of minority class samples. Similar conclusions hold for classifiers trained
using the tilted loss (Li et al. 2020 and group-DRO objective (Sagawa et al. 2020 (see Appendix Dj.
7 Discussion
We showed that undersampling is an optimal robustness intervention in nonparametric classification in the absence of significant overlap between group distributions or without additional structure beyond Lipschitz continuity. We worked in one dimension for the sake of clarity and would be interesting extend this study to higher dimensions. We focused on Lipschitz continuous distributions here, but is also interesting to consider other forms of regularity such Hölder continuity.
10

---

Published in Transactions on Machine Learning Research (06/2023)
At high level our results highlight the need to reason about the specific structure in the distribution shift and design algorithms that are tailored to take advantage of this structure. This would require to step away from the common practice in robust machine learning where the focus is to design "universal" robustness interventions that are agnostic to the structure in the shift. Alongside this, our results also dictate the need for datasets and benchmarks with the propensity for transfer from train to lest time.
Acknowledgments
We would like to thank Ke Alexander Wang for his useful comments and feedback in the early stages of this project. We would also like to thank Shibani Santurkar and Dimitrios Tsipras for useful discussions and encouragement. Finally, we would like to thank the anonymous reviewers whose many helpful comments improved the paper. NC was supported by a SAIL Postdoctoral Fellowship and TH was supported by gift from Open Philanthropy.
References
Michael Alcorn, Qi Li, Zhitao Gong, Chengfei Wang, Long Mai, Wei-Shinn Ku, and Anh Nguyen. Strike (with) pose: Neural networks are easily fooled by strange poses of familiar objects. In Computer Vision and Pattern Recognition (CVPR), 2019.
Martin Arjovsky, Kamalika Chaudhuri, and David Lopez-Paz. Throwing away data improves worst-class error in imbalanced classification. arXiv preprint 10X1:22255.1672, 2022.
Shai Ben- Devid and Ruth Urner. On the hardness of domain adaptation and the utility of unlabeled target samples. In Algorithmic Learning Theory (ALT), 2012.
Shai Ben-Davie and Ruth Urner. Domain adaptation can quantity compensate for quality? Annals of Mathematics and Artificial Intelligence, 2014.
Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. In Advances in Newral Information Processing Systems (NewrIPS), 2006.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 2010.
Christopher Berlind and Ruth Urner. Active nearest neighbors in changing environments. In International Conference Machine Learning (ICML), 2015.
Su Lin Blodgett, Lisa Green, and Brendan O'Connor. Demographic dialectal variation in social media: A case study of african-american english. In Empirical Methods in Natural Language Processing (EMNLP), 2016.
Jonathon Byrd and Zachary Lipton. What is the effect of importance weighting in deep learning? In International Conference on Machine Learning (ICML), 2019.
Clément Canonne. A short note on an inequality between KL and TV. arXiv preprint arXiv:2202.07198 2022.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with babel-distribution-wwaar margin loss. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Nitesh Chawla, Kevin Bowyer, Lawrence Hall, and Philip Kegelmeyer. Smote: Synthetic minority over- sampling technique. Journal of Artificial Intelligence Research, 2002.
Yin Cui, Menglin Jia, Tsung-Yi Yi Lin, Yang Song, and Serge Belongie. Class-balanced loss based on effective number of samples. In Computer Vision and Pattern Recognition (CVPR), 2019.
Shai Ben David, Tyler Lu, Teresa Luu, and Dávid Pál. Impossibility theorems for domain adaptation. In International Conference on Artificial Intelligence and Stalisties (AISTATS), 2010.
11

---

Published in Transactions on Machine Learning Research (06/2023)
Luc Devroye and László Györfi. and Mathematical Statistios, 1985.
Nonparometric density estimation: the L1 view. Wiley Series in Probability
David Freedman and Persi Diaconis. On the histogram as density estimator: Lg theory. Zeilschrift für Wotrscheinlcckeisshheerie und verwandte Gebiete, 1981.
Steve Hanneke and Samory Kpotufe. On the value of target data in transfer learning. In Aduances in Neural Information Processing Systems (NewrIPS), 2019.
Tatsunori Hashimoto, Megha Srivastava, Hongsook Namkoong, and Percy Liang. Fairness without demo- graphics in repeated loss minimization. In International Conference Machine Learning (ICML), 2018.
Dirk Hovy and Anders Søgaard. Tagging performance correlates with author age. In Association for Com- putational Linguistics (ACL., 2015.
Badr Youbi Idrissi, Martín Arjovsky, Mohammad Pezeshki, and David Lopez-Paz. Simple data balancing achieves competitive woss-group-acccraacy In Causal Learning and Reasoning, 2022.
Parameswaran Kamalaruban and Robert Williamson. Minimax lower bounds for cost sensitive classification.
arXiv preprint Xrxi 077237 2018.
Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak, and Christos Thrampoulidis. Label- imbalanced and group-sensitive classification under overparameeterization.. In Advunces in Newral Infor- mation Processing Systems (NeurIPS), 2021.
Samory Kpotufe and Guillaume Martinet. Marginal singularity, and the benefits of labels in covariate-shift. In Conference On Learning Theory (COLT), 2018
Miroslav Kubat and Stan Matwin. Addressing the curse of imbalanced training sets: one-sided selection. In International Conference on Machine Learning (ICML), 1997.
Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. Tilted empirical risk minimization. International Conference on Learning Represenlations (ICLR), 2020.
Zachary Lipton, Yu-Xiang Wang, and Alexander Smola. Detecting and correcting for label shift with black box predictors. In International Conference on Machine Learning (ICML), 2018.
Evan Liu, Behzad Haghgoo, Annie Chen, Aditi Raghunathan, Pang Wei Koh, Shiori Sagawa, Percy Liang, and Chelsea Finn. Just train twice: Improving group robustness without training group information. In International Conference on Machine Learning (ICML), 2021.
Subha Maity, Yuekai Sun, and Moulinath Banerjee. Minimax optimal approaches to the label shift problem.
arXiv preprint arXi::2003.100 104433 2020.
Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. Annals of Statistics, 2006.
Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar. Long-tail learning via logit, adjustment. In International Conference on Learning Representations (ICLR), 2020.
Shiori Sagawa, Pang Wei Koh, Tatsunori Hashimoto, and Percy Liang. Distributionally robust neural networks. In International Conference on Learning Representations (ICLR), 2020.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log-likelihood function. Journal of Stalistical Planning and Inference, 2000.
Rachael Tatman. Gender and dialect bias in youtube's automatic captions. In ACL Workshop on Ethics in Natural Language Processing, 2017.
Alexandre Tsybakov. Introduction to Nonparametric Estimation. Springer, 2010.
12

---

Published in Transactions on Machine Learning Research (06/2023)
Martin Wainwright. High-dimensional statistics: A non-asymptotic vieupoint. Cambridge University Press, 2019.
Byron Wallace, Kevin Small, Carla Brodley, and Thomas Trikalinos. Class imbalance, redux. In International Conference on Dala Mining (ICDM), 2011.
Ke Alexander Wang, Niladri Chatterji, Saminul Haque, and Tatsunori Hashimoto. Is importance weighting incompatible with interpolating classifiers? In International Conference on Learning Representalions (ICLR), 2022.
Larry Wasserman. Lecture notes nonparametric classification, 2019. URL https://www stat. cmu. edu/ larry//aam//onnaaclaass. pdf
[Online; accessed 12-May-2022)
Wikipedia
contributors. Poisson binomial distribution Wikipedia, the free encyclopedia,
phpptitle=PPisson htt.ooiisssonnimmmaaaalaal bww.mial.ddia................lla distributionk 2022. URL https://en wikipedia. http:://ww...ooppppooooooooooaao
01did=1071847908 (Online; accessed 5-May-2022).
Da Xu, Yuting Ye, and Chuanwei Ruan. Understanding the role of importance weighting for deep learning. In International Conference on Learning Representations (ICLR), 2020.
Yuzhe Yang and Zhi Xu. Rethinking the value of labels for improving class-imbalanced learning. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Han-Jia Ye, Hong- You Chen, De-Chuan Zhan, and Wei-Lun Chao. Identifying and compensating for feature deviation in imbalanced deep learning. arXiv preprint 01155 2020.
A
Technical tools
In this section we avail ourselves of some technical tools that shall be used in all of the proofs below.
A.1 Reduction to lower bounds over finite class
The lower bound on the minimax excess risk will be established via the usual route of first identifying a "hard" finite set of problem instances and then establishing the lower bound over this finite class. One difference from the usual setup in proving such lower bounds (see Wainwright 2019 Chapter 15) is that the training samples are drawn from an imbalanced distribution, whereas the test samples are drawn from balanced one.
Let P a class of pairs of distributions, where each element (Pmajs Pmin) E P is a pair of distributions over [0, 1] x 11,, As before, we let Prest denote the uniform mixture over Pmajj and Pmin- We let V denote finite index set. Corresponding to each element v E there P (P P.emaaj. Pu.min) P with P u,test (.am Pr. p/, Finally, also define pair of random variables (V, follows:
1. V is uniform random variable over the set V.
2. (S V = =) P e.maj
x Peeie u.min is an independent draw of Rmmjj samples from P Puymaj and 1mmin samples
from P Pa,min-
We shall let Q denote the joint distribution of the random variables (V.S), and let Qs denote the marginal distribution of
With this notation in place, we now present a lemma that lower bounds the minimax excess risk in terms of quantities defined over the finite class of "hard" instances P...
13

---

Published in Transactions on Machine Learning Research (06/2023)
Lemma A.1. Let the random variables (V be defined above. The minimar cocess risk is lower bounded follows:
Minimax Excess Risk(P) inf sup A (Pmaj.Pmin) PmilEP
E Pmmp "min maj
[R(AS; (R(f((Ptest) Poest)
mm
2 Fl Bv,
where Ry and Bayes-error By are defined as
Ry == Es-Qs linl
Pr
(h(x)) + v)).
(x.,))~ -..vv Q(vlS)Pu.er
By Ev(R(f* (Ptttes)): Pv,test)]
Proof. By the definition of Minimax Excess Risk,
Minimax Excess Risk inf (Prsy.Pmn Pmp
sup
E S
[R(AS; Ptest]] RR( Prest)
my
2 inf sup B.
pmp m,my
"my
xP"min s.mi
[R(AS; Pe,, Pe,test) )]
RRS" (P,tet() Pj Pe,test)
vEV
inf Ey
E
mmay Vimu
x P
[R(A4: Pv.cest]
(R(ff((V,,eest) Piieestt@PPeeeeee Pr,test)]
Vimin
inf Ev [E Ppie Miii
[R(AS; ; PV )ll
Ev[R(f (P vitest:: P Pv,test)
We continue lower bounding the first term as follows
inf Ev [ SSV
inf E (V.))~al V. x [R(A; Py.tes))
Pr
(A9 # y)]
A
A Pv.
inf RufEssqe Bv-Q(-19) (a
Pr
(A (x) + y)1
A
(4)
Es-qu linl Ev-Q(s)))
Pr (2.0))- Pyuse
(h(x) + v)]l
Es-Qs linf
Pr
(h(x) + y)]
(n,y)~ Σ. Q(vlS))
= Ry.
where (i) follows since A is a fixed classifier given the sample set S. This, combined with the previous equation block completes the proof.
A.2 The hat function and its properties
In this section, we define the hat function and establish some of its properties. This function will be useful in defining "hard" problem instances prove our lower bounds. Given positive integer K the hat function is defined
x
for
2K 0 [0,
4K
4K
Ox (x)
=
IK
1
x
4K
for otherwise.
2k
(6)
When K is clear from context, we omit the subscript.
14

---

Published in Transactions on Machine Learning Research (06/2023)
Hat Function (04)
-0.2
-0.1
0.1
Figure 3: The hat function with K = 4.
We first notice that this function I-Lipschitz and odd, so
Φx (x)x) dr = 0.
2
We also compute some other key quantitics for Φ.
Lemma A.2. For any positive integer K,
bx(()) dr 8K2
Proof. We suppress K in the notation. We have that,
[o(z) dr = {
1
+
dr +
dx.
4K
4K
4K
4K
2X
The integrand has area 16K2. Therefore,
4K + over x [-
2R 0] defines a triangle with base
1
and height 1
Tk thus it
2k
x +
dr 16K
4K
4K
The same holds for the second term. Thus, by adding them up we get that fax
[0(x) dx .ズ
Lemma A.3. For any positive integer K,
f log
1 + Φx (x - 2k)
2K ))
1
1 I+ ΦK
x
dz - 3K3
Φx 2x1
and
x log
dx (x 2k)
2K ))
1
Jo
Φx
+
dx S 3k3
1 Φx (x 2イ
15

---

Published in Transactions on Machine Learning Research (06/2023)
Proof. Let us suppress K in the notation. We prove the first bound below and the second bound follows by identical argument. We have that
k log
1 1 + 6(x
1
1 - Φ(I
2K
1
1 1
x 2K
dr
2k
オ
1 + (bx)
log
(1 + +(()) dr
1 - Φ(x)
IN
IK
1 + x(x))
1 + v(x))
log
(1 +xx)) dr +
log
(1 +(z)) da
x(x)
1- x(x))
II
1 ((x)
1 ((-z) 11- ((=x)-x)
log
(1 + σ(x)) dr
log
(1 + o( (-=)) dx
0
1 - 6(x)
2K
1 6(x)
IK
1- (-)((z)
log
(1 ((x)) dr +
log
(1 - o(z)) dr,
((x)
1+ ((z))
where the last equality follows since @ is an odd function. Now, we may collect the integrands to get that,
x
1 1+
2k
1 11
log
1 1
dr
1 6(x
2K
2K
IK
+ x(x))
2
log
δ(x) dx
1 - x(x)
I
1+ 20(x)
2
log
1-0(z) 6(x) dr
0
20(x)²
< 2 0
dx,
((x)
where the last incquality follows since log(1 + x) I for all x. Now we observe that x(x) S S
2 for
[0, } and in particular, [-p(z) 1 2. Thus,
1 + Φ( 2k
1 ) dx 2K
log
1 Φ
1 olx IR
8
2xx)² dr
< 8
x² dæ
Jo
1
3K3
This proves the first bound. The second bound follows analogously.
B Proofs in the label shift setting
Throughout this section we operate in the label shift setting (Section 3.2.1
First, in Appendix B.1 through a sequence of lemmas we prove the minimax lower bound Theorem 4.1 Next,
in Appendix B.2 we prove Theorem 5.1 which an upper bound on the excess risk of the undersampled
binning estimator (see Eq. (5) with Amin 1/3 bins by invoking previous results on nonparametric density
estimation Freedman & Diaconis 1981 Devroye & Györfi 1985
B.1 Proof of Theorem 4.1
In this section, we provide proof of the minimax lower bound in the label shift setting.
16

---

Published in Transactions on Machine Learning Research (06/2023)
We will proceed by constructing class of distributions where the separation between any two distributions in the class is small enough such that it is hard to distinguish wetween them with finite minority class samples. In particular, we split the interval [O, 1] into sub-intervals and each class distribution on each sub-interval either has slightly more probability mass on the left side of the sub-interval, on the right, or completely uniform. Since the minority class sample size limited, no classifier will be able to tell which distribution the minority class is generated from, and hence will suffer high excess risk.
We construct the "hard" set of distributions follows. Fix K to be integer that will be specified in the sequel function of Remin Let the index set be == [-1, 13 {-1,0,1}*, For V, we will let 01 E (-1,0,13) 13* be the first K coordinates and 8- [-1,0,1] be the last K coordinates. That is, V (U1,
For every E P we shall define pair of class-conditonnal distributions P.,1 and Po,-1 as follows: for x E 13 [211 k..
I j 1/2
Po,1(x) = 01.00
K
j + 1/2
(,,-(())= = 1 1-
4 K
where is defined in Eq. continue to define
Notice that Pe,1 only depends vi while Pe,-1 only depends 8-1. We
P Pu,maj (2, y) = P.. (x)
P Pu,min (I, y) P Pu.-1(x)1(3 = -1),
and
P Po,maj(Ir u) + Po.min((, (z) = 1) (t) -1)
=
P Pattest (z. y)
2
2
Observe that the test distribution
equally likely for the label to be +1
Recall that as described in Section A.1 V shall be uniform random variable over V and S V Pm v,min We shall let Q denote the joint distribution of (V, and let Qg denote the marginal over S. With this construction in place, we first show that the minimax excess risk is lower bounded as follows.
PRiin
Lemma B.1. For any positive integers K, nmaj. Ronin the minimar ercess risk is lower bounded as follows:
Minimax Excess Risk
inf
sup A (Pmmg (Pmmj.Piin Prin) EPLs
g Praal mai
E
|R(AS: Prest) R(f": Prest)
min
S)) u, ΣQ(e Q(v S)P sSPp )
EsNas
TV
Σ
EQ(u
Q(u |
(7)
36K
DEV
"EV
Proof. By invoking Lemma A.1 we get that
Minimax Excess Risk(
Es-Qs linf h (a.))~ uev Q(v|S)Pe..u
Pr
(h(x) * v)1
(Pv.est): Ev [ (P : P Pv,test))
=:B
=:9tv
We proceed by calculating alternate expressions for Ry and By get our desired lower bound on the minimax excess risk.
17

---

Published in Transactions on Machine Learning Research (06/2023)
Calculation of Ry: Immediately by Le Cam's lemma (Wainwright 2019 Eq. 15.13), get that
Ry Es-Qs
inf
Pr Eoer
(h(x) # v)
(2.9))~
Qio P w.t
1 Bsnas
1-TV TV
Σ Q(v SS) e,l,
Σ Q(u -S)Pe.-))
(8)
VEV
Calculation of By: Again by invoking Le Cam's lemma Wainwright 2019 any class conditional distributions PI, P-1,
Eq. 15.13), we get that for
1 TV(P,,
R(F"; Prest)
2
So by taking expectations, we get that
1
By = Ev (Prett)) Pv.test) = Ev
(VI,,,,
(9)
2 2
We now compute Ev (VVVVVPP... (v.y(,,,,,,,... as follows:
1
Ey
- Ev
[Pv;((r) Pv)-1(x) dz
am0
+ 1/2
Ev
VV V-
dr
2
1
K
1
*
(x (x- 1/2
EV
V1. -V-1al 10
dr
2
K
j=1
Ey [VV - V-1.jl.
16K
where (2) follows by Lemma A.2
Observe that V1,5, V-1ø are independent uniform random variables on {-1, 11, it therefore straightforward to compute that
8 Ev[[Vi V-1 9"
This yields that
By (IV(Pv.,PPy.-ll 18K
Plugging this into Eq.
9 allows us to conclude that
1 (1
By = Ey [R(f" (Pv,te)) Pvttes)]
(10)
2
18K
Combining Eqs. S and 10
establishes the claimed result.
In light of this previous lemma we now aim to upper bound the expectod total variation distance in Eq. Lemma B.2. Suppose that is drawn uniformly from the set 1 and that S is drawn from
P PR U.maj
X Paonn
v.min then,
EQ(1) s)Po...) )
Es
TV Σ Q(v Q(v
S)P,,,s
1
exp (-
Ammn 3K3
18K
144K
WEV
NEV
18

---

Published in Transactions on Machine Learning Research (06/2023)
Proof. Let v Es
TV (E
Q(v ()P,s E. Q(u s Then,
Σ Q(v s)P,,,, ΣQ(U s)Pe
Es
TV
WEV
VEV
Es
Σ
Q(v 8) (P),(()) - Pv, Pv,-1(z)) de
2 Es
==
NEV
Σ Q(u (P,,((() Po,- dr
REV
Σ Q(u ()) 2-1.j0 x (+ DEV
Es
dx
2
K
K
where the last equality is by the definition of Po,1 and Pe.-1. Continuing we get that,
j + 12/ dr Es
x
Σ VEV
Q(u S)(12, 2-1.))
2
K
Σ Q () - v-1s)
Es
16K
IVE
K
1
Q [S) v-15))
dQs(S)
16K
/=1
VEV
K
(1 - --11)) ds
16K²
/=1
IVE
Σ/
Σ
Q(S w) - v-15)
ds,
16K
V
BEV
where (i) follows by the calculation in Lemma A.2 and (ti) follows since v is uniform random variable over the set V.
The distributions Po,1 and Po.-1 are symmetrically defined over all intervals 1, = 1 $1. and hence all of the summands in the RHS above are equal. Thus,
/
Σ ((S) v11)) as.
(11)
16
NEY
Before we continue further, let us define
y = E
U1,1 v-1.)
19

---

Published in Transactions on Machine Learning Research (06/2023)
For every E V+, let i E V be such that is the same all coordinates, except U1,1 -111 and 1-1,1 = 1-111 Then continuing from Eq. 11 we find that,
Σ
(1111 (111- u) Q(5 6)) ds
1
NEVV
Σ
(11,1 --1,1 v) Q 6) ds
16K|V|
VEV+
1
(V1,1 v-1,)) / |Q(S) (((S)))) Q(S) B) as
16K
EEVI
(0111 - -VLL)) e), Q(S) B)),
(12)
8K
VEVT
where (i) we use the definition of V and 8, (ii) follows since 11 v-1,1 for V+.
Now we further partition V into 3 sets V(1.0), 100-1), v(1,-1) follows
((10) {UE V U1 U,, = 0},
1(0,1) = = V Un = 0,0-1,1 = -1},
((1-1) = -VEE V1 1,0-1,1 -1}
Note that Q(S v) =
Mmjj maja
x Piimin w.ming and therefore
E Σ
(01,1 1.I, (P"
v,maj
X Pilmis
v.min:
P Pmmal U.maj
P
B.min
EEV+
Σ
TV
(P Tmng
u.maj
x P Pumin v.min
B.maj
X Primin 8.min
vEVaL
Σ
TV (Pmaaa
Pitmin e.min
P Plmma 0.maj
P.mmin
vE
+2
Σ
TV
v.maj
X Punis
v.min:
Pimai E.maj
Pimmn
R.min
(13)
-)
where (1) follows since 0-1
1-1 E (-1,0, and by the definition of the sets (11.0), v(o.1) and (11--1)
Now by the Bretagnolle Huber inequality (see Canonne 2022
Corollary 4),
TV (P" Penj
e.maj
x PM e.min?
Pumjj G.maj
X
Pummis G,min)
= TV (P Pinj
B,maj
x Pr " 6,min? e,maj
x Puiie v.min
1
2 exp (-KL (P
Pimai m.
Piim
Imnaa n,maj X p,min
where we flip the arguments in the first step for simplicity later. Next, by the chain rule for KT-divergence, we have that
KL maja x paninn 1
Prlwis = KL (amalllP.mma)) + m'in (LiinLLPa.. (Pv.mim
6,min
Using these, let us upper bound the first term in Eq. 13 corresponding E (00,-)) For E V(0,-1), notice that KT.(Pi,ma)) (Pa.majll maj) 0 since Vi.j Ui.j for all (1,..., K). For the second term, KT, r.min [P min.m.).
20

---

Published in Transactions on Machine Learning Research (06/2023)
only 01 and 01,2 differ, so
/ P (r)-1())log log
P (r.- dx
PL I P..min) =
Pr.-1(I)
! log
1 Øx (x 2k
(1+ Φx
2x ))
x
dx
1 Φx (x 2k
3バ3
where the last inoquality result of the calculation in Lemma A.3 Therefore, we get
Σ
TV
(P
P v.min
Pomg E,maj
X
Prmm E,min
S -gk-1
1
1
exp
1mmn
2
3K3
vEVIO,
1)
For the lerms in Eq.
13
corresponding to D(U,-1), v(1,-1,, we simply take the trivial bound to get
Σ
TV
(Pr u.maj
x Pitmn u.min
Pimaj 8.maj
S g
0,min
V
Σ
TV (P"mm
u.maj
X P Pmn
mini
P Pimaj
m.maj
Pilmin
8.min I <9K-1
vEva,
Plugging these bounds into Eq.
13
wC get that,
9k
E < 4. K-
2
exp
333
Now using this bound on E\t in Eq.
12
and observing that [V| gk we get that,
S) ]
Es
TV
Q(u ΣQ(
S).o,1.
Σ
E9(
Quv
WEv
NEV
9K-1
4.9g-11
min
5 8
exp
199K
K
2
3k3
1
Ammin
exp
18K
144K
3K3
completing the proof.
Finally, we combine Lemma B.1 and Lemma B.2 establish the minimax lower bound in this label shift setting. We recall the statement of the theorem here.
Theorem 4.1. Consider the label shift setting described in Section 3.2.1 Recall that Pts the class of pairs of distributions (P (Pmaj Pmnn) that salisfy the assumplions in that section. The minimar excess risk over this class is lower bounded follows:
Minimax Excess Risk(Pls) = inf sup
Excess Risk[A; (Pmajy Pmin)] 2 600 Tlmin 1/3
(3)
A (Pmaj Pmn)PPs
we know that, Proof. By Lemmna B.1
Q(vi S)P )
Minimax Excess Risk(PLs) 2
1 Es-as
TV
Σ Q(u S)P Σ
36К
2
wev
21

---

Published in Transactions on Machine Learning Research (06/2023)
Next by the calculation in Lemma B.2 we have that
1
1
Minimax Excess (isk(
exp
36K
2
18K
144K
3k3 3
1
1min
exp
288
3K3
Sctting K Mmin 1/3 yields the following
7mmi
Minimax Excess Risk(Pis)
288
1mmi
1/3
exp
mmmimn 1/373
exp
3 Munin 1/313
Aliin
1lmin 1/3
IV
288
1mmi
1/3
Ammin 1/3
0.7 exp
(-
288
T1min 1/3
1
600 Mmmi 1/3"
where (i) follows since Almin" 1/3/ [ 1/31 2 0.7 for Timin 2 1.
B.2 Proof of Theorem
In this section, we derive upper bound on the excess risk of the undersampled binning estimator Ause (Eq. ( in the label shift sctting. Recall that given a dataset S this estimator first calculates the under- sampled dataset Sus, where the number of points from the minorily group (Mmin) is equal to the number of points from the majority group (Amin), and the size of the dataset 2n Throughout this section, (Pmaj Pmnn) shall be an arbitrary clement of PLs-
To bound the excess risk of the undersampling algorithm, we will relate it to density estimation.
Recall that R1, denotes the number of points in Sus with label +1 that lie in by and n-1. is defined analogously.
Given a positive integer K, for x E T, 1 I by the definition of the undersampled binning estimator (Eq. 5
{ {[
1
if mij > n-1 otherwisc.
A (a:)
Recall that since we have undersampled, E, n1. = E, n-1,j = 1emn Therefore, define the simple histogram estimators for Pi (x) P(x y 1) and P P-1(x) P(x y -1) follows: for Ij.
(x) =
11.j and (x) := K Kmmin
n-
K Knmin
With this histogram estimator in place, we may define an estimator for n)x)) = P Prest (y = 1 (x)) as follows,
(T)
1 (x) = (f( + P5
Observe that, for x E I
8 (x) 1/2 B1 > n-1j +
A 1.
Defining estimator 77 for the P Prest 1 x)) in this way will allow us to relate the excess risk of Ause to the estimation error in Ps and ps
Before proving the theorem restate it here.
22

---

Published in Transactions on Machine Learning Research (06/2023)
Theorem 5.1. Consider the label shift setting described in Section 3.2.1 1 For any (Pmaj P E PLs the with number of bins with K
expected encess risk of the Undersampling Binning Eslimator (Eq. 15 c emmimn 1/$1 is upper bounded by
C
Excess Risk[AUSER (Pmaj mmnn)] E
S. "mai xP myj
[R(AUse: Prest) R( Ptest)
1'min 1/3"
Proof. By the definition of the excess risk
[R(AÚSR: Pteat) - R(f"; Ptest]]. Excess Risk[[Uus:: (P maj. Pmin)] == E Sh xP"ninn
By invoking (Wasserman 2019 Theorem 1) we may upper bound the excess risk given a draw S by
R(Aúse: Prest) )) R(f"; Ptest) 2 (1() [1(x)| Prest(a) (a:) dr.
Continuing using the definition of 77 above and because 17 = P1/(PI P-1) we have that,
R(AÚsB; Prstt)
R( ; Prest)
(x(x)
PI(x)
(P((x) (Pi( P-1)))+-111)) dæ
2
Pf(x)) P5. (x)
PI(x) + (x)
2
1/')
Pi(x) + PP)(())
(f(()) - (1))) dæ
Pf(x) + P5, (x)
2 /
(f(x)) - Pi())) dx +
Pi(x) + (z)
(x() da
Pf(x) (5
/
Pf(() - PI(0)] dx [
Pf(xx)
(f) -P Pi(x) P-1(1)
dr
pf(x)) + PS. (x)
/ (pf(x) P1(x) dr+ S p3, -P-( dr
2
2/ S.' (P(())- dr + V.. (P=)(0)-P_1())) P_1(2))) dr,
where (i) follows by the triangle inequality, (ii) is by the Cauchy Schwarz inequality.
Taking expectation over the samples S and by invoking Jensen's inequality we find that,
Excess Risk(AAS: (Pmaj, Pmin))
Es [R(A Prese)) R(J": Ptest)]
Es (PP(0)) - dx + Es // (ps,(0)-P-1(0))) dr < 2
We note that ps 3 only depends on m'in i.i.d. draws from class j. Thus by Freedman & Diaconis 1981
Theorem 1.7), if K = c[mmin then
Es / (p)) dr <
Ammin 2/3
Plugging this into the previous inequality yields the desired result.
23

---

Published in Transactions on Machine Learning Research (06/2023)
C Proof in the group-covariate shift setting
Throughout this section operate in the group-covariate shift setting (Section 3.2.2
distributions such that it will be necessary for adequate samples in each sub-interval of [o, 1] to be able to learn the maximally likely label in that sub-interval. On the other hand, we will construct the group-covariate distributions to separated from one another. As consequence, sub-intervals with high probability mass under the minority group distribution will have low probability mass under the majority group distribution. Hence, these sub- intervals will not have enough training sample points for any classifier to be able to learn the maximally likely label and as result shall suffer high excess risk.
We will proceed similarly to Section B We shall construct family of
First in Appendix C.1 we prove Theorem 4.2 the minimax lower bound through a sequence of lemmas.
Sccond in Appendix C.2 we prove Theorem 5.2 that upper bound on the excess risk the undersampled
binning estimator with Mmin 1//3 bins.
C.1 Proof of Theorem 4.2
In this section, we provide a proof of the minimax lower bound in the group shift setting.
We construct the "hard" set of distributions as follows. Let the index set be = [-1, For every e E V define a distribution as follows: for x E E = 1 #)
1
1 1 x- (e-3+1/2) (+_
Pr = 1 2x) =
K
where & is defined in Eq. 6 Given a E [0 we also construct the group distributions follows:
Pa(x) 2 -T
if x E (0,0.5)
if x [0.5,
and let.
Pb(x) = PP)(.)
We can verify that
Overlap(Pa. Pb) = - TV.P., Pb) = =1 _
Pa((x) - Pp(x)) dr
dr=
We continue define
P Pa. (z, 3) = Po(y Pa)(((
P Pu.min (x. v) (v(y) Pt))))
and
(a(x)) + Pa(x)
P Pu.test (x, P 2)
2
Observe that (Pa(x) P=(x)//2 1, the uniform distribution over [0. 1].
Recall that as described in Section A.1 V shall be a uniform random variable over V and S V mm
u,maj X
v.min We shall let. Q denote the joint distribution of (V,S) and let Qs denote the marginal over S.
With this construction in place, we present the following lemma that lower bounds the minimax excess risk by a sum of exp(-KL fy 11) measure of how difficult it is to identify whether ij ey -1 from the samples.
= Q)]] by -1)) over the intervals. Intuitively, KL(Q(S) = 1)][Q(()
24

---

Published in Transactions on Machine Learning Research (06/2023)
Lemma C.1. For any positive integers K, Rmajj Mimin and 7 E [0, 11, the minimaz excess risk is lower bounded follows:
Minimax Excess Risk(Pas = inf
sup E
E S.. p"mu p
(R(AA)Ptest) ,testt R(S": Prest)
exp(-KL(Q(S) I uy = Q)]IQ(S | by = =
32K
j=1
Proof. By invoking Lemma A.1
know that the minimax excess risk is lower bounded by
Minimax Excess (isk(Pas(T))
Es linf
Pr
(h(x) + Ey]--E[R((T
[R[ (PVitest:: Pyytest)
(1.8)~ E Evev Q(v1S)P
BBy
=Bt
where V is uniform random variable over the set V VV = v is a draw from P Pilmii the joint distribution over (V,
u.maj
o.min and Q denotes
We shall lower bound this minimax risk in parts. First, we shall establish a lower bound on Ry, and then an upper bound on the Bayes risk By
Lower bound on Ry.
Unpacking By using its definition we get that,
By Es-Qs jinf (a.N)~ (..))..ED EvEN Q(v|S)P
Pr
(h(x) + y)]
inf / (z)
Es-Qs
Pr
(h(x)) # v) dx
yr EEV Q(v[S)P.(1z)
(5) Es-Qs 1/" (rest(x)) min
Q(u S)P,(1
Σ Q(u s))
de
PEV
VEV
Es-Qs 1/'1 (Pes((x)
(i)) 1
Q S)P. xx)
dr de,
2
NEV
(86) 1
Prest (x) Eswas
Σ Q(u S)P (1 x))
(14)
2
where (i) follows by taking h to be the pointwise minimizer over x, (ti) follows since P,(-1 =1 x) and (s, 1 - s} = (1- - [1 - 2=1)/2 for all E [0,1] 1], and (iii follows by Fubini's theorem which allows us switch the order of the integrals.
If x E I -' 1 for some j E (1...., K} let ju denote the value of this index j. With this notation in place let us continue to upper bound integrand in the second term in the RHS above as follows:
Es~Qs
Σ VEV
Q(u
S)) 1z) x)
2
in + 1/2 10
EsnQs
QQ(1) =| 8) Q(v,, -1 |S]]
K
1x 1/2
Es-Qs
[1(1/, (S) Q(1y. -1 |S]]
K
In + 1/2)
Q(S1 Uj. = 1)Qv (Uy, =1) Q(S) Uj. = =1)Qvv -1)
EsnQs
K
Qs(S)
Qs(S)
(124)
②
ix + 1/2
TV(Q(S) Uj = 1), Q(S) Uy =-)),
(15)
2
K
25

---

Published in Transactions on Machine Learning Research (06/2023)
where (i) follows since (. x) uj - (íz + 1/2)/KK)/2 and by marginalizing Q S) over the indices j * Ja. (fi) follows by using Bayes' rule and (iii) follows since the total-variation distance is half the & distance. Now by the Bretagnolle Huber inequality (see Canonne 2022 Corollary 4) we get that,
TV(Q(8) u, Q)QQ( U/ =
< 1 exp(-KI.(( fj = =)]SQ(S) U/, =-1))
(16)
Combining Eqs.
14
16
we get that
Ry
fa + 1/2 )
2
Proa((e)
dr
0
K
1
fs +++/1))
+
4
J
Prest (x)
x
K
eXp(-KI(Q(S] Uy = 1)][Q(() 8/. = =-1)) dr.
(17)
Upper bound on By: The Bayes error is
By = (
inf E (a.y)>PPP 1f(xx) # v)
Ev
( (y l [x)1(f(x) = =-
Ev
inf
== vE(-1,1)
1
Ev
Prest (x)
min vE(-1,1}
Piçcest xx)
Ey
1
P Prest(x)) PP Vistes(1 x)) - Pv,test ( (-1 x)) dæ
2
2=0
1
["
fx 1e+1/2) )
Ey
1
P (x))
Φ
dr
2
a==
K
1
Iu +1/2
Prest Pres(ar)
Φ
dr.
(18)
2
K
x=0
where (i) follows since Pb (z) = 1 Po and minfs, 1 1--s) s) = (1 -1-11122ss)2 for all s e [0, 1]. and
(ii) follows by our ruction of P. above along with the fact that P. x)) = =1 -
Putting things together:
Combining Eqs.
17 and 18 allows us to conclude that
Minimax Excess Risk(Pos(T))
Prest (2) @b (x x- ja + 1/2
2
exp(-KL(Q(S) 1/_ 1)||Q(S) Uy. = -1)) da
K
Poest (2ost(1)) (x j+
- 3+11/2 1/2)
exp(-KTT(Q()) uy 1)[ vy -1)) dx
Prest(z) 0 x j + 1/2 112) 1/2) dæ
exp( - KLL(((S) b =1][[((S) ue = -1))
K
j=1
K exp( (K((S(L)))))) u, = 1)] | by = 1))),
32K
1=1
where (1) follows by using Lemma A.2 along with the fact that Ptes(a)) in our construction to show that the integral in the square brackets is equal to 1/8K2. This proves the result.
26

---

Published in Transactions on Machine Learning Research (06/2023)
The next lemma upper bounds the KL divergence between Q(S 1, 1) and Q(S Dy -1) for each E (I,..., K). It shows that the KL. divergence between these two posteriors is larger when the expected number of samples in that bin is larger.
Lemma C.2. Suppose that is drawn uniformly from the set {-1,1}* and that S is drawn from
P m.maj
X Puimn
v.min Then for any j E (l..... K/2} and any T E [0, 11,
Mmaaj (2 7) + Ammin
KL(Q(S1 1/ = Q)] vj -1) -
3K
and for any j E 1,.2211....... K}
(T(Q(SS vj = 1) by = -1) Tmmaj + 10min (2 7)
3K3
Proof. Let us consider the case when j = The bound for all other j E (....., K} shall follow analogously.
Given samples S, let S Si) be partition where S1 are the samples that fall in the interval 41, and S be the other samples. Similarly, given vector E {-1,1}, let 01), where is the first component and in denotes the other components (2...., K) of v.
First, we will show that
Q(S u,) = Q(Si v))())))
To see this, observe that
Q v1) (((S), (1)) Q(S, v S1)
Further, is chosen uniformly over the hypercube f-1, 1] then
Q | 01, S1) = Σ Q(11, 01 (1)
81
Σ
Q 11 ō1 Si) (1,81)
81
Σ Q(ši 01. U1 (()))
81
(
Σ Q(S1 01, 01 Q(1))
Σ Q(3i T. Q(1))
Q(5))
where (i) follows since by Bayes' rule
Q vi Q(() 01, U1)
Q U1, S1)
Q(S1 U1)
Q(t))Q(S) Ui, 01)
(since ūn is independent of v1)
Q(Si vi)
Q(ūi Q(S) vI)
Q(T1)
(the samples in Si depend only on v1).
Q(51 u1)
Inequality (ti) follows since the samples are drawn independently given o = (v1,0)) Finally, (ii) follows since S, (the samples that lic outside the interval I,) only depend on i since the marginal distribution of x is independent of and the distribution of y x depends only on the value of corresponding the interval in which lies.
27

---

Published in Transactions on Machine Learning Research (06/2023)
Thus since, Q(S) v1) Q(S: (S)) we have that KL(Q(81) 01 Q) 0 1)) ( 0 1)[{((S) 01 = -1).
(19)
To bound this KL divergence, let us condition of the number of samples Si from group a, (the majority group) 71,, and the number of samples from group (the minority group), 01,b. Now since 71,a and 41,b are independent of 01 (which only affects the labels) we have that,
Q(Si (m)= = Σ
Q(mi,; R1,6 un Q(( (1,,
Σ (1, vi, 01,a, 01.))
"1,a"R1,b
- (Q(S) 01, 11, (1,)]]
Therefore, by the joint convexity of the KL-divergence and by Jensen's inequality we have that,
(L(Q((S) 11 = Q)]QQ(s) 1 = -1))
S E mis. [ t1 = 1, ai,a. ni I[Q(s [i = - 11, (1x))l
(20)
Now conditioned on 71.a and R1,6, samples in S are composed of 2 groups of samples (S1 S1,6). The samples in each group (1,,,S1,)) are drawn independently from the distributions Pa(x x E P.)P((y x) and Pa(x | x E P. (y x) respectively. Therefore,
( 01 = 1, 1, Q1.) 01 = -1, n1.1)
M1, KL E I.) - x)
[ Pa (m (1))))
(n,,KL(Ps(2 P1 x)) PP( x E Po)
(
(11, +1,bb E Unit(i
(L(Pe,=1(Y) x)
P x))
(152)
n1aa + 11.b
E Un-UUif(I.)
Σ
1 yd
x 2K
log
11 yo (x 2k
2
+ yo
(x 2R
EE{-1,1)
11.a
2
11,bb
Σ
Un-UUi((t)
1+ (I yo
x
2K
1
log
11 yo (x zス
+ yd (x ZR
yE 1-11
(1 + yo (xr 2
11.a m1,b
1 yo
x
log
dx
2K
2K
(1 + yo
(x 2R
VEI 1.1)
x=0
((v) 11,a + 11.6
(21)
3K2
where in (i) we let Pv, denote the conditional distribution of for x E In given U1, (ii) follows since both Pa and Ps are constant in the interval, (ii) follows by our construction of P. above, and finally (iv) follows by invoking Lemma A.3 that ensures that the integral is bounded by 1/3K2.
Using this bound in Eq. 20 along with Eq.
19 we get that
E I11a + n220)
(L(Q(S) 01 = Q)( 1 = 1))
3K2
Now there are majj samples from group a in S and mmin samples from group b. Therefore,
E [11 Pa E I1) A2ma -)
K
E [mI
n (b E (1)
Ammin
K
28

---

Published in Transactions on Machine Learning Research (06/2023)
Plugging this bound into Eq. 21 completes the proof by the first interval. An identical argument holds for E (...... K/2]. For j E (K/2 .,.., K} the only change is that
majj T
E [njaaa = PamaPPa(e E 1,)
K
Ammi (2 - T)
I [1J,]] = m'nn Po(xr E 11)
K
Next, combine the previous two lemmas establish our stated lower bound. We first restate it here.
Theorem 4.2. Consider the group shift setting described in Section 3.2.2 Given any overlap T E [0, 1]
recall that (T) is the class of distributions such that Overlap(P majj Pmnn) 2 T. The minimar excess risk in this selting lower bounded as follows:
Minimax Excess Risk (isk(Pos(T)) inf sup A (mm)..Pn
Excess Risk[A; (P (mmaj Pmin)]
2 200(rmin
(2- + Rmajj 7/1/3 2 200 1/3 +2)2/3
(4)
where = /mmaj//mmmn Mmmin >
Proof. First, by Lemma C.1
we know that
Minimax Excess Risk(Pos(T)) 2 32K exp(-KL(Q(S) Q)I 1 oy= -)))
Next, by invoking the bound on the KL divergences in the equation above by Lemma C.2 we get that
Minimax Excess Risk(Pos(T))
Amma (2 T) AmminT
1l (2 T) + Amajl
exp
+ exp
64K
3K3
3K3
1
1min (2 2-7) T) + Amajj
exp
64K
3K3
Setting K = [ (2 T) + 1/3 and recalling that r 5 1 we get that
Minimax Excess Risk(Pas(T))
mmin (2 T) + Rnmaj
64 (Tiin (2 T) + Maaj 1/33 exp
3 (Amin (2 3 T) + Rmmaj T) 1/3373
exp( 113)
(n (2 T) Mmaj Mmaj 1/3
64
(Temin (2 - T) + Rmaj T) 1/37
(Timn (2 - T) + 7
(4) 0.7 exx((1/33)
64
(1 (2 T) + Umajj 11/3
200 (Aiii (2 - T) + 7mmaj 12/33
where (i) follows since Pmmin (2 - T) + T2maj T [n 10mmin(2 7) + mmajt) 1/373 < 1, and (ti) follows since 0 1
and Mmin 2 1 and hence
(Amii (2- +m
1/8
2 0.7.
[ (2- +noo
29

---

Published in Transactions on Machine Learning Research (06/2023)
C.2 Proof of Theorem 5.2
In this section, we derive an upper bound on the excess risk of the undersampled binning estimator Ause (Eq. (5)) Recall that given dataset this estimator first calculates the undersampled datasct Sus, where the number of points from the minority group (Miin) is equal to the number of points from the majority group mmni,) and the size of the dataset is min Throughout this section, (P maj- P mmnn) shall be an arbitrary element of (T) for any E [0, 1]. In this section, whenever we shall often denote Excess Risk(A: (P (Pmaj, Pmin)) by simply Excess Risk(A).
Before we proceed, we introduce some additional notation. For any j E (I,...,K) and I 1-= kl let
43.1 P test (y = 11) Juel, P(y = x) (2r x Tz) da,
22
93.1 P Ptex(y 1 x 1
P(y ((y=1|=)Ptadl E I5) dr.
22
Jeel,
For the undersampled binning estimator AusB (defined above in Eq. (5), define the ercess risk in an interval Ig as follows:
R2 (AÚSE) = p - x EE - min (Ptest = 1j), Prest - (yss(y=-1|z E1)) = qj. A min 95.-17-
The proof of the upper bound shall proceed in steps. First, in Lemma CR3 will show that the excess risk is equal to sum the excess risk over the intervals up to factor of 2/ K on account of the distribution being I-Lipschitz. Next, in Lemma C.4 we upper bound the risk over each interval. We put these two together and to upper bound the risk.
Lemma C.3. The expected eacess risk of undersampled binning estimator AusB can be decomposed as follows
2 [RAAAS)) Ptest (1z) + K
Excess Risk(AusB)
EE SnP pmaj x P
where Ptest(1;) SZE1, Ptest(x) dr.
Proof. Recall that by definition, the expected excess risk is
EspP" Phn
R(A* : Prest) R(f"; Ptes))
x mai
mis
Let us first decompose the Bayes risk R(f*).
R(**) inl P( (1([(x) +)
inf Σ (f((x) # Prest Ptea dr
vE(-1.1)
inf 1 (1)) 1E(-1.1)
Σ 1(f(x) # y) 1 Ptest(())) dr
inf ==0 f(x)E(-1.1)
Prest (y = - f(r)) 1x) Pres((())))))) dr
min (Prest x)), Prest = - x)) (rest(x) dx.
(23)
30

---

Published in Transactions on Machine Learning Research (06/2023)
The risk of the undersampled binning algorithm Ause is given by
f ==
R(AÚSB)
Σ
1(AūsB (x) + Pest x Pes dr
8E{-1.13
Prest (y = AÚs((r)) | Pret dr.
==
Next, recall that the undersampled binning estimator is constant over the intervals 1y for j E {I,...,KK) where it takes the value Ag (to case notation let us simply denote by A, below), and therefore
/
R(AUsB)
Σ
Prest = - (P)gl)))Ptettt test (x) dx.
1=0 mer
This combined with Eq.
23
tells us that
R(AUsB)
R(f")
K-1
Σ
(y -Ayla) min (Pres x)) Prest -1 2)3 ) Prest (2) dx.
(24)
0=
xEL,
Recall the definition 9j.1 and Q3--1 from Eqs. [2 22 above. For any x E = - kl. Prest x)) - gj.ul $ 1/K, since the distribution Prest x) is 1-L.ipschitz and diy is conditional mean. Therefore,
R(AASE) -R(f*)
K
K Σ
(gi--A min (5-1) ) Prest (x) dx +
P Prest (I)) de
f=n
xEl,
K
j=0
K-1
2 K
Σ j=n
(y(A ) Prest (x) dx +
xEI,
Taking expectation over the training samples S (where Timin samples are drawn independently from Pmin and Rmaj samples are drawn independently from Pmaj) concludes the proof.
Next provide upper bound on the expected excess risk is interval (
Lemma C.4. For any j E {1,.... K} with I, = |3 I
E E. "mmi Paiin (AUsB)) S V V PPminPrsst Pres((,) + K
my
where is an absolute constant, and P Prest (1z) == SHE1, Pres(()) dr.
Proof. Consider an arbitrary bucket j E (1,....,K K}.
Let us roduee some notation that shall be useful in the remainder of the proof. Analogous to dg and
gj.-1 defined above (see Eqs. [22 p) define oi and oi as follows:
G. = Pa(y = x ET) = JUEI,
P(y= = 1 x T,) da,
25
/ Jeet
L. Po(y= 1 1 =
P(y = 1 P)) x x I,) dæ.
25
Essentially, G. the probability that a sample is from group a and has label conditioned on the event that the sample falls in the interval 75- Since
P (x x E 12)
Pa x E 1,) + Pa(x 1;)],
31

---

Published in Transactions on Machine Learning Research (06/2023)
therefore
Jeet, P(y = Pls=1//)Psst//xe / JzE1, P(y x) (x x 1,) dx
43,1 93,1
(26)
K
This follows since P(y 1:) is 1-Lipschitz and therefore can fluctuate by at most 1/K in the interval J5. Of course the same bound also holds for 19j,1 -..l-
With this notation in place let present bound the expected value of ( By definition
RA(()))) -3.-55 min (g.11 (j.-1).
First, note that f/.1 (ye = 1 11) 95.-1 Suppose that 9;11 1/2 and therefore 9, 1/2 (the same bound shall hold in the other case). Tn this case, risk is incurred only when Ad =1. That is,
E S. xP
[Rg = -11.--1 - 23.1 5 PPrlas =
-11-2gh.11 PaaiPPP/4 Pr[45 1].
(27)
Now by the definition of the undersampled binning estimator (see Eq. A = 1 only when there are more samples in the interval 1 with label 1 than -1 However, we can bound the probability of this happening since f3,1 smaller than Oj.-1
Let ny be the number of samples in the undersampled sample set Sus in the interval 15- Let nıj be the number of these samples with label 1, and n-1, ny nij be the number of samples with label -1. Further, let naj be the number of samples in from group a such that they fall in the interval Ij, and define ma,j analogously.
The probability of incurring risk is given by
P(Aj = 1| Σ
PIA, -1 ny = s][[n, = s).
(28)
where the sum is up to 2mmin since the size of the undersample dataset |Sus is equal to 2mmin
Conditioned on the event that ny = s the probability of incurring risk
P PlA, =1 ny = TP [m.. > n m = = PP [m1.j > n2/2 nj = =8]
[mn. > 8/2 ny = 8)
(29)
Now, note that n, = na,j + 1b.j.. Thus continuing, we have that
Plms > 8/2 my = =
Σ PP [mn. > 8/2 1 = 8, nb. = =8] = =d]
8'S.
Σ s'
P > 8/2 No.j = = s's, s']iP(no.j = =s].
In light of this previous equation, we want to control the probability that the number of samples with label in the interval 1 conditioned the event that the number of samples from group in this interval is - s' and the number of samples from group b in this interval is s'. Recall that gf and df, the probabilitics of the label of the sample being 1 conditioned the event that sample is in the interval I5 when it is group and b respectively. So we define the random variables:
za(s 87 ~ Bin(s - s), 26[87 Bin(s' .f..).
2[s] ~ Bin(s, max (f
32

---

Published in Transactions on Machine Learning Research (06/2023)
Then,
P mij > 8/2 n2 =s]
Σ
P. P(m1.j 8/2 Diaa =8- 8- 8 = =s|]p(naa =0]
50
Σ
P
P|za| $1 20(5)) > 8/2 Ma.j - 8s nnb,j = P/)P(mb.s sS
5'<a
<
Σ
nbj = 80) p/pln 5o) P[=[s] > 8/2 mas = =8- ,
[[ > 8/ P/m) = =s
P [z[s] 8/2]
_ exp (-2 2 max (L )
(30)
where (i) follows by invoking Hoeffding's inequality Wainwright 2019
Proposition 2.5). Combining this
with Eqs.
28 and 29) we get that
21imn
PIAj = 1]
exp -
(1- 2mx {or, (2, 1)) P(n, = =s].
Now ny which is the number of samples that lands in the interval 1 is equal to Ma.j + naj- Now each of may and nay (the number of samples in this interval from each of the groups) are random variables with distributions Bin(niin: (T)) and Bin(nmin: Po(T))) where Pa(T,) = SeEI, (a(x) da and Ps(T,) = Sher, Pa(x) dæ. Therefore, n2 is distributed as sum of two binomial distribution and is therefore Poisson binomially distributed (Wikipedia contributors, 2022). Using the formula for the moment gencrating function (MGF) of Poisson binomially distributed random variable we infer that,
(-11 (1- 2 max {ah. 12,1))² ))
PlA, = 1 (I-P((1)) + Pa(4)) exp
X
2
(
(1 2 max {9g.1- 22,1))2)
1 - - Po(())))+ +P(())))((())))))))))))))))))))) exp
exp
2
Plugging this into Eq.
28
we get that,
E S "mann [RAS)))
(1 - 2 max { 1/,1)2
11 2
- PP(T)) exp
2
(1 - 2 max {gf, 22,1)2²
Plyin
Pb(T5) + Pb(TT) exp
(1 - 2 max {9,11 1)
Thain
|1 2q
PI(
1 1-exp exp
2
(1 2 max
{uf,1 of 1))
Miis
1-exp
2
Since 1 - max {ff11 E $ 1,
(1 - 2 max
{ge 1)2 1
(1 max { 12,1)2
1 1- exp
2
33

---

Published in Transactions on Machine Learning Research (06/2023)
and therefore
1 - Pa(Tz) (1- 2 max (99,1 97,1))
Rmmis
E. Snup"ie "me xP"mm RR (Ry(AUUB) my
S -2z,11
(1- 2 max {ag,1 83,1)2²
Puain
--P((j)
(1)
(1 (1-29j,1 22))
[1 2q,,1
Pa(Ig)
x
2
1 P (1 - -29
(1-2g,11 -
27)²
Anin
(1t)
-I7min (Pa(T)) + Pb(T,)) (1 (1-29s,1 -2y)²
I 29 exp
2
where (i) follows since (n. 22 4, - 1/K by Eq. 26 and y such that h9 S 1/K, and (ii
follows since (1 2)) S exp(bz). Now the RHS above is maximized when (1 - 20,1 - 22)² (ann(a(()+PP((5))
for some constant c. Plugging this into the equation above get that
d
E
S-PP Pmii myj
xP
[Ry S v mmin (Pa(I,) Po(lT))
+cbl
d
v mmin (Pa(I)) + Pb(T,)
K
Finally, noting that (1)) (Pa(1) Pb(T)))22 completes the proof.
By combining the previous two lemmas we can now prove our upper bound on the risk of the undersampled binning estimator. We begin by restating it.
Theorem 5.2. Consider the group shift setting described Section 3.2.2 2 For any overlop [0, and for
any (Pmajy Pmin) E PT)((T) the expected ercess risk of the Undersampling Birningg Estimator (Eq. 5 with number of bins with K [ 1/31 is
Excess Risk[AusB: (amaj mmin)] = E P~ x xP"mi [ Prest)) - ;(ff"Pttest) S
Trmin
Proof. First by Lemma C.3
know that
K-
Excess Risk[Ause:
<
Σ
E Sup Pm'm [R
Ptese(T,) +
K
1=0
Next by using the bound on S~P"mm "mai x mij
[Rg (Aiss))
established in Lemma C.4 we get that,
Excess Risk Risk(Ause) Sc
P test (T,) + K
mmmin Prest Prest(T)) (T,)
1=0
K-1
Prest (1i) + K
//min
==0
K
VK
Prstt (Iz) +
1mii
K
1=0
K
c
0
1mmn
K
34

---

Published in Transactions on Machine Learning Research (06/2023)
where (i) follows since for any vector E RK || I VK|12112. Maximizing K yields the choice
K Mmin 1/31, completing the proof.
Additional simulations
Tilted Loss Classifiers
68
68
Only Majority
Test Accuracy (%)
Proportional Increase
66
M
64
62-
62
Only Minorily
60
Proportional Increase
60
500
1000
1500
500
1000
1500
2000
Extra Minority Samples Added
Extra Majority Samples Added
Group DRO Classifiers
68
Only Majority
Test Accuracy (%)
Proportional Increase
64-
64
62-
62
Only Minority
60
Proportional Increase
1000
1500
500 1000
1500
2000
Extra Minority Samples Added
Extra Majority Samples Added
Figure 4: Convolutional neural network classifiers trained on the Imbalanced Binary CIFAR10 dataset with a 5:1 label imbalance. (Top) Models trained using the tilted loss (Li et al. 2020 with early stopping. (Bottom) Models trained using group-DRO (Sagawa et al. 2020) with early stopping. We report the average test accuracy calculated on balanced test set over random seods. We start off with 2500 cat examples and 500 dog examples in the training dataset. We find similar trends to those obtained in Figure 2 even with these losses that are designed to optimize for the worst group accuracy.
E Discussion about minimax lower bounds for cost-sensitive losses applied to the label shift setting
We add more detailed discussion about applying minimax cost-sensitive losses to obtain a lower bound the presence of label shift.
Assume that Pmaj is distribution of the covariates y 1, and Pmin is the distribution of the covariates y -1 The training samples are drawn from the distribution:
P(z. v) P maj P(y P Pin: min:
where
Pyy = 1) P and P(y P(y= = -1) 1+p I+p
for some imbalance ratio p > On average the ratio between the number points from the majority class to the number of points from the minority class is equal to p.
35

---

Published in Transactions on Machine Learning Research (06/2023)
We set the cost of getting an incorrectly predicting the majority class label to be equal to and the cost of incorrectly predicting the minority class label be equal
1 1+p
c-1 1+p
Note that the costs 61 + C-1 and that c < C-1- The expected cost-sensitive loss is therefore equal to
B(ay)) [,, # v]l =
+ (())p [c [[(x) + 1]] +
P
1 |c (f(x) + -1]]
1
(c-
P
ExaPing [f((x) + 1]] +
E ExPPan [1 [f(x)) # -1]
(1 ppp
(1+ p)2
2p
= (1 + p)2 Bu--Uni(- [1 [f()) * ul1
Now if we invoke the minimax lower bound (Kamalaruban & Williamson 2018
Theorem 4) we get that
2p min max (1+ p)² Pu-fU Unt -.1). [f((x) * yll
C min (V (1+ p)n 1 p pnh
V 1 V
1+
where the minimum over f is over all measurable functions from the training data to binary labels, the maximum is over data distribution that be correctly classified with classifier from VC class with VC dimension at most V and h is the Massart noise margin. For more thorough definitions we urge the reader to see (Kaaalarbaan & Williamson 2018). With this lower bound we get that
C)
V
V
min max Uy--Unift- (.--UUnf((-111)).aa P(zl)) [ [f(x) # vll f
min (V (1 + p)n
2p
I+ p nh
C Σ 2
V
V
min
p1+ 1 nh
Therefore we find that this lower bound gets smaller as the imbalance ratio gets larger, predicting the wrong trend for the label shift problem.
F Details about results in Table
In Table we listed results regarding the performance of undersampled algorithms to others that are reported in the literature. Here we provide detailed references to these results.
Label shift. The results for label shift are from the paper by Cao et al. 2019 The results are reported in Table of that paper. For Imb CIFAR 10 (step 10), the undersampling result corresponds to the entry CB RS from that table with accuracy 84.59% (error 15.41%), while the best method corresponds to the method LDAM-DRW with accuracy 87.81% (error 12. 12.19%). For Imb CIFAR100 (step 10), the undersampling result again corresponds to CB RS with accuracy 53.08% (error 46.92%) while the best method corresponds to the method LDAM-DRW with accuracy 59.46% (error 40.54%).
Group-covariate shift. The results for the group-covariate shift are from Table 2 in Idrissi et al. (022 For the CelebA dataset, the undersampled accuracy corresponds to the method SUBG and the best accuracy is for gDRO. For the Waterbirds dataset, the undersampled method is SUBG and the best competitor is RWG. For the MultiNLI dataset, the undersampled accuracy corresponds the method SUBG and the best accuracy is for gDRO. Finally, for the CivilComments dataset, the undersampled method is SUBG and the best. method is RWG.
36

---

Published in Transactions on Machine Learning Research (06/2023)
G Experimental details for Figures
2 and 4
We construct our label shift dataset from the original CIFAR10 datasct. We create a binary classification lask using the "cat" and "dog" classes. We use the official test examples as the balanced test set with 1000 cats and 1000 dogs. To form the initial train and validation sets, we use 2500 cat examples (half of the training set) and 500 dog examples, corresponding to a 5:1 label imbalance. We use 80% those examples for training and the for validation. We left with 2500 additional cat examples and 4500 dog examples from the original train set which add into training set. to generate Figure 2
We use the same convolutional neural network architecture (Byrd & Lipton 2019 Wang et al. 2022 with random initializations for this dataset. We train this model using SGD for 800 epochs with batchsize 64, a constant learning rate 0.001 and momentum 0.9. The importance weights used upweight the minority class Examples
samples in the training loss and validation loss is calculated to be #Cat the experiments were performed on an internal cluster on GPUs.
We note that all of
#Dog Train Examples
VS loss: Given a datasct Deis9elim the VS loss (Kini al. 2021 is defined as follows
Lvs(f) = Σ log 1 exp (-(1)) gh yif(x;) Thg ))
1mmx
where denotes the group label, 'gg corresponds to the number of samples from the group, Mmma is the number of samples in the largest group and is the total number of samples. We set = 3 and 0.3, the best hyperparameters identified by Wang et al. (2022 on this dataset for this neural network architecture.
Tilted loss: The tilted loss Li et al, 2020 defined as
1 log Σ exp exp (tlly)((x))))
m
Ciited (f) = 7
where we take be the logistic loss. In our experiments we set
Group-DRO: We run group-DRO (Sagaaa al. 2020 Algorithm 1) with the logistic loss. We set adversarial step-size fg 0.05 which was the best hyperparameter identified by Wang et al. (0022)
37


Reviews:
[{"review_id": "OXxpnvehOO", "reviewer": "Reviewer_ipms", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I found the results in the paper interesting and think that the community will see these findings as a valuable contribution. As motivated by the authors, under group imbalance, empirically it is hard to improve upon learning on an undersampled balanced datasets. This has been observed in the empirical work, and is sometimes discussed at an intuitive level. Some results in transfer learning are applicable here too (which the authors mention and discuss relative to their work), but I have not seen work establishing minimax excess risk lower bounds in this particular setting.\n\nThe weaknesses of the paper relate to high dimensional extensions, experiments that do not evaluate undersampling,  potentially missed connection to memorization literature. For details, please see the comments and questions in the section below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents an analysis of binary classification under group imbalance (majority vs minority), when the group membership of individual examples is known. The authors prove lower bounds on minimax excess risk when there is either label shift (there are more examples of one class than another), or group-covariate shift (minority and majority groups have different distributions over the input features x, with varying overlap between these distributions). They find that these lower bounds depend purely on the number of minority class examples. Next, they study a predictor that first undersamples the majority group, then bins the features (scalars in a bounded interval), and then makes a prediction based on majority class of the examples in this bin. Finally, the authors run some simple experiments with neural networks, showing that the accuracy of the learned predictors increases with the increase of the minority samples, and not the majority, as predicted by the theory.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Comments and questions:\n\n- the authors mention that their findings can be easily extended to a high dimensional feature setting. However, it seems like the undersampling and binning algorithm would have terrible dependence on the dimension, and in practice have no relevance. More generally, I find Section 5 to be almost too toy to be interesting. Due to dimensionality dependence in the most straightforward extension of the results, they don’t really shed light on any realistic empirical studies. \n - Is there a version of undersampling such that the undersampled binning estimator would match the lower bound rate when there is overlap in the group-covariate shift distributions? Perhaps the undersampling should not be done as severely? \n- How does the literature on memorization relate to the results presented here? See, e.g., Feldman et al papers on memorization from ~2020, 2021.\n- Experiments: it would be natural to also show the results with undersampling. It would also help to further disentangle the contribution to accuracy coming from the majority group examples, and also at least somewhat tie back into the theory section on undersampling.\n- I see “robustness” mentioned several times (even in the title), however, it is never properly defined or being directly studied.  Robustness can mean a lot of things and is used differently in various research problems. In my opinion, if used, it should be more formally defined.\n\nTypos and minor comments:\n\n - “Eq. Equation XX” , see, e.g., theorems 5.1 and 5.2. (\\cref error).\n - The sentence just above Section 7 “When we add samples to both…” is incredibly hard to follow, and seems to be logically broken.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "DZTFLiPvCv", "reviewer": "Reviewer_8Fey", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nThe paper establishes lower bounds on the minimax excess risk, which shows that the rate depends only on the number of training examples from the minority distribution. The paper shows that a binning estimator applied to undersampling can achieve this minimax rate.\n\nThe paper presents experimental results to show that the number of negative examples plays a large role in the performance: increasing only the number of minority examples can improve the performance, while increasing only the number of majority examples does not. This matches well with the experimental results.\n\nWeakness:\n\nThe paper only considers the special case $d=1$. This is restrictive since $d$ can be large in practice. Furthermore, the effect of $d$ can be important on the performance. It would be very interesting to develop lower bounds for the minimax rate reflecting the dependency of $d$. As far as I see, the binning estimator may suffer from the curse of dimensionality, and therefore is not a good estimator if $d$ is large.\n\nThe paper considers a setting where the distribution for testing is a uniform average of $P_{min}$ and $P_{maj}$. It is not clear to me why the paper considers this specific setting. What will happen if the distribution for testing is another weighted average of $P_{min}$ and $P_{maj}$.\n\nThe lower bound in Thm 4.1 does not depend on the overlap between $P_{maj}$ and $P_{min}$. This is different from the bound in Thm 4.2. Can we use the information on the overlap to further improve the lower bound in Thm 4.1\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies a distribution shift setting where the distribution for training is a mixture of a minority distribution and a majority distribution, and the distribution for testing is a uniform average of the minority distribution and the majority distribution. The paper considers two kinds of distribution shift: a label shift and a group-covariate shift. For these two problems, the paper derives lower bounds on the minimax excess risk of order $n^{1/3}_{min}$, where $n_{min}$ is the number of examples for the minority distribution. The paper also shows that the undersampling scheme is able to achieve this minimax optimal rate. Empirical results are also presented.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Can we extend the analysis to the general case $d>1$. What is the potential challenge in this extension? Can the subsampling still achieve this minimal optimal rate?\n\nWhat will happen if we consider a general test distribution, i.e., the test distribution is not a uniform average of the $P_{min}$ and $P_{maj}$?\n\nCan we improve the bound in Thm 4.1 by incorporating the information on the overlap between $P_{min}$ and $P_{maj}$?", "broader_impact_concerns": "No concerns on the ethical impacts.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9a0cZbjbn6", "reviewer": "Reviewer_pxEG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n- **Importance of the hardness results**: Although the class imbalance problem has been extensively studied experimentally and theoretically, the fundamental hardness results were lacking. This work shows what we can do under given imbalanced conditions at best. We eventually admit the effectiveness of the undersampling strategy, which is simple but often dismissed, perhaps because it discards some information about the training samples.\n- **Educational proof**: The minimax lower bounds in this paper are shown by combining Le Cam's method and the total variation bound. The proof follows the classical flow with a new construction of the hard instance of the training distribution specifically for imbalanced learning. It is written in a transparent way and quite educational.\n- **Going beyond the existing analyses**: I like this paper particularly for giving a meaningful extrapolation for the limit $\\\\rho \\\\to 0$ (extreme imbalance) in Theorem 4.1 and interpolation for $\\\\tau \\\\to \\\\{0, 1\\\\}$ (hard/easy transfer) in Theorem 4.2. In particular, the interpolation of Theorem 4.2 gives us insights into when the minority sample size is the performance bottleneck. None of the existing work should be able to provide these insights, including the analyses of transfer learning and cost-sensitive learning.\n\n### Weaknesses\n\n- **Limited analysis for $d=1$**: The analyses in this paper focus merely on the one-dimensional case. Although the authors mention that the extension to the multi-dimensional case is elementary, I do not immediately see how to extend the construction of the \"hard\" distributions using the hat function beyond the one-dimensional case. It is illustrative to give readers instructions on constructing it when $d>2$. We do not necessarily need the full detail of the construction. In addition, the binning estimator in Section 5 seems to suffer from the curse of dimension under the extreme high-dimensional case. I understand that the authors do not intend to claim that the binning estimator is a \"silver bullet,\" but it should sound fair if you can discuss what happens under the high-dimensional case.\n- **Discussion of Kpotufe & Martinet (2018)**: In the last part of Section 4.2, the authors discuss the applicability of the minimax analysis of Kpotufe & Martinet (2018) in the current problem setting, but the discussion seems to be limited to only the zero-overlap case $\\\\tau=0$. What if $\\tau>0$? Can their analysis be applied to imbalanced learning, and if so, is there any agreement/contradiction with your results obtained in Theorem 4.2? Because the framework of Kpotufe & Martinet (2018) is slightly intricate, it is instructive for readers if you have some discussions here. (For the comparison of Theorem 4.1 and the existing analysis of cost-sensitive learning, I could imagine the difference)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper contributes to showing minimax lower bounds for imbalanced binary classification by considering two scenarios: label shift and group-covariate shift. The authors aim to convince that the classical approach of undersampling is a reasonable one even though it would not leverage some information from the majority samples, unlike more sophisticated methods such as oversampling and group distributionally robust learning.\n\nFor the label shift scenario, the training distribution can have an imbalanced proportion of positive and negative samples. The authors show that the minimax lower bound of the classification risk under this scenario is in the order of $n\\_\\mathrm{min}^{-1/3}$. This result is notable because the minimax rate is completely free from the majority sample size and captures the trend as the label proportion becomes more extreme. Indeed, the previous minimax bounds in transfer learning and cost-sensitive learning fail to capture this mode appropriately.\n\nFor the group-covariate shift scenario, the training samples have another attribute representing two groups in addition to their labels, and we suppose the covariate shift between the two groups. In this case, the authors show that the minimax lower bound is in the order of $n\\_\\mathrm{min}^{-1/3}$ when the two covariate distributions rarely overlap, and the minimax error becomes closer to the order of $1/n$ when they highly overlap. Thus, the two modes are interpolated smoothly in theory.\n\nFurther, the authors unveil that the binning estimator using the undersampled data achieves the obtained minimax rate for both scenarios. With neural network experiments, they additionally confirm that adding the minority samples is more effective in boosting the classification performance than adding the majority samples. These results altogether support the efficacy of the undersampling strategy and the fundamental hardness of learning under the limited availability of the minority samples.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Major suggestions are stated as the weaknesses above.\n\nSome minor comments:\n\n- In Section 3.1 (the second paragraph), the classifier domain should be $f: [0,1] \\\\to \\\\{-1, 1\\\\}$, not $f: \\\\mathbb{R} \\\\to \\\\{-1,1\\\\}$.\n- Right before Theorem 4.2, you may not need \"the absolute constant c > 0\" because it does not appear in the theorem.\n- Here and there, I found many typos like \"Eq. equation X.\" For example, you can find them in the statements of Theorems 5.1 and 5.2.\n- Right before Lemma B.1, it looks better to finish the sentence such as \"the minimax excess risk is lower bounded as follows.\"", "broader_impact_concerns": "Since this work is mainly theoretical, there is no concern about broader impacts.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The results are of interest and are mostly well substantiated. However, as the discussion on higher dimensions is not sufficiently well founded, the authors are requested to revise it so that it does not make unsubstantiated claims. Instead, the authors may wish to point to a promising direction without making strong claims. The authors are furhter requested to correct all other minor comments mentioned in the reviews.
Decision: Accept (poster)