Understanding Memorization from the Perspective of Optimization via Efficient Influence Estimation

Futong Liu, Tao Lin, Martin JaggiarXiv 2021 · arXiv

Abstract

Deep neural networks (DNNs) possess the remarkable ability to fit both structured patterns and random noise. This paper investigates the optimization dynamics underlying this phenomenon using an efficient influence estimation technique called "turn-over dropout." Contrary to the prevailing belief that models learn general patterns before memorizing noise, we show that optimization for both occurs simultaneously. We find that "easy" examples converge faster due to higher gradient similarity, while "difficult" examples act as more informative teachers, containing generalizable features as a subset of their complexity.

Introduction

Deep Neural Networks are notoriously adept at memorization, capable of fitting completely random labels as easily as real data. This raises a fundamental question: how do models distinguish between generalizable patterns and pure noise during training? Previous research suggested a two-stage process where models first learn simple, general patterns and only later succumb to memorizing difficult or noisy data. However, measuring this has traditionally been computationally prohibitive, requiring "leave-one-out" influence estimation. This study introduces a more efficient approach to debunk the sequential learning myth in favor of a simultaneous optimization perspective.

Methodology: Turn-over Dropout

To measure memorization efficiently, the authors employ Turn-over Dropout. This technique estimates a data point's influence without the need to retrain the model from scratch.

The Turn-over Dropout mechanism. It creates unmuted and muted sub-networks to estimate the influence of a specific training example z.

For every training example, the model generates a deterministic dropout mask. This splits the model into two sub-networks: an "unmuted" one that sees the example and a "muted" one that does not. By comparing the loss of these two sub-networks on the same example, the authors calculate a self-influence score. A high score indicates that the model requires that specific point to achieve low loss (memorization), while a low score suggests the model could have inferred the answer from other similar data (generalization).

Optimization Dynamics and Gradient Coherence

The study reveals that the perceived sequential nature of learning is actually a difference in "velocity" rather than timing. Optimization for both easy and difficult examples starts at the same time.

  • Gradient Coherence: Easy examples converge faster because their gradients are highly similar. They "agree" on the weight update direction, creating a strong, unified signal. In contrast, difficult or random examples have clashing gradients, making their progress significantly slower.
  • Informational Asymmetry: A key finding is that training a model exclusively on difficult examples helps it perform well on easy examples, but the reverse is not true. Difficult examples are "diverse" and contain general patterns as a subset of their complexity. In this framework, random labels are not a special category of noise but simply the extreme end of the difficulty spectrum.

Key Results

Empirical evaluations on MNIST, CIFAR-10, and Fashion MNIST support these insights. In experiments involving corrupted labels, the "real" data reached peak test accuracy rapidly, while random labels were fitted at a much slower pace.

Training and test accuracy dynamics. (a) shows the training progress for real vs. random labels, highlighting the speed differential. (b) tracks the overall test accuracy.

Despite their slower convergence, difficult examples provide a higher "contribution" to the Stochastic Gradient Descent (SGD) update throughout training compared to easy examples, which quickly settle into the background. Furthermore, models trained on a "difficult" subset of CIFAR-10 achieved significant accuracy on the "easy" subset, demonstrating clear transferability that does not occur when training on easy data alone.

Conclusion and Future Work

The ability to fit random noise is sensitive to optimization parameters, such as the learning rate schedule. While this study utilized architectures ranging from MLPs to Vision Transformers, the authors suggest that these memorization scores could be leveraged for core-set selection. By identifying the most informative (difficult) examples, researchers can create more efficient training sets that maintain high generalization performance without the computational burden of redundant data.

Summary updated

Abstract

Over-parameterized deep neural networks are able to achieve excellent training accuracy while maintaining a small generalization error. It has also been found that they are able to fit arbitrary labels, and this behaviour is referred to as the phenomenon of memorization. In this work, we study the phenomenon of memorization with turn-over dropout, an efficient method to estimate influence and memorization, for data with true labels (real data) and data with random labels (random data). Our main findings are: (i) For both real data and random data, the optimization of easy examples (e.g., real data) and difficult examples (e.g., random data) are conducted by the network simultaneously, with easy ones at a higher speed; (ii) For real data, a correct difficult example in the training dataset is more informative than an easy one. By showing the existence of memorization on random data and real data, we highlight the consistency between them regarding optimization and we emphasize the implication of memorization during optimization.
BibTeX
@misc{liu2021understanding,
  author = {Futong Liu and Tao Lin and Martin Jaggi},
  title = {{Understanding Memorization from the Perspective of Optimization via Efficient Influence Estimation}},
  year = {2021},
  eprint = {2112.08798},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.08798},
}
Figure