Trade-offs in Data Memorization via Strong Data Processing Inequalities

• URL: http://arxiv.org/abs/2506.01855v1
• Date: Mon, 02 Jun 2025 16:41:49 GMT
• Title: Trade-offs in Data Memorization via Strong Data Processing Inequalities
• Authors: Vitaly Feldman, Guy Kornowski, Xin Lyu,
• Abstract summary: Recent research demonstrated that training large language models involves memorization of a significant fraction of training data.<n>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.<n>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.
• Score: 19.969359347811398
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Generalization v.s. Memorization: Tracing Language Models' Capabilities Back to Pretraining Data [76.90128359866462]
  We introduce an extended concept of memorization, distributional memorization, which measures the correlation between the output probabilities and the pretraining data frequency.<n>This study demonstrates that memorization plays a larger role in simpler, knowledge-intensive tasks, while generalization is the key for harder, reasoning-based tasks.
  arXiv  Detail & Related papers  (2024-07-20T21:24:40Z)
• SoK: Memorisation in machine learning [5.563171090433323]
  Quantifying the impact of individual data samples on machine learning models is an open research problem. In this work we unify a broad range of previous definitions and perspectives on memorisation in ML. We discuss their interplay with model generalisation and their implications of these phenomena on data privacy.
  arXiv  Detail & Related papers  (2023-11-06T12:59:18Z)
• Exploring Memorization in Fine-tuned Language Models [53.52403444655213]
  We conduct the first comprehensive analysis to explore language models' memorization during fine-tuning across tasks. Our studies with open-sourced and our own fine-tuned LMs across various tasks indicate that memorization presents a strong disparity among different fine-tuning tasks. We provide an intuitive explanation of this task disparity via sparse coding theory and unveil a strong correlation between memorization and attention score distribution.
  arXiv  Detail & Related papers  (2023-10-10T15:41:26Z)
• MILD: Modeling the Instance Learning Dynamics for Learning with Noisy Labels [19.650299232829546]
  We propose an iterative selection approach based on the Weibull mixture model to identify clean data. In particular, we measure the difficulty of memorization and memorize for each instance via the transition times between being misclassified and being memorized. Our strategy outperforms existing noisy-label learning methods.
  arXiv  Detail & Related papers  (2023-06-20T14:26:53Z)
• A Survey of Learning on Small Data: Generalization, Optimization, and Challenge [101.27154181792567]
  Learning on small data that approximates the generalization ability of big data is one of the ultimate purposes of AI. This survey follows the active sampling theory under a PAC framework to analyze the generalization error and label complexity of learning on small data. Multiple data applications that may benefit from efficient small data representation are surveyed.
  arXiv  Detail & Related papers  (2022-07-29T02:34:19Z)
• Learning from Few Examples: A Summary of Approaches to Few-Shot Learning [3.6930948691311016]
  Few-Shot Learning refers to the problem of learning the underlying pattern in the data just from a few training samples. Deep learning solutions suffer from data hunger and extensively high computation time and resources. Few-shot learning that could drastically reduce the turnaround time of building machine learning applications emerges as a low-cost solution.
  arXiv  Detail & Related papers  (2022-03-07T23:15:21Z)
• Quantifying Memorization Across Neural Language Models [61.58529162310382]
  Large language models (LMs) have been shown to memorize parts of their training data, and when prompted appropriately, they will emit the memorized data verbatim. This is undesirable because memorization violates privacy (exposing user data), degrades utility (repeated easy-to-memorize text is often low quality), and hurts fairness (some texts are memorized over others). We describe three log-linear relationships that quantify the degree to which LMs emit memorized training data.
  arXiv  Detail & Related papers  (2022-02-15T18:48:31Z)
• Understanding Memorization from the Perspective of Optimization via Efficient Influence Estimation [54.899751055620904]
  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.
  arXiv  Detail & Related papers  (2021-12-16T11:34:23Z)
• When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning? [53.523017945443115]
  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. Our results do not depend on the training algorithm or the class of models used for learning.
  arXiv  Detail & Related papers  (2020-12-11T15:25:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.