A Law of Data Reconstruction for Random Features (and Beyond)
Not on the map. Why?
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.
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
58 of 79 references.
References · 58
- 2015Deep Residual Learning for Image Recognitioncited by 52,096
- 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
- 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
- 2020Extracting Training Data from Large Language Modelscited by 2,189
- 2016Understanding deep learning requires rethinking generalizationcited by 1,674
- 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 927
- 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
- 2022Quantifying Memorization Across Neural Language Modelscited by 763
- 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 738
- 2023Extracting Training Data from Diffusion Modelscited by 732
- 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
- 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
38 more
- 2020What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimationcited by 497
- 2019Does Learning Require Memorization? A Short Tale about a Long Tailcited by 460
- 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 413
- 2014Understanding Deep Image Representations by Inverting Themcited by 403
- 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 320
- 2021Deep learning: a statistical viewpointcited by 240
- 2020Directional convergence and alignment in deep learningcited by 178
- 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
- 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
- 2021Counterfactual Memorization in Neural Language Modelscited by 156
- 2021A Universal Law of Robustness via Isoperimetrycited by 151
- 2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 150
- 2022Reconstructing Training Data with Informed Adversariescited by 148
- 2022Reconstructing Training Data from Trained Neural Networkscited by 133
- 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
- 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
- 2020When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?cited by 104
- 2024Rethinking LLM Memorization through the Lens of Adversarial Compressioncited by 94
- 2022Position: Considerations for Differentially Private Learning with Large-Scale Public Pretrainingcited by 88
- 2020Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networkscited by 87
- 2020The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Trainingcited by 84
- 20244+3 Phases of Compute-Optimal Neural Scaling Lawscited by 68
- 2020Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topologycited by 66
- 2020A law of robustness for two-layers neural networkscited by 55
- 2023A Theory of Non-Linear Feature Learning with One Gradient Step in Two-Layer Neural Networkscited by 49
- 2021On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widthscited by 44
- 2022The curse of overparametrization in adversarial training: Precise analysis of robust generalization for random features regressioncited by 41
- 2021On the Optimal Memorization Power of ReLU Neural Networkscited by 40
- 2022Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterizationcited by 36
- 2025Extracting memorized pieces of (copyrighted) books from open-weight language modelscited by 30
- 2022Reconstructing Training Data from Model Gradient, Provablycited by 27
- 2023Deconstructing Data Reconstruction: Multiclass, Weight Decay and General Lossescited by 26
- 2024Asymptotics of Random Feature Regression Beyond the Linear Scaling Regimecited by 26
- 2024Dimension-free deterministic equivalents and scaling laws for random feature regressioncited by 23
- 2021Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networkscited by 21
- 2024The Files are in the Computer: On Copyright, Memorization, and Generative AIcited by 21
- 2023Understanding Reconstruction Attacks with the Neural Tangent Kernel and Dataset Distillationcited by 14
- 2023Beyond the Universal Law of Robustness: Sharper Laws for Random Features and Neural Tangent Kernelscited by 13
50 most cited of 58 All 58 (JSON)
Built on by
Citing papers per year: 2026: 3.
3 papers.