From Pixels to Privacy-Sensitive Features: An Information-Theoretic Framework for Reconstruction Bounds

Henry Bourne; Robert F. Allison

stat.MLOct 9, 2026

From Pixels to Privacy-Sensitive Features: An Information-Theoretic Framework for Reconstruction Bounds

Authors: Henry Bourne, Robert F. Allison

Organizations: Department of Mathematics The University of Bristol Beacon House, Queens Road, Bristol, BS8 1QU, United Kingdom

Abstract

What can an adversary recover from a model trained with DP-SGD? Its $(\varepsilon,δ)$ guarantee does not answer this question directly. We derive a distortion bound that can be computed before training and applies even to an adversary who observes the parameter trajectory during training, knows every other training record and the population distribution from which the training records are drawn. The analyst may choose the representation in which error is measured, allowing the bound to target the aspects of reconstruction that are privacy-sensitive in a given application. Our information-theoretic framework separates two contributions: the information about a record revealed by training, measured through conditional mutual information, and the uncertainty already present in the data distribution, measured through source entropy. Rate-distortion theory combines them into a lower bound on the expected error of every reconstruction attack. For DP-SGD, the leakage bound depends only on the sampling rates and noise multipliers, while the source entropy is lower-bounded from a sample with finite-sample confidence. An orthogonal block construction keeps the resulting bound informative for high-dimensional images. We instantiate the framework in pixel space and in LPIPS feature space, obtaining, to our knowledge, the first lower bound on reconstruction distortion measured directly by LPIPS. On a range of image datasets the bounds establish non-trivial unavoidable expected reconstruction error within heuristically recommended privacy-budget ranges and beyond. Experiments compare the bounds with strong reconstruction attacks and identify the principal sources of the remaining slack.

Figures & tables

Figure 1: Modular information-theoretic framework. Mechanism leakage and a held-out entropy bound in a chosen representation

\Psi

combine through rate–distortion into a lower bound on every attack; each module can be tightened or replaced independently.

Figure 2: CelebA:

95\%

-confidence reconstruction bounds and accuracy. Pixel and LPIPS bounds

\rho^{\star}

(left axis) and test accuracy (mean

\pm

s.d. over three seeds; right axis), against

\varepsilon

\delta=n_{\mathrm{train}}^{-1.1}

. The ratio

\rho^{\star}

measures reconstruction error relative to the optimal prior-only guess: larger is more protective, and

\rho^{\star}=1

means no improvement over that guess. Shading marks the privacy tiers of Ponomareva et al. (2023) ; other datasets in Figure 5 .

Figure 3: CelebA: bounds, attacks and slack decomposition. Pixel (left) and LPIPS (right) reconstruction ratios at leakage

\gamma

. The bound

\rho^{\star}

, block-specific bound

\rho_{\mathrm{blk}}

, achieved codebook-release error

\rho_{\mathrm{cb}}

, and attack errors against a single full-batch noisy-gradient release and a

100

-step subsampled DP-SGD trajectory are shown. The large

\rho^{\star}

-to-

\rho_{\mathrm{blk}}

gap is caused by charging every block the full leakage; the close

\rho_{\mathrm{blk}}

-to-

\rho_{\mathrm{cb}}

match shows that little slack remains in the rate–distortion step. Details are in Section G.6 .

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

	Threat Model	Mechanism Leakage Bound	Bounded Object (Metric)	Prior Integration into Bound	Prior Assumption and Source	Experimental Instantiation
Bhowmick et al. (2018)	Uninformed, all iterates	$\varepsilon$ -LDP: $e^{\varepsilon}$ scaling	$\Pr[\text{error}\leq\eta]$	Baseline success $p$	Analytic: Uniform/Zipfian	MNIST, CIFAR-10, Flickr, Reddit: Accuracy gap
Balle et al. (2022)	Informed, final release	RDP/ $\varepsilon$ -DP: $e^{\varepsilon}$ scaling	$\Pr[\text{error}\leq\eta]$	Baseline success $\kappa$	Analytic: Uniform/Gaussian	NA
Xiao & Devadas (2023)	Uninformed, final release	PAC Privacy: $I(X;\mathcal{M}(X)+B)$	$\Pr[\text{error}\leq\eta]$	Baseline success $\delta$	Analytic: Uniform population	CIFAR-10, MNIST: Noise magnitude
Guo et al. (2023)	Informed, final release	RDP + Fano: Generalized Fano	$\Pr[\text{exact}]$	Baseline success $p^{*}$ , Entropy $H(p)$	Analytic: Prob. vector $p$	Synthetic (RR, Gaussian), IWPC, GPT-2: Advantage, MSE
Hayes et al. (2023)	Informed, all iterates	ReRo: Blow-up function	$\Pr[\text{exact}]$	Baseline success $\kappa$	Analytic: Uniform shortlist	MNIST, CIFAR-10: Success probability
Kaissis et al. (2023)	Informed, final release	$f$ -DP: Closed-form / Edgeworth	$\Pr[\text{exact}]$	Baseline success $\kappa$	Analytic: Uniform $1/n$ prior	Numerical: success bound vs. $\kappa$ at published DP-SGD hyperparameters

Appendix

Table 1: The reconstruction-guarantee lineage in order of first public release, split by bounded metric: probability guarantees (

\Pr

) above the double rule, expected-error guarantees (

\mathbb{E}

) below. Threat Model gives background knowledge ( Informed : adversary knows all training records but the target; Uninformed : no background dataset knowledge; Target-informed : adds target-specific auxiliary data) and access ( Final release : the mechanism’s final output only; All iterates : intermediate updates or gradients). Prior Integration indicates whether a prior over the target enters the guarantee itself, and Prior Assumption and Source whether it is assumed ( Analytic ) or approximated from data ( Empirical ); structural assumptions on the estimator or data space are noted in the same cell. Baseline success unites disparate notations for the maximum probability of guessing the target from prior knowledge alone; Guerra-Balboa et al. (2026) instead use the collision probability

\kappa_{\pi}=\Pr_{Z,Z^{\prime}\sim\pi}[Z=Z^{\prime}]

, which coincides with a baseline success only under a uniform prior.

\Delta\Pr

denotes a guarantee stated as an advantage — the increase in success attributable to the target’s participation — rather than a raw probability. Experimental cells list representative settings, not an exhaustive inventory. Abbreviations: LDP/RDP/

f

-DP (Local, Rényi, and

f

-differential privacy), CMI (conditional mutual information), LCB (lower confidence bound), HCRB (Hammersley–Chapman–Robbins bound), CRB (Cramér–Rao bound), FIL (Fisher information leakage), dFIL (diagonal FIL), RR (randomized response).

Split	Supplies	Requirement	Disjoint from	Size and property
shared — the source side, computed once per dataset
$D_{\perp}$	$U=d^{-1/2}H_{d}V^{\top}$ , $\tr\hat{\Sigma}$ , dither scales	Req 3 , Req 4	$D_{\mathrm{est}}^{\star}$ , $D_{\mathrm{targets}}^{\star}$	$\gtrsim d$ , for a full-rank $\hat{\Sigma}$ ; may be replaced by a data-free $U$ and a declared $\tr\Sigma$
$D_{\mathrm{est}}$	$\bar{h}_{\mathrm{LB}}$	Req 5	$D_{\perp}^{\star}$	largest available; i.i.d. from $P_{x}$ ; margins $\propto n^{-1/2}$
(a) deployment, and the privacy-spectrum runs
$D_{\mathrm{train}}$	every charged DP-SGD run	Req 1 , Req 2	$D_{\mathrm{val}}$ , $D_{\mathrm{test}}$	i.i.d. from $P_{x}$ ; no cross-record preprocessing; may overlap $D_{\perp}$ and $D_{\mathrm{est}}$
$D_{\mathrm{val}}$	selection among runs	Req 6	$D_{\mathrm{train}}$	small

Appendix

Table 2: The partitions of Figure 4 , and what constrains each. The requirement column refers to Section F.1 ;

\star

marks a disjointness the guarantee or the threat model requires, the rest are kept for a clean joint statement and could be relaxed.

Panel of Figure 4 — Figure 4: How the available data is partitioned. Green blocks supply the bound, red blocks are the protected records trained on, and blue blocks are data the attack uses. In (a) the bound’s split into $D_{\perp}$ and $D_{\mathrm{est}}$ (top row) and the training split (bottom row) are drawn independently and may overlap; only $D_{\perp}$ and $D_{\mathrm{est}}$ must be disjoint. $D_{\perp}$ and $D_{\mathrm{est}}$ are shared, so the rotation and the entropy estimate are the same in the deployment (a) and the attack experiment (b) ; the targets are held out from both.

	pixel ( $\Psi=\mathrm{id}$ )			perceptual ( $\Psi=\Psi_{\mathrm{LPIPS}}$ )
Dataset	$\tr\Sigma$	UCB margin	$\mathrm{RMSE}_{\mathrm{prior}}/\sqrt{d}$	$\tr\Sigma_{\Psi_{\mathrm{LPIPS}}}$	UCB margin	$\mathrm{RMSE}_{\mathrm{prior}}/\sqrt{m}$
MNIST	$3.43\times 10^{6}$	$2.5\%$	$66.2$	$0.1338$	$5.8\%$	$2.05\times 10^{-3}$
CIFAR-10	$1.24\times 10^{7}$	$3.2\%$	$63.6$	$0.2463$	$3.3\%$	$2.78\times 10^{-3}$
CelebA	$5.91\times 10^{7}$	$0.5\%$	$69.3$	$0.1445$	$0.6\%$	$2.13\times 10^{-3}$
ImageNette	$2.46\times 10^{8}$	$16.6\%$	$70.7$	—	—	—

Appendix

Table 3: The reference scale and how far its finite-sample one-sided

95\%

upper confidence bound ( Section G.2 ) lies above it, relative to the point estimate, estimated on

D_{\perp}

(sizes in Section G.1 ).

\mathrm{RMSE}_{\mathrm{prior}}/\sqrt{d}

is the per-coordinate root-mean-squared error of the prior-mean guess, in grey levels for pixels and feature units for

\Psi_{\mathrm{LPIPS}}

(

m=31{,}872

Figure 5: What a deployed DP-SGD run guarantees across the privacy spectrum, on MNIST, CIFAR-10 and ImageNette (CelebA is in Figure 2 ). At each target

\varepsilon

(expected batch

1024

100

epochs,

C=1

\delta=n_{\mathrm{train}}^{-1.1}

): the pixel reconstruction bounds and, on MNIST and CIFAR-10, the perceptual bounds (left axis), each a

95\%

lower bound holding against every adversary of Section 3.1 and every architecture at that configuration, and the test accuracy the same run attains (right axis, mean

\pm

standard deviation over

3

seeds; non-private baseline as the dotted horizontal line). Shaded: the

\varepsilon\leq 1

(dark) and

1<\varepsilon\leq 10

(light) regimes of Ponomareva et al. (2023) ;

\varepsilon>10

is unshaded.

	MNIST			CIFAR-10			CelebA			ImageNette
$\varepsilon$	acc.	$\rho^{\star}_{\mathrm{px}}$	$\rho^{\star}_{\Psi_{\mathrm{LPIPS}}}$	acc.	$\rho^{\star}_{\mathrm{px}}$	$\rho^{\star}_{\Psi_{\mathrm{LPIPS}}}$	acc.	$\rho^{\star}_{\mathrm{px}}$	$\rho^{\star}_{\Psi_{\mathrm{LPIPS}}}$	acc.	$\rho^{\star}_{\mathrm{px}}$
$1$	0.313	0.907	0.908	0.187	0.887	0.952	0.923	0.888	0.944	0.122	0.865
$2$	0.865	0.892	0.886	0.373	0.867	0.940	0.946	0.861	0.931	0.239	0.845
$4$	0.953	0.845	0.831	0.564	0.815	0.901	0.954	0.805	0.892	0.440	0.795
$8$	0.970	0.754	0.726	0.655	0.711	0.822	0.957	0.696	0.801	0.603	0.683
$16^{\dagger}$	0.971	0.556	0.536	0.703	0.523	0.612	0.961	0.513	0.588	0.662	0.445

Appendix

Table 4: Values behind Figures 2 and 5 : test accuracy (mean over

3

seeds) and the pixel and perceptual bounds at each target

\varepsilon

, each a

95\%

lower bound.

\dagger

: the

\varepsilon>10

band of Ponomareva et al. (2023) .

Dataset	$\varepsilon$	$\gamma$ (bits)	$\sigma$	$k^{\star}$ (pix / $\Psi_{\mathrm{LPIPS}}$ )		$\nu^{2\star}$ (pix / $\Psi_{\mathrm{LPIPS}}$ )
MNIST	$1$	0.048	5.574	14	16	1.6	3.2
	$2$	0.169	3.028	16	32	1.6	6.4
	$4$	0.570	1.741	16	32	1.6	3.2
	$8$	1.785	1.110	28	32	1.6	1.6
	$16$	5.042	0.796	28	32	0.8	0.8
	$32$	13.150	0.617	28	32	0.4	0.4

Appendix

Table 5: Mechanism internals behind Figures 2 and 5 : the leakage each configuration incurs, the noise multiplier achieving it, and the binding pair. A dash: the bound is zero at that leakage; n/a: LPIPS is not evaluated on ImageNette.

k^{\star}

grows with

\gamma

overall up to single grid steps on CelebA.

	$\gamma$ (bits)	$0.72$	$2.89$	$8.01$	$72.13$
MNIST, pixel	$q=1$	$0.987$	$0.948$	$0.848$	$0.620$
	$(q,T)=(0.02,100)$	$1.006$	$0.984$	$0.921$	$0.690$
	bound	$0.831$	$0.673$	$0.397$	$0$
MNIST, LPIPS	$q=1$	$0.999$	$0.922$	$0.845$	$0.636$
	$(q,T)=(0.02,100)$	$1.001$	$0.964$	$0.926$	$0.681$
	bound	$0.816$	$0.653$	$0.396$	$0$

Appendix

Table 6: The attack against the bound:

\rho

over the

100

targets, bootstrap standard errors between

0.013

and

0.024

Figure 6: Per-target spread behind Figures 3 and 7 , for the single-step (circles) and subsampled (crosses) attack. Lines: the mean over the

100

targets; shaded: the

10

–

90

th percentile band of the per-target error at each leakage; faint points: every target. The bound is on expected error. At low leakage a sizeable fraction of individual targets fall below it (

9

–

40\%

\gamma\leq 0.72

bits,

1

–

11\%

2.89

bits, at most

3\%

8.01

bits), which the bound permits.

	$F(b)$ in equation 40	Lower-bounds	How evaluated	Gap to the row above
$\rho^{\star}$	$F_{\mathrm{cert}}=2^{\,2(h(\tilde{z}_{b})-\gamma)/k}$	every attack on every release leaking $\leq\gamma$	Proposition 5.1 at $\gamma=R$ , with its grid and margins	—
$\rho_{\mathrm{blk}}$	$F_{\mathrm{blk}}=2^{\,2(h(\tilde{z}_{b})-\gamma_{b})/k}$	every attack on this release	$k=1$ , $\nu^{2}=0.2$ , one-dimensional plug-ins equation 31 on $D_{\mathrm{est}}$ for $h(\tilde{z}_{b})$ and each $h(\tilde{z}_{b}\mid Q=c)$ ; point estimate; every cell must hold $20$ records, so $R\leq 8$ (pixel) and $R\leq 7$ (LPIPS)	per-block charge
$\rho_{\mathrm{cb}}$	—	—	cell-mean decoder; error on held-out targets, bootstrap standard error	residual slack of the Shannon lower bound at rate $\gamma_{b}$ , plus sampling error of the targets
$\rho_{\mathrm{dpsgd}}$	—	—	posterior mean under the empirical shadow prior ( Section G.5 ) on one full-batch step, at $\gamma=1/(2\ln 2\,\sigma^{2})$ bits, and on $T=100$ steps at $q=0.02$	what DP-SGD fails to convert into reconstruction

Appendix

Table 7: The chain equation 39 : what each term is, how it is evaluated, and what the gap between consecutive terms measures.

Figure 7: Tightness at fixed leakage on MNIST, in pixel (left) and LPIPS (right) error, as in Figure 3 : the chain equation 39 , with terms as in Table 7 . No attack crosses the bound.

\rho_{\mathrm{blk}}

is drawn while every codebook cell holds

20

estimation records. Dotted: the prior at

\rho=1

. On MNIST the attack reaches lower

\rho

than on CelebA at high leakage because the shadow sample contains near-duplicates of many held-out digits ( Figures 9 and 8 ).

$R$	$\rho^{\star}$	$\rho_{\mathrm{blk}}$	$\rho_{\mathrm{cb}}$ (SE)	$\rho_{\mathrm{blk}}-\rho^{\star}$	$\rho_{\mathrm{cb}}-\rho_{\mathrm{blk}}$
MNIST, pixel
$1$	$0.809$	$0.951$	$0.975$ ( $0.005$ )	$0.142$	$0.023$
$2$	$0.739$	$0.908$	$0.931$ ( $0.005$ )	$0.169$	$0.023$
$3$	$0.665$	$0.859$	$0.882$ ( $0.005$ )	$0.194$	$0.023$
$4$	$0.606$	$0.811$	$0.834$ ( $0.005$ )	$0.205$	$0.023$
$5$	$0.558$	$0.765$	$0.790$ ( $0.005$ )	$0.207$	$0.026$

Appendix

Table 8: Values behind Figures 3 and 7 , one block per panel. Gaps are computed before rounding.

Panel of Figure 8 — Figure 8: Attack reconstructions at each leakage, CelebA. As Figure 9 , for CelebA in pixel space (top) and LPIPS space (bottom). $D_{\mathrm{shadow}}$ holds no near duplicate of a held-out face, so the pixel $\rho$ levels off near $0.71$ beyond $\gamma\approx 70$ bits.

Panel of Figure 9 — Figure 9: Attack reconstructions at each leakage, MNIST. Outputs of the single-step attack of Section G.5 on $6$ fixed held-out targets at $7$ leakages, $\gamma\in\{0.2,0.72,2.89,8.01,30,72.13,500\}$ bits, in pixel space (top) and LPIPS space (bottom). Each column shows what reconstruction at its value of $\rho$ looks like in practice, so the bounds of Figures 2 and 5 can be read as images rather than numbers. In each panel the first column is the target and each further column is one leakage, headed by $\rho$ , the mean over all $100$ targets at that leakage. The LPIPS panel shows the feature estimate inverted to an image, headed by the feature-space $\rho$ . In pixel space most reconstructed digits are wrong at $\rho=0.85$ ( $\gamma=8$ bits) and all six are right at $\rho=0.65$ ( $\gamma=30$ bits). The attack outputs a weighted mix of shadow images, none of them close to a held-out target, so $\rho$ levels off near $0.62$ beyond $\gamma\approx 30$ bits.

Training Data Reconstruction Attacks

See all 17 papers

Sep 29, 2026

A Sharp Transition in Data Reconstruction under Differential Privacy

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

ρ\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

ρ\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

ρ\gg d

. Remarkably, the transition moves to

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

Max Cairney-Leeming, Simone Bombari, Marco Mondelli

Institute of Science and Technology Austria

Adversarial Attacks Training Data Reconstruction Attacks Differential Privacy Information-Theoretic Lower Bounds

Ask PDF

Oct 12, 2026

Can Rényi Accountants Beat Lossless Accountants for DP-SGD?

Recent frameworks in differential privacy (DP), such as privacy loss distributions and

f

-DP, provide lossless representations of the privacy leakage of mechanisms. These approaches are often considered to yield tighter

(\varepsilon, δ)

-DP guarantees than those obtained from relaxed notions such as Rényi DP. But is that always the case? We study this question for differentially private stochastic gradient descent (DP-SGD) with fixed-size batches under replace adjacency. Our key observation is that in this setting, privacy accounting based on Rényi DP can use a pair of worst-case distributions (i.e., a dominating pair) that differs from the one used in the lossless frameworks. In particular, we characterize the worst-case distributions as two-dimensional Gaussian mixtures and derive an improved Rényi DP bound for DP-SGD. Numerical and asymptotic comparisons show that across various hyperparameter settings, a Rényi DP accountant based on the new bound can yield better privacy guarantees than those obtained from the lossless frameworks.

Jinho Bok

Department of Statistics and Data Science, University of Pennsylvania.

Differential Privacy Differentially Private Stochastic Gradient Descent

Ask PDF

May 25, 2026

From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms

Understanding the relationship between generalization and privacy remains a challenge in modern machine learning theory, particularly for deep networks that are trained by variants of differentially private stochastic gradient descent (DP- SGD). In this work we make progress on this persistent open problem. First, we derive explicit upper bounds on the approximate max-information of any algorithm that fulfills

(ε, δ)

-differential privacy or Rényi differential privacy, thereby going beyond the classical results for pure

ε

-differential privacy. Subsequently, we show even stronger guarantees for two common private learning algorithms, output perturbation with the Gaussian mechanism, and streaming DP-SGD, by exploiting the structure of their internal randomization. As an application of our results, we demonstrate how to obtain non-vacuous PAC-Bayes generalization bounds for deep networks, in which the prior distribution is learned by DP-SGD instead of the classical way of choosing it in a data-independent way.

Christoph H. Lampert, Max Cairney-Leeming, Hossein Zakerinia

Institute of Science and Technology Austria (ISTA) Klosterneuburg, Austria

PAC-Bayesian Generalization Bounds Differentially Private Stochastic Gradient Descent Information-Theoretic Generalization Bounds Differential Privacy

Ask PDF

Abstract

Training Data Reconstruction Attacks

Explore similar work

A Sharp Transition in Data Reconstruction under Differential Privacy

Can Rényi Accountants Beat Lossless Accountants for DP-SGD?

From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms