Memorization in Overparameterized Autoencoders

Adityanarayanan Radhakrishnan, Karren Yang, Mikhail Belkin, Caroline Uhler

Abstract: The ability of deep neural networks to generalize well in the overparameterized regime has become a subject of significant research interest. We show that overparameterized autoencoders exhibit memorization, a form of inductive bias that constrains the functions learned through the optimization process to concentrate around the training examples, although the network could in principle represent a much larger function class. In particular, we prove that single-layer fully-connected autoencoders project data onto the (nonlinear) span of the training examples. In addition, we show that deep fully-connected autoencoders learn a map that is locally contractive at the training examples, and hence iterating the autoencoder results in convergence to the training examples. Finally, we prove that depth is necessary and provide empirical evidence that it is also sufficient for memorization in convolutional autoencoders. Understanding this inductive bias may shed light on the generalization properties of overparametrized deep neural networks that are currently unexplained by classical statistical theory.

Introduction: The Paradox of Overparameterization

In modern deep learning, models often possess far more parameters than training data points. Classical statistical theory suggests these models should simply overfit, yet they generalize remarkably well. This research investigates the inductive bias of autoencoders (AEs)—the hidden rules guiding gradient descent toward specific solutions. We demonstrate that overparameterized AEs possess a hidden preference for memorization, where training examples act as powerful attractors in the data landscape.

The Geometry of Memorization

Our analysis treats the autoencoder as a discrete dynamical system $x_{t+1} = f(x_t)$. By examining the Jacobian matrix at training points, we find that deep autoencoders do not merely learn an identity function; they learn a locally contractive map. Training examples become "sinks" or attractors.

Comparison of learned functions across different architectures. Deep networks exhibit a step-like behavior that facilitates memorization compared to shallow interpolation.

As shown in the figure above, depth is a critical factor. While shallow networks tend toward arbitrary interpolation, deep networks develop a step-like inductive bias that pulls inputs toward discrete training points. This "gravitational pull" ensures that even when a network could theoretically represent a wide range of functions, it prioritizes the reconstruction of its training set.

The "Superattractor" Phenomenon

In complex architectures like U-Nets, this contractive behavior becomes even more aggressive, leading to what we term "superattraction." In these cases, the network can map arbitrary noise or unrelated images to a specific training image in a single iteration or through a short feedback loop.

A U-Net autoencoder trained on a single image acts as a superattractor, mapping noise and unrelated images back to the training example.

This effect is visually demonstrated by training a U-Net on a single CIFAR-10 image. When tested with Gaussian noise or images from entirely different classes, the network "recovers" the original training image. This suggests that the learned function's basins of attraction are vast, covering significant portions of the input space.

Structural Constraints and Depth Bounds

Our work also provides theoretical bounds for Convolutional Neural Networks (CNNs). Unlike fully connected networks, the physical structure of convolutions (kernel size, stride, padding) creates a "forced zero" pattern in weight matrices. We prove that depth is mandatory for CNNs to overcome this sparsity; for a linear convolutional AE using $3 \times 3$ filters on an $s \times s$ image, at least $s-1$ layers are required to achieve memorization.

Conclusion and Future Directions

Memorization is a structural property of the learned function, distinct from traditional overfitting. A network can generalize well on new data while remaining contractive toward its training set. Future work will extend these concepts to supervised learning and investigate the specific optimization paths that lead to the formation of these basins of attraction. Understanding these attractors is a key step toward a complete theory of generalization in deep learning.

Summary updated

Abstract

The ability of deep neural networks to generalize well in the overparameterized regime has become a subject of significant research interest. We show that overparameterized autoencoders exhibit memorization, a form of inductive bias that constrains the functions learned through the optimization process to concentrate around the training examples, although the network could in principle represent a much larger function class. In particular, we prove that single-layer fully-connected autoencoders project data onto the (nonlinear) span of the training examples. In addition, we show that deep fully-connected autoencoders learn a map that is locally contractive at the training examples, and hence iterating the autoencoder results in convergence to the training examples. Finally, we prove that depth is necessary and provide empirical evidence that it is also sufficient for memorization in convolutional autoencoders. Understanding this inductive bias may shed light on the generalization properties of overparametrized deep neural networks that are currently unexplained by classical statistical theory.
BibTeX
@misc{radhakrishnan2018memorization,
  author = {Adityanarayanan Radhakrishnan and Karren Yang and Mikhail Belkin and Caroline Uhler},
  title = {{Memorization in Overparameterized Autoencoders}},
  year = {2018},
  eprint = {1810.10333},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.10333},
}
Figure