# A Law of Data Reconstruction for Random Features (and Beyond)

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 58 of its 79 references that are in the map.
- First posted on arXiv 26 Sep 2025.

## Builds on (most cited first, 30 of 58)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [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)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Quantifying Memorization Across Neural Language Models](https://mlsanity.com/paper/2202.07646/) (2022)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Extracting Training Data from Diffusion Models](https://mlsanity.com/paper/2301.13188/) (2023)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation](https://mlsanity.com/paper/2008.03703/) (2020)
- [Does Learning Require Memorization? A Short Tale about a Long Tail](https://mlsanity.com/paper/1906.05271/) (2019)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [Understanding Deep Image Representations by Inverting Them](https://mlsanity.com/paper/1412.0035/) (2014)
- [Gradient Descent Maximizes the Margin of Homogeneous Neural Networks](https://mlsanity.com/paper/1906.05890/) (2019)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [Directional convergence and alignment in deep learning](https://mlsanity.com/paper/2006.06657/) (2020)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [Counterfactual Memorization in Neural Language Models](https://mlsanity.com/paper/2112.12938/) (2021)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation](https://mlsanity.com/paper/2205.01445/) (2022)
- [Reconstructing Training Data with Informed Adversaries](https://mlsanity.com/paper/2201.04845/) (2022)
- [Reconstructing Training Data from Trained Neural Networks](https://mlsanity.com/paper/2206.07758/) (2022)
- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)
- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?](https://mlsanity.com/paper/2012.06421/) (2020)
- [Rethinking LLM Memorization through the Lens of Adversarial Compression](https://mlsanity.com/paper/2404.15146/) (2024)

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

- [Efficient Techniques for Data Reconstruction, with Finite-Width Recovery Guarantees](https://mlsanity.com/paper/2605.06519/) (2026)
- [Feature Learning in Linear-Width Two-Layer Networks: Two vs. One Step of Gradient Descent](https://mlsanity.com/paper/2605.17767/) (2026)
- [A Sharp Transition in Data Reconstruction under Differential Privacy](https://mlsanity.com/paper/2609.37344/) (2026)

## Abstract (arXiv)

Large-scale deep learning models are known to memorize parts of the training set. In machine learning theory, memorization is often framed as interpolation or label fitting, and classical results show that this can be achieved when the number of parameters p in the model is larger than the number of training samples n. In this work, we consider memorization from the perspective of data reconstruction, demonstrating that this can be achieved when p is larger than dn, where d is the dimensionality of the data. More specifically, we show that, in the random features model, when p gg dn, the subspace spanned by the training samples in feature space gives sufficient information to identify the individual samples in input space. Our analysis suggests an optimization method to reconstruct the dataset from the model parameters, and we demonstrate that this method performs well on various architectures (random features, two-layer fully-connected and deep residual networks). Our results reveal a law of data reconstruction, according to which the entire training dataset can be recovered as p exceeds the threshold dn.