Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strength: overall very well written paper with strong and clear motivation.

Weakness: my concern is primarily on the technical side. 

Tractable 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. 

Importance sampling: the choice of inverse weight seems a bit arbitrary. Have the authors considered an ablation study on the different choices of IS proposals?

Improving 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).
clarity,_quality,_novelty_and_reproducibility: The Clarity, Quality and Novelty of this paper could be improved. I consider the Reproducibility to be fair as no code has been provided yet.  
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.


strength_and_weaknesses: Strength: 
1. 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. 

2. The experiment results are competitive, especially for debiasing and OOD generalization.

Weakness: 
1. 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. 

2. 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. 

3. Problem with Lemma 4.1 
- 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. 

4. Experiments
- ERM is a fairly weak baseline, and comparison with DRO and EL2N are missing in Table 1. 
- 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.
- Code and hyperparameters are not provided. 
 
[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.

[2] Tang, Kaihua, et al. "Invariant feature learning for generalized long-tailed classification." arXiv preprint arXiv:2207.09504 (2022).
clarity,_quality,_novelty_and_reproducibility: Clarity: The writing is easy to understand, but there are many typos. 
Novelty: It seems quite novel to me using gradients for identifying biased groups. 
Reproducibility: Code and hyperparameters are not provided. 
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.


strength_and_weaknesses: Strengths:
- 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.
- The proposed method seems to outperform previous similar methods

Weaknesses (and further open questions that could/should be addressed in the paper):
1) 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.
2) The paper contains mainly empirical results, but the results in section 4 are shown only with a single model.
3) 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?
4) 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.
5) 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?
6) 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?
7) 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?
8) 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?
9) 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)?
10) Section 5: why are there no error bars for CMNIST?
11) Section 5.1: how do the clusters found through the authors' method overlap with the real clusters?
12) 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.
Furthermore, 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.
13) 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.
14) 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.



clarity,_quality,_novelty_and_reproducibility: 
Clarity:

x) The language is ok. 

x) The structure and flow are ok.

x) I would suggest a more intuitive color code (or line style) in Fig.2, relating the couples of runs with the same data.

x) Label sizes in figure 5 are too small

x) The topic of the spurious correlations is brought up for some hand-waving arguments and for justifying some experiments, but those are never actually used for any theory, so I don't see the need of defining the attributes $a_i$.

x) The appendix lacks text describing the figures.

x) The description of Fig.6 in page 4 is confusing. I am not even sure that Figure 6 has the content that is being described.

x) There are many typos in the text, I suggest a careful rereading. Here are some examples:
- forgettabiliy
- Spurious features has been
- neural network experience
- When an exampleS is learned
- and has been used [should be "have"]
- for every exampleS
- we independently generateS
- and dropS many examples
- Subset found by our method allow
- in-distribution. and out-of-distribution

Quality:

The paper is based on an idea that I find nice, but I feel that the paper could have developed and explored it more in depth.


Novelty:

The main message of the paper is a recipe to identify subpopulations within each class, and to exploit this knowledge for better training. As far as I know, this is novel.

Reproducibility:

- The code is not provided, hyperparameter tuning is not explained (nor is it stated how the HPs related to the authors' method should be chosen or how they influence the performance) and the details of the models are not given.
- I don't fully understand how the out of distribution experiments were brought through.


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.


---------------------------------

After rebuttal:

In 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.

---------------------------------

After second round of comments:

All 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).
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
strength_and_weaknesses: # Strengths
+ The idea of leveraging gradient trajectory for subgroup discovery and robustness seems to be novel and not explored before in this field.



---
# Weaknesses
Unfortunately, there are multiple major weaknesses exist in the current paper.

### Motivation
- I do not buy the motivation argument that "_large subpopulations are responsible for forming the initial linear model_".
1. 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?
2. How do you obtain "large subpopulation" in this toy example? What is "large subpopulation" and how is it defined w.r.t. CIFAR dataset?
3. 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.

- 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.


### Method
-  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).


### Related work
- 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].

- (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.


### Experiments
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.


### Writing
- The overall writing quality is bad. The writing needs to be significantly improved.
- 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.
- typo: line 4 page 4 - $y_f(w,x_i)$

## References
[1] Liu et al. Just Train Twice: Improving Group Robustness without Training Group Information. ICML 2021.

[2] Zhang et al. Correct-N-Contrast: A Contrastive Approach for Improving Robustness to Spurious Correlations. ICML 2022.

[3] Nam et al. Spread spurious attribute: Improving worst-group accuracy with spurious attribute estimation. ICLR 2022.

[4] Lahoti et al. Fairness without Demographics through Adversarially Reweighted Learning. NeurIPS 2020.

[5] Creager et al. Environment Inference for Invariant Learning. ICML 2021.

[6] Cha et al. SWAD: Domain Generalization by Seeking Flat Minima. 2021.

[7] Arpit et al. Ensemble of averages: Improving model selection and boosting performance in domain generalization. 2021.

[8] Gulrajani et al. In search of lost domain generalization. 2021.
clarity,_quality,_novelty_and_reproducibility: ### Clarity
Bad.

The descriptions in Section 4.1 (motivation part) 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?

The overall writing quality is bad. The writing needs to be significantly improved.

Please refer to the weaknesses part for a complete review.


### Quality
Not good for the current manuscript.

There are major weaknesses in Motivation, Methods, Related work, and Exepriments.

Please refer to the weaknesses part for a complete review.


### Novelty
Fair.

I understand that the idea of leveraging gradient trajectory for subgroup discovery and robustness seems to be novel and not explored before in this field. However, the literature review is pretty limited, and it seems that the paper is not well positioned w.r.t. the literature.


### Reproducibility
Fair.

No code is provided along with the submission. The pseudo code is provided for the algorithm.
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.

The 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.

However, 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.

In summary, I recommend rejection.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper aims to improve worst-group performance and out-of-distribution generalization, and builds upon the group-DRO framework. The conjecture is that large (majority) subpopulations can be identified based on gradient trajectory during the first few epochs. The paper performs clustering of similar gradient trajectories to identify these large subgroups and subsample them to rebalance the dataset, and to improve worst-case and OOD performance. 

While acknowledging that the proposed model is potentially useful, the reviewers have provided detailed comments and raised many concerns -- see weakness sections of all reviewers, especially Reviewer gnhj, Reviewer BcrE. Most critical are related to 1) empirical evaluations that are required to assess the scope and significance of this work contributions, including strong baselines, and 2) writing and presentation clarity of the paper. Extensive rebuttal convinced one of four reviewers to vote for acceptance. The reviewer acknowledged, however, that they haven’t seen a revised version of the manuscript. The manuscript will further benefit from an extended related work that highlights similarity and differences when benchmarking ODD approaches to clarify any confusions. 
AC decides that albeit it’s an important study, the manuscript will require too many revisions to be prepared and verified at this stage, and will benefit from another round of reviews. We hope the reviews are useful to improve the manuscript.
justification_for_why_not_higher_score: Three out of four reviewers raised many concerns that need to be addressed and passed through another round of reviews.
Decision: Reject