Undersampling is a Minimax Optimal Robustness Intervention in Nonparametric Classification
Authors: Niladri Shekhar Chatterji
Saminul Haque
Tatsunori Hashimoto
Venue: NeurIPS 2022 Submitted (2022)
Keywords: theory of distribution shift
nonparametric classification
undersampling

Abstract: While a broad range of techniques have been proposed to tackle distribution shift, the simple baseline of training on an \emph{undersampled} 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. While 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.

Undersampling is a Minimax Optimal Robustness Intervention in Nonparametric Classification
Anonymous Author(s)
Affiliation
Address
email
Abstract
While broad range of techniques have been proposed to tackle distribution shift, the simple baseline of training 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 indeed the case 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 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. While in the case of group-covariate shift show that there is an undersampling algorithm that is minimax optimal when the overlap between the group distributions 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.
undersampled dataset often achieves close
10
12
14
16
Introduction
18
19 key challenge facing the machine learning community is to design models that are robust to distribution shift. When there is mismatch between the train and test distributions, current models this paper, our focus is on group-structured distribution shifts. In the training set, have many samples from majority group 23 and relatively few samples from the minority group, while during test time we are equally likely to
21 are often brittle and perform poorly on rare examples [11 2 20 I0
24
get a sample from either group.
25 To tackle such distribution shifts, a naïve algorithm is one that first undersamples the training data by discarding excess majority group samples [14 and then trains model on this resulting dataset (see Figure for an illustration this algorithm). The samples that remain in this undersampled dataset constitute i.i.d. draws from the test distribution. Therefore, while classifier trained this pruned 29 dataset cannot suffer biases due to distribution shift, this algorithm is clearly wasteful, as it discards training samples.
27
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

No Undersampling
Undersampling
Learned Boundary
Predicted Minority
Minority 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, while on the right we have the maximum margin classifier over the undersampled dataset. The undersampled classifier less biased and aligns more closely with the true boundary.
31 This perceived inefficiency of undersampling has led to the design of several algorithms to combat
32 such distribution shift 6 18
5
17 (29 13 [24]. spite of this algorithmic progress, the simple undersampled dataset remains competitive. In the case of label
baseline of training models shift, where one class label overrepresented in the training data, this has been observed by Cui et al.
34
77, Cao et al. [5] and Yang and Xu [28]. While in the case of group- covariate shift, study by Idrissi al. showed that the empirical effectiveness these more complicated algorithms limited.
36
37 For example, Idrissi et al. 12] showed that on the group-covariate shift CelebA dataset the worst-
38 group accuracy of ResNet-50 model on the undersampled CclebA dataset which discards 97% of the
39 available training data is as good as methods that use all of available data such importance weighted [16. In Table [ we report the performance of ERM 19. Group-DRO 18 and Tei-Traii--Twee
40
41 the undersampled classifier compared to the state-of- oifte-ofthh-anee thh-aart-mthhoe in the literature across several
42 label shift and group-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.
44
Table 1: Performance of undersampled classifier compared to the best classifier across several popular
label shift and 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 on the MultiNLI dataset.
shift datasets. When reporting worst-group accuracy we denote by
Test Accuracy/Worst-Grovne Accuracy"
Shift Type
Dataset/Paper
Best
Undersampled
Imb. CIFARIO (step 10) 5
87.81
84.59
Label
Imb. CIFARI00 (step 10)
58.71
55.06
CclebA 12
86.9 + 1.1*
85.6 + 2.3*
Waterbirds [12
87.6 + 1.6*
89.1 + 1.1*
Group-Covariate
MultiNI. 12
78.0 + 0.7*
68.9 + 0.8*
CivilComments 12
72.0 + 1.9*
71.8 + 1.4*
Inspired by the strong performance of undersampling in these experiments, ask:
46
the performance of model under distribution shift fundamentally constrained by the lack of minority group samples?
48 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

---

50
samples (Amin). 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 Amin-
51
For our study, consider the well-studied setting of nonparametric binary classification 21 By operating in this nonparametric regime we are able to study the properties of undersampling in rich data distributions, but are able circumvent the complications that arise due the optimization and implicit bias of parametric models. We explore two distribution shift scenarios: label shift and group-covariate shift. Under label shift, one of the labels is overrepresented in the training data, P (y 1) 2 Pirain = -1 1), whereas the test samples are equally likely to come from either shift, 59 class. Here the cladscconi distribution (( y) is Lipschitz in z. Under group-covarine
54
55
56
57
58
60
we have two groups {a, b} and in the training data we have more samples from the distribution P. (a(z) than from (a())). Whereas during test time, is equiprobable to receive samples from either group. In this case, the distribution P(y) æ) is Lipschitz in x.
61
62
63
Our Contributions. We show that in the label shift setting there is fundamental constraint, and that the minimax excess risk of any robust learning method is lower bounded by 1/ 1/mmin 1/3, That is, minority group samples fundamentally constrain performance under distribution shift. Furthermore, by leveraging previous results about nonparametric density estimation [9] we show a matching upper bound on the excess risk of a standard binning estimator trained on an undersampled dataset to demonstrate that undersampling is optimal.
64
65
66
67
68
69 In the case of group-covariate shift, we show that when the overlap (defined in terms of total variation distance) between the group distribution P. and Po is small, similar result holds and the minimax excess risk of any robust learning algorithm is lower bounded by 1/mmin 1/3 We show that this lower bound is tight, by proving upper bound the excess risk of the binning estimator acting on the undersampled dataset.
70
71
73
Finally, 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.
75
78
77
78
Taken together, our results underline the need to move beyond designing "general- purpose" robustness algorithms (like importance weighhing 55
79
17 13 24 g- g-DRO [8], JTT [16]. SMOTE ( etc.) that are agnostic to the structure in the distribution shift. Our worst case analysis highlights that to successfully beat undersampling, an algorithm must leverage additional structure in the distribution shift.
80
81
2 Related Work
83
84
On several group-covariate shift benchmarks (CelebA, CivilComments, Waterbirds), Idrissi et al. [2] showed that training ResNet classifiers on an undersampled dataset either outperforms performs 96 as well as other popular reweighting methods like Group-DRe DRO (18), reweighted ERM, and Just- Train-Twich [6]. They find Group-DRO performs comparably to undersampling, while both tend to outperform methods that don't 't utilize group information.
88
One classic method to tackle distribution shift is importance weighting [19]. which reweights the loss of the minority group samples to yield an unbiased estimate of the loss. However, recent work 3 27 has demonstrated the ineffectiveness of such methods when applied to overparameterized neural networks. Many followup papers (5] 29 17 13 24 have introduced methods that modify the loss function in various ways to address this. However, despite this progress undersampling remains competitive alternative to these importance weighted classifiers.
90
91
92
94
95
Apart from borrowing Our theory draws from the rich literature on non-par-en parametric classification 21
96
this setting of nonparametric classification, we also utilize upper bounds on the estimation error of the simple histogram estimator [9] 8 to prove our upper bounds in the label shift case. Finally, we note that to prove our minimax lower bounds we proceed by using the general recipe of reducing from estimation to testing 22 Chapter 15J. One difference from this standard framework is that our
97
96
100
training samples shall be drawn from different distribution than the test samples used to define the
risk.
3

---

102
3
Setting
103
In this section, we shall introduce our problem setup and define the types of distribution shift that we consider.
104
105
3.1
Problem Setup
The setting for our study is nonparametric binary classification with Lipschitz data distributions. We are given n training datapoints S := {(x1 ((11,))..... 31)...., (Ias yn)} ]n]]e E ([0, 1] (-1,1})* that are all drawn from train distribution P Ptriin- During test time, the data shall be drawn from different distribution Prest To present a clean analysis, we study the case where the features x are bounded scalars, however, it is easy extend our results the high-dimensional setting.
107
109
111 Given a classifier f: R + (-1, 1l, we shall be interested the test error (risk) of this classifier under the test distribution Ptest:
R(;PPtst = (a (1[(1) fy)]
113
3.2 Types of Distribution Shift
114
We assume that Ptrain consists of mixture of two groups of unequal size, and Prest contains equal numbers samples from both groups. Given a majority group distribution Pmaj and a minority group
115
116
distribution P min. the learner has access to Amaj majority group samples and Amin minority group
117
samples:
Smaj ~ Pi and Smin
P Puiin
The full training dataset is S Smaj U Umin = ((111,)) ,,),,..,. (Xi, }a))- We assume that the learner has access to the knowledge whether particular sample (27, ye) comes from the majority or minority group.
Here Romaj > n2/2 and 1lmin < n/2 with m'maj 71min
119
The test samples will be drawn from Prsst = P + P uniform mixture over Pmaj and min- Thus, the training dataset is an imbalanced draw from the distributions P Pmaj and P Pmin. whereas the test samples are balanced draws. We let p == Pimaj/mmin > denote the imbalance ratio in the training data.
121
122
123
124
We focus on two-types of distribution shifts: label shift and group-covariate shift that describe below
126
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 = is the majority class. Then, we define the majority and the minority class distributions
P mmj (z. y) = (z)
and Pmin = P- -1)
where P1, P-1 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),
129
(z (x S |x z'I.
130
We denote the class of pairs of distributions majj P mmin) that satisfy these conditions by PLs.
3.2.2
Group-Covariate Shift
In this setting, we have two groups {a, 6}, and corresponding to each of these groups is distribution (with densities) over the features (z) and Pa(r). We let a correspond to the majority group and correspond to the minority group. Then, we define
P Pmaj( (x., y) = (z)) x)) and (m, y) = Po(x) 1x).
We assume that for y 1), for all x, E 1]:
PP x) P(u 2')l < |x =21,

---

133
that is, the distribution of the label given the feature is 1-Lipschitz, and it varies slowly over the domain.
134
135
To quantify the shift between the train and test distribution, we define notion of overlap between the group distributions Pa and Pa as follows:
136
Overlap(P o1 Pb) =- 1 TV(P., Ps).
137
Notice that when P. and Ps, have disjoint supports, TV(Pa., Ps) = 1 and therefore Overlap(Pa: Pb) and Overlap(Pa: Ps) = 1. When the overlap is 1. the majority and minority distributions are identical and hence we have no shift between train
138
On the other hand when P. Pb. TV Pt)
139
140
and test. Observe that Overlap(P... Pb) Overlap(P maj. Pmin) since P x) is shared across mai
and min-
Given a level of overlap [0, 1] we denote the class of pairs of distributions (Pmaj. minn) with overlap at least r by Pas (T). is easy to check that, (TS(T) S Pas (0) at any overlap level T E [o, 1].
143
Lower Bounds on the Minimax Excess Risk
144
145
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 minn Before we state our lower bounds, we need to introduce the notion of excess risk and minimax excess risk.
148
147
148
Risk and Minimax Excess Risk. We measure the performance of an algorithm A through its excess risk defined in the following way. Given an algorithm A that takes as input dataset S and returns classifier A and pair of distributions (P (Pmaj. Pmin) with Ptest = Pmaj + P Pinn the expected excess risk is given by
Excess
149
150
151
Excess Risk[A; (Pmaj Pmin)] == S. xP Pnin ;R(AA;Ptest) - (Ptest)::): Prest)]
(I)
152
where ("((tett) is the Bayes classifier that minimizes the risk R((; Prest). The first term corresponds
153
to the expected risk for the algorithm when given majj samples from maj and remin samples from
154 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 problem, since for any particular
156
data distribution (Pmaj P min) the best possible algorithm A to minimize the excess risk would be the trivial mapping A = (Ptest). Therefore, to prove meaningful lower bounds on the performance of algorithms we need define the notion of minimax excess risk [see 22 Chapter 15]. Given class of pairs of distributions define
157
159
Minimax Excess Risk(P) = inf sup A (Pimj:Pamnn) Pain )
Excess [isk[A; (Pmaj. Pmii)]s
(2)
160
where the infimum is over all measurable estimators A. The minimax excess risk is the excess risk of the "best" algorithm the worst case over the class of problems defined by P.
161
162
4.1
Label Shift Lower Bounds
183
We demonstrate the hardness of the label shift problem in general by establishing a lower bound on the minimax excess risk. Below we let be an absolute constant independent of problem parameters like maj and m-min-
184
185
186
Recall that PLs is the class of pairs of distributions (P majy Pmin) that satisfy the assumptions in that section. The minimax excess risk over this class is lower bounded as follows:
Theorem 4.1. Consider the label shift setting described in Section 3.2.1
188
Minimax Excess Risk(Pts) = inf sup A (Pmaj P
Excess Risk[Ar (Pmajy Pmin)]
(3)
T'min 1/3
189 We establish this result in Appendix
B
We show that rather surprisingly, the lower bound on the minimax excess risk scales only with the number of minority class samples Rmin 1/3 and does not depend on 7'aj. Intuitively, this is because
5

---

172 any learner must predict which class conditionl distribution (P(z: 1) or P(æ -1) assigns higher likelihood at that z. To interpret this result, consider the extreme scenario where Maa -> 0o but m'min 174 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 æ. This uncertainty underlies the reason why the minimax rate of classification is constrained by the number of minority samples mmin
173
175
176
177
179
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 as is to be expected in nonparametric classification.
180
181
4.2
Group-Covariate Shift Lower Bounds
182
Next, we shall state our lower bound on the minimax excess risk that demonstrates the hardness of the croup-covariate shift problem. In the theorem below > O shall be an absolute constant independent
183
184
of majj. Temin and т.
185
Theorem 4.2. Consider the group shift setting described in Section 3.2.2
Given any overlap
186
T E [0. 1] recall that (T) is the class of distributions such that Overlap( maj: Pmin) 2 T. The
187
minimax excess risk in this setting is lower bounded as follows:
Minimax Excess Risk(Pos(1))
inf sup A (Pmyj. EPo((()
Excess Risk[A: (P (Pmaj. P Pmin)]
C
c
(4)
[mmin (2 - 7) + Mmaj 1/3
11min 1/3 r + 22)1/33"
188
where p /lmaj/ Amin
189 We prove this theorem in Appendix C
We see that in the low overlap setting (r < 1/p), the minimax excess risk is lower bounded by 1 min 1/3 and are fundamentally constrained by the number of samples in minority group. To see why this is the case, consider the extreme example with r = O where Pa has support [o. 0.5) and Pg has support [0.5, 1]. The maaj majority group samples from P. provide information about the correct label predict in the interval [0,0.5) (the support of P.). However, since the distribution Pl 2) 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 on the support of Pú requires samples from the minority group and this results in the Amin dependent rate. In fact, in this extreme case (T 0) even if Amaj + 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
192
198
194
195
196
197
198
199
200
shows that minority samples are much more valuable than majority samples at reducing the risk.
On the other hand, when the overlap is high (r > 1/p) the minimax excess risk is lower bounded by (1(mmin (2- 7) ? 1/3 and the extra majority samples quite beneficial. This is roughly because the supports of P. and Ps have large overlap and hence samples from the majority group useful in helping make predictions even in regions where P, is large. In the extreme case when 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/33/3, as one might expect.
202
203
204
205
206
207
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.
208
Upper Bounds on the Excess Risk for the Undersampled Binning Estimator
209
210
211
We will show that an undersampled estimator matches the rates in the previous section showing that undersampling an optimal robustness intervention. We start by defining the undersampling procedure and the undersampling binning estimator.
212
213
214
Undersampling Procedure. Given training data = ((11,31),-.. (Kn, Ww)). generate new undersampled dataset Sus by

---

218
including all min samples from Smin and,
217
including min 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/0mnn
219
The undersampling binning estimator defined next will first run this undersampling procedure to obtain Sus and just uses these samples to output a classifier.
221
222
Undersampled Binning Estimator The undersampled binning estimator Ause takes as input dataset S and a positive integer K corresponding to the number bins, and returns a classifier ASe [0, 1] + {-1,1}. This estimator is defined as follows:
223
224
1. First, compute the undersampled dataset Sus-
228
2. Given this dataset Sus. let n1, be the number of points with label +1 that lie in the interval
13 12-1 k. Also, define n-1,j analogously. Then set
A₁ = {
if mi > n-11j: otherwise.
3. Define the classifier AusB such that if I then
S.S (z) Ay.
(5)
Essentially in each bin I,. we set the prediction be the majority label among the samples that fall in this bin.
230
Whenever the number bins K is clear from the context we shall denote Aush by A Below establish upper bounds on the excess risk of this simple estimator.
232
233
5.1
Label Shift Upper Bounds
We establish upper bound the excess risk of Ause in the label shift setting (see Sec- tion 3. Below we let C > O be absolute constants independent of problem parameters like maj and 7mmin-
235
Theorem 5.1. Consider the label shift setting described in Section
3.2.1 For any (Pmaj. P Pmin) PLs the expected excess risk of the Undersampling Binning Estimator (Eq.
238
5) with number of bins with
K mmi 1/31 is upper bounded by
Excess Risk[AusB: (amajs Pmin)] SrPP "nojj
[R(AUsB: Prest) :R(f"; S
Tomin 1/3
240
We prove this result in Appendix 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.
242
We note that our analysis leaves open the possibility of better algorithms when the learner has additional information about the structure of label shift beyond Lipschitz continuity.
244
245
5.2
Group-Covariate Shift Upper Bounds
248
Next, we present our upper bounds on the excess risk of the undersampled binning estimator in the group-covariate shift setting (see Section [.2.2p. the theorem below, C. > is an absolute constant independent of the problem parameters Maaj. R-min and т.
247
Theorem 5.2. Consider the group shift setting described in Section 3.2.2 For any overlap 7 E [o. 249
and for any (Pmaj Pmnn) (Ps(T)) the expected excess risk of the Undersampling Binning Estimator (Eq. with number bins with K [in 1/37 is
Excess Risk (P maj: Pmin)] = E
S Pmii Phimin
R(AS Ptex)) - R(f"; ;Pest))
Am 1/3
7

---

252
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 mmnn + ?maj?) 1/3 the upper bound for the undersampled binning estimator always scales with 1/12min 1/3 since operates on the undersampled dataset (Sus).
254
255
Thus, we have shown that in the absence of overlap (T < 1/p = mimin/ /maj) there is an under- sampling algorithm that is minimax optimal up constants. However when there is high overlap
257
TT
1/p) there is a non-trivial gap between the upper and lower bounds:
Upper Bound
c(p + 22)/33
Lower Bound
258
6
Minority Sample Dependence in Practice
Cross Entropy Loss Importance Weighted Classifiers
68
Only Majority
Test Accuracy (%)
Propottional 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 Proportional Increuse
Test Accuracy
66
66
64
64
62
Only Minority
62
Proportional Increase
60
60
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 CIFARIO 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 [33] with early stopping. We report the average test accuracy calculated on balanced test set over 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 we add majority and minority samples in 5:1 ratio (green), the gain is largely due to the addition of minority samples and is only marginally higher (< 2%) than adding only minority samples. The green curves correspond to the same classifiers in both the left and right panels.
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?
260
262
To explore this question, we conduct a small case study using the imbalanced binary CIFARI0 dataset 3 24 that is constructed using the "cat" and "dog" classes. The test set consists of all
284
of the 1000 cat and 1000 dog test examples. 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
8

---

286
label imbalance. We then use 80% of those examples for training and the rest for validation. In our experiment, we either (a) add only minority samples; (b) add only majority samples: (c) add both majority and minority samples in a 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 [13]. We early stop using the importance weighted validation loss in both cases. The additional experimental details are presented
267
269
270
271
in Appendix D
273
Our results in Figure 2 are generally consistent with our theoretical predictions. By adding only minority class samples the test accuracy of both classifiers increases by great extent (6%), while by adding only majority class samples the test accuracy remains constant or in some cases even decreases owing to the added bias of the classifiers. When we add samples to both groups proportionately. the
274
275
278
277
increase in the test accuracy appears to largely to be due to the increase in the number of minority
278
class samples and on the left panels, we see that the difference between adding only extra minority
279
group samples (red) and both minority and majority group samples (green) is small. Thus, we find
that the accuracy for these neural network classifiers is also constrained by the number of minority
281
class samples.
Discussion
282
283
We showed that undersampling is an optimal robustness intervention in nonparametric classification in the absence of significant overlap between group distributions or without additional structure beyond Lipschitz continuity.
284
285
286
At a high level our results highlight the need to reason about the specific structure in the distribution shift and design algorithms that tailored to take advantage of this structure. This would require
287
288
us to step away from the common practice in robust machine learning where the focus is to design "nniversal" robustness interventions that agnostic the structure in the shift. Alongside this,
289
290
our results also dictate the need for datasets and benchmarks with the propensity for transfer from training time to test time.
291
References
292
293
[1] M. A. Alcorn, Q. Li, Z. Gong, C. Wang, L. Mai, W.-S. Ku, and A. Nguyen. Strike (with) a pose: Neural networks are easily fooled by strange poses of familiar objects. In Computer Vision and Pattern Recognition (CVPR). 2019.
294
295
[2] S. L. Blodgett, L. Green, and B. T. O'Connor. Demographic dialectal variation in social media: A case study of african-american english. In Empirical Methods in Natural Language Processing (EMNLP), 2016
297
298
[3] J. Byrd and Z. Lipton. What is the effect of importance weighting in deep learning? In International Conference on Machine Learning 2019. 2019.
300
301
[4] C. L. Canonne. short note on an inequality between KL and TV. arXiv preprint arXiv:2202.07198, 2022.
303
[5] K. Cao, C. Wei, A. Gaidon, N. Arechiga, and T. Ma. Learning imbalanced datasets with label-distriburion-awar margin loss. Advances in Neurul Information Processing Systems (NeurIPS), 2019.
304
308
[6] N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer. Smote: Synthetic minority over-sampling technique. Journal of Artificial Intelligence Research, 2002.
307
308
Y. Cui, M. Jia, T.-Y. Lin, Y. Song, and S. Belongie. Class-balanced loss based effective number of samples. In Computer Vision and Pattern Recognition (CVPR), 2019.
309
[8] L. Devroye and I.. Györfi. Nonparametric density estimation: the Ia view. Wiley Series in Probability and Mathematical Statistics, 1985.
310
[9] D. Freedman and P. Diaconis. On the histogram as density estimator: Le theory. Zeitschrift für Wahrscheinlichkeisshheooe und verwandte Gebiete, 1981.
313
314
[10] T. Hashimoto, M. Srivastava, H. Namkoong, and P. Liang. Fairness without demographies in repeated loss minimization. In International Conference Machine Learning (ICML), 2018.

---

316
[11] D. Hovy and A. Søgaard. Tagging performance correlates with author age. In Association for Computational Linguistics (ACL), 2015.
317
318
[12] B. Y. Idrissi, M. Arjovsky, M. Pezeshki, and D. Lopez-Paz. Simple data balancing achieves
319
competitive worst-grouppaccurreyy In Causal Learning and Reasoning, 2022.
320
[13] G. R. Kini, O. Paraskevas, S. Oymak, and C. Thrampoulidis. Label-imbalanced and group-
sensitive classification under overparameteriiztionn Advances in Neural Information Processing
322
Systems (NeurlPS), 2021.
325
[14] M. Kubat, S. Matwin, et al. Addressing the curse of imbalanced training sets: one-sided selection. In International Conference on Machine Learning (ICML), 1997.
324
325
[15] Z. Lipton, Y.-X. Wang, and A. Smola. Detecting and correcting for label shift with black box predictors. In International Conference on Machine Learning (ICML), 2018.
328
327
[16] E. Z. Liu, B. Haghgoo, A. S. Chen, A. Raghunathan, P. W. Koh, S. Sagawa, P. Liang, and C. Finn. Just train twice: Improving group robustness without training group information. In International Conference on Machine Learning (ICML., 2021.
328
329
[17] A. K. Menon, S. Jayasumana, A. S. Rawat, H. Jain, A. Veit, and S. Kumar. Long-tail learning via logit adjustment. In International Conference on Learning Representations (ICLR), 2020.
331
332
[18] S. Sagawa, W. Koh, T. B. Hashimoto, and P. Liang. Distributionally robust neural networks.
333
In International Conference on Learning Representations (ICLR), 2020.
334
[19] H. Shimodaira. Improving predictive inference under covariate shift by weighting the log-
335
likelihood function. Journal of Statistical Planning and Inference, 2000.
[20] R. Tatman. Gender and dialect bias in youtube's automatic captions. In ACL Workshop Ethics in Natural Laguage Processing, 2017.
337
338
[21] A. B. Tsybakov. Introduction to Nonparametric Estimation. Springer, 2010.
339
[22] M. J. Wainwright. High-ddmensional statistics: A non-asymptotic viewpoint. Cambridge
340
University Press. 2019.
341
[23] B. C. Wallace, K. Small, C. E. Brodley, and T. A. Trikalinos. Class imbalance, redux. In
342
International Conference on Data Mining (ICDM, 2011.
[24] K. A. Wang, N. S. Chatterji, S. Haque, and T. Hashimoto. Is importance weighting incompatible
with interpolating classifiers? In International Conference on Learning Representations (ICLR), 2022.
344
[25] I. Wasserman. Lecture notes in nonparametric classification. URL wtt.:tttp://// /eettps:/www.... www.wwwattt........ cmu
347
hhaa///arrr/ssmm/nnnaaraaaasss pdf [Online; accessed 12-May-2022].
348
2022. URL https::/enn wikipedia. wrggw/indee/reeeeeeooogeoogeoeoe phppttite-ooissson binomial_in [26]
Wikipedia contributors. Poisson binomial distribution Wikipedia, the free encyclopedia.
349
350
distribut 1tt.ttiioooollad1111111100000000
[Online; accessed 5-May-2022).
[27] D. Xu, Y. Ye, and C. Ruan. Understanding the role of importance weighting for deep learning.
352
In International Conference on Learning Representations (ICLR), 2020.
353
[28] Y. Yang and Z. Xu. Rethinking the value of labels for improving class-imbalanced learning.
Advances in Neural Information Processing Systems (NeurIPS), 2020.
355
[29] H.JJ. Ye, H.-Y. Chen, D.-C. Zhan, and W.-L. Chao. Identifying and compensating for feature deviation in imbalanced deep learning. arXiv preprint arX10:2001.013385, 2020.
356
Checklist
357
358
1. For all authors...
359
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
360
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
382
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
363
(d) Have you read the ethics review guidelines and ensured that your paper conforms to
them? [Yes]
10

---

385
2. If you are including theoretical results...
386
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
387
(b) Did you include complete proofs of all theoretical results? [Yes]
368
3. If you ran experiments..
369
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL.?? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
372
373
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
374
375
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
377
4. If you are using existing assets (e.g., code, data, models) or curating/releasnng new assets...
378
(a) If your work uses existing assets, did you cite the creators? [Yes]
379
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
381
382
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
383
384
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
386
5. If you used crowdsourcing or conducted research with human subjects...
387
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
389
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
380
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
382


Reviews:
[{"review_id": "k8DfxIsyXNr", "reviewer": "Reviewer_YJwh", "summary": "The paper studies group-structured distribution shift, in which there exists an identifiable majority and minority group in the dataset. The later group having fewer samples in train time even though at test they are equally likely to be in either group. The paper looks into two specific types of this type of distribution shift. In the case in which the distribution shift is controlled via the balance of labels, the paper proves that the minimax excess risk can be lower bounded with only the size of the minority class samples. They further introduce an undersampled binning estimator which achieves this lower bound up to a constant. The paper also examines group-covariate shift, in which the distribution shift is over the marginal of a feature. In this case the minimax excess risk can be lower bounded, but also requires the ratio of samples (wrt minority / majority groups) and the overlap of group-covariate measures, alongside the size of the minority class samples. Their undersampled binning estimator also has an upper bound on the minimax excess risk, but there is a gap when there is a high overlap in the minority / majority distributions. Simple experiments are presented which are consistent with the theory.", "questions": "Questions / Comments / Suggestions\n1. Is the 1-Lipschitz assumption common? It would be useful for a discussion on if this assumption appears in practice or if its is a common technical assumption.\n2. Short definitions / descriptions of $\\mathrm{TV}$ and VS loss would be useful for completeness\n3. There are short notes about the generalization of Theorem 4.1 and 4.2 for higher dimensions. Does the \"1/3\" to \"1/3d\" also hold for corresponding Theorem 5.1 and 5.2?\n\nMinor / Typos\n  - There seems to be a few typos / errors in the Appendix, the set of equation below Line 483: (1) on the first line the summation seems to be misplaced; and (2) the second last line seems to be incorrect / should be removed. This doesn't invalidate the proof.\n  - In the Appendix, equations below Line 514: \"$n_{maj}$\" -> \"$ n_{min}$\"", "limitations": "Assumptions / limitations of analysis is clear.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n  - The paper presents lower bounds for the lower bounds for the minimax excess risk for label shift and group-covariate shifts.\n  - Their proposed \"Undersampled Binning Estimator\" are optimal (or optimal in certain scenarios) up to a constant.\n  - The explanations and intuition provided of the setting and results.\n\nWeakness\n  - There are a few symbols which are not defined and some components in the experiments section which are not clear.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "iosBNa0iBnm", "reviewer": "Reviewer_xuzq", "summary": "The paper points out that minimax excess risk is lower bounded by a function of only the size of the minority group without additional parametric model assumptions or knowledge of the problem at hand. However, an undersampling + binning estimator achieves said lower bound. This implies that using samples from the majority-class/group does not improve, meaning that undersampling is optimal.", "questions": "I think many existing methods do infact use more structure than is allowed by the theory in the paper. Can the authors comment on what kinds of structure in the existing OOD literature helps do better than the proved lower-bound?", "limitations": "See questions.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper targets an important problem and the paper does a very good job pointing out both why undersampling does wonders in many cases and also why further work toward improve OOD should assume more structure. Good work!", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "V_3sIJlyKzv", "reviewer": "Reviewer_JtaE", "summary": "Motivated by the fact that undersampling the majority class remains a competitive approach to learning in the presence of class imbalance, this paper sets out to answer the following question: Is it fundamentally possible to learn a better model than that of undersampling? The paper also considers a related question pertaining to covariate shift, which I am dropping to make the summary concise. To answer this question, the authors prove a lower bound (converse bound) that shows that the number of samples needed to learn a min-max optimal classifier in this setting scales with $n^{-1/3}$. They show a matching upper bound based on undersampling based on which they conclude that undersampling is min-max optimal. The authors provide some experiments that confirm the results. Overall, I like the general positioning of the paper and the story is told nicely. However, I have serious concerns about the main theoretical results of the paper (Theorems 4.1 and 4.2) based on which I recommend the paper to be rejected given that these lower bounds are major contributions of this work.\n\n\n***** Update ******\n\nThe authors clarified my concerns in the rebuttal; in particular, I can see that the proof of Thm 4.1 was suffering from a typo, and the additional details clarified my concerns about the proof of Thm 4.2. As such, I agree with the other two reviewers that this is a significant piece of work and think should be highlighted in the conference (adjusting the score to 8). ", "questions": "* Can you please elaborate on the main weaknesses listed above with respect to the lower bounds in Theorems 4.1 and 4.2? There might be a way to fix this by updating the construction that is considered and working through the details but I was not able to immediately see a way out.\n\n* The proof of Theorems 4.1 and 4.2 are dense. It would be best to give an outline of how the proof goes first. For example, I was confused when $K$ was introduced for the first time, as it was not clear how this was going to be used.", "limitations": "The main limitation of this paper is that Theorems 4.1 and 4.2 in their current form are either vacuous or trivial (depending on how $n_{maj}$ is related to $n_{min}$), and hence they do not support the narrative of the paper. It is not clear to me how this might be fixed.", "rating": 8, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The authors ask an important question about min-max optimality of undersampling.\n\n* The paper is nicely written, nicely exposed, and the results appear to be novel to me.\n\n* The upper bounds for undersampling are intuitive, and the analysis is nicely done.\n\nWeaknesses:\n* The main weakness of the paper lies in the constant $c$ in Theorem 4.1. A closer look at the proof on page 19, line 514, shows that the constant $c = e^{-\\frac{n_{maj}}{3 n_{min}}},$ which *does* depend on both $n_{min}$ and $n_{maj}$ as opposed to the general story of the paper. In fact, $c \\to 0,$ as $n_{maj} \\to \\infty$ which contradicts parts of the story of the paper. The only way to keep $c$ to be a constant as $n_{maj} \\to \\infty$ is to let $n_{min} \\to \\infty$ with $\\frac{n_{maj}}{n_{min}} \\to \\eta$ for constant $\\rho$ in which case the result loses its interestingness because there is no distinguishable difference between $\\frac{c}{n_{min}^{1/3}} = \\frac{c_2}{n_{maj}^{1/3}}$ for some other constant $c_2$ and the theorem doesn't tell us anything non-trivial about class imbalance. In summary, the lower bound is vacuous unless $\\frac{n_{maj}}{n_{min}} \\to \\eta,$ in which case the lower bound is trivial.\n\n* A similar weakness applies to Theorem 4.2 for any $\\tau \\in (0,1)$, where $c$ vanishes as $n_{maj} \\to \\infty$. This can be seen based on the equation on line 637 which vanishes as $n_{maj} \\to \\infty$. Hence, similarly the lower bound is either vacuous or trivial in this setting as well.\n\n* Since the metric of interest is min-max excess risk, I wonder why the authors didn't consider a min-max baseline (instead of ERM) in this setting; Also smoothened versions of such min-max loss for better generalization, e.g., tilted loss (Li et al 2021): \nLi, T., Beirami, A., Sanjabi, M. and Smith, V., 2021. Tilted empirical risk minimization. ICLR.\nI also wonder if these baselines would be subject to the same empirical observations of Figure 2.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject