# Trade-offs in Data Memorization via Strong Data Processing Inequalities

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 47 references that are in the map.
- First posted on arXiv 2 Jun 2025.

## Builds on (most cited first, 24 of 24)

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Membership Inference Attacks From First Principles](https://mlsanity.com/paper/2112.03570/) (2021)
- [The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks](https://mlsanity.com/paper/1802.08232/) (2018)
- [Extracting Training Data from Diffusion Models](https://mlsanity.com/paper/2301.13188/) (2023)
- [Does Learning Require Memorization? A Short Tale about a Long Tail](https://mlsanity.com/paper/1906.05271/) (2019)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Visualizing and Measuring the Geometry of BERT](https://mlsanity.com/paper/1906.02715/) (2019)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [Measuring Forgetting of Memorized Training Examples](https://mlsanity.com/paper/2207.00099/) (2022)
- [Tightening Mutual Information Based Bounds on Generalization Error](https://mlsanity.com/paper/1901.04609/) (2019)
- [When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?](https://mlsanity.com/paper/2012.06421/) (2020)
- [How much does your data exploration overfit? Controlling bias via information usage](https://mlsanity.com/paper/1511.05219/) (2015)
- [Generalization in Adaptive Data Analysis and Holdout Reuse](https://mlsanity.com/paper/1506.02629/) (2015)
- [Overparameterized Neural Networks Implement Associative Memory](https://mlsanity.com/paper/1909.12362/) (2019)
- [Identity Crisis: Memorization and Generalization under Extreme Overparameterization](https://mlsanity.com/paper/1902.04698/) (2019)
- [Calibrating Noise to Variance in Adaptive Data Analysis](https://mlsanity.com/paper/1712.07196/) (2017)
- [A Limitation of the PAC-Bayes Framework](https://mlsanity.com/paper/2006.13508/) (2020)
- [Information Theoretic Lower Bounds for Information Theoretic Upper Bounds](https://mlsanity.com/paper/2302.04925/) (2023)
- [A Direct Sum Result for the Information Complexity of Learning](https://mlsanity.com/paper/1804.05474/) (2018)
- [Communication Complexity of Estimating Correlations](https://mlsanity.com/paper/1901.09100/) (2019)

## Built on by (most cited first, 6 of 6)

- [A Law of Data Reconstruction for Random Features (and Beyond)](https://mlsanity.com/paper/2509.22214/) (2025)
- [Cram Less to Fit More: Training Data Pruning Improves Memorization of Facts](https://mlsanity.com/paper/2604.08519/) (2026)
- [Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing](https://mlsanity.com/paper/2602.00906/) (2026)
- [Tighter Information-Theoretic Generalization Bounds via a Novel Class of Change of Measure Inequalities](https://mlsanity.com/paper/2602.07999/) (2026)
- [We Should Separate Memorization from Copyright](https://mlsanity.com/paper/2602.08632/) (2026)
- [An Accuracy-Information Tradeoff for Loss-Difference Conditional Mutual Information](https://mlsanity.com/paper/2610.09206/) (2026)

## Abstract (arXiv)

Recent research demonstrated that training large language models involves memorization of a significant fraction of training data. Such memorization can lead to privacy violations when training on sensitive user data and thus motivates the study of data memorization's role in learning. In this work, we develop a general approach for proving lower bounds on excess data memorization, that relies on a new connection between strong data processing inequalities and data memorization. We then demonstrate that several simple and natural binary classification problems exhibit a trade-off between the number of samples available to a learning algorithm, and the amount of information about the training data that a learning algorithm needs to memorize to be accurate. In particular, Omega(d) bits of information about the training data need to be memorized when O(1) d-dimensional examples are available, which then decays as the number of examples grows at a problem-specific rate. Further, our lower bounds are generally matched (up to logarithmic factors) by simple learning algorithms. We also extend our lower bounds to more general mixture-of-clusters models. Our definitions and results build on the work of Brown et al. (2021) and address several limitations of the lower bounds in their work.