Undersampling is a Minimax Optimal Robustness Intervention in Nonparametric Classification
Authors: Niladri Shekhar Chatterji
Saminul Haque
Tatsunori Hashimoto
Venue: Submitted to ICLR 2023 (2023)
Keywords: robustness
distribution shift
nonparametric classification
minimax lower bounds
undersampling
label shift
covariate shift

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. 

Under review as a conference paper at ICLR 2023
UNDERSAMPLING IS A MINIMAX OPTIMAL ROBUST- NESS INTERVENTION IN NONPARAMETRIC CLASSIFI- CATION
Anonymous authors Paper under double-bling review
ABSTRACT
While broad range techniques have been proposed to tackle distribution shift, the simple baseline of training undersampled balanced dataset often achieves close to -hat---taaaat- across several popular benchmarks. This rather surprising, since undersampling algorithms discard excess majority group data. To understand this phenomenon, we ask if learning is fundamentally constrained by lack of minority group samples. We prove that this is indeed the case in the setting of nonparametric binary classification. Our results show that the worst case, an algorithm cannot outperform undersampling unless there is high degree of overlap between the train and test distributions (which is unlikely to be the case in real-world datasets), if the algorithm leverages additional structure about the distribution shift. In particular, in the case of label shift we show that there 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 experimental case study on a label shift dataset and find that in line with our theory, the test accuracy of robust neural network classifiers constrained by the number of minority samples.
INTRODUCTION
key challenge facing the machine learning community is to design models that are robust to distribution shift. When there is 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 group- structured distribution shifts. In the traiing set, we have many samples from a majority group and relatively few samples from the minority group, while during test time we are equally likely to get sample from either group.
To tackle such distribution shifts, naïve algorithm is that first undersamples the training data by discarding excess majority group samples (Kubat & Matwin 1997, Wallace et al.) 2011) and then trains model on this resulting dataset (see [ an illustration of this algorithm). The samples that remain in this undersampled dataset constitute i.i.d. draws from the test distribution. Therefore, while a classifier trained this pruned dataset cannot suffer biases due to distribution shift, this algorithm is clearly wasteful, as it discards training samples. This perceived inefficiency of undersampling has led the design of several algorithms
combat such distribution shift (Chawla
et al. 2002; Lipton et al.) 2018 [Sagawa et al.) 2020 Cao et al. 2019: Menon et al.) 2020 Ye et al. 2020; Kini et al. 202 I| Wang al. 2022). In spite of this algorithmic progress, the simple baseline undersampled dataset remains competitive. In the case of label shift, where one class label overrepresented in the training data, this has been observed by Cui et al. | shift, study by Idrissi et al. 2022) showed that the empirical effectiveness of these more complicated algorithms is limited.
of training models
et al. (2019), and Yang & Xu (2020). While in the case of group-covare
For example, Idrissi et al. (022) showed that on the group-covariate shift CelebA dataset the worst- g group accuracy of a ResNet-50 model on the undersampled CelebA dataset which discards 97% of the available training data is good methods that use all of available data such importance-

---

Under review as a conference paper at ICLR 2023
No Undersampling
Undersampling
Leurned Boundary
Predicted Minority
Minurity Samples
Dropped Samples
Predicted Majority
Majority Samples
--
True Boundary
Figure I: 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.
weighted ERM (Shimodairal 2000), Group-DRO (Sagawa et al. 2020) and Just-Train Tea-Tr-in--cieee (Liu
et al. 2021). ). In Table we report the performance of the undersampled classifier compared to the state-of- tiee--of-hheartee the-arr-methods in the literature across several label shift and group-com covariate shift datasets. We find that, although undersampling isn't always the optimal robustness algorithm, it is typically very competitive baseline and within 1-4% the performance of the best method.
Table Performance undersampled classifier compared to the best classifier across several popular label shift and group-covariate shift datasets. When reporting worst-group accuracy denote it by When available, we report the 95% confidence interval. We find that the undersampled classifier is always within 1-4% of the best performing robustness algorithm, except the MultiNLI dataset.
Test/Worst-Group Accuracy
Shift Type
Dataset/Paper
Best
Undersampled
Imb. CIFARIO (step 10) (Cao et al. 2019
87.81
84.59
Label
Imb. CIFAR 100 (step 10) Cao et al.
2019
58.71
55.06
CelebA (Irissi et al. 2022
86.9 + 1.1*
85.6 + 2.3*
Waterbirds Idrissi et al.
2022
87.6 + 1.6*
89.1 +: 1.1*
Group-Covariate
MultiNLI Idrissi et al. 2022
78.0 + 0.7*
68.9 + 0.8*
CivilComments
(Idrissi et al.
2022
72.0 + 1.9*
71.8 + 1.4*
Inspired by the strong performance of undersampling in these experiments, ask:
Is the performance of model under distribution shift fundamentally constrained by the lack of minority group samples?
To answer this question we analyze the minimax excess risk. We lower bound the minimax excess risk to prove that the performance of any algorithm is lower bounded only as function of the minority samples (mmin). This shows that even if a robust algorithm optimally trades off between the bias and the variance, is fundamentally constrained by the variance on the minority group which decreases only with min
Our Contributions. In our paper, we consider the well-studied setting of nonparametric binary classification (Tsybakov 2010). By operating in this nonparametric regime able study the properties of undersampligg in rich data distributions, but are able to circumvent the complications that arise due the optimization and implicit bias of parametric models.
2

---

Under review as a conference paper at ICLR 2023
We provide insights into this question in the label shift scenario, where one of the labels is overrep- resented in the training data, Ptrain = 1) 2 Ptrain (y = -1), whereas the test samples are equally likely to come from either class. Here the cass-conditional distribution P(x: y) is Lipschitz in 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/ 1/3, That is, minority group samples fundamentally constrain performance under distribution shift. Furthermore, by leveraging previous results about nonparametrie density estimation (Freedman & Diaconis 1981) we show a matching upper bound on the excess risk of standard binning estimator trained undersampled dataset to demonstrate that undersampling is optimal.
Further, we experimentally show in 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 [0188] Hanneke & Kpotufe| 2019) from train to test distributions, often focusing on deriving specific conditions under which this transfer possible. In this work, we demonstrate that when the overlap (defined in terms of total variation distance) between the group distributions Pa and P& is small, transfer difficult, and that the minimax excess risk of any robust learning algorithm is lower bounded by 1 m/n 1/3 While this prior work also shows the impossibility of using majority group samples in the extreme case with no overlap, our results provide simple lower bound that shows that the amount of overlap needed 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 undersampled dataset.
Taken together, our results underline the need to move beyond designing "general-purpose" robustness
algorithms (like importance- weighting (Cao et al. 2019, Menon et al. 2020; Kini et al. 202 Wang al. 2022), g- g-DRO (Sagawa et al. 2020). JTT (Liu et al. 2021). SMOTE (Chawla et 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, Waterbirds), Idrissi et al.) (0022) showed that training ResNet classifiers performs as well as other popular reweighting methods like Group-DRO (Sagawa et al. 2020), reweighted ERM, and Just-Train-Twwe (Liu et al.] (021). They find Group-DRC performs compara- bly to undersampling, while both tend to outperform methods that don't utilize group information.
undersampled dataset either outperforms or
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 to overparameterieed neural networks. Many followup papers (Cao et al. 2019 Ye al., 2020 Menon et al. 2020) 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.
Our theory draws from the rich literature on non paraameerric classification (Tsybakov) 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 1985) to prove our upper bounds in the label shift case. Finally. we note that to prove our minimax lower bounds proceed by using the general recipe of reducing from estimation to testing (Wain) wright 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.
There is rich literature that studies 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- BoniD 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
3

---

Under review as a conference paper at ICLR 2023
from the target domain, rather than to characterize the relative value of the number of labeled samples from the majority and minority groups. Among these papers, most closely related to our work are those in the covariate shift setting (Kpotufe & Martinet, 2018 Hanneke & Kpotufe 2019). 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//2mnn 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. (2022) recently showed that undersampling can improve the worst-class accuracy of linear SVMs in the presence of label shift. In comparison, results hold for arbitrary classifiers with the rich nonparametric data distributions.
SETTING
In this section, we shall introduce our problem setup and define the types of distribution shift that 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 : [(x11, 31),,.., (In, yn)} E ((0, 1] x {-1,1})" that are all drawn from a train distribution Ptrain. During test time, the data shall be drawn from different distribution Prest. To present clean analysis, sis, we study the case where the features are bounded scalars, however, it is easy to extend our results the high-dimensional setting.
Given a classifier f R + (-1, we shall be interested in the test error (risk) of this classifier under the test distribution P Prest:
R(f; Ptest) == P [1((x) + v)].
3.2 TYPES OF DISTRIBUTION SHIFT
We assume that Pirain consists of mixture of two groups unequal size, and Prest contains equal numbers of samples from both groups. Given a majority group distribution P maj and a minority group distribution Pmnn. the learner has access to Maaj majority group samples and Timin minority group samples:
Smaj ~ P Pumi and Smin maj
P Ponin
min
Here Maajj > n/2 and 1mmin < n// with Meajj + A'min n. The full training dataset is S =
Smaj U Smin = [(1r1, 3/)) .1),..., (In, yn)) We assume that the learner has access to the knowledge whether particular sample (Is, yi) comes from the majority or minority group
The test samples will be drawn from Prsst = } P + P min+ uniform mixture over Pmaj and min- Thus, the training dataset is an imbalanced draw from the distributions P Pmaj and Pmin. whereas the test samples are balanced draws. We let p == Umaj/ Amin > denote the imbalance ratio in training data.
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 y = 1 the majority class. Then, we define the majority and the minority class distributions as
Pmaj [e, y) = (z) =1 1) and Pmin = (-)(())(y = -1)
where P1, 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 I-Lipschitz: for any x, x' E [0, 1].
PP.(z) Px())) < </ z').
We denote the class of pairs distributions (P (Pmaj. P min) that satisfy these conditions by Pis. We note that such Lipschitzness assumptions are common in the literature (see Tsybakov 2010).
4

---

Under review as a conference paper at ICLR 2023
3.2.2
SHIFT
In this setting, we have two groups {a, b). and corresponding to each of these groups is distribution (with densities) over the features Pa and Pa(x). We let correspond to the majority group and correspond to the minority group. Then, we define
P maaj (z, y) (a x) and (zin v) Po(x)P(y Iz).
We assume that for E {- for all I, x' E [0,
PVy x) P(y a²) S | a'|,
that is, the distribution of the label given the feature is 1 1-Lipschitz, and 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 Pb as follows:
Overlap(P a. Pb) == TV(Pa, Pb)
where TV Pb) == 1 Pa(E) Po (E)), denotes the total variation distance between Pa and Pa. Notice that when Pa and P have disjoint supports, TV(Pa, Pa) and therefore Overlap(P... Ps) O. On the other hand when P. Ps. TV(P.. Pb) = 0 and Overlap(Pas Pb) 1. When the overlap 1, the majority and minority distributions are identical and hence we have no shift between train and test. Observe that Overlap(P a, Pt) Overlap maj. min) since P(y x) is shared across Pmaj and Pmin-
Given a level of overlap [0, 1] we denote the class of pairs of distributions (Pmajo minn) with overlap at least r by PGs(T), easy to check that, PTS(T) S Pas at any overlap level 7 E [o, 1].
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 constrained by the number of minority samples Ammin- Before we state lower bounds, need to introduce the notion excess risk and minimax excess risk.
Excess Risk and Minimax Excess Risk. We measure the performance of an algorithm through its excess risk defined in the following way. Given an algorithm A that takes as input dataset S and returns classifier A and pair of distributions (P maj. min) with P Ptest = Pajj maj + P min- the expected excess risk is given by
Excess Risk[A; (Pmaj Pmiin] == B "sS-P"mmi x "min ;
Ptest)] (1)
where f" (P(tes) is the Bayes classifier that minimizes the risk R(-; Ptest). The first term corresponds to the expected risk for the algorithm when given maaj samples from maaj and mimi samples from P min, whereas the second term corresponds to the Bayes error for the problem.
Excess risk does not let us characterize the inherent difficulty of a problem, since for any particular data distribution (P majs Pmin) the best possible algorithm to minimize the excess risk would be the
trivial mapping S f' (P Therefore, to prove meaningful lower bounds 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 (Pmaj Pmi)
sup
Excess Risk[A; (Pmaj: Pmin))s
(2)
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 a lower bound on the minimax excess risk.
5

---

Under review as a conference paper at ICLR 2023
Theorem 4.1. Consider the label shift setting described in Section 3.2.1| Recall that PLs is the class of pairs of distributions (Pmaj: minn) that satisfy the assumptions in that section. The minimax excess risk over this class is lower bounded as follows:
1
Minimax Excess Risk(PLs) = inf
sup
Excess Risk[A; (Pmaj, P Pmnn)] 600
(3)
A (Pmaj Pmn))s
Tlmin 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 mm 1/3 and does not depend on memaj- Intuitively, this is because any learner must predict which class-conditional distribution (P(x 1) P(ar -1]) assigns higher likelihood at that æ. To interpret this result, consider the extreme scenario where 7mmaj - Do but 7emin is finite. In this case, the learner has full information about the majority class distribution. However, 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 z. This uncertainty underlies the reason why the minimax rate of classification is constrained by the number of minority samples mmin-
We also note that the theorem can be trivially extended to higher dimensions. In this case the exponents degrade to 1/3d rather than 1/3 is to be expected in nonparametric classification.
We briefly note that, applying minimax lower bounds from the transfer learning literature (Maity et al. 2020 Theorem 3.1 with = 1, 3 = 0 and d = 1) to our problem leads to a more optimistic lower bound of 1/n Our lower bounds that scale as 1/ //mi 1/3 uncover the fact that only adding minority class samples helps reduce the risk.
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. In the theorem below > shall be an absolute constant independent of Mmaj. Romin and T.
Theorem 4.2. Consider the group shift setting described in Section 3.2.2 Given any overlap
[] recall that (T) is the class of distributions such that Overlap majs P Pmin) 2 т. The minimax excess risk in this setting is lower bounded as follows:
Minimax Excess Risk(Pas( inf sup
Excess Risk[A; (P (Pmajy Pmin)]
A
(Pinj.Prin P(s))))
(4)
( (2- -3-T) T) + Majj 1/3 200 (/3 + 2)1/3
where p = mmmja/ Amin
We prove this theorem in Appendix C
We see that in the low overlap setting (r < 1/p), the minimax excess risk lower bounded by 1 1/nmin 1/3 and we are fundamentally constrained by the number of samples in minority group. To see why this is the case, consider the extreme example with = O where P. has support [0, 0.5] and Ps has support [0.5, 1]. The Tmmaj 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 Pt). Thus, predicting samples from the minority group and this results in the mmii dependent rate. In fact, in this extreme case (r 0) even if nmajj co, the minimax excess risk is 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.
the support of P, requires
On the other hand, when the overlap is high (r > 1/p) the minimax excess risk is lower bounded by 1/(mmin - 7) + 7 1/3 and the extra majority samples are quite beneficial. This roughly because the supports of Pa and Ps have large overlap and hence samples from the majority group are useful in helping make predictions even in regions where Ps is large. In the extreme case when 7 1, we have that P. P, and therefore recover the classic i.i.d. setting with no distribution shift. Here, the lower bound scales with 1 1/n-/3 as might expect.

---

Under review as a conference paper at ICLR 2023
Identical to the label shift case, the theorem can be extended to hold in higher dimensions with the exponents being 1/3d rather than 1/3.
Previous work transfer learning with covariate shift has considered other more elaborate notions of transferability (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 with 1, B 0 and y oo) yield the same lower bound of m/i 173. Beyond the case of no overlap (T O), our lower bound is key to drawing the simple conclusion that when overlap is small between group distributions, minority samples alone dictate the rate of convergence. On the other hand, when the overlap is large our bound tells us that all samples can help reduce the risk.
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 undersampling is an optimal robustness intervention. We start by defining the undersampling procedure and the undersampling binning estimator.
Undersampling Procedure. Given training data == ((11,81),.... (Z vn)), generate new undersampled dataset Sus by
including all miin 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| 2/1min
The undersampling binning estimator defined next will first run this undersampling procedure to obtain Sus and just uses these samples output classifier.
Undersampled Binning Estimator The undersampled binning estimator AusB takes as input dataset S and a positive integer K corresponding to the number bins, and returns a classifier A [0, 1] + 1}. This estimator is defined as follows:
1. First, we compute the undersampled dataset Sus-
2. Given this dataset Sus, let ni.j be the number of points with label +1 that lie in the interval
15 1=1 K k. Also, define n-1.; analogously. Then set
f
if n1 > n-1 otherwise.
A
S.K 3. Define the classifier A such that if I, then
A (x)
(5)
Essentially in each bin Ly. we set the prediction to be the majority label among the samples that fall in this bin.
Whenever the number bins K clear from the context we shall denote AS.. by A Below we establish upper bounds the excess risk of this simple estimator.
5.1 LABEL SHIFT UPPER BOUNDS
We establish upper bound the excess risk of Ause in the label shift setting (see Sec- tion 3.2.Ip. Below we let c, > 0 be absolute constants independent of problem parameters like Mmaj and Ammin-
7

---

Under review as a conference paper at ICLR 2023
Theorem 5.1. Consider the label shift setting described in Section the expected excess risk of the Undersampling Binning Estimator (Eq. 5
3.2.1 For any (Pmaj. Pmin) PLs
with number of bins with
K c/ min 1 is upper bounded by
C
Excess Risk[AUsB: (Pmaj: Pmin)] =
SNPP mmaj
xP [A(AAUsB: Prst R( ;
Prest)
Tomin 1/3"
We prove this result in Appendix B
This upper bound combined with the lower bound Theorem 4. shows that undersampling approach is minimax optimal up constants in the presence of label shift.
Our analysis leaves open the possibility of better algorithms when the learner has additional infor- mation about the structure of the label shift beyond Lipschitz continuity. We also note that it is straightforward to generalize the upper bound higher dimensions with the exponent being 1/3d instead of 1/3.
5.2
GROUP-COVARIANE 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 problem parameters m'ajj Tmmn and T.
Theorem 5.2. Consider the group shift setting described in Section 3.2.2 For any overlap T E [0, 1]
and any (Pmaj, Pmin) E (TG the expected excess risk of the Undersampling Binning Estimator (Eq. 5 with number of bins with K = [mimin 1/3 is
C
Excess Risk[AusB: (Pmaj Pmin)] E.Spppm "mmmi ma
x xPinn [R(AUSB: Ptest) R(f"; Ptest)]
S
1lmin 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 7) +
1/3 7maj?)) the upper bound for the undersampled binning estimator always scales with 1/11min 1/3 since it operates on the undersampled dataset (Sus).
Thus, have shown that in the absence of overlap (r < 1/p mmmnn/ (maj) there is under- sampling algorithm that is minimax optimal up to constants. However when there is high overlap (T 1/p) there is a non-trivial gap between the upper and lower bounds:
Upper Bound
Lower Bound = c(p + + 2
Again this upper bound can be generalized higher dimensions.
MINORITY SAMPLE DEPENDENCE IN PRACTICE
Inspired by our worst-case theoretical predictions in nonparametric classification, 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 CIFARIO 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 5:1 label imbalance. We then use 80% of those examples for training and the rest for validation. our experiment, we either (a) add only minority samples; (b) add only majority 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 (Kini et al. 2021). We early stop using the importance weighted validation loss both cases. The additional experimental details are presented in Appendix
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
8

---

Under review as a conference paper at ICLR 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 CIFAR 10 dataset with 5:1 label imbalance. (Top) Models trained using the importance weighted cross entropy loss with early stopping. (Bottom) Models trained using the importance weighted VS loss (Kini et al.) 202T) with early stopping. We report the average test accuracy calculated on balanced 5 random seeds. We start off with 2500 cat examples and 500 dog examples in the training dataset. We find that in accordance with our theory, for both of the classifiers adding only minority class samples (red) leads to large gain in accuracy (~ 6%), while adding majority class samples (blue) leads to little or no gain. In fact, adding majority samples sometimes hurts test accuracy due to the added bias. When add majority and minority samples in a 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.
set over
adding only majority class samples the test accuracy remains constant or in some cases even decreases owing 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 and on the left panels, we see that 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 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 [).
7 DISCUSSION
We showed that undersampling an optimal robustness intervention in nonparametric classification in the absence of significant overlap between group distributions or without additional structure beyond Lipschitz continuity. At a 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 us to step away from the common practice in robust machine learning where the focus is design "universall" 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 test time.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Michael Alcorn, Qi Li, Zhitao Gong, Chengfei Wang. Long Mai, Wei-Shinn Ku, and Anh Nguyen. Strike (with) a 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 arXiv:2205. /167, 2022.
Shai Ben-David and Ruth Urner. On hardness of domain adaptation and the utility of unlabeled target samples. In Algorithmic Learning Theory (ALT), 2012.
Shai Ben- and Ruth Umer. 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 Neural Information Processing Systems (NeurIPS), 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 on 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 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 Machine Learning (ICML), 2019.
Clément Canonne. A short note on an inequality between KI. and TV. arXiv preprint arXiv:2202.07/98, 2022.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with label-distribution- aware 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 Statistics (AISTA7S), 2010.
Luc Devroye and László Györfi. Nonparametric density estimation: the L1 view. Wiley Series in Probability and Mathematical Statistics, 1985.
David Freedman and Persi Diaconis. On the histogram as a density estimator: L2 theory. Zeitschrift für Wabhschhenniccheiittteeee und verwandte Gebiete, 1981.
Steve Hanneke and Samory Kpotufe. On the value of target data in transfer learning. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographies in repeated loss minimization. International Conference on Machine Learning (ICML), 2018
Dirk Hovy and Anders Søgaard. Tagging performance correlates with author age. In Association for Computational Linguistics (ACL), 2015.
Badr Youbi Idrissi, Martin Arjovsky. Mohammad Pezeshki, and David Lopez-Paz. Simple data balancing achieves competitive worst-group-aceuraey. In Causal Learning and Reasoning, 2022.
10

---

Under review as a conference paper at ICLR 2023
Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak, and Christos Thrampoulidis. Label- imbalanced and group-sensitive classification under overparameterizzaton. In Advances Neural Information Processing Systems (NeurlPS), 2021.
Samory Kpotufe and Guillaume Martinet. Marginal singularity, and the benefits of labels covariate- shift. In Conference On Leurning 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. In International Conference on Learning Representations (ICLR), 2020. 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, Perey 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 the label shift problem. arXiv preprint arXiv:2003. 10443, 2020. 20200.
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 Statistical Planning and Inference, 2000.
Rachael Tatman. Gender and dialect bias in youtube's automatic captions. In ACL Workshop Ethics Natural Language Processing, 2017.
Alexandre Tsybakov. Introduction to Nonparametrie Estimation. Springer, 2010.
Martin Wainwright. High-dimensional statistics: A non-asymptotic viewpoint. Cambridge University Press, 2019.
Byron Wallace, Kevin Small, Carla Brodley, and Thomas Trikalinos. Class imbalance, redux. In International Conference on Data 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 Representations (ICLR), 2022.
Larry Wasserman. Lecture notes in nonparametric classification, 2019. URL httphttts:://e stat
cmu. cmu. www.:eeo//llarrysssm//oooaaarass
pdf [Online; accessed 12-May-2022].
Wikipedia contributors. Poisson binomial distribution dia, 2022. URL latpps://en
Wikipedia, the free encyclope- wwwpptttee-Poiissseeeeee. http:///pp.pppppttttttooooooooo.
binomia htt.aaaaaaaaatttoooosseeeeeeeaaa
[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 imbalanced deep learning. arXiv preprint arXiv:2001.01385 2020.
11

---

Under review as a conference paper at ICLR 2023
A TECHNICAL TOOLS
In this section we avail ourselves of some technical tools that shall be used all of the proofs below.
A. REDUCTION TO LOWER BOUNDS OVER A FINITE CLASS
The lower bound on the minimax excess risk will be established via the usual route of first identifying a "hard" finite set problem instances and then establishing the lower bound over this finite class. One difference from the usual setup in proving such lower bounds (see Wainwwriht 2019 Chapter 15) is that the training samples are drawn from an imbalanced distribution, whereas the test samples are drawn from a balanced one.
Let P be a class of pairs of distributions, where each element (Pmaj, Pmin) E P is pair of dis- tributions over [0, 1] {-1,1). As before, let Prest denote the uniform mixture and P min- We let V denote finite index set. Corresponding to each element E V there is P. (P& P..maja P Pu,min)
Pmaj
with Pu,test (P [Pe.maj + /22 Finally, also define pair of random
variables (V, () as follows:
1. V a uniform random variable over the
2. (S V= v) P P"mai
m.j X - is an independent draw of maaj samples from Puymaj and
Mmmi samples from P p.min-
We shall let Q denote the joint distribution of the random variables (V, and let Qs denote the marginal distribution of S.
With this notation in place, we now present lemma that lower bounds the minimax excess risk in terms of quantities defined over the finite class of "hard" instances Pv.
Lemma A.1. Let the random variables (V, S) be as defined above. The minimax excess risk lower bounded as follows:
Minimax Excess Risk(P) = inf sup (Pnni,min) PPP
E S-
Pmail xP'lnin maj
(((APPPtes)) (Rff"(Peesd Ptest)
2 Ry Bv,
where By and Bayes-error By are defined as
Ry = Es-Qs [inl P F(a.)>> Q(vlS)) (1(x)) + y)},
By == Ev [ (Pv,tes);; Pv,test))
Proof. By the definition of Minimax Excess Risk.
Minimax Excess Risk = inf sup A (Pmaj (Pinj,PannEE
E SPPPia xP : Ptest)) - (R(f((Ptest) Prest)
2 inf sup E
[R(AS: s: Pu,test)] - R(f (offf(PP,teee (Pv,test;; Po,test)
A NEV
2 inl Ev [ [ESI
[R(AS: Pv,test)) - (Pviest)))s))) P Py.ces)))
Time way
Vinin
inf Ey [E SEvV (oa
[R(AS: PV.ces))) [V[RR[ (P (itees): P Pv.cest)
x
Pinin
V.mn
=By
We continue lower bounding the first term follows
inf Ev E BSSV
A
"eaj V.mai V.
"mii
[R(AS: Pv.test)]]
= inf
A
(A # y)]
inf Es Ev-q (P)) (AA (x) ) v)1
2 Es-Qu |inl Ev~q (P. (M(x) + r)]l
Es-qs [inf IP (x.)) Q(v19)P (h(2)) + v)
Ry.
12

---

Under review as a conference paper at ICLR 2023
where (i) follows since A is 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 to prove our lower bounds. Given a positive integer K the hat function defined as
x +
4K
1
4K
for E
[ 2K: 0
Φx
(z)
for [0, 2R otherwise.
(6)
1K
When K clear from context, we omit the subscript.
Hat Function (04)
0.00
00.05
0.2
0.1
0.0
0.1
0.2
Figure 3: The hat function with K 4.
We first notice that this function I-Lipschitz and odd, so
2x
Φx (x) dr 0.
+
We also compute some other key quantities for á Lemma A.2. For any positive integer K,
o (x)) dr
8K2
Proof. We suppress in the notation. We have that,
2k
1
x
[o(x) dx
dr
dr.
4K
4K
4K
4K
The integrand thus has area 16K2 Therefore,
over
0]
defines triangle with base
2K and height ak*
4K
2K
1
1
+
dr
4K
4K
16K
The same holds for the second term. Thus, by adding them up get that tेe [o(x)) dr
S
13

---

Under review as a conference paper at ICLR 2023
Lemma A.3. For any positive integer K,
! log
Φx (3r 2R
(1 ØK
x- 2k ))
dæ S
1 Φx (2: ER
3K3
and
Jo x
1 Øx (x
1x) 1+0x (x 2k
(1 (1-0k
2K )) da 1
1 ]
log
ΦK
3K3
Proof. Let suppress K in the notation. We prove the first bound below and the second bound follows by an identical argument. We have that
k
+ 6( 2k
1+ x 2K )) dr
log
1 6(I
2K
1 + x(x)
log
(1 + +(x)) dr
1 ((x)
2k
1 ((x)
0
1 + x(x))
log
(1 +(x)) dr +
log
(1 +1+ (1+)(1)) dæ
1 ((x))
1 x(x))
1 (xx)
(1 Φ(-x)
log
(1 ((x)) dx
log
(1+ + (x))) dr
Ju
1 ((x)
1 øl xx-x)
Ix
I
( ((z) 1 - 6(x)
1 - <(x)
log
(1 + x(x)) dr +
log
(1 - o(x)) dx,
Jo
1 x(x)
where the last equality follows since is an odd function. Now, we may collect the integrands to get that,
1 + 6(x
x 2x)
))
log
1 1
2K dr
1
+ ((x))
2
log
δ(x) dx
1 - Φ(x)
ix
26(x)
2
log
1 1- --x(x)
((xx) dr
0
*
20(x)
<
2
dx,
J0
((x)
where the last inequality follows since log(1 + x) S for all x. Now we observe that ((x) S x
for x E [0, 3. and in particular, I-0(4] S 2. Thus,
/ log
1 + 61 2x)
1 111
)) dæ
1 Φ
1 6(x 2k
I
2K
8
(xx)² dx
< 8
a dx
3K3
This proves the first bound. The second bound follows analogously.
14

---

Under review as a conference paper at ICLR 2023
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. through sequence of lemmas we prove the minimax lower bound Theorem 4.1 Next, in Appendix B.2 we prove Theorem 5.1 which is an upper bound on the excess risk of the undersampled binning estimator (see Eq. (5) with [mmin 1/3 bins by invoking previous results on
nonparametric density estimation (Freedman & Diaconis 1981 Devroye Györfi 1985).
B. PROOF OF THEOREM 4.1
In this section, we provide a proof of the minimax lower bound in the label shift setting.
We will proceed by constructing a class of distributions where the separation between any two distributions the class small enough such that it hard to distinguish between them with finite minority class samples. In particular, distribution on each sub-interval either has slightly more probability mass on the left side of the sub-interval, the right, or completely uniform. Since the minority class sample size is limited, classifier will be able to tell which distribution the minority class is generated from, and hence will suffer high excess risk.
split the interval [0, 1] into sub-intervals and each class
We construct the "hard" set of distributions as follows. Fix K to be an integer that will be specified
in the sequel as function of Aminn Let the index set be V { 1-1,0, 1] x {-1,0, 1) For will let #1 E 0,,, be the first K coordinates and v- { (- 13 be the last K coordinates. That is, = v-1)
For every E P we shall define pair of class-conditional distributions P.,1 and P Pu,-1 1 follows: for 1 = |=1 K k
j + 1/2
Pe.1(z) = 01.00
K
j 1/2
P Pr.-1(z) 1 1+
1-
K
where is defined in Eq. Notice that Pe,1 only depends on U1 while Ps,-1 only depends on V-1- We continue to define
P Pr.maj (Ir, y) Po. (x) 1)
P Pu,min (x, y) (x) = -1),
and
P (I, y) + Po.min(x,3)
P 1) to
P Pu,test (z.
2
2
Observe that in the test distribution is equally likely for the label to +1 or
Recall that as described in Section A. V shall be uniform random variable over V and S V ~ pitmaj e.maj Pumiis
We shall Q denote the joint distribution of (V,S) and let Q, denote the marginal
over S.
With this construction in place, we first show that the minimax excess risk is lower bounded by Lemma B.1. For any positive integers K, Amaj. Pmnin the minimax excess risk is lower bounded as follows:
Minimax Excess Risk(Pis)
inf
sup A (Pmij Pann) EPis
E R.SppTm may x pmin [R(AS; Ptest) R(J*; Ptest)]
|S), Σ Q(v s)P )
Es-Qu
TV
Σ
DQ(
Q(u
36K
2
4EV
15

---

Under review as a conference paper at ICLR 2023
Proof. By invoking Lemma
A.1
get that
Minimax Excess Fisk(PLs)
Es-Qs [inf PP (a.)> P(els)P e.s (h(x)) + v)] By (Pvtttt) P Pv.rest)
(Pittt));
:25
We proceed by calculating alternate expressions for Ry and By to get our desired lower bound on the minimax excess risk.
Calculation of Ry: Immediately by Le Cam's lemma (Wainwright 2019 Eq. 15.13), we get that
Ry = Es-Qs
inf IP
(x..)(
Q(olS)P (h(x) + v)
S)) -S)P..-.) )
Es-Qs
- TV Σ
S))
Σ [
(8)
2
WEV
VEV
Calculation of By: Again by invoking Le Cam's lemma (Wainwrighl, 2019 Eq. 15.13), we get that for any class conditional distributions P1, P-1,
1 R('"; Prest)
TV(P),
2
2
So by taking expectations, get that
By = Bv (P.teest) Pv.cest) = Ey
1
TV(P,,,
(9)
2
2
We now compute By [TV(Pv,, Pv.-2)] ]) follows:
Ev
Ev
[Pv.(x)) Pv.-1(z)| dx
2
z=0
K
Ev
V11 - V-1a1 Φ
dx
2
K
K
g Viis - V- (
j 1/2
Ey
dx
2
K
j=1
Ev VV - V-1alls
16K
where (i) follows by Lemma A.2 Observe that Vi V-1,5 are independent uniform random variables on (, 1}, is therefore straightforward to compute that
Evi|Vi V-1
This yields that
Ey [TV(Pv.
Pv.-1)] (TV(Pv..Py..i)) =
18K'
Plugging this into Eq. 9 allows to conclude that
1
1
By Ey (P(.t(( (Pv.test); Pvttest))
(10)
2
18K
Combining Eqs.
8 and 10 establishes the claimed result.
16

---

Under review as a conference paper at ICLR 2023
In light of this previous lemma aim to upper bound the expected total variation distance in Eq.
Lemma B.2. Suppose that is drawn uniformly from the set { {-1,1}K and that S is drawn from
Pu Pilmis e.maj u.min then,
Q(u (S)Pu, v, EQ(u) S)P )
Es TV Σ
1
(-
7m
exp
18K
144K
3
VEV
Proof. Let 1b = Es
TV (Erev Q(v (S) EvEv Q(v (s){))),,))]] Then,
Σ Q(v s), [Q(uIS)Po.)) sSpp...))
3 = Es
TV
DEV
VEV
Es
P pv)) dr Q(r () (P (1)
NEV
Es
EQ(u (P,, - (x)) dr
Q(ui
NEV
1+ EQ(ul Q(u (ols)(u1, v-13)0 -- /+1 1/2
Es
dx
where the last equality is by the definition of P., and Pe,-1- Continuing we get that,
K
j + 1/2
x
dr Es
Σ LEV
Q(u |S)(1s) v-1.5)
K
Es
Σ
Q(v () - --11))
16K
1=
K
1
Quv (S1 v-1.))
dQs(S)
16K
j=1
PEV
K
1
Quu, S)(15 - --11)) ds
16K
2=1
VEV
(18)
Σ Q(S v)( - v-1s) dS,
16K
V
.EV
where (i) follows by the calculation in Lemma A.2 and variable over the set
(ii follows since is uniform random
The distributions Po.: and Pu.-1 symmetrically defined over all intervals 1, = [ * and
hence all of the summands in the RHS above are equal. Thus,
/
Σ NEV
Q(S ( -v011,
v-1,)) ds.
(11)
16K
Before we continue further, let us define
- (vEV 11,1 v-11).
17

---

Under review as a conference paper at ICLR 2023
For every E V+, let e V be such that is the same all coordinates, except U1,1 -1,1 and 8-1,1 = 1-11-- Then continuing from Eq. [II we find that,
Σ (11,1 U-1.) v) Q(5 6)) ds
16K
Σ (01,1 -011)111)))06 v) Q(S 6) ds
16K|V|
1
Σ (V1,1 v-1,1) [Q(S) Q(S B) as
16K
Σ EEV+
(V1,)
(VI))) v), Q(S) 6)),
(12)
8
where (i) we use the definition of V and i, (it) follows since v1 v-1,1 1.1 for E V+
Now further partition V into 3 sets (1100) 1(0,-1, ((1-1) follows
((100) = {u V 11 1-1 = 0},
(00,-1 = (UE U1, 0,u-1,1 = -1}
V(1-11 = fu V U1 = 1, 111-1,1 = 11..
Note that Q(S v)
Rimaj v.maj
Pmii v.min
and therefore
Σ (11,1 - E-LIVV
(P
v,maj
X Prmminn
Pumm U.maj
Pimmi
6.min
DEV+
Σ
TV
Pimmi v.maj
Pimmi v.min
Pinaaj E,maj
X Piiin E,min
*EV(1.)
TV
(P (Pimmy
Bjmajj
X P Piinii
a.min
Pitmii s.min
1) 1)
+ 2
Σ
TV
Phnai v.maj
X
Phmmis
m.min:
Piaa E.maj
X
Timin
F.min
(13)
-EV(L-1)
where (1) follows since u1 v-1 E f-1,0,13 and by the definition of the sets (LLD)) v(u.1) and (1,,1),
Now by the Bretagnolle-Huber inequality (see Canonne 2022 Corollary 4),
TV ( Pl
X
Pimm Pimjj ä.maj
n. min
Pimin 8,min
TV
(p (Pima H,maj
X pitmin 8,
Pleajj e,maj
< 1
exp
(-KL KL
Romy Ejmaj
X
Priin 8,min
| /
e,maj
x
Penin e.min )):
where we flip the arguments in the first step for simplicity later. Next, by the chain rule for KL-divergence, we have that
(L Rmajj 8.maj
||
Prmini ) MLaj (..L() || Pu,.aa)
+ mm KL. 8,min l (P..min).
Using these, let us upper bound the first term in Eq. corresponding (00--), notice that KT.(P,, i,mjjl majillPu.mm Po.maa) since U1 θτ for all j E {1,..., K}. For the
(00--1), For
18

---

Under review as a conference paper at ICLR 2023
second term, KL(Pas a,min (P,,minn)) only V1,1 and 01,1 differ,
/ P Pr) log
P Pr,-((z)
KL(P P P.,min) =
dr
P Pc.-1(z)
= 1 log
Φx 2R)
(1 (1+
x 2x
2K ))
Ox
dæ
1 ØK (x 2k
3K3
where the last inequality is result of the calculation in Lemma A.3 Therefore, we get
Σ TV
P
Ting u,maj
X P
Nimin u,min:
X P Plmin E,min
- k-
(1 exp
(-
71
m,maj
2
333
V
1)
For the terms in Eq.
13
corresponding (00-1), 1010-1,),111) we simply take the trivial bound to get
V(1,1),
Σ
TV
(Prmi v.maj
x Primin
s.min
P Pimaj 0.maj
Pimii a.min
S 9K-1
1)
Σ
p Pim TV
n.maj
X P
mimi
Piaaj m.maj
ä.min
I
59K-1 9k
1)
Plugging these bounds into Eq.
13 we get that,
gk-
E 4 gk 9--1
10
2 exp
3K
Now using this bound on =\t in Eq.
12 and observing that [ = 9 we get that,
Es
TV
E Q(ui
s)),,,,
Σo(
Q(u (S)
NEV
9K-1
4. 4.9k-1
(-
1min
cxp
8 8. 99 K
2
3K'
1
Rmin
exp
18K
144K
3K3
completing the proof.
Finally, combine Lemma B.1 and Lemma B.2 to establish the minimax lower bound in this label shift setting. We recall the statement the theorem here.
Theorem 4.1. Consider the label shift setling described in Section 3.2.1 Recall that Pis the class of pairs of distributions (P maj. P min) that satisfy the assumptions in that section. The minimax excess risk over this class lower bounded as follows:
Minimax Excess Risk(PLs) = inf sup
Excess Risk[A; (P (Pmaj. Pmin)]
(3)
600 T9min 1/3
(P (Pmaj:F PLs
Proof. By Lemma B.I we know that,
Σ Q( (Q(11S)Po.-1) )
TV Σ Q(o 1 S)P
Minimax Excess Risk (Ls) 2
Es-Qs
36K
2
KEEV
vev
Next by the calculation in Lemma B.2
have that
1
1m 333
Minimax Excess Risk
Risk (Pis)
exp
36K
18K
144K
1
12min
288K
exp
3K3
19

---

Under review as a conference paper at ICLR 2023
Setting K
12in 1/31 yields the following
mimi
Minimax Excess Risk(Pis) 2
288 11 1/3 exp
m/n 1/3
exp
3 1lmin 173
Timis
Ammi
1/3
1
288
1mmn 1/3
TAmin 1/3
0.7 exp (-3
3
288
A'mi 1/3
IV
600 Pemin 1/3
where (i) follows since Amin 1/3 h//////////////// [[[mmmn 1/3
0.7 for mmmi 2
B.2 PROOF OF THEOREM 5.1
In this section, we derive an upper bound on the excess risk of the undersampled binning estimator AusB (Eq. (5) in the label shift setting. Recall that given dataset S this estimator first calculates the undersampled dataset Sus, where the number of points from the minority group (Amin) is equal to the number of points from the majority group mmin,), and the size of the dataset is 2m Throughout this section, maja minn) shall be an arbitrary element of PLs.
To bound the excess risk of the undersampling algorithm, will relate it density estimation.
Recall that n1. denotes the number of points Sus with label +1 that lie in Ij. and n-1.; is defined analogously.
Given positive integer K, for I, = 1 1 by the definition of the undersampled binning estimator (Eq. (5)
if my > n- otherwise.
AusB (x)
(-1
Recall that since have undersampled, E, R1. E, n mmmin Therefore, define the simple histogram estimators for (I P(r y 1) and P P_((x) P(x =1) as follows: for
E lj.
(x)
1J K Amin
and
Ps (x)
1.
K T0min
With this histogram estimator in place, may define an estimator for 71x) = Prest (y) 1/xx) as follows,
(x)))
(x))
PT(x) + PS.
Observe that, for x E I
(x 1/2 n1 > Pn-5
A =
Defining estimator Sj for the Prest (y 1 |x) in this way will allow us to relate the excess risk of Ause to the estimation error in PS and ps. 1-
Before proving the theorem we restate here.
Theorem 5.1. Consider the label shift setting described in Section
3.2.1 For any (Pmaj Pmin) E PLs
the expected excess risk of the Undersampling Binning Estimator (Eq. 5p with number of bins with
K c. m'mi 1/31 is upper bounded by
C
Excess Risk[Ausa (Pmaj Pmin)] E5 SNUP Pmaj "mni [R(ASSE: Prest) R(f"; P Ptest)
7omin 1/3
20

---

Under review as a conference paper at ICLR 2023
Proof.
By the definition of the excess risk
Excess Risk[AAusB; (P maj: mmin]] == I2 SmP mii xPiii
|R(AUSB: Prest)) - R(f"; Pres)].
By invoking Wasserman 2019 Theorem 1) we may upper bound the excess risk given a draw of by
R(AúsB: Prstt)
- 2
1 (1())) -7(2)) P Prese
dr.
Continuing using the definition of fj$ above and because 7) PI/(PI + P-1) have that,
R(AÚSBi Ptest)
R(J"; Prest)
2 f.
(f())
P1(x)
(P((x) + PP de
(f()) + P=)(x)
(1 + P (3)
2
/.1)
P1 + P-)
Pf(x)) - P1(x)) dx
Pf(x) + +
/
(1())) - Pi(x) dx + /
Pi(x) + PP-1
(x) dz
Pf(x) + +PS (x)
/
Pf())) - P1(1)
dæ + //
(f(()) -P- Pi(x) - P-1(z)
(5(())
dr
(z(2) + P.. (2)
2 / |p((x) PI(x) dr + S .s. p01(2) - -P-1(x) dr
(2)
2/ [' (Pf(s)-P1(0)) dr V. (P)t)) dx,
(x))))
where (i) follows by the triangle inequality, (di) is by the Cauchy-Schwarr Schwarz inequality.
Taking expectation over the samples S and by invoking Jensen's inequality we find that,
Excess R (P (Pmaj, Pmnn))
= Es [R(AUSBi Prest)) Ptest)]
s V Es [ (P(()) dx
+ Es // (PS
-P))()))) dr
We note that PS only depends on mmin i.i.d. draws from class j. Thus by (Freedman & Diaconis 1981 Theorem 1.7), if K
c. em 11/3 then
/ (=) Py(x) 2 dr <
C
Es
1mmn 2/3
Plugging this into the previous inequality yields the desired result.
C PROOF IN THE GROUP-COVARIATE SHIFT SETTING
Throughout this section we operate in the group-covariate shift setting (Section 3.2.2
We will proceed similarly to Section We shall construct family of class-conditional distributions such that 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-inter sub-interval. On the other hand, will construct the group-covariate distributions to be separated from one another. As a 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 be able to learn the maximally likely label and result shall suffer high excess risk.
we prove Theorem 4.2 the minimax lower bound through a sequence of lemmas. Second in Appendix C.2 we prove Theorem that upper bound on the excess risk of the undersampled binning estimator with [2 1/3 bins.
First in Appendix C.I
21

---

Under review as a conference paper at ICLR 2023
C.I 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 follows. Let the index set be 1-1,13% For every
E V define distribution as follows: for E 1 [ #
+ ejo (x- (x- 2 1/2
P ( 7
K
where ø is defined in Eq. Given a [0, 1] also construct the group distributions as follows:
2 - T
if [0, 0.5) if [0.5, 1],
Pa(x) (z)
and let
Po(x) = 2 -PPa(())
We can verify that
{
Overlap(Pa: Pb) TV(P,, Pb) = =1 2=-0
[a((x) -P(())] dr=
We continue to define
P P.jmaj (xt, 9) = P.(y x) Pa(x)
P P. (z, v) Po(y x)) Pb))
and
P (x(x) + Pa(a)
P Pu,test (z, 3) Pv(y x)
2
Observe that (Pa(z) + P( = the uniform distribution over [0, 1].
Recall that as described in Section A.1 V shall be uniform random variable over V and S V ~ We shall let Q denote the joint distribution of (V.S) and let Qş denote the marginal
Pr e.maj Pumii
over S.
With this construction in place, we present the following lemma that lower bounds the minimax excess risk by sum of KL(Q(S ey = Q)I Fy = 11) is a measure of how difficult it is to identify whether ey = 1 or B/ = from the samples.
vy = Q)I[Q(() v, -11 1)) over the intervals. Intuitively,
Lemma C.1. For any positive integers K, mmajj mimi and T E [0, 1]. the minimax excess risk is lower bounded as follows:
Minimax Excess Risk(Pos(T)) inf
sup (Pra) Pmn Pos(T)
E Sg "imin maj
[ :test) R( Ptest))
min
exp(-KL(Q(S) vy 1)|[((S) u. -1))-
32
f=1
Proof. By invoking Lemma A. we know that the minimax excess risk lower bounded by Minimax Excess Risk(Pes(T))
Es-qs [inl P h (a.y)~ Q(v[S) (M(x) + v)] Ey [v[RR[( (Pv,tes)); Pv. }}
BBy
=Bt
where V is uniform random variable the set S V is draw from P o.maj Q denotes the joint distribution over (V,S).
X v.min and
We shall lower bound this minimax risk in parts. First, we shall establish a lower bound on Ry, and then upper bound the Bayes risk By.
22

---

Under review as a conference paper at ICLR 2023
Lower bound Ry.
Unpacking Ry using its definition get that,
Ry Bs-Qu [inf P (a.)) Q(v)S) (m(x) + y)]
ho
inf /
= Qs
a Re + yl dx
① Eg-Qu
(res((e)
min
Q(u [((1s))p(111 S)),(1
Σ
Q(u ()),(-1
dx
VEV
DEV
1%' PPootal
(i))
Bs-as
Q( (tols) xx) dr
2
DEV
(86i) 1
Prest (3t Es-aa
Ea(u Q(u P)) (2)
(1Pp((1()))
dr,
(14)
2
2
where (i) follows by taking h to be the pointwise minimizer over x. (ii) follows since P. x)
1 (1 x) and min 1 - =) = | 11-22 2s()/2 for all [0, 1]. and (iii) follows by Fubini's theorem which allows us to switch the order of the integrals.
I E I, = K & for some j E fI...., we let ja denote the value of this index j. With this notation in place let continue upper bound integrand in the second term in the RHS above as follows:
Es~Qs
Σ
Q(u
S)) x+)
BEV
In + 1/2)
Es-Qs
1Q(0%= 1 () Q(v,, --1 ||)s|
K
fx 1/2
EsnQs [QQ(y, 1| 5) Q(1i. S)]l
K
In + 1/2)
Q[S|| 1/ 1)Qv (2i 1) Q(S) U/ 1)Q -1)
x
K
Esnos
Qs(5)
Qs(5)
(181)
1
②
jz + 1/2
TV(Q(S) U/2 ==== =1, 1), Q(S1 U/ =-)))
(15)
2
K
where (i) follows since (1(1l))=(1+)) 6(x (j 4/2))/KKKK) 2 and by marginalizing Q(v S)
over the indices * jz, (ii) follows by using Bayes' rule and (Mi) follows since the rotal-variation
distance is half the & distance. Now by the Bretagnolle- -uber inequality (see Canonne 2022
Corollary 4) we get that,
TV(Q(S Uj = 1), Q(S Uj. -1))
< 1 exp( exp(-KL(Q(S) vy. Q)[[((S)) uy = -1)))
(16)
Combining Eqs. 14 (4-166) get that
Ry
1
(2 x
fx + +1/2)
2
2 2
(z)
dr
//'' Prest(a)) 1
ju + 1/2
+
exp(- "y. = 1)|[((S)) 10, = 1))) dr. (17)
4
K
23

---

Under review as a conference paper at ICLR 2023
Upper bound on By:
The Bayes error is
By = Ey (Pv):))
inf E (a.y)>PPe aan (f((x) # v)
Ev
Ev
inf
(est(a)) x)](f(() = =
== VE(-1.1)
Ev
P test (2)
min yE(-1,1}
P Prçcost (y 2²)
Ev
1
P Prest()) P Vistes(1 x)) - Pu.test (-1 x:) dæ
2
==0
1
fx 1.+1/2
Ey
1
Prest (2) 1
dr
2
K
x==
1
iz +1/2
Prsst (x)
Φ x
dx.
(18)
2
K
x=0
where (1) follows since (1
(x)= P - x) and min s) = (1 -1 2s))/2 for all
E [0, 1]. and (ii) follows by our construction of P. above along with the fact that (1 x)
1 - (-1
Putting things together:
Combining Eqs. 17 and (18 allows to conclude that
Minimax Excess Risk(Pas(T))
x In + 1/2
2
Prest (2)
exp(-KT((Q(S 1/2 = []][ uy. -1]) dr
K
K
j 5+ ---+1/22
) exp(-KI(Q(5) my = 1)(IQ(S) = -1)) dx
Prest (z) Φ x
K
)=1"
exp( (TS(QS1) v, =]][|((} uy = -1])) [ Pres((t)
j 1/2
) dr
x
K
j=1
K
cxp(-KI(Q(S) uy 1)) by = --))),
32K²
where (1) follows by using Lemma A.2 along with the fact that Prest (x) = our construction to show that the integral in the square brackets equal 1/8K2. This proves the result.
The next lemma upper bounds the KL divergence between Q(S) uy 1) and Q(S by --1 1) for each j E (1....,.f K). 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]K and that S u is drawn
from v.maj X Pr Then for any j E (l....,Ks K/2} and any E [0, 1].
(I(Q(S) 0y Q]]][((S| by =1)) Mmaj (2 7) + 1mmin
3K3
and for any j (K/2 1.....K) K}
KL(Q(S) "y = Q)) by = --)) Mmaj? + 11 (2 7)
3K3
Proof. Let us consider the case when j = The bound for all other j E (,...., K} shall follow analogously.
24

---

Under review as a conference paper at ICLR 2023
Given samples S, let S = S1) be partition where S1 are the samples that fall in the interval I1, and S the other samples. Similarly, given a vector u E {-1, 1), let v = (U1, 81), where U1 the first component and 8n denotes the other components (2...., K) of v.
First, we will show that
Q(S v1) Q(Si vi))(S)).
To see this, observe that
Q v1) = Q((S), v1) = Q(Si 01 (n)Q(Si U1, S1).
Further, if e is chosen uniformly over the hypercube {-1, 1] then
Q(31 (1.
Σ Q(S1, "1 (1.
Σ Q(3 Un 1n 61, Si) vi, S1)
81
Σ Q(S) (1)
(8
Σ Q(S1 U1, 81 Q
U1
(186)
Σ Q(3: 0. Q(())
P1
Q(S1);
where (1) follows since by Bayes' rule
Qū Uu, S1) = Q 01 (5:) v1, 01)
Q v1)
( Q({ 01)
(since o1 is independent of u1)
Q v1)
Q (1 QS{1 v1) Q(5))
(the samples in S₁ depend only on 01).
Q v1)
Inequality (ti) follows since the samples drawn independently given
(v1, 01). Finally, (fi)
follows since S (the samples that lie outside the interval 4j) only depend on ú since the marginal distribution of æ is independent of and the distribution corresponding to the interval in which x lies.
depends only the value of
Thus since, Q(S) 01) Q(S1 v1) Q(i) we have that
KL(Q(S 01 Q(S 01 -)) KL(Q(S) 0i Q)|(((S) vi = -)).
(19)
To bound this KL divergence, let us condition of the number of samples S₁ from group a, (the majority group) n1,a and the number of samples from group b (the minority group), 11,6- Now since M1,a and 11,6 are independent of i) (which only affects the labels) we have that,
Q(S1 mn)
Σ a1
Q(nia 71,6 un Q( U1, 01,a; 11,6)
Σ
((11,, Uı, (1,5)
En Q(S1
01, R1,a, m1,))
Therefore, by the joint convexity of the KL.-divergence and by Jensen's inequality we have that, KL(Q(S) 01 1)][Q((, 01 = -1))
Emiamis [KL(Q(S, 1i 1, a n Q(S( vi -11, R1))]]]
(20)
25

---

Under review as a conference paper at ICLR 2023
Now conditioned on v1, R1,a and n1,b. samples in S1 are composed of groups of samples (S1.a: S1.b). The samples in each group (S1,a S1,b) are drawn independently from the distributions Pa x E (y) x) and Pa(z x
E P,) respectively. Therefore,
( U1 1, ()()) 01 =1,,
@ 11. (LPa(( x / 1,
x) Pa x =
mn,KTL (2 PP) 1 1))
|P x TT) x))
(11a + +11bb E Unift
(L(Pe,=1(0)
x) o,, 2
(152) nı, + n1,b
UniuUi((Ts)
Σ
1 yd
(a- 1
x 2K
log
yo (xr 2k
2
+ yo (x 2R
wEf-1,11
11,a 11,bb
1
1 yo (x ZR
2
(nwUUif()))
1 yo
x
2K
log
(1 + ub (x: 2K
yE 1.11
11,a M1,6
Σ
1 yo
x
1
log
(1 + yo (1: 2K
dx
2K
2K
(1 + yo (xr 2K
WE( 1.1)
x=0
(1e)
11,a + 11,6
(21)
3K2
where in (i) we let P.,, denote the conditional distribution of y for 11 given 01, (ii) follows since both P. and P are constant in the interval, (Mii 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/3K².
Using this bound in Eq. 20 along with Eq.
19 get that
E B + 72200
( 01 = Q)( 01 = 1)) s
3K2
Now there are m'aj samples from group in and Timin samples from group b. Therefore,
E [11 Amajj Pa E 11) Mmaj (2-))
Amin?
E [[11,]] mmii Pa(a E [1)
Plugging this bound into Eq. (1) completes the proof by the first interval. An identical argument
holds for j E {,...., K/2}. For j E (K/2+ 1, 1,..,, K} the only change is that
Tmaj
E [njjall Pmaj I,)
K
7min (2 T)
[n,a]] = mmin Po E 12)
K
Next, we combine the previous two lemmas to establish our stated lower bound. We first restate it here.
Theorem 4.2. Consider the group shift setting described in Section 3.2.2 Gäven any overlap
E [0 recall that (Gs(T) is the class of distributions such that Overlap maj: Pmin) 2 The minimax excess risk in this setting is lower bounded as follows:
Minimax Excess Risk(Pos(T)) = inf A
sup
Excess Risk[A: (P majj: Pmin)]
(Pmij, PPPs)))))()
200( A1 - T) + Amaj 1)1/3 200 1/3 T + 2)1/3' (4)
where p mmajj/ Domin
26

---

Under review as a conference paper at ICLR 2023
Proof. First, by Lemma C.I we know that
Minimax Excess Risk(Pas(F)) 2
32K Σ
exp(-KK[(((5] = 1)|QQ() = =-1)).
Next, by invoking the bound on the KI. divergences in the equation above by Lemma C.2
we get that
Minimax Excess Risk(Past) (Pos(T))
Pmmaj (2 7) - 7mmin
7'min (2 - TT) + 7maj
64K
exp
3K3
exp
3K3
1
Ammn (2 - -T) + Amaaj
exp
64K
3K3
Setting K mm (2 - 7) + Amaj 1/33 and recalling that r Σ 1 we get that
Minimax Excess Risk(Pas(1
7m (2 - T) + T2maj
64 (Tiin (2 - r) + 1majj 1/33 exp
3 (1mmn (2 - T) + Rlmaj T 11/373
( exp(-
1/3) (xp()
(1 (2 T) majj Tm T)333
64
(nein (2 - T) + Rmaj T) 1//3 (Timn (2 - T) + ()majT)21
0.7 exx((11/3))
64
(Amin (2 T) + [mmjj7 11/3
200 (Amin (2 - T) + Mmmaj 12/3
where (i) follows since A'min T) + mmaj T/ (n -7) mmaj < 1, and (ii) follows
(Mmin (2- r) Ping
since S and Amin 1 and hence
[[ (2- Tmmi 13/31 2 0.7.
C.2 PROOF OF THEOREM
In this section, we derive an upper bound on the excess risk of the undersampled binning estimator Ause (Eq. (5)) Recall that given dataset S this estimator first calculates the undersampled dataset Sus. where the number of points from the minority group (1min) is equal the number of points from the majority group (Amin), and the size of the dataset is 2n Throughout this section, (P (Pmaj. P mmin) shall be an arbitrary element of PGs(1 (r) for any E [0, 1). In this section, whenever we shall often denote Excess Risk(A; (Pmaj. P min)) by simply Excess Risk(A).
Before we proceed, we introduce some additional notation. For any j {1,...,KK and I, [i=] i let
K
9/ = Ptes(y = 1
P(y 1 2 1 I2) dx,
22
uel,
f.11 : Prex = E;) Joel,
P(y=1la P E I,) dr.
22
For the undersampled binning estimator AusB (defined above in Eq. 5)) define the excess risk in an interval Iú as follows:
R2 (A(is))) : -pppy- (y=-Aff 1x min (Presty = 1 E 1;), Prest = - E 13)
- min(gi.1 3.
The proof of the upper bound shall proceed in steps. First, in Lemma C3 we will show that the excess risk is equal to sum the excess risk over the intervals up to a factor of 2/K account of the distribution being 1-Lipschitz. Next, Lemma C.4 we upper bound the risk over each interval. We put these two together and upper bound the risk.
27

---

Under review as a conference paper at ICLR 2023
Lemma C.3. The expected excess risk of undersampled binning estimator Ause can be decomposed as follows
K
2 K
Excess Risk(AUuBB) S
Σ
[Ry [Rg(Aisa)]
P (Ts) +
SruP
xP
jm0
where Prest (Iz) = JMEI, Prest())) (2)) dæ.
Proof. Recall that by definition, the expected excess risk P xP"mm [R(AA Ptest) - R(S"; Prest)
Let us first decompose the Bayes risk R(f*),
R(f*) = inf P) Pess [1(((z) b)]
inf Σ ((((x) # y) (ys Prest (2) dx
vE(-1,1)
inf == (())(-1111)
Σ 1(f(x) + Pres x: Ptest(() da yE(-1.1)
inf == (1)){-1111)
P Prest (y -f(()) 1x)) (tes(())())) dx
min = x)) Prest = =-1 x)} Prest(r) dæ.
(23)
==
The risk of the undersampled binning algorithm Ause is given by
[
R(AÚsE)
Σ
I(AūsB()) (x) # v) Pestt (y ly x:) Ptese))( dr
0E(-1,1)
f Prestly -ASs x)) Pres((r) dr.
Next, recall that the undersampled binning estimator is constant over the intervals IG for (1...., K} where it takes the value Aς (to ease notation let simply denote it by Ag below), and therefore
f
R(A(ss))
Σ
Prest -Aglx) test (I) da.
j=0 xEE
This combined with Eq. (23) tells us that
R(AūsB)
R((*)
K-1
Σ
- min (Prest = ()), Prest = x}) (((r))))Peee Prest(x) dr. (24)
j=0
ZEI;
Recall the definition of qja1 and 45 from Eqs. 22
2 b2p) above. For any x E I, = }
(yest(y x) Vivl I 1/K, since the distribution Prest y x is 1-L-pschitz, and Zi.y is its conditional mean. Therefore,
R(AAsee) R(
K
K K-1
(9i-A, - min (6.1, Cj. (;.1)) ) Prest (x) dx +
Σ
Peest (x) da
0= wel,
K
j=0
K-1
Σ
/ R2 (A rest (x) dr +
2 K
xEL,
Taking expectation over the training samples S (where nmin samples are drawn independently from P min and Mmaa samples are drawn independently from Pmaj) concludes the proof.
28

---

Under review as a conference paper at ICLR 2023
Next provide upper bound on the expected excess risk is interval Ry (A(ss) Lemma C.4. For any j E (I,..., K} with 1, = 1' kl.
E Sw x priin [R -
+ c
v Mmin Pessn Pestt(])
K
where c is an absolute constant, and Prest(I)) == -JEE,, Prest(x) dæ.
Proof. Consider an arbitrary bucket j E {I,...,K} K}.
Let us introduce some notation that shall be useful in the remainder of the proof. Analogous to 6.11
and 95.-1 defined above (see Eqs. 22 )2 define zf, and g², follows:
G
P(v - 1 Pa x I5) dx,
25
DEl,
L1 Po = Juel;
P(y æ Po x 15) dx,
25
Essentially, 9f is the probability that a sample is from group and has label 1, conditioned on the event that the sample falls in the interval 1y. Since
Ptest x E 12)
Pa x EE) Po(e E 1,)),
therefore
P(g = (/g=1|2)Ptestl IE 1,) dr / IEI,
|4,1 - 93.1
JKEI, P(y 2)Pa(x x E 1,) dr
< K
(26)
This follows since P(y) I) is 1-Lipschitz and therefore fluctuate by most 1/K in the interval I5. Of course the same bound also holds for 19,1 g/11-
With this notation in place let present bound on the expected value of (y( By definition
Ry(A -9,--5 min (gi,1. min(gj,1 (j.-13-
First, note that Qj.1 Pter(y = 1 E I2) -j.-1- Suppose that 9j,1 1/2 and therefore Φ.-1 > 1/2 (the same bound shall hold in the other case). In this case, risk is incurred only when
A = 1. That is,
Ss Pmaj XP mij
(AUSE)
14j,-11 - 1 - 1]
min
= = =1 Ps--2g.il's(A4 =1].
(27)
Now by the definition the undersampled binning estimator (see Eq. (5) A only when there are more samples in the interval I, with label than -. However, we can bound the probability of this happening since Qj.1 is smaller than Jj,-1-
Let ny be the number of samples in the undersampled sample set Sus in the interval 1y. Let M1.j be the number of these samples with label 1, and n- = ny Mi. be the number of samples with label 11. Further, let Na.j be the number of samples in from group such that they fall in the interval I,. and define ma. analogously.
The probability of incurring risk is given by
2n
1
PIA, = sPIn, s),
(28)
where the sum is up 27 since the size of the undersample dataset |Sus is equal 2n
29

---

Under review as a conference paper at ICLR 2023
Conditioned on the event that n the probability of incurring risk is
PIA, = 1 nj = s] = [m. > n- ni = 8] = [n > n2 n2 nj = 8]
TP [m1.j > 8/2 my s).
(29)
Now, note that nz Ru., + nb.jj. Thus continuing, we have that
P(n1. > 8/2 n = s) =
Σ P [m1.5 > 8/2 1/21n = s, nb.j = s0 s'|P(no,j = ss
Σ
IP [11.
> 8/2 | na. = - ss nb. 5i) s']iPrmo.s = s').
In light of this previous equation, want to control the probability that the number of samples with label in the interval 1y conditioned on the event that the number of samples from group a in this interval is s s' and the number of samples from group b in this interval is s'. Recall that 98, and Lh, the probabilities of the label of the sample being conditioned the event that sample is in the interval I5 when it is group a and b respectively. So we define the random variables:
Bin(s - s', (,,): =0|61 Bin(s', og..), =als - 51
=[s] ~ Bin(s, max 1 })
Then.
P [mis > 8/2 ny =]
Σ P P[11. > s/2 Rjaa = 5 - nz,b6 -,,,,, = s/]P[1 = s']
P P|za[s 8 81 + mn(l) > 8/2 Na.j = 8 - ss,, n', = 5S) s/]p(mn.. = 8']
P[ > 8/2 nas =5- s', s's = s/|plmbis =s'
nos
8'S
Σ P(#[s) > s/2] =8]
S'Sa
= P [2[s] > 8/21
(-a 2 max (L. of )P).
2 exp
(30)
where (i) follows by invoking Hoeffding's 's inequality Wainwright 2019 Proposition 2.5). Combining
this with Eqs. 28) and
29 we get that
2nmis
PLA, = 1] <
exp
- 2 max (1-
(f P(n, = s].
Now nj, which is the number of samples that lands in the interval I, is equal to Na.i + na.j. Now each of Rayj and no.j (the number of samples in this interval from each of the groups) are random variables with distributions (in(m Pa(I,)) and (in Po(T))) where Pa(4,) = Seer, Pa(x) dx and Pb(4)) Jret, (a(x) dr. Therefore, ny is distributed as sum of two binomial distribution and is therefore Poisson binomially distributed (Wikipedia contributors 2022). Using the formula for the moment generating function (MGF) of a Poisson binomially distributed random variable we infer that,
(1 - 2 max {9f.1 of
Panis
PlA,- = 1/3 S
1- PPPa(() Pa())) exp
(1 - 2 max f0E11 2311))²) )) Vini
1 - (I[I,)+PPC exp
2
30

---

Under review as a conference paper at ICLR 2023
Plugging this into Eq. (28) get that,
E SruP "maj xPinn mai
RR AUBB)
(1 2 max
{15.1 0311))²
Timi
$ 11 2q
1 - Pc((4))+ exp
2
(1 2 max
{qh Tr,1 1).
Alin
1 Pb(I)) + Pb( exp
(1 max {1h 13.13)
Tlmin
[1 2
exp
(1 2 max
{99 g..1 })²
1min
1 Pb(1,)
1- exp
2
Since |1 - max { 13.1 1 11 1.
( (1- - 2 max (0,1119111 0311)²²
(1 max {95.1 gf,1))²
1 exp
2
2
4
and therefore
(1- max (05.1 o2,n)))
Mini
E "mai xmin [R [RsBA S -2
1 1 PaPa()))
ShPP ma)
- Pb(Tg) (1 (1-2 max {g),1 1)2 Timis
2
(
(1 11-29;,1 22)) 2 Pmnn
[1 24
Pa(I,)
x
2
1 (1 - 29,,1 - 27))
2
(58)
(1 29j.1
1 -2y))
11 29 exp
-Remin (Pa(I)) + Pb(,))
2
where (i) follows since max o8 -,,, < 1/K by Eq. (26) and is such that |1| S 1/K, and
(it) follows since (1 2)xh < cxp(bz). Now the RHS above is maximized when (1 - 2q,, - 2y)
(P.(P.(1)) (L,)+ for some constant c. Plugging this into the equation above we get that
d
E S. Fmal Pmin [RA < mij
+dbl
mmin (a (Pa(1)) Po(I,)
d
v Amin (T) ( Pb(T,)
K
Finally, noting that Prea((1)) = (Pa(T)) P2(T,))/2 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 in Section 3.2.2 For any overlap 7 E (0, 1] for any (P (Pmaj Pmin) ) PGs(T) the expected excess risk of the Undersampling Binning Estimator (Eg. with number of bins with K = [mmin 1/37 is
Excess Risk[AusB; (Pmaj Pmin)] = E "mai x Pein [R(ASS Prest)) - ;R(f;; Ptest)
Ammin 1/3
31

---

Under review as a conference paper at ICLR 2023
Proof. First by Lemma C.3
know that
Excess Risk[AAsB
S
"m ma
x
[AA(B))) Prest (1₁)
==0
Next by using the bound on S-
Rmaj
x "iin
(AAse)) established in Lemma C.4
we get that,
mai
Excess Risk (iuk( S
P rest (Tz)
Amin Prest (1z)
K
j=0
K-1
Prest (Lj) +
mmnn
K
j=0
K
VK
Prest Pest(1y)) + e
V Amin
K
j=0
K
c
+
1lmin
K
where (i) follows since for any vector E K
|=||1 S VK||=112 Maximizing over K yields the
choice K [mmin 1/37, completing the proof.
D ADDITIONAL SIMULATIONS
Tilted Loss Classifiers
68
68
Only Majority
Proportional Increase
66
66
Test Accuracy
62
62
Only Minority
60
Proportional Increase
60
500
1000
1500
500
1000
1500
2000
Extra Minority Samples Added
Extra Majority Samples Added
Group DRO Classifiers
68
68
Only Majority
Test Accuracy (%)
Proportional Increuse
64-
64
62-
62
Only Minority
60
Proportional Increase
1000
1500
500
1000
1500
2000
Extra Minority Samples Added
Extra Majority Samples Added
Figure Convolutional neural network classifiers trained on Imbalanced Binary CIFARIO 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 al. (0200) 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 dataset. We find similar trends to those obtained in Figure even with these losses that are designed to optimize for the worst group accuracy.
32

---

Under review as a conference paper at ICLR 2023
E EXPERIMENTAL DETAILS FOR FIGURES 2 AND 4
We construct our label shift dataset from the original CIFARIO dataset. We create a binary classi- fication task using the "cat" and "dog" classes. We use the official test examples 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 use 80% of those examples for training and the rest for validation. We are left with 2500 additional cat examples and 4500 dog examples from the original train set which we add into our training set to generate Figure 2
5:1 label imbalance. We
We use the same convolutional neural network architecture as (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 momentumn 0.9. The importance weights used upweight the minority class samples in the training loss and validation loss is calculated to be internal cluster on
#CCat Train Examples
We note that all of the experiments were performed
#Dog Train Examples
GPUs.
VS Loss:
Given a dataset {Ii, Mi Jim1 the VS loss (Kini et al. 2021 is defined as follows
(-(
y;f(2;) - Tug:
Cvs(f) = log
exp exp
1maxx
where Ii denotes the group label, Rg: corresponds to the number of samples from the group, mmax is the number of samples in the largest group and is the total number of samples. We set T = and y = 0.3, the best hyperparameters identified by Wang et al. (0022) on this dataset for this neural network architecture.
Tilted Loss:
The tilted loss (Li et al. 2020) is defined as
1 7. log Σ exp (Il(y)((x))))
Liiteed (f) =
where we take to be the logistic loss. In our experiments we set
Group-DRO: We run group-DRR DRO (Sagawa et al. 2020, Algorithm 1) with the logistic loss. We set
adversarial step-size 7, = 0.05 which was the best hyperparameter identified by Wang et al. (2022).
33


Reviews:
[{"review_id": "xh0Y4zw7p2", "reviewer": "Reviewer_dgxz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors investigate the minimax optimality of classification problems under label and covariance shift on groups. They show that the minimax classification error is characterized by the sample size for the minor group essentially, indicating that increasing the major group's sample size does not affect the classification accuracy. They also demonstrate that the undersampling-based estimator achieves the optimal minimax.", "summary_of_the_review": "This paper is well-written and technically sound. However, the significance of the technical contribution is unclear. I thus recommend rejection at this time. It is welcome to clarify the significance during the rebuttal. ", "strength_and_weaknesses": "Strength:\n- Well-written with a clear claim\n- Technically sound\n- The claim of characterization with a minor group's sample size is interesting\n\nWeakness:\n- Lack of significance of techniques.\n- The results are limited to too simple cases. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "ierei_RQYF", "reviewer": "Reviewer_9dze", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proves that the min-max excess risk of nonparametric classification algorithms is bounded by the number of minority samples when there is a distributional shift between train and test, and therefore concludes that in the worst case, undersampling is optimal unless there is a high degree of overlap between the train and test distributions, or if the algorithm leverages additional structure about the distribution shift. They conducted an experimental case study on a label shift dataset and showed that the test accuracy of robust neural network is constrained by the number of minority samples.", "summary_of_the_review": "Overall I am satisfied with the quality of the paper. I think it has a fairly important contribution to guide the research direction in robust algorithms dealing with distributional shift. The theoretical results also nicely supporting their conclusions. The experimental section can potentially be improved, by incorporating a comparison between undersampling and other robust algorithms, and may also be extended to other datasets, classification algorithms such as Random Forest. ", "strength_and_weaknesses": "Strength:\n1. The conclusion of the paper is very interesting in that it shows the optimality of a simple undersampling scheme, and dictates the need to design tailored algorithms that exploit the structure of distributional shift between train and test, instead of aiming to design a universal robust algorithm that is agnostic to the type of distributional shift. This is fairly important to lead to a directional change in designing robust algorithms to deal with distributional shift. \n\n2. The idea is explained very well, using succinct language to explain complicated mathematical theorems so that it is easy to understand. The theoretical results are also justified well by the experimental studies.  \n\nWeakness:\n1. The paper makes the assumption that the test set is balanced. I am curious about whether these results still hold when the test set is somehow also unbalanced, but there still exists some distributional shift between the train and test. When the positive - negative ratio is unknown in the test set, how should undersampling be implemented? In this case, do we prefer other state-of-the-art robust algorithms to undersampling, since the test distribution is unknown?\n\n2. The experiments add evidence in supporting the theoretical results. In Fig. 2, the left pane, why the green curve is only up to 500 samples? Can we add the other half of the green curve? Also, if the green and red curves add the same number of minority samples, we expect their performance to be quite close, based on the theoretical results, right? But why do we still see a performance gap in those plots?\n\n3. The experiments used importance weighted classifiers to demonstrate the importance of minority samples. Personally I am also interested in seeing the comparison of undersampling with other robust algorithms, and to understand whether it is true that simple undersampling (without any importance weighting) performs as good as state-of-the-art. In Section 2, the 2nd paragraph, the authors also mentioned that importance weighting is ineffective when it comes to over-parameterized neural networks. If that's the case, I expect undersampling to outperform importance weighted classifiers.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "-noa7z3lxlR", "reviewer": "Reviewer_yVEH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This draft studies the problem of learning with a distribution shift. The authors show that in the worst case of label shift or group-covariate shift, with the measure of minimax excess risk, no other algorithm can provably outperform the undersampling algorithm without further investigating the structure of distribution shift. The results are also consistent with previous empirical studies.", "summary_of_the_review": "This paper provides a theoretical analysis for the problem of worst-case label shift and group-covariate shift. They prove that in the worst case of label shift and group-covariate shift problem, with the measure of minimax excess risk, a simple undersampling algorithm has obtained the minimax optimal result. This result is intuitively obvious, but there is no theoretical proof for it in the literature. The proposed analysis is sound and the empirical studies verify their proposal.", "strength_and_weaknesses": "Strength:\n+ This work theoretically shows that in the worst case of label shift and group-covariate shift problem, with the measure of minimax excess risk, a simple undersampling algorithm has obtained the minimax optimal result. This result is intuitively obvious, but there is no theoretical proof for it. This work provides a formal formulation and proves this intuitive result. In these two cases, the lower bound of undersampling matches its upper bound. This result also matches the empirical results proposed by other researchers.\n+ Overall, the draft is well organized, and its theoretical results are clear.\n \n\nWeaknesses:\n- This work analyzes the worst-case scenario for label shift or group-covariate shift. Without any test (labeled) data or knowing the structure of distribution shift, it is easy to see that no other method could provably outperform the undersampling method. This result does not help in the design of a practical algorithm to handle the problem. For example, how to decide whether to use undersampling or other approaches to handling the label shift and group-covariate shift?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-gbPDIMMHHS", "reviewer": "Reviewer_1VuN", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper explores the minimax optimality of undersampling. Specifically, for balanced test sets assuming Lipschitz label shift or group covariate shift, the lower bound on the minimax excess risk depends on the number of samples in the minority class at the rate n_{\\min}^{-1/3}, in the univariate case. Undersampling with a binning estimator has the same rate, and so undersampling is minimax optimal.\n", "summary_of_the_review": "* This is a clear, well-typeset paper. The theoretical arguments are nice and should be published, but whether they answer the real questions around undersampling is debatable.\n", "strength_and_weaknesses": "Strengths\n\n* Clear paper.\n* Reasonable theory result.\n\nWeaknesses\n\n* Restricting to the univariate covariate case is lazy, or, if the group covariate shift upper bound Theorem 5.2 cannot be generalized to higher dimensions at the same -1/3d rate, deceitful.\n* My understanding of the subsampling phenomenon is that we are interested in why subsampling seems to work when the test distributions are not balanced, as they are artificially in this case. My intuition for that phenomenon is just artifacts of SGD training for neural networks. That subsampling is optimal in this case just follows from the fact that the uncertainty of the minority class is still dominant, and this manifests in these lower bounds. So this answers an undersampling problem, but not the undersampling problem.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject