When Majorities Prevent Learning: Eliminating Bias to Improve Worst-group and Out-of-distribution Generalization
Authors: Yu Yang
Gintare Karolina Dziugaite
Baharan Mirzasoleiman
Venue: Submitted to ICLR 2023 (2023)

Abstract: Modern neural networks trained on large datasets have achieved state-of-the-art (in-distribution) generalization performance on various tasks. However, their good generalization performance has been shown to be contributed largely to overfitting spurious biases in large datasets. This is evident by the poor generalization performance of such models on minorities and out-of-distribution data. To alleviate this issue, subsampling the majority groups has been shown to be very effective. However, it is not clear how to find the subgroups (e.g. within a class) in large real-world datasets. Besides, naively subsampling the majority groups can entirely deplete some of their smaller sub-populations and drastically harm the in-distribution performance. Here, we show that tracking gradient trajectories of examples in initial epochs allows for finding large subpopulations of data points. We leverage this observation and propose an importance sampling method that is biased towards selecting smaller subpopulations, and eliminates bias in the large subpopulations. Our experiments confirm the effectiveness of our approach in eliminating spurious biases and learning higher-quality models with superior in- and out-of-distribution performance on various datasets.

Under review as a conference paper at ICLR 2023
WHEN MAJORITIES PREVENT LEARNING: ELIMINAT- ING BIAS TO IMPROVE WORST-GROUP AND OUT-OF- DISTRIBUTION GENERALIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Modern neural networks trained on large datasets achieve state-of-the-art (in- distribution) generalization performance on various tasks. However, their good generalization performance has been shown to be contributed largely to overfit- ting spurious biases in large datasets. This is evident by the poor generalization performance of such models on minorities and out-of-distribution data. To al- leviate this issue, subsampling the majority groups has been shown to be very effective. However, it is not clear how to find the subgroups (e.g. within a class) in large real-world datasets. Besides, naively subsampling the majority groups can entirely deplete some of their smaller sub-populations and drastically harm the in-distribution performance. Here, we show that tracking gradient trajecto- ries of examples in initial epochs allows for finding large subpopulations of data points. We leverage this observation and propose an importance sampling method that is biased towards selecting smaller subpopulations, and eliminates bias in the large subpopulations. Our experiments confirm the effectiveness of our approach in eliminating spurious biases and learning higher-quality models with superior in- and out-of-distribution performance on various datasets.
INTRODUCTION
Large datasets have enabled modern neural networks to achieve unprecedented success various tasks. Large datasets are, however, often heavily biased towards the data-rich head of the distri- bution (Le Bras et al. 2020) Sagawa et al., 2020 2019). That means, there are large groups of potentially redundant data points belonging to majority subpopulations, and smaller groups of ex- amples representing minorities. Larger groups often contain spurious biases, i.e., unintended but strong correlations between examples (e.g. image background) and their label. In such settings, overparameterized models learn to memorize the spurious features instead of the core features for the majority, and overfit the minorities (Sagawa et al., 2020). As a result, despite their superior per- formance on in-distribution data, overparameterized models trained on biased datasets often have poor worst-group and out-of-distribution generalization performance.
To improve the high worst-group error and of duitrf-distribution generalization, techniques such as distributionally robust optimization (DRO), or up-weighting the minority groups are commonly used (Sagawa al. 2019 2020). However, such methods have been shown be highly ineffective for overparameterized models in the presence of spurious features (Sagawa et al. 2020). When majority groups are sufficiently large and the spurious features are strong, overparameterized models choose to exploit the spurious features for the majorities and memorize the minorities, it entails less memorization on the entire data. this setting, upweighting minorities only exacerbates spurious correlations, and subsampling the majorities has been advocated for (Sagawa al.) (020)). But, this requires the groups to be specified beforehand, which not available for real-world datasets. Be- sides, random subsampling of the majority groups entirely deplete some of their subpopulations and drastically harm the in-distribution performance (Toneva et al. 2018 Paul et al.) 2021). l).
In this work, propose effective way to find large subpopulations of examples (see Fig, I and subsample them to ensure inclusion of representative examples from all the subpopulations. We rely on the following recent observations. In the initial training epochs, the network learns important

---

Under review as a conference paper at ICLR 2023
Subpopalations
Groups
Majority groupe Landbird with background
Minerity group: Landbird with background
Group Size
120
Larger subpopulation
80
60
23
Smaller sa subiaquutttion
An illustration of large/small subpopulations within the majority/minority groups in the same class of the Waterbirds dataset (Sagawa et al. 2019).
Figure 1:
features and the NTK undergoes rapid changes, which determine its final basin of convergence (Fort al., 2020). This results in learning linear function during the initial epochs, followed by learning functions of increasing complexity (Nakkiran et al. 2019). We show that large subpopulations are responsible for forming the initial linear model, by inserting large gradient forces in the first few epochs. The minorities, the other hand, dictate the higher-complexity functions later in training. To find the large subpopulations, we track the gradient trajectories- the way the gradient changes- during initial training epochs. Then, cluster similar gradient trajectories together, and employ an importance sampling method that samples data points from every cluster by probability equal to the inverse of the size of the cluster it belongs clusters. By studying the effect of our method on the evolution of the model early during the training, we show that our method allows the model to better learn from all the subpopulations by balancing the gradient forces between different groups. This enables learning higher-quality features.
This allows selecting balanced subset from different
Our empirical studies confirm the effectiveness of our method in improving the worst-group and out-of cittof-diitribbtiin generalization, while enjoying superior in-distribution performance even when the size of the selected sample is small. Notably, on CMNIST (Alain et al.) (0155) and Waterbird (Sagawa et al., (019)) datasets which contain strong spurious biases, our method achieves a com- parable or even better performance than the state-of-the-as methods, which rely on the underlying group information to uniformly subsample the majority group. In addition, on CIFARIO, CIFAR Krizhevsky et al., 2009), and Caltech256 (Griffin et al., (007)) our method provides a superior in- distribution performance to state-of-the-as the-aart data pruning methods, based on forgettability (Toneva et al., 2018) and EI2N (Paul et al.) 2021) scores, especially for small subsets. At the same time, outperforms such methods on custof--istiobution data, CIFARIOC (Hendrycks & Dietterich 2019).
2 RELATED WORK
Data pruning for worst-group generalization. To improve the generalization performance on minorities, preventing the model from learning spurious features is very helpful (Sagawa et al.) 2019) 2020). For overparameterized models, randomly subsampling the majorities has been shown to be the most effective (Sagawa et al. 2020) than distributionally robust optimization (DRO) (Sagawa (et al. 2019) and up-weighting the minority groups (Sagawa et al. 2020). However, this requires the group labels to be specified beforehand, which is not available for large real-world datasets. Be- sides, if the majority contains imbalanced subpopulations, random subsampling inherits similar bi- ases. Finally, random subsampling of the majority groups entirely deplete some of their smaller subpopulations and drastically harm the in-distribution performance, as we empirically show.
A different line of work (Sohoni et al. 2020
Nam et al. 2020 Ahmed et al.) 2020 Liu al. 2021
Creager et al., 2021 Taghanaki et al. 2021
2021) studies how to improve worst-group generalization without having access group labels. These methods require training a model first to minimize the average empirical risk before training the robust model, which
Zhang et al.) 2022 Nam et al.
doubles the training time and is thus also not practical for large real-world datasets.
2

---

Under review as a conference paper at ICLR 2023
Data pruning for OOD generalization. Spurious features have been shown to also harm the out-
of-distribution generalization (Le Bras et al. 2020). To alleviate this, Swayamdipta et al. (2020)
proposed to train the subset of most ambiguous instances whose true class probabilities fluctuate
frequently during training, and Le Bras et al. (2020) employed AFLite (Le Bras et al. (020) to iter-
atively filter highly-predietan partitions of the data. However, such methods drastically harm the in-distribution performance.
examples by training multiple linear classifiers different random
Data pruning for in-distribution generalization. The main idea behind all data pruning methods to define notion of example difficulty, and prune the easy-to-leam examples. Notably, Coleman et al. 2020) used a smaller trained proxy model to find the most uncertain examples to train larger model. [ooeva et al. (2018) defined a forgetting event of an example as transitioning from being classified correctly to incorrectly during training, and drop the examples with forgetting events. Most recently, Paul et al. (202I) dropped examples with the lowest average errors (EL2N) recorded early in training and averaged over several initializations. The above heuristics require full or partial training of multiple models, can only drop a relatively small fraction of the examples, and hurt the ant-of-distribution performance, as we show in experiments. In contrast, our method can successfully alleviate bias and achieve a superior in- and out-of-distribution performance.
3 PROBLEM FORMULATION
Training machine learning models is often reduced to minimizing an empirical risk function (ERM). That is. the goal is to find the parameter w" that minimizes the average error on the entire training data D (X.y) y (I., vi)lev where V = [1,...,,) .n} indexes the training data. Formally,
w" arg mew
[(w) B. [[[(w, ..). yr))):
(w,z;), where w is the model parameter, and (w.) and (ff(w, xz), y1) are the output of the network and
the value of the loss associated to training example (z,, yk). respectively. For large datasets, the average error L is minimized by applying (Stochastic) Gradient Descent with learning rate ry starting from a random initial point Wo:
Wi+1 = wi VVW(()) V((w:) = = [w,, X) ()((((;; (
(2)
where y = {m X = {.:)7-1 1. and J (w, X) E Rxxx is the Jacobian matrix associated with the nonlinear network f:: R2d + R defined as
-ff(w x1)
of(w, xnn) }n)JT,
J(w,
Ow
and V vy((f(w; (w,, x)), ys) is the gradient of the loss w.r.t the network. Furthermore, ( X)
X
I J(w, X J [),(w x)" is the empirical neural tangent kernel (NTK) (Jacot et al., 2018 Du et al. 2018), describing the evolution of the network during training by gradient descent.
Spurious features and majority groups. We consider similar setting with (Sagawa et al. 2019 2020), where each training example (z,, y:) is associated with a spurious attribute o, that correlated with its label ys- The examples with the same spurious attribute and label make a group 9j.k E G, where Ij.A = ((x,, yi)li E V, = j. = k}. The groups which contain considerably more examples than the rest are referred as majority groups. For example, in the Waterbirds dataset (Sagawa et al. 2019). every example (x,, belongs to one of the 2 classes, Vi (waterbird, landbird] and the image background ag E {water background, land background) is spuriously correlated with the label yi- Thus, there are four groups of examples associated with every combination of spurious attribute and label, i.e., G =(waterbird,, water background), (waterbird, land background), (landbird, water background), (landbird, land background).. The majority groups are (waterbird, water background), and (landbird, land background). Importantly, in this work, we assume that the groups and spurious attributes are not known at training time.
Subpopulations. Every dataset can be partitioned into s different subpopulations of examples that are similar in terms of their effect on training, i.e. the indices of the training data V can be partitioned into V = (V1.- V.}. For a formal definition, see Section 4.2 Note that subpopulations may represent finer clustering compared group clustering. Fig. shows illustration of groups subpopulations for Waterbird dataset. We develop a method that automatically clusters the data and identifies large subpopulations.
3

---

Under review as a conference paper at ICLR 2023
Objective. Our goal is to find subset S C V of size [S] from all training examples indexed by V. such that training on the subset alleviates the effect of spurious biases and improves (1) the worst-group generalization when the groups are imbalanced, or (2) out-of-distribution generalization under distribution shift. In both cases, we aim to preserve a good performance on the in-distribution data. In particular, the worst-group error is defined as,
Errwg = max LE yeg
Ee..vigll # yr (w, x;)],
(4)
where ys (w (2;,,) wi) is the label predicted by the model. In other words, Eriwng measures the highest fraction of examples that are incorrectly classified across all groups. Similarly, the out-of distribution (OOD) performance measures the performance of the model I trained on the training set DD and tested on D' (c(X), v). when è is from a set of shifting functions C. Formally,
oroood E (r, )ED' [ys + yy (w, (w,z;)),
(5)
measures the fraction of examples that are misclassified when (I,, yi) is drawn i.i.d from D'.
4 ELIMINATING BIAS IN THE DATA
In this section, we present our main results. We start by discussing the effect of large subpopulations on early learning dynamics. Then, we explain how gradient trajectories of examples during the initial training epochs allow finding the large subpopulations. Next, we employ importance sampling to find a subset that contains similar number of examples from subpopulations. Finally, we study how the subset found by our method affects the network's early learning dynamics.
4.1 EFFECT OF LARGE SUBPOPULATIONS ON EARLY LEARNING DYNAMICS
Recent empirical studies on neural networks" training dynamics show that in the initial epochs the performance of a network trained by SGD can be explained by a linear classifier. Formally, if F and L are the corresponding random variables for the neural network and a linear model respectively, the mutual information between F' and conditioned on L, y(F's( L), captures the part of F's success on the prediction of y in addition to L. Then the performance correlation between and L, (F; L)= := I(F: y) [[F; y L). is the part of F's success on the prediction of that can be ::F:g explained by L. Nakkiran et al. (2019) show that there exists To such that My (F;; L) I(F;;y) at training step for all / < To As training progresses, the network learns functions of increasing complexity (Nakkiran et al. 2019). Furthermore, Fort et al. (2020) show that during the first few epochs of training, neural network experience a rapid initial transient which determines the final basin of convergence. During this period, the NTK changes very rapidly and learns useful features.
First, we empirically show that large subpopulations responsible for forming the initial linear model in the first few training epochs. Effectively, during training every example contributes to minimizing the loss by its gradient. Examples with similar gradients insert similar force the model and affect the model in the same direction. In the first few epochs, large gradient forces of large subpopulations highly bias the initial linear function. As the gradient forces of large sub- populations persist during training, the initially learned linear function is retained, to the point of zero training error (Nakkiran et al. 2019). As result, large subpopulations dictate the rapid initial change of the NTK and the prominent features learned in this phase. On the other hand, smaller sub- populations have smaller influence on the model, and require a larger number of training iterations to be learned by the higher-complexity functions that are shaped later during the training.
When the spurious bias is strong, the initial linear function is dictated mainly by the spurious fea- ture, and persists during training. This provides good training and generalization error on the large groups, and thus prevents learning their core features On the other hand, on the small subpopula- tions, functions with much higher complexity overfit and memorize the minorities. Such functions result in a small training error but a poor worst-grous generalization performance on the minorities. This further explains the observation by Sagawa al. (2020) showing that overparameterized mod- els memorize the spurious feature and overfit the minorities. Effectively, the spurious features in large subpopulations prevent the model from learning the core features from the data.
Fig. 22 shows that the network's prediction early in training can be well explained by a linear clas- sifier (red). Besides, the network trained on large subpopulations can be well explained by the same
4

---

Under review as a conference paper at ICLR 2023
IKFe YI I0F Y| LINIARPE VI
IMF, Lange: Vi- R.F, Lange: Lin 1)
Mutual Information
Mutual Information
[MFF, Sclect, V) Select, LINMMEF
MF: Lange:
Accuracy
IPF, Select 1)
Y2-MM Y
RFF: Lange: Y-- Y Lin)
Solect 1) Riy Lmm)
Post Linerr
SGD epochs
SGD epochs
(a)
(b)
Figure 2: CIFAR-10/- CNN. (a) mutual information between the labels, and linear model
fitted to entire training data, with networks trained on full data, large subpopulations, and our subset. (b) Fraction of network predictions explained by a linear classifier fitted to full data (blue). large subpopulations (orange), and our subset (green). Large subpopulations shape the model initially.
linear classifier (purple). This confirms that early training dynamics are dictated by large subpopu- lations. We also see that the behavior of the network trained on the subset selected by our method (discussed in Section 4.3) cannot be explained by the same linear model (brown). Fig. 2b shows that the linear model explaining the network trained on full data (blue) is similar to the linear model explaining the network trained on large subpopulations (orange), but different than the one explain- ing the network trained on our chosen subset (green). We see that the performance of the network can be well explained by a linear mode, and the linear model fitted on large subpopulations closely matches the one fitted on the entire data. These results further confirm that the linear classifiers fitted to entire data and large subpopulations are effectively the same during the initial training epochs.
4.2 FINDING THE LARGE SUBPOPULATIONS IN EVERY CLASS
The first question we aim to answer is how to find the large subpopulations of the data, without hav- ing such labels. As discussed, larger subpopulations insert large gradient force on the model, and are learned during the initial epochs. When an example is learned, its gradient becomes nearly zero. Hence, every example has a gradient trajectory interpolating between its gradient at initialization and zero. Subpopulations that affect the model similarly have a similar gradient trajectory during training. Therefore, large subpopulations with similar gradient trajectories can be identified based on their gradient trajectory during the first few epochs.
To find the large subpopulations, we cluster the gradient trajectories during the initial epochs of training. As gradients are very high-dimensional, we first reduce the gradient dimensionality to better find the clusters. To do so, we rely on the following observation: for neural networks, the variation of the gradient norms is mostly captured by the gradient of the loss w.r.t. the input to the last layer of the network (Katharopoulos & Fleuret 2018). The above wwwer-dimensional gradients can be efficiently computed in closed form, and has been used as gradient proxy in several recent works (Mirzasoleiman et al. 2020 Paul et al.] [021]] Pooladzandi et al., 2022). Formally, for every example we build its gradient trajectory by concatenating the lower-dimensional gradients during the first training epochs, i.e.,
I0 = (V ([[((W U:), ()1(( v:), . (,,((w,,,,)) v:),
U:),
(6)
where V v,(((W,, 21). y4) is the gradient of the loss w.r.t the input to the last layer of the network at epoch j for training example (z, 24). Note that as the gradient of an example depends on its label, examples from different classes do not have a similar gradient. Hence, we find similar gradient trajectories from every class separately.
Next, we cluster gradient trajectories to find the large subpopulations in every class. While any clustering algorithm can be used, we use the k-medoids objective find the clusters efficiently. In particular, for 0 < к < 1, we partition a class indexed by V. S V to ki = k - |Val subpopulations, by first finding the set S. of its ke most centrally located gradient trajectories (medoids) by solving:
Ste arg max F(S) s.t.
F(S)= = Σ max [ v.) V9' W;))), (7)
SCV,, Sk.
VeV.
JES.
5

---

Under review as a conference paper at ICLR 2023
Algorithm Training without Bias
Input: Model f. initial epoch number I, subset fraction Output: Model f trained without bias
1: Train the model f for t epochs from wo and save gradient trajectories Vg y.) for all i V
2: for every class Va do
3:
So 5-
4:
for = 1,,,....
|Vl do j E arg mVV. F(e(S.)
5:
6:
S. = S. {i}
7:
for E |S.l do
8:
Ve, {j Vali = arg min [in - [1y(w,x,))
9:
for V do
10:
Wj = Voil s.t. j E Vo
11:
p 1/w;
s.t. u, (0, 1) is uniform random number
12: S= fr examples with the largest p.}
13: Train the model f from wo on 5
where ent is large constant. Then to find the subpopulations, we assign every example to the medoid j with the most similar trajectory. This partitions examples in class Va to k. subpopula- tions V. (Ve,1. Ve where Ve,
{ie Velj arg min [(= y)) I(x, vo)ll)-
The maximization problem (Eq. 77) is NP-hard. However, since the k-medoids objective is mono- tone and submodular] a near-optimal solution of size i can be found efficiently in O([V] k) time. For maximizing a monotone submodular function, the greedy algorithm provides (1 1/e) ap- proximation guarantee (Wolsey 1982). The greedy algorithm starts with the empty set So and at each iteration I, chooses an element e V such that S S U {arg max F S(-1))
4.3 BALANCING THE SUBPOPULATIONS
To alleviate the bias of the large subpopulations and enable effective learning of core features, we aim prune the large gradient trajectory clusters formed in initial epochs. This prevents the initial linear model from being biased toward the large subpopulations. In doing so, we allow the initial linear model to capture the complexity in different subpopulations, and learn the core features in- stead of the spurious features of the majorities. Hence, the model obtains a better generalization performance on minorities and -iitr--diittibttion data. However, this should be done carefully as over-pruning the large subpopulations prevents them from participating in forming the initial model. This drastically harms the in-distribution generalization performance of the model.
To address this, we employ an importance sampling method on the union of the subpopulations of all classes, select every example by probability equal the inverse of the size of the subpopulation it belongs to. In particular, we weigh every example i E V.., by the size of the cluster j E S, it belongs to, i.e., w;; |Vogl- Then, we use the algorithm of Efraimidis sample with probabilities equal to = 1/w,, without replacement. The sampling procedure works as follows. For each example in the dataset, we independently generate a uniform random number u, E (0, 1) and calculate g; = u. 1/w, Examples that possess the r largest 9; form the final subset S.
Spirakis (2006) to select
Our sampling method biases the sample selection towards the smaller subpopulations, and drops many examples from the larger subpopulations. However, it still preserves the patterns in larger subpopulations, by including smaller number of their examples in the sample. Effectively, our method balances the gradient forces between different subpopulations. This increases the strength of the core gradient vs. the spurious gradient. In doing so, allows different subpopulations to participate in forming the initial linear model and dictate more generalizable basin in which the model can be further -uned. Hence, enables better learning the core features.
The pscudocode is illustrated in Algorithm !
A set function F 2 + R is submodular if F(e(S) F(SU F(S) F(TU()) F(T), for any V and V AT. F monotone if F (e((S) for any EEVYS and CV.

---

Under review as a conference paper at ICLR 2023
Epoch = 1.0
Epoch = 2.0
Epoch 3.0
Epoch = 4.0
Grad Norm
1.0
0.5
20
40
20
40
0
20
40
20 Cluster Size
40
Cluster Size
Cluster Size
Cluster Size
Figure 3: Average gradient norm per cluster vs. cluster size.
4.4 EFFECT OF PRUNING EARLY NETWORK EVOLUTION
Next, we take a closer look at the effect of our method on the evolution of the model. In particular, show that training on the subset selected by our method decreases the speed of learning on large subpopulations and lets the other groups have larger contribution to the initial phase of learning.
When the model is trained on the subset Ds = (X s: ys), the weight evolution over one step can be written as
Asw; = - Vi(w,, Xs) = -nj -w; X s) ''V /[(f(w;; xs) ys). Furthermore, the network evolution can be approximated using a first-order Taylor expansion, i.c.,
(8)
A X) J Jww, A) -w; X) (w: Xs ' ( X s))
x
(9)
= - X V f(1, (X s. s.ys)),
(10)
where (x (s) I (wi, (w; x) is the empirical neural tangent kernll, describing the evolution of the network when training only on the subset S. The following Lemma quantifies the effect of pruning the large subpopulation on the model evolution at one training step.
Lemma 4.1 Training on the subset S sampled from Ç subpopulations found by our method, with learning rate 1, S 1/1l (w, X)l changes the predictions of the model at every step by at most: (w,,
[ X) - As (w, XI||
,l (X w.) 0,(X, X w:)ll
(11)
< Σ la's -axl max Vi(f (z) JEV.
(12)
=E(
where ag V₂l is the size of subpopulation Ve, and a' = V n S is its size in the subset S.
The proof can be found in Appendix A.I
Lemma 4.1 upper-bounds how training on the subset found by our method changes the effect of different subpopulations on the model predictions. When the subpopulations are approximately balanced, we have a' Kag. Thus, training tion to that of the full data, and only scales down the learning rate. However, when subpop- ulations are imbalanced, it effectively decreases the gradient force of large subpopulations by la, -a'l- max,ev; ( x; U;), Effectively, this reduces the speed of learning and bias of such subpopulations preserves the small subpopulations, i.e., Ot s a' and maintains their original gradient force on the model. Therefore, our subset balances the gradient forces and let different subpopulations par- ticipate in forming the examples large subpopulations have smaller gradient norm. Hence, a larger number of them can be pruned without significantly affecting the model. However, entirely dropping the large subpopu- lations have a larger cumulative effect compared to dropping a smaller number of examples small subpopulations with larger norms. Hence, it drastically harms the in-distribution performance.
the subset S yields similar network evolu-
the model. On the other hand, our importance sampling method
models in the initial epochs. As Fig, B shows, individual
5 EXPERIMENTS
In this section, we evaluate the effectiveness of our method assisting neural networks to learn better features. In particular, consider the following two scenarios. First, apply our method to improve the worst-grous generalization performance, when training data contains spurious corre- lation. Then, consider the application of our method improve auttof-dditributtion performance, under distribution shift. both cases, we also compare the in-distribution generalization perfor- mance of the networks trained subset full training data.
7

---

Under review as a conference paper at ICLR 2023
Water background
Land background
Original
ERM
Random
Ablation
Original
ERM
Random
Abtistion
Ours
Waterbirds
Landbirds
Figure 4: GradCAM Visualization. Warmer colors denote higher saliency, and correspond to the pixels that are more important in making the final classification. The subset found by our method allows the model to effectively learn the features instead of spurious ones.
Table 1: Worst-group and average accuracy (%) Waterbird and CMNIST 20% subsets.
Group
Train
CMNIST
Waterbirds
Labels
Twice
Worst-group
Average
Worst-group
Average
ERM
No
58.4118.8
89.811.4
67.4
97.7 0.1
Balanced
Yes
No
92.5:11.0
95.1+110
89.1 0
90.7 0.9
Upweight
Yes
No
0.0:0.00
21.210.0
78.0=20
86,8 1.8
Random
No
No
56.7+3.2
90.0+0.33
6.0
97.7 0.1
Ablation
No
No
0.0+00.0
20.0++0.1
2.3
93.7
Ours-Prune
No
No
85.5+44.9
94.2-006
77.2 1 1.3
97.7 0.2
Ours-Reweight No
No
91.6.11.0
96.0
79.1 1 0.9
97.4 0.1
5.1 WORST-GROUP GENERALIZATION IN PRESENCE OF SPURIOUS CORRELATION
First, we evaluate the worst-group generalization performance of a model trained on our subset vs full data, in presence of spurious correlation. We record gradient trajectories during the initial epochs and select 10% training examples the subset. The reported results are averaged over runs.
Datasets & Models. We apply our method to the Colored- -NIST and Waterbirds datasets. The CoNSTTd-MNIST dataset is synthetic dataset derived from MNIST (LeCun et al. 1998). It was first proposed in (Alain et af.; 2015) as a binary classification task that contains spurious correlations the grey-scale digits changed to colors that are strongly correlated with the labels. We a 5- layer CNN with 2 convolutional layers and fully-connected layers. The Waterbirds dataset is intro- duced by (Saawa al. (2019) study the spurious correlation between the background and the fore- ground in image recognition. Species in Caltech- UCCD fards-200-200 (Wah al. (011] are grouped into classes, waterbirds and landbirds. All birds are then cut and pasted onto new background images, with waterbirds more likely to appear water and landbirds having a higher probability on land. There are 4795 training examples total, 3498 for landbirds with land background, 184 for landbirds with water background, 56 for waterbirds with land back- ground, and 1057 for waterbirds with water background. We use a pretrained ResNet-50 model.
(CUB-200) (0002001) dataset
Baselines. Empirical risk minimization (ERM) trains all data, Random selects subset uni- formly at random, Upweight weights every example by the inverse the group size, Balanced samples equal number of examples from different groups. Ablation. To show the failure mode of random sampling when the majority has imbalanced subpopulations, we modify the dataset to make it more imbalanced, by pruning smaller clusters.
Evaluation metrics. We use two metrics proposed in Sagawa et al. (2019), namely worst-group accuracy and adjusted average accuracy. Worst-grous accuracy is the minimum accuracy across all groups, and A Adjusted average accuracy is the average accuracy over groups weighted by their size. Results. Table shows that the models trained on subsets found by our method obtain the high- est worst-group and in-distribution test accuracy, when compared with baselines that do not require group labels. Besides, our method achieves a comparable performance to those that use the group in- formation, and even outperforms them on the Waterbird dataset. We note that having group labels is not available in real-world datasets. Methods that do not rely on group labels, including our method, do not require knowing the minority groups Therefore, they more practical in realistic settings.
8

---

Under review as a conference paper at ICLR 2023
CINA-10
C3TA4-100
Catech
Terpd treche
Ne Frining
No Prrrine
Kandon
kanden
EL2h 22
1.2h-tppoh2
Cur
Cur
0.
2.6
6.7
0.
0.
6,5
0.7
0.2
0.6
6.3
0.
(a) CIFAR-10
(b) CIFAR-100
(c) Caltech-256
One snot Starataatin 95% Prreed
G2.
Pusns
Oum
GRA0CAR nol thet irppl Nieciooc Mrr
2o0m,bar Dar
Agg
fratt
br orggevass
CentaN diattc www.dorrrmmmmmmmmmmmm plotitaa peg_compastton
Comppiion
(d) Out-of-distribttoon performance on CIFAR-IOC
Figure 5: In-distribution and out-of-distribution generalization. (a)-(c) final test accuracy on a stan- dard (in-distribution) test set, (d) out-of-distribution performance for subset of size 20%.
GradCam. Fig. demonstrates GradCAM (Selvaraju et al. 2017) visualizations depicting saliency maps for samples from the Waterbirds dataset with water and land backgrounds. Warmer colors denote higher saliency, suggesting that the model considered these pixels more important in making the final classification measured by gradient activations. We see that the subset found by our method allows the model to learn the core features much better than ERM and Random baselines.
5.2 OUT-OF-DISTRIBUTION GENERALIZATION UNDER DISTRIBUTION SHIFT
Next, we empirically evaluate the in-distribution. and under distribution shift. The results are based on 3 independent runs, each with different mini- order and initial parameter values. We record gradient trajectories during the initial 4 epochs.
performance of our method
Datasets. We apply our method to CIFAR-I0 and CIFAR-100 (Krizhevsky et al. 2009), and C56 (Griffin et al. (007). In particular, we keep the number of training iterations fixed (78k for CIFAR- and CIFAR-TO0, and 4.8k for Caltech- 256) as we vary the size of the subset.
Baselines. We compare our method with Random sampling, and the state-of-the-art baselines for in-distribution data pruning, based on EL2N (Paul et al. 2021), forgetting scores (Toneva et al.) 2018 The EL2N score of training example is defined as E V x;) y 2l22- We calculate EL2N after 20 epochs of training and average it over 10 different runs, as this is shown to be the most accurate. Forgetting score of example the number of times the examples are misclassified after being correctly classified during the entire training. We calculate the number of forgetting events for each training example by averaging over 5 runs of 200 epochs, as suggested by Toneva et al. (2018). Results. Fig. 5 (a), (b), (c) show that on different datasets, training on the subset selected by our method gives much higher in-distribution test accuracy than Random, and EL.2N or forgetting scores particularly when the subset is small. Note that EI2N and forgettability baselines use more information over many training epochs and multiple runs. Importantly. Fig. (d) confirms that our method outperforms the baselines on CIFAR- 10C (Hendrycks & Dietterich 2019), with distribution shift. We train on our downsampled CIFAR- 10 training set, and test on CIFAR-TO-C (Hendrycks & Dietterich 2019). a collection of OOD test sets for CIFAR-10. For each corruption type, we report the average test accuracy over 5 different intensity levels. Our method can achieve at least 2% higher test accuracy than other baselines. For some corruption types (Gaussian noise, shot noise, and impulse noise), performance is even on par with or surpasses training the full data.
CONCLUSION
We showed that larger subpopulations containing spurious biases prevent learning high-quality fea- tures. We showed that large subpopulations can be identified by tracking gradient trajectory of examples in initial epochs. Then, we proposed an importance sampling method to balance the subpopulations and ensure inclusion of representative examples from all the subpopulations. Our experiments confirmed the effectiveness of our approach in eliminating spurious biases and learning higher-quality models with superior in- and -fitt---iittiuution performance various datasets.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Faruk Ahmed, Yoshua Bengio, Harm van Seijen, and Aaron Courville. Systematic generalisation with group invariant predictions. International Conference on Learning Representations, 2020.
Guillaume Alain, Alex Lamb, Chinnadhurai Sankar, Aaron Courville, and Yoshua Bengio. Variance reduction in sgd by distributed importance sampling. arXiv preprint arXiv:1511.000 1.06488,, 2015.
Coleman, C Yeh, S Mussmann, B Mirzasoleiman, P Bailis, P Liang, J Leskovec, and M Zaharia. Selection via proxy: Efficient data selection for deep learning. In International Conference Learning Representations (ICLR), 2020.
Elliot Creager, Jörn-Henrik Jacobsen, and Richard Zemel. Environment inference for invariant learning. International Conference on Machine Learning, pp. 2189-2200. PMLR, 2021.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes ewer-parameterized neural networks. In International Conference on Learning Representations, 2018.
Pavlos S Efraimidis and Paul G Spirakis. Weighted random sampling with reservoir. Information processing letters, 97(5):181-185 2006.
Stanislav Fort, Gintare Karolina Dziugaite, Mansheej Paul, Sepidch Kharaghani, Daniel M Roy, and Surya Ganguli. Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the neural tangent kernel. Advances in Neural Information Processing Systems, 33:5850-5861, 2020.
Gregory Griffin, Alex Holub, and Pietro Perona. Caltech-256 object category dataset. 2007.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common cor- ruptions and perturbations. Proceedings of the International Conference on Learning Represen- fations, 2019.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, 31, 2018.
Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling. In International conference on machine learning, pp. 2525-2534. PMLR, 2018.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Ronan Le Bras, Swabha Swayamdipta, Chandra Bhagavatula, Rowan Zellers, Matthew Peters, Ashish Sabharwal, and Yejin Choi. Adversarial filters dataset biases. International Confer- ence on Machine Learning, pp. 1078-1088. PMLR, 2020.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 96(11):2278-2322 1998.
Evan Z Liu, Behzad Haghgoo, Annie S Chen, Aditi Raghunathan, Pang Wei Koh, Shiori Sagawa, Percy Liang, and Chelsea Finn. Just train twice: Improving group robustness without training group information. In International Conference on Machine Learning, pp. 6781-6792. PMLR, 2021.
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In International Conference on Machine Learning, pp. 6950-6960.
PMLR, 2020.
Preetum Nakkiran, Gal Kaplun, Dimitris Kalimeris, Tristan Yang, Benjamin L Edelman, Fred Zhang, and Boaz Barak. Sgd neural networks learns functions of increasing complexity. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 3496-3506, 2019.
10

---

Under review as a conference paper at ICLR 2023
Junhyun Nam, Hyuntak Cha, Sungsoo Ahn, Jacho Lee, and Jinwoo Shin. Learning from failure: De-biasing classifier from biased classifier. Advances in Neural Information Processing Systems, 2020.
Junhyun Nam, Jachyung Kim, Jaeho Lee, and Jinwoo Shin. Spread spurious attribute: Improving worst-group accuracy with spurious attribute estimation. In International Conference on Learning Representations, 2021.
Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on a data diet: Find- ing important examples early in training. Advances in Neural Information Processing Systems, 34, 2021.
Omead Pooladzandi, David Davini, and Baharan Mirzasoleiman. Adaptive second order coresets for data-efficient machine learning. In International Conference Machine Learning, pp. 17848- 17869. PMLR, 2022.
Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang, Distributionally robust neural networks. International Conference on Learning Representations, 2019.
Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang. An investigation of why overparameterization exacerbates spurious correlations. In International Conference on Machine Learning, pp. 8356. PMLR, 2020.
Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based local- ization. In Proceedings of the IEEE international conference on computer vision, pp. 618-626, 2017.
Nimit Sohoni, Jared Dunnmon, Geoffrey Angus, Albert Gu, and Christopher Ré. No subclass left behind: Fine-grained robustness in coarse-graines grained classification problems. Advances in Neural Information Processing Systems, 33:19339-19952 2020.
Swabha Swayamdipta, Roy Schwartz, Nicholas Lourie, Yizhong Wang. Hannaneh Hajishirzi, Noah A Smith, and Yejin Choi. Dataset cartography: Mapping and diagnosing datasets with training dynamics. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 9275-9293, 2020.
Saeid Taghamaki, Kristy Choi, Amir Hosein Khasahmadi, and Anirudh Goyal. Robust representa- tion learning via perceptual similarity metrics. In International Conference Machine Learning, pp. 10043-10053. PMI.R, 2021.
Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey Gordon. An empirical study of example forgetting during deep neural network learning. In International Conference on Learning Representations, 2018.
C. Wah, S. Branson, P. Welinder, P. Perona, and S. Belongie. Technical Report CNS-TR-2011-000 1-000, California Institute of Technology, 2011.
Laurence Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385-393, 1982.
Michael Zhang, Nimit S Sohoni, Hongyang R Zhang, Chelsea Finn, and Christopher Re. Correct-n- contrast: a contrastive approach for improving robustness to spurious correlations. Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Ma- chine Learning Research, pp. 26584-26516. PMLR, 17-23 Jul 2022.
11

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
A. PROOF OF LEMMA 4.1
The logits evolution at one step can be written as:
A fw), x)
Asf(w, http:///w/lllllllll..x//////.//.
w.)ll
(13)
(14)
s n/|J X||| ,,, " - J (w. (s) (X s, w.))
(15)
< (((((w),)))) - Σ vI(f(w::2,))
(16)
E
JES
E v((f(w:xz)) 2,).
(17)
SEV.
- Σ
Σ
[V [1, 2,), B3),
(18)
*E
JEV.
la!- azl
max vl(f(w,,z,) JEV.
(19)
=E[c]
where Eq. equation 14 holds because 7, S 1/J (w,,
A.2
EXPERIMENTATION DETAILS
A.2.1 DATASETS
CMNIST We construct colored MNIST dataset with spurious correlations by using colors as the spurious attributes as the following. First, we define an image classification task with classes by mapping every 2 consecutive digits (0 and 1, and 3, 4 and 5, 6 and 7, 8 and 9) into the same class. We use the official test split of MNIST, randomly select 50k examples from the train split as the training set, and then the rest 10k samples in the train split as the validation set.
Then, for each class yr. we color the foreground of Peorr.i fraction of training examples with color a, from the set of colors A=(4 by their hex codes. We call this fraction of data the majority group of class y;- The higher the Peorrii the stronger the spurious correlation between the class yi and the spurious attribute az For the rest
#855E00, #00fff3, 4 6e00ff, 4 4ff0018] represented
1-Pcorr, training examples, we color them with random color from A' a,, In Fig. 6 we visualize examples classes with 5 colors and highlight the majority groups with white bounding boxes. In our experiments, we used Pcorr = [0.995, 0.95, 0.9, 0.8, 0.6] to construct spurious correlations with different strengths and groups with different sizes.
A.3 ADDITIONAL EXPERIMENTS
12

---

Under review as a conference paper at ICLR 2023
Class
Class Class
3
2
3
2
3
4
S
5
3
Class
6
6
7
6
6
Class
9
8
9
9
9
Figure 6: Visualization of the CMNIST dataset. We combine every 2 digits into one class and used
different colors to construct groups This figure shows one example for each of the 25 groups Groups with white bounding boxes the majority groups. See Appendix A.2.1 for more details.
Log(Number ber of Clusters)
102
101
10
10
30
40
Cluster Size
Figure 7: Distribution of cluster sizes, for Fig.
13

---

Under review as a conference paper at ICLR 2023
(a) CIFAR-10 images large clusters,
amples are similar to each other.
(b) CIFAR- 10 images in small clusters.
CIFAR-10 images sampled by our algo- rithm.
Figure 8: Images in large, and small subpopulations of CIFAR-10, subset used for OOD evaluation in Fig. 5d
14

---

Under review as a conference paper at ICLR 2023
75
97.25
average acc
porst-group
97.00
70
96.75
96.50
65
2.5
5.0
7.5
10.0
initial epoch numbert
2.5
5.0
7.5
10.0
initial epoch number t
(a) Average accuracy (%) initial epoch
(b) Worst-group accuracy (%) vs initial epoch number.
80
97.6
NO77 st 0 grou o acc
average acc
79
97.4
78
97.2
77
97.0
0.1n
0.2n
0.3n
0.4n
0.1n
0.2n
0.3n
0.4n
number of clusters
number of clusters
(c) Average accuracy (%) number of clusters.
(d) Worst group accuracy (%) vs number of clusters.
Figure Average and worst-group accuracy on Waterbirds dataset for different initial epoch number t (defined in Algorithm [ and different numbers of clusters.
Initial Epoch Number t (CIFAR-10)
94
T=1
T=2
Final Test Accuracy (%))
92
T=4
T=8
84
0.8
Fraction of Dataset Pruned
Figure 10: Test accuracy on CIFAR-10 dataset for different initial epoch number é (defined in Algo- rithm
15

---

Under review as a conference paper at ICLR 2023
Mutual Information
MFF Y)
I(F Large,
Accuracy
0.3
1[F Seleect,
I(F Y) -KFg Y Lin)
0.-
I(F, Large; Y) I0F; Y Lin)
I(F; Select; Y) I(P Y Lin)
-0.
Best Linear
08
0.5
SGD epochs
Figure 11: Mutual information between linear model trained on full CIFAR-IO and ResNet- 18 models trained on full or subsets of CIFAR-10. See the caption for Fig. and Section 4. for more details.
10a
cnn
resnet-18
10a
log(counts)
10'
101
10a
20
50
cluster size
Figure 12: Comparison of gradient trajectory clusters for 4-layer CNN ResNet-18.
101
(Count))
100
Full Select
10
15
20
25
Group Index
Figure 13: Number examples in different groups of CMNIST and examples subsampled with our algorithm. Each bar represent one group and the dashed lines separate the classes. Our algorithm effectively pruned the large groups.
16


Reviews:
[{"review_id": "qdwAb5ASqk", "reviewer": "Reviewer_d2Nd", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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 proposes a method to up weight the smaller sub-populations that are found by performing clustering of gradient trajectories. This method is improved upon Group-DRO, which automatically identifies groups and prevents overfitting on spurious correlations. In order to achieve that, they use the premise that spurious features are abundant in majority groups and large subpopulations with similar gradient trajectories can be identified based on their gradient trajectory during the first few epochs. Their main contribution is to introduce an automatic clustering process that identifies large groups with spurious features and eliminating these biases improves worst-case and OOD performance. The authors validates the effectiveness of their methods on crafted datasets (Waterbird and CMNIST) and general image classification datasets ( CIFAR and Caltech-256). Improvements are shown in both classification accuracy and Gradcam saliency.\n\n", "summary_of_the_review": "Overall, this paper could be a significant algorithmic contribution, with a few caveats for some clarifications on the theory and experiments. This algorithm can be applied to worst-case robustness, OOD generalization, and can be extended in general to the debiasing scenario. If these problems are sufficiently addressed in the rebuttal, I would lean to accept this paper. ", "strength_and_weaknesses": "Strength: \n1. An elegant solution for an important problem. DRO is intractable in deep learning and manually crafted groups are introduced to solve this problem. Automatic 1) selection of shared-feature groups, 2) identification of data with spurious features, and 3) debiasing has been an unsolved problem. This paper uses gradient-related statistics to identify majority groups and can inspire many future works in this area. \n\n2. The experiment results are competitive, especially for debiasing and OOD generalization.\n\nWeakness: \n1. The motivation has not been stated clearly enough. The authors in fact introduce three concepts \"long-tail\"->\"spurious features & debiasing\"->\"OOD & worst-case generalization\".  The link between majority group (long tail) and improved generalization is a bit weak and the author could better elucidate this connection. You may find these papers [1] [2] helpful on this subject. \n\n2. I'm confused by the motivation for using gradient trajectories to identify majority groups. \"In the initial training epochs, the network learns important features and the NTK undergoes rapid changes, which determine its final basin of convergence\" and \"As a result, the large subpopulations dictate the rapid initial change of the NTK and the prominent features learned in this phase\". The authors seem to be motivated by the dynamics of NTK for identifying majority groups. Therefore, I'm confused why they chose gradient trajectory rather than gram matrix trajectory as the indicator. \n\n3. Problem with Lemma 4.1 \n- I think the result is not specific to this particular choice of grouping based on gradient. Actually, it seems to be only affected by group size and this result is rather trivial as balanced groups would be less affected by reweighting. \n\n4. Experiments\n- ERM is a fairly weak baseline, and comparison with DRO and EL2N are missing in Table 1. \n- Gradient trajectories are instable and sensitive to hyperparameters. Sensitivity analysis and error bars are missing (CMNIST, Figure 5d). Also, a large variety of models should be chosen and analyzed, as different backbones have very different training dynamics.\n- Code and hyperparameters are not provided. \n \n[1] Ming Y, Yin H, Li Y. On the impact of spurious correlation for out-of-distribution detection[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2022, 36(9): 10051-10059.\n\n[2] Tang, Kaihua, et al. \"Invariant feature learning for generalized long-tailed classification.\" arXiv preprint arXiv:2207.09504 (2022).", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ma_7Q5gYMJJ", "reviewer": "Reviewer_gnhj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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 address the problem that, in a dataset, examples within classes can be grouped into subpopulations that are similar to each other, and this influences the dynamics. They propose an intuitive solution, which does not require previous knowledge on the subpopulations. This solution consists of looking at the gradients related to the single during the initial stages of learning. These gradients are expected to be similar for elements belonging to a single subpopulation, and this allows to identify them through a simple clustering algorithm. The authors test the method on two tasks: worst-group generalization in datasets with spurious correlations, and out-of-distribution generalization under distribution shift. They find promising results in their experiments.\n\n", "summary_of_the_review": "I like the idea underlying the main message of the paper, i.e. separating the examples in subpopulations through the gradients in the first stages of learning, and would be happy to see it published at some point. However, in my view, the current elaboration and presentation do not meet the standards of ICLR. I am open to increase my evaluation if my principal concerns in the Weaknesses and Reproducibility sections are addressed in a convincing manner.\n\n\n---------------------------------\n\nAfter rebuttal:\n\nIn summary, I  think that the paper has some interesting information, and I appreciate that some of my points were addressed directly, many of which I believe improve the quality of the paper. I changed the evaluation to 6.\n\n---------------------------------\n\nAfter second round of comments:\n\nAll my comments were addressed seriously. I cannot see a new version of the manuscripts, but given the thoroughness of their replies in the forum I have little doubt that the last version will be good. I changed the evaluation to a 7 (I've left a 6 because openreview does not allow for 7).\n\n\n\n\n", "strength_and_weaknesses": "Strengths:\n- The idea of selecting subpopulations based on the gradients during the initial phase of learning is a very nice effective way of understanding data. This could even be expanded to make static studies of datasets.\n- The proposed method seems to outperform previous similar methods\n\nWeaknesses (and further open questions that could/should be addressed in the paper):\n1) The argument of section 4.1 leverages on an intuition provided by Nakkiran 2019, the knowledge that minority examples are learned later (which is known, see e.g. arXiv:2104.01769 and arXiv:2207.00391), and the empirical evidence provided in Fig.2. This evidence is provided for a single architecture on a single data set, which is clearly too little to make a general claim.\n2) The paper contains mainly empirical results, but the results in section 4 are shown only with a single model.\n3) The results in section 5.1 are obtained on one single model and simple datasets. Why not use e.g. the superclasses of cifar-100, with the single classes representing the single populations? In that case there would be no explicitly-imposed spurious correlation, but they can be implicit (i.e. not imposed by hand) and in any case I don't fully understand the need of imposing clear sources of spurious correlations to validate the algorithm (beyond that they allow to show in fig4 that some times spurious correlations are avoided). If the algorithm is meant to help in generic application cases, then I would assume that its efficacy would be visible for any data set, and not only very specific ones, right?\n4) There is no analysis of the obtained subpopulation clusters. It is not clear whether the result of the clustering depends on the specific choice of architecture and HyperParameters. Do I obtain the same populations if I change architecture or hyperparameters? Are these found subpopulations actually significant? Analyzing them could confirm whether the arguments leading to the method are correct, or if different explanations should be sought.\n5) As I understand from Alg.1 (this was not too clear to me from the main text), the subpopulations are collected in an initial dummy run that lasts t steps. How is t chosen and how do the clusters/performances change with t?\n6) The authors select given examples with a probability p_i which depends on the subpopulation [page 6]. What would happen if they didn't use these weights for selection, but rather for reweighting of the single examples?\n7) Relatedly, the suggested recipe essentially consists in downsampling the dataset in a smart way, and using a subset S of data instead of the full dataset. One could instead use the probabilities p_i to select the minibatches, and assign examples to a batch depending on p_i. I assume that this would have the same effect as downsampling the dataset, but with the advantage that no example is completely discarded, right?\n8) The arguments given by the authors focus on the initial linear model that is created in the first steps of the dynamics. Does this mean that algorithm 1 is not necessary after the beginning of the dynamics?\n9) In Fig.3 it is shown that the norms of the examples belonging to the largest clusters are smaller. Going further, shouldn't one be looking for each cluster to have the same total norm (i.e. GradNorm*ClusterSize=constant)?\n10) Section 5: why are there no error bars for CMNIST?\n11) Section 5.1: how do the clusters found through the authors' method overlap with the real clusters?\n12) The following statement is not supported by the experiments and should be restated: \"training on the subset selected by our method gives much higher in-distribution test accuracy than Random, and EL2N or forgetting scores particularly when the subset is small\". I would rather say that for high pruning -when the subset is small- this is true (though the adjective \"high\" is arbitrary: I would rather say that this is \"consistent\" or \"systematic\" through datasets). For low pruning this is not even true.\nFurthermore, the x axes of figures 5a and 5c are skipping the 0.4 point, giving more visual importance to the highly-pruned runs (where the authors' method outperforms the others) than they actually should have. I hope this was not intentionally done to give a false perception of the results.\n13) From Figure 5, I see that using the whole dataset is still better than using a subset. Therefore, it would seem that the title (\"When majorities prevent learning\") is misleading, since keeping the majorities is still good.\n14) Beyond the metrics used in table 1, why is the bare accuracy or macro-F1score not reported? As a reader I would be interested in knowing how the authors' method compares to a vanilla training as far as the traditional metrics are concerned. If \"majorities prevent learning\", do I get an advantage on the global by removing these majorities? Do I lose something? How much? I think these questions should be addressed.\n\n\n", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "cxIsaGWd3J", "reviewer": "Reviewer_BcrE", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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 studies the problem of (in-distribution) generalization when facing potential subgroups / subpopulations in the training data, without knowing the group annotations. The paper claims that tracking gradient trajectories of examples in initial epochs allows for finding large subpopulations of data points. It also proposes an importance sampling method that is biased towards selecting smaller subpopulations, which is claimed to eliminate bias in the large subpopulations. Experiments on several datasets show that the method might be effective over several baselines in both in-distribution or out-of-distribution generalization.", "summary_of_the_review": "The paper studies an interesting yet important problem, model generalization when facing potential subgroups / subpopulations in the training data without knowing the group annotations.\n\nThe overall idea of leveraging gradient trajectory for subgroup discovery and robustness seems to be novel and not explored before in this field, which is plausible.\n\nHowever, currently there are many drawbacks and weaknesses, in terms of Motivation, Methods, Related work, and Exepriments. The writing quality  is bad and needs to be significantly improved.\n\nIn summary, I recommend rejection.", "strength_and_weaknesses": "# Strengths\n+ The idea of leveraging gradient trajectory for subgroup discovery and robustness seems to be novel and not explored before in this field.\n\n\n\n---\n# Weaknesses\nUnfortunately, there are multiple major weaknesses exist in the current paper.\n\n### Motivation\n- I do not buy the motivation argument that \"_large subpopulations are responsible for forming the initial linear model_\".\n1. Specifically, the descriptions in Section 4.1 are messy and unclear, sometimes even not readable (see comments later in \"Writing\"). First, _mutual information_ is never formally defined or described in the text, but appears in Figure 2 -- how do you compute (or estimate) the mutual information? Is the computation the same across methods?\n2. How do you obtain \"large subpopulation\" in this toy example? What is \"large subpopulation\" and how is it defined w.r.t. CIFAR dataset?\n3. Does this observation persist across different datasets and different network architectures? The authors used a 4-layer CNN -- again, the detailed architecture is not explained, and the rationale behind using this architecture is not justified (why not using a standard ResNet-18?). The obseravation could be easily driven by the fact that the capacity of the network is limited. That being said, different datasets and/or architectures might directly influence the observation, and more justifications are needed; otherwise it is not convincing.\n\n- Related to the point above, Figure 2 in Section 4.1 is not understandable. There's no text describing the figure. Fig 2b is completely missing in the text, rather the authors refer to Figure 6 in the last paragraph of Section 4.1, which is a label distribution figure in Appendix.\n\n\n### Method\n-  For the importance sampling method, why directly use the inverse of the size of the subpopulation? Samples and subpopulations could have hierarchy and semantic similarities. Past works also show square-root inverse weighting can be empirially better than inverse weighting. Please explain the rationale, either theoretically or empirically, that this leads to better outcomes than other heuristic approaches (e.g., square-root inverse weighting).\n\n\n### Related work\n- The related work is somehow misleading and not comprehensive. The authors discuss only \"Data pruning\" oriented methods, either for in-distribution (avg / worst) or out-of-distribution generalization. However, the real theme of the paper is how to **improve sub-group robustness without training group information**, and this very related line of works is rather totally missing. To name a few methods along this direction (improving worst-group accuracy without group annotations): [1]-[5].\n\n- (also weaknesses in experiments) As stated above, the line of work on worst-group accuracy **without** group annotations should also be compared in the experiments to show what advantage this paper brings, and to properly position this paper in the literature.\n\n\n### Experiments\n- As detailed in the \"Related work\" part, a major drawback of the paper is that it fails to compare with the actual line of works that is mostly related, i.e., improving worst-group accuracy without group annotations [1]-[5]. Without comparing to strong baselines as [1]-[5], the performance is not justifiable or convincing.\n- Moreover, for \"out-of-distribution generalization\" part, the paper also failed to compare with SOTA domain generlization (DG) approaches, including [6, 7] as well as those competitive methods in the DomainBed benchmarks [8]. Again, the selected baselines are no longer SOTA, and without comparing to the aforementioned strong baselines, the results are not convincing.\n- Related to the questions above, I wonder why not the authors directly test on the DomainBed benchmark. Directly testing on DG benchmarks [7] would be the most reasonable choice to fairly evaluate the proposed method to other algorithms in DomainBed.\n- The choice of **first several epochs** for gradient trajectories seems to be an important hyper-parameter for the method. However, the number in the experiments seems to be rather randomly chosen; there are also no ablation studies on the number of epochs, or how does the number affect the performance.\n- Related to the questions above, there are no ablation studies on the \"inverse importance sampling\" part. Whether this is necessary, or it is better than other heuristic approaches (e.g., square-root inverse weighting), is completely missing.\n- The \"gradient trajectory\" idea is plausible, but also introduces potentially high computational costs. For example, ERM does not need any tracking or storing intermediate variables. Although the authors claim in the paper that the method can be implemented efficiently, I would like to see the actual computational cost w.r.t. time and memory costs. Wall-clock training time comparison as well as memory consumption to other baseline methods would be good.\n- Despite of mentioning \"large subpopulation\" in the methods, the results never show what is the actual \"large subpopulation\" the model discovers, and how meaningful it is.\n\n\n### Writing\n- The overall writing quality is bad. The writing needs to be significantly improved.\n- For example, last paragraph in page 4 is not even self-contained or readable. The first sentence in this paragraph is not grammarly correct. Moreover, \"Fig. 6\" mentioned in the text refers to a figure in the Appendix showing the label distribution, but has nothing to do with the texts here.\n- typo: line 4 page 4 - $y_f(w,x_i)$\n\n## References\n[1] Liu et al. Just Train Twice: Improving Group Robustness without Training Group Information. ICML 2021.\n\n[2] Zhang et al. Correct-N-Contrast: A Contrastive Approach for Improving Robustness to Spurious Correlations. ICML 2022.\n\n[3] Nam et al. Spread spurious attribute: Improving worst-group accuracy with spurious attribute estimation. ICLR 2022.\n\n[4] Lahoti et al. Fairness without Demographics through Adversarially Reweighted Learning. NeurIPS 2020.\n\n[5] Creager et al. Environment Inference for Invariant Learning. ICML 2021.\n\n[6] Cha et al. SWAD: Domain Generalization by Seeking Flat Minima. 2021.\n\n[7] Arpit et al. Ensemble of averages: Improving model selection and boosting performance in domain generalization. 2021.\n\n[8] Gulrajani et al. In search of lost domain generalization. 2021.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "NxqgLJ1Nx1", "reviewer": "Reviewer_nnQ5", "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": "Good generalization performance of DL could be attributed to the undesirable overfitting spurious biases in large datasets. This apper proposed a way to conduct smart sub-sampling by tracing the gradient trajectories of initial examples. An importance sampling algorithm is then proposed to conduct sub-sampling.", "summary_of_the_review": "I would like to see the rebuttal of this paper and reconsider my standpoint, but currently, I incline to reject as is, unless a better explanation and validation of the gradient tracking technique is added. ", "strength_and_weaknesses": "Strength: overall very well written paper with strong and clear motivation.\n\nWeakness: my concern is primarily on the technical side. \n\nTractable toy examples: While the high-level idea of tracking gradient seems to make sense, the introduction of clustering and dimensionality reduction inevitably introduce a lot of approximation errors into the process. The authors conducted experiments mainly w.r.t CIFAR cases, but it would that make more sense to design some analytical examples to demonstrate the effectiveness of this work, where things stay low-dimensional to begin with. \n\nImportance sampling: the choice of inverse weight seems a bit arbitrary. Have the authors considered an ablation study on the different choices of IS proposals?\n\nImproving the implementations: I don't think ERM is the SOTA baseline to compare with, as it is known to have sub-par performance. In addition, the authors might want to conduct more ablation studies w.r.t. the gradient tracking, as some of the techniques adopted are quite sensitive to seed initialization (the k-means clustering, for example).", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject