PaperlayerView exact revision on arXiv

Source-linked AI summary

A Sharp Transition in Data Reconstruction under Differential Privacy

Max Cairney-Leeming, Simone Bombari, Marco Mondelli

arXiv:2609.37344v1cs.LGcs.AIstat.ML

TL;DR

The paper studies when differential privacy prevents an informed attacker from reconstructing a training sample, a question left open by earlier bounds for general target priors. It combines entropy-based lower bounds with an attack on output-perturbed linear regression, finding a transition at ρ ≍ d that shifts to ρ ≍ s for data in an s-dimensional subspace.

  • Problem

    Prior bounds leave unclear whether reconstruction is possible for ρ ≫ d for general target priors, while small-ball probabilities can be difficult to compute.

    Source: §1 · p. 2

  • Method

    The paper derives entropy-based lower bounds for any ρ-zCDP mechanism and attack, and analyzes an explicit attack on output-perturbed linear regression, including a subspace-aware extension.

    Source: §1 · p. 2

  • Results

    The results identify a reconstruction transition at ρ ≍ d, shifting to ρ ≍ s for data supported on an s-dimensional subspace.

    Source: §1 · p. 2, §6 · p. 10

  • Takeaways & Limitations

    Data dimensionality, including effective dimension for subspace-supported data, is a relevant scale for assessing privacy budgets against reconstruction.

    Source: §1 · p. 2

    The analysis leaves extensions to other algorithms and nonlinear subspaces, and to attackers lacking the remaining training data, for future work.

    Source: §6 · p. 10

Abstract

from arXiv · show

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

1 Introduction

The paper asks when a privacy budget makes accurate reconstruction feasible, given that prior bounds left tightness for general target priors unclear. It identifies a transition at ρ ≍ d, shifting to ρ ≍ s for data in an s-dimensional subspace.

1 Introduction

  • The unresolved question is whether reconstruction can succeed for ρ ≫ d, since prior general-prior bounds rely on small-ball probabilities that may be difficult to compute.The paper studies informed attackers who know all non-target training data and the output-perturbation hyperparameters.Source: §1 · p. 2
  • For any ρ-zCDP mechanism and attack, accurate reconstruction is impossible when ρ ≪ h(xt); for target priors with h(xt) ≍ d, this gives ρ ≪ d.The stated entropy scaling holds for the target distributions considered by Balle et al. (2022) and for distributions with independent entries.Source: §1 · p. 2
  • An explicit attack on output-perturbed DP linear regression succeeds with high probability when ρ ≫ d for a natural range of regularization and clipping parameters.This provides the converse to the entropy-based lower bound.Source: §1 · p. 2
  • The reconstruction threshold is ρ ≍ d in DP linear regression and shifts to ρ ≍ s for data supported on an s-dimensional subspace.The paper reports experiments on synthetic data and natural images from CIFAR-10 and ImageNet.Source: §1 · p. 2
  • For data on an s-dimensional subspace, entropy-based lower bounds and a subspace-aware attack together place the reconstruction transition at ρ ≍ s.Source: §1 · p. 2

2 Related work

Prior work studies reconstruction from non-private and private models, as well as the privacy budgets associated with membership attacks. This work combines entropy-based impossibility bounds with a successful reconstruction attack to establish a sharp transition.

2 Related work

  • Prior reconstruction research covers extraction from generative models and classifiers, theoretical results in specific network settings, and a closed-form attack on unclipped, non-private generalized linear models when the rest of the data is known.The cited settings include homogeneous networks, infinite-width shallow networks, and sufficiently over-parameterized models.Source: §2 · p. 2
  • For private models, prior work links membership-inference feasibility to privacy budgets and studies reconstruction robustness, stronger mechanism-specific bounds, f-DP, multiple-point recovery, and DP-SGD batch recovery.The discussion also notes bounds based on attack bias and variance that require budgets logarithmic in the target-prior diameter to rule out reconstruction.Source: §2 · pp. 2–3
  • This work combines entropy-based impossibility guarantees with a provably successful attack, identifying effective data dimension as the scale for assessing reconstruction protection.Source: §2 · p. 3
  • Prior work reports that larger, sometimes dimension-dependent privacy budgets can preserve utility while providing meaningful membership protection in several settings.Examples include locally private methods, language models, and medical imaging; Aerni et al. (2024) report budgets well above 10^3 outperforming heuristic defenses against membership attacks.Source: §2 · p. 3

3 Preliminaries

The preliminaries specify the informed reconstruction threat model and the linear-regression setting. They also describe output perturbation as adding Gaussian noise to a regularized empirical-risk minimizer, with noise calibrated to privacy and sensitivity-related hyperparameters.

3 Preliminaries

  • The linear-regression setup uses bounded-norm features and i.i.d. feature-label pairs, and evaluates estimates by test risk.Source: §3 · p. 3
  • The paper defines ρ-zCDP using the α-Rényi divergence between outputs on datasets differing in one input-label pair.Source: §3 · p. 3
  • Output perturbation adds Gaussian noise to the regularized empirical-risk minimizer, with the noise scaled according to privacy and the feature-norm bound.The method uses regularization λ and clipping threshold Cclip; larger λ or smaller Cclip reduces the effect of one training sample on the minimizer.Source: §3 · p. 4
  • The attacker receives the released model, all training data except the target, and the output-perturbation hyperparameters, then reconstructs the target feature.Source: §3 · p. 4

4 Main results

The section establishes a reconstruction threshold by pairing entropy-based impossibility bounds for arbitrary private mechanisms and attacks with a successful attack on private linear regression. When data lie in a known lower-dimensional subspace, the threshold scales with that effective dimension rather than the ambient dimension.

4.1 Information-theoretic lower bound

  • For normalized targets with differential entropy h(x′_t) = Θ(d), accurate reconstruction is information-theoretically impossible when ρ ≪ d, for example for isotropic Gaussians, uniform-ball distributions, and independent entries with marginal entropy bounded away from zero.The lower bound applies to any ρ-zCDP mechanism and attack; it relates normalized mean squared error to the target's scale-normalized differential entropy.Source: §4.1 · pp. 4–5

4.2 Algorithmic upper bound

  • When ρ ≫ d, an attack using the non-target data and perturbed linear-regression weights can reconstruct the target direction with high probability under suitable regularization and clipping.The result assumes well-behaved feature tails; the stated regime uses n = Ω(d), λ = Θ(1), and small clipping constants, with sign and scale ambiguities remaining.Source: §4.2 · pp. 6–7

4.3 Extension to low-dimensional data

  • For data in a rank-s subspace known to the attacker, the entropy lower bound and projected attack establish a sharp transition at ρ ≍ s when the target's entropy scales with s.The lower bound applies when the target lies close to the subspace; the attack result uses R and target norm of order √s and conditions including n = Ω(s), λ = Ω(1), and Cclip = O(ζ).Source: §4.3 · p. 8

5 Experiments

Experiments reproduce the predicted reconstruction transition across synthetic data and natural images: it scales with ambient dimension d for full-dimensional data and with effective dimension s for projected attacks. CIFAR-10 also shows that choosing too-small a subspace can leave signal unreconstructed.

5 Experiments

  • Reconstruction error curves collapse when plotted against ρ/d for synthetic data and ImageNet, showing a transition near ρ/d ≍1 across dimensions and image resolutions.For synthetic data, the ρ/d boundary separates successful from unsuccessful attacks; ImageNet shows the same pattern.Source: §5 · p. 9, Figure 3 · p. 9
  • ImageNet reconstruction curves collapse against ρ/d across image resolutions, providing evidence that the dimension-scaled transition persists for natural images.Figure 3 searches hyperparameters within λ ≥0.1 and Cclip ≤0.01; Figure 4 shows reconstructions as the privacy budget grows.Source: §5 · p. 9, Figure 3 · p. 9, Figure 4 · p. 9
  • For projected attacks, curves overlap against ρ/s but separate against ρ on synthetic rank-s data, indicating a transition at ρ ≍s.The attack estimates the rank-s PCA projector from the other training examples.Source: §5 · pp. 9–10, Figure 5 · p. 10
  • On CIFAR-10, projected-attack curves also collapse against ρ/s, but rank s = 10 leaves an error plateau even at large ρ/s because the subspace misses target signal.Similar results for ImageNet are reported in Figure 6.Source: §5 · p. 10, Figure 5 · p. 10

6 Conclusions

The conclusions place the reconstruction transition at ρ ≍d when target entropy scales with dimension, and at ρ ≍s for data on a known s-dimensional subspace. The appendices define matrix notation and support the privacy analysis of output perturbation.

6 Conclusions

  • When target entropy is Θ(d), reconstruction is impossible for ρ ≪d, while an output-perturbation attack achieves arbitrary accuracy for ρ ≫d; on a known s-dimensional subspace, the transition is ρ ≍s.The conclusion identifies the data prior as relevant to the effective guarantees of a privacy budget.Source: §6 · p. 10

A Additional notation

  • For symmetric matrices, tr(A) denotes trace, smin(A) and smax(A) denote extreme singular values, and λmin(A) and λmax(A) denote extreme eigenvalues.The notation also defines A ⪯B as B−A positive semidefinite and [b]+ as max{b, 0}.Source: A Additional notation · p. 14

B Sensitivity and privacy of output perturbation

  • The appendix bounds the sensitivity of the output-perturbation minimizer and states a condition under which the algorithm is ρ-zCDP.It assumes the learner uses the smallest noise variance satisfying the privacy bound, since larger variances cause greater-than-necessary utility loss.Source: B Sensitivity and privacy of output… · pp. 14–15

C Proof of the information-theoretic lower bound

The lower-bound proof combines the information limit imposed by zCDP with a rate-distortion argument. This yields a bound on reconstruction error for any attack, subject to assumptions on the target feature distribution.

C Proof of the information-theoretic lower bound

  • The proof first bounds the mutual information between the target and the private mechanism’s output by ρ, then applies data processing to the attacker’s reconstruction.The target feature is assumed independent of the rest of the dataset.Source: C Proof of the information-theoretic… · pp. 15, 17
  • Theorem 1 gives a lower bound on expected reconstruction error for any ρ-zCDP mechanism and any attack, assuming the target feature is independent of the remaining dataset.The proof also assumes the target has a density, finite differential entropy, and finite positive second moment.Source: C Proof of the information-theoretic… · p. 17
  • A rate-distortion inequality relates the target’s differential entropy to the reconstruction error when the induced reconstruction channel has rate at most ρ.The proof applies the rate-distortion definitions to the target feature in dimension d.Source: C Proof of the information-theoretic… · pp. 16, 18

D Proof of the algorithmic upper bound

The proof of the algorithmic upper bound combines control of the target-dependent signal with bounds on the effect of privacy noise. Its argument uses a leave-target-out optimizer, concentration estimates, and a geometric lemma relating the signal to the reconstruction.

D Proof of the algorithmic upper bound

  • A geometric lemma bounds the reconstruction error when q is a nonzero scaled target vector plus an additive perturbation.The proof applies the reverse triangle inequality and minimizes over a scalar in [-1, 1].Source: D Proof of the algorithmic upper bound · p. 18
  • A leave-target-out optimizer provides a reference point for lower-bounding the target-dependent clipped residual.The objective on the non-target data is strongly convex and has a unique minimizer; its gradient vanishes there.Source: D Proof of the algorithmic upper bound · p. 19
  • Conditioning on the target feature and non-target data leaves independent Gaussian noise in the residual, enabling an anti-concentration bound.The residual and its clipped version have the same sign in the stated argument.Source: D Proof of the algorithmic upper bound · p. 19
  • The proof bounds the change in F− caused by output perturbation using matrix control and a concentration bound on the Gaussian perturbation.It combines these bounds with the signal event to establish the theorem's stated probability guarantee.Source: D Proof of the algorithmic upper bound · p. 20
  • The proof closes Theorem 2's high-probability bound by combining signal anti-concentration, Gram-matrix control, and privacy-noise bounds.A union bound gives total failure probability at most η + 2e^(-c1(n+d)) + 2e^(-c2d).Source: D Proof of the algorithmic upper bound · pp. 19–20

E Proofs for the extension to low-dimensional data

The low-dimensional proofs adapt the reconstruction bounds to data in a known s-dimensional subspace. A comparison subsection describes how the paper converts Balle et al.'s small-ball guarantees into expected squared error for comparison.

E Proofs for the extension to low-dimensional data

  • Theorem 3's lower-bound proof represents the target in orthonormal subspace coordinates and applies data-processing and entropy arguments in s dimensions.The coordinates preserve Euclidean norms under the subspace embedding.Source: E Proofs for the extension to… · p. 21
  • Theorem 4's proof replaces the ambient dimension d with s in the attack bound under the stated sample-size and algorithm-parameter conditions.The proof uses n = Ω(s), λ = Ω(1), and Cclip = O(ζη).Source: E Proofs for the extension to… · pp. 21–22

F Comparison with Balle et al. (2022)

G Experimental details and additional numerical results

The appendix collects experimental details and supplementary results, covering datasets, procedures, figures, additional reconstructions, and parameter settings.

G Experimental details and additional numerical results

G.1 Datasets

The experiments use synthetic data and binary image-classification datasets, with a separate synthetic construction for near-subspace data. Image features are centered using a public mean and rescaled.

G.1 Datasets

  • The full-dimensional synthetic experiment draws 1,000 training examples uniformly from a sphere and generates labels using the paper's linear-regression setup.Validation and test sets each contain 10,000 examples drawn from the same distribution.Source: §G.1 · p. 22
  • The synthetic rank-s construction combines independent components in complementary coordinate blocks, with a strong signal component and a weak orthogonal component.In Fig. 5a, τb = 0.01, so the data lies near rather than exactly in the signal subspace; the attacker estimates the subspace from non-target examples.Source: §G.1 · p. 23
  • CIFAR-10 is used for a frog-versus-truck binary task, with 8,000 training, 2,000 validation, and 2,000 test examples.Source: §G.1 · p. 23
  • ImageNet-21K is used for an African-elephant-versus-giant-panda binary task, with images resized to vary their dimension.The split contains 2,160 training and 270 validation and test examples.Source: §G.1 · p. 23
  • Image pixels are mapped to [0, 1], centered with a public mean image, and rescaled to a fixed norm; the binary labels are retained without added label noise.Source: §G.1 · p. 23

G.2 Experimental procedure

The appendix documents the experimental procedure and its privacy accounting, then supplies projected and additional image reconstructions alongside per-figure run configurations.

G.2 Experimental procedure

  • Each run trains clipped, regularized Huber regression to convergence with a damped Newton solver, then adds Gaussian noise using the specified variance.Source: §G.2 · p. 23
  • Quantitative image settings average reconstruction error across six target attacks, while visual panels show four targets from one random seed without averaging.Source: §G.2 · p. 23
  • Reported ρ guarantees cover each trained mechanism, not validation-based hyperparameter selection; deployment requires private selection for guarantees covering the full process.Source: §G.2 · p. 23
  • For display, centered reconstructions are sign-aligned and rescaled using the target, then shifted by the public mean and clipped to [0, 1].Source: §G.2 · p. 23

G.3 Projected reconstruction: remaining figures

  • Figure 6 plots ImageNet projected reconstruction error against ρ/s and ρ, with colors encoding PCA projection rank s.Source: Figure 6 · p. 24

G.4 Further visual reconstructions

G.5 Run configurations per figure

  • Appendix G.5 lists configurations by figure and summarizes wide parameter ranges by endpoints, value count, and increment.Source: §G.5 · p. 26

Related papers

Loading 2609.37344v1…