Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Deep learning uses augmentations to improve generalization performance. Using all augmentations for a dataset may slow down training. A subset selection technique is proposed (e.g., "coreset") using insights from the Neural Tangent Kernel (NMT) framework such that an alignment between the NMT Jacobian and the residuals is preserved. This alignment score is used to select the coreset using submodular optimization, which allows the model to be trained on a subset of augmented data (e.g., 0.1% to 30%) while preserving most augmentation benefits. The speedup of the method is reported to be up to 6.3x.
main_review: Strengths:
* The paper presents a convincing reason why the approach can work in theory.
* The approach seems novel and connects various prior works.

Weaknesses:
* I thought the algorithm description in Section 4 was a bit rushed. For example, equation 11 was hard to understand and is core to the algorithm.
* I also though the Section 5 was rushed. The whole evaluation is ~1 page, which leaves the reader wanting for 1) how speedup is calculated 2) what is the objective of the experiments 3) what takeaways should be had. I would recommend moving other text to the appendix (e.g., anything reviewing prior work can be shortened and pushed to appendix).
* Figure 3b seems like a random walk. Figure 3c x-axis and text labels seem misaligned. Overall, I think this figure can be improved to give a clearer and more convincing story.
* The theory is appreciated but maybe it's worth contextualizing what values of the constants L and epsilon_0 are common in practice. Even a simple augmentation like translate can cause a large pixel deviation. For example, with 100 pixels horizontally, each varying by 1 intensity via a gradient (e.g., 0 to 99), shifting by 1 pixel will cause a change in the image that is 100 large.
* The good results seem very CIFAR10 specific. For example, Figure 4b shows SVNH has minimal improvement. More experimental evaluation is always good. For example, MNIST would have been an easy result to add and is in-fact mentioned in the paper, yet I didn't see it in evaluation.
summary_of_the_review: The paper is ok. I think there is enough theoretical justification for why the method could work, though I think empirical evidence is necessary to still show that. The theory is a bit disconnected and seems more like a synthesis of many different works; I wonder if it can be presented more succinctly? In any case, I found the writing good enough to follow. My biggest concern is the generalization of the evaluation, since it seems quite short at the moment and very CIFAR10 specific.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper first provides a theoretical analysis, under some assumptions, of the effect of data augmentation on the singular values of the network Jacobian and then proposes a method to improve the sample complexity of data augmentation, that is to select a subset of the data on which to perform the transformations to speed up training. The proposed method aims to find subsets of data whose augmentation yields similar alignment of the Jacobian with the residual vector as the fully augmented data. 
main_review: The main contribution of this paper is, in my opinion, a sound theoretical analysis of the impact of input perturbations on the singular values of the Jacobian, or the eigenvalues of the Neural Tangent Kernel (NTK), that may inspire other researchers. However, the limitations of the analysis with respect to real-world image data augmentation, as well as the limited motivation, in my opinion, for the need for the proposed method, have an overall negative impact in my assessment of the significance of this work. I elaborate on these concerns below. 

First, the whole theoretical analysis, built upon that of Rajput et al. (2019), is based on modelling data augmentation as additive perturbations of the inputs. This is stated at the beginning of Section 2 and never recalled as a limitation again in the paper (except for one section in the supplementary material). On the contrary, the authors argue that this modelling of data augmentation captures typical real-world image transformations, such as "translations, crops, rotations, and [...] other pixel-wise augmentation methods such as sharpening, blurring, and color distortions" (second paragraph of Section 2). This is in sharp contrast with the limitations discussed by Rajput et al. (2019) themselves, on whose work the current paper takes inspiration for the theoretical analysis. In their Conclusion and Open Problems, Rajput et al. (2019) wrote: "There are several interesting open problems that we plan to tackle in the future. First, it would be interesting to theoretically analyze practical state-of-the-art augmentation methods, such as random crops, flips, and rotations. Such perturbations often fall outside our framework".

In line with Rajput et al. (2019), I would strongly argue that additive perturbations, while interesting from a mathematical point of view, only very weakly capture the extent of image transformations used in practice. Geometrical transformations can hardly be approximated by additive perturbations. One example of a widely common transformation that strongly differs from additive perturbations is horizontal flipping. This introduces a strong inductive bias, based on the properties of human visual perception, which is why it is included in almost all data augmentation schemes. Therefore, any conclusions from such a mathematical approximation to real-world data augmentation needs to be cautious. For example, the paper concludes saying that it has been shown "that data augmentation improves training and generalization by enlarging the smaller singular values of the neural network Jacobian". As argued above, this seems a strong claim given the limitations. The strength of the claims is particularly surprising after the authors wrote about other existing works on the theoretical analysis of data augmentation that they "do not provide insights on the effect of data augmentation on training deep neural networks".

My other main concern has probably a stronger impact on my overall assessment of the paper. This has to do with the motivation for the need for methods to select subsets of data on which to apply data augmentation. On the second sentence of the abstract, the authors write that "modern data augmentation techniques become computationally prohibitive for large datasets". This statement is extended in the introduction, where the authors cite several papers on so-called _automatic data augmentation_. First, these methods are indeed disproportionally expensive in computational terms, while providing only marginal improvements (in the best case) with respect to traditional, simple, cheap data augmentation techniques (Pérez and Wang, 2017). The authors mention that "multiple augmented examples are usually generated for a single data point to obtain better results, increasing the size of the training data by orders of magnitude", as though this was a weakness of data augmentation, while it is actually one of its main strengths. In particular, that the effective training size may be increased orders of magnitude while keeping the training time within the same order of magnitude. 

An analysis of such advantages and the reasons for it (such as the fact that data augmentation can be performed in parallel to the parameter updates of the model, and even create a queue of data that would effectively keep the training time identical, given sufficient memory), as well as compelling evidence of the efficiency of data augmentation is provided by Hernández-García and König (2018). In that paper we see that training with light data augmentation (translations and horizontal flips) on the full training set provides large performance gains with a marginal increase of the training time. Furthermore, they also provide empirical evidence that training with 50 % data _and_ data augmentation (again on the full available set) achieves more than 95 % of the _full_ accuracy in about half the training time. Therefore, given that data augmentation can be applied almost _for free_ and training time can be traded by reducing the training data for a marginal reduction of the accuracy, why do we need a complex algorithm such as the one presented in this paper?

It is not clear from the paper how the training times are calculated, but we still see that in the best case the gains stay within the same order of magnitude. I believe that a stronger justification of the need for this method should take into account the considerations mentioned above, as well as a comparison with other alternative ways to trade training time for performance, such as changes in the architecture, etc.

### References

* Pérez and Wang. [The effectiveness of data augmentation in image classification using deep learning](https://arxiv.org/abs/1712.04621). 2017.
* Hernández-García and König. [Data augmentation instead of explicit regularization](https://arxiv.org/abs/1806.03852). 2018
summary_of_the_review: While the paper seems solid in terms of correctness, I have a less positive impression due to, in my opinion, limited significance. This has to do with the simplification of data augmentation with respect to real world necessary for the theoretical analysis, as well as with the lack of strong motivation for the proposed algorithm.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors model data augmentation as an additive perturbation and analyze its effect on training dynamics and how it enlarges the smaller singular values of the network jacobian.
Then they propose a new method to iteratively extract a subset of the training data that when augmented closely capture the full augmented data dynamics.
Authors show that by augmenting this subset combined with full training data they can outperform the state-of-the-art method by 7.7% on CIFAR-10 and 4.7% on SVHN while achieving 6.3x and 2.2x speedup respectively.
main_review: **Strengths**

I appreciate that this paper provides rigorous theoretical analysis to data augmentation, its connection to NTK and effect on eigenvalues and how data augmentation affects the training dynamics and generalization, and it also provides mathematical proofs to the theorems proposed.

In the presence of noisy labels, the proposed technique is outperforming reference methods.

And even when the selected subset is very small compared to randomly augmenting datasets of similar size the proposed method is capable of providing good augmentation resulting and a decent increase in performance.

**Weaknesses**

As I understand one of the observations in section 3.1 suggests that augmentation cannot change the singular values considerably for diverse datasets, but we still see a gain in performance when augmenting these datasets.
My concern is if we have a more diverse dataset than the ones experimented on, according to my understanding we will have a larger number of singular values and that will limit the ability to find a subset to augment and we need to increase the size of the subset which can largely limit the effectiveness of the method.

In my opinion, one of the main strengths of the method is when we have a very large dataset but unfortunately, the authors didn’t provide any experiments regarding large datasets like ImageNet.

The proposed method outperforms the baseline when the size of the subset is fairly small, but when increasing the size into reasonable percentages the improvement is marginal see Table 4 in appendix C.

**Suggestion To Authors**

Though the whole paper is nicely executed and demonstrated, in my opinion, some of the figures aren’t easy to read e.g. (Figure 4) I suggest splitting the figure into two side by side showing the speed gain and accuracy improvement separately.

summary_of_the_review: I think the paper is of interest, especially the theoretical analysis. It is well written and provides rigorous mathematical analysis to data augmentation and proofs for all the theorems, lemmas and corollaries mentioned.

But I believe the main application of the proposed method is in large scale dataset settings, while in small or medium-size datasets augmenting the full dataset is not an issue, but that wasn’t presented (see my concerns in the previous section).
Also, the improvement when increasing subsampling size is marginal, especially with diverse datasets.
This problem and the lack of experiments with large and diverse datasets prevents me from giving a higher recommendation of acceptance.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper shows that data augmentation can speed up learning by enlarging the smaller singular values of the Jacobian. Following this idea, this paper proposed a framework to iteratively extract small subsets of training data that captures the alignment of NTK with the residual when augmented.

main_review: Strengths:
1) The motivation of the paper is clearly justified. 
2) The presentation of the theoretical analysis and the algorithm are clear and sound.
3) The results shows improvement over the max-loss method on some datasets.

Weakness:
1) What is the extra computation cost for finding the coreset compared with that of  the random and max-loss baseline?
2) Does the coreset change significantly at different epochs?
3) It would be interesting to show the performance when transferring the core-set found on one architecture (e.g., ResNet20) to train on a different architecture (e.g., Wid-ResNet). Will transfer the corset leads to performance loss?
4) You might referred to the wrong figure in the sentence “Figure 3b depicts the increase in intersection between max-loss subsets and coresets over time”
5) The paper only did experiments on small datasets other than large datasets such as ImageNet.


summary_of_the_review: This paper proposed a data efficient augmentation framework with extensive theoretical analysis. The presentation and the proposed method are sound. However, the lack of experimental results on large datasets such as ImageNet makes the results of the paper much less convincing.
review_title: null

Meta-review: The work presents a theoretical analysis of data augmentation, presenting evidence that data augmentation enlarges the smaller the singular values of the network Jacobian. Based on this theory the authors present a method for selecting a subset of training data to use with augmentation that decently approximates performance of training w/ augmentation on the full dataset. Reviewers overall agreed that the theoretical analysis was interesting, and did not find any flaws (though it is worth noting that the theory is restricted to additive perturbations). However, multiple reviewers found the presented experiments unconvincing, and questioned the stated motivation. The AC agrees with reviewers that most simple augmentations are not prohibitive in training speed. Certainly training on less data with a fixed epoch budget would require less compute time, but this is has nothing to do with augmentation and instead is a result of fewer steps taken in training. In the rebuttal, the authors argued that training on Imagenet is prohibitive with a single GPU (taking 2 weeks to do full training). However, given the authors claim their method speeds up training by a factor of 6.3x, then reducing ImageNet training from 2 weeks to 2 days would be a more convincing application of their method and would strengthen the work.
Decision: Reject