The Curious Case of Benign Memorization
Authors: Sotiris Anagnostidis
Gregor Bachmann
Lorenzo Noci
Thomas Hofmann
Venue: ICLR 2023 poster (2023)

Abstract: Despite the empirical advances of deep learning across a variety of learning tasks, our theoretical understanding of its success is still very restricted. One of the key challenges is the overparametrized nature of modern models, enabling complete overfitting of the data even if the labels are randomized, i.e. networks can completely \textit{memorize} all given patterns. While such a memorization capacity seems worrisome, in this work we show that under training protocols that include \textit{data augmentation}, neural networks learn to memorize entirely random labels in a benign way, i.e. they learn embeddings that lead to highly non-trivial performance under nearest neighbour probing. We demonstrate that deep models have the surprising ability to separate noise from signal by distributing the task of memorization and feature learning to different layers. As a result, only the very last layers are used for memorization, while preceding layers encode performant features which remain largely unaffected by the label noise. We explore the intricate role of the augmentations used for training and identify a memorization-generalization trade-off in terms of their diversity, marking a clear distinction to all previous works. Finally, we give a first explanation for the emergence of benign memorization by showing that \textit{malign} memorization under data augmentation is infeasible due to the insufficient capacity of the model for the increased sample size. As a consequence, the network is forced to leverage the correlated nature of the augmentations and as a result learns meaningful features. To complete the picture, a better theory of feature learning in deep neural networks is required to fully understand the origins of this phenomenon.

Published as a conference paper at ICLR 2023
THE CURIOUS CASE OF BENIGN MEMORIZATION
Sotiris Anagnostidis", Gregor Bachmann', Lorenzo Noci", Thomas Hofmann
Department of Computer Science ETH Zürich, Switzerland (sotirios anagnostidis, gregor how.emmmmnn..reezoooooooooeooe wtw.iinnneethh.ommmm
ABSTRACT
Despite the empirical advances of deep learning across a variety of learning tasks, theoretical understanding of its success is still very restricted. One of the key challenges is the overparametrized nature modern models, enabling complete overfitting of the data even if the labels randomized, i.e. networks can pletely memorize all given patterns. While such a memorization capacity seems worrisome, in this work show that under training protocols that include data augmentation, neural networks learn to memorize entirely random labels in a be- nign way, i.c. they learn embeddings that lead highly non-trin non-trivial performance under nearest neighbour probing. We demonstrate that deep models have the sur- prising ability to separate noise from signal by distributing the task of memoriza- tion and feature learning to different layers. As result, only the very last layers are used for memorization, while preceding layers encode performant features which remain largely unaffected by the label noise. We explore the intricate role the augmentations used for training and identify a ceanoorzzaiinnggnnaaaiiazzn trade-off in terms of their diversity, marking clear distinction to all previous works. Finally, we give first explanation for the emergence of benign memoriza- tion by showing that malign memorization under data augmentation is infeasible due to the insufficient capacity of the model for the increased sample size. As a consequence, the network is forced leverage the correlated nature of the aug- mentations and as result learns meaningful features. To complete the picture, better theory of feature learning in deep neural networks is required fully understand the origins of this phenomenon.
INTRODUCTION
Deep learning has made tremendous advances in the past decade, leading to state-of-the-art per- formance various learning tasks such computer vision (He al., 2016), natural language processing (Devlin et al., 2019) and graph learning (Kipf & Welling, 2017). While some progress has been made regarding the theoretical understanding of these deep models (Arora al., 2018; Bartlett et al., 2019; 2017; Neyshabur et al., 2015; 2018; Dziugaite & Roy, 2017), the considered settings are unfortunately often very restrictive and the insights made are only qualitative or very loose. One of the key technical hurdles hindering progress is the highly overparametrized nature of neural networks employed in practice, which stark contrast with classical learning theory, according to which simpler hypotheses compatible with the data should be preferred. The challenge beautifully illustrated in the seminal paper of Zhang al. (2017), showing that deep networks are able to fit arbitrary labelings of the data, i.e. they can completely memorize all the patterns. This observation renders tools from classical learning theory such as VC-dimension needed. or Rademacher complexity vacuous and new avenues to investigate this phenomenon The random label experiment has been applied as a sanity check for new techniques (Arora et al., 2018; 2019a; Bartlett et al., 2017; Dziugaite & Roy, 2017), where approach is evaluated based on its ability to distinguish between networks that memorize or truly learn the data. From a classical perspective, memorization is thus considered as bug, not feature, and goes hand in hand with bad generalization.
of overparametrization
In this work we challenge this view by revisiting the randomization experiment of Zhang et al. (2017) with a slight twist: we change the training protocol by adding data augmentation, a standard practice used in almost all modern deep learning pipelines. We show that in this more practical

---

Published as a conference paper at ICLR 2023
setting, the story is more intricate;
Neural networks trained on random labels with data augmentation learn useful features!
More precisely, we show that probing the embedding space with the nearest neighbour algorithm of such a randomly trained network admits highly non-trivial performance on a variety of standard benchmark datasets. Moreover, such networks have the surprising ability to separate signal from noise, as all layers except for the last ones focus on feature learning while not fitting the random labels at all. On the other hand, the network uses its last layers to learn the random labeling, the cost of clean accuracy, which strongly deteriorates. This is further evidence of a strong, implicit bias present in modern models, allowing them to learn performant features even in the setting of complete noise. Inspired by the line of works on benign overfitting (Bartlett et al., 2020; Sanyal et al., 2021; Frei et al., 2022), we coin this phenomenon benign memorization. We study our findings through the lens of capacity and show that under data augmentation, modern networks are forced to leverage the correlations present in the data achieve memorization. As consequence of the label- preserving augmentations, the model learns invariant features which have been identified to have strong discriminatory power in the field of self-supervised learning (Caron et al., 2021; Grill al., 2020: Bardes et al., 2022; Zbontar et al.; Chen & He, 2021). Sppecciicillllllyy we make the following contributions:
We make the surprising observation that learning under complete label noise still leads to highly useful features (benign memorization), showing that memorization and generalization are not necessarily at odds.
We show that deep neural networks exhibit an astonishing capability separate noise and signal between different layers, fitting the random labels only at the very last layers.
We highlight the intricate role of augmentations and their interplay with the capacity of the model class, forcing the network to learn the correlation structure.
We interpret our findings in terms of invariance learning, an objective that has instigated large successes in the field of self-supervised learning.
2 RELATED WORK
Memorization. Our work builds upon the seminal paper of Zhang et al. (2017) which showed how neural networks can easily memorize completely random labels. This observation has inspired a multitude of follow-up works and the introduced randomization test has become standard tool to assess the validity of generalization bounds (Arora al., 2018: 2019a; Bartlett et al., 2017; Dzi- ugaite & Roy, 2017). The intriguing capability of neural networks to simply memorize data has inspired researchers to further dissect the phenomenon, especially in the setting where only a subset of the targets is randomized. Arpit et al. (2017) studies how neural networks tend to learn shared patterns first, before resorting to memorization when given real data, as opposed to random labels where examples are fitted independently. Feldman & Zhang (2020) study the setting when real but llon-ttileed" data is used and show how memorization in this case can be beneficial to performance. Maennel et al. (2020); Pondenkandath et al. (2018) the other hand show how pre-training net- works on random labels can sometimes lead to faster, subsequent training on the clean data or novel tasks. Finally, Zhang et al. (2021) show how training on random labels can be valuable for neural architecture search. In all these previous works, data augmentation is excluded from the training pipeline. For partial label noise, it is well-known in the literature that neural networks exhibit sur- prising robustness (Rolnick et al., 2017; Song et al., 2020; Patrini et al., 2017) and generalization possible. We highlight however that this setting is distinct from complete label noise, which we study in this work. Finally, Dosovitskiy et al. (2014) study the case where each sample has a unique label and achieve strong performance under data augmentation. This setting is again very different from ours two examples never share the same label, making the task significantly simpler and distinct from memorization.
Data augmentation. Being a prominent component of deep learning applications, the benefits of data augmentation have been investigated theoretically in the setting of clean labels (Chen et al., 2020b; Dao et al., 2019; Wu et al., 2020; Hanin & Sun, 2021). The benefits of data augmentation have been verified empirically when only subset of the data is corrupted (Nishi et al., 2021). On the other hand, investigations with pure label noise where signal remains in the dataset are absent in
2

---

Published as a conference paper at ICLR 2023
9
h
Input
Encoder
Embedding
Projector
Visualization of secoder-projecton pair. The encoder is typically chosen as a ResNer18, while the projector is one hidden-layer MLP.
(b) Illustration of standard data aug- mentation. Notice how each augmen- tation indeed preserves the label "cat".
Figure 1: (Left) Encoder-projectte pair. (Right) Standard data augmentations.
the literature. Finally, we want to highlight the pivotal role of data augmentation in self self-supervised learning frameworks (Caron et al., 2021; Grill et al., 2020; Bardes et al., 2022; Zbontar et al.; Chen & He, 2021; HaoChen et al., 2021), where it facilitates learning of invariant features.
BACKGROUND
Setting. In this work we consider the standard classification setting, where we are given n. N i..dd samples (I), ...., (In, Vn) 5.i.d. 'D from some data distribution D. consisting of inputs E I&d and one-hot targets y E RC, each encoding one out of C' classes. We consider family of parametrized functions (in this work, neural networks) fe Ra - R,,, where 0 θ denotes the (concatenated) weights from some space θ C IP where p is the total number of parameters. Moreover, specify loss function :: RC RCC R4 which measures the discrepancy between a prediction fx( and its corresponding target y. i.e. 1(fo(z),))) y). We then perform learning by minimizing the empirical loss i as function of the parameters 0,
n
i = argmingge i(())= : argmin Σ ((o(())))))
using some form of stochastic gradient descent and measure the resulting generalization error L(Ô) = Eg y>) (x)) [.]] We denote by px the marginal density of the inputs and by Py the conditional density of the labels given input. py x encodes the statistical relationship be- tween an input æ and the associated label y. As typical in practice, we assume that we are in the so-called interpolation regime (Ma al., 2018), i.e. assume that stochastic gradient descent can find a parameter configuration Ô that achieves zero training loss (see Eq. 1).
Architecture. Throughout this work, we consider networks composed of an encoder h Rd R.m and a projector Jø m + RC, where both 1b and & denote the parameters of the respec- tive building block. As encoder, we typically employ modern convolutional architectures such as ResNets (He et al., 2016) or VGG (Simonyan & Zisserman, 2014), excluding the final fully- connected layers, while the projector is usually MLP with one hidden layer. We illustrate such network in Fig. la. Such architectures have become very popular in the domain of feature learning and are extensively used in unsupervised and self supervied learning (Caron al., 2021; Grill al., 2020; Bardes et al., 2022; Zbontar et al.). In this work, we are interested in assessing the quality of the encoder's features hep when the network fo Go hep is trained on random labels.
Probing, To evaluate the embeddings hys, we apply nearest-neighhour-boe based and linear probing, which refers to performing K-nnarest-neighhour (or linear) classification based on the embeddings (#:)(
y:)) y We fix the number of neighbours to K 20 throughout this work unless otherwise specified. Probing measures how useful given set of features hy is for a fixed task. A special case will often consider in this work is probing the encoder of network initialization, which we refer to as probing at initialization. Due to the lack of feature learning in probing, the resulting performance is very dependent on the quality of the input representations hg. Such method
3

---

Published as a conference paper at ICLR 2023
2.5
dean label dcantabels
ranoom lbels
Layer
Initialization
End of training
2.0
Training loss
Layer
36.9
34.3
Layer 2
36.4
33,5
Layer
36.5
30.4
1.0
Layer 4
36.2
14.9
0.5
Embedding
40.2
12.4
0.0g
2000
4000
5000
8000
10000 12000
Projector hidden layer
38.4
10.5
Steps
Output
24.2
10.5
Fitting random la- bels on unaugmented data on CI- FARIO with a ResNet18 is not significantly slower than fitting clean labels.
Figure 2:
Table 1: K-NN probing accuracies (percentage) for a R8 initialization versus the end of training on random labels without augmentations on CIFARIO. The four layers correspond the intermediate representations after each stage of ResNer.
has been used to assess the quality of a given embedding space in various works, for instance Alain & Bengio (2017); Chen et al. (2020a); Caron et al. (2021); Grill et al. (2020); Bardes et al. (2022); Zbontar ct al..
Random labels and memorization. Denote by et BCC the I-th unit vector, i.e. the one-hot encoding of class L. Zhang et al. (2017) introduced a randomization test, where any clean label y: E fel..... ec} in the training set is replaced by random one-hot encoding, Yi e, where I ~~ (([1.... C}) with U denoting the uniform distribution over the discrete set {1,.... C}. Throughout this text, we will denote randomized variables with on top. Notice that such an intervention destroys any statistical relationship between inputs and targets, i.c. PY|x = py. As consequence, training on such a dataset should become very difficult as there no common pattern left to exploit and an algorithm has to resort to pure memorization approach. Zhang et al. (2017) showed that deep neural networks have an astonishing capacity to perform such memorization tasks, easily overfitting any random label assignment even on large-scale datasets such as ImageNet (Deng et al., 2009) without a large increase in training time (see Fig. 2). Even explicit regularizers such as weight decay and Dropout (Srivastava et al., 2014) can be used in standard manner, data augmen- tation however is excluded from the pipeline. We have reproduced a subset of the results of Zhang et al. (2017) in Table 2, first column. As expected, deep neural networks indeed manage achieve zero training error across a variety of datasets while not generalizing at all, both with respect to a well the original, clean test labels. In order to further study the amount of distortion in the resulting embedding space, we apply neirest- probing with respect to the clean data. More precisely, given the features h& learnt from training on the random label task { Dt } we apply probing based on the clean training data {< y:) and evaluate with re- spect to clean test data. We display the results in Table In line with previous works, (Cohen al., 2018; Maennel et al., 2020), we find that while very early layers might retain their performance at initialization, a significant drop occurs with increasing depth, further highlighting the lack of feature learning and the malignant nature of memorization in this setting. This is in line with observations that early layers Iearn useful representations (Zhang et al., 2019).
random test labeling
Data Augmentation. A standard technique present in almost all computer vision pipelines is data augmentation. We consider transformations T' Rd + Rd, that take a given input æ and produce a new augmentation क- == T(x), which by design, should preserve the associated label, i.e. ý y. Such transformations are usually given as a composition of smaller augmentations including random crops, flips, color-jittering etc. In Fig. 1b we show set of different augmentations of the same underlying image æ. Notice how these transformations indeed leave the associated label invariant. We denote by 'T the set of all possible augmentations. Data augmentation is usually applied in an online fashion, i.c. at every step of gradient descent, we uniformly sample a fresh transformation T' ~ 21 (T) and propagate through the network. We highlight that data augmentation a standard technique necessary for sfate-of-the-an performance for variety of vision tasks. Indeed, the top five leaders on ImageNer' (Yu al., 2022; Dai et al., 2021; Zhai al., 2021; Pham et al., 2021; Liu et al., 2021) all rely on some form of data augmentation in their training pipeline. If one hence
hhttps://papee www.rrsswwthhhcc.cocooooooo scta/ http//sttaaaaaeeeeeeeee www.imalaaaa.ooooo a ficati on-on- magenett
4

---

Published as a conference paper at ICLR 2023
DATASET
MODEL.
RANDOM
RANDOM + DA
CLEAN
CLEAN + DA
INIT
RexNei18
12.4
76.2
83.6
91.3
40.6
CIFARIO
VGG11
15.0
71.9
83.0
89.0
14.3
ResNet18
5.0
42.7
50.5
68.2
16.6
CIFARI00
VGG11
6.0
46.4
51.2
59.0
18.9
RexNet18
33.4
38.3
46.6
TinylmageNet
VGGIT
1.2
29.4
34.6
43.8
5.4
Table 2: K-NN probing accuracies (in percentage) of the embeddings for various datasets under different settings. DA refers to training under standard data augmentation. INIT refers to the perfor- mance at initialization. Except for INIT, all models reach perfect (unaugmented) training accuracy.
wants to study the memorization potential of neural networks in practical settings, data augmentation needs to be considered. We notice that the results of Zhang et al. (2017) and subsequent studies on the properties of memorization under random labels (Arpit et al., 2017; Maennel et al., 2020) were obtained without the use of data augmentation, leaving the memorization picture thus incomplete.
BENIGN MEMORIZATION
In this section, we present the curious phenomenon of benign memorization i.e. how neural networks manage to completely fit random labels under data augmentation, while at the same time learning predictive features for downstream tasks. Let us first formally introduce the terms benign and malign memorization, which are central to the results of this work. In the following, S == {(x;, y;)) its randomly labeled version.
denotes the original clean dataset and S = {(z; U:)
Definition 4.1 We call an encoder-projector pair 96.) a memorization of S, if fx perfectly fits S. Moreover, we call ( : a malign memorization if additionally, probing of he. on S does not improve over probing initialization. On the contrary, call (hp.. benign memorization of & if probing of ha. on S outperforms probing at initialization.
As highlighted in Sec. and shown in Table 2, memorizing solutions found with stochastic gradient descent without data augmentation on standard vision benchmarks are of malign nature. This is very intuitive, as randomizing the targets destroys any signal present in the dataset and thus gener- alization seems impossible. We show now how including data augmentation in the training pipeline completely reverses this observation.
Training details. In all subsequent experiments involving data augmentations, we use the stan- dard transfornations employed in self-supervised learning frameworks such Chen al. (2020c); Grill et al. (2020); Chen He (2021). These consist of a composition of random crops, color- jittering, random greyscaling, and random horizontal flips, leading mations. Moreover, we rely on mixup augmentations Zhang et al. (2018), where two images 31. 32 are combined into linear interpolation, according some weighting C = aæı + (1 a)æ2. The corresponding label ÿ is accordingly subject to the same linear combination, i.e. ÿ az1 (1 a)yz where labels represented their one-hot encodings. We use the standard vision datasets CIFARIO and CIFARI00 (Krizhevsky & Hinton, 2009), as well as TinylmgeeNer (Le Yang, 2015). For more details, we refer the reader to Appendix
diverse set of transfor-
[o, 1], i.c.
Benign Memorization. We display the results of training under data augmentation in Table 2. We observe that, surprisingly, nearest-neighbour probing of the learnt embeddings leads to clearly non-trivial performance, strongly improving over the models trained under random labels without data augmentation. Moreover, we strongly outperform probing at initialization, showing that indeed rich feature learning is happening. As consequence, data augmentation does not simply prevent malign memorization by preserving the signal at initialization but actually leads to learning from the data. On the other hand. it holds that the projector achieves perfect training accuracy the random labels and the network thus indeed memorizes the training data perfectly. Under data augmentation, deep models hence exhibit benign memorization. In Appendix C, Fig. further underline the
5

---

Published as a conference paper at ICLR 2023
0.35
0.49
2:0
0.5
0.64
1000
2015
1180
336
1683
1883
3893
1980
1923)
1328)
1250
1980
KAt orbbing on train
KCNN probing
0.3
baszd on cla ubus
Deoder
Layer
Layer2
Layer
Layer
Emtedding
0.2
Sxden
Output
Intressing deallt
Figure 3: K-NN probing of R CIFARIO, based on (flattened) representation of different layers. Dashed blue lines indicate K-NN accuracies fitted on the clean training data and evaluated W.r.t. clean test data. Solid lines indicate K-NN training accuracies based the random labels. Notice the sharp phase transition when reaching the projector layers"P" and "O", i.e. the projector reaches strong performance on the noisy labels (dashed) but randomly guesses on the clean data (solid). The opposite happens for the embedding layer, reaching 76% K-NN accuracy.
utility of the learnt features by evaluating their performance under transfer learning. We remark that this is, to the best of our knowledge, the first work showing that learning under random labels can lead to strong downstream performance, highlighting that memorization and generalization are not necessarily at odds. We notice that the training time under randomized targets together with data augmentation increases significantly, both compared to training under clean labels well fitting random labels without augmentations. In Fig. we show the evolution of both the training loss as well as nearest-neighhour probing test accuracy function of the number of epochs. Observe that for as long as 3000 epochs, neither training loss nor probing accuracy show any progress but then suddenly start rapidly improve.
We stress that our goal not to compete with standard training under clean labels, it can be seen in Table 2 that there is a large gap between the two methods. Instead we rather aim for deeper understanding of how deep networks generalize. We show that generalization, contrary to prior beliefs, remains possible even in the most adversarial setting of complete label noise.
Signal-Noise Separation. We now further inspect models trained under random labels and data aug- mentation, with an emphasis how the noise stemming from the random labeling affects different parts of the network. To gain insights into this, we perform nearest-neighhour probing of different layers in the network, with the twist that fit the K-NN classifier both with respect the clean training labels, as well as with respect to the random labels. This way we can assess how much given feature has adapted the particular structure (clean vs. random). We visualize the results of such a clean and noisy probing strategy in Fig. 3 at different stages of training. Surprisingly, we can see a striking separation between feature learning and memorization within the architecture; noisy probing only starts to improve over random guessing once we reach the projector, whereas encoder remains largely unaffected. On the other hand, clean probing outperforms probing at initialization throughout the entire embedding stage but sharply decays once we get the projector. Some previous work highlighted that even when training on random labels without data augmenta- tion. the very first layers learn data dependent features which lead to subsequent fast re-training clean data Maennel et al. (2020). We give an interpretation of this finding in Sec. 5.2. We further investigate the role of the projector in Appendix C, Fig. 7, finding that higher widths lead to better performance in general.
THE ROLE OF AUGMENTATIONS
The empirical evidence in the previous section highlights the crucial role of data augmentation for benign memorization. In this section, aim to gain insights into the phenomenon by investigating more closely what properties of data augmentation are essential for benign memorization and how "ideal" augmentations might strongly differ when learning with clean random labels.

---

Published as a conference paper at ICLR 2023
Dataset Size
1000
50000
Random
11.41
12.41
Ti (ex)
No
"arrale"
'grafo"
Random + ii.d. DA
12.41
Sigrei
Clean
36.75
83.66
Clean i..dd. DA
82.73
(Ry)
Clean + DA
69.7
91.3
Random + DA
54.7
76.2
"al aafffee
Figure 4: Illustration of the thought experiment in Sec. 5. The true cat Φ1 labeled as "giraffe" is augmented, leading to positive signal between the augmentations but to more noise due to 22, that has as true label "dog".
Table 3: K-NN probing accuracies of the embeddings of a ResNet18 for CIFARIO with and without i..d. augmentations un- der clean and random labels. 50000 refers to full CIFARIO for reference.
Label Preservation. The first important characteristic of augmentations is their label-preserving nature. i.e by augmenting an image (x, y) twice to produce (Ti (Tx)) y) .)))())))))))) (T2 y). we have ef- fectively added information, as indeed Ti (z) and (2 share the same label. Unfortunately, this reasoning is flawed in the setting of random labels, or the least only forms part of larger pic- ture, as we show in the following thought experiment. Consider two "original" samples (æ1, 9) and (222, ÿ) which happen share the same random label ÿ but in truth have distinct labels yı * y2. In this case, forming augmentations (T' ( 7) and (T2(x11,, 7) might lead to some correct signal as Ti (x1) and (21) share the same, true label, but the same time leads to more distortion as 22 has the same, random label, reinforcing the wrong correlation even more. As consequence, separating noise from signal remains equally challenging as before. We illustrate the argument in Fig. 4. To check this hypothesis, we consider the extreme case where augmentations T E TT produce a new, i..dd sample T(x) that shares the same, true label with æ. sense, this is the ideal augmentation and leads to the highest information gain. We implement such i.i.d. augmentations by only using a subset of the training data while using the remainder to assign to each training point B potential, independent examples with the same, true label. We choose the subset size number of augmentations as B = 50 for CIFARIO and train the same models as in Sec. 4, both under random and clean labels. We display the results in Table 4. Notice that for clean label training, such augmentations increase the training set size from 1000 to 1000 x 50 = 50000, thus leading to almost identical performance as training on the full dataset. Nounter-intuitivee above, training under random labels severely suffers under such ideal, independent augmentations and leads to malign memorization. In fact, this experiment is equivalent to fitting random labels without augmentations on the full training set where malign memorization occurs, as seen in Sec. 4.
1000 and the
but for the reasons outlined
This thought experiment demonstrates that under random labels, augmentations seem to play a very distinct role compared to the clean setting and label preservation in itself is not enough to guarantee benign memorization. This raises the following question:
What other properties of augmentations, besides label preservation, cause benign memorization?
We hypothesize that the origins of the phenomenon lie at the interplay between the highly correlated nature of augmentations and the inflated effective sample size that exceeds the model capacity (Sec 5.1), forcing the model to learn meaningful features (Sec 5.2).
5.1 GOING BEYOND THE MODEL CAPACITY
We now study the phenomenon of benign memorization from the view point of capacity of a model class. Intuitively speaking, the capacity C2 of a model captures how many distinct datapoints we can fit in é gradient steps, even if the corresponding targets are completely randomized. We refer to Appendix D.I for the formal definition adopted here. If a model has enough capacity, it can potentially memorize all the patterns in the dataset. As seen in Zhang et al. (2017), deep models used in practice in conjunction with standard datasets, operate below the capacity threshold but nevertheless, they do not "abuse" their power and fit clean data in meaningful way. On the other
7

---

Published as a conference paper at ICLR 2023
K-NN probing after 5000 epochs
Training loss after 5000 epochs
Label preserving augmentati ond Non-label preserving augmentations
Loos correspendion rig untttrm fanaam class mestgh
0.8
0.4
0.2
Randomireeddt
0.0
16
32
84
128
256
1024
2048
4006
19
37
128
1074
2048
4096
Number of augmentations
Number of augmentations
Figure 5: IIlustration of nearest-neighbour probing accuracy (left) and (running) training loss (right)
of R8 CIFARIO with increasing number of standard augmentations. We consider both label- preserving (blue) and completely random labeling of augmentations (red).
hand, by using data augmentation we inflate the number of samples and consequently operate above the capacity level. As a result, a model needs to efficiently encode augmentations (pure memorization is not possible) and hence meaningful features need to be learnt.
As seen in Sec. 3, standard datasets such as CIFARIO have size n below the capacity C of modern networks such as ResNets. When using data augmentation however, we now show that the resulting dataset exceeds the capacity.
Inflated Sample Size. Consider a set of augmentations T and assume that it has a finite size, B : [T] < 0C. Augmenting thus leads larger effective dataset Sang of size Bn. We can now study whether the capacity of standard networks trained by GD for a fixed number of epochs exceeds such an augmented dataset by varying B and randomly labeling each sample. We pre- compute fixed set of B random augmentations for each sample for varying B and attempt to memorize a random labeling, where labels of augmentations are not preserved. We use the same setup in Sec. 4 and augment CIFARIO using the standard augmentations in the way described in Sec. 4. We display the results in Fig. 5. We see that indeed, overfitting the random labels becomes more difficult we increase B and actually infeasible for fixed number of gradient steps t. = 5000 x 196 (fixed batch size on CIFARIO). Moreover, notice that in the standard setting of online augmentations, this observation becomes even more drastic as / increases over time if typical, continuous augmentations such as color jittering are included in the pipeline. We hypothesize that malign memorization under such an augmentation strategy thus becomes infeasible.
Learn if you must. We now investigate the influence of capacity on the resulting probing accuracy, in the case where augmentations are preserrres and hence offer valuable signal. We thus consider the same setup as in the previous paragraph for varying number of augmentations B while assigning the same label to augmentations of the same image. We show the results in Fig. on the left. We observe that as the number of augmentations B increases, probing accuracy improves and eventually surpasses probing at initialization. We hypothesize that as we approach and eventually surpass capacity, the model is increasingly forced to leverage the signal in augmentations and thus learns more and more relevant features. As we increase B, we saturate the information gain provided by the augmentations, the signal becomes redundant and performance starts to plateau.
5.2 WHAT CAN YOU LEARN FROM AUGMENTATIONS?
While have seen that the model is forced leverage the signal in augmentations, it remains unclear why this leads to high-quality embeddings. We now show how augmentations encourage features to become invariant, a property that has been identified in SSL to be strongly predictive.
Normalized Invariance. To measure the invariance of a function q Rd - IRo, we introduce the following quantity:
1(x: T) = E,, E (x:) q (22(2)))
(2)
E Ex fx (g(x)) 9xx')(()) 111
8

---

Published as a conference paper at ICLR 2023
Method
Normalized invariance
Normlizes invarsance
0.7
Initialization
0.867
Layer Layer 2
Clean
0.912
Layae.3
KANN
Clean + DA
0.691
Random
0.989
KNNN probing error
Random + DA
0.680
0.5
2303
4203
5000
6000
Epoch
Figure 6: Averaged normalized invariance of a 8 on CIFARIO, as function of epochs, lower value means more invariant. The dashed line represents K-NN probing error of the embedding layer.
Intuitively, (æ; T) captures the features' similarity of augmentations of the same datapoint compared to the representations of different datapoints x' * æ. Model's invariance implies [(x: q. 7) = 0, hence different augmentations are mapped to the same datapoint, while the model still able to meaningfully distinguish between the representations of different datapoints (i.e. Bm
<(=')ll * 0). In Fig. 6, we show how T(a;; q, T) for different layers correlates with probing performance and indeed decreases over time. Due its better implicit bias (RexNet vs MLP). invariance is largely learnt in the encoder, leading to the striking signal-noise separation identified in Sec. 4. These results suggest that when the model has insufficient capacity to mem- orize the (augmented) samples, it lears be more invariant with respect to the label-preserving augmentations. Consequently, this mechanism reduces the "effective sample size" and allows the model to fit the data in a benign (i.e. augmentation-invariant way. But why do invariant features imply a better clustering in embedding space as evidenced by a high K-NN accuracy? This is heavily researched topic with several plausible theories in the area of self-supervised learning (SSL) (Saunshi et al., 2022; Arora et al., 2019b; Wen & Li, 2021). In Appendix B, we derive a more formal connection between SSL loss and training with random labels. Others have looked the improved sample complexity caused by incorporating invariances into the model (Bietti et al., 2021; Xiao & Pennington, 2022).
DISCUSSION AND CONCLUSION
In this work we have identified the surprising phenomenon of benign memorization, demonstrating that generalization and memorization are not necessarily at odds. We put forward an interpretation through the lens of model capacity, where the inflation in sample size forces the model to exploit the correlation structure by learning the invariance with respect to the augmentations. Furthermore, we have shown that invariance learning happens largely in the encoder, while the projector performs the noisy memorization task.
Our findings underline the complicated and mysterious inner workings of neural networks, showing that generalization can be found where we least expect it. To describe benign memorization, complete generalization theory needs capture the strong implicit bias built into deep models, which enables clean separation of noise and signal. Secondly, such theory needs to incorporate feature learning, benign memorization only emerges the encoder. Both those goals remain very challenging. In particular, we speculate that the line of work based on the neural tangent kernel (Jacot al., 2018) which connects SGDD-optimized neural networks in the infinite width regime and the realm of kernels cannot explain benign memorization. In fact, in this regime the weights do not move from initialization, thus preventing feature learning. Some recent works have pushed further and study neural networks outside of the kernel regime (Allen-Zhu & Li, 2019; 2020) and we believe that the developed tools could be very helpful in understanding benign memorization. Another promising direction perturbative finite width corrections to NTKs (Hanin & Nica, 2019; Zavatone- Veth et al., 2021) which also incorporate feature learning. We leave exploring benign memorization in such mathematical framework future work.

---

Published as a conference paper at ICLR 2023
7 REPRODUCIBILITY STATEMENT
We have taken multiple steps to ensure reproducibility of the experiments. We refer the reader to Appendix F for complete description of the training protocol. We have also released the code as part of the supplementary material, including scripts on how to reproduce our results.
REFERENCES
Guillaume Alain and Yoshua Bengio. Understanding intermediate layers using linear classifier probes. International Conference on Learning Representations (ICLR), abs/1610.01644, 2017.
Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond ker- nels? In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL https: http::///ccceeeei........oc nwwriis........s..eeeeeerre...ee http:/gg.....aoooooo//////////// cctppaper//019//111e. pdf.
Zeyuan Allen-Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning. ArXiv, abs/2001.04413, 2020.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. Proceedings of the 35th International Conference on Machine Learning (ICML), 2018.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. Proceedings of the 36th International Conference on Machine Learning (ICML, 2019a.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saun- shi. A theoretical analysis of contrastive unsupervised representation learning. arXiv preprint arXiv:1902.09229, 2019b.
Devansh Arpit, Stanislaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxin- der S Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, et al. A closer look at memorization in deep networks. In International conference on machine learning, pp. 233-242. PMLR, 2017.
Adrien Bardes, Jean Ponce, and Yann LeCun. VICReg: soriance-nvariane-ccvainne regular- ization for self-supervised learning. In International Conference on Learning Representations (ICLR), 2022.
Peter Bartlett, Dylan J. Foster, and Matus Telgarsky. Sperttally-normaaizzed margin bounds for neural networks. 31st Conference on Neural Information Processing Systems (Neurips). 2017.
Peter L. Bartlett, Nick Harvey, Chris Liaw, and Abbas Mehrabian. Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research 20, pp. 1-17, 2019.
Peter L. Bartlett, Philip M. Long, Gá bor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117445):00663-00077 apr 2020. doi: 10. 10.1073/pnas. 1etpmnas...977770 1907378117.
Alberto Bietti, Luca Venturi, and Joan Bruna. On the sample complexity of learning under geometric stability. Advances in Neural Information Processing Systems, 11188633-16888 2021.
Mathilde Caron, Hugo Touvron, Ishan Misra, Herv' e egoo, Julien Mairal, Piotr Bojanowski. and Armand Joulin. Emerging properties in self-supervised vision transformers. 2021 IEEE/CVF International Conference Computer Vision (ICCV), pp. 9630-9640, 2021.
Mark Chen, Alec Radford, Jeff Wu, Heewoo Jun, Prafulla Dhariwal, David Luan, and llya Sutskever. Generative pretraining from pixels. In Proceedings of the 37th International Conference on Ma- chine Learning (ICML), 2020a.
10

---

Published as a conference paper at ICLR 2023
Shuxiao Chen, Edgar Dobriban, and Jane Lee. A group-theoretic framework for data augmentation. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 21321-21333 Curran Associates, Inc., 2020b.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In Hal Daumé III and Aarti Singh (eds.), Proceed- ings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 1597-1607. PMLR, 13-18 Jul 2020c.
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 15750-15758, 2021.
Adam Coates, Andrew Ng, and Honglak Lee. An analysis of single-layer networks in unsupervised feature learning. In Geoffrey Gordon, David Dunson, and Miroslav Dudík (eds.), Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics (AISTATS), volume 15 of Proceedings of Machine Learning Research, pp. 215-223, Fort Lauderdale, FL, USA, 11-13 Apr 2011. PMLR.
Gilad Cohen, Guillermo Sapiro, and Raja Giryes. Dnn or k-nn: That is the generalize vs. memorize question. ArXiv, abs/ 0ats/1800 805.06822, 2018
Ekin Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. Randaugment: Practical automated data augmentation with reduced search space. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition workshops, pp. 702-703, 2020.
Zihang Dai, Hanxiao Liu, Quoe Le, and Mingxing Tan. Coatnet: Marrying convolution and attention for all data sizes. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021.
Tri Dao, Albert Gu, Alexander Ratner, Virginia Smith, Chris De Sa, and Christopher Re. A kernel theory of modern data augmentation. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceed- ings of Machine Learning Research, pp. 1528-1533 PMLR, 09-15 Jun 2019.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hier- archical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 248-255, 2009. doi: 10. 109/CVP...20009...... 5206848.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutamova. Bert: Pre-training of deep bidirectional transformers for language understanding. Proceedings of NAACL-HLT, 2019.
Alexey Dosovitskiy, Jost Tobias Springenberg, Martin Riedmiller, and Thomas Brox. Discrimi- native unsupervised feature learning with convolutional neural networks. Advances in neural information processing systems, 27, 2014.
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence, 2017.
Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. Advances in Neural Information Processing Systems, 33:2881- 2891, 2020.
Spencer Frei, Niladri S Chatterji, and Peter Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Po-Ling Loh and Maxim Raginsky (eds.), Proceedings of Thirty Fifth Conference Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 2668-2703. PMLR, 02-05 Jul 2022.
Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernaroo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, Bilal Piot, koray kavukcuoglu, Remi Munos, and Michal Valko. Bootstrap your own latent- a new approach sulf-super learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), ), Advances in Neural Information Processing Systems, volume 33, pp. Curran Associates, Inc., 2020.
11

---

Published as a conference paper at ICLR 2023
Boris Hanin and Mihai Nica. Finite depth and width corrections to the neural tangent kemel.. arXiv preprint arXiv:I909.00 05999, 2019.
Boris Hanin and Yi Sun. How data augmentation affects optimization for linear regression. In A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan (eds.), Advances Neural In- formation Processing Systems, 2021.
Jeff Z. HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self- supervised deep learning with spectral contrastive loss. In NeurIPS, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Tianyu Hua, Wenxiao Wang, Zihui Xue, Sucheng Ren, Yue Wang, and Hang Zhao. On feature decorrelation in self-supervised learning. In Proceedings of the IEEE/CVF International Confer- ence on Computer Vision, pp. 9598-9608. 2021a.
Tianyu Hua, Wenxiao Wang, Zihui Xue. Yue Wang, Sucheng Ren, and Hang Zhao. On feature decorrelation in self-supervised learning. 2021 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 9578-9588, 2021b.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. Advances neural information processing systems, 31, 2018.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. Proceedings of the Sth International Conference on Learning Representations, 2017.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical Report 0, University of Toronto, Toronto, Ontario, 2009.
Ya Le and Xuan S. Yang. Tiny imagenet visual recognition challenge. 2015.
Ze Liu, Han Hu, Yutong Lin, Zhuliang Yao, Zhenda Xie, Yixuan Wei, Jia Ning, Yue Cao, Zheng Zhang, Li Dong, Furu Wei, and Baining Guo. Swin transformer v2: Scaling up capacity and resolution, 2021.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness SGD in modern over-parametrized leaming. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3325-3334. PMLR, 10-15 Jul 2018.
Hartmut Maennel, Ibrahim M Alabdulmohsin, llya Tolstikhin, Robert Baldock, Olivier Bousquet, Sylvain Gelly, and Daniel Keysers. What do neural networks learn when trained with random labels? Advances Neural Information Processing Systems, 33:19693- 19704, 2020.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. Proceedings of The 28th Conference on Learning Theory (PMLR), 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally-normaaizedd margin bounds for neural networks. International Conference on Learning Representations (ICLR), 2018
Kento Nishi, Ding, Alex Rich, and Tobias Höllerer. Augmentation strategies for learning with noisy labels. 202/ IEEE/CVF Conference on Computer Vision and Puttern Recognition (CVPR), pp. 8018000880000 8027, 2021.
Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu. Making deep neural networks robust to label noise: A loss correction approach. 2017 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 2233-22--222 2017.
Hieu Pham, Zihang Dai, Qizhe Xie, Minh- Taan-ThangTun Luong, and Quoe V. Le. Meta pseudo labels. In IEEE Conference Computer Vision and Pattern Recognition, 2021.
12

---

Published as a conference paper at ICLR 2023
Vinaychandran Pondenkandath, Michele Alberti, Sammer Puran, Rolf Ingold, and Marcus Liwicki. Leveraging random label memorization for unsupervised pre-training. Workshop of Integration of Deep Learning Theories at Conference Neural Information Processing Systems (NIPS), abs/181 1.01400, 2018.
David Rolnick, Andreas Veit, Serge Belongie, and Nir Shavit. Deep learning is robust to massive label noise. arXiv preprint arXiv: 7001170694 2017.
Amartya Sanyal, Puneet K. Dokania, Varun Kanade, and Philip Torr. How benign is benign overfit- ting? In International Conference on Learning Representations, 2021.
Nikunj Saunshi, Jordan Ash, Surbhi Goel, Dipendra Misra, Cyril Zhang, Sanjeev Arora, Sham Kakade, and Akshay Krishnamurthy. Understanding contrastive learning requires incorporat- ing inductive biases. Proceedings of the 39th International Conference Machine Learning, (ICML), 2022.
recognition. International Conference on Learning Representations (ICLR), 2014. Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image
Hwanjun Song, Minseok Kim, Dongmin Park, Yooju Shin, and Jae-Gil Lee. Learning from noisy labels with deep neural networks: A survey, 2020.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting, Journal of Machine Learning Research, (5(56):1229-199))
2014.
V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264-280, 1971. doi: 10. 1011113/111010 116025.
Zixin Wen and Yuanzhi Li. Toward understanding the feature learning process of self-supervised contrastive learning. In International Conference on Machine Learning, pp- 11112-11122. PMLR, 2021.
Sen Wu, Hongyang R. Zhang, Gregory Valiant, and Christopher Ré. On the generalization effects of linear transformations in data augmentation. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
Lechao Xiao and Jeffrey Pennington. Synergy and symmetry in deep learning: Interactions between the data, model, and inference algorithm. arXiv preprint arXiv:2207.04611. 2022.
Jiahui Yu, Zirui Wang, Vijay Vasudevan, Legg Yeung, Mojtaba Seyedhosseini, and Yonghui Wu. Coca: Contrastive captioners are image-text foundation models. Transactions Machine Learn- ing Research, 2022.
Jacob Zavatone- Veth, Abdulkadir Canatar, Ben Ruben, and Cengiz Pehlevan. Asymptotics of repre- sentation learning finite bayesian neural networks. Advances in neural information processing systems, 34:24765-244 -27777, 2021.
Jure Zbontar, Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self-supervised learning via redundancy reduction. In Proceedings of the 38th International Conference Ma- chine Learning (ICML.
Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer. Scaling vision transformers, 2021.
Chiyuan Zhang, Samy Bengio. Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Repre- sentations (ICIR), 2017.
Hongyi Zhang, Moustapha Cisse, Yann N. Dauphin, and David Lopez-Paz. mixup: Beyond empiri- cal risk minimization. In International Conference Learning Representations, 2018.
13

---

Published as a conference paper at ICLR 2023
Junjie Zhang, Lingqiao Liu, Peng Wang, and Chunhua Shen. To balance not to balance: A simple- yet-effcttee approach for learning with long-tailed distributions. arXiv preprint 1rXi::1112.044866 2019.
Xuanyang Zhang, Pengfei Hou, X. Zhang, and Jian Sun. Neural architecture search with random labels. 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 10902-10911, 2021.
14

---

Published as a conference paper at ICLR 2023
DATASET
MODEL.
RANDOM
RANDOM + DA
CLEAN
CLEAN + DA
INIT
RexNei18
29.8
77.0
83.9
92.5
43.8
CIFARIO
VGG11
23.9
71.0
81.8
89.8
10.7
ResNet18
10.3
44.2
52.3
69.6
18.5
CIFARI00
VGG11
12.7
47.5
51.5
61.4
16.9
RexNet18
4.7
33.9
39.5
47.7
TinylmageNet
VGGIT
3.7
22.3
33.0
41.3
Table 4: Linear probing accuracies (in percentage) of the embeddings for various datasets under different settings. DA refers to training under data augmentation. INIT refers to the performance at initialization.
A LINEAR PROBING RESULTS
We replicate results of Table 4 but with linear probing instead of K-NN probing of the embed- dings, for the same models and the same datasets. In this train linear classifier top of the embeddings of the true (unaugmented) training data and evaluate on the left-out test set. We see that random without data augmentation although above guessing is still below the performance initialization.
B CONNECTION TO SELF-SUPERVISED LEARNING
In this section, we investigate the connection between non-contrastive SSL (Hua et al., 2021b; Grill et al., 2020; Chen & He, 2021) and training with random labels on the mean squared error (MSE) loss. We start with the following result:
Lemma B.1 Fix B N vectors 31
EB E Rd and a E Rd. Then it holds that
B
B
1
a.
all
l|a
B
2B
B
+,1=
1=1
Proof: We simply expand the first term on the right-hand-side:
B
B
1
23 111
x a + a a-aaxpp 11
2B
2B2
1
1-==1
1
[2 all² + || all2-
- 2(x; - -a)
2B2
1,1=1
[2
all
(x; a)²(zz a)
B i-j=1
B
all2
- ||a|
1
Σ
x æj
+
Σ
a"
B
B2
B
i=l
On the other hand, we have that
la
1
|||||
n
/ æj
2 n
Σ
a
T
B
B2
{,==
Hence we see that
Σ
x
2|
1
Σ
x
a
2
||a
1
Σ
x;
||
2B2
B
B
15

---

Published as a conference paper at ICLR 2023
and re-arranging terms concludes the proof.
We now apply this result in the case where the label plays the role of a and x play the role of different augmentations. Let us thus consider B augmentations Ti, .' and è N samples 21,.... In I Moreover we have some labels y1...., Yn Æ that could be completely random. Using the previous result we can write the (random) supervised loss (assuming mean- squared error) as follows:
Theorem B.2 Denote the supervised loss under data augmentation
1 Iupeer (0)
BB ΣΣ
[[o(Ta(a))) yy:l
Then decompose into the following two terms,
L super (0)
1 71
B Σ fo (Ta (z.)))
yi
Bn i=1 1,b
1=1
=lu(())20
Bins (0)20
Notice that in (O), we group augmentations of the same input together, measuring thus how invariant a given model fe w.r.t. to the augmentations. This is the positive signal illustrated in the thought experiment in Fig. 4. Interestingly, minimizing Inv(0) is core ingredient for so-called non-contrastive supervupe learning methods (Hua et al., 2021b; Grill et al., 2020; Chen & He, 2021).
The bias term on the other hand influenced by the random labeling. To better understand the bias term, define N₂ {i E [l,...,n} y: ), i.e. all samples that have label c. Furthermore, let fo(2;) 1
B Ex= fo (a:)) be the model average over all the B augmentations. We can show that we can express the bias
Bias 0)
1 Σ
Σ cll
Cc fo(x:))
Notice that as in random labeling experiment, the number of classes C' can be considered hyperparameter. hence if we choose C' >> n, then each sample #1,..., Iy is assigned a different class with high probability. this case, the "bad bias" given by assigning the same label to samples of different classes vanishes, and one has:
1 -1 e((ea-o(zz))) n
Bias ())
where w.l.o.g we have re-ordered the labels such that the i-th label is assigned to sample æ;, In this limiting case, the bias term represents a contrastive term that encourages the average model (x,) to be different from the other samples x, I; and their augmentations. In this sense, this term can be related to contrastive SSL. On the other hand - unlike contrastive SSL - the distance between the average models of two datapoints cannot be arbitrarily large, and once the loss is driven to zero,
Bias () = 0 and it is trivial to see that [o(x)) fo( fo( =
We refer the reader to Appendix C for experiments with varying number of classes. We observe that, as hypothesized, the influence of the bias diminishes and performance increases as a function of the number of classes C.
C MORE EXPERIMENTS
In the following present more empirical evidence that may help better interpret findings.
Role of the Projector. We visualize Fig. the effect of varying the size the hidden layer in the projector. There is threshold under which learning is impossible (or at least very hard given
16

---

Published as a conference paper at ICLR 2023
fixed computational budget). Surprisingly, using larger projector seems beneficial beyond the point where we manage to decrease the loss significantly and achieve memorization of the original dataset.
Projector hidden d224
0.7
524288
393216
393216
0.6
262144
K-NN accurecy
65536
16394
0.4
4096
1924
258
Epochs
Figure 7: Nearest-neighbour probing accuracy as function of the size of the projector.
The role of the number of random classes. So far we assigned to each sample random label in RC, where C is the number classes in the original dataset. In principle, increasing the number of classes decreases the strength of the noise provided to the model. We verify this in Fig. 8, where we vary the number of possible classes that each sample is randomly assigned to. In the extreme case, every sample is assigned its unique class label yı E₁ where E I" recovering the result of Dosovitskiy et al. (2014) which we refer to as 'Per samplc'. We observe that while increasing number of classes performance improves (as less noisy assignments made). We refer the reader to Appendix for more formal connection.
0.9
Per sample
5203
0.7
2003
KNNN probing
0.6
500
0.4
baiion
100
6.2
10
Random guesdnng
6.1
Epochs
Figure 8: Nearest-neighhour probing accuracy as a function of the number of classes.
Transferability. Features learnt with random labels are also useful when evaluated different datasets. In Fig. 9 on the hight-hand-side we transfer the features learnt on CIFARIO, to CIFAR100 and STLIO (Coates et al., 201 1). We observe that highlighting the strength of the features learnable under random labels. Moreover, we see that using data augmentation is crucial when label noise is high without data augmentation
achieve strong downstream performance,
17

---

Published as a conference paper at ICLR 2023
Lobel
Figure 9: Nearest-neighbour probing accuracy for transfer learning to different datasets function of label noise. A R trained based on random labels on CIFARIO with (right) and without (left) data augmentation.
Dependence on noise and speed of convergence. Augmentations have been shown to be especially useful under the presence of heavy label noise. In Fig. 10 visualize the performance achieved during the first stage of training under varying level of label noise. Label noise specifies the percent- age of labels that are randomly permuted versus the percentage of labels that are kept the same.
8.0
65%
50%
40%
40%
0.2
5%
0%
(a) CIFARIO
(b) TinylmageNet
Figure 10: Nearest-neighhour probing during training for the CIFARIO and TinylmageNet datasets during training.
Effect on the strength of the augmentation. Although malign memorization gets impossible as the number of augmentations keeps increasing, the strength the augmentations themselves plays role on the generalization achieved. The strength of the augmentation basically dictates the strength of the invariance that the model has to learn, which also correlates with the quality of the features learned seen in Fig. 11. To control strength use the strength level of RandAugment (Cubuk et al., 2020). We clearly see that stronger augmentations are beneficial for the quality of the embed- dings, underlining the fact that invariance indeed plays key role in benign memorization.
18

---

Published as a conference paper at ICLR 2023
Augmentalion byoe
Strength
Strength 6
0.5
KNN accurecy
Strength 5
0.4
Strength
Strength 3
0.3
Strength
Strength
1000
1250
1500
1750
2000
Epochs
Figure 11: Weirest- probing accuracy when trained on random labels with varying strength of (infinite/online) augmentations.
Varying levels of label noise. Previous works have highlighted the importance of augmentations in the presence of high-label noise. We examine the relationship between label noise and generalization both with and without augmentations in Fig. 12. We see that while data augmentation is not so crucial for clean labels, its role becomes more and more critical as we increase the amount of label noise. Without augmentations, we suffer from strong decrease performance, eventually ending reach complete label noise. On the other hand, using augmentations
with random guessing stabilizes this decay and we still achieve strongly non-trivial performance even in the setting of complete label noise.
Training augmentations
Training augmentations
0.8
K-NN Probing
0.2
Random quessing
20%
40%
Label noise
Figure 12: Neageot-neighhour probing accuracy when trained varying levels of label noise with and without augmentations.
D MORE DISCUSSION
D.1 MODEL'S CAPACITY
Here we mathematically introduce the concept of capacity of model class trained with Gradient Descent (GD) that was informally used the main text. We remark that similar definitions have been explored in prior work (Arpit et al., 2017).
Definition D.I Consider æi,..., Fn for n N in general position and a fixed number of classes C. Given a labeling S {ax,, {2 let As(S) C O denote the of solutions reachable by GD
19

---

Published as a conference paper at ICLR 2023
with computational budget t. We define the capacity Ct of the model class (fe 0 ) as
C. = sup(n NJ VA 30 E A.(5) s.1. memorizes S)-
While similar to standard measures such as the VC-dimension (Vapnik & Chervonenkis, 1971), the capacity defined here depends the learning algorithm (including the computational budget t) and is thus always smaller than the corresponding VC-dimension.
D.2 RELATED WORKS
We give a more detailed discussion on the related work of Dosovitskiy et al. (2014) since although very different, a quick reading of it mislead the reader into finding it more similar than is actually the case. The authors in Dosovitskiy et al. (2014) consider dataset without labels, and sample N patches from different images, leading examples {II..... ØN }. augmentations are produced for each sample and all of those augmentations get the same label i. There are thus N so-called surrogate classes. When varying the number of surrogate classes in Figure 3, the authors also adjust the number of samples used in the experiments, if the authors use 8000 surrogate classes, they also use 8000 patches, if they use 16000 classes they also use 16000 patches. At no point do different samples share the same label the dataset size is not preserved in each experiment. This is in contrast to our experiment in Fig. where we indeed vary the number of classes and assign the same labels to several samples. Having label per sample of course strongly differs from only having 10 labels (or C, depending on the dataset). First, achieving strong performance in this setting is far more difficult (and thus surprising) since by reducing the number of classes drastically, introducing a bias into the dataset as examples with different underlying labels might suddenly share the same label. We refer to the thought experiment Sec. 5 for more details and remark that this reasoning does not apply for Dosovitskiy et al. (2014) precisely due to the fact that they use the same number of labels as samples. Second, our setup recovers the well-studied setting of random labels and thus memorization, connecting hence two very different fields, further distinguishing our results from Dosovitskiy et (2014) that were obtained in the context of self-supervised learning.
D.3 INVARIANCE MEASURE
Here we give a bit more background and motivation for the invariance measure
Er, ( ((2
T(:; q, T)
Exy (00)>1l(0)) (g)()) (12)
This measure is inspired by loss functions often used in self-supervised learning where we aim to explicitly optimize for invariance to different augmentations (Chen et al., 2020c). We use normalization term to ensure that there is diversity between predictions of different, unrelated samples in order to rule out that simple collapse (i.e. constant) representations do not achieve a high invariance.
E TOY EXAMPLE
To better understand the role of augmentations with respect to the capacity of the model we devise simple toy setting.
We consider samples Fi...., In E Rd that belong to one the C underlying classes. We select the first d1 < d coordinates to denote the true class assignment 2; uniformly selected from the set {1...., C). by sampling from a mixture of Gaussian distributions and let the rest d, dimensions correspond to noise. More specifically:
x [idd 21 N(Hi; Σ1),
Dijdi:] ~N(0, Ez).
20

---

Published as a conference paper at ICLR 2023
1.0
150
100
Number samples n
80
60
Capacity
0.6
B
45
35
0.2 random guessing
5
oo
12
Pt
16
15 20 24
28
32
48
64
128
256
512
1024
Number augmentations
Figure 13: K-NN probing for the downstream class assignment on unseen test points for the toy example, after training on random labels.
With μe; denote the cluster centers that are sampled randomly. In this case, consider augmen- tations of the samples:
2 = a, where (jdd,) = and a'd::] ~ ~N(0 Ez).
As set the covariance matrices Σ3 Σg 10 o² where I is the identity matrix. It is obvious that learning invariance for this task under these augmentations leads to embeddings that ignore the noise subspace. We employ in this case a simple linear encoder hw (ar) Wa, with W paxd
1
As projector we use gv = >K
x
Uall
L. Here is one hot encoding sampled
Ej=1
| Uyy
randomly from the set fei....,ecl cc We choose such projector as it is not difficult to verify that in the limit case where gv (x) larg min, ||--,e/|- r.rll. we have an upper bound the capacity of the model, based on the number K of the vectors used by the projector. Additionally, its non-linear nature proposes that any possible invariance learning will occur at the encoder. In Fig. we visualize the K-NN probing for the downstream task of correctly predicting the clean label of unseen test samples, after training on random labels. By varying the number samples n and augmentations B available, we directly control whether full memorization can take place not. When the number of samples n is smaller than 6. where is the capacity of the model, full memorization is possible, which discourages any feature learning, leading to bad generalization.
F EXPERIMENTAL SETUP
We conducted experiments the classic CIFAR-IO, CIFAR-100 and Tinylma- geNer datasets, using the default dataset splits. For completeness, we present in Table statistics regarding these datasets.
Dataset Details:
21

---

Published as a conference paper at ICLR 2023
Dataset
Examples in train split
Examples in test split
Number of classes
CIFAR-10
50000
10000
10
CIFAR-100
50000
10000
100
'inylmageNer 3
100000
10000
200
Table 5: Statistics for the datasets used.
Architecture: As commonly done for smaller size images (Chen & He, 2021; Hua et al., 2021a) we use a variant of the ResNer18 architecture, where the max-pooling layer removed, and the first convolution is modified to have a kernel size of 3 and stride of 1. We also remove the last fully con- nected layer, as we replace it with our projector. We provide more details about the hyperparameters used in Table 6. For the experiments on VinylmageNet, we rescale images to size of 64 x 64 and additionally restore the stride of the first convolution to the value 2. We apply the same modification to VGG when trained TinylmageNet.
Hyperparameters
Value (0.08, I)
Random cropping scale
Augnentations
Horizontal flip probability
0.5
Color-Jittering
(0.8, 0.8, 0.8, 0.2) 0.2
Grayscale probability
Mixup
yes
Parameters
image-size
32/64
clip-norm
'none'
dropout
'none'
Projector size
65536
Projector MLP normalization
'none'
Learning rate
4e 46-3
Learning rate scheduler
'none' (0.9, 0.999)
Training
Adam (31,82)
Batch size
256
Weight decay
0.0
Loss
'MSE-loss'
Table 6: Hyperparameters for the random labels experiments.
22


Reviews:
[{"review_id": "hsMbVvhmam", "reviewer": "Reviewer_dZQx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "**Strength**\n\n1. This paper identifies an interesting phenomenon called benign memorization, which has not been systematically studied in the past. \n2. This paper analyzed this phenomenon from various aspects, including identifying where memorization happens, and potential explanation from the perspective of effective model capacity.\n\n**Weakness**\n\n1. 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).\n\n2. 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. \n\n    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.\n    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.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "W-EpsmdENTu", "reviewer": "Reviewer_CAZe", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. ", "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. ", "strength_and_weaknesses": "* Strengths: \n    * 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. \n    * The paper empirically demonstrates that the embeddings learned under random noise are useful, and memorization happens in the last layer in their setting.\n    * 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). \n    * 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.\n    * 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.\n\n\n* Weaknesses: \n    * 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. \n    * 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.\n    * 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). \n   * 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.\n   * 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "Tc-1l6CxYA", "reviewer": "Reviewer_rsqh", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.\n", "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.\n\nUPDATE: 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.", "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.\n\nHowever, 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].\n\n1. 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.\n\n2. 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]).\n\n3. 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?\n\n\n### Minor comments\n\n* 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.\n\n* “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.\n\n* 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.\n\n* 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.\n\n* Typos to fix: “totice” → “notice” and ““applied3” → “applied”.\n\n* In Figure 6, the dashed curve values can be presented on the right y-axis.\n\n* The main findings of the experiments presented in the appendix can be summarized concisely in the main text.\n\n### References\n\n[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.\n\n[2] Gilad Cohen, Guillermo Sapiro, and Raja Giryes. DNN or k-NN: That is the generalize vs. memorize question. ArXiv, abs/1805.06822, 2018.\n\n[3] Alexey Dosovitskiy, Jost Tobias Springenberg, Martin Riedmiller, and Thomas Brox. Discriminative unsupervised feature learning with convolutional neural networks. In NeurIPS, 2014.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "CJArNGdfSB", "reviewer": "Reviewer_ZaD4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "summary_of_the_review": "In general, I think this is a good paper meaningful to both theory and empirical researchers.", "strength_and_weaknesses": "Strength:\n1. The paper is well-written and easy to follow. The idea is well-motivated from recent benign overfitting papers.\n2. The discovered phenomenon is very interesting and provides useful insights to theory works.\n\nWeakness:\n1. How does the augmentation magnitude affect the results? In my experience, if the augmentation is too strong, the network cannot fit the data.\n2. 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.\n3. In addition to K-NN, will training a linear classifier on fixed feature mappings (learned from random labels) also exhibit similar results?\n4. 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.\n\n[1] To Balance or Not to Balance: A Simple-yet-Effective Approach for Learning with Long-Tailed Distributions", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster