OpenNovelty.org

A Law of Data Reconstruction for Random Features (And Beyond)

ICLR 2026 Conference SubmissionAnonymous Authors
OpenReview Score: 6.5Download Report PDF
random featuresdata reconstructionmemorizationdeep learning theoryprivacyhigh-dimensional statistics
Abstract:

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 pp in the model is larger than the number of training samples nn. In this work, we consider memorization from the perspective of data reconstruction, demonstrating that this can be achieved when pp is larger than dndn, where dd is the dimensionality of the data. More specifically, we show that, in the random features model, when p≫dnp \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 pp exceeds the threshold dndn.

Disclaimer
This report is AI-GENERATED using Large Language Models and WisPaper (A scholar search engine). It analyzes academic papers' tasks and contributions against retrieved prior work. While this system identifies POTENTIAL overlaps and novel directions, ITS COVERAGE IS NOT EXHAUSTIVE AND JUDGMENTS ARE APPROXIMATE. These results are intended to assist human reviewers and SHOULD NOT be relied upon as a definitive verdict on novelty.
NOTE that some papers exist in multiple, slightly different versions (e.g., with different titles or URLs). The system may retrieve several versions of the same underlying work. The current automated pipeline does not reliably align or distinguish these cases, so human reviewers will need to disambiguate them manually.
If you have any questions, please contact: mingzhang23@m.fudan.edu.cn

Overview

Overall Novelty Assessment

The paper establishes a 'law of data reconstruction' for random features models, showing that training data can be recovered when the number of parameters p exceeds dn (data dimensionality times sample count). It resides in the 'Gradient-Based Theoretical Analysis' leaf under 'Theoretical Foundations and Identifiability', alongside one sibling paper (Gradient Reconstruction Provably). This leaf is notably sparse, containing only two papers within a broader taxonomy of 50 works, suggesting the paper targets a relatively underexplored theoretical niche focused on formal identifiability conditions rather than empirical attack development.

The taxonomy reveals that most reconstruction research concentrates on practical attack methods (Direct Parameter-Based Reconstruction, Gradient Inversion Attacks) and defense mechanisms (Differential Privacy Bounds), with fewer works establishing theoretical foundations. Neighboring leaves include 'Implicit Bias and Margin Maximization' (four papers exploiting gradient descent properties) and 'Bayesian and Probabilistic Frameworks' (one paper on inverse problems). The paper's focus on random features and parameter-dimensionality thresholds distinguishes it from these adjacent directions, which emphasize optimization dynamics or statistical inference rather than capacity-based reconstruction limits.

Among 30 candidates examined, the theoretical contributions (law of data reconstruction, Theorems 1 and 2) show no clear refutation across 10 candidates each, suggesting limited prior work on this specific threshold phenomenon. However, the optimization method for reconstruction faces overlap: 2 of 10 candidates appear refutable, indicating that algorithmic approaches to parameter-based data recovery have received more attention. This pattern aligns with the taxonomy structure, where attack algorithms dominate the literature while theoretical characterizations of reconstruction regimes remain less developed.

Based on this limited search scope (top-30 semantic matches), the theoretical framing around the dn threshold appears relatively novel, though the optimization method connects to a more established algorithmic literature. The analysis does not cover exhaustive citation networks or domain-specific venues, so additional related work may exist outside the examined candidates. The sparse population of the theoretical analysis leaf suggests the paper addresses a gap in formal reconstruction theory.

Taxonomy

Core-task Taxonomy Papers
50
3
Claimed Contributions
30
Contribution Candidate Papers Compared
2
Refutable Paper

Research Landscape Overview

Core task: Reconstructing training data from model parameters. This field examines whether and how an adversary can recover sensitive training examples by inspecting learned model weights or gradients. The taxonomy organizes research into several main branches: Theoretical Foundations and Identifiability explores fundamental limits and conditions under which reconstruction is possible, often through gradient-based analysis (e.g., Gradient Reconstruction Provably[8], Law of Data Reconstruction[0]); Attack Methods and Algorithms develops practical techniques for extracting training data across diverse settings, from federated learning to graph neural networks (e.g., Informed Adversaries Reconstruction[1], Stealing Training Graphs[3]); Defense Mechanisms and Privacy Guarantees investigates countermeasures such as differential privacy and bounds on reconstruction risk (e.g., Bounding DP-SGD Reconstruction[5], Bounding Private Learning[13]); and Related Privacy and Security Contexts covers adjacent concerns like model inversion, unlearning vulnerabilities, and membership inference (e.g., Unlearning Reconstruction Attacks[6], Model Inversion Landscape[24]). Recent work highlights tensions between theoretical guarantees and practical attack efficacy. Many studies focus on gradient-based reconstruction in federated or distributed settings, where even a single gradient update can leak substantial information about individual training samples. Others examine reconstruction from final model weights, exploring how overparameterization or specific architectures enable data recovery. Law of Data Reconstruction[0] sits within the Gradient-Based Theoretical Analysis cluster, providing foundational insights into when and why reconstruction succeeds, closely aligned with Gradient Reconstruction Provably[8]. In contrast, works like ReCIT[4] and Loki[7] emphasize algorithmic innovations for practical attacks, while Bounding DP-SGD Reconstruction[5] and Deconstructing Data Reconstruction[14] investigate the interplay between privacy mechanisms and reconstruction risk. Open questions remain around scaling these attacks to large models, understanding the role of model architecture, and designing defenses that balance utility with rigorous privacy.

Claimed Contributions

Law of data reconstruction for random features

The authors establish a theoretical threshold showing that entire training datasets can be reconstructed from random features models when the number of parameters p exceeds dn, where d is data dimensionality and n is the number of training samples. This reveals a fundamental law governing when data reconstruction becomes feasible.

10 retrieved papers
Theoretical characterization via Theorems 1 and 2

The authors prove that when the feature representations of training samples lie in the span of reconstructed sample features under sufficient over-parameterization, the reconstructed samples must be close to original training data. Theorem 2 extends this to show reconstructed samples are distinct, ruling out duplicates.

10 retrieved papers
Optimization method for data reconstruction

The authors develop a practical reconstruction algorithm based on minimizing the projection of trained parameters onto the orthogonal complement of reconstructed feature space. They demonstrate this method successfully recovers training data across random features, two-layer networks, and deep residual networks when p exceeds dn.

10 retrieved papers
Can Refute

Core Task Comparisons

Comparisons with papers in the same taxonomy category

Contribution Analysis

Detailed comparisons for each claimed contribution

Contribution

Law of data reconstruction for random features

The authors establish a theoretical threshold showing that entire training datasets can be reconstructed from random features models when the number of parameters p exceeds dn, where d is data dimensionality and n is the number of training samples. This reveals a fundamental law governing when data reconstruction becomes feasible.

Contribution

Theoretical characterization via Theorems 1 and 2

The authors prove that when the feature representations of training samples lie in the span of reconstructed sample features under sufficient over-parameterization, the reconstructed samples must be close to original training data. Theorem 2 extends this to show reconstructed samples are distinct, ruling out duplicates.

Contribution

Optimization method for data reconstruction

The authors develop a practical reconstruction algorithm based on minimizing the projection of trained parameters onto the orthogonal complement of reconstructed feature space. They demonstrate this method successfully recovers training data across random features, two-layer networks, and deep residual networks when p exceeds dn.

Table of Contents