When is memorization of irrelevant training data necessary for high-accuracy learning?

By Gavin Brown, Mark Bun, Vitaly Feldman, Adam M. Smith, Kunal Talwar. 2020

130 citations recorded by the source corpus.

Modern machine learning models are complex and frequently encode surprising amounts of information about individual inputs. In extreme cases, complex models appear to memorize entire input examples, including seemingly irrelevant information (social security numbers from text, for example). In this paper, we aim to understand whether this sort of memorization is necessary for accurate learning. We describe natural prediction problems in which every sufficiently accurate training algorithm must encode, in the prediction model, essentially all the information about a large subset of its training examples. This remains true even when the examples are high-dimensional and have entropy much higher than the sample size, and even when most of that information is ultimately irrelevant to the task at hand. Further, our results do not depend on the training algorithm or the class of models used for learning. Our problems are simple and fairly natural variants of the next-symbol prediction and the cluster labeling tasks. These tasks can be seen as abstractions of text- and image-related prediction problems. To establish our results, we reduce from a family of one-way communication problems for which we prove new information complexity lower bounds.

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

Deduplicating Training Data Mitigates Privacy Risks in Language Models (2022, background): “For long-tailed data distributions, counterfactual memorization can be necessary for learning accurate models (Feldman & Zhang, 2020; Brown et al., 2021).”
Extracting Training Data from Large Language Models (2020, background): “Understanding why this happens is an important problem for future work [6,40].”
Differentially Private Decoding in Large Language Models (2022, background): “In addition, intense memorization also has the potential to degrade utility and hurt fairness by not generalizing well to the true data distribution (Kawaguchi et al., 2017; Brown et al., 2021; Feldman and Zhang, 2020).”
Memorization Without Overfitting: Analyzing the Training Dynamics of Large Language Models (2022, unknown): “However, recent work has established a more symbiotic relationship between memorization and generalization in deep learning [2, 3, 4].”
Datamodels: Predicting Predictions from Training Data (2022, background): “Relatedly, Brown et al. (2021) proves that for certain natural distributions, memorization of a large fraction of data, even data irrelevant to the task at hand, is necessary for close to optimal generalization.”
Large-Scale Differentially Private BERT (2021, methodology): “Memorization properties of the DP trained model have been investigated in (Carlini et al., 2021; Brown et al., 2021); Feldman (2020) studies the generalization properties of DP models.”
Metadata Archaeology: Unearthing Data Subsets by Leveraging Training Dynamics (2022, background): “…during training (Wang et al., 2018; Talukdar et al., 2021), upweighting or balancing training on atypical, or avoid memorization of noisy labels (Brown et al., 2020), upweighting minority-group samples to promote model fairness (Liu et al., 2021; Sagawa et al., 2020; 2019; Zhang et al., 2022),…”
The Low-Resource Double Bind: An Empirical Study of Pruning for Low-Resource Machine Translation (2021, background): “Impeding mem-orization constrains model learning to the most general high level features, rather than atypical low-frequency features and noisy examples which typically require memorization and are less likely to generalize across other tasks (Brown et al., 2020; Feldman and Zhang, 2020).”
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).”
Membership Inference Attacks From First Principles (2021, background): “A recent line of work initiated by Feldman [14] shows both theoretically and empirically that some amount of memorization may be necessary to achieve optimal generalization [2, 15].”