Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: - The authors tried to tackle a fundamental problem, data valuation.
- Most previous works need model training for quantifying the values of the samples (which is computationally inefficient); however, the proposed method does not need model training.
- The authors provided various experimental results that show the superiority and usefulness of the proposed data valuation in multiple datasets (including CIFAR-10)
strength_and_weaknesses: Strength:
- The proposed method is computationally much more efficient than alternatives.
- Still, the proposed method shows competitive empirical results in comparison to alternatives.
- The proposed method is well supported with the theoretical analyses.

Weakness:
- It is unclear whether the data value can be "independent" of the model.
- In some experimental results, the proposed method shows somewhat consistently worse performance.
- It would be good if the authors can provide empirical advantages of computational complexity.
clarity,_quality,_novelty_and_reproducibility: - The paper itself is well written and easy to follow.
- The proposed method is somewhat heavily based on the previous work (Arora et al., 2019) but applied to the new problem. Thus, the novelty is somewhat marginal.
summary_of_the_review: 1. Generalization
- In this paper, the proposed method is highly dependent on two-layer overparameterized MLP. (H in Equation (2))
- In that case, can we say that this score is generalized to more general neural networks? Or, can we say this score is generalized to simpler models such as linear models?
- Can we also generalize this method for a regression problem?

2. Connection between data value and model
- The value of the data can be different across different models.
- For instance, the value of the sample with a linear model can be different with a non-linear model.
- In that case, how can the proposed method quantify the value of the data depending on the models?
- The author said that this model is independent of the model but I am not sure in general whether data value can be independent of the model.

3. Experiments
- The experimental results are interesting. 
- Especially, the authors show consistent improvements for noisy label finding.
- It would be interesting if the authors can provide the results with a higher noisy ratio (like even higher than 50%) to check the robustness of the model.

4. Figure 2
- For pruning lower value samples, the proposed method shows somewhat consistently worse performance than alternatives.
- Is there any intuition that the proposed method does not do well for discovering lower value samples? Especially with a smaller training data portion?
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose a new data instance valuation metric (CG score) - for scoring the how impactful a particular training instance would be on training a neural net.  This can be viewed in terms of how difficult of an example it is to learn and how much it effects generalization, etc.  This metric does not require actually training any neural net (for any number of steps), unlike much previous work on the topic.  The approach is based on a generalization error bound for 1-hidden-layer neural networks (under a number of simplifying assumptions) - in particular, measuring the change in this bound if a particular data instance is excluded from the training set.  They develop a succinct and computational efficient method to compute this change for each data instance.

They propose using such a metric for data pruning before training - to reduce the size of the data set used / needed for training a network, and for identifying mislabeled data points - and validate this with analyses and experiments.  They also demonstrate it could identify those data instances that are harder to learn - which suggests it could also be useful for something like curriculum learning.

strength_and_weaknesses: 
Strengths:
1) The approach is interesting (and thought-provoking) and soundly developed.  It is not purely a trivial application of the prior developed error bound as a lot of thought went into how to apply it and efficiently compute it, and a lot of analyses to understand what is doing and measuring, and how it relates to other metrics.

2) Compared to recent past work analyzing data importance from neural net training it has clear advantage in not requiring training any neural network.  

3) Thorough and varied experiments are provided to illustrate the properties of the metric.

4) The paper is well written and organized.


Weaknesses:

1) I feel perhaps the biggest weakness is lack of mention and comparison to prior work targeting the particular problems this metric is proposed to be applied to - selecting a subset of data for more efficient training, and finding mislabeled training data.

In particular - a major motivation of the approach was to "dataset pruning" - which is essentially using the score per data instance to select a subset of data points for training, e.g., in order to enable fast / less expensive training on just a subset of the data.  The paper is a bit misleading in stating it is the only approach to doing this that doesn't require training a neural network first - as in general this is an area of research with a long history, and there are many methods that have been developed to select a subset of the data for training that don't all require fitting a particular predictive model to it first.  It would be best to mention these methods, why this proposed approach may have some advantage, if any, and also include some of these in the experiment results.  In particular - would I use this proposed metric, or one existing approach to identifying a subset of the data to use for training?  What are the advantages and disadvantages of each?  Additionally there are many other alternatives to accelerating machine learning training such as data sketches - not just selecting a subset of data, but summarizing the data in some way first (perhaps even with random features) to speedup training using a smaller transformed set of data.

Some examples of papers in this area:
- "Coresets for Data-efficient Training of Machine Learning Models" Mirzasoleiman et al.
- "Subset Selection in Machine Learning: Theory, Applications, and Hands On" (tutorial) Iyer et al.
- "Training Data Subset Selection for Regression With Controlled Generalization Error" Sivasubramanian et al.
- "Introduction to Core-sets: an Updated Survey" Feldman
- "GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning" Killamsetty et al.
- "Finding High-Value Training Data Subset through Differentiable Convex Programming" Das et al.
- "Oblivious Sketching for Logistic Regression" Munteanu et al.

The same also goes for handling label error or detecting which data instances are mislabeled - again there is a large body of related work in this area not mentioned or compared to.  E.g.:
- "An instance level analysis of data complexity" Smith et al.
- "Identifying mislabeled training data." Brodley et al.

I found myself wondering throughout, how this work sits compared to these other approaches.  Overall it may be this is more of an analyses of a particular metric derived from a bound - so may not be claiming to be better than other approaches for each problem, but in order to have a complete and thoroughly useful analysis, it would be helpful to know how it compares.

2) The original bound and the corresponding proposed metric is based on a single hidden layer MLP relu neural net - with a lot of further restricting assumptions such as on the data and weights, and also with only the hidden layer parameters being trained in the process.  The analyses of the proposed metric also make various other assumptions, of varying strength.  It would be helpful to see more experiments and analyses to understand how the proposed approach performance changes as these assumptions are violated - especially since the datasets and variations used with them were limited (just 3 datasets with no exploration of varying model types, for example).  

It would also be helpful for some discussion around what it would mean for the metric with changing neural net architecture or assumptions - how would it diverge, what would a good metric change in these cases, etc.

I.e., what about different kinds of nets, e.g., more complicated (like transformer / self-attention), or with different form (e.g., different types of convolution or RNN) or activation, or with more layers?  The intrinsic biases the different network configurations and architectures correspond encode would seem to suggest different metrics might be better suited to different architectures - so what kind of universality does the proposed metric have?

3) The two objectives / proposed uses for the proposed metric seem at odds and hard to reconcile. The proposed metric simultaneously is higher if a training example is necessary for good generalization (e.g., close to the decision boundary), but also higher if the training example is mislabeled.  It's being used for both things but both would require the user to take opposite actions - if the data instance has a high score and if we assume it is an important training instance we want to keep it in the training data over other instances.  On the other hand if the data instance has a high score, and we assume it is a mislabeled data instance, we would want to remove it from the training data.  How then could one decide based on this metric whether or not exclude a data instance?  I.e., how can you differentiate such cases?


4) The idea is pretty straightforward - in the sense of taking an error bound and just measuring the difference on it by removing a data instance - this kind of leave-out-out analyses approach has been widely used and is common in machine learning (e.g., for feature importance as well), in many different context.  This may be seen as somewhat limiting the novelty, but I feel the additional development of a computational efficient algorithm and analyses of the approach overcomes this limitation.


clarity,_quality,_novelty_and_reproducibility: The work is clearly written and organized and high-quality in terms of sound development and analyses of the approach (aside from perhaps not situating it with respect to some related work).  As mentioned, although the basic approach of measuring the removal of an item to measure its importance or impact is a common one in ML - this is a novel application of it on this bound and an interesting idea, and there is significant development beyond this starting point.

The authors provided their code in supplementary material as well - so reproducibility should be good.
summary_of_the_review: Overall I found it to be an interesting and potentially useful paper on the one hand that could inspire further research, but on the other hand also raising several questions and missing fields of prior work on the target applications (i.e., dataset subset selection / pruning, and handling label error).  In particular I feel it is not really accurate to claim past methods have not been developed to quantify data instance complexity without also training the predictive model, and that the missing related work and describing where this work fits in comparison could have a negative effect, as related work may end up being rehashed if readers are unaware of it.  Further it is not enough to determine if the proposed approach should be used in practice (i.e., the practical benefit) vs. the other methods not mentioned or compared to.  I hope these concerns can be addressed in revisions and in appendices as needed as well.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work proposes a method for scoring the utility of individual samples in a dataset, a problem that's relevant for dataset pruning and identifying incorrect/noisy labels. Whereas previous work has developed solutions that involve training the model with the full dataset one or more times, this work proposes a model-free approach. The approach focuses on the data complexity score defined by Arora et al (2019) and calculates the difference when the sample is included vs excluded. The computational complexity for this approach is potentially high, requiring the inversion of a $n \times n$ matrix (where $n$ is the training set size), but this will in some cases compare favorably to the cost of model training.

The authors provide experiments with three image datasets showing that the method (complexity gap score) is useful for dataset pruning, and that it can highlight cases where the dataset has noisy labels.
strength_and_weaknesses: --- Strengths ---

- A reasonable and relatively simple approach to quantify the value of individual training samples: the difference in a data complexity measure (the complexity gap score).
- An interesting application of the generalization gap analysis for two-layer networks from Arora et al (2019).
- The authors consider how to minimize computation time by reducing the number of matrix inversions.
- One of very few methods that enables dataset pruning without performing a full training run.
- The authors elaborate on the mathematical relationship between the complexity gap score several existing scores ("Correlation to other scores").
- Provides similar or better performance to existing methods in the experiments with FashionMNIST, CIFAR-10/100

--- Weaknesses ---

- Heavily based on ideas from Arora et al (2019). I personally don't view this as a major shortcoming, I think it's a valuable insight that work from a very different part of the field is applicable here.
- The authors could consider adding an appendix section to walk through their derivations for eq. 3-4 in more detail. It took me a while to see where these results come from, particularly the part about the Schur complement (it seems related to the formula for inversion of block matrices, which was not mentioned).
- Could the authors provide more information about the running-time they observe in practice? It seems important to know how the large matrix inversion $(\mathbf{H}^\infty)^{-1}$ compares to a single training run, or how much the computation is reduced when performing the stochastic calculation.
- In the experiments, the C-score doesn't appear to have been used for Fashion-MNIST (Figure 2). Is there a reason for this, would the authors be able to add it?
- One shortcoming in this approach seems to be that we expect large complexity gap scores both for useful/difficult samples and for samples with incorrect/noisy labels. This means that if we prune the dataset by keeping only samples with large scores, we're likely to retain samples with incorrect labels. I suspect this issue does not exist for any previous method that explicitly evaluates performance on a validation/test set when training with partial training sets. Could this be discussed/acknowledged somewhere in the paper?

About the method:
- It would be nice to allude to several implementation details in the main text, such as how you ensure scalar labels, $|y| < 1$, vector-shaped inputs and $||x||_2 = 1$. I see that these were described in Appendix A, but this would have been nice to point to more clearly, perhaps in the experiments section.
- The stochastic calculation approach was not mentioned at all in the main text, but it seems to play a crucial role in reducing the practical computation time. Is that what was used throughout the experiments? The sanity check with Spearman's rank correlation is helpful, but could the authors also include a plot with Pearson's correlation? I would hope that we see the results converging to something closer to 1, because Pearson's will be less sensitive to small disagreements between the lowest scores.
- Do the authors have any practical recommendations for determining the required number of runs required for convergence of their stochastic approach? Could it be significantly different for different datasets?

A couple missing works that should probably be mentioned:
- TracIn [1] belongs to the family of methods that analyze training dynamics to understand the value of each sample in the dataset. This should probably be cited and could even be considered as an additional baseline for the complexity gap score.
- There's a paper that attempts to derive a closed-form solution for the Data Shapley values [2], and I believe it doesn't require training a model either. The results end up being bounds rather than the exact values, but I think this work ends up falling in the same category. This work should definitely be mentioned, and perhaps compared against in the experiments.

[1] Pruthi et al, "Estimating training data influence by tracing gradient descent" (2020)
[2] Kwon et al, "Efficient computation and analysis of distributional Shapley values" (2021)
clarity,_quality,_novelty_and_reproducibility: The work is well written and it has decently high novelty (although it's based on ideas from Arora et al, 2019). I have no concerns about reproducibility.
summary_of_the_review: I think this work is a valuable addition to the data valuation literature. The method has some shortcomings and the paper could be improved in a couple places, but I view it favorably overall. If the authors could make some of the changes mentioned in my review, I would be inclined to raise my score.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes the complexity gap (CG) score, which quantifies the change in data complexity when each training instance is removed from the training set.  The primary differentiator between CG score and other data valuation measures (e.g., Shapley value, C-score, etc.) is that CG score can be calculated without any (partial) model training.  
strength_and_weaknesses: Reading the paper's abstract, I was quite excited by the stated claims.  The ideas and the paper have promise.  However, the paper has problems; it is not yet ready for publication and needs to empirically evaluate and candidly discuss where this "training-free" data valuation runs into limitations.

#### **Strengths**

- A competent method to evaluate the quality of data without model training is clearly highly valuable.  This makes CG score's motivation clear and compelling.

- The generalization of complexity score from a dataset valuation method to an instance valuation method is a natural strategy.  It makes the paper's theoretical foundation easier to understand.

- I appreciated the discussion of CG', and I am glad the authors included it.

#### **Weaknesses**
- Evaluating only Fashion MNIST and CIFAR10(0) is very disappointing.  These are not particularly challenging datasets.  Related work (e.g., Jiang et al. 2020) evaluate on ImageNet.  I could not recommend acceptance without more challenging datasets.

- I am surprised about Table 4's poor rank correlation between "feature space CG" and vanilla CG.  It is concerning how well your method will work on more challenging tasks.  Moreover, I imagine that pretrained features will generally be more semantically meaningful than the raw pixel values.  My intuition could be wrong here, but I imagine I would not be the only one to hold such a prior.  The authors really need to address this point at least in Section G but ideally in the main paper.

- In Section 3.1, the authors describe CG score as a "*data-centric measure*."  However, all evaluation in this paper is on vision datasets.  Data-centric/data-agnostic measures should be evaluated on multiple data modalities.  At best, this evaluation could only show that CG score is an effective vision data metric.

- Figure 2 was confusing at first review.  I believe a primary reason for that is that in one case "larger is better" and in the other "smaller is better."  Perhaps dividing it into two subfigures where that difference is made more obvious (e.g., in the caption) would improve clarity.

- The paper as a whole needs more baselines.  There are many alternate data valuation approaches (e.g., Influence Functions, TracIn, Shapley Value methods) not evaluated here that should be for at least some experiments 
  - Figure 3b should at least include C-score.  I understand Jiang et al. do not provide precalculated C-score values for FashionMNIST but they do for standard MNIST.  Hence, Figure 3b's evaluation could use regular MNIST. Jiang et al. also provide C-score for CIFAR100.

- This paper needs a self-contained section explicitly specifying the computational and space complexity. It is fine to include it in the supplement, but it needs to be there.  If I missed it, please let me know, but I also checked the supplement.  Section A.2 came the closest but largely glossed over the point.
  - I assume you have data on the execution time of your method.  It should be in the supplement for reference.

- The "*Related Works*" does not adequately discuss the relation between data valuation and training-set influence. This relationship is primarily contextualized through Data Shapley which is only one method in this broader field. I also think the evaluation would be stronger with one or more training-set influence methods (e.g., TracIn [Pruthi et al. 2020]) included.
clarity,_quality,_novelty_and_reproducibility: The writing quality was fine overall.  At points, the writing was, in places, quite wordy with sentences too long (e.g., the first sentence in the abstract).  Similarly, paragraphs were often too long.  These long sentences/paragraphs detract from the paper's clarity and from the ability of the reader to grasp the authors' main point.  I did not base my score on this point much, and this is primarily provided as feedback to the authors.

The authors do not provide an implementation of their method.  The experiments are simple enough many of them could be implemented.  
* Figure 5's caption lacks many of the key experimental details. The description of the experiment in Sec. A.3 is not clear or easy to follow.  Also, the number of trials in each experiment is not clear.

A non-exhaustive list of typos:
* Pg. 2: 'has a close relation to 'learning *difficult*' of the instances'
* Pg. 8: 'by analyzing the training dynamics *of CIFAR10 dataset* in'
* Pg. 13: '*filpping*'
summary_of_the_review: The concept of estimating data's value without any training is obviously attractive. However, there are no free lunches. "Low-cost" strategies usually require tradeoffs and encounter limitations where the method breaks down.  The authors never really address this point by, for example, affirmatively showing that such a "breakdown" does not occur on hard tasks. They also do not include a substantive, stand-alone discussion or acknowledgment of the method's observed "breaking points."  That is a grievous omission.

If the authors have evaluated their method on harder tasks and did not report the results, those results are needed.  Without them, the paper is definitely incomplete.  

The paper has promise. Perhaps with a strong author response, I could be persuaded to acceptance. However, the paper changes, in particular the additional necessary evaluation, needs significant revision.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes a data valuation score that can effectively be used as a proxy for the impact of individual datapoints in the optimization/generlization of DNNs called the complexity-gap score. This score finds irregular or mislabeled data instances and can be computed without needing to train the model.

The proposed method tackles an important and fundamental problem in ML regarding data valuation and data quality. The method is more efficient than the alternatives and is shown to be effective on a range of tasks. Moreover, the idea is proposal and nicely justified both empirically and theoretically.

The main weakness is that it's unclear whether results hold on more complex data-- in such settings, the intermediate representations of the model may be less reliable. The authors are encouraged to address these possible limitations.
justification_for_why_not_higher_score: Lack of experiments or discussion for more complex datasets.
justification_for_why_not_lower_score: The paper is overall strong-- it presents some nice and useful contributions which are both empirically and theoretically justified.
Decision: Accept: poster