# Does Learning Require Memorization? A Short Tale about a Long Tail

arXiv: https://arxiv.org/abs/1906.05271 · HTML: https://mlsanity.com/paper/1906.05271/

## Key facts

- Cited by 460 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2019.

## Built on by (most cited first, 30 of 460)

- [PaLM 2 Technical Report](https://mlsanity.com/paper/2305.10403/) (2023)
- [Membership Inference Attacks From First Principles](https://mlsanity.com/paper/2112.03570/) (2021)
- [Extracting Training Data from Diffusion Models](https://mlsanity.com/paper/2301.13188/) (2023)
- [Deep Learning on a Data Diet: Finding Important Examples Early in Training](https://mlsanity.com/paper/2107.07075/) (2021)
- [Diffusion Art or Digital Forgery? Investigating Data Replication in Diffusion Models](https://mlsanity.com/paper/2212.03860/) (2022)
- [Differentially Private Fine-tuning of Language Models](https://mlsanity.com/paper/2110.06500/) (2021)
- [Detecting Pretraining Data from Large Language Models](https://mlsanity.com/paper/2310.16789/) (2023)
- [Analyzing Leakage of Personally Identifiable Information in Language Models](https://mlsanity.com/paper/2302.00539/) (2023)
- [RAFT: Adapting Language Model to Domain Specific RAG](https://mlsanity.com/paper/2403.10131/) (2024)
- [Enhanced Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/2111.09679/) (2021)
- [Memorization Without Overfitting: Analyzing the Training Dynamics of Large Language Models](https://mlsanity.com/paper/2205.10770/) (2022)
- [What Does it Mean for a Language Model to Preserve Privacy?](https://mlsanity.com/paper/2202.05520/) (2022)
- [Can Bad Teaching Induce Forgetting? Unlearning in Deep Networks using an Incompetent Teacher](https://mlsanity.com/paper/2205.08096/) (2022)
- [Datamodels: Predicting Predictions from Training Data](https://mlsanity.com/paper/2202.00622/) (2022)
- [Fast Machine Unlearning Without Retraining Through Selective Synaptic Dampening](https://mlsanity.com/paper/2308.07707/) (2023)
- [On the Necessity of Auditable Algorithmic Definitions for Machine Unlearning](https://mlsanity.com/paper/2110.11891/) (2021)
- [The Curious Case of Hallucinations in Neural Machine Translation](https://mlsanity.com/paper/2104.06683/) (2021)
- [Counterfactual Memorization in Neural Language Models](https://mlsanity.com/paper/2112.12938/) (2021)
- [Reconstructing Training Data with Informed Adversaries](https://mlsanity.com/paper/2201.04845/) (2022)
- [Impact of Pretraining Term Frequencies on Few-Shot Reasoning](https://mlsanity.com/paper/2202.07206/) (2022)
- [The Privacy Onion Effect: Memorization is Relative](https://mlsanity.com/paper/2206.10469/) (2022)
- [Training Data Influence Analysis and Estimation: A Survey](https://mlsanity.com/paper/2212.04612/) (2022)
- [Zero-Shot Machine Unlearning](https://mlsanity.com/paper/2201.05629/) (2022)
- [Reconstructing Training Data from Trained Neural Networks](https://mlsanity.com/paper/2206.07758/) (2022)
- [Scaling Up Influence Functions](https://mlsanity.com/paper/2112.03052/) (2021)
- [On Memorization in Diffusion Models](https://mlsanity.com/paper/2310.02664/) (2023)
- [Interpretable Deep Learning: Interpretation, Interpretability, Trustworthiness, and Beyond](https://mlsanity.com/paper/2103.10689/) (2021)
- [Large-Scale Differentially Private BERT](https://mlsanity.com/paper/2108.01624/) (2021)
- [Dataset Inference: Ownership Resolution in Machine Learning](https://mlsanity.com/paper/2104.10706/) (2021)
- [Calibrated Language Models Must Hallucinate](https://mlsanity.com/paper/2311.14648/) (2023)

## Abstract (arXiv)

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 the labels of the training data 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 the first conceptual explanation and a theoretical model for this phenomenon. Specifically, we demonstrate that for natural data distributions memorization of labels is necessary for achieving close-to-optimal generalization error. Crucially, even labels of outliers and noisy labels need to be memorized. 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 our results show that memorization is necessary whenever the distribution of subpopulation frequencies is long-tailed. Image and text data is known to be long-tailed and therefore our results establish a formal link between these empirical phenomena. Our results allow to quantify the cost of limiting memorization in learning and explain the disparate effects that privacy and model compression have on different subgroups.