Title: DOWNSAMPLING LEADS TO IMAGE MEMORIZATION IN CONVOLUTIONAL AUTOENCODERS

Abstract: Memorization of data in deep neural networks has become a subject of significant research interest. In this paper, we link memorization of images in deep convolutional autoencoders to downsampling through strided convolution. To analyze this mechanism in a simpler setting, we train linear convolutional autoencoders and show that linear combinations of training data are stored as eigenvectors in the linear operator corresponding to the network when downsampling is used. On the other hand, networks without downsampling do not memorize training data. We provide further evidence that the same effect happens in nonlinear networks. Moreover, downsampling in nonlinear networks causes the model to not only memorize just linear combinations of images, but individual training images. Since convolutional autoencoder components are building blocks of deep convolutional networks, we envision that our findings will shed light on the important phenomenon of memorization in over-parameterized deep networks.

1. INTRODUCTION AND RELATED WORK:

As deep convolutional neural networks (CNNs) become ubiquitous in computer vision due to their applicability and strong performance on a range of tasks (Goodfellow et al., 2016) , recent work has begun analyzing the memorization properties of such networks in classification. For example, Zhang et al. (2017) show that popular CNNs can achieve almost zero training error on randomly labeled datasets, indicating that CNNs have the capacity to "memorize" large training data sets. Arpit et al. (2017) and Sablayrolles et al. (2018) build on the experiments from Zhang et al. (2017) to better understand and evaluate the extent to which CNNs memorize training data. Arpit et al. (2017) show that CNNs, when trained on large datasets, are able to learn patterns from realistic data before memorizing training images. Sablayrolles et al. (2018) present experiments on "membership inference" (i.e. determining whether an image was used during training) and conclude that modern architectures are capable of "remember[ing] a large number of images and distinguish[ing] them from unseen images".

Although the above methods analyze memorization in the classification setting, they do not provide a mechanism through which memorization of training data occurs. We here present downsampling as one mechanism by which deep CNNs memorize specific training images. We will focus our study on the memorization properties of linear and nonlinear fully convolutional autoencoders. The architectures we use (such as U-Net, (Ronneberger et al., 2015) ) are commonly employed in imageto-image tasks, see e.g. Ulyanov et al. (2017) . However, we will use these architectures only in the autoencoding framework. We primarily focus on autoencoders (Baldi, 2012) for the following reasons: (1) components of convolutional autoencoders are building blocks of many CNNs; and (2) layerwise pre-training using autoencoders is a technique to initialize individual layers of CNNs to improve training (Bengio et al. (2007) , Erhan et al. (2010) ). It is important to note that there are many potential solutions to the autoencoding problem when using over-parameterized autoencoders. In particular, in the linear case, these models may range from learning the (full rank) identity function (which has 0 error in the autoencoding task) to low rank solutions where each training example corresponds to an eigenvector with eigenvalue 1. Thus, understanding how autoencoders learn is of interest in order to gain insights into how deep CNNs memorize training data.

Figures 1a and 1b provide two examples of memorization: A typical U-Net architecture (the same as e.g. used in Ulyanov et al. (2017) for large hole impainting) when trained on a single image "memorizes" the training image in the sense that for any input, the output always contains the training image (even if the input is random noise or an arbitrary white square). This paper provides a mechanism for this phenomenon.

The outline is as follows: After introducing some notation in Section 2, we will show in Section 3 that memorization is tightly coupled with downsampling and also occurs in the simpler setting of linear autoencoding CNNs. In the linear setting, the neural network corresponds to matrix multiplication. In Section 4, we show how to extract this matrix representation and we provide our main conjecture, namely that linear combinations of the training images are stored as eigenvectors of this matrix, whose rank is given by the dimension of the span of the training set. We also provide strong evidence for this conjecture on 2 × 2 images. In Section 5, we analyze the eigenvalue decay and show in various examples that using downsampling linear CNNs, linear combinations of the training examples are stored as eigenvectors with eigenvalues close to 1. Finally, we return to the nonlinear setting in Section 6, providing evidence that memorization is an even stronger phenomenon in nonlinear networks, since the actual training images (in contrast to linear combinations of training images) are memorized. We end with a short discussion in Section 7.

2. NOTATION:

In this section, we introduce the mathematical framework for our work and highlight two different functions learned by autoencoding CNNs, namely the identity function and the point map.

We denote a training set of n square images by X = {x 1 , x 2 , ..., x n }, where each x i ∈ R c×s×s with c being the number of color channels (or filter channels) and s denoting the width and height of an image. We will focus on convolutional autoencoders, i.e., CNNs trained to map between the same image. In particular, we will consider linear CNNs, by which we mean convolutional autoencoders with layers being either nearest neighbor upsampling or convolutional with kernel size 3, zero padding, no activation functions, and no biases. To simplify the computations in Section 4, we assume throughout that the input image as well as the stride size are a power of 2.

We denote the function learned by a CNN on the training set X by C X : R c×s×s → R c×s×s .

The training procedure minimizes a given loss function between the input image and its reconstruction by C X . We use the mean squared error loss throughout; thus the loss function is given by

i=n i=1 1 ncs 2 (C X (x i ) -x i ) 2

, where subtraction and exponentiation are taken elementwise. For linear CNNs, we denote the matrix corresponding to C X by A X . Denoting the vectorized (or "flattened") version of an image y ∈ R c×s×s by y

f ∈ R cs 2 , then A X satisfies A X y f = (C X (y)) f .

In this work, we identify and analyze an architectural mechanism that is able to fundamentally alter the function C X learned by an autoencoding CNN on a given training set. The following two functions will play an important role in the subsequent analysis: (1) the identity function given by C X (y) = y for any y ∈ R c×s×s and (2) the point map given by C X (y) = C X (x 0 ) for any y ∈ R c×s×s , where x 0 is a particular element in span C X (X) where span C X (X) = span {C X (x i ), 1 ≤ i ≤ n}. An extreme form of memorization occurs when a CNN learns the point map on a training set of size one, i.e., it maps any image to the same fixed image.

3. DOWNSAMPLING: A MECHANISM FOR MEMORIZATION:

In this section, we will illustrate how downsampling acts as a mechanism for learning the point map in deep CNNs. In particular, we will show that even if a downsampling network has the capacity to learn the identity function, it prefers to learn the point map.

We consider the linear CNNs defined by Network ND (non-downsampling) and Network D (downsampling) in Figure 2a . Both networks employ 128 filters in each convolutional layer in all but the last layer, which contains 3 filters. The two networks only differ by the property that Network D uses filters of stride 8 in the first layer to downsample the image and then later uses nearest neighbor upsampling with scale factor 8 to rescale the image, while Network ND does not perform any downsampling. In concordance with the severe downsampling from 224 × 224 to 7 × 7 images performed by ResNet and VGG (He et al. (2016) ; Simonyan & Zisserman (2015) ), Network D downsamples from 32 × 32 to 4 × 4 images. However, we will show in Section 5 that the same memorization phenomenon is also observed in networks that only downsample using multiple convolutional layers of stride 2 as is done in U-Nets (Ronneberger et al. (2015) ). In the examples, the networks were initialized using the default in the PyTorch deep learning library (Paszke et al., 2017) , namely each layer's weights were drawn i.i.d. from a uniform distribution U(-a, a) with a = 1/ √ P where P is the number of parameters in that layer.

Both networks were trained for 2000 iteration on a single 3 × 32 × 32 image from CIFAR10 (Krizhevsky, 2009) of a frog. Network ND reconstructed the digit 3 with a training loss of 10 -4 and Network ND with loss 10 -2 . We then applied the trained networks to test images consisting of both realistic images and random images with each pixel in the image being drawn from the standard normal distribution. As shown in Figure 2c and 2b, although trained on the same input for the same number of iterations Network D (with downsamling) learned the point map while Network ND (no downsampling) learned the identity function up to sign. The possible sign flip is a consequence of using no biases. In fact, this contrasting behavior is very robust throughout the training process. In Figure 3 , we see that regardless of when we stop training, even after only 10 iterations, Network D learns a point map, while Network ND learns a function visually similar to the identity map.

One may conjecture that the memorization phenomenon that occurs using Network D could be due to the small number of filters in the downsampling layer, so that not all the features from the input could be preserved and the network would not be capable of learning a full rank identity map. This is not the case. To demonstrate that this is in general not the reason why downsampling networks learn a point map, we next present a downsampling network which, as we show, has the capacity to learn the identity function, but still prefers to learn the point map instead as the result of optimization. Example. Consider the linear CNN defined by the small downsampling Network DS presented in Figure 4a , which is trained on a single 1×2×2 image for 2000 iterations. Figure 4b shows that there exists an initialization such that the network learns the identity function. A full description of how we computed this manual initialization is provided in Appendix A. In contrast, as shown in Figure 4c initializing Network DS with the default PyTorch uniform distribution results in the point map. This provides the first example showing that even though the network has the capacity to learn the identity function, it prefers to learn a point map using the default PyTorch initialization. We observed the same effects using the Xavier uniform initialization, which is based on the assumption that activations are linear (Glorot & Bengio (2010) ). However, the results are not observed for linear networks when using Kaiming initialization, which is expected since this initialization is meant for nonlinear networks with ReLU/PReLU activations (He et al. (2015) ). In Appendix E, we show that nonlinear networks memorize training images under any of these initializations.

4. MATHEMATICAL ANALYSIS OF MEMORIZATION IN LINEAR CNNS:

We now turn to extracting and analyzing the linear operator that describes the function learned by the linear CNN. While the full algorithms for extracting the matrix A X from the network are described in Appendix B, we here provide intuition for this procedure. Since the matrix A X can be decomposed as a product of matrices, one for each layer, it suffices to provide intuition for converting a general convolutional layer and a general upsampling layer into a matrix. We then discuss our main conjecture and proposition linking the eigenvectors of A X to the mechanism of memorization.

4.1. EXTRACTING THE LINEAR OPERATOR FROM A LINEAR CNN:

To simplify notation, we assume that the inputs and outputs are already zero padded images (with 1 layer of zero padding on each side), i.e., the original images lie in R c×(s-2)×(s-2) such that the images after vectorization and zero padding lie in R cs 2 . The convolutions all consist of kernels of size 3 × 3, 1 layer of zero padding. Consider a particular convolutional layer consisting of f filters, stride size t, kernel volume f × 3 × 3, and 1 layer of zero padding, which operates on an incoming zero padded vectorized image of f s 2 voxels, where f is the depth and s the width and height of the incoming image. Assuming that the stride and image sizes are powers of 2, it follows that (s -2) is a multiple of t. Hence the matrix corresponding to the operator of this particular layer is of size f ( s -2 t + 2) 2 × f s 2 , where s -2 t + 2 corresponds to the width and height of the output after striding and zero padding. The matrix itself is circulant-like, where the zero padding must be carefully accounted for by additional shifts and rows of zeros. A particular example is shown in Appendix B.

Next, we provide intuition on how to extract the matrix corresponding to the nearest neighbor upsampling operation. The full algorithm together with an example is given in Appendix B. Given a vectorized zero-padded image of f s 2 voxels as input, then nearest neighbor upsampling with scale factor k corresponds to a matrix of size f (k(s -2) + 2) 2 × f s 2 , where (k(s -2) + 2) comes from having to scale only the non-zero-padded elements of the representation and adding 2 for the new zero padding. This matrix is composed of blocks of circulant-like matrices consisting of one-hot vectors, where blocks of s identical rows are shifted by 1 element. Finally, the full operator A X for a linear network C X is obtained by multiplying the matrices corresponding to each layer.

4.2. SPECTRAL ANALYSIS OF LINEAR OPERATOR:

Being able to extract the linear operator A X from a linear CNN is critical for analyzing the mechanism of memorization, since it allows an examination of its eigenvalues and eigenvectors. Note that A X operates on the space of c × s × s images. Hence every eigenvector (when stripped of zero-padding and reshaped to c × s × s) represents an image in this space. However, since A X is in general not symmetric, eigenvectors can be complex and hence the real and imaginary components of the eigenvectors represent separate images in the original space.

We can easily obtain a bound on the rank of A X : Since A X is given by a product of matrices, one for each layer in the linear CNN, the rank of A X is at most equal to the rank of the minimal rank matrix in the factorization of A X . We denote this number by r min . We now present our main conjecture.

Conjecture. Let X = {x 1 , . . . , x n }, x i ∈ R c×s×s , be a training set of images of size c × s × s.

(a) If A X is the linear operator of a downsampling network trained to zero loss, then rank(A X ) = min (dim(span (X), r min )),

where all eigenvalues are equal to 1 and the corresponding eigenvectors are linear combinations of the input training images.

(b) If A X is the linear operator of a non-downsampling network trained to zero loss, then

min (dim(span (X), r min )) ≤ rank(A X ) ≤ cs 2

. In other words, we conjecture that linear downsampling networks learn a low rank solution when the number of linearly independent training examples is not sufficiently large (i.e. larger than cs 2 ), even when they have the capacity to learn the identity function. In particular, we conjecture that the rank is given by the dimension of the span of the training images. Most importantly, we conjecture that the mechanism of memorization in downsampling networks is by storing linear combinations of the training images as eigenvectors of the linear operator. On the other hand, we conjecture that linear non-downsampling networks learn a much higher rank solution, thereby often rendering the solution visually indistinguishable from the identity function. Our conjecture also implies that when training a linear downsampling CNN on images of size 3 • 224 • 224, which corresponds to the input image size for VGG and ResNet (He et al. (2016) , Simonyan & Zisserman (2015) ), the number of linearly independent training examples needs to be at least 3 • 224 • 224 = 153, 228 before the network can learn the identity function. However, assuming that realistic images lie on a low-dimensional manifold, this conjecture indicates that a linear downsampling network will learn a basis for the low-dimensional manifold instead of the identity when trained on sufficiently many realistic images.

Before providing empirical evidence for our conjecture in Section 5, we end this section by summarizing our theoretical evidence in the following proposition showing that the network in Figure 4a can learn solutions of all ranks 1 through 4 for 1 × 2 × 2 images depending on the dimension of the span of the training set. Proposition. The linear Network DS presented in Figure 4a can learn a linear operator of rank min (dim(span (X), 4)) with 1 ≤ dim(span (X)) ≤ 4.

The proof is given in Appendix C. Note that this proposition does not imply that A X must obtain rank r = min (dim (span (X), 4)) for all training sets X on 1 × 2 × 2 images, but rather that the conjecture holds for any example of training sets that we tried, in particular also training sets covering each possible nonzero value of min (dim (span (X), 4)).

5. EMPIRICAL EVIDENCE FOR MAIN CONJECTURE:

We now provide empirical evidence for our main conjecture by analyzing the operator A X for networks trained on CIFAR10 color images (which have width and height 32). First, we show that when training on one or two images respectively, a downsampling network learns an operator that has very low effective rank with the top eigenvector(s) corresponding to the training image(s). On the other hand, we show that a non-downsampling network trained on the same data learns an operator with much higher rank, closer to the full dimensionality of the data. Finally, we will train downsampling networks on tens to thousands of images from a single class of CIFAR10 and present the rank of the learned solutions in Appendix D.

All of our downsampling networks downsample using 3 convolutional layers with stride 2 and then upsample using a 1 nearest neighbor upsampling layer with scale factor 8. The general architecture is shown in Figure 5 . Importantly, we note that if we use such a network on color CIFAR10 images, we need at least b = 3•8•8 = 192 filters in order to be able to learn the identity function since otherwise r min < 3 • 32 • 32. Our non-downsampling networks have the same convolutional layer scheme as the downsampling networks. We denote a downsampling (respectively non-downsampling) network with a filters on upsampled representations and b filters on downsampled representations by D a,b (respectively N D a,b ).

The networks are initialized using the default initialization in PyTorch (Paszke et al. (2017) ), trained using the Adam optimizer (Kingma & Ba (2015) ) with learning rate 10 -4 , and trained until the loss decreased by less than 10 -4 or for 20, 000 epochs. Note that we disregard overfitting in training, since we expect an overfitted autoencoder to learn the identity function. As pointed out in Figure 3 , the memorization effect is robust throughout the training process. However, in this case, we wish to train until the training error is sufficiently low (i.e. around 10 -3 ) so that we can understand the rank of the operator in relation to our conjecture.

Figure 6 shows the results for various downsampling and non-downsampling networks when trained on 1 ≤ k ≤ 2 images. As shown in Figures 6a and 6b , in both cases Network D 64,192 stores the k images (up to a shift in the color channels) as eigenvectors with eigenvalues close to 1 and produces roughly a rank k solution. In particular, when trained on a single picture of a plane from CIFAR10 this network stores the training image as the real component of the top eigenvector; it is an inverted color image of the plane and the rank of the learned solution is approximately 1 (Figure 6a ). When trained on a picture of the plane and a car, the top two eigenvectors are linear combinations of the plane and the car with the plane having inverted colors (Figure 6b ). In fact, the plane is more visible in the complex component of the second eigenvector while the car is more visible in the real components. The learned solution is of rank approximately 2 with the top two eigenvalues being complex conjugates (hence having the same magnitude). On the other hand, Figures 6c and 6d show that training the non-downsampling network N D 4,4 on a single image or on two images results in a higher-rank solution, with rank and spectrum being independent of k.

When training on k > 2 images from different classes of CIFAR10, our conjecture stipulates that the rank of the learned solution indicates the dimension of the span of the training set. Since visu- 

6. MEMORIZATION IN NON-LINEAR AUTOENCODERS:

In this section, we analyze the phenomenon of memorization for non-linear networks. In the following experiments, we use the linear CNNs D a,b and N D a,b as the backbone architecture but with LeakyReLU activations (Xu et al., 2015) 

7. CONCLUSIONS AND FUTURE WORK:

This paper identified downsampling as a mechanism through which linear CNNs memorize training images. We demonstrated that downsampling convolutional autoencoders memorize training images in both the linear and nonlinear setting. In particular, we showed that it is not just the dimensionality reduction of downsampling that causes these models to learn point maps by demonstrating that a downsampling CNN architecture with the capacity to learn the identity function still prefers the point map. In the linear case, this preference for low-rank over the equally valid high-rank solutions is highly suggestive of similar phenomena observed in problems such as matrix completion (e.g., Gunasekar et al.) .

In the non-linear case, memorization in downsampling networks is manifested even more strikingly with nearly arbitrary input images being mapped to output images that are visually identifiable as one of the training images. While the exact mechanism still needs to be explored, this is reminiscent of FastICA in Independent Component Analysis (Hyvrinen & Oja, 1997) or more general non-linear eigen-problems (Belkin et al., 2018) , where every "eigenvector" for certain iterative maps has its own basin of attraction. On the other hand, non-downsampling auto-encoders do not memorize the training data and consistently learn a "high rank" map, similar to the identity map, at least visually.

We conjecture that our findings will help to shed light on the strong generalization properties of downsampling networks for image classification and recognition tasks. Indeed, if downsampling networks memorize images or linear combinations of images, when trained on large datasets, they may be capable of learning representations within the space of all realisitic images instead of learning the standard full rank basis.

We conclude with a mention of further areas of exploration spurred on by our work. We still need to understand why downsampling forces the network to learn low rank solutions even when the network has the capacity to learn the identity. This requires developing a better grasp of optimization and initialization, starting with linear autoencoders and proceeding to the non-linear settings. Finally, we need to explore connections between our conjecture and the manifold hypothesis to better understand the space of realistic images. 2. Now nearest neighbor upsampling will be applied to each of the outputs.

3. The second convolutional layer has 4 filters of size (4, 3, 3). Filter i should have position (i, 1, 2) set to 1 for 0 ≤ i ≤ 3.

4. The third convolutional layer has 4 filters of size (4, 3, 3). Filter i should have position (i, 2, 1) set to 1 for 0 ≤ i ≤ 3.

5. The fourth convolutional layer has 4 filters of size (4, 3, 3). Filter 1 should have indices (0, 1, 1) set to 1. Filter 2 should have indices (1, 1, 0) set to 1. Filter 3 should have indices (2, 0, 1) set to 1. Filter 4 should have indices (3, 0, 0) set to 1.

6. The last filter is of size (4, 3, 3). This filter should have indices (i, 1, 1) set to 1 for 0 ≤ i ≤ 3.

B LINEARIZING A CNN:

In this section, we present algorithms for converting convolutional layers and nearest neighbor upsampling layers into matrices. We first present how to construct a block of this matrix for a single filter in Algorithm 1. To construct a matrix for multiple filters, one need only apply the provided algorithm to construct separate matrix blocks for each filter and then concatenate them. We now provide an example of how to convert the first layer from the network in Figure 4a into a single matrix for 1 × 2 × 2 images.

First suppose we have a zero padded 1 × 2 × 2 matrix as input, which is shown vectorized to the right:

   0 0 0 0 0 A 1 A 2 0 0 A 3 A 4 0 0 0 0 0    → [0 0 0 0 0 A 1 A 2 0 0 A 3 A 4 0 0 0 0 0]

T Now we apply the first convolutional layer to this 16 × 1 vector. We have 4 convolutional filters with parameter C

(j) i denote the ith parameter (read in row-major order) from filter j for 1 ≤ i ≤ 9 and 1 ≤ j ≤ 4. The resulting convolutional matrix is of size 4 • 3 • 3 × 1 • 4 • 4, but here we show just the first 9 columns (i.e. the pattern for the ith filter):

            

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

C (i) 5 C (i) 6 0 0 C (i) 8 C (i) 9

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

            

We similarly create matrices for the other convolutional layers.

Next we present how to construct the rows of such a matrix in Algorithm 2. We now provide the upsampling matrix for an upsampling layer with scale factor 2 operating on a vectorized zero padded 1 × 1 × 1 image:

                        

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

                        

We now give an example for the network from Figure 3a when it is applied to vectorized zero padded 1 × 2 × 2 input images. Suppose that the ith convolutional layer can be written as a matrix A i and the upsampling layer is written as a matrix U . Then we have the following matrix factorization for our network: 

A X = A 5 A 4 A 3 A 2 U A 1 Now A 1 has dimensions 4 • 3 • 3 × 1 • 4 • 4. U has dimensions 4 • 4 • 4 × 4 • 3 • 3. Now A 2 , A 3 , A 4 have dimensions 4 • 4 • 4 × 4 • 4 • 4. Finally A 5 has dimensions 1 • 4 • 4 × 4 • 4 • 4.

U ← zeros matrix of size (f • outputSize 2 , f • (s + 2) 2 ) 4: index ← outputSize + 1 5: for f ilterIndex ← 0 to f -1 do 6:

for rowIndex ← 1 to s do 7:

for scaleIndex ← 0 to scale -1 do 8:

for columnIndex ← 0 to s do 9:

row ← zeros vector of size (f (s + 2) 2 ) 10:

row[columnIndex + rowIndex(s + 2) + f ilterIndex(s + 2) 2 ] ← 1 11:

for repeatIndex ← 0 to scale -1 do return U 22: end function dimensions 1•4•4×1•4•4. Now the rank of A X is at most the rank of any of A 1 , A 2 , A 3 , A 4 , A 5 , U . Furthermore, as A X is operating on vectorized zero-padded images, the rank of A X is at most the size of the vectorized original image without zero padding. For this example, this means that the rank of A X is at most 4 = 1 • 2 • 2.

C PROOF OF PROPOSITION:

Here we present the proof of our proposition. We first show that A X obtains rank k = dim (span (X)) when X is a nonzero subset of k of the following basis elements for the space 1 × 2 × 2:

1 0 0 0 , 0 1 0 0 , 0 0 1 0 , 0 0 0 1 1. We first train Network DS on 1 0 0 0

After training, the resulting eigenvalues are 1, -7.2 • 10 -4 + 0.003i, -7.22 • 10 -4 -0.003i, -1 • 10 -2 . The corresponding largest eigenvector is -1 0 0 0 which is the negative of the training example.

2. We now train Network DS on 1 0 0 0 , 0 1 0 0 For example, the real components of eigenvectors 1, 2, and 3 contain the bird training example, but with inverted colors. Similarly, the real components of eigenvectors 4 and 5 contain the the boat example again with inverted colors; the real components of eigenvectors 6 and 7 contain the frog example; the real components of eigenvectors 8 and 9 contain the car example.

Next we consider the rank of the learned operators when training on thousands of examples from a single class of CIFAR10. In particular, we trained using 2000 dogs, 5000 dogs, or 5000 planes from CIFAR10's training set. If our conjecture holds, then the resulting solution should be of rank equal to the dimension of the span of each of these training sets. Note that the rank of the learned solution should be less than 3072 even though we are training on greater than 3072 images because it is unlikely that there are 3072 linearly independent images in each of the sets. The training losses on each of these datasets is shown in Table 1 and the corresponding eigenvalue and eigenvector plots are shown in Figure 10 .

From the plot of eigenvalues, it appears that the rank of the resulting matrix for D 64,192 on 2000 dogs, 5000 dogs, and 5000 planes is around 500, 900, 750 respectively. However, it could be the case that the remaining eigenvalues are providing small nonzero contributions to the learned solution. To rectify this issue, we took the SVD of the resulting operator and zeroed out the lowest singular values and compared the MSE of the reconstructions using the resulting operator against those of the original. In particular, we compared the MSE of the reconstructions (after min-max scaling) to the training set used. The results are summarized in the Table 1 .

From this table it is evident that only the top 500, 900, and 750 components were necessary to achieve low training error. Assuming our conjecture holds, this would indicate that these values are approximations for the dimension of the span of the corresponding training sets. We note that this is an approximation because the true dimension would be given when the training error approaches 0.

The training errors here are of the order of 10 -3 , thereby justifying such approximations. 

:



Figures and Tables:

(a) U-Net Autoencoder trained on a dog. (b) U-Net Autoencoder trained on a car.

Figure 1: U-Net Autoencoder trained on a single image from CIFAR10 for 2000 iterations. When fed random sized white squares, a standard Gaussian, or new images from CIFAR10 the model outputs the training image.

Figure 2: Linear CNNs with Network ND (non-downsampling) and Network D (downsampling) were trained for 2000 iterations to autoencode a single frog from CIFAR10. While Network ND approximately learns the identity function, Network D learns the point map (up to sign).

(a) D trained for 10 iterations. (b) D trained for 100 iterations. (c) D trained for 1000 iterations. (d) ND trained for 10 iterations. (e) ND trained for 100 iterations. (f) ND trained for 1000 iterations.

Figure 3: While the downsampling network D learns the point map regardless of the stopping point, the non-downsampling network ND begins to learn a function similar to the identity even after training on a single image for only 10 iterations.

(a) Small downsampling network DS (b) Manual initialization in identity function (c) Default PyTorch uniform initialization

Figure 4: Linear CNN with network DS when trained on a single 2 × 2 image learns the identity function when manually initialized in the identity function, but learns the point map when initiated using the default PyTorch uniform initialization.

Figure 5: The general architecture of a linear CNN with a filters on upsampled representations and b filters on downsampled representations. We denote the downsampling version of this network as Network D a,b and the non-downsampling version Network N D a,b .

(a) Downsampling network D64,192 autoencoding a single image. (b) Downsampling network D64,192 autoencoding two images. (c) Non-downsampling network N D4,4 autoencoding a single image. (d) Non-downsampling network N D4,4 autoencoding two images.

Figure 6: Plots show magnitude of eigenvalues together with visualization of real and imaginary components of the top eigenvector and their complex conjugates (for complex eigenvalues). alization of the eigenvectors when trained on k > 2 images is not as insightful (it becomes difficult to visually identify the training images in the linear combination), the corresponding visualizations and eigenvalue plots are moved to Appendix D.

after every convolutional layer. We denote the resulting architectures by N LD a,b (for the non-linear downsampling network with backbone D a,b ) and N LN D a,b (for the non-linear non-downsampling network with backbone N D a,b ).

Figure7shows the impact of downsampling on nonlinear networks trained on a single image. It is apparent that N LD 128,128 has memorized the training image while N LN D 128,128 has not, since for artifical, random noise, and real image inputs N LD 128,128 always outputs the training example while N LN D 128,128 's output is more simliar to the identity function.For Figure8we trained the non-linear downsampling network N LD 128,128 on a set of 10 images, one from each class of CIFAR10. Interestingly, when fed in a new image from CIFAR10, Gaussian noise or artificial white squares, the output was always one of the training images. This suggests that the effect of memorization is even stronger for non-linear downsampling networks, since they output specific training examples as compared to linear combinations of training examples, which we had observed for linear downsampling networks. In other words, the individual training examples act as strongly attracting fixed points for non-linear downsampling networks.We end this section with a remark on the impact of different initializations on training. While the experiments shown in Figure7were initialized in the default uniform distribution from PyTorch, Appendix E shows results with different initializations. In particular, we show that memorization still occurs when training N LD a,b with either Xavier or Kaiming uniform/normal initializations.

Figure 7: A comparison of nonlinear non-dowsampling (N LN D 128,128 ) and nonlinear downsampling (N LD 128,128 )) networks when trained on a single image of a plane from CIFAR10. N LD 128,128 has learned the point map while N LN D 128,128 has not.

Figure 8: The nonlinear downsampling network N LD 128,128 is trained on a set of 10 images, 1 from each class of CIFAR10. The training images are reproduced when feeding in new test images from CIFAR10, white squares or standard normal noise. For each of the training examples, we present some test examples that produced the training example. Interestingly, only the deer was reproduced when given artificial images of white squares.

MANUAL INITIALIZATION FOR SMALL NETWORKS Here we provide the initialization of the identity function for the network from Figure 4a. The procedure is as follows (the positions are 0 indexed): 1. There are 4 filters in the first layer each of size (3, 3) and with stride 2. Filter 1 should have indices (1, 1) set to 1. Filter 2 should have indices (1, 2) set to 1. Filter 3 should have indices (2, 1) set to 1. Filter 4 should have indices (2, 2) set to 1.

Create Matrix for Single Convolutional Filter given Input with dimensions f × s × s Input: parameters:= parameters of f trained 3 × 3 CNN filters, s:= width and height of image without zero padding, f := depth of image, stride:= stride of CNN filter Output: Matrix C representing convolution operation 1: function CREATEFILTERMATRIX(parameters, s, f, stride) ilterIndex][rowIndex] ← parameters[f ilterIndex][kernelIndex] ← zeros matrix of size ((resized + 2) 2 , f • paddedSize 2 ) 12: index ← resized + 2 + 1 13: for shif t ← 0 to resized -1 do 14: nextBlock ← zeros matrix of size (resized, f • paddedSize 2 ) 15: nextBlock[0] ← rowBlocks 16: for rowShif t ← 1 to resized -1 do 17: nextBlock[rowShif t] ← rowBlocks shifted right by stride • rowShif t : index + resized, :] ← nextBlock 20: index ← index + resize + 2 21: rowBlock ← zero shift rowBlock by paddedSize • stride

(a) 10 training examples from CIFAR10 with 1 example per class. (b) The real and imaginary components of the eigenvectors corresponding to the top 64 eigenvalues of the operator of D64,128 trained on the set in Subfigure 9a. (c) The magnitude of eigenvalues of the operator of D64,128.

Figure 9: Training set, eigenvector visualization, and plot of magnitude of eigenvalues for D 64,128 trained on 10 examples from CIFAR10.

Figure 11: The nonlinear downsampling network (N LD 128,128 ) learns the point map regardless of the initialization used. However, we note that for Kaiming intializations, the resulting reconstruction after feeding in new inputs is a blurred version of the training image.

Hence A X has Algorithm 2 Create Matrix for Nearest Neighbor Upsampling Layer Input: s:= width and height of image without zero padding, f := depth of image, scale:= re-scaling factor for incoming image Output: Matrix U representing convolution operation 1: function CREATEUPSAMPLINGMATRIX(s, f, scale)

Table content: <table><tr><td>2:</td><td>outputSize ← s • scale + 2</td></tr><tr><td>3:</td><td/></tr></table>

Peer review (iclr2019):
 Summary:- The authors investigates downsampling as one method by which autoencoding CNNs may memorize data. The theoretical motivation provided concentrates on linear CNNs. They show that downsampling linear CNNs tent to learn a point-map of the training data, even though (under certain initializations) they are capable of learning identity maps. However, non-downsampling linear CNNs learn identity maps. Given enough data however, the authors claim that the downsampling CNN will learn the identity map. Strengths:- + Authors present a good exploration of how linear CNNs memorize data when they do downsampling. + A theoretical prediction of the amount of training data needed to counteract data memorization for downsampling linear CNNs is provided, "Our conjecture also implies that when training a linear downsampling CNN on images of size 3 · 224 · 224, which corresponds to the input image size for VGG and ResNet (He et al. (2016), Simonyan & Zisserman (2015)), the number of linearly independent training examples needs to be at least 3 · 224 · 224 = 153, 228 before the network can learn the identity function." Weaknesses:- + Not enough theoretical proof is provided to support the hypothesis. Which would be fine but some key experiments are missing to make the paper empirically rigorous. ++ Would be good to see experiments that illustrate the predication that a certain amount of data would allow for learning identity maps, both for linear and non-linear CNNs. ++ In the non-linear CNN setting, I*d like to see the same early-stopping experiment done for linear CNNs whose results are in Fig. 3. I don*t see any obvious theoretical reason why that result form Fig. 3 must extend to the non-linear setting. + Initializations are pointed to as effecting the type of function the network learns. The authors give an example of a hand-designed initialization that allows a downsampling linear CNN to learn the identity map but they don*t explain how they arrived at this initialization, or its properties that make it a good initialization. In general however, I think it*s alright to assign exploration of effect of initialization to future work, since it seems like a non-trivial task. + It is mentioned that "the results are not observed for linear networks when using Kaiming initialization," which I read to mean the downsampling linear CNNs with Kaiming initialization learn the identity map, not point-map. If this is true, it seems like a vital point and should be included in discussions of future work. Recommendation: I think this could be a better short paper. There are some interesting contributions, but maybe not enough for a full length paper. For a full length paper, some further exploration of _why_ downsampling leads to (if indeed there is a causality) data memorization is needed. Minor stuff:- Citation "Gunasekar et al." is missing year (conclusions section)