Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper empirically studies the phenomenon of memorization in deep neural networks for image classification tasks, and presents several novel findings: 1) appropriate data augmentation significantly improves the performance of embedding learning when training with random labels; 2) with data augmentation, there is a clear separation between the final embedding layer applied with $k$-NN and the projection layer -- the embedding is successful at generalizing to true labels, while the projection layer memorizes the random training labels; 3) the benefits of data augmentation in this setting are not explained by label invariance; 4) a possible explanation of the discovered effect is due to augmented datasets increasing the effective size of the dataset beyond the capacity of function class. 
strength_and_weaknesses: * Strengths: 
    * This paper finds a very interesting set of phenomena regarding memorization in deep neural networks, and performs several thorough and well-thought-out experiments to delineate and explain the phenomena. 
    * The paper empirically demonstrates that the embeddings learned under random noise are useful, and memorization happens in the last layer in their setting.
    * The paper empirically demonstrates the usefulness of augmented labels (and the added benefit in the presence of larger amounts of label noise) for the purpose of learning the useful (under $k$-NN) embeddings, and show that without augmentation, the embeddings learned are not useful (under $k$-NN). 
    * The paper proposes an explanation for the usefulness of data augmentation that derives from a concept of invariance under augmentation which correlates with improved performance, and empirically shows that the embedding layer exhibits the most invariance.
    * The paper empirically demonstrates that larger sizes of (appropriately) augmented datasets results in higher difficulty in overfitting during training, and proposes this empirical fact as an explanation for why data-augmentation helps embedding learning.


* Weaknesses: 
    * Only one relatively simple architecture for image classification is studied in the paper, and it is unclear whether the phenomena exhibited here will generalize to other kinds of architectures. 
    * The heuristic arguments regarding the explanation of data augmentation's advantage in terms of capacity are rather loose and should probably be framed differently. In particular, I feel that Definition $5.1$ and the language of VC-dimension etc. are unnecessary and not useful framings to make the argument that empirically we see that with data augmentation, the training loss after 5000 epochs (Fig. 5b) no longer goes to zero (also, what do plots like Fig. 5b look like if we increase 5000 to say 20000?). Instead of giving a technical definition that is essentially a stand-in for whether or not zero training error is reached or not, it would be simpler and clearer to avoid giving that definition since it is not used anywhere else. I was also unclear about the phrase "as effectively $B \to \infty$" in the Inflated Sample Size section on page 8 -- this is also used throughout the paper, for instance in the description of Fig. 11, and it doesn't seem to be entirely correct to me.
    * Quality of embeddings is assessed solely via $k$-NN probing -- I agree this approach is very reasonable and interesting to study, and has indeed been used in many prior works. I would also be interested in the results of other forms of probes (say, training a linear classifier on top of the embeddings on true data) beyond just $k$-NN. It is also not entirely clear to me what the quality of embeddings with respect to $k$-NN probes implies about the quality of embeddings used in other ways (if this has been addressed in prior literature, perhaps this could be elaborated on in the paper or at least mentioned). For instance, it would be helpful to elaborate upon "due to the very restricted complexity of probing, the resulting performance is very dependent on the quality of input representations" (pg. 3). In particular, what complexity? Restricted in what way? Is quality being used loosely here? It would also be nice if pointers were included to any existing literature on measuring the quality of representations beyond $k$-NN probes (perhaps in the appendix). 
   * The normalized invariance measure introduced in Eq. 2 seems reasonable, but it would be helpful to remark upon/ explain why this particular measure was chosen; in particular it is not clear to me that the value for each data point $x$ is on the same scale since there is included in the normalization a dependence on the particular dataset as well. This doesn't seem like too big of an issue since the measure seems to be averaged over the data points $x$ anyways (is this true? Fig. 6 wasn't clear on this), but some more discussion would be good to have.
   * Regarding related work, it might be a good idea to add more and more recent citations (later than 2019) to the section in the intro on progress in deep learning, benign overfitting, and the section on data augmentation (https://arxiv.org/abs/2106.04156 for instance among others for data augmentation). There are also of course several more works that are related in the memorization setting (other papers by Feldman for example). I would also particularly recommend the authors look at the line of work relating to understanding feature learning in deep networks (for instance, https://arxiv.org/abs/1905.10337, https://arxiv.org/abs/2001.04413 and prior citations as well as work that cites this paper), as it relates to some of the questions raised in the Discussion and Conclusion section.
clarity,_quality,_novelty_and_reproducibility: * Clarity: The paper was for the most part clear, though I have mentioned a few minor points below:
    * pg. 1: "commands new avenues" -- commands is odd word choice, perhaps "suggests" is better
    * pg. 1: typo "applied3" 
    * More clarity about the train-test splits for the $k$-NN procedure should be included somewhere, might have missed it
    * Generally, the kind of data augmentation being used for random labels (i.i.d., non-i.i.d. procedure given in Section 4, etc) should be better clarified throughout the paper, I was confused several times about which kind of data augmentation was being referred to. For example, in Table 2, in Fig. 5, in the "Learn if you must" section on pg. 8, and in the body of the paper throughout.
    * In Figure 3, consider using a histogram for the probing results graphs or instead indicating on the x-axes some arrow that signifies "increasing depth". 
    * pg. 7: I wouldn't use the phrase "counter-intuitively", it seems to me at least pretty intuitive and expected that label-preserving i.i.d. augmentations for random labels would be bad.
    * pg. 8: "As we increase B", B should be in LaTeX format.
    * pg. 9: Fig. 6 should clarify if normalized invariance is averaged over the whole dataset and whether the $k$-NN probing error is using the embedding layer. It should also clarify what kind of data-augmentation is being used. 
    * pg. 9: Eq. 2 doesn't appear to define which norm is being used (I assume $\ell_2$).
    * pg. 14: I believe Lemma A.2 is standard and that should be mentioned. 
    * pg. 16: first word, "classes," -- there should be no comma there.
    * pg. 16: "recovering the result" -- it should be clarified what this result is, the sentence is unclear. 
    * pg. 17: "RandAugment" -- it would be helpful to describe what strength means here. 
    * pg. 17: "Previous works have highlighted the importance of augmentations" -- cite them
    * pg. 18: "We employ is this case a simple linear encoder" -- typo
    * pg. 18: In the Toy Example section, I was confused by the choice of projector and the justifications given for it -- what is the capacity of the model? Capacity in what sense? VC-dimension? I was also confused by the phrase "its non-linear nature guarantees any possible invariance learning will occur at the encoder instead" -- is that true? Why? This seems like a plausible hypothesis, but it's unclear that it's true. More description of where this particular projector comes from would also be helpful. 
    * pg. 18-19: In Figure 13, how is the capacity $\mathcal{C}$ of the model computed (as in what formula are you using and why)? 



* Quality: The paper's development and experiments are of high quality. 


* Novelty: The paper has some very interesting (and to my knowledge, novel) experiments and insights.


* Reproducibility: The paper seems easy to try to reproduce, though I have not done so myself.
summary_of_the_review: Overall, the paper described an interesting empirical investigation into the phenomenon of memorization in noisy label vision classification tasks and came away with several interesting nuggets of insight. I thought the insights were quite interesting and novel, and the paper was for the most part pretty clear to read. I also thought the experiments well supported the claims and made sense. The paper will certainly give theorists more food for thought when thinking about how to study the problems associated with data augmentation and memorization in deep networks.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies a notion coined as "benign memorization", which refers to the phenomenon that when training with standard data augmentation, a deep neural network could fit to complete random label assignment on the training set, yet still learns representations that shows surprisingly good discrimination power under kNN probe (using the *clean* training and test labels). The paper went on to conduct a number of experiments aim to understand this behavior, and found that different layers behave differently, and the phenomenon cannot be fully explained by the label-preserving property of data augmentation.
strength_and_weaknesses: **Strength**

1. This paper identifies an interesting phenomenon called benign memorization, which has not been systematically studied in the past. 
2. This paper analyzed this phenomenon from various aspects, including identifying where memorization happens, and potential explanation from the perspective of effective model capacity.

**Weakness**

1. The experiments in Section 5 with i.i.d. data aug are a bit puzzling, and would benefit with more in-depth analysis. For example, to what extent is the observation due to the reduced base training set size (1000 vs 50,000)? Can you include 2 extra rows in Table 3 for Random + standard DA, and Clean + standard DA (potentially also compare to online DA vs. 50 copies of pre-generated augmentations).

2. I'm a little confused by the arguments from effective capacity under a fixed computational budget. The paper argues that the models do not have enough capacity to efficiently memorize with augmented samples, therefore it is forced to benign memorization. 

    1. The argument does not explain why the models do not do benign memorization (i.e. learning good representations and only memorizing with the projector) when the capacity is enough.
    2. The main phenomenon of benign memorization is not under a computational budget. The model in Fig.3 was trained for 13,000 epochs and still demonstrate benign memorization. Does the effective capacity argument help with the understanding here? One potential argument is that this experiment is done with online augmentation, leading to increasingly larger training set size as training goes. To complete the picture, it would be good to conduct the same experiment (i.e. *without* computation budget) but with fixed number of standard data augmentations.


clarity,_quality,_novelty_and_reproducibility: The paper is clearly written and easy to follow. Experimental details are provided in the appendix, and the experiments seem to be relatively easy to reproduce. I do have the following questions:

1. Can you clarify how the "Non-label preserving augmentation" are generated?

2. Can you explicitly clarify in the main text how "training loss" are defined and computed under data augmentation? Do you simply report the running average of the training loss, which is the loss computed *before* the model trains on each augmented version of the image? Or do you load a model checkpoint and go over the entire training set + augmented copies and compute the average loss?
summary_of_the_review: This paper identifies an interesting phenomenon of model learning representation with surprisingly good discriminative power even for completely random label assignment, when trained under standard data augmentation. This could potentially provide an interesting angle for future studies of the role of data augmentation in deep learning, and in particular, in self-supervised learning.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This submission considers neural networks trained with completely random labels with or without data augmentations. The main observation is that when data augmentations are enabled, neural networks learn meaningful representation of data. This is supported by fitting a k-NN classifier on learned representations using ground-truth labels, and demonstrating significantly increased performance compared to representations at initialization. The explanation that the authors give for this phenomenon is that data augmentation increases the effective dataset size, which given the limited capacity of the neural network, makes it impossible to memorize random labels without uncovering the structure in the augmented data. The paper also highlights that the label noise memorization usually happens in later layers of neural networks.

strength_and_weaknesses: The topic of memorization and generalization in deep learning is of high relevance to the ICLR community. The paper is mostly well-written (apart from some parts references below) and the details for reproducing the work are provided. The main findings described above are supported convincingly.

However, I think the paper has limited technical and experimental novelty. Furthermore, the most related work of Dosovitskiy et al. [3] is not discussed in the main text. It is referenced only in the appendix, in the context of an experiment (Fig. 8) which is essentially a reproduction of the experiment described in section 4.3.1 of Dosovitskiy et al. [3].

1. The finding that it is possible to learn meaningful representations of data by fitting random labels/targets was well-established by Dosovitskiy et al. [3], where a neural network is trained with random surrogate classes (in the limit each example gets its own class) and **data augmentations**. It is clear that it is the presence of data augmentations that provides the signal for learning useful representations. Dosovitskiy et al. [3] also analyze the effect of the number of the surrogate classes.

2. The finding that label noise memorization happens mostly in later layers of neural networks has been presented before (see for example Arpit et al. [1] and Cohen et al. [2]).

3. The observation that training with data augmentations leads to representations that are more invariant to data transformations is also present in Dosovitskiy et al. [3]. I believe this direction is still underdeveloped. Exploring more the theoretical aspect of this (along the lines of arguments presented in the appendix A) and understanding what kind of representation properties emerge from different types of data augmentations can significantly improve this work. For example, it would be interesting to find out what is the exact effect of the MixUp augmentation on representations?


### Minor comments

* I suggest to state early in the paper that the term “memorization” refers to the ability of memorizing a noisy label. In some existing works memorization is defined as the difference between training and test accuracies (mostly in the noiseless setting). Feldman & Zhang (2020) define it differently. Different settings and definitions of memorization will probably lead to different conclusions whether generalization and memorization are in conflict or not.

* “While previous works have identified that the very first layers provide non-trivial performance even without data augmentation, including it strengthens this effect significantly.“ – it would be nice to provide some citations here.

* I think the thought experiment presented in Sec 5.1 can be removed. If one aims to check whether the label-preserving property of data augmentations is the key that enables learning of useful representations, then the natural experiment to do is to generate a random label with every augmentation and check whether learning still happens. This is indeed done in Figure 5 and clearly demonstrates that the signal comes from many similar examples having the same [random] label.

* The normalized invariance of eq. (2) is defined using predictions of the network. It is expected that this invariance score is going to be lower when training with data augmentations, as essentially the network is supervised to output the same target for all transformations of one example. I think it will be more appropriate to probe *representations* in order to check if representations become more invariant to data transformations.

* Typos to fix: “totice” → “notice” and ““applied3” → “applied”.

* In Figure 6, the dashed curve values can be presented on the right y-axis.

* The main findings of the experiments presented in the appendix can be summarized concisely in the main text.

### References

[1]  Devansh Arpit, Stanisław Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, et al. A closer look at memorization in deep networks. In ICML, 2017.

[2] Gilad Cohen, Guillermo Sapiro, and Raja Giryes. DNN or k-NN: That is the generalize vs. memorize question. ArXiv, abs/1805.06822, 2018.

[3] Alexey Dosovitskiy, Jost Tobias Springenberg, Martin Riedmiller, and Thomas Brox. Discriminative unsupervised feature learning with convolutional neural networks. In NeurIPS, 2014.


clarity,_quality,_novelty_and_reproducibility: See above.
summary_of_the_review: In summary, I think the findings of this submission are not novel enough to be published at ICLR. This is the main determinant of my recommendation.

UPDATE: Given that I had misunderstood the setting of Dosovitskiy et al. [3] initially, after the discussion with the authors, I have updated my recommendation from 3 to 5.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work discovers interesting phenomena about benign overfitting: 1) even training on random labels, early layers can still learn meaningful representations; 2) deep layers are prone to fit noises in data and cannot learn useful features.
strength_and_weaknesses: Strength:
1. The paper is well-written and easy to follow. The idea is well-motivated from recent benign overfitting papers.
2. The discovered phenomenon is very interesting and provides useful insights to theory works.

Weakness:
1. How does the augmentation magnitude affect the results? In my experience, if the augmentation is too strong, the network cannot fit the data.
2. I am curious about what role does BatchNorm play in this study. Current theory works (at least for benign overfitting) do not consider BN. I would appreciate it if the authors could verify if BN is important to helping early layers learn useful features under random labels.
3. In addition to K-NN, will training a linear classifier on fixed feature mappings (learned from random labels) also exhibit similar results?
4. Related feature learning behavior is also mentioned in previous application papers, just name a few [1]. Basically, people also found the network backbone is responsible for feature learning and the classifier is more prone to label quality. The authors may consider discussing more on these related works.

[1] To Balance or Not to Balance: A Simple-yet-Effective Approach for Learning with Long-Tailed Distributions
clarity,_quality,_novelty_and_reproducibility: Overall this work is clearly organized, with high-quality experiments and novel designs.

I could not check the reproducibility since there are no supplementary materials or anonymous github links. I hope the authors could release the code.
summary_of_the_review: In general, I think this is a good paper meaningful to both theory and empirical researchers.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This work studies the memorization in neural networks trained on data with random labels. The authors find that without data-augmentation, such training does not lead to meaningful feature learning, however with label-preserving data-augmentations, earlier layers in networks learn meaningful features. These are interesting empirical findings worthy of publication. That being said, I would encourage the authors in the introduction and discussion to more dramatically emphasize the connection to self-supervised techniques (such as SimCLR). In particular, the label-preserving augmentations studied here encourage representations of the same base image with different augmentations to align as much as possible (predict the same random output class label), and to not align with different images (predict different random output vectors). Viewed in this light, one could describe this work as a variation on previous self-supervised approaches. For example, in SimCLR, the lower layers learn meaningful representations which are used for classification after the initial self-supervised training with a projection head used to align images with different augmentations. That being said, it is interesting to see that random labels and heavy augmentations are enough to realize this.
justification_for_why_not_higher_score: The work would benefit from more direct comparison to previous self-supervised techniques, which lead to similar conclusions. 
justification_for_why_not_lower_score: The authors make in interesting observation that training with random labels, but heavy data augmentation leads models to learn meaningful representations.
Decision: Accept: poster