A Law of Data Reconstruction for Random Features (And Beyond)
Authors: Leonardo Iurada
Simone Bombari
Tatiana Tommasi
Marco Mondelli
Venue: ICLR 2026 Poster (2026)
Keywords: random features
data reconstruction
memorization
deep learning theory
privacy
high-dimensional statistics
Primary area: learning theory
TL;DR: We show that it is possible to reconstruct the training data from a random features model (i.e., the model memorizes them), when the number of parameters exceeds the number of training samples times the input dimension.

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 $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$.

Published as a conference paper at ICLR 2026
A LAW OF DATA RECONSTRUCTION FOR RANDOM FEATURES (AND BEYOND)
Leonardo Iurada" Simone Bombari" ! Tatiana Tommasi?, Marco Mondelli
Politecnico di Torino, Italy Institute of Science and Technology Austria (ISTA)
ABSTRACT
Large-scale deep learning models are known to memorize parts of the training set. In machine learning theory, memorization is often framed interpolation label fitting, and classical results show that this can be achieved when the number of parameters p the model is larger than the number of training samples 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 >> 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 law of data reconstruction, according to which the entire training dataset can be recovered as exceeds the threshold dn.
INTRODUCTION
How many parameters does a neural network need to memorize the training data?
The answer to this question depends on what one means by memorization, term used with different purposes in the machine learning literature. Informally speaking, it captures the phenomenon of models storing the information of individual training samples, as opposed to learning the statistical patterns in the data. Thus, on the one hand, it is used to describe the phenomenon of label fitting (Zhang et al. 2017) forms of lcave-one-out output stability (Feldman 2020 Feldman & Zhang 2020). On the other hand, memorization is associated with reconstructing parts of the training ser through knowledge of the model parameters (Carlini al. 2023b [Scwarzschild et al. 2024 Cooper & Grimmelmann, 2024). Notably, this reconstruction is possible in modern founddaion models (Carlini al. 202 Nast al. 2025; Cooper al. 2025). with consequences in terms of privacy
concerns and copyright infringement (Trmer et al. 2024 Cooper & Grimmelmann 2024
Understanding how many parameters a neural network needs to interpolate the dataset (or, equiv- alently, memorize the labels) is classical problem {Cover 1965), with more modern literature showing that interpolation occurs as soon as the number of model parameters exceeds the number of training samples (Soltanolkotabi et al.) 2018 Montanari & Zhong, [022) Bombari et al. 2022). An intuition for the phenomenon is that solving y equations (given by the training samples) generally requires p 2 n degrees of freedom (given by the model parameters). In contrast, for the problem of reconstructing the training dataset, the situation is less clear. Empirical work has observed that this task becomes easier as the model gets larger (Haim al., 2022 Carlini et al., (2026)). However, theoretical work has taken different perspectives, focusing e.g. on impossibility results for differen- tially private training (Balle et al.) 2022). on reconstructing the data from the model gradients (Wang) al. 2023) or models with infinite number of parameters (Loo et al. 2024). To the best of our knowledge, there is no theoretical result connecting feasibility of data reconstruction and model size.
To address this gap, propose law of data reconstruction, giving threshold for which recon- struction becomes possible. We consider random features (RF) regression, where the model is
"Joint first authorship. equal contribution
Emails: (leonardo. iurada, tatiana. . tommasi @p
Emails; (simone bombari, marco. monde e ac.ac.

---

Published as a conference paper at ICLR 2026
CIFAR 10 (Binary Labds,, 100
Reomsetratiin Eine
Thaising Low
Figure 1: Thresholds for label fitting and data reconstruction in the random features model. (Left) We consider RF regression with ReLU activation on binary labels (frogs vs. trucks) with n 100 images (50 examples per class) from CIFAR-10 (d = 3072). We report the mean for both the reconstruction error (in red, defined in [12) and the training error (in black, mcan squared crror), as the number of parameters p increases. Statistics are computed across 4 distinct random seeds, and the standard deviation across seeds is very small (the confidence interval
standard deviation is reported in the plot shaded area, but it is imperceptible). For p 2 n, training labels are memorized, while reconstruction feasible when p becomes larger than dn. (Right) Results of the reconstruction when p = 10dn. Odd rows report the ground truth images, while even rows the reconstructed ones which are all visually very similar.
fRr 8) = ( 0, see Eq. (1. Here, x' is the d-dimensional input, (o(x) the corresponding p- dimensional feature vector, and f the p-dimensional model parameter vector obtained by running gradi- ent descent on the square loss over n samples. Our paper gives theoretical and empirical evidence that:
all the training data can be reconstructed when p >>>>> dn.
An intuition for the phenomenon is that solving dn equations (given by each dimension of each training sample) generally requires 2 dn degrees of freedom (given by the model parameters). Our analysis also suggests an optimization algorithm to reconstruct the training dataset and, proof of concept, we discuss the results of the designed method on CIFAR-10. We train a family of RF models using the square loss the training loss black and the reconstruction error in red (formally defined in Eq. (12) as functions of the number of parameters p. As expected, the training interpolation threshold p n, where labels are memorized. In contrast, the reconstruction error drops only when p is of order dn. In the right panel of Figure we display training images (odd rows) and reconstructed ones (even rows) for = 10dn, showing that the whole dataset is recovered successfully. Our contributions are summarized below:
100 training samples. The left panel of Figure shows
converges to 0 after the
Theorem ! we consider a set of n points $1...., &n E Rd, and prove that when p >> dn, if for every training sample x; it holds sp(xz) (pan(( then all the s must be close to one of the original training data.
As the previous result does not exclude the possibility of duplicates within the žy-s, in Theorem we prove that the i must be distinct, focusing on the case n = 2 for simplicity. Taken together, Theorem [ and 2 show that, when p dn, the entire training set can be reconstructed given one ......,,,, &n s.t. V E span ((($))) for any v spant (1(2)))
knowledge of the subspace span [ In fact, having access to spanf can then look for 21.....
In practice, have access to the vector of trained parameters 0*, which is in span ((((x)));11 see Eq. ( This motivates considering the reconstruction loss ||P where Ps is the projector on span ( (= if ||P 00 = 0, then 6* E span (<((,))) We empirically show that optimizing this loss over the c via gradient descent leads to the reconstruction of the training dataset, when p > dn. Notably, this procedure for data reconstruction is not limited to the RF model, but performs well also for two-layer and deep residual networks, see Figures 6
We finally remark that the scaling p > dn was previously considered in the context of adversarial robustness: prior work proved that the condition > dn is both necessary (Bubeck et al. 2021 Bubeck & Sellke, 2021) and, in some settings, sufficient (Bombari et al. (023) for smooth label interpolation. This suggests an inherent connection between the adversarial robustness the model and the ability to reconstruct training data from knowledge of its parameters.
2

---

Published as a conference paper at ICLR 2026
2 RELATED WORK
Over-paramettrization and memorization. The problem of label memorization and how it relates to the number of parameters in a neural network dates back to seminal results (Cover) 1965]
Baum 1988). More recently, a line of work aimed at showing that gradient descent converges to 0 training loss (i.e., the model memorizes the labels) for networks with progressively smaller
2019b Oymak & Soltanolkotabi, [2020] Nguyen & Mondelli 2020 Nguyen 2021 Nguyen et al.
over- prer-paramtteizatioon (Allen-Zhu et al., 2019 Du et al.
2021 Bombari et al.] 2022). with [Bobbai parameters are sufficient fit any set of labels in deep neural networks. Under a separability assumption, it has also heen shown that n arbitrary training points can be perfectly classified by a neural network with p > vni parameters (Vardi et al. 2022). This, in the context of regression, implies that p >> log(1/e) v T is sufficient to guarantee an error of at most e. In contrast, input data memorization and reconstruction is less explored from theoretical standpoint. Balle et (2022) proved impossibility results if the model is trained with differential privacy (Dwork et al. 2006), and showed that in generalized linear models it is possible to reconstruct an individual data provided all other samples are known. Loo et al. (2024) considered networks with an infinite number of parameters, Smorodinsky et al. (2024) focused on partial uni-dimensional (d = 1) training set reconstruction, and Wang et al. (2023) assumed knowledge of model gradients, requiring p >> parameters with n at most of order d'4 The regime p >> dn was heuristically identified by Haim ct al. (022)) as enabling successful data reconstruction, while (Brown et al. 2021 Feldman et al. 2025 studied its role as requirement for learning certain tasks, rather than for data reconstruction.
al. (2022) proving that p
Data reconstruction.
Recent studies have shown that training data can be extracted from generative models by carefully prompting their generation routines (Carlini et al. 2023a Zhang et al. 2023
Nasr et al., 2025: Cooper et al. 2025). More generally, data reconstruction is broader task, not limited to generative models, that aims to recover the training set directly from the learned model's parameters (Cooper & Grimmelmann 2024). A possible approach is via model inversion attacks, which optimize over the input space to raise a class score, although this method generally recovers class prototypes rather than specific training samples (Fredriksson et al., 2015 Mahendran & Vedaldi 2015). Another strategy relies on the implicit bias of gradient descent for homogeneous networks (yyu & Li 2020 Ji & Telgarsky 2020): Haim et al. (2022) proposed a reconstruction objective motivated by the observation that gradient descent converges to points satisfying the KKT conditions of max- max-margin problem, and empirically showed that training samples on the classification margin can be recovered. This method was then extended by Buzaglo et al. (2023); Oz et al. (2024) to the multiclass setting with general losses, and to larger scale pretrained models. Looo et al. (2024) adapted the idea to neural networks trained with the square loss in the linear (or NTK) regime (Jacot et al.) 2018: Lee et al. 2019). This leads to an optimization method for data reconstruction which has similarities with ours (compare Eq. (7) in (Loo et al. 2024) with Eq. 11 in this work).
Random features (RF) regression. The RF model (Rahimi & Recht 2007) can be regarded as a two-layer network with random first layer weights. Its popularity stems from its mathematical tractability and, in contrast with linear regression where number of parameters equals input dimension, it captures the statistical effects of wwerparramttrrization, as the number of parameters p scales independently from d and n. Mei & MMntanarr] (2022) characterized the test loss of random features, showing that it displays double descent (Belkin et al. 2019). Furthermore, the RF model has been used to understand various phenomena such as feature learning (Ba et al. [002 Damian et al.] 2022
Moniri et al.) (023). robustness under adversarial attacks (Dohmatob & Bietti 2022, Bombari et al. 2023 Hassani & Javanmard 2024), distribution shift (Tripuraneni et al. |021 Lee et al. 2023
Bombari & Mondelli 2025b), and scaling laws (Defilippis et al. 2024
Paquette al. 2024)
3 PROBLEM SETUP
Notation. All complexity notations w, 22 O O, o are understood for sufficiently large input di- mension d and number of parameters p. Given a positive number k, [k] denotes the set of positive numbers from 1 to k. Given a vector v. ||e/|/2 denotes its Euclidean norm. Given a matrix A E R we denote by PA E R=x= the projector over span (rows(A))) We say that an event holds with overwhelming probability if it holds with probability at least 1 wloo
Let (X, Y) be labeled training dataset, where X = [æ1,..., xx IT E Raxd contains the training input data (sampled i.i.d. from a distribution px) ) on its rows and Y = (y)...., ..)) E R" contains the corresponding labels. We define the random features (RF) model as
3

---

Published as a conference paper at ICLR 2026
far 0) <VV=) x
(1)
where va(2)) E I&P is the feature vector associated to the input x E Rd, and 0 E R are trainable parameters. The random features matrix V E R2xd is s.t. Vi,, wiid (O,01/d and 6 o: R + R is a non-linearity applied component-wise. We note that (2) is generalized linear model, and it can be regarded as a two-layer fully-connected neural network, where only the second layer is trained. We consider the supervised learning setup where a quadratic training loss (without regularization) is minimized via gradient descent. When the learning rate is sufficiently small, gradient descent converges to the interpolator which is the closest in E norm to the initialization (see Equation (33) in (Bartlett et al. (02T), which we consider equal to O for simplicity. Then, denoting with Ra* the feature matrix, the trained parameters are
== ( (1)........
A"
4 Y.
where t is the Moore-Penrose inverse of + Assumption (Data distribution). The training samples (21,...,IA, are n i.i.d. samples from the sub-Gaussian distribution Px, with ||=1 (1), and such that ||>||| = vd.
This assumption requires the data to have well-behaved tails (see the definition of the uub-Gaussian norm I1-1lyp in Eq. (13) in Appendix AA for further details), and allows for badly conditioned distribu- tions. This hypothesis is commonly used in the related literature, and it includes e.g. Gaussian data, data respecting Lipschitz concentration (Bubeck & Sellke 202TT Bombari et al.] 2023 von Berg et al.) 2025), and data uniform on the sphere (Mei & Montanari 2022 Hu et al,] 2024). The normalization
| = vd is chosen for technical convenience, and this scaling of the norm (combined with the scaling of the random features matrix V) guarantees that the pre-activations of the model (i.e., the entries of x)) are of constant order.
Assumption 2 (Activation function). The activation function @ BR + R. is a non-linear, Lipschitz continuous function such that its derivative is also Lipschitz. Letting iu denote the 1-th Hermite coefficient of 6. we further assume that plo μ22 O, fii + O, and that there exist two non-zero Hermite coefficients of order 2 3 with different parity.
This assumption is motivated by theoretical convenience, and we expect our results to hold for wider set of activations (as in (Mci et al. 2022)) after more involved analysis. Except for the Sarioonn@@eeee resembles the setting considered by Hu & Lu (2022). and it covers a wide family of odd activations, including tanh. The parity of high-order Hermite coefficients is used to reconstruct the correct sign of the training data, and it appears to be necessary for that, see Remark for details.
last condition on the parity of high-order Hermite coefficients. Assumption
Assumption 3 (Overr-araameterizaton We consider a data dimensionality regime where n = O(d),
and an over-parameterized model with
p= w (ndlog' d).
(3)
To guarantee that the RF model interpolates the data, suffices that p >> n (Mei et al.) 2022 Wang
& Zhu 2024). The stronger over-parene parameterization requirement in Eq. was shown to be both necessary (Bubeck & Selkke 202T) and, in some settings, sufficient (Bombari et al. 2023) to achieve smooth interpolation. We focus on the regime n O(d), which includes the popular proportional regime n = (d) as well as the regime where n is a fixed constant (independent of d)p). We expect our results to be generalizable also to n d (Mei et al. 2022 Hu al. 2024 Pandit al. 2024).
MAIN RESULTS
In this section, we present our main theoretical results, pinpointing p > dn the over- parameterization threshold such that data reconstruction can take place given knowledge of the subspace of the training samples in feature space.
More formally, the goal of data reconstruction is to exhibit matrix A E Raxd such that its rows st d are close the rows of the original training data matrix X. When | 212 = ||0:1|2 Vd. reconstructed sample æty can be considered close to a training sample x; if - = of /d). Let us also define &- (e((1), ((.x)) )} E R the feature matrix of the reconstructed data. Then, the result below gives sufficient conditions for all rows of X to be close to training samples.
4

---

Published as a conference paper at ICLR 2026
Theorem 1. Let Assumptions
1 and hold. Let X E R be such that its rows satisfy
|l+1l|2 vd, and for every i m2. (x(x)) E span span (rows {)). Then, with overwhelming probability, for any i E [n]. there exists E [n) such that
|| 2il12 = o(vd).
In words, Theorem states that, the random features of training samples are spanned by the random features of matrix X, the rows of X must be close (in input space) to the original training samples. Geometrically, this result proves that, when p > dn, in order to span the subspace generated by the training data features, one has to consider approximately the same vectors, as there is no solution to this problem obtained by non-degenerate linear combinations. In contrast with (Loo et al. 2024) which tackles the case p - 3c, our main contribution is to pinpoint the threshold p >> dn constituting sufficient amount of over-parameterization to reconstruct the data. We also highlight that, for the claim of Theorem Tto to hold, assumptions on the activation are necessary: if Φ is linear, picking
I1 ll2 gives a counterexample to Eq. 4 The proof of Theorem i deferred to Appendix B and sketch is below.
i = vd(z; + 1;+1)/ / [|=; + Zi+1 122 (f E [n- 1) and &, = vd(r, - x1 21)111
Proof sketch. Prior results on the RF kernel concentration (Mei et al.
2022 Wang & Zhuu 2024)
guarantee that, for p >> n. the smallest eigenvalue Amin (Φ-6 ) is bounded away from 0. Thus, the rows of + are linearly independent (they span a sub-space of dimension exactly n). Then, as the n row vectors of span all rows of & (by hypothesis), (ppa((row(()) = (ppanroos(()) This in turn gives that, if & E Rd is generic row of X, then (a.) span (rows(#)). i.e.,
((())
Σ axp(zz)
(5)
As argued above, the result cannot hold for linear activations, so let us focus on the non-linear component (0(;;) = <(Vx,) in Vx, in the Hermite basis. Taking the inner product of both sides of (5) with ((x;) and with ((t) yields, with overwhelming probability,
(v dn
|aal - = dn p
(+(x:) - - a²a =
+ o(1)
+ o1))
(6)
where E RR is defined as the vector containing a; in its i-th entry, and jt is the sum of the squares of the Hermite coefficients of & of order at least 3. The two results in Eq. O are formalized in Lemmas B.2 B.3 and they rely on concentration arguments on the random features V, which have to hold uniformly over any å E vd To obtain such uniform concentration, we rely e-net argument which crucially uses the condition p >> dn.
Next, in Lemma B.4 we show that, with overwhelming probability.
I +
(X d'
if C = max,
then
+((),
d
uniformly for every / 2 2. Combining Eq. 6 gives that IC- = o(1), i..., there exists a single
training sample z, aligned with f. To resolve the ambiguity in the sign, we use that there exist two non-zero Hermite coefficients of order 2 with different parity, which concludes the argument. O
Remark 1 (Sign ambiguity). The existence of two non-zero Hermite coefficients with different parity is necessary condition recover the sign of the training samples. In fact, if o is either even or odd, the problem is
in terms of the sign of the i..s, span (rows( (pan(rows( ( does not depend on them. Remarkably, this effect is also evident in numerical experiments optimizing the reconstruction loss defined in Eq. (T7): Figure considers consiiers ReLU activation (which violates the last condition of Assumption 2 as its Hermite coefficients p21+1 = 0 for all 1. >> 1) showing that negatives of training samples may be reconstructed.
Theorem guarantees that all the rows of X are close to the training samples. However, may still happen that multiple rows of X are close to the same sample, leaving part of the training dataset not reconstructed. This gap is approached by next result which focuses on the case = 2.
Theorem 2. Let Assumptions
1 and 3 hold. Let n and X 2xd be such that rows satisfy || = Vd, and for every E (1,2), (x(x)) E froanf ($)}. Then, with overwhelming probability, for any E {1, there exists E {1,2) such that
|| zillz = o(v)).
(8)
5

---

Published as a conference paper at ICLR 2026
In words, Theorem shows that all training samples are in fact reconstructed, ruling out the possibility of X containing repetitions. The proof is deferred to Appendix C and sketch is below.
Proof sketch. By contradiction, suppose there exist two vectors 61, <2 E IR such that
|eil|2 ||e2||2 o(vd),
()x2) a] + ei) + a24(21) + +22,
for some real values dn and 02. A Taylor expansion of p + +22 around x1 + é gives xx22) = (a1 + (2) + G1) + a2 (V +1) (V(e2 -1))
(9)
+ aa ((p(x1 + E2) f(01 + =1) - (V( + (1) o (V(e2 - e))),
where denotes the component-wis, product of two vectors. First, we take the inner product of both sides of Eq. (9) with Vzj, which yields
|a + a2l 0 a2 1l - c1ll2 (0all
+ o(1),
Vd
with overwhelming probability (see Lemma C.5 Then, we take the inner product with (((2 - ()) and show that the first and third term of the RHS of Eq. (9) are negligible with respect to the second one (see Lemmas C.3 and C.4). An upper bound on the LHS of Eq. ( based on Cauchy-Schwartz
inequality is then enough to show in Lemma C.6 that
vd ||e2 a1le) -lll
(
|22l 0
la + 02l 0(1),
with overwhelming probability. The argument in Lemma relies on concentration result on the sum of independent random variables with sub-exponential norm much larger than their standard deviation (see Lemma C.2). This is obtained via Bernstein-typp bound combined with an e-net argument as, similarly to Theorem [
we need a uniform control over any choice of 61, f2, Finally, by taking the inner product of the two sides of Eq. (9) with ((I2), we obtain
((x2)) (x(22))) S (a2 02)(((1)) (p(21 61) (02)((2)) (v0(11 + (2) p(a1 G)) (10)
Now, the LHS of Eq. (10) O(p) since is non-linear; the first term in the RHS of Eq. 10) is o(p)
as Ty and 22 are roughly orthogonal with overwhelming probability; and the last term in the RHS of
Eq. (10) is also o(p) via generalized Stein's lemma (see Lemma C.7 This gives a contradiction. O
Remark 2 (Technical challenge for > 3). We note that, already when n 3. the presence of duplicates is either given by the "triplet" I1, 32, 5.3 all similar to each other, or by a pair of duplicates 01,42 22 with different 4t3. The constructive approach used in the proof of Theorem would require us to consider the two cases separately, and the amount of cases increases combinatorially with n. Nevertheless, we suspect the idea that the span of duplicate samples cannot contain higher order terms of the left-out samples (G(x2) in Eq. (10)) to carry over to a general n, as long as >> dn.
From the theory to a reconstruction algorithm. Our theoretical analysis shows that, under sufficient over-parameterrizaton (p >> dn), the matrix X successfully reconstructs the training dataset when ((x:))) O for every i E [n]] where P4 denotes the projector on (rows((ws)))) In practice, we only have access to the trained model 0*, V and the activation ø. Recall 0 ++ span ppan(rows: (roows(()), so 8* is a linear combination of {1x(x))) which suggests to solve the problem:
X
arg min ((X), ((X) = || 11
(11)
& :vv
Importantly, enforcing that 0* lies in the span of the reconstructed features (L(X) 0) does not immediately imply that yo(z;) E span(rows($)) (+)} for all i (as the implication only goes in the other direction). In Figure 2 we numerically minimize ((X) and check whether the vectors pp(x,) approxi- mately lie in the subspace span ))). To do so, we calculate the average per-feature orthogonal residual, i.e. the average over E [n] of [P))] (zzz))l2// vp. where Pş
Ps projects onto the orthogonal complement of span(rows( ()). This quantity equals 0 if and only if every (((x,) lies in span ( (rows( (.)). The normalization by v makes r(Φ) == Ei= P ( ((x:))ll/((r (n//) of order I so that values of r()) < indicate numerically negligible residuals (i.e., effective span inclusion).

---

Published as a conference paper at ICLR 2026
- 300,
30,
100
100, 100,
03
Revonstruction
Error
Trsining Loss
Figure 3: Thresholds for label fitting and data reconstruction when training ii.d. data uniformly drawn from the d-dimensional sphere. We consider RF regression with ReLU activation, fitting noisy linear model. We report mean (solid line) and standard deviation (shaded area) for both the reconstruction error (in red) and training loss (in black) as the number of parameters increases, at different choices of input dimensions d and number of dataset examples Statisties computed across 10 distinct random seeds. Two distinct thresholds clearly emerge: p > for label fitting, and > dn for data reconstruction.
the per-feature orthogonal residual (plotted in blue) remains large until the model crosses the threshold = dn, after which it drops sharply (for S n, the optimization converges to the non- degenerate case P = J, which makes the orthogonal residual trivially zero). Thus, this numerical evidence suggests that minimizing ((X) is sufficient to satisfy the hypotheses of our main theorems for > dn, and hence to successfully reconstruct the training data. Equipped with these insights and recipe for dataset reconstruction, we complement our theory with numerical results as discussed below.
In Figure
CIFAR-10 10 (Binary Labels, n 100)
NUMERICAL EXPERIMENTS
14
We initialize the rows 2; of X with i.i.d. standard Gaus- sian vectors. We then minimize ((X) in 11) with gra- dient descent with momentum, normalizing each row it, after the update to constrain it the d-dimensional sphere Vd- In every experiment, perform the optimization until the reconstruction loss converges to zero, ie.. -(²* = 0 (up to machine precision). To quantify reconstruction quality, we report the average & distance between the rows of the ground truth and reconstructed data matrices, modulo a permutation on the rows of the latter, i.e.,
307
35
Resontruztion Error
Ang. aa
Figure Features of the training dataset are spanned by the features of the recon- structed dataset t We consider the setup as in Figure [ For different values of p, optimize until L(X) 0, and re- port reconstruction error (in red, defined in Eq. 12 and normalized residual P|PP (pxx))) )lla av- eraged over i E [n]] (in blue), with their confi- dence interval at one standard deviation (shaded area). Further details and evidence are in Ap- pendix E.1
p(X, X
min IEP. nV
(12)
where Pn, denotes the set of permutations of [n]. Obtain- ing II constitutes a classic linear assignment problem (Bertsekas) 1998), which we solve in polynomial time via the Hungarian method (Kuhn 1955). We normalize our success metric with nvd so that a reconstruction
see Figure 9
can be considered successful x(X, becomes much smaller than 1. As our main focus is on ReLU activations, whose odd Hermite coefficients (except μ1) are zero, recovered samples can appear with flipped sign (see Remark and Figure Accordingly, we also maximize p(X,X* over per-image sign flips. the following, we present numerical results by first considering a synthetic setup (i.i.d. data uniformly distributed on the d-dimensional sphere), and then by reconstructing natural images from the CIFAR- 10 dataset (Section 5.T). Finally, we explore the extent to which these phenomena observed in neural networks trained with gradient descent (Section 5.2)
5.1 RANDOM FEATURES REGRESSION
Synthetic data on the d-dimensional sphere. We begin with a synthetic task, where the training
data X [æ]...., xT] E gaxd are n i.i.d. samples drawn uniformly from the sphere of radius vd. The labels Y IR" are given by Y Xg + e, where g Rdd has entries yi ~ NN(0, 1/d) and the
7

---

Published as a conference paper at ICLR 2026
Figure 4: Images reconstructed from an RF model with ReLU activation may have the wrong sign. We repeat the experiment of Figure [ Jusing different random seed and observe that reconstructions from ReLU models appear sign- flipped versions of original training data. This is due to the fact that ReLU has odd Hermite coefficients of order 2 equal to zero.
noise R" is independent of the data X, with i... Gaussian entries with zero mean and variance 0.25. Figure showcases the same trend for several choices of d and n: at p 2 n, the training loss approaches zero, while the reconstruction error approaches zero when p becomes larger than dn.
Natural images with binary labels. The same phenomenon observed in the previous scenario carries over natural images with binary labels {+1]. For these experiments, we re- strict the CIFAR-10 10 training split to the first 50 instances of the "frog" and "truck" classes, fitting several RF mod- els with ReL.U activation. In the left part of Figure I we can appreciate the same transitions at p and p dn respectively for label fitting and data reconstruction; the right part of the figure then demonstrates that the re- constructed dataset appears perceptually indistinguishable from the original training dataset. Notably, for ReLU the above visual match may fail due to a sign error. In fact, with a different seed, we reconstruct the negatives of some training images (Figure 4 even if the condition p >>>>> dn met and the loss in Eq. (II) converges. This aligns with Remark I ReLU violates Assumption since 1 = 0 for L >>> In Figure 10 deferred to Appendix E.2 we show that the sign ambiguity disappears upon taking the activation x(2) RcLU(=) + tanh(2), which has mixed-parity Hermite 2 In Figure [5] we display the reconstructed images from the same experiment on ImageNn, which has input dimension d 3 x 64 x 64, for n 20 (additional details can found in Figure [4 and Appendices
Figure S: Reconstruction of dineesoai images. We re- peat the same experiment of Figure [ (right) using n 20 samples from Imag-ema and random Teatures model with 10dn.
coefficients and, therefore, satisfies Assumption
5.2 NEURAL NETWORKS TRAINED WITH GRADIENT DESCENT
Motivated by the RF baseline, now turn our attention to finite-width networks, studying how the number of parameters in the last layer p determines the ability to reconstruct the training dataset. Concretely, we train two-layer and deep residual networks with full-batch gradient descent, minimizing the square loss. Given that in this case the initialization is non-zero, we modify the reconstruction loss as ((X)
( (o! of )IB. where g(2)) and ((()) are respectively the
parameters of the last layer at initialization and at the end of training. The feature matrix & stacks the penultimate layer feature vectors v(t)). We assume access to trained weights of all layers
(0(2) ...., 064)). the last layer initialization (64) and the neural network's computational graph.
8

---

Published as a conference paper at ICLR 2026
2 Layorr NN cluss
ResNel (Binayy Laines)
Recocntrractinn Error
Training Lows
Figure 6: Thresholds for label fitting and data reconstruction for neural networks trained with gradient descent 10 CIFAR-10 images. We consider regression with the square loss, training two-layer ReLU networks on one-hot encoding the 10-class labels (left) and ResNets on binary labels (right). We report mean (solid line) and standard deviation (shaded area) across 10 distinct random seeds both reconstruction error (in red) and training loss (in black), as the number of parameters in the last layer p increases.
Figure 7: Multi-class training data reconstructed from a neural network trained on CIFAR-10. train a two-layer ReLU network on 100 images from CIFAR- 10 datasct (10 examples per class) with gradient descent. We cast the training procedure as multi-class regression square loss, using one-hot encoded class labels as targets. The number parameters in the last layer the network is p(4) 4dn.
Two-layer neural networks. We consider two-layer neural network fNN(2) = g(2) ((0())) with k-class output and ReLU activation d. The weight matrices ((1) E hgx and ((2) E k have i.idd
entries, initialized 0()) NO, 1/d), o!2) No. 1/h). In this setting, p = k h, where h is width of the network. In the left panel 2.2 Figure we analyze the ability to reconstruct CIFAR-10 images with one-hot targets for each of the 10 classes. Although the output is no longer scalar (as for random features), when p(L) becomes larger than dn, the reconstruction eтror starts decreasing. For all models reported the plot, the total number of trainable parameters satisfies p > (even when (4) < nt), so the model interpolates training labels and the training loss is close zero. As a confirmation of the quality of reconstructed images. we report in Figure 7 the reconstruction of n 100 examples (10 per class), when p(L) 4dn. Also in this scenario, the reconstructed images are perceptually indistinguishable from original training data.
Deep residual networks. We conclude the experimental evaluation with residual architectures, probing how their structure (i.e., residual connections and convolutions) affects reconstructability. We defer the formal definition of the model involved in these experiments to Appendix D.I On CIFAR-10 (frogs vs. trucks), shown in the rightmost panel of Figure ResNets display a transition for data reconstruction consistent with earlier experiments and happening after the ((4)) dn threshold. As for two-layer networks, the ResNets interpolate training labels even when ((L) < n, since the total number of parameters is much larger than the number of samples n for all models considered.
Classification via logistic and cross-entropy loss. We consider synthetic task, where the training data x; are n 100 i.i.d. samples drawn uniformly on the sphere of radius Va = 10. The labels given by sign(g Iz), where E IRd has entries gi ~ (O 1/d). We compute 0* minimizing the logistic loss E(0) Σm= log(1 + e wop(a) 8) with gradient descent, and consider the same

---

Published as a conference paper at ICLR 2026
RP (Synthetie n 100, Logistic Laes)
2-Layer NN (Multiiclasss Cross-Entroge Entropy]
64
62
12g Pi
Figure 8: Thresholds for data reconstruction on classification experiments. (Left) We consider binary classification over n 100 i..d. samples uniformly drawn from the d-dimensional sphere RF models with ReLU activation by minimizing the logistic loss with gradient descent. (Right) We consider multi-class classification and train two-layer ReLU networks on n = 10 CIFAR-10 10 images by minimizing cross-entropy loss with gradient descent. We report mean (solid line) and standard deviation (shaded area) for the reconstruction error (in red), for the training loss (in black) and for the per-feature orthogonal residual of projecting & onto span span(rows(( ( (in blue). We indicate with p the number of parameters in the last layer. Statistics computed across 10 distinct random seeds.
100). We train
reconstruction algorithm as in Eq. (TT). In the left panel of Figure 8 we find the usual threshold p z dn for successful reconstruction of the training set. In the right panel of Figure g we consider two-layer neural network trained with cross-entrops loss on 10 samples from the 10 classes of CIFAR-10. and we see that the reconstruction algorithm yields similar results as the ones for regression in Figure [ Further implementation details can be found in Appendix E. and the reconstructed images can be found in Figure 17
Additional ablation studies. In Appendix E.3 we first show that the optimization of L(X) is robust to different choices of the learning rate 7) (if it is sufficiently small). Then, we explore the setting where X has f n rows, showing that the result of the optimization gives overlapping images in the case ñ < n, and successfully reconstructs the full training set (plus some extra duplicates) in the case > n. We later show successful reconstruction from the parameters of a vision transformer, and give empirical evidence that adding a weight decay regularizer does not affect the law of reconstruction. Finally, we show that it is possible to reconstruct the data from a pruned neural network, albeit with higher values of p depending on the sparsity.
6 CONCLUSIONS
This work studies data memorization, intended as the feasibility of reconstructing n data samples of dimension dl from trained model, focusing on the number of parameters p which this becomes possible. Our results on random features point to a law of data reconstruction, establishing the threshold p s dn. Remarkably, the reconstruction method grounded in our theoretical analysis is also successful in two-layer and deep residual networks. While our analysis assumes knowledge of the subspace of the training samples in feature space (span (eean(((((z))) (<<()))) the experimental results demonstrate that, by optimizing the loss ((X) in Eq. 11). the whole training set is reconstructed when p >> dn. This suggests two outstanding open problems to be tackled in future research: proving that (i) all the global optima of L(X) permutations of the training dataset, and that (ii) the optimization problem can be efficiently solved with gradient methods despite the non-convexity of ((X). Another interesting direction is to understand what happens in the regime n < p < dn. On the one hand, Balle et al. (2022) indicate how to reconstruct any single training sample in this regime under certain model assumptions, given access to the final parameters and, additionally, to the remaining training data. On the other hand, we cautiously suspect that, without this additional knowledge, reconstructing the entire dataset is information- information-thhoreeicall theoretically impossible when p < dn: at fixed machine precision, this would require recovering (cn) bits from only (pp) bits, underscoring a hard limit on reconstructability. Importantly, this would not guarantee that none of the training samples is memorized. There is empirical evidence that learning models tend to memorize outliers (Feldman 2020), and possible direction for future work is to investigate if parts of the training data sampled from a heavy-tailed distribution (therefore not respecting Assumption I would result in memorization before the threshold p dn.
10

---

Published as a conference paper at ICLR 2026
ETHICS STATEMENT
This paper presents work whose goal is to advance the field of machine learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
REPRODUCIBILITY STATEMENT
We have made significant efforts to ensure the reproducibility of our results. Full implementation details provided in Appendix D alongside practical design choices to address potential challenges in implementing our experiments. Additionally, we provide the complete codebase at https wtcphhuw..ommm//m www./oo.mmaaaeeee data- reeossstoio.
//github.
ACKNOWLEDGEMENT
M.M. is funded by the European Union (ERC, INF2, project number 101161364). S.B. was supported by a Google PhD fellowship. L.I. acknowledges the grant received from the European Union Next- GenerationEU (Piano Nazionale di Ripresa E Resilienza (PNRR)) DM 351 on Trustworthy AI. T.T. & L.I. acknowledge the EU project ELSA European Lighthouse on Secure and Safe AI. This study was carried out within the FAIR Future Artificial Intelligence Research and received funding from the European Union Bext-GenerationEU (PIANO NAZIONALE DI RIPRESA RESILIENZA (PNRR) MISSIONE 4 COMPONENTE 2, INVESTIMENTO 1.3 - D.D. 1555 1 11/10/2022, PE00000013 This manuscript reflects only the authors' views and opinions, neither the European Union nor the European Commission can be considered responsible for them. The authors would like to thank Yizhe Zhu for helpful discussions.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning (ICML), 2019.
Jimmy Ba, Murat Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang. High- dimensional asymptotics of feature learning: How gradient step improves the representation. In Advances Neural Information Processing Systems, 2022.
Borja Balle, Giovanni Cherubin, and Jamie Hayes. Reconstructing training data with informed adversaries. In 2022 IEEE Symposium on Security and Privacy (SP), 2022.
Peter L Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: a statistical viewpoint. Acta numerica, 30:87-201, 2021.
Eric B Baum. On the capabilities of multilayer perceptrons. Journal of complexity, 4(3):193-215. 1988.
Mikhail Belkin, Daniel Hsu. Siyuan Ma, and Soumik Mandal. Reconciling modern machine- leaaniin practice and the classical bias variance trade-off. Proceedings of the National Academy of Sciences, 116632)15849-15854 2019.
Dimitri Bertsekas. Network optimization: continuous and discrete models, volume 8. Athena Scientific, 1998.
Simone Bombari and Marco Mondelli. How spurious features are memorized: Precise analysis for random and NTK features. In International Conference on Machine Learning (ICML), 2024.
Simone Bombari and Marco Mondelli. Privacy for free in the overparameterriee regime. Proceed- ings of the National Academy of Sciences, 122(15):e2423072222, 2025a. doi: 10.1073/pnas. 2423072122.
Simone Bombari and Marco Mondelli. Spurious correlations in high dimensional regression: The roles of regularization, simplicity bias and over-parameterrizaioon. In Forty-second International Conference Machine Learning, 2025b.

---

Published as a conference paper at ICLR 2026
Simone Bombari, Mohammad Hossein Amani, and Marco Mondelli. Memorization and optimization in deep neural networks with minimum over- pvee-parameterizationn. Advances in Neural Information Processing Systems, 2022.
Simone Bombari, Shayan Kiyani, and Marco Mondelli. Beyond the universal law of robustness: Sharper laws for random features and neural tangent kernels. In International Conference on Machine Learning (ICML), 2023.
Gavin Brown, Mark Bun, Vitaly Feldman, Adam Smith, and Kunal Talwar. When memorization of irrelevant training data necessary for high- high-accuracy learning? In Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, pp. 123-132, 2021.
Sebastien Bubeck and Mark Sellke. A universal law of robustness via isoperimetry. In Advances in Neural Information Processing Systems, 2021.
Sébastien Bubeck, Yuanzhi Li, and Dheeraj M Nagaraj. law of robustness for two-layers neural networks. In Conference on Learning Theory (COLT), pp. 804 820, 2021.
Gon Buzaglo, Niv Haim, Gilad Yehudai, Gal Vardi, Yakir Oz, Yaniv Nikankin, and Michal Irani. Deconstructing data reconstruction: Multiclass, weight decay and general losses. In Advances in Neural Information Processing Systems, 2023.
Nicholas Carlini, Florian Tramèr, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom B. Brown, Dawn Xiaodong Song, Ülfar Frlingsson, Alina Oprea, and Colin Raffel. Extracting training data from large language models. In USENIX Conference on Security Symposium, 2021.
Nicholas Carlini, Jamie Hayes, Milad Nasr, Matthew Jagielski, Vikash Sehwag, Florian Tramèr, Borja Balle, Daphne Ippolito, and Eric Wallace. Extracting training data from diffusion models. In USENIX Security Symposium, 2023a.
Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models. In The Eleventh International Conference on Learning Representations, 2023b.
Feder Cooper and James Grimmelmann. The files are in the computer: On copyright, memorization, and generative ai. Cornell Legal Studies Research Paper Forthcoming, Chicago-Ken Kent Law Review, Forthcoming, 2024.
A Feder Cooper, Aaron Gokaslan, Amy B Cyphert, Christopher De Sa, Mark Lemley, Daniel E Ho, and Percy Liang. Extracting memorized pieces of (copyrighted) books from open- weight language models. In 2025 Workshop Reliable and Responsible Foundation Models, 2025.
Thomas M. Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE Transactions on Electronic Computers, 14(14):326-334, 1965.
Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn representations with gradient descent. In Conference Learning Theory, pp. 5413-5452. PMLR, 2022.
Leonardo Defilippis, Bruno Loureiro, and Theodor Misiakiewicz. Dimension-Frn deterministic equivalents and scaling laws for random feature regression. In Advances in Neural Information Processing Systems, 2024.
Elvis Dohmatob and Alberto Bietti. On the (non-) robustness of two-layer neural networks in different learning regimes. arXiv preprint urXiv:2203. 1864, 2022.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn. Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
12

---

Published as a conference paper at ICLR 2026
Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning (ICML), 2019a.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations (ICLR), 2019b.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, volume 3876 of Lecture Notes Computer Science, pp. 265-284, Springer, 2006.
Vitaly Feldman. Does learning require memorization? A short tale about long tail. In ACM Symposium on Theory of Computing (STOC), pp. 954-959, 2020.
Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. In Advances in Neural Information Processing Systems, 2020.
Vitaly Feldman, Guy Kornowski, and Xin Lyu. Trade-off's in data memorization via strong data processing inequalities. arXiv preprint (xXiv:2506.01855 2025.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pp. 1322-1333, 2015.
Niv Haim, Gal Vardi, Gilad Yehudai, Ohad Shamir, and Michal Irani. Reconstructing training data from trained neural networks. Advances in Neural Information Processing Systems, 35: 2291 | 129244, 2022.
Hamed Hassani and Adel Javanmard. The curse of overparametrization in adversarial training: Precise analysis of robust generalization for random features regression. The Annals of Statistics, 52(2):441 4655, 2024.
Babak Hassibi and David Stork. Second order derivatives for network pruning: Optimal brain surgeon. Advances in Neural Information Processing Systems, 5, 1992.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Magnus Hestenes, Eduard Stiefel, et al. Methods of conjugate gradients for solving linear systems. Journal of research of the National Bureau of Standards, 49(6):409-436, 1952.
Hong Hu and Yue M Lu. Universality laws for high-dimensional learning with random features. IEEE Transactions on Information Theory, 69(3):1932-1166) 2022.
Hong Hu, Yue M. Lu, and Theodor Misiakiewicz. Asymptotics of random feature regression beyond the linear scaling regime. arXiv preprint arXiv:2403.08766) 2024.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances Neural Information Processing Systems, 2018.
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. Advances in Neural Information Processing Systems, 33:17176-17188 2020.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. Master's 's thesis, University of Toronto, ON, Canada, 2009.
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-97, 1955.
Yann Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 7 2015.
13

---

Published as a conference paper at ICLR 2026
Donghwan Lee, Behrad Moniri, Xinmeng Huang, Edgar Dobriban, and Hamed Hassani. Demys- tifying disagrreeeent-on-tee-iiieee high dimensions. In International Conference on Machine Learning, pp.
PMLR, 2023.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances Neurul Information Processing Systems, 2019.
Noel Loo, Ramin Hasani, Mathias Lechner, Alexander Amini, and Daniela Rus. Understanding reconstruction attacks with the neural tangent kernel and dataset distillation. In The Twelfth International Conference on Learning Representations, 2024.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In The Eighth International Conference on Learning Representations, 2020.
Aravindh Mahendran and Andrea Vedaldi. Understanding deep image representations by inverting them. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 5188-5196 2015.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75 (4):667-766, 2022.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Generalization error of random feature and kernel methods: Hypercontractivity and kernel matrix concentration. Applied and Computational Harmonic Analysis, 59:3-84, 2022. ISSN 1063-5203. Special Issue on Harmonic Analysis and Machine Learning.
Behrad Moniri, Donghwan Lee, Hamed Hassani, and Edgar Dobriban, theory of non-lineat feature learning with one gradient step in two-layer neural networks. arXiv preprint arXiv:2310.0788 2023.
Andrea Montanari and Yiqiao Zhong. The interpolation phase transition in neural networks: Mem- orization and generalization under lazy training. The Annals of Statistics, 5065):2816-2847, 2022.
Milad Nasr, Javier Rando, Nicholas Carlini, Jonathan Hayase, Matthew Jagielski, A. Feder Cooper, Daphne Ippolito, Christopher A. Choquette-Choo, Florian Tramèr, and Katherine Lee. Scalable ex- traction of training data from aligned, production language models. In The Thirteenth International Conference on Learning Representations, 2025.
Quynh Nguyen. On the proof of global convergence of gradient descent for deep relu networks with linear widths. In International Conference on Machine Learning (ICML), 2021.
Quynh Nguyen and Marco Mondelli. Global convergence of deep networks with one wide layer followed by pyramidal topology. In Advances in Neural Information Processing Systems, 2020.
Quynh Nguyen, Marco Mondelli, and Guido Montufar. Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep ReLU networks. In International Conference Machine Learning (ICML), 2021.
Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparameterization: Global con- vergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 1(1):84-105, 2020.
Yakir Oz, Gilad Yehudai, Gal Vardi, Itai Antebi, Michal Irani, and Niv Haim. Reconstructing training data from real world models trained with transfer learning. arXiv preprint arXiv:2407.15845 2024.
Parthe Pandit, Zhichao Wang, and Yizhe Zhu. Universality of kernel random matrices and kernel regression in the quadratic regime. arXiv preprint 3xXi:2440.00166) 2024.
Elliot Paquette, Courtney Paquette. Lechao Xiao, and Jeffrey Pennington. 4+3 phases of compute- optimal neural scaling laws. In Advances in Neural Information Processing Systems, 2024.
14

---

Published as a conference paper at ICLR 2026
Yaniv Plan and Roman Vershynin. Random matrices acting sets: Independent columns, 2025.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in Neural Information Processing Systems, 20, 2007.
Avi Schwarzschild, Zhili Feng, Pratyush Maini, Zachary Chase Lipton, and J Zico Kolter. Rethinking
LLM memorization through the lens of adversarial compression. In Advances in Neural Information Processing Systems, 2024.
Guy Smorodinsky, Gal Vardi, and Itay Safran. Provable privacy attacks trained shallow neural networks. arXiv preprint arXiv:2410.07632, 2024.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2):742-769, 2018.
Florian Tramèr, Gautam Kamath, and Nicholas Carlini. Position: Considerations for differentially private learning with large-scale public pretraining. International Conference on Machine Learning, 2024.
Nilesh Tripuraneni, Ben Adlam, and Jeffrey Pennington. Overparameterizattoon improves robustness to covariate shift in high dimensions. Advances in Neural Information Processing Systems, 34: 13883-13897, 2021.
Gal Vardi, Gilad Yehudai, and Ohad Shamir. On the optimal memorization power of reLU neural networks. In International Conference on Learning Representations, 2022.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science. Cambridge university press, 2018.
Jonas von Berg, Adalbert Fono, Massimiliano Datres, Sohir Maskey, and Gitta Kutyniok. The price of robustness: Stable classifiers need overparameterizaaton. In High-dimensional Learning Dynamics 2025, 2025.
Martin J. Wainwright. High- Ligh-DDimesiooal Statistics: A Non-Asympiotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
Zhichao Wang and Yizhe Zhu. Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks. The Annuls of Applied Probability, 34(2): 1896 1947, 2024.
Zihan Wang, Jason Lee, and Qi Lei. Reconstructing training data from model gradient, provably. In Proceedings of The 26th International Conference Artificial Intelligence and Statisties, 2023.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017.
Chiyuan Zhang, Daphne Ippolito, Katherine Lee, Matthew Jagielski, Florian Tramer, and Nicholas Carlini. Counterfactual memorization in neural language models. In Advances in Neural Informa- tion Processing Systems, 2023.
15

---

Published as a conference paper at ICLR 2026
A ADDITIONAL NOTATIONS AND PRELIMINARIES
We use the definition of the Orlicz norm of order a: of a real random variable X as
X v. = =infft > 0 E (exp(IX))//t))
(13)
From this definition, it follows that |||X|"|| Iya., = 1 We will say that a random variable X is sub- Gaussian (sub-exponential) if its uub-Gaussian norm ||X (sub-exponential norm || yl is O(1) (i.e. it does not increase with the scalings of the problem). Notice that if X and Y are scalar random variables, we have || S |XX pl || We use the analogous definitions for vectors. In particular, let X IR" be a random vector, then ll supp |/ XI and
|| 01 = |u X lly We note that if X E R is sub-Gaussian (sub-exponential) and T : R + R is Lipschitz, we have that r(X) is sub-Gaussian (sub-exponential) as well. Also, random variable is sub-Gausee Gabs-aass sub-exponential, its p-th momentum is upper bounded by constant (that might depend on p).
Given a matrix A, we indicate with A; its i-th row, and with A.j its j-th column. Given square matrix A, we denote by Amia (A) its smallest eigenvalue. Given matrix we indicate with || its operator (or spectral) norm, and with ||A|| p its Frobenius (or Hilbert-Schmidt) norm AlI Eig At)). Given two matrices A, B RR denote by A o B their Hadamard (component wise) product and by A o (o(-1) the 1-th Hadamard power, with A A.
B PROOF OF THEOREM
First, notice that, with overwhelming probability over V and X, due Lemma 4.5 in (Bombari & Mondelli 2025a), we have
Amin ( (T = s2()..
(14)
In particular, notice that the lower bound on n in their statement not required to lower bound the smallest eigenvalue of the kernel. This implies that 44 is full rank. Since for every i [n] we have (x())) E span grow( ( also have
span S span span(rows($)) (.))
(15)
Thus, the equation above implies that a subspace of dimension (#47 T is full rank) is a subset of another subspace of dimension most n. This implies that the two subspaces must be identical, which in turn implies, for every E [n].
((t,) E span(rows(4))-
(16)
Throughout the proof, we omit the subscript i to simplify the notation and we let á denote row of X such that L(X) O. Then, due to (16), we will write
( = + a Σ p(a))a;
(17)
where introduced the vector (sp(x;))=
Is containing the coefficients of (o() written in the basis
Furthermore, in this section, we will introduce the shorthand ((x) 3(Vz), Vx), where 3. : R + R is
non non-linearity that shares the same Hermite coefficients as ó. but with the first #1 0. This implies that d(2) ((2) #12 is a Lipschitz function. We will use the shorthand j Eis.1..
Lemma B. For any t p and any i [ni], have that
(p(x;) ((x;) - j. = 0
(18)
with probability at least 1 2exp(- -tt) over V. Furthermore, for any i # j. we have
(0 (WD
log d 8//2
(z())) x(xx)) 0
(19)
16

---

Published as a conference paper at ICLR 2026
with probability at least 1 - 2exp( eexp(-clog d) over V and X. Finally, we jointly have
(0() ((() - pp =0 (Vpdlogd + P.
sup BE vasd
(20)
sup REvage-1
@ (0(x;) - - ((x))" [({) 0 (Vndlog d (())
p d3)
(21)
sup
(o(x;) ( " 0 (Vpd
p
(22)
=EV
for all i E [n], with probability at least 1 2exp(-cd log² d) over V.
Proof. For the first statement, we have
((x;)) x((;) = E ~i 2))((([()))
(60 x;) x3,) - LEve ((
(23)
p By (ō(") ())((TTT))))
Let us analyze the two terms in the RHS separately. The first is the sum of p independent, mean-0, sub-exponential random variables (in the probability space of V). This holds since both ø and are Lipschitz due to Assumption [ and they arguments are sub-Gausee Sab-Gaussian. Then, due to Bernstein inequality (see Theorem 2 of /Vershynin 2018)), for any 0 < < p. have
लi z:)o(1z x2) Eve (((T) m5)]
s stvp.
(24)
with probability at least 1 - 2 exxp(-e1t)) over For the second term the RHS of 23 using the Hermite decomposition of á and ē. we have that
x.))
Ev jo( ((uTa))(uTTa)) =
(25)
Considering the case = j. we readily obtain 18) For the case i i j. since the a;-8 are sampled independently from sub-Gaussian distribution due to Assumption and ||æi||2 = vi for every i, we have that
max 1 1TJx xzト S V Vdlog d,
(26)
with probability at least 2n2 exp( log² d) - eexp(-e cs log² d), due Assumption 3 Then, with this probability, we have that
x. 23))
a1 xD p
log" d 1/2
p
p
2
p0
(27)
db
d3
for every + j. which gives
19
Let us now consider an c /dd-net of Vd namely {-t ) such that for any x E Vd
there exists m E [M] such that || - x ll2 S vd. Due to Corollary 4.2.13 in (Vershynin 2018).
for e < we have that the net can be chosen such that M < (3/e)d. Notice that, for any m E M the same argument leading to (8) yields
(( Teenn)Tpaae ((( - ppp O(Vpdlog
(28)
with probability at least 1 - performing a union bound on all m E [M], we have that the previous statement holds uniformly with probability at least
2 exp(-cadlon log² d), after setting = Vdlog d. Setting e = 1/d2, and
1 1-2(3/e)* lop d) 1- 1=2eep((log(3/e) e3 log² ddd) 1-2exp(-cadlog" d). (29)
17

---

Published as a conference paper at ICLR 2026
where ca is an absolute constant. By Lemma C.3 in (Bombari & Mondelli 2024) we also have that for any m E [M.] we jointly have
[1 = O(vD),
1 O(vD),
(30)
with probability at least 1-2 exp(-csp)) Taking union bound for all m E M 30 holds uniformly over the net with probability least 1 exp( (cpp) due Assumption Since 1/d8, for any i, there exists m such that || m2 - 1/d3/2, This implies
sup ée aevasd
ll I [M (|50(= +
sup #EVags
[|((()) ( 1l
max (1 + L L
llop
sup
|| a
BE 1d
(31)
P =o L,
O(VP).
d d3/2
where the third step follows from I| 0( p/dd/)
which holds with probability at least Then, we have
2 eexp(-e7)) due to Theorem 4.4.5 in /eessyynin 2018).
= (()) v sup sup (((())) (((f..)) (((=)))
( ((=))) - () px()
#EVAS4-1
aE aEvaSa-
+ sup #EVaSu
(+(=))) (0()) = p({
max (6 ll2 T. V op sup
|| - #112
sEVaSt-1
+ sup
|| L | op sup
| - 2112
#EVOSu-1
#EV
vp VD
= Vd d3/2
d2
(32)
Thus, merging 28
29 and 32 yields
P ( ((t) 1 pp'pl 0 (Vpdloo d +
sup
(33)
d2
se /
with probability at least - 2 exp((ccd d) over V, which proves Let us now consider fixed E [ni] and m [M]. We have
20)
((x:)) T p((()) - ((xx,) (((())))))))))))))))))))))))((
2()021)000aa Ev Tolo) x,)0()) xmmm
(5tا) a;) am)) -Evr ( x:)) (5 mmm)
+ E,, (ō(o" x; x;)((() mmm)
T5l x3 21)0(v T Immmm
p En
(34)
The last line is equal to 0, due to the Hermite coefficients of o and क. The first two lines of the RHS can be bounded separately via Bernstein inequality as (24 giving
[x(x:) p(rim)) ((x))) ((+..)) = O(vp(),
(35)
with probability at least 1 - 2 exp(-cctt) over V. for any < t < p. As done in 29 considering again e = 1/d², we have that the previous bound holds uniformly for every E [ and for every
m [M], after setting
Vdlogg, with probability least expp cind log d). Then,
similar argument as the one used in 32) yields
sup
(pxx)) ( ((xx) [ O (Vudlog d + z
(36)
=Ev
with probability at least 1 2 and the argument is complete.
d). This proves 21 The proof of 22 is analogous
18

---

Published as a conference paper at ICLR 2026
Lemma B.2. Let be generic row of X such that ((X) and I be defined according to Then, we have that, for any i E [n].
(p(x,) (()) - ji² pippail =0 (Ilalla 1) ([Vall++))(Vddlg d /pn log d + p vrllog d3/2 )
(37)
with probability at least 1 2exp(-clog d) over V and X.
Proof. For any
[n]. 17 implies
((x;) (0)) = ((x.)) " x Σ p(x;) ((kxs)Tpl ((xx))a
(38)
= pa; + ((())))(((;)0 - pippa))
Σ
((x,)) ((z))))
j
This implies
(x())) (((xx)T((C (0()) prpall s ( (aaz)){(((2)) sp(xx))
pi2pl lail
Σ
(p(z)) T x((x;)) I|ll|
||a||2 Vplogd+ V pplog* d p² log 6 d. d3
(39)
0 [|all2 VVlogd d Vpnlog d + v log d
d3/2
with probability least 2 exp (-c log" d) over and where the second step holds due the first two equations in the statement of Lemma B.1 Then, due to the fourth equation in the statement of Lemma B.I we have
(x;;)) p(()) (fx)) (+))) = = (Vrd P )
(40)
which, together with
39 gives the desired result.
Lemma B.3. We have that
|aa12 - =0= (0
dn log + log" d vd )
(41)
with probability at least 2 2exp(-clog d).
Proof. 17 directly implies
= (
Σ (()) p(z))ag.
(42)
Due to the third and fifth equations in the statement of Lemmal B.I respectively have that
(+()) p(t)) ji2pl pl -0
= (Vpdlogd +
p dz
(43)
(p(x:) T T(() (x:) ((+)) o o (Vpdlogd+
p p
(44)
with probability at least 2expp dexp(-eidlo log d). Then, by CauchhySchward inequality, (44) yields
Σ ((t) ((xx)a; Σ ((t) ((x)))))))) )a = -0(1all, (Vpdnnoos d PVn) ))
(45)
d2
19

---

Published as a conference paper at ICLR 2026
Again by Mouchy-Schwarte inequality, have
ai (0(+) (a(x)) ji² pai)
log² d
[lall2 (lla 1) VVndllg + vpn log + pm
(46)
d3/2
log" d Vd
o ||all2 (llal2 +) Vpndllg d +
with probability at least 1 - 2 exp( 02 log d). due to Lemma B.2 where the last step is a consequence of Assumption Then, merging (42). (43) (45) yields
and 446), application of the triangle inequality
pp' ||a| - 1| = (1aa)++1) (Vndnloog d
log" d' Vd ))
(47)
Notice that, ||a|| ((1, the LHS of the previous equation would be S2(p [|a]])) while the RHS would op [|al]] due to Assumption Then, we necessarily have that ||a||2 = O(), which yields
|1112 - = -1|=0
(v dn log d
log² d vd
(48)
with probability at least 2 2exp(-cp log" d), which gives the desired result. Lemma B.4. Let vd generic vector, and let S C S 1 be defined as
r T J
C = max;
(49)
d
Then, with probability at least 2exp
[coVd] over X, we have that
(x
< 1d-0..
(50)
d'
uniformly for every 2
Proof. Fix 0 < 8 < 1, and consider the values of i [n] such that
x + d
> 6.
(51)
Define M C [n]] as the set containing all the values of i that satisfy the inequality above, m |M as the cardinality of M, and X5 E IR mxd xd as the matrix that contains its rows all and only the 2,-8 such that E M. Note that X is matrix with independent sub-Gaussian columns, with fixed & norm equal to vd. Then, Theorem 1.3 in (Plan & Vershynin 2025 yields
|
val = O(Vn).
(52)
with probability at least 1 - 2 exxp( -nnn) This, due to Assumption O1), and therefore
guarantees that |
op
X
X
82 m
<
O(1),
(53)
d
Vd
Vdl
op
which implies
1
m = 0
(54)
8
20

---

Published as a conference paper at ICLR 2026
Consider all the possible subsets of size of [n]. There are in total
nm S cxp (mlogn) I exp (cs log 82
(55)
m
such subsets, where C' is an absolute constant, and where we used Assumption subsets, the operator norm of the matrix X, E Rmxdd with rows indexed by M
For each of these
|| va & C2 (vm++) tt)
(56)
with probability 1 - 2 exp((oo2f), again due to Theorem 1.3 in (Plan & Vershynin 2025 Then, performing union bound over all subsets and setting
/2C1/ /22 Vlog d we have that all matrices with rows belonging to a generic subset of size m of the rows of X respect (56) with probability at
least 1 2 exp
(-Ci log d In particular, with this probability, we also have
Xall val s C2 (vm 1) -
Vloge
(57)
where in the second step we used (54).
Then, we have that
(x
(X
+ (n - ( S 021-2 Xz 2 d
<
+ nd
(58)
2
1
where in the last step we used that 2 2, and the definition of C in Assumption gives nō (d--0.2) which yields
(49
Setting = d-0.3
X d
X - s1+ -1+ Cg
Mog d
< +
(59)
vdd
where the last step holds due to 57) with probability least 1 - expp
lng (-01
2 1
2 exx (-cava). Thus, plugging in 588 the thesis readily follows.
Proof Theorem i done in Lemma B.1 consider the e-ee of the sphere Vd with 1/d. For any element zt, of this set (with fixed index [M], where M denotes the cardinality the net), (17 yields
( p(t) To
TT
Σ
(60)
where each term of the sum above reads
(( T((s))
(5(0) (or xz)) - Eve
(61)
p Er (8(0) xm I Tob(0 (6(xTTr)) Tori)
By Bernstein inequality (see the same argument in 24 ) have that
(a(vz smm )d(u xx.) - Eug (5(0] x (((TTT = =
(62)
with probability least 2 exp (-cidlog² d). Performing union bound over the elements of the net, we have that (62) holds uniformly for all [n] and all m [M]] with probability least
1 2 2exp (-c2d d) (see the argument prior to (9)). Furthermore, the Hermite decomposition
of & and & gives
+o0
(2.T x:m) 1r
Eg [0 T f )o 2:)
=
d!
(63)
1=3
21

---

Published as a conference paper at ICLR 2026
which thus allows to write
4:0
(2) x
Σ p( {((;));
0 (Iaall2 v pdn
02
Mi
d'
(64)
=0 co(Vvoo par log d
where the first step follows from 61
662
and 63 and an application of Cauchy Schwartz inequality;
the second step holds due to Lemma B.3 with probability at least - 2 exp (-c3 log" d).
By the definition of the net, there exists E [M] such that ||=55 =112 S 1/vd. Fixing such m, have
+00
$ ppp p(t) ((tt) + 18(2) p()) ((²)) f()))) ( [p(())
d'
t=1
t=3
(
x
Σ ((
T (p(s;)a p Σ
d'
(65)
i=1
1=3
0 ldg d
p
d
P
p
vdd log
(Vpdn log d
2)
due to the third equation in the statement of Lemma B.1 argument equivalent to the one in (32).
and (64). Considering the union bound on these high probability events, we have that (65) holds with probability at least 1 - 2 exp ( c-c log? d).
Let's suppose we have
$ Iz
max;;
SC 1
(66)
where C' is an absolute constant (independent of d, p). Thus,
x
x4 I
f TTx
|| Ell2 |alاll
1 SC
max;
max;
+ max;
s C. <1,
(67)
d
d
d
d
where the last inequality holds for sufficiently large d. Then, we have
(Xai )o! d'
$ ||a||2
d
1=3
1=3
(1
dn
log 3 d
)
400
C1
log d +
Σ
(C.-1
O2d O21 (68)
p
Vd
dn (10 log d + d d=
$ C2 + Cs
where we applied Cauchy Schwartz inequality separately for every in the first step and used Lemmas B.3 and [B4 in the second step. Here, C₁ and C2 denote two positive absolute constants, and the inequality holds with probability at least 1 - 2 exx (-cs log² d). Plugging 68 in (65) yields
2 (1 (1- = =0( dn
log d d d o(1),
(69)
where the last step is a consequence of Assumption hypothesis in (66), implying that
3 which provides a contradiction with the
1 max;
o(1),
(70)
with probability at least
exxp (-os log" d).
22

---

Published as a conference paper at ICLR 2026
Let j arg max; Tz (taking the smallest index if there are multiple indices that maximize this value), and suppose a1 24 0. Then, the law of cosines yields
| xzll22
v 2d (1
2d
8: 21 = (v(V).
(71)
d
where the last step holds due 70). Thus, for k #f we have
2
2 d
2 2j
T ( mz) | xzyl
+ 1 la 1| - وااlع = o(1),
(72)
d
d
d
where the last step holds with probability at least 1 - 2 exp (-cs log" d) due to 71 and 26 In the case a 24 < 0 the same argument with -zj instead of zj yields the same thesis. Thus, comparing
with (70) we have that arg max; [ z.| has unique solution j. and all other indices are such that [ xi d (1))
This proves that è is aligned with r;. It remains to prove that also has the correct sign (i.e., is close to 24 and not -x;). To do so, following the same approach that led to (68). we have that
+00
Σ
05
M1
o(1),
(73)
d
iデj
1=3
with probability at least 2 exp
(-07 log
d). Thus, comparing with (65). we get
+00
(z)
aj
1
=(().
(74)
1=3
(74 can hold only if (xr sm)) ) have all the same sign for all I 1 such that μ4 * O. By Assumption this is possible only if x x > O, which concludes the argument.
Since |a,] + o(1) by Lemma B.3
C PROOF OF THEOREM 2
Due to Theorem 1 we have that, with overwhelming probability, every 2 has unique "closest" row vector in X, such that
24 o
(75)
Then, if we consider the case n = 2, either both samples are reconstructed, or the same training sample reconstructed twice. By contradiction, let us suppose the latter hypothesis, which without loss of generality can be framed as the first sample z1 being reconstructed twice.
Since we have that (xx2)) e span (aon/(ros(()))) which means that there exist two real numbers a₁ and 02 such that
p(x²)) = a1 p + + + azpp(11 + +2),
(76)
where
| + + = |a + c2ll2 Vd,
(77)
as we are considering data reconstruction on the sphere. From now on, we will always assume that (76) and (77) hold. We will often consider the following expansion:
(((2)) a ( + e1) + a2p(11 + 62)
aip(áz + +e) + azp(x1 +el + (e2 -1))
(a1+a))p(a +e1)
(78)
+ (( (2) ((x) a)) - x ('(((z + G))) + ('(V (z) + e)) o (V =1)),
which can be used since o admits first derivative according to Assumption Note that || 11 2x 61 ||<
0 |m e 3
(79)
23

---

Published as a conference paper at ICLR 2026
which yields
2 2 ||e
(80)
with the same relation holding for c2. Similarly, we have
0 0= ||ر a112
| <2l12 = 2x, (c1 (2) (111l12 + l1call2) (111l12 11<2l12),
(81)
which yields
2 | (El - 62)] S (||ill2 + l|22|12) ||e e2l12.
(82)
We will use the following notation
max m|xx|eellla [22112] 0(1),
(83)
Vd
and
| -1ll2 0().
8
(84)
dd
Notice that, by definition, we have = (e). The idea to prove that, with overwhelming probability. there exists solution to (76) such that o(1). This then readily implies the claim of Theorem To do so, we state and prove number of preliminary results.
Lemma C.1. We jointly have
IVVllap O(vp/d).
IVVI2 = (p),
Σ 12 (p),
(85)
with probability at least 2exp (-clog² d) over V. Furthermore, we have that
xEV7sd-1 ||<p())]22 =((V))
sup
sup revast-1
(86)
with probability at least 2exp (-clog² d) over V.
Proof. The first equation holds with probability at least 1 2 exp(pccc due to Theorem 4.4.5 in (Vershynin 2018). The second equation direct consequence of Thcorem 3.1.1 in (Vershynin 2018). For the third equation, due to Theorem 3.1.1 in (Vershynin, 2018), we have that
||||æ|12 111
0
(87)
which implies
|||
elpp
(
(88)
Then, we have that the Orlicz norm
|| 1|
O(1), which also implies ||
0(1).
1/a/ 2023).
Then, due to Lemma B.6 in (Bombari et al.
we have that
|| = O(p),
(89)
with probability at least 1- 2 exp (-c log² d), where we also used Assumption 3 The last statement statement can be obtained via the same argument in 31).
Lemma C.2. Let pt, P2, P3 TR. be sub-Gaussian random variables, necessarily independent. Consider the random variable
= min (prl) lpzpsl.
(90)
where M = w (1). Then, Z - [| is sub-exponential with parameters (v, oi) (see Definition 2.7 in Wainwright 2019 such that
0(),
a = O(M).
(91)
24

---

Published as a conference paper at ICLR 2026
Proof. Since the p-s Gaussiann,, have that both the absolute value of the mean and the second moment of (and therefore its variance) are upper bounded by positive absolute constants. Denote with 1 constant order upper bound on the absolute value of [[ Furthermore, without loss of generality, we will consider the sub-Gaussian norms of P1, P2, P3 to be equal to 1.
Consider a real number such that 4M S 1. Defining 2 Z E| and noting that e S
1 1 2²el=1/ for every = E R (due to the mean-value theorem), we have that
X 2²elAl1e 2
E
AZ
< E
+
XZ
+
2
X2
7 2
$ 1 E
2
11+
2
2
Micaralt
(92)
X2
(1P1p2ps) + +C1)² 1
+1+
2
E ((PIPaps) (1PIPaPs++CI))"
+G))
1/2
E [ (
1 1/2
1+
$ 1 C2A²
$ e C2X
Here, in third line used Z < M|ppps|: in the fourth line used that M 2 C1 and Z 1p12pp3l: in the sixth line we upper bounded the expectations via an absolute constant, as |p2Ps| is sub- exponential with norm Thus, we can a 4., and for all [^] S 1/a, we have
E
< C2A2
(93)
which gives the desired result according to Definition 2.7 in (Wainwright 2019).
Lemma C.3. We have that
( - () TTT ((v(x1 + (2) - pp(11 + ()) - (VV(z (V(c2 (V(c2-1)) -)))
(94)
= =0 (po% + d dlog do²),
with probability at least 2cxp ( cc log d) over
Proof. Since @ differentiable due to Assumption exists Ç E Rº such that
by the mean-value theorem, we have that there
p(œ1 + e2) p(11 e1) 6' (V(( + e1) +1) + (V(e2 ei)):
(95)
where each entry of Ç such that Se [0, (V(c2 c))l (or So E [[V(2-G))a 0). [V(ez - -1]l is negative). Then, we have that the thesis becomes
(c2 ei) TVT ((0'(V(z) +G1 + d'(V(z + (V(g ct)))
(96)
O (no + dlog² do²).
First, get _d be defined
62 6
(97)
8
i.e. the vector lying on the sphere Vdgd-1 with the same direction 62 <1. Then, dividing both sides of (96) by 8 and expanding the sum, the desired result can be reformulated as
(UTE) (' (a) + ( + (c) 2 2'(1ī (x1 +()) (VI =0 (0+ dlogg d) 1).
(98)
25

---

Published as a conference paper at ICLR 2026
Due to Assumption 2 we have both d'(2) I L and (0'(2) - 2'(22)l S 11 22/-
Thus, the
previous equation is implied by
P
2L ( 1 [T (vT 0 ( d dlogg 2 d
Σ
min
(99)
as we have |cx| & 01g El from its definition in 95
Let us now consider an Vd-net of vdsu-1, namely { JM m==1, such that for any E vdsi-1 there exists E [M] such that || - =m 12 e vd. Due to Corollary 4.2.13 in (Vershynin 2018). for we have that the net can be chosen such that M I (3/e)(. Setting = d d=3/2, we have that - 2|2 S. 1/d, and M S loidlogd, where 0j is an absolute positive constant. Consider a generic element zm and define
there exists m² E [M] such that || - -mm
2L - 1u minl x
T(m)
Σ min k=1
(100)
Each term T/(m) in the sum above is such that its expectation is
B
T (m)
Eus
min
22
L'
UE
(ny xmm
/ S L'Eve
|1 xm 31
0(1).
(101)
Furthermore, T(()) is sub-exponential (in the probability space of un)) with parameters (v, a) (see Definition 2.7 in Wainwright 2019)) such that
= 0(1), a a= 0
(102)
due to Lemma
Thus, Equation (2.18) (Winwwight 2019) guarantees that
Py
(m))
Bag
(
dlog" d p
I exp
(-c2 min (p. log d))
(103)
S exp (-c3dlog² d).
where the last step used Assumption obtaining that
Next, we perform a union bound on the elements of the net,
T(m) 0 (p+
=0(p
d dlog" d
sup mEMM
(104)
6
with probability at least 1 cxp this same probability, due (101) we also have that
log d + Ci cid d) 2 1 ccxp (-cadlog² d). Then, with
2L (5)))
(v )² =²=0
d log d
min
T.' 0/ fmm
(105)
8
Since the min function is Lipschitz in any of its arguments, for every ie E [p]. we have
2T c
2h (5) L' I l
S L' |oxlll ll5 x 1lz = O ||oeel2
min
L'
0k
min
(106)
d
Thus,
2L 5
The min-l))
min (2%. 2L I'' ux El (MT xm=))))))
min
1/k
(107)
C2 || l 112 Opp)
Am1
where the last step used the first statement of Lemma C. and holds with probability at least 1 exx (cs log" d). Furthermore, for every & E [p), we have
(oT = )² (e x) = lexl (x -E) 1i (I + +E]
|10a
(108)
< 2/d || 1 11 - Ell2 =
Vd
26

---

Published as a conference paper at ICLR 2026
which yields
Σ min
- ²
(vI
S
Iklll - Opp).
(109)
again due to Lemma C.I
Finally, applying the triangle incquality to 105
(107
and 109
gives
2L 8
L' Iu |
(vEC)² =0 -01
d log d
min
(110)
with probability at least - 2 exp (-co log d), which concludes the proof. Lemma C.4. Suppose E = o(1. Then, we have that
(t2 (22-c)) (V'(((a) + +e1)) (V(e2 - -i))) | E1 1
ppl
=(po2),
(111)
d
with probability at least 1 cxx (-clog² d) over V.
Proof. First, let & E IRd be defined as in 197 Then, the desired result can be reformulated as
(un (0) + +e))) (vn E)² ppd = o(p).
(112)
Let now consider v d-eeet of vdgd-1 (as we did after 99 ). Setting d we have that there
exist (5) and m²(") in [M] such that ||c s ll 1/d9/2 (In e1) - l12 1/d9/2, and
the size of the net is M S cordlogd where cı is an absolute positive constant. Consider two generic elements of this net: x m))) and maays and define
Σ
(vT (m (n) (= )²= Ev (vT (ma)) (M a (m
(113)
Since d' (o. x men) S L, each element of the sum is sub- sub-exponential (in the probability space of Uz). Then, due Bernstein inequality (see Theorem 2 in (Vershynin 2018).. we have that
Py (I(nn)) ml))) C1 dploog
< 2 exx (-o2 min (G d, divdllogd))
(114)
< exxp (-cgCidlogd),
where the second step is consequence of Assumption 3 Performing a union bound, we have that, for every pair of points on the net (there are less than of such pairs), including of af and
xe m the equation above holds with probability at least 2 exp (-c3 log d 20,d log d) > 1 2exp loc d) if C is chosen sufficiently large. Thus, with this probability, have
(1 (0))
o (ut ( (m)))) (ut ar (e)m Ery [d' (1(x=)me)) (1T ))))))))))))
Σ 0' x (v pE 06 (pt) (pε)²
(115)
0
dp log d = o(p),
where we used Assumption and introduced P and O two standard Gaussian variables with correlation (I)))e))
x. / /d. Note that
2
(pE)² 2 = 1 22
= to (pE) + 22h₂ (pE)
(116)
2
27

---

Published as a conference paper at ICLR 2026
where by and fy denote the Oth and 2nd Hermite polynomials. Thus, we have that
(I (Iiite)
E Φ (p2) (pt)
Mo
of V2
(117)
o' where Ho is the Oth Hermite coefficient of ø'. Note that po corresponds to the 1st Hermite coefficient The second term on the RHS of (117) can be bounded
of o, which is fn # 0 due to Assumption via
2
(=))
x mmte)
-
||
|
l1z [mics
- -1l2 + || - 20111--0
11 11E112 + (x) + ta)T
r (c1
8 + cJ (c1 (2)
(2)
= (2 + de
(118)
+
8
where we used
82 in the last step. Then, plugging in (117) we obtain
E3 o' (P (pE)*
p1 =
(( +
Jt
= o(1).
(119)
We also have
8' (Uk mnio) (o% x(())) - ~0'(0) (1/ (21 + (1)) ()
(d' (v smmca:)) 06 (1/ (Ir + +1))) (v ( )²
+ ø' (vk (x1 + E1) (vh) mm))) 2² (0g ())
(120)
$ L' | 2 || - x1 - E1112 12l d 2L || || El12
$ C2
vd
where C2 some positive constant. This yields
(22
(U mn) (n x ammce:) o' (1) +1) (vTee)
o(p).
(121)
with probability at least 1 - 2 2exp (-os log" d) due to Lemma inequality to (15).. (199.. and (12T). the proof is complete.
C.1
Then, applying the triangle
Lemma C.5. Suppose o(1) Then, we have that
0 (100) +
logd)
|a + a2l = O
(122)
Vd
with probability at least 1 exp (-clog² d) over V and X.
Proof. Consider
78
written as
(xr)) = (a1 + 02) + (1)= + a2 (p(z) + (2) p(11 + +c))
(123)
Let us now take an inner product of both sides of 123) with V1 Due to Lemma C.I and since æq is sub-Gaussian vector independent of V and x2 due to Assumption[] we have that
V p((2) o (paa log
(124)
with probability at least
2exp (-c1 log² d) over æn and V. Then, consider
x VT (((z E1) udll < x V o (V(z, +e)) 2TV (VVz)))
(125)
+ +| [oVas) - /rl),
((Vx1)
28

---

Published as a conference paper at ICLR 2026
and let bound the two terms the RHS separately. For the first one, since & is L-Lipschitz by Assumption 2 we have that
1 V e (V + EI)) - zi V <(Vx1)) < L [V [V O (pe),
(126)
with probability at least - 2 exp (-c1 log d) due to Lemma C.1 and (83). For the second term in the RHS of (15)), using the Hermite decomposition of Φb have that
2 V ((V21)
Mipl
Uk 2
Evg (1(2)
(127)
Since Φ is Lipschitz, we have that ( 21) is a sub-Gaussian random variable (with respect to v%)), and thus U/ 21 ([]xx) x1) are i..dd sub-exponential random variables. Thus, Bernstein inequality (see Theorem 2.8.1. in (Vershynin) 2018) yields
21 V @(Vx1) - pipl = O (vplog d)
(128)
with probability at least 1 - 2 exx (-cs 1-cyloo log² d) over V. Then, plugging this and (26)
125
together with the fact that P4 * 0 by Assumption we have
| V (p(x + E1) - Mipl O (pe + volog d) = o(p),
(129)
with probability at least - 2 exp (-c4 log* d) over Considering now the last term in 123
have
11ę( + 62) - f((1 + aall2 = O (vp6),
(130)
due to the Lipschitzness of and due to Lemma C.1 we have
Thus, with probability 1 exp (-cs log d).
b V (p(#1 + (2) - p(1 + [)) = O (p5),
(131)
where we used again Lemma the triangle inequality yields
C.I Then, plugging (124). 129 and (31 in 123). an application of
la + azl azlp= a0lp=0 (10))100
pd + p plog d
(132)
Vd
which gives the desired result.
Lemma C.6. Suppose = o(1). Then, we have that
|a2| = )) lai + a2l = 0(),
(133)
with probability at least 1 exx (-clog² d) over V and X.
Proof. The proof consists in considering the inner product of both sides of 78 namely
xx(2)) (an (2))((1 + +e)
+ 02 ((p(1) + + p(1 +))) (V(c2 -()),
(V(e2 -1)))
(134)
+ a ø'
with ((E2 - e1).
First, we have that the LHS reads
((2-g)TT T ((x2) = 0
(135)
due to Lemma C.1 with probability at least 2 cxp (-c log² d) over V. Consider now (c2
e Ty p(1 + ).). A net argument similar to the one used to obtain the third statement in Lemma
yields
(6)-G) p(1, + +(1 mip (e2 - (x) + E1)
6p = 06v/ndlogd
(136)
d
d
29

---

Published as a conference paper at ICLR 2026
with probability least 1 - eex (-cz log d) over V. This, together with 82) gives
and Lemma C.5
(01 02)(c2 -e) V pp1 + + =0 -0((0))0 va b
dl
(ov
6p dep
(137)
with probability at least 2 exp (-1a log d) over V and X. Due to Lemma
C.3
we have
(c2 VV ((v(21 + 62) - 4(11 +()) (V((v) (V(e-
(138)
O (po* dloog do²) o(po*),
and due to Lemma C.4 we have
(E2 e)) - (0'( +e)) (V(e2 - =1)) |22
l2 ppl
o(po²),
(139)
jointly with probability 1 - 2 exp (-c, log d) over V. Then, taking 135 together, have that
137
138
and
139
||2 G1l2 Lld A1 A As A4.
a2
(140)
where
[A1 O(ōp);
( (sVndlog
6p d²
+ +8cp) )) =(6p) (la2lp0"),
[A2 O
|a2 6+
(141)
|Aal
a2 1p0*)
|A4| (1 a0 126²).
As μa # this readily implies that
|22| = 0
(142)
which, together with Lemma C.5 giives the desired result.
Lemma C.7. Suppose = o(1. Then, we have that
(225(x²2) (yp(1 + +2) - se(n + =1))]= olp).
(143)
with probability at least 1 exp (-clog² d) over V and X.
Proof. First, following the same decomposition considered in (95). we have
( T (p(in + e2) - p(x +e))]
s {122((12) + (o2p(11) T T6
- ('V((z) +e)))) (V(e2 -())=)))))
(144)
(V(2))))))))
where each entry of ( such that (a (V(22-eei)) (or &x [V(e2 - =1)l2 is negative). The first term on the RHS can be bounded as
[[V(e2 - ei)]e 0).
(22)((>)) ((o((V(z) +e1) () d' + +e)))) (V =1))
< [02
Σ
pb 122) min (2I, I.' I (c2 a)) 1o (c2 n))
(145)
A=1
|a2| 0 (po² d dlog² do) O (pò + dlog² d)
with probability at least - 2 exp ( (-c log² dd) over V and X, due to the same argument used in
Lemma C and where used also Lemma C.6
Next, let us look at the second term on the RHS of 144), and consider an c /d-net of Vdgd-1
(as we did after (99)). Setting d=2, we have that there exist m((), m()1) and m (#2) in [M]
such that [ x s 1/d3/2 (where is defined in 197)). [x1 6)) of m 1//3/2
30

---

Published as a conference paper at ICLR 2026
112 - 1/d and the size of the net is M I eoadlogd, where 0g is absolute positive constant. Consider three generic elements of this net: xe mma xt m(a) and w (3) and define
- -m -
T(m! m m)
Colk ( ma ( mess) (vh ( mon))
(146)
Bun @5Vk x ) (vk mmoo)) (Nk o mm)
Since ø' (v. ( < I, each element the sum is sub-exponential (in the probability space of vx)). Then, the argument based on Bernstein inequality used in Lemma C.4 after performing union bound on the net, yields
Ti (x1)) (5)))
Σ (olo) mi ) (v (m())) (v mmse)) p1 (p o (Pm,) (DE) o(p),
(147)
with probability at least 1 2 exp (-c3d d) (due to Assumption 3 where we introduced PL.1 Pr and p three standard Gaussian variables with correlations
(I (
2 mlle))
(x (mm )
Txe
P12 corr (00,
Pig corr (Pr,
mi
d
d
(148)
(x (122)))) ) Tu
P2g == coir (Poz, PE)
d
Note that
|p12|= = o(1),
ooel=
(149)
where the two bounds hold due our net definition, due to | x2 o(d) with probability at least 1 1-2exp(--ee log" d) (coming from Assumption 1 and due 82 By Isserlis' theorem (or generalized Stein's ' lemma) we also have
[0(002)000 (p..)) pε] = P2ę1B ('(n' (Ptn) + PIglE
(0pp)) 00" (pm))
(150)
We have that
|IeeE @(P )d" (ps.))
lenel E B(P )²]
1/2 0" (pE,) (0%)) 1/2 =0())
IE
(151)
where we used (49)) [0"1 S (L' being the Lipschitz constant of Φ') and that T is Lipschitz due Assumption 2 To study the first term the LHS of (150), notice that the Hermite coefficient of order 0 of Ø is O. since the Hermite coefficient of order of Φi is O by definition. Thus, denoting by 14, FY the r-th Hermite coefficient respectively of Φ', Ø' we have
P2.E (Po (Pz..) )}
< |2el
P12
r=1
< |112|
Σ (i,))
Σ (14)2
(152)
< |12 E
33 (p )²]
1/2
E
of (22,))²
====0 o(1),
=01),
where in the step we used 119
[6 S and that @ Lipschitz due to Assumption!
Putting
[51 and (122 in (150), and plugging this in (147) yields
Hlv (e )o' (vy sm
(uy T xmmo)) = =o(p),
(153)
k=1
with probability at least 2exp(-ppppp -cs log d) over V and X.
31

---

Published as a conference paper at ICLR 2026
Then, following similar argument as the one that led to 121 obtain
Σ Ö(uk oe (o do (ot x m (1x x mie)) - 2(0 x2) (vk (a) +ei)) (v = =o(), (154)
with probability least 2 exp (-c6 log d) over V due to Lemma C.1 together with the result of Lemma C.6 yields
Putting 153 and (154)
(22)(x>) (V + (1) o (V((2 61) = o(p).
(155)
with probability at least 2 exp (-c7 log d) over V and X. This last equation, when plugged in 144 together with (145). gives the desired result.
Proof of Theorem 2
Let consider
p(x²)) = a1 +(1) + a2p(p11 + +2),
(156)
where
| + fall2 |m| c2ll2 Vd.
(157)
Suppose by contradiction that there exists solution to the equations above such that o(1). Take the inner product of both sides of (156) with the vector ((x2)) namely
((x2)² ((12) (a1 + (2)) c(x +e1) + (22(2)2) T (s((x) + + p(x1 + +
(158)
For the LHS, we have that
(x2)) (x(22) = (p)).
(159)
with probability least 1 - 2 exp (-c1 log² d). due the first statement of Lemma B.1 For the first term the RHS, we have
(a1 a2) ((x2) p0z) + (a, + 02) p(z2) p(21)]
(160)
< a1 11 ( ll L || op ||e = o(p),
with probability at least 1- exp (-c2 log d), due to Lemmas expansion of Φ and @ we have
C.I and C.6
Then, using the Hermite
((x2) (((1)) p
I2 d
o(p).
(161)
with probability at least exp (-03 log² d) due to Bernstein inequality. we have |n] 01 = o(d)
with this same probability due to Assumption
[ we readily obtain
((0 + a2))(x2) p())))()))))))))))))))))) o(p).
(162)
where we also used the bound on |a1 + 02l from Lemma C.6
Finally, due to Lemma C.7 have
|a2σ(1=2 (p(21 (2) p(x1 + + o(p)
(163)
with probability at least 2exp (-c4 log" d).
Plugging 159
160
162 and (663 in 158) generates a contradiction with high probability.
This implics that, with probability at least 2 exp (-cs log² d), we have = 2(1). Taking the intersection between this event and the described by Theorem T we obtain the thesis.
n
32

---

Optimization details for the reconstruction algorithm. We provide precise implementation details of the reconstruction algorithm. The inputs of our procedure are the model's 's optimal weights H* and the structure of fRF. i.e., V and Φ. As already mentioned in Section 5.2] in the case of neural networks where initialization is not zero, we define 0 å o! ol" where d, are the initial parameters and 8" are the trained parameters after gradient descent converged on the training set. The superscript (1. indicates the weights of the last layer. For neural networks we also assume access to their trained weights of all layers Published as a conference paper at ICLR 2026
D IMPLEMENTATION DETAILS
Computational resources. We executed all the experiments on a machine equipped with two GPUs (an NVIDIA GeForce RTX 3090, 24 GB VRAM and NVIDIA RTX A5000, 24 GB VRAM), an Intel(R) Core(TM) 19-10920X CPU @ 3,50GHz and 128 GB of RAM.
Training procedure of neural networks. By default, we train both two-layer and deep residual networks with full-batch gradient descent with step size 10-S on square loss for 10 steps, unless stated otherwise. For the classification experiments on random features and two-layer neural networks, we set the step size to 10 and optimize logistic loss (in the case of binary classification) or cross- entropy loss (in the case of multi-class classification) with full-batch gradient descent for 10 steps.
...., (0))), but we only require knowledge of the initialization of the last layer o(4) and their internal structure. The reconstruction problem solved by minimizing the following objective via gradient descent with momentum:
arg arg X-I1a.ll=vva
| 0-
(164)
We initialize the rows i. as i.i.d. standard Gaussian vectors. To efficiently compute the objective in (164) at each gradient descent iterate, we leverage the fact that, by definition, P is symmetric (PP) = p and idempotent ((P))= = P Expanding according to the definitions and properties above,
112 0 P0 ((X) |
=00'T [ 0 PO
[0']((I- $ 6)00
= [0"TT0- 0" - [0r] T $ (T -00
[0']T0- 0- - |0-1T $ a.
Here, is the solution of the system of linear equations in unknowns ($4) 60 which can be numerically computed via the conjugate gradient method (Hestenes et al. 1952), skipping
the need of inverting explicitly Φ E m=*x" at each iteration. After the gradient descent update on X, we then normalize its rows i; to force them to lie on the d-dimensional sphere vd gd-1, More precisely, f; < Vd /;/ thus respecting the fact that minimization should happen on the sphere as in (144. Unless stated otherwise, the step size set by default 10 for the CIFAR-10 experiments and to 20 for the experiments on synthetic data. On ImageNna we use a step size of 8 103 Momentum is set 0.9. We consider the reconstruction optimization converged when the normalized reconstruction loss L ((X)) / [[3 drops below 10-7 Normalizing by ||0*] makes the loss of order 1 at the beginning of the optimization so that the chosen threshold of 10- corresponds to the effective numerical resolution in floating point representation. Unless explicitly mentioned otherwise, in every experiment we perform, the optimization is run until the reconstruction loss has converged.
Statistical robustness. To ensure that our findings not tied to particular random initialization, all experiments are repeated over multiple random seeds. Each seed induces independent initializations of network parameters and of the reconstruction variables X. All the quantitative results reported in the paper correspond to averages (and variability) across these runs
CIFAR-10 protocol. For random features experiments, we construct a balanced subset from the CIFAR-10 Krizhevsky et al. 2009) training split by iterating once through the data and collecting the
33

---

Published as a conference paper at ICLR 2026
first n 2/2 occurrences of the "frog" class (negative) and n/2 of the "truck" class (positive), yielding samples. Each image is flattened to d = 3 -.32: 32 = 3072 and concatenated into X E Raxd We standardize using subset statistics computed over the selected examples. Targets are Y E {=1]", with the first n/22 entries set to -1 and the remaining n to +1. We use "frog" vs. "truck" purely convenient benchmark. Our conclusions do not hinge on category semanties, and we observed the same qualitative behavior across alternative class pairs. For multi-class experiments, we use the same balanced construction; targets are one-hot encoded as 10-dimensional vectors with a single 1 at the true class index (and O elsewhere). Also for ResNet and vision transformer rums we use the same protocol as for random features, but images are kept tensor form (Ix3x32x22 and normalized per channel using the full CIFAR-10 training split statistics (mean [0.4914, 4822,, 0.4465]. std [0.247, 0.243, 0.261]).
Tiny-ImageNet protocol. We construct balanced subset from the Tmny-ImageNet <Le & Yang 2015) training split by iterating once through the data and collecting the first n occurrences of class 2 (negative) and 2 of class 116 (positive), yielding samples. Each image is flattened to = 3- 64 64 = 12288 and concatenated into X E Rnnxd, We standardize using subset statistics computed over the selected n samples. Targets are Y [=1]", with the first n/2 entries set -1 and the remaining n12 to +1. We have randomly drawn class 2 vs. class 1 116 and used this pair purely as a convenient benchmark. Also in this case, our conclusions do not hinge on category semantics.
D.1 ADDITIONAL DETAILS ON DEEP RESIDUAL NETWORKS
In this section, we give precise implementation details of the class of deep residual networks we consider. We focus on ResNet-style architectures (He et al. 2016) adapted to CIFAR-10 images while preserving the canonical residual topology. Specifically, ll,, we remove batch normalization and max pooling layers that feature map resolution and statisties are maintained throughout. Apart from this, the residual block structure and overall layout are preserved. More formally, let Φ(-) = (eLU(-) applied element-wiss and let C denote a bias- free 2D convolution with kernel size x k, stride I and padding mapping from b channels. Let residual block be
B B(u) <uu + 3x3 (x)))
(165)
Given an image E R33x32x32 (as the case of CIFAR- CIFAR-10examples) we consider in our experiments deep residual networks with architecture
z0 C28x28 [x]
=b = B(z-1) for = lelbb==..... 1,...:4, [RN(F) = vec(zz), (166)
with 0(4) E R.--77 the last layer's parameters. We denote with vec(.) the flattening of the dimensions of the 3D tensor 24 to a vector. The choice of dimensionality for ((4) is motivated by the first convolution mapping the spatial size for CIFAR- 10 images to / x 7 x and the blocks preserving it. We select the number of output channels h based on the choice of the number of parameters in the last layer 2(4) these two quantities are tied together, being h rL /72, eventually truncated to the nearest integer. Parameters of the first convolutional layer are initialized as 0 NO, 1/d) ii.d., while for > parameters are initialized as 0 ~ ~N 1/fan_in) i.i.d. Here, fan_in equals the number of input units (for convolutional layers: h k2; for the last linear layer: (()))
E ADDITIONAL NUMERICAL RESULTS
E.1 FURTHER RESULTS ON SPAN INCLUSION
As mentioned at the end of Section and in the caption of Figure 2 test whether the features computed on the training dataset are spanned by the features of the reconstructed examples. To this end, we calculate the average per-feature orthogonal residual, formally defined as
r())
(167)
where P I I Pa projects onto the orthogonal complement of span (rowsross()), Thus r r()) = 0 if and only if every (pxx)) lies in spon(rows($)). The normalization by nyp makes r(δ) of order 1 so that values of r()) < indicate numerically negligible residuals (Le., effective span inclusion).
34

---

Published as a conference paper at ICLR 2026
RF [Lineur plus Noise, Synihosie)
2 Layer NN class, CIPAR-10)
RoNNe (Binary Labels, CIEAR 10)
y
Rocactrucion Eror
Thaining Losk
Aug (PPtaeed ba
Figure 9: Features of the training dataset & are spanned by the features of the reconstructed dataset a We consider RF regression with ReLU activation on i.idd. samples uniformly distributed on the d-dimensional sphere (d 100, 20), 10-class one-hot regression with a 2-layer ReLU network trained with gradient 10) and regression binary labels (frogs
descent CIFAR-10 gradient descent CIFAR- 10 (n 10). We report mean (solid line) and standard deviation (shaded area) for the reconstruction error (in red), for the training loss (in black) and for the per-feature orthogonal residual of projecting & onto span (panfrows(4)) rows($)) (in blue), as the number of parameters increases. We indicate with o the number parameters last layer. Statistics are computed across 10 distinct random seeds.
trucks) with ResNet trained with
Figure 10: Reconstructing CIFAR-10 training images from RF model with the activation function satisfying Assumption We repeat Figure 4 with the same seed, reconstructing CIFAR- 10 training images 100) from an RF model with activation function Φ(z) ReLU(z) tanh(z) on binary labels at p = 10dn. Odd rows report the ground truth images, while even rows the reconstructed ones. In this experiment the activation function is consistent with Assumption and indeed, this excludes the possibility of reconstructing
sign-flipped versions of the originals.
Figure 9 summarizes the interpolation-rrcoonttucci behavior across RF regression (synthetic data, same setting of Figure 3). two-layer ReLU neural networks (CIFAR-10, multi-class, same setting of left Figure 6). and deep residual networks (CIFAR-10, 10, binary, same setting of right Figure 6). Both the reconstruction error (red) and the per-feature orthogonal residual (blue) remain large until the model crosses the threshold p dn (p(4) dn for neural networks), after which they drop sharply. This trend is consistent with Figure 2 successful reconstruction occurs precisely when pp(;)) E span (rows($)) { } for all i, ie., when I <p(x;))l2 F 0. Also in these settings, for p S the optimization converges to the non-degenerate case Pa = I, which makes the orthogonal residual trivially zero.
E.2 DATA RECONSTRUCTION ON RF WITH MIXED PARITT ACTIVATIONS
Figure [oTrpeaas the setup of Figure seed and optimization protocol, but replacing ReLU with the activation Φ(=) ReI.U(z) + tanh(z)
f on CIFAR- 10 (binary labels, n = 100) using the same random
35

---

Published as a conference paper at ICLR 2026
that has high-order Hermite coefficients of different parities. In contrast to Figure 4 sign-flipped reconstructions appear. This outcome is precisely what Assumption 2 and Remark predict: ReLU alone violates the assumption (its odd Hermite coefficients #22+1 vanish for é >> 1), allowing z; and -x; to be indistinguishable under the reconstruction loss. Adding tanh supplies non-zero coefficients of opposite parity, restoring identifiability of the sign and removing this degeneracy.
E.3 ADDITIONAL ABLATION STUDIES
Effects of different learning rates in the reconstruction optimization. To assess the effect of the step size on the success of the data reconstruction. we have conducted an additional ablation using Binary CIFAR-10 10 (n = 20) on the RF model. Starting from the base step size "y" = 2 10S we have considered 1) E {n/ /4, 17" /2, 17": 2n," "n]} across 10 distinct random seeds. In Figure [1, we plot the reconstruction error, the total number of iterations for which the reconstruction algorithm is run, and the final reconstruction loss L. as a function of the number of parameters p. For larger step sizes (2ny" and 4sy"), we observe oscillatory behavior of the reconstruction loss that prevents convergence within a reasonable budget. Guided by the smallest step size (1)" /4), for which the loss consistently converges to zero within at most 6 10* iterations across seeds and number of parameters p. cap the optimization at 6 10a iterations in this experiment. As shown in Figure 11 for all step sizes that converge within this budget (1)* /4,n" / /2, nn') )" the reconstruction error drops to zero once p >> dn, indicating that the reconstruction procedure robust to the choice of the step size provided it is not taken excessively large.
Number of reconstructed samples different from number of training samples. So far, we only discussed the results of optimizing ((X) when setting X to a matrix in Raxd In Figure 12 we numerically investigate the effects of setting X to be a matrix of size ñ x d, when á & n. Specifically, consider Binary CIFAR-10 with 50 (25 "frog" images vs. 25 "truck" images) and RF model with p 10dn. When reconstructing fewer samples (n < n)) we observe that the outputs of the reconstruction often mix the structure coming from multiple ground-truth images. Intuitively, this translates in the fact that the reconstruction seems to be minimized when X has rows that are a superposition of multiple training data, rather than a subset of the training data themselves. Increasing progressively reduces this noise. Conversely, when reconstructing with more rows than training samples (n > n.) we find that 50 of the recovered images match the n 50 training samples, while the extra â - n = 10 reconstructions are simply duplicates. From a practical perspective, this means that, in order to estimate n,, it suffices to iteratively increase á until the first duplicate appears.
we provide numerical results on vision transformers trained on CIFAR-10 in the multi-class setting, using the same reconstruction procedure. We study randomly initialized vision transformers (Dosovitskiy et al., 202T) akin to ViT-B/16 on which we vary the embedding dimension trained on one- hot encoded labels from the first five classes of the CIFAR-10 dataset (n = 5). Vision transformers display a similar phenomenology to fully connected and residual architectures: when the number of parameters p(²)) exceeds dn, the reconstruction eтror goes down and images are recovered successfully.
Reconstruction from vision transformer architecture. In Figure [3
Effects of weight regularization. So far, we discussed reconstruction from the weights of a trained model without regularization, as expressed in Eq. (2. Adding a ridge parameter À > 0 would change the training loss as
Liroin (0)
Σ (p(x,)
To 0 w)²² 11101
(168)
whose unique minimizer is
0r - T (ΦDD + +nXi)= Y.
(169)
For fixed value of À (not dependent d, n and p), and due to Eq. 14). we have
|| (n), Amin (Φ 9(p).
(170)
Intuitively this suggests that, as p grows large, the effect of a fixed regularization term À becomes negligible, and reconstruction is still possible. This is verified numerically in Figure [1]] where we see that even for very large values of À we find a qualitatively similar threshold for successful reconstruction.
36

---

Published as a conference paper at ICLR 2026
CIFAR-10 (Binary Labels, n== 20)
Rocossttetion Groc
Deconsrrctoon 1.000
7//4
7/2
Figure 11: Ablation on step size used for the reconstruction procedure. We consider RF regression with ReLU activation binary labels (frogs trucks) with 20 images (10 examples per class) from CIFAR 10. Starting from the hase step size 17" 2 10 used in all the CIFAR-10 10 experiments, error (left), total numher of training iterations needed by the reconstruction algorithm (center) loss (right) as function of the number of paramcters aggregated over 10 distinct random seeds. Guided by the smallest step size (1)" /4), for which the loss consistently converges to zero within at most 6 10 iterations cap the optimization at 6 10 iterations.
report the reconstruction
reconstruction
across seeds and number of parameters
(Top-50 recenstructed examples)
20
Surplus examples (as ñ m))
Figure 12: Dataset reconstruction without knowing the exact number of training samples n. We fit an RF model with ReLU activation and p 10dn binary labels (frogs trucks) with 50 images (25 examples per class) from CIFAR-10. We then optimize the reconstruction loss C(X) with X E Raxd and the number of reconstructed samples ñ different from We assess both the case when reconstructing fewer samples (ñ left column) and more samples (ñ n., right column) than the ground- -ruth number of samples nt. In the latter case, we also plot extra
examples.
Effects of pruning. In Figure 16 we explore numerically the behavior of our reconstruction
algorithm on a pruned network, following the same synthetic setup Figure 3 We first obtain 0" ++ Y and then run Optimal Brain Surgeon (Hassibi & Stork 1992 which in context
(convex problem on square loss) provably incurs in the minimal increase in training loss, given a d 100, 100
fixed sparsity ratio. We select either d 30, 20 (left plot of Figure (right plot of Figure reporting the results for several sparsity ratios. As expected, pruning seems to increase the number of parameters needed for data reconstruction.
37

---

Published as a conference paper at ICLR 2026
Vision Transformer (Multi-class)
19
30
122
DP
Beoonetruction Broor
Training
Avg. Payoriaal Vitt
Figure 13: Thresholds for label fitting and data reconstruction for Vision Transformers trained with gradient descent on CIFAR-10 images. (Left) We consider regression with the square loss, training Vision Transformers on the one-hot encoding of S-class labels. We report mean (solid line) and standard deviation (shaded area) for the reconstruction error (in red), for the training loss (in black) and for the per-feature orthogonal residual of projecting onto span(rowse ()) } (in bluc), as the number of parameters in the last layer (2 increases. Statistics are computed across 10 distinct random seeds. (Right) Results of the reconstruction when (d) 4dn. The first row reports the ground truth images, while the second row the reconstructed ones.
Tiny- ImageNet (Binary Labels, 20)
10
Roonsstenction
Triining
Figure 14: Thresholds for label fitting and data reconstruction on Tiny-ImageNer (I.fft) We consider regression with ReI.U activation on binary labels (class 2 vs. class / //6) with n = 20 images (10 examples per class) from Iny-TmmgeNet (d 12288). We report mean (solid line) and standard deviation (shaded area) for the reconstruction emror (in red), for the training loss (in black) and for the per-feature orthogonal residual of projecting & onto span rros(()) ) (in blue), the number of parameters increases. Statistics are computed across 10 distinct random seeds. (Right) Results of the reconstruction when p 10dn. Odd rows report the ground truth images, while even the reconstructed ones which are all visually very similar.
38

---

Published as a conference paper at ICLR 2026
d 30,
20
d
100, 72
100
1-0.0
0.0
1.0
1.0
100
10000
1000
0.
0.4
02
06
P Reconstruction Error
Training Loss
Figure 15: Thresholds for label fitting and data reconstruction in the presence of regularization. We consider regression ReLU activation, fitting noisy linear model with & penalty (ridge). The training data is i.idd. uniformly drawn from the d-dimensional sphere. We report mean (solid/dashed lines) and standard deviation (shaded areas) for both the reconstruction error (solid lines) and training loss (dashed lines) as the number of parameters p increases, at different choices of input dimensions d and number of samples n. Statistics are computed across 10 distinct random seeds. Lighter colors refer stronger regularization, which does not significantly deviate from behavior training without regularization (red lines, occluded).
d
30,
20
d 100,
100
1.4
Sparsity
Sparsity
122
0.5
0.2
0.2
06 124 UP
117
107
P
Reconstruction Error
Training Loss
Figure 16: Thresholds for label fitting and data reconstruction pruned models. We consider RF regression with ReLU activation, fitting noisy linear model. The training data is i.i.d. uniformly drawn from the dimensional sphere. After fitting, prune the trained parameters 0" with Optimal Brain Surgeon (Hassibi) Stork 1992) to desired sparsity ratio (i.e., p' with p' the number of remaining parameters). We report mean (solid/dashed lines) and standard deviation (shaded areas) for both the reconstruction error (solid lines) and training loss (dashed lines) as the number of parameter increases, at different choices of input dimensions d and number of samples Statistics are computed across 10 distinct random seeds. Lighter colors refer to lower sparsity ratios, compared against the unpruned baselines (red lines).
39

---

Published as a conference paper at ICLR 2026
Figure 17: Multi-class training data reconstructed from neural network trained with cross-entropy CIFAR-10. We repeat experiment of Figure by training a two-layer ReLU network on n 100 images from CIFAR-10 dataset (10 examples per class) with gradient descent. In this experiment, we cast the training procedure as multi-class classification on cross-entropy loss. The number of parameters in the last layer of the network (*) 4dv.
40


Reviews:
[{"review_id": "PAE2yOvOrW", "reviewer": "Reviewer_JmYG", "summary": "The paper proposes a law of data reconstruction for over-parametrized model in random feature regression showing that the training set can be reconstructed when $p \\gg dn$ where, $p$ is parameter count, $d$ is data dimensionality and n the number of samples in the set. They provide elegant theoretical results with empirical validation.", "questions": "1. How sensitive is success to initialization and stepsizes? Runs across initalizations, learning rates; report success rates and iterations could help strengthen the paper\n2. What is the theoritical challenge in addressing the no duplicates results beyond n=2? \n3. How do results change beyond sub-Gaussian isotropic inputs? Statements/experiments under covariance is not $I$ and heavy-tailed features or discussion on how to potentially handle this in the future would help", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* Clear “law” with an intuitive threshold: The paper isolates a memorable scaling for data reconstruction in random-features regression: once the parameter count satisfies ($p \\gg dn$), full input recovery becomes feasible. This makes the results feel elegant and easy to understand.\n* Crisp geometric criterion (Theorem 1). If the training feature vectors lie in the span of features generated by candidates, each sample must be close (in input space) to some training sample. This spanning-subspace view is conceptually simple and informative.\n* Experiments visualize two thresholds: labels fit near ($p\\approx n$), while reconstruction error collapses near ($p\\approx dn$). The figures make the phenomenon immediately clear.\n* Activation analysis. The parity/sign-ambiguity discussion (e.g., ReLU vs. mixed-parity activations) explains when reconstructions may flip signs and how to avoid it, giving a quick diagnostic practitioners can check.", "weaknesses": "1. Specialized setting and assumptions: The theory is developed for random-feature regression under sub-Gaussian data, Lipschitz activations, and a strong overparameterized regime (e.g., (p) on the order of (nd) with log factors). This is narrower than many trained deep-net scenarios.\n2. Partial completeness of theory. The uniqueness/no-duplicates guarantee is proved cleanly for (n=2); a full characterization of global optima (and uniqueness) for general (n) remains open.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NtSbSiOTTv", "reviewer": "Reviewer_heHJ", "summary": "The paper studies data memorization as the ability to reconstruct training inputs from model parameters. It shows that, unlike label memorization (which occurs when $p \\gg n$), full input reconstruction requires $p \\gg nd$, where $p$ is the number of parameters, $n$ the number of samples, and $d$ the data dimension. The authors prove that in random features models, if the span of the features of $X \\in \\mathbb{R}^{n\\times d}$ lies inside the span of the features of $\\hat{X}$, then (up to permutation) $\\hat{X}$ must match $X$ with high probability. They also propose a reconstruction loss and show empirically that the same scaling enables recovery in random features, two-layer networks, and deep residual networks.", "questions": "Please refer to the previous section", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper is clearly structured and well written, and it is easy to follow.\n2. Data memorization, in the sense of recovering training inputs from a trained model, is an important problem with implications for privacy and model safety. The paper addresses it in a timely way.\n3. The theoretical and empirical results are convincing. Although the theory is developed for random feature models with assumptions on the nonlinearity, it is compelling that similar empirical behavior appears in more complex architectures under the same scaling.\n4. To my knowledge, both the analysis and the reconstruction algorithm motivated by the theory are novel, and the results are convincing.", "weaknesses": "1. The reconstruction algorithm, although motivated by the theory, still feels somewhat mysterious. In particular, the trained $\\theta*$ is only known to be a vector in the span of the features of the training data. Enforcing that $\\theta*$ lies in the span of the reconstructed features does not immediately imply that $\\varphi(x_i)$ is in $\\text{span}(\\varphi(\\hat{x}_j))$ for all $i$. It would be helpful if the authors could clarify this.\n2. The theory appears to require knowing the exact number of training samples $n$. Is this correct? What would happen if $\\hat{X}$ had a different number of rows than $X$?\n3. In the proof sketch of Theorem 1 (lines 227–229), it seems that the roles of $\\hat{x}$ and $x$ might be swapped. Can the authors clarify whether this is a typo?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WP4emzEpQ8", "reviewer": "Reviewer_Krj1", "summary": "This paper proposed a new law of data reconstruction in overparameterized neural networks. The authors point out that when model parameters contain sufficient information to reconstruct the entire training set. The key finding is that full data reconstruction becomes feasible when the number of parameters 𝑝 greatly exceeds the product of data dimension 𝑑 and sample count 𝑛.", "questions": "1. Does this theorym could transfer to transformer or diffusion models?\n2. Will this thoerm still work when the training datapoints become morem complex with larger size?\n3. Will regularization or pruning invalidate the reconstruction law?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Clear statement of the reconstruction law with 2 new theorem.\n2. Proposed the first quantitative relationship between model size and data reconstructability.\n3. Visualization validation from light-weight models convincingly support the claims.", "weaknesses": "1. Analysis restricted to random features and small networks (even no evidence from the widely-used transformer to show whether it also works on the attention framework), not large-scale modern models.\n2. Experiments involve small sample sizes (mainly on 32*32), limiting statistical robustness on larger size image from STL10 or Imagenet.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kl0dHsjmS6", "reviewer": "Reviewer_hVw8", "summary": "The paper considers a random-features model, and proves that if the number of parameters $p$ of the output layer is larger than the total number of coordinates in the training dataset ($nd$), then the linear subspace spanned by the features of the training examples gives enough information for (approximately) reconstructing training examples. This requires certain assumptions, including some assumptions on the Hermite expansion of the activation function. Inspired by their theoretical results, they suggest a method for reconstruction without knowing the subspace of training features. They demonstrate how their method works in various settings. Also, they show how empirically p=n is the threshold for interpolation while p=nd is the threshold for reconstructability.", "questions": "The paper only considers the square loss function. However, the empirical part may also work for classification with the logistic or cross-entropy loss. That is, Eq. 11 should still hold for classification (since the max margin predictor is spanned by the inputs). Have the authors verified whether the “law of data reconstruction” also appears in classification?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The theoretical results (Theorems 1 and 2) are very nice and non-trivial. I think that understanding the theoretical aspects of the ability to reconstruct training data is a challenging and intriguing question, and the paper makes a step in this direction.\n\nRegarding the empirical results, I liked the consistent thresholds of p=n for interpolation vs. p=nd for reconstruction. The authors show that these thresholds appear in various settings, which improves our understanding of this aspect.", "weaknesses": "My main concern is that the implications of the results on reconstruction in the common setting, where the attacker does not know the subspace of training features, are somewhat limited for the following reasons:\n\nFirst, the theoretical results only consider the case where the attacker knows this subspace, and hence it is unclear whether the attacker can reconstruct training data without this knowledge. The theoretical results imply that it suffices to know the subspace of training features, which is interesting and non-trivial, but it does not allow for reconstruction only from the network’s parameters, as in “common” reconstruction attacks. \n\nRegarding the reconstruction algorithm that does not assume knowledge of the training features subspace: The proposed method relies on the fact that the output weights are spanned by the features. This observation is similar to Loo et al. (2024), as the authors noted. Thus, this method does not rely on the theoretical results, and it could be argued that they are independent of the theoretical part of the paper. The fact that it is similar to Loo et al. also makes it less novel (although the setting here is different). Having said that, I still think that the empirical results here give convincing evidence regarding the importance of the p=nd threshold. This was not studied in such a systematic way in previous works, and I view it as a valuable observation.\n\nOverall, I think that the theoretical results are intriguing and nontrivial, and that the conceptual contribution regarding the “law of data reconstruction”, which appears both in the theoretical results and in the experiments, is valuable. But given the limitations discussed above, I tend to “weak accept”.\n\nA more minor comment: In the paper, the authors mention that for interpolation, we need more parameters than training samples. A more accurate claim is that the number of parameters times the depth needs to be larger than the number of samples. Or alternatively, that the number of bits in the network’s representation needs to be larger than the number of samples. See the paper “On the Optimal Memorization Power of ReLU Neural Networks” by Vardi, Yehudai, and Shamir for details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)