Does learning require memorization? a short tale about a long tail

By Vitaly Feldman. 2019

666 citations recorded by the source corpus.

State-of-the-art results on image recognition tasks are achieved using over-parameterized learning algorithms that (nearly) perfectly fit the training set and are known to fit well even random labels. This tendency to memorize seemingly useless training data labels is not explained by existing theoretical analyses. Memorization of the training data also presents significant privacy risks when the training data contains sensitive personal information and thus it is important to understand whether such memorization is necessary for accurate learning. We provide a simple conceptual explanation and a theoretical model demonstrating that for natural data distributions memorization of labels is necessary for achieving close-to-optimal generalization error. The model is motivated and supported by the results of several recent empirical works. In our model, data is sampled from a mixture of subpopulations and the frequencies of these subpopulations are chosen from some prior. The model allows to quantify the effect of not fitting the training data on the generalization performance of the learned classifier and demonstrates that memorization is necessary whenever frequencies are long-tailed. Image and text data are known to follow such distributions and therefore our results establish a formal link between these empirical phenomena. Our results also have concrete implications for the cost of ensuring differential privacy in learning.

Subfields: Artificial Intelligence, Scaling & Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Scaling & Learning Theory

Citations in the corpus

Extracting Training Data from Large Language Models (2020, background): “to capture the long tails of the data distribution [17, 18, 62].”
Modifying Memories in Transformer Models (2020, background): “In general, without speciﬁcally focusing on language models, Feldman (2020); Feldman and Zhang (2020) have demonstrated both theoretical results and empirical evidences to imply that close-to-optimal generalization requires memorization of labels for samples from the low-frequency sub-populations.”
Differentially Private Learning Needs Better Features (or Much More Data) (2020, background): “Yet, training deep neural networks with strong DP guarantees comes at a significant cost in utility (Abadi et al., 2016; Yu et al., 2020; Bagdasaryan et al., 2019; Feldman, 2020).”
Tempered Sigmoid Activations for Deep Learning with Differential Privacy (2020, background): “Such accuracy loss may sometimes be inevitable: for example, the task may involve heavy-tailed distributions and noise added by DP-SGD hinders visibility of examples in the tails (Feldman 2019; Bagdasaryan and Shmatikov 2019).”
PaLM 2 Technical Report (2023, background): “Due to their presence in the tail of the overall data distribution, it is plausible that the model may memorize this data (Feldman, 2019).”
What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation (2020, methodology): “For a more detailed comparison of the long tail theory with the standard approaches to understanding of generalization and work on interpolating methods we refer the reader to [13].”
Counterfactual Memorization in Neural Language Models (2021, methodology): “The mathematical formulation of counterfactual memorization is borrowed from a notion of label memorization in Feldman [2020] and adapted to the context of neural LMs in this paper.”
What Does it Mean for a Language Model to Preserve Privacy? (2022, neutral): “mally generalize to long-tailed data distributions [30].”
Characterising Bias in Compressed Models (2020, background): “As seen in Figure 1, CelebA is representative of many natural image datasets where attributes follow a long-tail distribution (Zhu et al., 2014; Feldman, 2019).”
Class-Weighted Classification: Trade-offs and Robust Approaches (2020, background): “In text data, the distribution of words in documents has been observed to follow a power law in that there are many labels with few instances (Zipf, 1936; Feldman, 2019).”
Datamodels: Predicting Predictions from Training Data (2022, background): “Feldman (2019) suggests that memorization of atypical examples may be necessary to generalize well due to a long tail of subpopulations that arises in standard datasets.”
Dataset Inference: Ownership Resolution in Machine Learning (2021, background): “Prior works have also argued how over-parametrized deep learning networks memorize training points (Zhang et al., 2016; Feldman, 2019).”
Distilling Model Failures as Directions in Latent Space (2022, neutral): “The composition of the training dataset has key implications for machine learning models’ behavior (Feldman, 2019; Carlini et al., 2019; Koh & Liang, 2017; Ghorbani & Zou, 2019; Ilyas et al., 2022), especially as the training environments often deviate from deployment conditions (Rabanser et al.,…”
Bounding Training Data Reconstruction in Private (Deep) Learning (2022, background): “L G ] 9 J un 2022 h, D training data (Feldman, 2020), enabling adversaries to extract samples from the training dataset when given access to the trained model.”
Differentially Private Fine-tuning of Language Models (2021, background): “One oft-cited explanation is that the constraint of DP necessitates much more training data (Tram`er & Boneh, 2021; Feldman, 2020; Brown et al., 2021).”
Metadata Archaeology: Unearthing Data Subsets by Leveraging Training Dynamics (2022, background): “…(Brown et al., 2020; Jiang et al., 2020), difficult examples (Agarwal et al., 2021), minority-group examples (Liu et al., 2021; Sagawa et al., 2020; 2019; Zhang et al., 2022), points worth training (Mindermann et al., 2022), or domain identity in a domain generalization setting (Creager et al.,…”
When is memorization of irrelevant training data necessary for high-accuracy learning? (2020, methodology): “1 Generating Mixtures over Subpopulations We generate a mixture over N subpopulations using the process introduced in [19].”