Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes a heuristic to prune the dataset for training by using the norm of the gradient for an ensemble of random networks as a proxy score. They provide some intuition for the proposed method and conduct experiments to verify that the method works well in practice.
main_review: Strengths:
- The problem is well-motivated with clear potential applications to speed up training and save computational costs
- The method proposed is sound. It also poses an interesting question about how the initial random network 'essentially' determines characteristics of future training. The connection to NTK and forgetting score is also interesting. 
- The experimental set up is reasonable, and the empirical results suggest the method works well in practice
limitations_and_societal_impact: Yes, the authors have discussed these aspects well
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose GraNd score based on expected gradient loss to filter out low impact examples from the training. The proceed to empirically show that pruning examples with low GraNd score is competitive with state of the art methods with the benefit of being able to use the score early at training (as to save on compute). 

The paper then discusses the relationship of GraNd with EL2N---the norm of the prediction vector minus the one hot of the true label, showing that EL2N can be used to improve the performance of models by removing the examples with high EL2N. 

Then, the authors go and compare different scoring ranges for pruning to find that the highest scores are not beneficial when there is label noise. Moreover, they experimentally show that high scoring examples drive learning velocities in NTK and contribute to rougher loss landscape.


main_review: While the score the authors suggest is interesting I have some reservations about the paper. First, the 'theoretical derivation' is very unclear (I mention a couple of examples below) and also I'm not completely sure whether it is correct. Therefore, this score could be just a random functional that might or might not be too interesting. 

Moreover, the results are a bit scattered and I'm not sure what is the main message of the paper. Do we want to find important examples? If so, I would first try to define what is an important example. Then for every experiment I would want to understand why this experiment was conducted, and why this demonstrates that the metric indeed finds examples that are important. To me it seems that the main experiment is the pruning one and it seems that the metric proposed by this paper is slightly worse than the forgetting score so the contribution is incremental. (Also, you should compare to Area-Under-Margin, see comment below).

Other comments:

* When the authors discuss time derivatives it is unclear what they mean. Unless doing gradient flow (which was not mentioned in the paper) time works in discrete steps, so I don't see why the time derivative is well defined. If the point was to discuss discrete derivatives it is unclear why the equation below eq 2 has \approx because then it should be =. 

* In Lemma 2.2. I'm not sure why \|d\ell(f(x,y))  / dw_t \| is finite and why does it not depend on (x,y) as mentioned in the discussion above? For the former, there could be example for which the loss is unbounded after some step, for the later, to me it seems that the derivative of the loss at example (x,y) has to be dependent on (x,y). Also, would appreciate an explanation to what does the chain rule mean (and why it holds) when the derivative discrete. 

* Not sure what 'maintaining \Delta_t x` means in line 128.

* I assume that in equation 4 the expectation is over initialization, this should be mentioned.

* In figure 1. I would remove 'for pruning strategy see left' and have a large legend that spans the entire figure so it is clear that the legend is relevant to everything.

* while forget score is calculated later in training it seems to be beating both proposed measures in the paper.

* I think this paper is relevant and probably should be cited and compared against: https://arxiv.org/abs/2001.10528 

+++++ 
Post rebuttal:
I would like to thank the authors for their detailed review and alleviating some of my concerns and decided to change the score 5 -> 6. I think some minor edits along the lines of the rebuttal could help the paper's readability and motivation. 
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes two metrics to rank training set samples for reducing the training set size:

1. L2-norm of the error vector (EL2N).
2. L2-norm of the gradient vector (GraNd).

These can be evaluated cheaply and relatively early in training (10-20 epochs) or even at initialization. For instance, by keeping only the top 50% CIFAR10 of training data according to this metric, one can achieve the same test accuracy as when using the whole training set.

The authors evaluate their method on several datasets and architectures, and run several experiments that relate these metrics to change in NTK during training or the onset of linear mode connectivity, and more.

main_review: ## Post-rebuttal update:


I am raising my score from 5 to 6 due to good results on architecture/hyperparameter robustness, and conditioned on other changes discussed in the rebuttal: ablation against label-independent metrics + impact of number of evaluations on performance of GraNd/EL2N + rework presentation / theory based on the mismatch between empirical and theoretical GraNd. I believe these changes will not change the paper results/narrative by too much, but will improve its significance and address some of my prior concerns about motivation/ablations. I thank the authors for actively engaging in the rebuttal.

-------
## Initial Review:

I find the key result of this paper very interesting and surprising (that one can trim the training set so significantly with such simple metrics). However, due to lacking motivation / insight / ablations, I do not feel like advocating for acceptance.

## Originality

To my knowledge the idea is novel, although I am not well familiar with dataset pruning literature.

## Quality

Overall the quality is good, and experiments are thorough and exhaustive. However, certain aspects are lacking that make me lower the score:

1. IMO section 2.2. is not at all clear and contains multiple errors. For instance:

	* Line 114: why does $\Delta_t$ depend on  $S_t$? I don't see it on the RHS. $f_t$ does not depend on $S_t$ per equation (1). But even if it did, extra dependence on $S_t$ would be redundant due to dependence on $f_t$.
    * Line 115: "where the gradient is computed on the minibatch $S_t$" - what does this mean exactly? Expression in line 114 is the derivative of the loss of outputs at $x$ after $t$ training steps, and as before, I don't see dependence on $S_t$.
    * Line 116: should it be $w_t - w_{t - 1}$? Otherwise RHS contradicts the definition in Equation (1).
    * Line 118: Here and after $\Delta_t$ is evaluated at the whole $S$, but I still don't understand how exactly it depends on this argument.
    * Line 120: Formula for $dw_t/dt$ now contradicts the one in line 116, where the sum is over $S_{t-1}$.
    * Line 124: "constant $c$ does not depend on $(x, y)$" - isn't it clearly defined as a function of $(x, y)$ in line 121?
    * Lines 131-133, 135-136: why do individual logit gradients become roughly orthogonal and similar in size _after_ training? I can see them being such at the beginning, but shouldn't logits start to differentiate as the network learns different classes?
  
  
Overall, I found this section quite vague and confusing, and hope it can be improved in terms of mathematical rigor and clarity.

2. By definition (i.e. in expectation over random initializations), for a fixed $x$, EL2N and GraNd at $t = 0$ are precisely the same for any $y$ among one-hot targets $[1, 0,\dots, 0],\dots, [0,\dots, 0, 1]$ via a symmetry argument. Therefore, at initialization, they can't possibly depend on $y$, and yet the metrics are still helpful per Figure 1 and others. Hence,

	2.1. I think it's necessary to ablate the metrics against $y$-independent baselines such as (a) the L2 norm of the network outputs $f_t(x)$ (or L2 distance from $f_t(x)$ to e.g. a constant vector of $[1/C,\dots,1/C]$), and (b) the Frobenius norm of the outputs-to-parameter Jacobian $\partial f_t(x)/\partial w_t$, or other alternatives. These could be simpler and more interpretable, and with more potential applications, since you don't need the label. 
    
    2.2. Could you please confirm that the 10 random seeds used to compute the metrics do not intersect with 4 random seeds used to train and evaluate networks afterwards? Otherwise $y$ could indeed be useful at initialization, but only because it helps pick luckier random seeds.

## Clarity

Apart from section 2.2, the paper is very clearly written. However, in my opinion the experimental design itself doesn't shed that much light into the nature of these metrics, and they remain a bit mysterious to me. For instance, why is one sometimes better than the other? Why can there be dips in performance, as in e.g. epoch 2, Figure 1? Do training samples get reordered frequently as training progresses? Do these metrics work for other loss functions? Can we predict the sharp dip in performance as we increase the fraction of pruned examples? Do rankings computed for one architecture work well for pruning the dataset for a different architecture?

## Significance

On one hand, I think the findings are unexpected and can make follow-up work ask many interesting questions. On the other hand, I don't see a practical use case for compressing the dataset this way. Namely, there are quite a few hyper-parameters (EL2N vs GraNd; sliding window location; epoch used for ranking), and I think in the vast majority of cases it will be simpler to just train the network on the whole dataset.

One way to apply this could be to demonstrate that these metrics computed for one architecture (e.g. VGG) work well for other architectures (e.g. ResNet), in which case one could produce an architecture-agnostic ranking of images for each dataset, which would be very useful. If this kind of result could be added (or is already in the paper and I missed it?), I would rate this paper higher in terms of significance.

Alternatively, significance could be improved if the authors used a label-independent metric as I mention in section "Quality", in which case I could imagine applications in semi-supervised / active learning (e.g. one could use these scores to request labels for highly-ranked images).

limitations_and_societal_impact: All good.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper focuses on identifying important examples for training neutral networks early in training with the goal of pruning a significant portion of training examples in later training stages. It analyses the influence of a training example on the loss reduction of other examples and defines two scores:  gradient norm (GraNd) and error norm (EL2N) that bound or approximate this influence. It shows that the  higher scores generally correlate with the higher influence. However, the paper also finds that the highest scoring examples tend to be outliers and are subject to label noise, or are otherwise difficult. The paper then proceeds with analyzing the high and low scoring examples (under the defined GraNd and EL2N metrics) in training dynamics. 

main_review: On one hand, the findings of this paper seem quite trivial, as examples that have larger gradients (in expectation) are likely to be more important. It reminds the heuristics of choosing neurons with higher weigh norm in neural network pruning in earlier works on model compression. On the other hand, the intuitive rule in this paper is motivated by a principled analysis (or at least an attempt to derive one). My other concern is the practical value of this paper. The empirical results show that when the pruned ratio becomes interesting (over 50%) then the proposed data pruning method is only marginally better than a random pruning. 
limitations_and_societal_impact: yes
review_title: null

Meta-review: This paper proposes a new heuristic to prune the dataset for training a neural network by using the norm of the gradient for an ensemble of random networks as a proxy score (error norm: EL2N, gradient norm: GraNd).  Authors show that pruning examples with low GraNd score is competitive with state of the art methods with the benefit of being able to use the score early in the training. Using these metrics, they shed light on how the underlying data distribution shapes the training dynamics: they rank examples based on their importance for generalization, detect noisy examples and identify subspaces of the model’s data representation that are relatively stable over training.


Common weaknesses pointed out were some lack of clarity (`ghFJ`, `EkuL`), unclear practical value (`V5c3`, `EkuL` ) and efficacy(`V5c3`). The authors actively engaged in the discussion and provided explanations and results to address the reviewer's concerns. The AC believes analyses performed and explanations given during the discussion would improve the final version of the paper further and strongly encourages the authors to adopt them. Questions regarding architecture / hyperparameter robustness and lack of ablations, raised by reviewer `EkuL`, were also resolved. 

After the discussion, all reviewers recommended acceptance (1 clear accept, 3 weak accepts). While efficacy and practical applications are not fully developed, for this type of theory inspired work those should be criteria for higher distinction than acceptance. The AC believes strengths outweigh the weaknesses. The problem studied in the paper is well motivated and provides interesting insights for understanding deep neural networks and, as authors claim, have potential to inspire new methods and new theories of deep learning. The AC recommends acceptance. 

Decision: Accept (Poster)