Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper focuses on the problem of identifying bad training data when the underlying cause is unknown in advance. Authors develop an algorithmic framework, DATASIFTER, for general robustness to bad training data. Empirical evaluation show efficacy of DATASIFTER in a wide range of tasks, including backdoor, poison, noisy/mislabel data detection, data summarization, and data debiasing
main_review: Overall the paper is clearly written and presents a novel framework to identify bad training data. Empirical results and comparison with baselines look interesting. 

However, I have the following concerns with the work: 

-  Proposed method (as described in Section 5) is based on a set learning phase where the task is the following: Given a training set, the aim is to learn how an underlying model when trained on that training set will generalize to unseen data from the same distribution. Their method DATASIFTER crucially depends on this step. However, this set learning problem is in general underspecified and hence hard to tackle. At a high level, to perform well on this task, the set functional learning architecture would not only need to mimic the underlying model trained on some training set (without actually using that model) but would also need to understand how the underlying model generalizes. The authors present no empirical evidence their algorithm solves this task in a reasonable manner.  Some empirical results showing correlations would be interesting to see. 

- Models considered in the work are small in size as compared to the state-of-the-art models. Is there any specific reason for this? 
summary_of_the_review: The proposed framework of DATASIFTER is interesting and novel with promising results. However, the method primarily depends on a set selection phase for which no empirical/theoretical evidence is provided.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes, *DataSifter*, an optimization-based, general-purpose framework for filtering "bad data" from a training set.  General-purpose broadly covers different data corruption types (e.g., adversarial perturbation, label noise, etc.), different model architectures, and performance metrics (e.g., test error).
main_review: Overall, I enjoyed reading the paper.  It was well-structured, easy to follow, and presented ideas clearly.  Nonetheless, it is my view that the paper still needs more work in particular around the experimental evaluation.

**Strengths**: 

1) The idea of training empirical estimator $\hat{U}$ is simple (a strength) and nice.  

2) Most recently published methods too narrowly target specific forms of “bad data”, specific learning domains (e.g., vision), specific model types, or even specific adversarial attacks.  More work needs to be directed towards agnostic robustness, which the authors do here.  Such general-purpose methods are generally harder to achieve (both theoretically and empirically) and are more useful in practice.

3) Your empirical evaluation includes an impressively large number of baselines.  This level of thoroughness is commendable. 

**Weaknesses**: 

1) The proposed methodology relies on utility metrics displaying "'approximate' submodularity."  Intuitively such submodularity is very plausible.  However, more detail is needed.  A more quantitative understanding/definition of what constitutes "approximate" would be appreciated.  Similarly, reading the first paragraph of Sec. 5 seems to imply that while many potential applications exhibit "'approximate' submodularity", others do not. Even if it only appears in the supplement, expanding this discussion so a potential reader knows when DataSifter applies (and more importantly when it does not) is important.  It is also unclear how the submodularity approximation affects DataSifter’s practical worst case performance.

2) Beyond the number of baselines, I have concerns about other aspects of your experimental design.

* I would have appreciated seeing empirically how well $\hat{U}$ performs in practice (e.g., a correlation plot between predicted and actual subset utility perhaps across different size subsets).  This could be in the supplement.

* Reviewing your supplemental materials, most of the models you consider are small in size (please correct me if I am wrong).  Do you have any analysis on large models -- e.g., SOTA, modern transformers?  Even if numerical values cannot be included now, can you anecdotally speak to how well your method has performed on such models (both in terms of execution time and numerical performance)?

* Mislabeling Detection (6.2.1.IV) - It seems that DataSifter underperforms some Shapley Value-based methods for moderately sized datasets.  I did not find the explanation around small amounts of data not affecting validation accuracy very strong.  While in absolute terms, the change in accuracy is small, the relative change in error rate seems large.  Perhaps I am missing something.

* For the experiments, I would have preferred a table in the supplemental materials that summarized the various dataset sizes, attack set sizes, perturbation distances etc.  It was time consuming to piece that various information together from reading the individual paragraphs.

* If I understood Sec. 6.2.1 and suppl. Sec. E.5.2 correctly, the backdoor experiments used a poisoning rate of 20%-25%, which is high and somewhat unrealistic in practice.  Also, by having a high poisoning rate, influence based methods generally will perform poorly since the effect of the attack is diffused over all the attack samples.  How does your method perform with much smaller poisoning rates?

* Methods like TracIn and Influence Functions consider a specific target example.  Are the attack success rate values w.r.t. to the specified target or any backdoored sample?  How was the target selected?
 
* In suppl. Section E.3, your proposed model for CIFAR10 has two convolutional layers and three fully-connected layers.  This seems a peculiar choice for CIFAR10 classification and probably would not perform well on larger dataset sizes.

* Section E.5.8 mentions that Influence Functions (i.e., LOO) took >24 hours on a small CNN model.  Having worked with influence functions before, including the source implementation you cite, this seems quite high.

* For TracIn, sampling every 15 epochs seems too sparse -- especially if you are training only 30 epochs and seems more akin to TracInCp than TracIn -- correct me if I misunderstood.  Also, reviewing Pruthi et al. again, using only the last linear layer is a speed-up due to limitations with Influence Functions.  Did you compare to TracIn using all layers as well?

    * Further to this end, it would be helpful if you had a table of the hyperparameters for the various methods (e.g., influence functions) to determine how the corresponding baseline hyperparameters were set.  That would allow me to better evaluate your setup.

* Since you are considering groups of points, perhaps second-order influence methods that directly consider group effects would have been a better baseline choice.  See for example: Basu et al. 2021 “On Second-Order Group Influence Functions for Black-Box Predictions” or Koh et al. 2019 “On the Accuracy of Influence Functions for Measuring Group Effects”.  If these baselines do not work, please provide more of an explanation why.

**Questions**

1) I assume $\mathcal{A}$ can be stochastic (e.g., in initial parameters, batch sequence, underlying implementation like CUDA).  Should Objective (1) then be the expected utility over randomization?  If Objective (1) is shown as deterministic for simplicity, that should be stated.

2) Did you observe randomization having any effect on $\hat{U}$’s performance (e.g., restarting analysis leading to meaningfully different utility predictions)?  As mentioned above, I did not see any ablation-like analysis of just this component of the method.

3) Do any alternatives exist to DeepSets (Zaheer et al 2017), and if so why did you select DeepSets over alternatives?

**General Points**

* In the abstract, you specify a “key insight”, but I was unsure of its intended meaning. It seemed like the most likely meaning was that the “bad data” does not contribute much (if anything) to a model’s corresponding performance metric(s).  This feels like an elementary insight so I think I may have missed your intended idea.

* You use the term “general robustness” in the introduction’s first paragraph.  When I read it, I was not sure exactly what you intended (it does becomes clear later).  General robustness is a clear strength of your method so being explicit on this definition earlier may be more impactful to a reader.

* A reference that seems related to your work is Feldman & Zhang from NeurIPS’20.

* I think your claims of general robustness would be significantly strengthened if you had more empirical evaluation on NLP data.  SPAM is used but the bag of words representation is somewhat simple and outdated.

* There is a good number of typographical errors in the main text.

summary_of_the_review: Promising paper with clear ideas.  I have concerns in particular around the evaluation as detailed above.  Author response is important for my setting of the final score.

Edit: The authors provided thoughtful detailed reviews and addressed many of my concerns.  Their responsiveness and turnaround time on feedback was quite remarkable and duly noticed.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors study the problem of data selection in the presence of bad training data by maximizing the utility function $U$ over all subsets of cardinality $k$. The authors first show that the valuation based approaches can have bad performances, and propose the DataSifter algorithm to approximately solve the combinatorial optimization problem.
main_review: The paper is well-written and easy to follow. The problem of identifying harmful or bad training data is interesting and important in dataset creation and cleaning. The theory for worst case performances of valuation based approaches is motivating but it doesn't necessarily imply the method will fail as it's only a worst case analysis. The other drawback is that the DataSifter algorithm is highly empirical with no theoretical support. Some detailed comments are made as follows.

1. The counterexamples in Theorem 1 to 3 are highly constructive in $U$ and might not reflect actual performances of linear heuristics on real datasets. Especially if the utility function has certain structure and cannot be defined arbitrarily. The experiment in E.5.1 uses SVM as utility metric which as a special instance can be much better than the worst-case performance bound (and the same is also true for a wider range of utility functions used in practice). I would like results more with additional constraints on the utility function or lower bounds for a particular class of utility functions used in practice.
2. The paper shows good empirical performance of the DataSifter algorithm in certain identification tasks. It seems a bit unrelated to the first part of the paper as the good performance for some datasets doesn't imply a higher worst-case lower bound. A more reasonable comparison is to either provide a better worst-case lower bound for DataSifter (maybe under assumptions like exact recovery $\widehat{U} = U$) or as pointed out in my first point to give instance-specific performance upper bound for the valuation-based approaches.

In all, I think the paper gives some interesting empirical results but the theory doesn't exactly corroborate the main argument that we should prefer DataSifter over coventional heuristics. I incline to reject the paper.
summary_of_the_review: The paper provides worst-case analysis of data selection using linear heuristics, revealing potentially hazards using valuation-based approaches, which is interesting and novel. However, it doesn't exactly corroborate the main argument that we should prefer DataSifter over coventional heuristics.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this work, the authors:

1. shows that linear heuristic like Shapley value based methods do no perform well w.r.t worst case performance in selecting the best subset of data. 

2. develops an algorithmic framework based on utility optimization approach to achieve robust ness against general \textit{bad} data
main_review: \textbf{Strength:}

1. This paper suggests an algorithmic framework based on utility optimization approach to achieve robustness against general bad data. The method performs well empirically. 

2. Theoretically shows that Shapley value based methods has small domination ratio.

\textbf{Weakness:}

1. Regarding Theorem 3: "...even if the data utility function U is submodular"  Bad worst case performance could be due to restricting U to be submodular. What happens if U is not submodular? I disagress with the choice of words "even if". In my opinion it should read "...when the data utility function U is submodular."

2. It should be highlighted clearly in the main paper (not in appendix) that the better empirical performance is for a specific choice of utility function $u$, ,e.g., average accuracy in debiasing. Since choice of utility function is the most important part of detecting bad data, and the supremacy of one method over the other may not hold for a different utility function. 

3. The authors criticize linear heuristic methods showing that worst case domination ratio of the methods are small. But there is no theoretical analysis of DataSifter. It performs only empirically better, and since the experiments are done for a specific choice of utility function, nothing can be said about its worst case performance, and it could as well be as small as linear heuristics. 

4. The DeepSets approach to utility optimization has been introduced by Wang et.al. 2021a (as the authors agree) and this method itself is not a novel contribution of this work (including the label information does not contribute anything new to the idea). 

\textbf{Minor issues:}

1. On page 2: "Guided by goals of downstream..." It is not clear to me what this line means. 

2. Line 7, page 5: adds ----> add
summary_of_the_review: My decision is borderline accept for this paper only because of empirical success in some specific examples and theoretical results on the domination ratio of Shapley value based methods. Although, I should mention this paper has considerable weakness. Depending on discussion with other reviewers I may increase/decrease my score.
review_title: null

Meta-review: The paper considers the question of identifying bad data so that models can be trained on the subset of data that is good. This question is formulated as a utility optimization problem. The paper shows that some popular heuristics are quite bad in the framework they propose. They also propose a new algorithmic framework called DataSifter. There is empirical evaluation provided for this. Questions have been raised in the reviews about the size of the models that have been used in the empirical evaluation. The authors have responded to this by suggesting the use of proxy model techniques. There are also questions about learnability of data utility for which some responses are provided in the rebuttal.
Decision: Reject