Paper deep dive
A Sharp Transition in Data Reconstruction under Differential Privacy
Max Cairney-Leeming, Simone Bombari, Marco Mondelli
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Data reconstruction attacks have empirically been successful in recovering training samples from learned models, raising privacy concerns and motivating defenses with guarantees that remain valid against future threats. While differential privacy (DP) provides formal protection, choosing the privacy budget remains a challenge: small budgets severely reduce utility, but it is hard to quantify how large the budget can be without allowing accurate reconstruction. In this work, we study informed attackers who aim to reconstruct a single $d$-dimensional training sample from a $\rho$-zero-concentrated DP model, knowing all other training data. Our main contribution is to establish a sharp transition at $\rho \asymp d$ for data reconstruction: on the one hand, we derive entropy-based lower bounds for any private mechanism and any attack, characterizing a set of target priors for which reconstruction is information-theoretically impossible for $\rho \ll d$; on the other hand, we analyze a simple attack on private linear regression with output perturbation, showing that reconstruction is practically feasible for $\rho \gg d$. Remarkably, the transition moves to $\rho \asymp s$ for data lying in an $s$-dimensional subspace, demonstrating that the privacy budget guaranteeing adequate protection must be assessed in terms of the effective dimension of the data. We validate our findings via experiments on synthetic data and natural images (CIFAR-10, ImageNet).
Tags
Links
- Source: https://arxiv.org/abs/2609.37344v1
- Canonical: https://arxiv.org/abs/2609.37344v1
Trouble viewing inline? Open PDF directly →
Full Text
74,317 characters extracted from source content.
Expand or collapse full text
A Sharp Transition in Data Reconstruction under Differential Privacy Max Cairney-Leeming Institute of Science and Technology Austria max.cairney-leeming@ist.ac.at Simone Bombari Institute of Science and Technology Austria simone.bombari@ist.ac.at Marco Mondelli Institute of Science and Technology Austria marco.mondelli@ist.ac.at Abstract Data reconstruction attacks have empirically been successful in recovering training samples from learned models, raising privacy concerns and motivating defenses with guarantees that remain valid against future threats. While differential privacy (DP) provides formal protection, choosing the privacy budget remains a challenge: small budgets severely reduce utility, but it is hard to quantify how large the budget can be without allowing accurate reconstruction. In this work, we study informed attackers who aim to reconstruct a single d-dimensional training sample from a ρ-zero-concentrated DP model, knowing all other training data. Our main contribution is to establish a sharp transition at ρ ≍ d for data reconstruction: on the one hand, we derive entropy-based lower bounds for any private mechanism and any attack, characterizing a set of target priors for which reconstruction is information-theoretically impossible for ρ ≪ d; on the other hand, we analyze a simple attack on private linear regression with output perturbation, showing that reconstruction is practically feasible for ρ ≫ d. Remarkably, the transition moves to ρ ≍ s for data lying in an s-dimensional subspace, demonstrating that the privacy budget guaranteeing adequate protection must be assessed in terms of the effective dimension of the data. We validate our findings via experiments on synthetic data and natural images (CIFAR-10, ImageNet). 1 Introduction Easy access to vast amounts of training data is a key ingredient in the success of modern deep learning, naturally encouraging the collection of data that may contain sensitive personal information or copyrighted material. Standard training methods often memorize such training data, making it possible for attackers to recover information about their content from the final model (Carlini et al., 2021; Nasr et al., 2025; Cooper et al., 2026). For example, membership inference attacks are designed to determine whether a given target sample x t was included in the training set (Shokri et al., 2017; Nasr et al., 2019; Carlini et al., 2022), while data reconstruction aims to recover the full x t from scratch (Haim et al., 2022; Buzaglo et al., 2023). A way to address these risks is via differential privacy (DP) (Dwork et al., 2006), which has become the standard paradigm for provably safeguarding models from leaking private information e.g. through unintended memorization. DP quantifies data protection through a numerical parameter (ρ in Definition 1), which bounds the impact a single data point can have on the output of the algorithm. However, the noise required by DP training negatively affects performance (Abadi et al., 2016), thus limiting its adoption. In particular, this performance cost is generally noticeable for constant-order (i.e., not dependent on sample size or data dimensionality) privacy budgets ρ≍ 1, a regime that is also the usual focus in the literature (De et al., 2022; McKenna et al., 2025) 1 . This scaling provides non-trivial trade-offs for membership inference 1 The cited work often focuses on (ε,δ)-DP with ε ≍ 1. Given the conversion from ρ-zCDP to (ε,δ)-DP (Bun and Steinke, 2016), we interpret this regime as ρ≍ 1, neglecting the logarithmic dependence on δ. As an example, a zCDP guarantee with ρ≃ 1.05 implies the (8, 10 −5 )-DP guarantee reported by De et al. (2022). 1 arXiv:2609.37344v1 [cs.LG] 29 Sep 2026 attacks (Dong et al., 2022; Mahloujifar et al., 2022; Kairouz et al., 2015): informally, attacks are possible when ρ≫ 1, and impossible when ρ≪ 1. On the other hand, much larger privacy budgets yield negligible utility losses in some domains and still protect models from reconstruction attacks (Bhowmick et al., 2019; Stock et al., 2022; Ziller et al., 2024), motivating interest in the regime ρ ≫ 1 (Cyffers, 2025). In particular, Balle et al. (2022) have shown that, for suitable priors on x t ∈ R d , ρ ≪ d suffices to make reconstruction statistically impossible. However, for general priors, their bound relies on small-ball probabilities which may be hard to compute in practice (e.g., for natural language data). Most importantly, it is unclear whether the result is tight, in the sense that reconstruction attacks are possible for ρ≫ d. Our work takes a step towards understanding when the privacy budget sharply characterizes the feasibility of reconstruction from the final model parameters, identifying a sharp transition at ρ ≍ d in DP linear regression. We focus on informed attackers with access to the training set (except for the target example), as well as the hyper-parameters of the output perturbation algorithm used to train the model. More specifically, our contributions are the following: 1. We derive a lower bound on the expected reconstruction error in terms of the target’s differential entropy h(x t ), valid for any ρ-zCDP mechanism and any attack (Theorem 1). This result implies that accurate reconstruction is impossible as long as ρ≪ h(x t ). For the target distributions considered by Balle et al. (2022), or for distributions with independent entries, we have h(x t )≍ d, demonstrating the impossibility of reconstruction for ρ≪ d. 2. We characterize the performance of an explicit reconstruction attack on a DP model trained via output perturbation (Theorem 2). For a natural range of regularization parameters λ and residual clipping thresholds C clip , the attack succeeds with high probability whenever ρ≫ d, providing a tight converse to Theorem 1. 3. We extend our results to data distributions with lower effective dimension, in particular to data sup- ported on an s-dimensional subspace of R d . We obtain an analogous entropy-based lower bound (Theorem 3) and derive a reconstruction attack that exploits knowledge of the subspace (Theorem 4). Together, these results show that the relevant transition for data reconstruction in this setting occurs at ρ≍ s. We validate our findings through numerical experiments on synthetic data (Figs. 2 and 5a) and natural images from CIFAR-10 and ImageNet (Figs. 3, 4 and 5b), demonstrating the wider generality of our results beyond the technical assumptions. Overall, our work identifies data dimensionality as a relevant scale for assessing privacy budgets, providing a concrete basis for studying the risks and potential utility benefits of larger budgets. 2 Related work Data reconstruction from non-private models. Large models are known to memorize individual train- ing data within their parameters. Such data can be extracted through appropriate prompting in generative models (Carlini et al., 2023; Nasr et al., 2025; Cooper et al., 2026), or reconstructed directly from the pa- rameters of classifiers (Haim et al., 2022; Buzaglo et al., 2023; Oz et al., 2024; Shen et al., 2026). In the theoretical literature, the problem of fully reconstructing the training set has been tackled in specific settings: the heuristic method of Haim et al. (2022) relies on the implicit bias of gradient descent in homogeneous networks (Lyu and Li, 2020; Ji and Telgarsky, 2020); Loo et al. (2024) and Iurada et al. (2026) show that reconstruction is possible in, respectively, infinite-width shallow networks and sufficiently over-parameterized models. If the attacker knows the rest of the dataset, an effective reconstruction method against a generalized linear model, trained without the clipping or noise required for privacy, has also been expressed in closed form by Balle et al. (2022). Attacks on private models. For models trained with DP, the feasibility of membership inference attacks (MIAs) is closely linked to the privacy budget (Yeom et al., 2018; Kairouz et al., 2015; Mahloujifar et al., 2022), and there is a connection to privacy auditing, as these results mean that successful membership 2 attacks set lower bounds on the privacy guarantee of an algorithm (Jagielski et al., 2020; Nasr et al., 2023; Steinke et al., 2023). Reconstruction attacks have also been linked to privacy budgets, primarily through reconstruction robustness (Balle et al., 2022). This framework has been extended to give stronger bounds for specific mechanisms (Hayes et al., 2023; Kaissis et al., 2023), to use f -DP (Kulynych et al., 2025), and to reconstruct multiple data points (Swanberg et al., 2026). Additional related work has focused on recovering one batch from DP-SGD (Liu et al., 2025), specializing reconstruction robustness to discrete alphabets (Guo et al., 2023), or lower bounding the reconstruction error through the bias and variance of the attack (Guo et al., 2022), though requiring the privacy budget to be at most logarithmic in the diameter of the target prior to rule out reconstruction. Our work combines impossibility guarantees based on the entropy of the target with a provably successful attack, thus establishing a sharp transition for data reconstruction. Large privacy budgets. A classical convention in the DP literature is to take the privacy budget to be a moderately small constant (Dwork and Roth, 2014). This is consistent with theoretical analyses showing that MIAs fail when ρ≪ 1 (Bun and Steinke, 2016; Kairouz et al., 2015; Dong et al., 2022). When membership is not a sensitive attribute, much larger (possibly dimension-dependent) budgets provide meaningful protection while better preserving utility. This has been shown in the locally private setting (Bhowmick et al., 2019; Sarwate and Sankar, 2014; Kalantari et al., 2018), in language models (Stock et al., 2022), and in medical imaging (Ziller et al., 2024), with Aerni et al. (2024) even finding that budgets well above 10 3 can outperform other heuristic defenses against membership attacks. This evidence also partly motivates the recent position taken by Cyffers (2025), who argues that larger budgets should not be dismissed in favor of uncertified protection methods. Our results provide a theoretical foundation for this perspective, identifying the data’s effective dimension as the scale for assessing how large privacy budgets can be while still protecting against accurate reconstruction. 3 Preliminaries Notation. We set [n] := 1,...,n. Given a vector v, let ∥·∥ 2 denote its Euclidean norm. Given a matrix A ∈ R n×m , let ∥A∥ op be its operator (spectral) norm. Let h(a) = − R p a (x) logp a (x)dx denote the differential entropy of a random variable a. We use the letters x,X to denote feature vectors and the space of features; y,Y for labels; and z,Z for feature-label pairs. Complexity notations O (≲), Ω (≳) and Θ (≍) are meant for large input dimension d and sample size n. Linear regression. Let Z = (X,Y ) be a labeled training dataset, where X = [x 1 ,...,x n ] ⊤ ∈ R n×d contains the training data (features) on its rows and Y = [y 1 ,...,y n ] ⊤ ∈ R n contains the corresponding labels. We assume features to have bounded norm ∥x∥ 2 ≤ R and input-label pairs to be sampled i.i.d. from a joint distribution P XY . We consider the linear regression model y i = x ⊤ i θ true + ν i ,(1) where θ true ∈ R d and ν i is independent label noise. The goal of DP linear regression is to output an estimate that guarantees a privacy budget and minimizes the test risk, defined for θ ∈ R d as P(θ) = 1 2 E (x,y)∼P XY h x ⊤ θ− y 2 i (2) Differential privacy (DP) and output perturbation. We say that the datasets Z and Z ′ are adjacent if they differ in a single input-label pair. We quantify DP via ρ-zero-concentrated DP (ρ-zCDP) which uses the α-R ́enyi divergence between two probability distributions P,Q: D α (P∥Q) := 1 α− 1 log Z dP dQ α dQ, α > 1.(3) Definition 1 (ρ-zCDP (Bun and Steinke, 2016)). A randomized algorithm M satisfies ρ-zCDP if, for every adjacent pair of datasets Z,Z ′ , and every α > 1, D α M(Z)∥M(Z ′ ) ≤ ρα.(4) 3 Fix a regularization parameter λ > 0, and a residual clipping threshold C clip > 0. Let ℓ C clip be the Huber loss, i.e., a square loss linearized to be C clip -Lipschitz: ℓ C clip (a) := ( a 2 /2,|a|≤ C clip , C clip |a|− C 2 clip /2, |a| > C clip . (5) Writing Z = (X,Y ), output perturbation first computes the regularized empirical-risk minimizer θ ∗ (Z) := arg min θ∈R d ( 1 n n X i=1 ℓ C clip x ⊤ i θ− y i + λ 2 ∥θ∥ 2 2 ) ,(6) and then releases ̃ θ = θ ∗ (Z) + b DP , b DP ∼N (0,σ 2 DP I d ).(7) Proposition 1. The output perturbation algorithm defined by (6)-(7) is ρ-zCDP provided σ 2 DP = 2R 2 C 2 clip λ 2 ρn 2 .(8) This result follows standard arguments on the Gaussian mechanism applied to minimization algorithms with bounded sensitivity (Mironov, 2017), and its proof is deferred to Appendix B. Intuitively, larger λ (or smaller C clip ) implies that the effect of a single training sample on the resulting θ ∗ (Z) is smaller. Then, to guarantee privacy, Gaussian noise is added proportionally to 1/ρ and R 2 = sup x ∥x∥ 2 2 . We will refer to C clip and λ as the hyper-parameters of output perturbation. Reconstruction threat model. We follow the same threat model as Balle et al. (2022). A trusted processor has a dataset Z = (X,Y ), decomposed into a target point z t = (x t ,y t ) and the rest of the dataset, Z − = (X − ,y − ). For convenience, we associate t ∈ [n] with an index in the data. The processor releases the output M(Z) ∈ Θ of a ρ-zCDP mechanism on the dataset. The attacker then develops a function A : Z n−1 × Θ → X to reconstruct the target feature x t ∈ X from M(Z) and all other datapoints Z − . We note that the attacker also has knowledge of the mechanism’s hyperparameters λ and C clip . The resulting reconstruction is bx :=A(Z − ,M(Z)). 4 Main results 4.1 Information-theoretic lower bound We first show a lower bound on the expected error an attacker must incur when reconstructing the target point, regardless of (X − ,y − ), the ρ-zCDP mechanism, or the reconstruction method. Theorem 1. Let the target feature x t be independent of the rest of the dataset Z − = (X − ,y − ). Let A : Z n−1 × Θ → X be an attack, taking as input Z − and the output M(Z − ∪z t ) of a ρ-zCDP mechanism, and producing as output an estimate bx of x t . Then, E∥x t − bx∥ 2 2 E∥x t ∥ 2 2 ≥ 1 2πe exp 2 d (h(x ′ t )− ρ) ,(9) with x ′ t := √ d √ E∥x t ∥ 2 2 x t . We note that the bound in (9) is scale-invariant, in the sense that neither the LHS or RHS depend on the norm of x t . Since the LHS of (9) is 1 for the all-0 estimator and 0 for ˆx = x t , we conclude that any attack fails whenever ρ is small compared to the differential entropy of the (normalized) point to be reconstructed. This dependence on h(x ′ t ) is natural: the differential entropy quantifies the prior uncertainty in the target, with normalization removing its dependency on the scale of the distribution, and ρ bounds the information that the mechanism can reveal. 4 0.00.51.01.52.0 ρ/d 0.00 0.25 0.50 0.75 1.00 Lower bound on D / ‖ x t ‖ 22 0.00.51.01.52.0 ρ/d Theorem 1Balle et al. (2022) (a) Gaussian (b) Uniform in ball radius √ d Figure 1: Lower bounds on the normalized mean squared error D/E∥x t ∥ 2 2 , with D = E∥x t − bx∥ 2 2 . We take d = 20 and let the distribution of x t be standard Gaussian (left) or uniform on the ball of radius √ d (right), following the setting of Propositions 6-7 of Balle et al. (2022). The guarantees of Balle et al. (2022) are translated into bounds on the mean squared error using the Gaussian Chernoff and uniform-ball volume bounds, see Appendix F for details. When h(x ′ t ) = Θ(d), Theorem 1 implies that, if ρ ≪ d, reconstructing x t accurately is information- theoretically impossible. This is the case e.g. for isotropic Gaussians, for the uniform distribution on a ball, and for distributions with independent entries, each with marginal entropy bounded away from 0. Moreover, while (9) bounds normalized mean squared error in terms of h(x ′ t ), similar bounds can be obtained for (i) the per-coordinate error E∥x t −bx∥ 2 2 /d in terms of h(x t ), and for (i) different norms/orders (e.g., E∥x t −bx∥ 2 ) whenever the max-entropy distribution under bounded distortion is computable. The proof of Theorem 1 is in Appendix C, with a sketch given below. Proof sketch. Let us consider normalized features E[∥x t ∥ 2 2 ] = d for simplicity, so that x ′ t = x t . The idea is to combine an upper bound on the mutual information coming from the privacy guarantee with a rate-distortion inequality. First, in Lemma 2, we show that I(z t ;M(Z − ∪z t )) ≤ ρ. This follows by taking the R ́enyi order α ↓ 1 in the zCDP condition and using convexity of the KL divergence to bound mutual information. As shown by Bun and Steinke (2016), an application of the data processing inequality, combined with the independence of x t and Z − , then implies I(x t ;bx)≤ ρ.(10) Writing D = E∥x t − bx∥ 2 2 and using that the Gaussian distribution maximizes the differential entropy when the second moment is constrained, in Lemma 3 we show that h(x t )− d 2 log 2πeD d ≤ I(x t ;bx).(11) Combining (10)-(11) yields the claimed lower bound. Comparison with prior bounds. Balle et al. (2022, Corollary 4) bound the probability of reconstruction within a radius r through the small-ball probability sup v P(∥x t − v∥ 2 ≤ r). In contrast, our bound is on the mean squared error and the distribution of x t enters through its differential entropy. We note that the examples of a uniform and Gaussian distribution in Propositions 6-7 of Balle et al. (2022) also show that ρ ≪ d guarantees the impossibility of reconstructing training data. However, Fig. 1 demonstrates that the bound of Theorem 1 is tighter for the Gaussian case and also for the uniform case unless ρ/d approaches 0. The improvement is particularly noticeable for moderate values of ρ/d, i.e., when a strong privacy guarantee is required. 5 4.2 Algorithmic upper bound We next design an attack on the linear model in (1) privatized via output perturbation (see (6)), and give provable guarantees on its reconstruction error. Assumption 1. Each feature datapoint x ∈ R d in X is independently and identically drawn from a O(1)- subGaussian distribution with bounded norm ∥x∥ 2 ≤ R for R = Θ( √ d). Furthermore, we assume ∥x t ∥ 2 = Θ( √ d) and ν i ∼N (0,ζ 2 ). In words, we require the data to have well-behaved tails, as commonly done in related work (Brown et al., 2024; Iurada et al., 2026). We also note that this assumption can be relaxed to requiring ∥X − ⊤ X − ∥ op = O(n + d). The normalization R = Θ( √ d) is chosen for convenience, and it corresponds to taking the entries of x of constant order. The Gaussian assumption on ν i is also chosen for simplicity, as it can be relaxed to requiring sufficient anti-concentration of the noise. Note that the derivative of the Huber loss is ψ C clip (a) := ℓ ′ C clip (a) = sign(a) min|a|,C clip . Given the non-target data, define the leave-one-out gradient F − (θ) := X i∈[n],i̸=t x i ψ C clip (x ⊤ i θ− y i ) + nλθ.(12) For λ > 0, the regularized objective in the RHS of (6) is strongly convex, and it has a unique minimizer θ ∗ . The first-order optimality condition thus gives −F − (θ ∗ ) = x t ψ C clip (x ⊤ t θ ∗ − y t ).(13) Then, given access to θ ∗ , through the knowledge of X − , y − , C clip and λ, one can compute F − (θ ∗ ). This quantity, assuming ψ C clip (x ⊤ t θ ∗ − y t ) ̸= 0, is an exact estimator of the direction of x t , due to (13). As the attacker has access to the perturbed weights ̃ θ (and not to θ ∗ ), it is natural to pick F − ( ̃ θ) to estimate the direction of x t . The performance of this reconstruction attack is characterized below. Theorem 2. Let Assumption 1 hold, and let λ > 0, C clip > 0 and ρ > 0 be the parameters of the algorithm chosen by the learner. The attacker computes bx := R F − ( ̃ θ) ∥F − ( ̃ θ)∥ 2 .(14) Let η ∈ (0, 1) be a failure probability and C,c > 0 be absolute constants. Then, with probability at least 1− η− 2e −cn − 2e −cd , min τ∈[−1,1] ∥x t − τbx∥ 2 2 ∥x t ∥ 2 2 ≤ C max 1, C clip ζη 1 + d nλ 1 + 1 λ 1 + d n 2 d ρ .(15) Theorem 2 states that, for large enough privacy parameter ρ, the estimate F − ( ̃ θ) is approximately aligned to the target x t . We note that the remaining sign and scale ambiguities may be easily resolvable in practice: the attacker has only two signs to consider (which would reconstruct the original image or its negative), and prior knowledge of the typical sample norm is a natural choice of scale. Formally, we remark that it is also possible to extend the lower bound in Theorem 1 to the metric considered here, without losing the dependence on the dimension. Consider now the case where η is a small constant (e.g., η = 0.01), the label noise is of constant order ζ = Θ(1) and the number of training samples satisfies n = Ω(d), often needed in linear regression to achieve non-trivial test loss (Wainwright, 2019; Mourtada, 2022). Then, the smallest ρ allowing successful reconstruction depends on the hyper-parameters C clip ,λ used by output perturbation. Fig. 2a shows that small clipping constants C clip = O(1) and a sufficiently large regularization λ = Θ(1) empirically yield good performance and, under this scaling, (15) reads min τ∈[−1,1] ∥x t − τbx∥ 2 2 ∥x t ∥ 2 2 ≲ d ρ .(16) 6 -3-2-10123 log 10 C clip -1 0 1 2 3 4 log 10 (1/ λ ) -3-2-10123 log 10 C clip -1012345 log 10 ρ 1 2 3 4 log 10 d 10 −3 10 0 10 3 ρ/d 0.0 0.5 1.0 0 1 2 3 4 Validation risk 0.0 0.5 1.0 Err d = 321003161000 (a) Hyperparameter search at ρ = 10 and ρ = 10 4 (b) Reconstruction error relative to ρ and d Figure 2: Hyper-parameter selection and reconstruction, for synthetic data sampled uniformly on the sphere. The first two panels show validation mean squared error (MSE) over a hyper-parameter grid at n = d = 1000, ζ = 0.5, for ρ = 10 and ρ = 10 4 . The third and fourth panel show normalized reconstruction error after hyper-parameter selection within the range λ≥ 0.1 and C clip ≤ 0.1ζ. This matches the scaling of the impossibility result of Theorem 1, and the sharp transition in data recon- struction at ρ≍ d is clearly displayed in Fig. 2b. We also remark that the findings in Fig. 2(a) on C clip are in analogy with the evidence that small gradient clipping constants yield good downstream performance in private gradient methods (Li et al., 2022; De et al., 2022; Bombari et al., 2026). The proof of Theorem 2 is in Appendix D, with a sketch given below. Proof sketch. The idea is to separate the signal carried by the target point from the perturbation induced by the privacy noise. Writing a = ψ C clip (x ⊤ t θ ∗ − y t ), the optimality condition (13) gives −F − ( ̃ θ) = ax t + w, w := F − (θ ∗ )− F − ( ̃ θ). First, to lower-bound |a|, we show that the target residual at θ ∗ is close to that at the leave-one-out estimator θ − defined in (31). Conditional on (x t ,Z − ), the latter residual is Gaussian with variance ζ 2 . Gaussian anti-concentration, combined with Lemma 5 , then yields |a|≳ min C clip , ζη 1 + R 2 /(nλ) with probability at least 1− η; see (36). Next, the same lemma controls the amplification of the privacy noise through F − . Combining concentration of the Gram matrix X − ⊤ X − and of the norm of the Gaussian noise gives, with high probability, ∥w∥ 2 ≲ σ DP √ d (nλ + n + d), as established in (38). Finally, Lemma 4 gives min τ∈[−1,1] ∥x t − τbx∥ 2 2 ≤ 4∥w∥ 2 2 /a 2 . Substituting σ DP from Proposition 1, using R 2 = O(d), and taking a union bound yields the final guarantee. 4.3 Extension to low-dimensional data The bounds above show that ρ ≍ d is a sharp threshold for reconstructing data in dimension d privatized via a ρ-zCDP mechanism: Theorem 1 implies that reconstruction is information-theoretically impossible for ρ ≪ d, and Theorem 2 exhibits a successful attack for ρ ≫ d. However, the impossibility result, and therefore the tightness of this threshold, relies on the entropy of x t to scale with the number of dimensions, i.e., h(x t ) ≍ d, which may not be the case for data in practical applications. To model that, we now focus on data lying in a lower dimensional subspace of R d . More precisely, let P be a fixed orthogonal projection of rank s < d, and let U ∈ R d×s have orthonormal columns spanning Im(P ), so that P = U ⊤ . Define h s (x t ) := h(U ⊤ x t ), 7 where h is taken with respect to the Lebesgue measure on R s . Note that this definition does not depend on the specific choice of orthonormal basis, and its purpose is to avoid computing the differential entropy of Px t in the original ambient space R d , where its distribution would be singular. The result below (proved in Appendix E) extends the lower bound of Theorem 1. Theorem 3. In the same setting as Theorem 1, for any rank-s projection P satisfying the conditions above, any reconstruction of x t from a ρ-zCDP mechanism obeys: E∥x t − bx∥ 2 2 E∥Px t ∥ 2 2 ≥ 1 2πe exp 2 s (h s (x ′ s )− ρ) ,(17) with x ′ s := √ s √ E∥Px t ∥ 2 2 Px t . We note that the lower bound in (17) is analogous to that in (9) upon replacing (i) E∥x t ∥ 2 2 with E∥Px t ∥ 2 2 in the denominator of the LHS, and (i) h(x ′ t ) with h s (x ′ s ) on the RHS. Thus, if the point to be reconstructed x t lies close to the span of Im(P ) (i.e., E∥x t ∥ 2 2 ≈ E∥Px t ∥ 2 2 ), then any attack fails whenever ρ is small compared to the differential entropy h s (x ′ s ) computed on that span. Furthermore, as this span has dimension s, we would typically have h s (x ′ s ) = Θ(s), implying the impossibility of data reconstruction whenever ρ≪ s. To complement this lower bound, the result below (also proved in Appendix E) characterizes the perfor- mance of a variant of the attack in Theorem 2 that seeks to reconstruct an s-dimensional projection of the target. Theorem 4. Consider the same setting as Theorem 2, but with R = Θ( √ s) and ∥x t ∥ 2 = Θ( √ s) replacing the corresponding Θ( √ d) assumptions. Let P ∈ R d×d be a rank-s projector, known to the attacker, such that x i ∈ Im(P ) for all i∈ [n]. Let ˆx P := R PF − ( ̃ θ) ∥PF − ( ̃ θ)∥ 2 .(18) Then, if n = Ω(s),λ = Ω(1),C clip = O(ζ), we have min τ∈[−1,1] ∥x t − τ ˆx P ∥ 2 2 ∥x t ∥ 2 2 ≲ s ρ ,(19) with probability at least 0.99. While the result of Theorem 3 is scale-invariant, Theorem 4 considers R and∥x t ∥ 2 of order √ s. 2 Modulo this scale difference, the upper bound in (19) is analogous to that in (16) upon replacing (i) the estimator bx with its projected version ˆx P , and (i) the dimension d of the ambient space with the dimension s of the subspace containing the data. In words, Theorem 4 shows that an attack having knowledge of the subspace of dimension s in which the data lies, is successful whenever ρ ≫ s and, combined with Theorem 3, this establishes ρ≍ s as a sharp threshold for data reconstruction. 5 Experiments We study the attacks of Sections 4.2-4.3 for data sampled uniformly on the d-dimensional sphere, synthetic data concentrated near an s-dimensional subspace, and binary regression on data taken from ImageNet (elephants vs. pandas) and CIFAR-10 (frog vs. trucks). Details on datasets construction, learning algorithm, and attacks are given in Appendix G. We report the squared reconstruction error (see e.g. the LHS of (19)), with the sign ambiguity resolved. 2 If one wishes to keep those quantities of order √ d, we note that the same result would hold upon taking λ of order d/s and assuming that, for any feature x∈ R d , p s/dx is O(1)-subGaussian. 8 012345 log 10 (ρ) 12 48 192 768 3072 12288 d 0.0 0.5 1.0 reconstruction error (a) ImageNet reconstruction heatmap 10 −3 10 −2 10 −1 10 0 10 1 10 2 10 3 10 4 ρ/d 0.0 0.5 1.0 Reconstruction error d= 12 48 192768 (b) ImageNet, ρ/d Figure 3: Reconstruction of ImageNet data (ele- phants vs. pandas).Hyperparameter search for mean validation MSE within λ ≥ 0.1 and C clip ≤ 0.01. The panels show squared relative error against (ρ,d) and against ρ/d. Target ρ / d = 1 1.000.980.781.00 ρ / d = 10 0.990.910.750.97 ρ / d = 100 0.670.560.670.64 ρ / d = 1000 0.140.120.450.13 Figure 4: Reconstructions of four target images from ImageNet (elephants vs. pandas) as the privacy bud- get grows, with λ = 1 and C clip = 0.125. The num- ber inside each reconstruction is its reconstruction error. Here, d = 12,288 (64× 64 RGB images). Ad- ditional plots appear in Figs. 7 and 8. Synthetic d-dimensional data. In Fig. 2a, we investigate how different choices of C clip and λ affect the performance of the output perturbation algorithm in (7). The heatmaps show that, for both values of ρ, the best performance is achieved for (i) sufficiently small values of C clip , and (i) an appropriate ratio C clip /λ. In fact, the lowest validation risk occurs on a top-left to bottom-right diagonal of the heatmap. Then, for any output perturbation algorithm, we take the values of λ≥ 0.1 and C clip ≤ 0.1ζ that minimize the validation risk. In the left panel of Fig. 2b, we plot the reconstruction error as a function of ρ and d, and identify a clear diagonal boundary ρ/d≍ 1 between successful and unsuccessful attacks, validating our result in (16). In the right panel of Fig. 2b, we plot the same reconstruction error as a function of ρ/d, and show that curves corresponding to different values of d (in different colors) collapse onto each other under this scaling. Natural images. In Fig. 3, we consider ImageNet data, and perform the same experiments as those described in Fig. 2 for synthetic data. Here, we tune the value of d by down-scaling images to a lower resolution, and we optimize the output perturbation algorithm across the hyper-parameters ranges λ ≥ 0.1 and C clip ≤ 0.01. In Fig. 3a, we plot the reconstruction error as a function of ρ and d, and identify the same clear diagonal boundary as in Fig. 2 for the attack success across different image resolutions. In Fig. 3b, we then plot the same reconstruction error as a function ρ/d, noting that curves corresponding to different values of d collapse onto each other. This provides evidence that our proposed threshold ρ ≍ d for data reconstruction persists in natural images as well. Furthermore, in Fig. 4 we give a visual presentation of some target images (first row) and the corresponding reconstructions for increasing values of ρ/d. Additional visual reconstructions appear in Figs. 7 and 8 (Appendix G.4). Low-dimensional data. In Fig. 5, we numerically investigate the conclusions of Theorems 3 and 4. More precisely, in Figure 5a, we fix the ambient dimension at d = 1000, and generate synthetic data concentrated near an s-dimensional subspace. The construction is detailed in Appendix G.1. We test the reconstruction 9 10 −2 10 0 10 2 ρ/s 0.0 0.5 1.0 Reconstruction error 10 1 10 2 10 3 10 4 ρ s= 10 full 22 46 100215464 10 −2 10 0 10 2 ρ/s 0.0 0.5 1.0 Reconstruction error 10 1 10 2 10 3 10 4 ρ s= 10 464 22 1000 46 100 215 (a) Synthetic rank-s data(b) CIFAR-10 (frog vs. truck) Figure 5: Reconstruction error for projected attacks on (a) synthetic rank-s data with d = 1000, and (b) CIFAR-10 (frog vs. truck) data with d = 3,072 (32× 32 RGB images). Each pair of plots uses ρ/s (left) and ρ (right) on the x-axis, and different colors for different values of the rank s. attack in (18), estimating the rank-s PCA projector P from X − , and report its performance as a function of ρ/s (left panel) and ρ (right panel). The reconstruction error curves with respect to ρ/s overlap for different values of s, showing a transition at the level of ρ ≍ s. In contrast, the curves are clearly separated when plotted against ρ. This validates our bound in (19), and it shows that the same privacy budget ρ can result in different guarantees in terms of data reconstruction, depending on the effective dimension of the data. Next, in Fig. 5b, we consider a similar class of experiments, training our DP linear regression model on CIFAR-10 data. We perform the reconstruction attack in (18), defining P as the projector over the s principal components of the data distribution, estimated from X − . We again plot the reconstruction error both in terms of ρ/s (left panel) and ρ (right panel). As for the synthetic data, the curves are separated when plotted against ρ, and they collapse onto each other when plotted against ρ/s. However, differently from the synthetic data, when s is too small (e.g., s = 10), the error exhibits a plateau even at large ρ/s, capturing the fact that low-rank subspaces do not capture all of the signal of the target. Similar results for ImageNet are reported in Fig. 6 (Appendix G.3). 6 Conclusions In this work, we study how differential privacy quantitatively determines the feasibility of successful recon- struction attacks. First, in Theorem 1, we prove that any ρ-zCDP mechanism prevents data reconstruction as long as the privacy budget is sufficiently smaller than the entropy of the target, i.e., ρ ≪ h(x t ). When h(x t ) = Θ(d) (which holds, e.g., for distributions with independent entries), this provides the sufficient con- dition ρ≪ d to protect from reconstruction attacks. Then, in Theorem 2, we show that this condition is also necessary: there exists an attack on a linear model trained with output perturbation that achieves arbitrary accuracy as ρ≫ d. Taken together, these results identify ρ≍ d as a sharp transition in data reconstruction. We next show that this threshold shifts according to the effective dimension of the data: when the data lies on an s-dimensional subspace known to the attacker, the transition moves to ρ ≍ s (Theorems 3 and 4). This highlights the role of the data prior in assessing the effective guarantees given by a privacy budget. A first natural research direction for future work is to extend Theorem 2 to other algorithms (e.g., DP gradient descent or objective perturbation) and beyond the linear model assumption, as well as expand our results on low-dimensional data to non-linear subspaces. A second exciting avenue is to consider less powerful attackers, without knowledge of all remaining training data. Information-theoretic lower bounds in that setting would complement the recent work by Swanberg et al. (2026) on adversary-aware privacy guarantees. We suspect that matching those bounds with attacks would require a different learning model: when multiple training examples are unknown, the optimality conditions of a linear model generally leave their individual values under-determined (Runkel et al., 2025). Thus, the success of the attack will likely depend on the capacity of the learning model, in agreement with the results of Iurada et al. (2026) in the context of non-private learning. 10 Acknowledgements This research was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/COE12. For the purpose of open access, the authors have applied a C BY public copyright license to any Author Accepted Manuscript version arising from this submission. Simone Bombari was supported by a Google PhD fellowship. The authors would like to thank Edwige Cyffers for helpful discussions. This research was supported by the Scientific Service Units (SSU) of the Institute of Science and Tech- nology Austria through resources provided by Scientific Computing (SciComp). References Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In ACM SIGSAC Conference on Computer and Communications Security (CCS), 2016. Michael Aerni, Jie Zhang, and Florian Tram`er. Evaluations of machine learning privacy defenses are mis- leading. In ACM SIGSAC Conference on Computer and Communications Security (CCS), 2024. Borja Balle, Giovanni Cherubin, and Jamie Hayes. Reconstructing Training Data with Informed Adversaries. In IEEE Symposium on Security and Privacy (SP), May 2022. doi: 10.1109/SP46214.2022.9833677. Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers. Protection against reconstruction and its applications in private federated learning. arXiv:1812.00984, 2019. Simone Bombari and Marco Mondelli. Privacy for free in the overparameterized regime. Proceedings of the National Academy of Sciences, 2025. Simone Bombari, Jialei Luo, Inbar Seroussi, and Marco Mondelli. High-dimensional private linear regression with optimal rates. arXiv:2505.16329, 2026. Gavin R Brown, Krishnamurthy Dj Dvijotham, Georgina Evans, Daogao Liu, Adam Smith, and Abhradeep Guha Thakurta. Private gradient descent for linear regression: Tighter error bounds and instance-specific uncertainty estimation. In International Conference on Machine Learning (ICML), 2024. Mark Bun and Thomas Steinke. Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. In Theory of Cryptography, Lecture Notes in Computer Science. Springer, 2016. doi: 10.1007/ 978-3-662-53641-4 24. Gon Buzaglo, Niv Haim, Gilad Yehudai, Gal Vardi, Yakir Oz, Yaniv Nikankin, and Michal Irani. De- constructing data reconstruction: Multiclass, weight decay and general losses. In Conference on Neural Information Processing Systems (NeurIPS), 2023. Nicholas Carlini, Florian Tram`er, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, ́ Ulfar Erlingsson, Alina Oprea, and Colin Raffel. Extracting training data from large language models. In USENIX Security Symposium, 2021. Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tram`er. Membership inference attacks from first principles. In IEEE Symposium on Security and Privacy (SP), 2022. Nicholas Carlini, Jamie Hayes, Milad Nasr, Matthew Jagielski, Vikash Sehwag, Florian Tram`er, Borja Balle, Daphne Ippolito, and Eric Wallace. Extracting training data from diffusion models. In USENIX Security Symposium, 2023. A Feder Cooper, Mark A Lemley, Allison Casasola, Ahmed Ahmed, Aaron Gokaslan, Amy B Cyphert, Christopher De Sa, Daniel E Ho, and Percy Liang. Extracting memorized pieces of (copyrighted) books from open-weight language models. In Conference on Language Modeling, 2026. 11 Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley-Interscience, 2001. Edwige Cyffers. Setting ε is not the issue in differential privacy. In Conference on Neural Information Processing Systems (NeurIPS), 2025. Soham De, Leonard Berrada, Jamie Hayes, Samuel L. Smith, and Borja Balle. Unlocking high-accuracy differentially private image classification through scale. arXiv:2204.13650, 2022. Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 2022. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 2014. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In Theory of Cryptography, Lecture Notes in Computer Science, Berlin, Heidelberg, 2006. Springer. Chuan Guo, Brian Karrer, Kamalika Chaudhuri, and Laurens van der Maaten. Bounding Training Data Reconstruction in Private (Deep) Learning. In International Conference on Machine Learning (ICML), 2022. Chuan Guo, Alexandre Sablayrolles, and Maziar Sanjabi. Analyzing privacy leakage in machine learning via multiple hypothesis testing: A lesson from Fano. In International Conference on Machine Learning (ICML), 2023. Niv Haim, Gal Vardi, Gilad Yehudai, Ohad Shamir, and Michal Irani. Reconstructing Training Data from Trained Neural Networks. In Conference on Neural Information Processing Systems (NeurIPS), 2022. Jamie Hayes, Saeed Mahloujifar, and Borja Balle. Bounding training data reconstruction in DP-SGD. In Conference on Neural Information Processing Systems (NeurIPS), 2023. Leonardo Iurada, Simone Bombari, Tatiana Tommasi, and Marco Mondelli. A law of data reconstruction for random features (and beyond). In International Conference on Learning Representations (ICLR), 2026. Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing differentially private machine learning: How private is private SGD? In Conference on Neural Information Processing Systems (NeurIPS), 2020. Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. In Conference on Neural Information Processing Systems (NeurIPS), 2020. Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International Conference on Machine Learning (ICML), 2015. Georgios Kaissis, Jamie Hayes, Alexander Ziller, and Daniel Rueckert. Bounding data reconstruction attacks with the hypothesis testing interpretation of differential privacy. arXiv:2307.03928, 2023. Kousha Kalantari, Lalitha Sankar, and Anand D. Sarwate. Robust Privacy-Utility Tradeoffs Under Dif- ferential Privacy and Hamming Distortion. IEEE Transactions on Information Forensics and Security, 2018. Antti Koskela and Tejas Kulkarni. Practical differentially private hyperparameter tuning with subsampling. In Conference on Neural Information Processing Systems (NeurIPS), 2023. Bogdan Kulynych, Juan Felipe Gomez, Georgios Kaissis, Jamie Hayes, Borja Balle, Flavio P. Calmon, and Jean Louis Raisaro. Unifying Re-Identification, Attribute Inference, and Data Reconstruction Risks in Differential Privacy. In Conference on Neural Information Processing Systems (NeurIPS), 2025. Xuechen Li, Florian Tram`er, Percy Liang, and Tatsunori Hashimoto. Large language models can be strong differentially private learners. In International Conference on Learning Representations (ICLR), 2022. 12 Sheng Liu, Zihan Wang, Yuxiao Chen, and Qi Lei. Data Reconstruction Attacks and Defenses: A Systematic Evaluation. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2025. Noel Loo, Ramin Hasani, Mathias Lechner, Alexander Amini, and Daniela Rus. Understanding recon- struction attacks with the neural tangent kernel and dataset distillation. In International Conference on Learning Representations (ICLR), 2024. Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations (ICLR), 2020. Saeed Mahloujifar, Alexandre Sablayrolles, Graham Cormode, and Somesh Jha. Optimal membership infer- ence bounds for adaptive composition of sampled Gaussian mechanisms. arXiv:2204.06106, 2022. Ryan McKenna, Yangsibo Huang, Amer Sinha, Borja Balle, Zachary Charles, Christopher A. Choquette- Choo, Badih Ghazi, Georgios Kaissis, Ravi Kumar, Ruibo Liu, Da Yu, and Chiyuan Zhang. Scaling laws for differentially private language models. In International Conference on Machine Learning (ICML), 2025. Ilya Mironov. Renyi Differential Privacy. In IEEE Computer Security Foundations Symposium (CSF), 2017. Jaouad Mourtada. Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices. The Annals of Statistics, 2022. Milad Nasr, Reza Shokri, and Amir Houmansadr. Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning. In IEEE Symposium on Security and Privacy (SP), 2019. Milad Nasr, Jamie Hayes, Thomas Steinke, Borja Balle, Florian Tram`er, Matthew Jagielski, Nicholas Car- lini, and Andreas Terzis. Tight auditing of differentially private machine learning. In USENIX Security Symposium, 2023. Milad Nasr, Javier Rando, Nicholas Carlini, Jonathan Hayase, Matthew Jagielski, A. Feder Cooper, Daphne Ippolito, Christopher A. Choquette-Choo, Florian Tram`er, and Katherine Lee. Scalable extraction of training data from aligned, production language models. In International Conference on Learning Repre- sentations (ICLR), 2025. 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:2407.15845, 2024. Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with renyi differential privacy. In Interna- tional Conference on Learning Representations (ICLR), 2022. Christina Runkel, Kanchana Vaishnavi Gandikota, Jonas Geiping, Carola-Bibiane Sch ̈onlieb, and Michael Moeller. Training data reconstruction: Privacy due to uncertainty? In Computer Vision and Pattern Recognition (CVPR) Workshops, 2025. Anand D. Sarwate and Lalitha Sankar. A rate-distortion perspective on local differential privacy. In Allerton Conference on Communication, Control, and Computing (Allerton), 2014. Yujie Shen, Zihan Wang, Jian Qian, and Qi Lei. Data Reconstruction: Identifiability and Optimization with Sample Splitting. In International Conference on Machine Learning (ICML), 2026. Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In IEEE Symposium on Security and Privacy (SP), 2017. Thomas Steinke, Milad Nasr, and Matthew Jagielski. Privacy auditing with one (1) training run. In Conference on Neural Information Processing Systems (NeurIPS), 2023. Pierre Stock, Igor Shilov, Ilya Mironov, and Alexandre Sablayrolles. Defending against reconstruction attacks with r ́enyi differential privacy. arXiv:2202.07623, 2022. 13 Marika Swanberg, Meenatchi Sundaram Muthu Selva Annamalai, Jamie Hayes, Borja Balle, and Adam Smith. A unified framework for adversary-aware differential privacy bounds. arXiv:2507.08158, 2026. Tim van Erven and Peter Harremo ̈es. R ́enyi Divergence and Kullback-Leibler Divergence. IEEE Transactions on Information Theory, 2014. Roman Vershynin. Introduction to the Non-Asymptotic Analysis of Random Matrices. Cambridge University Press, 2012. Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cam- bridge University Press, 2018. Martin J Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 2019. Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learning: Ana- lyzing the connection to overfitting. In IEEE Computer Security Foundations Symposium (CSF), 2018. Alexander Ziller, Tamara T. Mueller, Simon Stieger, Leonhard F. Feiner, Johannes Brandt, Rickmer Braren, Daniel Rueckert, and Georgios Kaissis. Reconciling privacy and accuracy in AI for medical imaging. Nature Machine Intelligence, 2024. A Additional notation Given a symmetric matrix A, we denote with tr(A) its trace, and by s min (A) (s max (A)) its smallest (largest) singular value. Given a symmetric matrix A, we denote by λ min (A) (λ max (A)) its smallest (largest) eigen- value. For square, symmetric matrices A,B, we write A⪯ B if B−A is positive semi-definite (p.s.d.), where A is p.s.d. if x ⊤ Ax≥ 0 for all x∈ R n . We use the notation [b] + = maxb, 0 for b∈ R. B Sensitivity and privacy of output perturbation Lemma 1 (Sensitivity of (6)). Fix λ,R,C clip > 0. Let Z,Z ′ be adjacent datasets of size n, with every feature vector in either dataset having norm at most R. Then, the minimizer in (6) satisfies ∥θ ∗ (Z)− θ ∗ (Z ′ )∥ 2 ≤ 2RC clip λn .(20) Proof. Without loss of generality, let Z and Z ′ differ in their first example, and write θ := θ ∗ (Z), θ ′ := θ ∗ (Z ′ ), r := θ− θ ′ . Define g i (θ) := x i ℓ ′ C clip (x ⊤ i θ− y i ), g ′ 1 (θ) := x ′ 1 ℓ ′ C clip ((x ′ 1 ) ⊤ θ− y ′ 1 ). The first-order optimality conditions for the two strongly convex objectives are 0 = 1 n g 1 (θ) + n X i=2 g i (θ) ! + λθ,0 = 1 n g ′ 1 (θ ′ ) + n X i=2 g i (θ ′ ) ! + λθ ′ . Subtracting these equations and taking the inner product with r gives λ∥r∥ 2 2 = − 1 n r ⊤ n X i=2 g i (θ)− g i (θ ′ ) ! − 1 n r ⊤ (g 1 (θ)− g ′ 1 (θ ′ )).(21) 14 The first term on the RHS is non-positive. In fact, P n i=2 ℓ C clip (x ⊤ i θ− y i ) is convex in θ, so its gradient is monotone, i.e., r ⊤ n X i=2 g i (θ)− g i (θ ′ ) ! ≥ 0. Since |ℓ ′ C clip (·)|≤ C clip and ∥x i ∥ 2 ≤ R, every per-example gradient satisfies ∥g i (θ)∥ 2 ≤ RC clip . Then, plugging this result into (21), Cauchy-Schwarz and the triangle inequality yield λ∥r∥ 2 2 ≤ ∥r∥ 2 n (∥g 1 (θ)∥ 2 +∥g ′ 1 (θ ′ )∥ 2 ) ≤ 2RC clip n ∥r∥ 2 . If r = 0, the claim is immediate. Otherwise, dividing by λ∥r∥ 2 proves ∥r∥ 2 =∥θ ∗ (Z)− θ ∗ (Z ′ )∥ 2 ≤ 2RC clip λn , which gives the desired result. Proposition 1. The output perturbation algorithm defined by (6)-(7) is ρ-zCDP provided σ 2 DP = 2R 2 C 2 clip λ 2 ρn 2 .(8) Proof. By Lemma 1, for adjacent Z,Z ′ , ∥θ ∗ (Z)− θ ∗ (Z ′ )∥ 2 ≤ ∆ 2 := 2RC clip λn . For every α > 1, the R ́enyi divergence between Gaussians with means μ,μ ′ and common covariance σ 2 DP I d is given by (see (Mironov, 2017, Proposition 7)) D α N (μ,σ 2 DP I d ) N (μ ′ ,σ 2 DP I d ) = α∥μ− μ ′ ∥ 2 2 2σ 2 DP . Taking μ = θ ∗ (Z) and μ ′ = θ ∗ (Z ′ ), the stated lower bound on σ 2 DP gives D α ̃ θ(Z)∥ ̃ θ(Z ′ ) ≤ α∆ 2 2 2σ 2 DP ≤ ρα. The claim follows from Definition 1. Note, of course, that larger variances than the value stated also satisfy ρ-zCDP given the same hyperpa- rameters, but lead to greater-than-necessary utility loss; we therefore assume the learner chooses the smallest variance to satisfy their desired privacy bound. C Proof of the information-theoretic lower bound We start with a lemma using arguments from Bun and Steinke (2016). Lemma 2 (Mutual information bound from ρ-zCDP). Suppose M is a ρ-zCDP mechanism, applied to a dataset Z = Z − ∪z t , where z t is a random variable and Z − is fixed. Then, we have I(z t ;M(Z − ∪z t ))≤ ρ,(22) where I(·;·) denotes the mutual information in the probability space of z t and of the private mechanism. 15 Proof. As M is ρ-zCDP, due to Definition 1, we have that D α (M(Z)∥M(Z ′ ))≤ ρ· α, for all α > 1 and all neighboring datasets Z,Z ′ where Z = Z − ∪z, Z ′ = Z − ∪z ′ , for arbitrary z,z ′ ∈Z. By continuity of the R ́enyi divergence as α → 1 (on α ∈ [0,∞] when D α (P∥Q) < ∞) (van Erven and Harremo ̈es, 2014, Theorem 7), the above condition gives D KL (M(Z)∥M(Z ′ )) = D 1 (M(Z)∥M(Z ′ ))≤ ρ.(23) For shorthand, we introduce the notation ̃ θ = M(Z − ∪z t ), θ for a value taken by ̃ θ, and z for a value taken by z t . Then, we have I(z t ; ̃ θ) = Z p z t (z)p ̃ θ|z t (θ|z) log p ̃ θ|z t (θ|z) p ̃ θ (θ) dz dθ = Z p z t (z) Z p ̃ θ|z t (θ|z) log p ̃ θ|z t (θ|z) p ̃ θ (θ) dθ ! dz = Z p z t (z)D KL (( ̃ θ | z t = z)∥ ̃ θ) dz = Z p z t (z)D KL (( ̃ θ | z t = z)∥ E z t [ ̃ θ | z t ]) dz ≤ Z p z t (z)p z t (z ′ ) Z p ̃ θ|z t (θ|z) log p ̃ θ|z t (θ|z) p ̃ θ|z t (θ|z ′ ) dθ ! dz ′ dz = Z p z t (z)p z t (z ′ )D KL (M(Z)∥M(Z ′ )) dz ′ dz ≤ Z p z t (z)p z t (z ′ )ρ dz ′ dz, = ρ, where the fifth line holds as the KL divergence is convex in its second argument (van Erven and Harremo ̈es, 2014, Theorem 12) and the seventh line follows from (23). We can now turn to a brief discussion on rate-distortion and distortion-rate functions, before we develop a theorem combining this with the mutual information bound. For more details, we refer the interested reader to the classical textbook (Cover and Thomas, 2001). Let S be a random variable in R k , for an arbitrary dimension k ≥ 1, and consider a (possibly random) function C : R k → R k which we will refer to as channel. We define its rate and distortion by R(C) := I(S;C(S)), D(C) := E ∥S−C(S)∥ 2 2 . Then, we define the rate-distortion and distortion-rate functions as r(D) :=inf C:D(C)≤D R(C),d(R) :=inf C:R(C)≤R D(C).(24) We will use this notation in the remaining part of the section. Lemma 3 (Rate/distortion bounds for the squared ℓ 2 distortion). Let D > 0 andR ≥ 0. Then, the rate-distortion and distortion-rate functions defined in (24) satisfy r(D)≥ h(S)− k 2 log 2πe D k + ,(25) d(R)≥ k 2πe exp 2 k (h(S)−R) .(26) 16 Proof. We have r(D) =inf C:E∥C(S)−S∥ 2 2 ≤D I(S;C(S)) = h(S)−sup C:E∥C(S)−S∥ 2 2 ≤D h(S|C(S)) = h(S)−sup C:E∥C(S)−S∥ 2 2 ≤D h(S−C(S)|C(S)) ≥ h(S)−sup C:E∥C(S)−S∥ 2 2 ≤D h(S−C(S)) = h(S)−sup ∆:E∥∆∥ 2 2 ≤D h(∆) = h(S)− k 2 log 2πe D k . Here, the second line uses I(S;C(S)) = h(S)−h(S|C(S)); the third line uses that the conditional differential entropy is translation-invariant; the fourth line uses that conditioning decreases entropy; in the fifth line we take ∆ = S −C(S) and use that the space of all random variables ∆ with ∥∆∥ 2 2 ≤ D is equivalent to S−C(S) : E∥C(S)− S∥ 2 2 ≤ D; the sixth line uses that, under this distortion condition, the max-entropy distribution is Gaussian (Cover and Thomas, 2001, Theorem 9.6.5). Combining this with r(D)≥ 0 gives the first bound. For any channel with R(C)≤R, we have h(S)− k 2 log 2πe D(C) k ≤ r(D(C))≤R(C)≤R. Rearranging and taking the infimum over such channels gives d(R)≥ k 2πe exp 2 k (h(S)−R) . Theorem 1. Let the target feature x t be independent of the rest of the dataset Z − = (X − ,y − ). Let A : Z n−1 × Θ → X be an attack, taking as input Z − and the output M(Z − ∪z t ) of a ρ-zCDP mechanism, and producing as output an estimate bx of x t . Then, E∥x t − bx∥ 2 2 E∥x t ∥ 2 2 ≥ 1 2πe exp 2 d (h(x ′ t )− ρ) ,(9) with x ′ t := √ d √ E∥x t ∥ 2 2 x t . Note that we assume that the differential entropy is well-defined, i.e. that x t has a density with respect to the Lebesgue measure on R d , has finite differential entropy, and 0 < E∥x t ∥ 2 2 <∞. Proof. Fix Z − and write z t = (x t ,y t ). Consider the shorthand θ(z) =M(Z − ∪z). The target pair z t , the resulting learned weights θ(z t ), and the reconstruction bx =A(Z − ,θ(z t )) form a Markov chain z t → θ(z t )→ bx. Since x t is the feature component of z t , we have I(x t ;bx)≤ I(z t ;bx)≤ I(z t ;θ(z t ))≤ ρ, where the first two steps follow from the data-processing inequality, and the last step holds due to Lemma 2, since M is ρ-zCDP. All information quantities here are evaluated conditional on the fixed Z − . Now, define the induced channel C(x t ) = bx, averaging over the conditional distribution of y t and the randomness of the mechanism and attack. We apply the rate-distortion definitions to the feature variable 17 x t , taking S = x t and k = d in Lemma 3. Since R(C) = I(x t ;bx) ≤ ρ, using the definition of distortion-rate function d in (24) and Lemma 3, we have E∥x t − bx∥ 2 2 =D(C)≥ d(ρ)≥ d 2πe exp 2 d (h(x t )− ρ) . Finally, to remove the effect of the scale of x t , we apply the fact that h(AX) = h(X) + log| det(A)| (Cover and Thomas, 2001, Theorem 9.6.4) with x ′ t = q d E∥x t ∥ 2 2 x t , and divide by E∥x t ∥ 2 2 to obtain (9). D Proof of the algorithmic upper bound Lemma 4. Let x t ∈ R d , and let q ∈ R d be such that q = ax t + w ̸= 0, for some real number a ̸= 0, and some w ∈ R d . Defining bx =∥x t ∥ 2 q ∥q∥ 2 , we have min τ∈[−1,1] ∥x t − τbx∥ 2 2 ≤ 4∥w∥ 2 2 a 2 . Proof. If x t = 0, choose τ = 0. Otherwise, set R t =∥x t ∥ 2 > 0 and choose τ = sign(a)∈ [−1, 1]. Then 1 R t ∥x t − τbx∥ 2 = q ∥q∥ 2 − ax t ∥ax t ∥ 2 2 ≤ q ∥q∥ 2 − q ∥ax t ∥ 2 2 + q− ax t ∥ax t ∥ 2 2 = ∥ax t ∥ 2 −∥q∥ 2 ∥ax t ∥ 2 + ∥w∥ 2 ∥ax t ∥ 2 ≤ 2∥w∥ 2 |a|R t . The last inequality follows from the reverse triangle inequality and q = ax t +w. Multiplying by R t , squaring, and minimizing over τ ∈ [−1, 1] gives the desired result. Lemma 5 (A property of F − ). Let F − be defined as in (12). Then, for any θ 1 ,θ 2 ∈ R d , we have F − (θ 1 )− F − (θ 2 ) = M (θ 1 − θ 2 ),(27) for some positive semi definite matrix M that satisfies nλI ⪯ M ⪯ X − ⊤ X − + nλI.(28) Proof. Define a diagonal matrix D ∈ R (n−1)×(n−1) with entries D i := ψ C clip (x ⊤ i θ 1 − y i )− ψ C clip (x ⊤ i θ 2 − y i ) x ⊤ i (θ 1 − θ 2 ) , if x ⊤ i (θ 1 − θ 2 )̸= 0, 0,otherwise, where we consider non-target points X − =x i i∈[n−1] . Then, (12) yields F − (θ 1 )− F − (θ 2 ) = X i∈[n−1] x i D i x ⊤ i (θ 1 − θ 2 ) + λn(θ 1 − θ 2 ) = M (θ 1 − θ 2 ), with M = X − ⊤ DX − + nλI.(29) Since the gradient of the clipped loss function ψ C clip is non-decreasing and 1-Lipschitz, we have 0≤ D i ≤ 1, which implies that X − ⊤ DX − is p.s.d. and such that X − ⊤ DX − ⪯ X − ⊤ X − . 18 Theorem 2. Let Assumption 1 hold, and let λ > 0, C clip > 0 and ρ > 0 be the parameters of the algorithm chosen by the learner. The attacker computes bx := R F − ( ̃ θ) ∥F − ( ̃ θ)∥ 2 .(14) Let η ∈ (0, 1) be a failure probability and C,c > 0 be absolute constants. Then, with probability at least 1− η− 2e −cn − 2e −cd , min τ∈[−1,1] ∥x t − τbx∥ 2 2 ∥x t ∥ 2 2 ≤ C max 1, C clip ζη 1 + d nλ 1 + 1 λ 1 + d n 2 d ρ .(15) Proof. Consider the shorthand for the residuals r t (θ) := x ⊤ t θ− y t . As noted in (13), we have that −F − (θ ∗ ) = x t ψ C clip (x ⊤ t θ ∗ − y t ). On the perturbed noisy weights ̃ θ, we have −F − ( ̃ θ) = x t ψ C clip (r t (θ ∗ ))− (F − ( ̃ θ)− F − (θ ∗ )).(30) Firstly, we lower bound the absolute value of ψ C clip (r t (θ ∗ )). A useful tool is the optimal solution to the same learning problem on all datapoints except the target, i.e., just on X − , with a slightly altered regularization parameter n n−1 λ: θ − := arg min θ∈R d 1 n− 1 X i∈[n],i̸=t ℓ C clip (x ⊤ i θ− y i ) + 1 2 nλ (n− 1) ∥θ∥ 2 2 .(31) This objective is strongly convex, so its minimizer is unique, and its gradient is F − /(n−1). Hence F − (θ − ) = 0. Due to Lemma 5, we have θ ∗ − θ − = M −1 (F − (θ ∗ )− F − (θ − )) = M −1 F − (θ ∗ ), where the second step holds as F − (θ − ) = 0. Note that M ∈ R d×d is a p.s.d. matrix such that M −1 op ≤ (nλ) −1 . Then, we have r t (θ ∗ ) = x ⊤ t θ ∗ − y t (32) = x ⊤ t (θ ∗ − θ − ) + x ⊤ t θ − − y t | z :=r t (θ − ) (33) = x ⊤ t M −1 F − (θ ∗ ) + r t (θ − )(34) =−x ⊤ t M −1 x t ψ C clip (r t (θ ∗ )) + r t (θ − ).(35) Since r t (θ ∗ ) and ψ C clip (r t (θ ∗ )) have the same sign, and 0≤ x ⊤ t M −1 x t ≤ R 2 nλ , we have |r t (θ − )| =|r t (θ ∗ )| + x ⊤ t M −1 x t |ψ C clip (r t (θ ∗ ))|≤ 1 + R 2 nλ |r t (θ ∗ )|. Thus, for any u≥ 0, we have P(|r t (θ ∗ )|≤ u)≤ P |r t (θ − )|≤ 1 + R 2 nλ u . The residual r t (θ − ) decomposes as r t (θ − ) = x ⊤ t (θ − − θ true )− ν t . Conditional on (x t ,Z − ), the first term is fixed and ν t ∼N (0,ζ 2 ) remains independent. Its density is bounded by 1/(ζ √ 2π), so P |r t (θ − )|≤ ζη p π/2 ≤ η. 19 Together, this gives P(|r t (θ ∗ )|≤ u)≤ η, u := ζη p π/2 1 + R 2 /(nλ) .(36) Next, we upper bound the term ∥F − ( ̃ θ)− F − (θ ∗ )∥ 2 . Using Lemma 5, since ̃ θ− θ ∗ = b DP by definition (see (7)), we can write F − ( ̃ θ)− F − (θ ∗ ) = (X − ⊤ DX − + nλI) | z M dp b DP , where ∥M dp ∥ op ≤ X − ⊤ X − op +λn. Due to Assumption 1, we can apply Remark 5.40 in Vershynin (2012) with deviation parameter t = √ n + d to get X − ⊤ X − op ≤ (n− 1) E[x ⊤ ] op + C(n + d), with probability at least 1− 2e −c 1 (n+d) , for absolute constants C,c 1 > 0. Then, again by Assumption 1, we have that E[x ⊤ ] op ≤ C (see e.g. the argument in Lemma C.1 of Bombari and Mondelli (2025)), which readily gives, after enlarging C, ∥M dp ∥ op ≤ nλ + C(n + d).(37) Theorem 3.1.1 in Vershynin (2018), applied to the independent Gaussian coordinates of b DP /σ DP , yields ∥b DP ∥ 2 = O( √ dσ DP ) with probability at least 1− 2e −c 2 d , for an absolute constant c 2 > 0. Taking the intersection with the previous event, whose total failure probability is at most 2e −c 1 (n+d) + 2e −c 2 d , gives ∥F − ( ̃ θ)− F − (θ ∗ )∥ 2 =∥M dp b DP ∥ 2 = O σ DP √ d (nλ + n + d) .(38) Then, merging (36) and (38) in (30), and using Lemma 4, gives, with probability at least 1 − η − 2e −c 1 (n+d) − 2e −c 2 d , min τ∈[−1,1] ∥x t − τbx∥ 2 2 R 2 ≤ C 1 n 2 (λ + (1 + d/n)) 2 σ 2 DP d R 2 minu 2 ,C 2 clip ,(39) where we used |ψ C clip (r)| 2 = minr 2 ,C 2 clip and |r t (θ ∗ )| > u on the signal event. Recalling u from above and σ DP from Proposition 1: u := ζη p π/2 1 + R 2 /(nλ) , σ DP = √ 2RC clip λ √ ρn , the bound becomes, for an absolute constant C 2 > 0, min τ∈[−1,1] ∥x t − τbx∥ 2 2 ∥x t ∥ 2 2 ≤ C 2 R 2 ∥x t ∥ 2 2 max ( 1, 2C 2 clip πζ 2 η 2 1 + R 2 nλ 2 ) 1 + C λ 2 1 + d n 2 d ρ . Here we used 1 + C(1 + d/n) λ ≤ 1 + C λ 1 + d n . By Assumption 1, ∥x t ∥ 2 2 = Θ(d) and R 2 = Θ(d), so the ratio displayed in the bound is O(1). Absorbing it into the absolute constant proves (15). A union bound over the Gram-matrix event, the privacy-noise event, and the signal anti-concentration event gives total failure probability at most η + 2e −c 1 (n+d) + 2e −c 2 d . 20 E Proofs for the extension to low-dimensional data Theorem 3. In the same setting as Theorem 1, for any rank-s projection P satisfying the conditions above, any reconstruction of x t from a ρ-zCDP mechanism obeys: E∥x t − bx∥ 2 2 E∥Px t ∥ 2 2 ≥ 1 2πe exp 2 s (h s (x ′ s )− ρ) ,(17) with x ′ s := √ s √ E∥Px t ∥ 2 2 Px t . Proof. Let U ∈ R d×s have orthonormal columns spanning Im(P ), so that P = U ⊤ and U ⊤ U = I s . Set x ∥ = Px t and bx ∥ = Pbx, both in Im(P ) ⊆ R d , and let v = U ⊤ x t and bv = U ⊤ bx be their coordinates in R s . Thus x ∥ = Uv, bx ∥ = Ubv, and the entropy notation in the theorem means h s (x t ) = h(v). Fix Z − . As in the proof of Theorem 1, the data-processing inequality and Lemma 2, applied to z t = (x t ,y t ), give I(v;bv)≤ I(x t ;bx)≤ ρ. Let us apply Lemma 3 with S = v and k = s, to the source v and reconstruction bv in R s . Since U preserves Euclidean norms, we obtain E∥x ∥ − bx ∥ ∥ 2 2 = E∥v−bv∥ 2 2 ≥ s 2πe exp 2 s (h s (x t )− ρ) .(40) Letting x ⊥ = (I − P )x t ∈ Im(P ) ⊥ , we have ∥x t − bx∥ 2 2 =∥x ∥ − Pbx∥ 2 2 +∥x ⊥ − (I − P )bx∥ 2 2 (41) ≥∥x ∥ − bx ∥ ∥ 2 2 .(42) Taking expectations, dividing by E∥Px t ∥ 2 2 and using h s (x ′ s ) = h s (x t ) + s 2 log s/E∥Px t ∥ 2 2 (again, via an application of Theorem 9.6.4 in Cover and Thomas (2001)) gives (17). Theorem 4. Consider the same setting as Theorem 2, but with R = Θ( √ s) and ∥x t ∥ 2 = Θ( √ s) replacing the corresponding Θ( √ d) assumptions. Let P ∈ R d×d be a rank-s projector, known to the attacker, such that x i ∈ Im(P ) for all i∈ [n]. Let ˆx P := R PF − ( ̃ θ) ∥PF − ( ̃ θ)∥ 2 .(18) Then, if n = Ω(s),λ = Ω(1),C clip = O(ζ), we have min τ∈[−1,1] ∥x t − τ ˆx P ∥ 2 2 ∥x t ∥ 2 2 ≲ s ρ ,(19) with probability at least 0.99. Proof. Consider the shorthand a := ψ C clip (x ⊤ t θ ∗ −y t ). Recall that b DP = ̃ θ−θ ∗ is the Gaussian noise defined in (7) and M dp = X − ⊤ DX − + nλI is the matrix constructed in the proof of Theorem 2. Projecting both sides of (30) over P gives −PF − ( ̃ θ) = aPx t − PM dp b DP = ax t − PM dp b DP .(43) Notice that we have PM dp b DP = PM dp Pb DP + PM dp (I − P )b DP = PM dp Pb DP , where we use that X − (I − P ) = 0, due to x i ∈ Im(P ) for all i∈ [n]. Let U ∈ R d×s have orthonormal columns spanning Im(P ), and set Z − := X − U . The rows of Z − are independent O(1)-subGaussian vectors in R s . Applying the concentration argument used for (37), now in dimension s, gives X − ⊤ X − op = Z ⊤ − Z − op ≤ C(n + s) 21 with probability at least 1− 2e −c 2 n . Consequently, ∥PM dp ∥ op ≤∥M dp ∥ op ≤ nλ + C(n + s). Then, we have that ∥PM dp b DP ∥ 2 ≤∥PM dp ∥ op ∥Pb DP ∥ 2 = O ((1 + λ)n + s)σ DP √ s , with probability at least 1− 2e −c 2 n − 2e −c 3 s , where the last equality follows from a similar argument as the one used to obtain (38). Then, the argument follows the same path as the one for the proof of Theorem 2, after (38) and using Lemma 4. This yields, with probability at least 1− η− 2e −c 2 n − 2e −c 3 s , min τ∈[−1,1] ∥x t − τbx∥ 2 2 ∥x t ∥ 2 2 ≤ C 1 R 2 ∥x t ∥ 2 2 n 2 (λ + (1 + s/n)) 2 σ 2 DP s R 2 minu 2 ,C 2 clip , where u is defined as a function of η in (36). Apart from the factor R 2 /∥x t ∥ 2 2 , the RHS is the bound in (39) with d replaced by s. Furthermore, ∥x t ∥ 2 2 = Θ(s) and R 2 = Θ(s), so that R 2 /∥x t ∥ 2 2 = O(1). Following the same substitution as at the end of the proof of Theorem 2, with n = Ω(s), λ = Ω(1), and C clip = O(ζη), we obtain the desired result by taking η to be a sufficiently small absolute constant. F Comparison with Balle et al. (2022) Corollary 4 in (Balle et al., 2022) bounds reconstruction success in terms of the small-ball probability κ(r) := sup v∈R d P(∥x t − v∥ 2 ≤ r). Writing ̄κ(r) ∈ (0, 1] for an upper bound on κ(r), we convert their guarantee to expected squared error by integrating the corresponding tail bound: D := E∥x t − bx∥ 2 2 ≥ Z ∞ 0 2r 1− exp − h p log(1/ ̄κ(r))− √ ρ i 2 + dr.(44) This follows from D = R ∞ 0 2rP(∥x t − bx∥ 2 > r)dr. For x t ∼N (0,I d ), we use the Chernoff bound from their proof of Proposition 7, ̄κ(r) = exp d 2 1− r 2 d + log r 2 d , 0 < r ≤ √ d, 1,r > √ d. For the uniform distribution on the ball of radius √ d, their Proposition 6 proof gives, after rescaling, κ(r) = min(r/ √ d) d , 1. Thus, our comparison uses the small-ball bounds in their proofs, retaining their radius dependence before the asymptotic simplifications in the statements of the propositions. G Experimental details and additional numerical results This appendix describes the datasets (Appendix G.1) and the experimental procedure (Appendix G.2), and then provides more details for the figures in the main text. We provide further visual reconstructions for the full-dimensional attack (Appendix G.4) and the remaining experiments on the low-dimensional setting (Appendix G.3). Parameter configurations are given in Appendix G.5. G.1 Datasets Synthetic data. We draw n = 1000 training examples independently and uniformly from the sphere of radius R := √ d. We draw θ true uniformly from the unit sphere and generate labels according to Eq. (1). Validation and test sets of 10,000 examples are drawn from the same distribution. 22 Synthetic rank-s data. For the low-dimensional experiments, we design a distribution that has a subspace with a strong signal, and a weak component on its complement. For s < d, each example is initially generated as x = x ∥ + x ⊥ , where the two components are independent and uniform on spheres in complementary coordinate blocks of size s and d− s, with respective radii √ s and τ b p s/(1− τ b 2 ). Then, E[x ∥ x ∥ ⊤ ] = I on the signal block, E[x ⊥ | x ∥ ] = 0, and every example has norm ∥x∥ 2 = p s/(1− τ b 2 ), with ∥x ⊥ ∥ 2 /∥x∥ 2 = τ b . The experiments in Fig. 5a use τ b = 0.01, so the data lies near, rather than exactly in, the signal subspace. A fixed Householder reflection is applied to every split, mixing the coordinate blocks without changing these norms. The attacker estimates the rank-s projector from the leading right singular vectors of X − ; the true signal subspace is not supplied to the attack. The feature clipping radius R is set 0.01 above the sample norm to avoid clipping due to rounding. We use 1000 training examples and 2000 examples in each of the validation and test sets, with θ true and labels generated as in the preceding paragraph. CIFAR-10. We form a binary frog-versus-truck problem from classes 6 and 9. The official training data for those classes are split into 8000 training and 2000 validation examples, and the official test split provides 2000 test examples. ImageNet. We form binary problems from pairs of ImageNet-21K classes, specifically African elephant (n02504458) versus giant panda (n02510455). The pooled images of each class are shuffled and split 80/10/10, giving 2160 training and 270 validation and test examples. Images are resized by downscaling to produce data of varying dimension. Image preprocessing. RGB pixel values are mapped to [0, 1] and centered as follows: for each dataset and resolution, we subtract a fixed public mean image, fitted using 10,000 training images from classes outside the private binary pair. The same mean is reused across the training, validation, and test splits. Each centered feature vector is then rescaled to norm √ d, with R = √ d. Images retain their binary class labels, and label noise is not added. G.2 Experimental procedure For each run, data is generated as described above. The learner’s private linear regression is implemented using a damped Newton solver on the clipped, regularized Huber objective in (6), running until convergence. The private release is implemented by adding Gaussian noise as in (7), with the variance set by (8). Replicates and aggregation. Each quantitative synthetic setting attacks one target for each of three independent seeds, hence three target attacks in total. Each quantitative image setting attacks one target from each binary class for each of three seeds, hence six target attacks in total. Hyperparameters are selected using the mean validation risk over these replicates. Each plotted heatmap cell or curve point is then the mean reconstruction error over the same target attacks. The visual reconstruction panels are not averaged: each displays four targets (two from each class) for a single random seed. The numbers of seeds and targets per class used for each figure are listed in Appendix G.5. Privacy of hyperparameter selection. Our experiments compare output-perturbation mechanisms to illustrate the theoretical scaling laws, rather than evaluate an end-to-end private model-selection procedure. We therefore select hyperparameters using validation performance without accounting for the privacy cost of selection. The reported ρ guarantees apply to each trained mechanism, not the complete process including hyperparameter selection. Naturally, a real-world deployment on sensitive data would require private hyper- parameter selection, for example using the methods of Papernot and Steinke (2022); Koskela and Kulkarni (2023), and would give guarantees that covered the entire process. Image visualisation. For display of centered reconstructions, we choose the sign to give a nonnegative inner product with the centered, normalized target. We then multiply by the target’s saved inverse normal- ization scale, add back the public mean image, and clip RGB values to [0, 1]. We use the sign and scale of the target for visualization only. 23 G.3 Projected reconstruction: remaining figures 10 −2 10 0 10 2 10 4 ρ/s 0.0 0.5 1.0 Reconstruction error 10 0 10 2 10 4 ρ s= 10 464 22 1000 46 100 215 Figure 6: Projected reconstruction error on ImageNet (elephant vs. panda) data with d = 12,288. The projected attack uses a rank-s PCA subspace estimated from the known data. The left panel plots the projected attacks against ρ/s; the right panel plots them against ρ. Colours indicate the projection rank s. G.4 Further visual reconstructions In addition to Fig. 4, we present several more examples of reconstruction of ImageNet data in Fig. 7; and similarly for CIFAR-10 in Fig. 8. Target ρ / d = 1 0.951.000.950.92 ρ / d = 10 0.800.950.790.75 ρ / d = 100 0.350.460.350.32 ρ / d = 1000 0.060.060.060.05 Target ρ / d = 1 1.000.640.950.98 ρ / d = 10 0.990.570.980.94 ρ / d = 100 0.920.380.950.74 ρ / d = 1000 0.570.130.360.26 (a)(b) Figure 7: Additional ImageNet elephant-versus-panda reconstructions, presented as in Fig. 4. 24 Target ρ / d = 1 0.920.990.980.90 ρ / d = 10 0.920.720.690.58 ρ / d = 100 0.180.170.160.14 ρ / d = 1000 0.020.020.020.02 Target ρ / d = 1 0.580.680.820.69 ρ / d = 10 0.250.300.370.30 ρ / d = 100 0.050.060.060.05 ρ / d = 1000 0.010.010.010.01 (a)(b) Target ρ / d = 1 0.890.640.970.92 ρ / d = 10 0.620.980.730.82 ρ / d = 100 0.170.230.200.47 ρ / d = 1000 0.020.020.020.11 (c) Figure 8: CIFAR-10 frog-versus-truck reconstructions for all three target seeds, presented as in Fig. 4. 25 G.5 Run configurations per figure Each table below lists the configurations for each figure. If a parameter had a large number of values, we summarize this as the endpoints of the range, the number of values, and the increment, if it was a geometric range. SettingSynthetic Training examples n1,000 Validation examples10,000 Test examples10,000 Dimension d10–10,000 (7) Feature norm ∥x∥ 2 √ d Feature clipping R √ d Label noise ζ0.5 Privacy budget ρ0.1–10 5 (7, ×10) Regularization λ10 −4 –10 (11, × √ 10) Residual clipping C clip 10 −3 –1,000 (13, × √ 10) # of seeds3 Table 1: Configuration for Figure 2. SettingImageNet (elephant/panda) Training examples n2,160 Validation examples270 Test examples270 Dimension d12–12,288 (6, ×4) Feature norm ∥x∥ 2 √ d Feature clipping R √ d Privacy budget ρ1–10 5 (11, × √ 10) Regularization λ10 −4 –1 (9, × √ 10) Residual clipping C clip 10 −3 –10 (9, × √ 10) # of seeds3 Targets per class1 Table 2: Configuration for Figure 3. Hyperparameter selection used validation risk within λ ≥ 0.1 and C clip ≤ 0.01. SettingImageNet (elephant/panda) Training examples n2,160 Validation examples270 Test examples270 Dimension d12,288 Feature norm ∥x∥ 2 √ d Feature clipping R √ d Privacy budget ρ1.23× 10 3 –1.23× 10 8 (6, ×10) Regularization λ1 Residual clipping C clip 0.125 # of seeds1 Targets per class2 Table 3: Configuration for Figure 4. 26 SettingSynthetic rank-s signal CIFAR-10 (frog/truck) Training examples n1,0008,000 Validation examples2,0002,000 Test examples2,0002,000 Dimension d1,0003,072 Feature norm ∥x∥ 2 — √ d Feature clipping R3.17–31.6 (7) √ d Label noise ζ0.1— Privacy budget ρ10–10,000 (7, × √ 10)10–10,000 (10, ×2.15) Regularization λ10 −4 –1 (9, × √ 10)3.07, 307, 3,072 Residual clipping C clip 10 −4 –1 (9, × √ 10)0.1 Attacker PCA rank s10–1,000 (7)10–1,000 (7) Signal rank of the data 10–1,000 (7)— Bulk-to-signal ratio τ b 0.01— # of seeds33 Targets per class—1 Table 4: Configuration for Figure 5. Hyperparameter selection used validation risk within λ ≥ 0.1 and C clip ≤ 0.1ζ for Synthetic rank-s signal; λ≥ 10 and C clip ≤ 0.1 for CIFAR-10 (frog/truck). SettingImageNet (elephant/panda) Training examples n2,160 Validation examples270 Test examples270 Dimension d12,288 Feature norm ∥x∥ 2 √ d Feature clipping R √ d Privacy budget ρ1–10 5 (11, × √ 10) Regularization λ1–1,000 (7, × √ 10) Residual clipping C clip 0.01, 0.1 Attacker PCA rank s10–1,000 (7) # of seeds3 Targets per class1 Table 5: Configuration for Figure 6. Hyperparameter selection used validation risk within λ ≥ 10 and C clip ≤ 0.01. SettingImageNet (elephant/panda) Training examples n2,160 Validation examples270 Test examples270 Dimension d12,288 Feature norm ∥x∥ 2 √ d Feature clipping R √ d Privacy budget ρ1.23× 10 3 –1.23× 10 8 (6, ×10) Regularization λ1 Residual clipping C clip 0.125 # of seeds2 Targets per class2 Table 6: Configuration for Figure 7. 27 SettingCIFAR-10 (frog/truck) Training examples n8,000 Validation examples2,000 Test examples2,000 Dimension d3,072 Feature norm ∥x∥ 2 √ d Feature clipping R √ d Privacy budget ρ307–3.07× 10 7 (6, ×10) Regularization λ1 Residual clipping C clip 0.125 # of seeds3 Targets per class2 Table 7: Configuration for Figure 8. 28