Interpolation of data in deep neural networks has become a subject of significant research interest.   We prove that over-parameterized single layer fully connected autoencoders do not merely interpolate, but rather, memorize training data: they produce outputs in (a non-linear version of) the span of the training examples. In contrast to fully connected autoencoders, we prove that depth is necessary for memorization in convolutional autoencoders.   Moreover, we observe that adding nonlinearity to deep convolutional autoencoders results in a stronger form of memorization: instead of outputting points in the span of the training images, deep convolutional autoencoders tend to output 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 question of the inductive bias in over-parameterized deep networks.
 As deep convolutional neural networks (CNNs) become ubiquitous in computer vision thanks to their strong performance on a range of tasks (Goodfellow et al., 2016) , recent work has begun to analyze the role of interpolation (perfectly fitting training data) in such networks BID0 Zhang et al., 2017) . These works show that deep overparametrized networks can interpolate training data even when the labels are random. For an overparameterized model, there are typically infinitely many interpolating solutions. Thus it is important to characterize the inductive bias of an algorithm, i.e., the properties of the specific solution chosen by the training procedure. In this paper we study autoencoders (Goodfellow et al., 2016) , i.e. maps ψ : R d → R d that are trained to satisfy DISPLAYFORM0 Autoencoders are typically trained by solving arg min DISPLAYFORM1 by gradient descent over a parametrized function space Ψ.There are many interpolating solutions to the autoencoding problem in the overparametrized setting. We characterize the inductive bias as memorization when the autoencoder output is within the span of the training data and strong memorization when the output is close to one of the training examples for almost any input.Studying memorization in the context of autoencoders is relevant since (1) components of convolutional autoencoders are building blocks of many CNNs; (2) layerwise pre-training using autoencoders is a standard technique to initialize individual layers of CNNs to improve training (Belilovsky et al., 2019; Bengio et al., 2007; Erhan et al., 2010) ; and (3) autoencoder architectures are used in many image-to-image tasks such as image segmentation, image impainting, etc. (Ulyanov et al., 2017) . While the results in this paper hold generally for autoencoders, we concentrate on image data, since this allows identifying memorization by visual inspection of the input and output.To illustrate the memorization phenomenon, consider linear single layer fully connected autoencoders. This autoencoding problem can be reduced to linear regression (see Appendix A). It is well-known that solving overparametrized linear regression by gradient descent initialized at zero converges to the minimum norm solution (see, e.g., Theorem 6.1 in (Engl et al., 1996) ). This minimum norm solution translated to the autoencoding setting corresponds to memorization of the training data: after training the autoencoder, any input image is mapped to an image that lies in the span of the training set.In this paper, we prove that the memorization property extends to nonlinear single layer fully connected autoencoders.We proceed to show that memorization extends to deep (but not shallow) convolutional autoencoders. As a striking illustration of this phenomenon consider FIG0 . After training a U-Net architecture (Ronneberger et al., 2015) , which is commonly used in image-to-image tasks (Ulyanov et al., 2017) , on a single training image, any input image is mapped to the training image. Related ideas were concurrently explored for autoencoders trained on a single example in (Zhang et al., 2019) .The main contributions of this paper are as follows. Building on the connection to linear regression, we prove that single layer fully connected nonlinear autoencoders produce outputs in the "nonlinear" span (see Definition 2) of the training data. Interestingly , we show in Section 3 that in contrast to fully connected autoencoders, shallow convolutional autoencoders do not memorize training data, even when adding filters to increase the number of parameters.In Section 4, we observe that our memorization results for linear CNNs carry over to nonlinear CNNs. Further, nonlinear CNNs demonstrate a strong form of memorization: the trained network outputs individual training images rather than just combinations of training images. We end with a short discussion in Section 5. Appendices E, F, G, and H provide additional details concerning the effect of downsampling, early stopping, and initialization on memorization in linear and nonlinear convolutional autoencoders. This paper identified the mechanism behind memorization in autoencoders. While it is well-known that linear regression converges to a minimum norm solution when initialized at zero, we tied this phenomenon to memorization in non-linear single layer fully connected autoencoders, showing that they produce output in the nonlinear span of the training examples. Furthermore, we showed that convolutional autoencoders behave quite differently since not every overparameterized convolutional autoencoder memorizes. Indeed, we showed that overparameterization by adding depth or downsampling is necessary and empirically sufficient for memorization in the convolutional setting, while overparameterization by extending the number of filters in a layer does not lead to memorization.Interestingly, we observed empirically that the phenomenon of memorization is pronounced in the non-linear setting, where nearly arbitrary input images are mapped to output images that are visually identifiable as one of the training images rather than a linear combination thereof as in the linear setting. While the exact mechanism for this strong form of memorization in the non-linear setting still needs to be understood, this phenomenon is reminiscent of FastICA in Independent Component Analysis (Hyvrinen & Oja, 1997) or more general non-linear eigenproblems (Belkin et al., 2018b) , where every "eigenvector" (corresponding to training examples in our setting) of certain iterative maps has its own basin of attraction. We conjecture that increasing the depth may play the role of increasing the number of iterations in those methods.Since the use of deep networks with near zero initialization is the current standard for image classification tasks, we expect that our memorization results also carry over to these application domains. We note that memorization is a particular form of interpolation (zero training loss) and interpolation has been demonstrated to be capable of generalizing to test data in neural networks and a range of other methods (Zhang et al., 2017; Belkin et al., 2018a) . Our work could provide a mechanism to link overparameterization and memorization with generalization properties observed in deep convolutional networks.Belilovsky, E., Eickenberg, M., and Oyallon, E.
 We identify memorization as the inductive bias of interpolation in overparameterized fully connected and convolutional auto-encoders. 
{"src": "scitldr-AIC_train", "paper_id": "BJeZw4B334"}